.co This is the `source form' of the user documentation for Gofer, to be .co processed using my simple prn formatter before being printed. .co .co Mark P. Jones August 1991 .co-------------------------------------------------------------------| .>ch00 .op .ti Introduction to Gofer __________ __________ __________ __________ ________ / _______/ / ____ / / _______/ / _______/ / ____ \ / / _____ / / / / / /______ / /______ / /___/ / / / /_ / / / / / / _______/ / _______/ / __ __/ / /___/ / / /___/ / / / / /______ / / \ \ /_________/ /_________/ /__/ /_________/ /__/ \__\ Functional programming environment, Version 2.20 Copyright Mark P Jones 1991. A N I N T R O D U C T I O N T O G O F E R draft version only --- please report any errors, suggestions for improvements, extensions (or deletions!) to jones-mark@cs.yale.edu This version includes a number of small corrections made since the original release. -------------------------------------------------------------------- Permission to use, copy, modify, and distribute this software and its documentation for any personal or educational use without fee is hereby granted, provided that: a) This copyright notice is retained in both source code and supporting documentation. b) Modified versions of this software are redistributed only if accompanied by a complete history (date, author, description) of modifications made; the intention here is to give appropriate credit to those involved, whilst simultaneously ensuring that any recipient can determine the origin of the software. c) The same conditions are also applied to any software system derived either in full or in part from Gofer. The name "Gofer" is not a trademark, registered or otherwise, and you are free to mention this name in published material, public and private correspondence, or other documents without restriction or obligation. Gofer is provided "as is" without express or implied warranty. -------------------------------------------------------------------- .pa .po .pn -100 T A B L E O F C O N T E N T S .in contents .pa .pn 1 .co-------------------------------------------------------------------| .>ch01 .ST 1. INTRODUCTION Gofer is a functional programming environment (in other words, an interpreter) that I have implemented for my own personal use as part of my research into `qualified types'. Nevertheless, the system is sufficiently complete for me to believe that Gofer may be of interest and use to others interested in the field of functional programming. These notes give a brief introduction to the Gofer system and include some examples of Gofer programs. They are not the notes that I originally intended to write, being somewhat longer and perhaps more tutorial in nature. Nevertheless, you will not be able to learn functional programming from this document alone. A number of useful references are given in the reading list at the end of this document. In particular, the book by Bird and Wadler [1] is particularly good as a general introduction to the use, techniques and theory of functional programming. Although their notation is a little different from the language used by Gofer, it is a relatively straightforward task to translate between the two, and some suggestions for this are given in a appendix D. More importantly, the underlying semantics of Gofer do correspond to those expected by the authors of [1]. Whereas the work involved in investigating and implementing the ideas on which Gofer is based were motivated largely by my own program of work, the writing of these notes has rather more to do with the hope that Gofer will be useful to others. I would therefore be very grateful for any feedback on any aspect of the these notes (or of the Gofer system itself). Please let me know if you discover any errors, or if you find particular sections of these notes rather hard to follow. Suggestions for improvements or extensions are more than welcome. .pa .co-------------------------------------------------------------------| .>ch02 .ST 2. BACKGROUND AND ACKNOWLEDGEMENTS The language supported by Gofer is both syntactically and semantically similar to that of the functional programming language Haskell [5]. My principal task in the implementation of Gofer has therefore been to decide which features I should omit and then to implement what remains. Features common to both include: o Non-strict semantics (lazy evaluation). o Higher-order functions. o Extended polymorphic type system with support for user-defined overloading. o User-defined algebraic datatypes. o Pattern matching. o List comprehensions. o Facilities for I/O, whilst retaining referential transparency within a program. For the benefit of readers familiar with Haskell, the following features of Haskell are not supported in the standard version of Gofer: o Modules. o Arrays. o Defaults for unresolved overloading. o Derived instances of standard classes. o Contexts in datatype definitions. o Full range of numeric types and classes. But Gofer is not just a partial implementation of Haskell; it also includes a number of experimental features which extend the type system in several ways: o An alternative approach to type classes which avoids the need for construction of dictionaries during the evaluation of an expression. o Type classes may take multiple parameters. o Instances of type classes may be defined at arbitrary non-overlapping types. o Contexts may include arbitrary type expressions. These extensions stem from my own research [8, 9, 10, 11, 12] and were among the principal motivations for the development of Gofer. Full details of the differences between Gofer and Haskell 1.1 are given in appendix C. Gofer would not have been implemented without my original introduction to functional programming using Orwell [6], and I am particularly grateful to Quentin Miller for answering so many of my questions about functional programming and about the Orwell system in particular. I should also like to mention the influence of the Haskell B. compiler from Lennart Augustsson and Thomas Johnsson and based on their earlier LML compiler [7]. Right from the beginning, I wanted to be able to use Gofer on a range of machines - and in particular, on the humble PC that I use at home. With this in mind, Gofer was actually developed on that same PC using Borland's Turbo C 1.5 and a public domain version of the yacc parser generator that I picked up some time ago. Gofer was also written with some degree of portability in mind and has subsequently been compiled to run on Sun workstations. I hope it will also be possible to port it to other platforms. It is my intention that Gofer be distributed complete with source code and I hope that this will be of interest to some users. Many of the ideas used in the back-end of the Gofer system (i.e. the compiler and abstract machine) originate from the chapters of Simon Peyton Jones textbook [2]; I very much doubt whether Gofer would have been completed without frequent reference to that book. The lambda-lifter used in Gofer is based on Thomas Johnsson's algorithm described in [3]. On the theoretical side, I'm grateful to Phil Wadler for the encouragement that he has given me with my work on qualified types. Many of the basic ideas that I have used were inspired by his original paper motivating the use of type classes [4]. .pa .co-------------------------------------------------------------------| .>ch03 .ST 3. STARTING GOFER The Gofer interpreter is usually entered by giving the command `gofer', after which a display something like the following will normally be produced: Gofer Version 2.20 Reading script file "/gofer/prelude": Parsing........................................................ Dependency analysis............................................ Type checking.................................................. Compiling...................................................... Gofer session for: /gofer/prelude Type :? for help ? The file name "/gofer/prelude" mentioned in the output above is the name of a file of standard definitions which are loaded into Gofer each time that the interpreter is started. By default, Gofer reads these definitions from a file called "prelude" in the current working directory. Alternatively you can set the environment variable GOFER to the name of the standard prelude file, which will then be used, whatever the current working directory might be. Most commands in Gofer take the form of a colon followed by one or more characters which distinguish one command from another. There are two commands which are particularly worth remembering: o :q exits the Gofer interpreter. On most systems, you can also exit from Gofer by typing the end of file character (^Z on an MS-DOS machine, usually ^D on a unix based machine). o :? prints a list of all the commands, which can be useful if you forget the name of the command that you want to use. The complete range of commands supported by the Gofer interpreter is described in appendix F. Note that the interrupt key (^C on most systems) can be used at any time whilst using Gofer to abandon the process of reading in a file of function definitions or the evaluation of an expression. When the interrupt key is detected, Gofer prints the string "{Interrupted!}" and prints the "? " prompt so that further commands can be entered. .pa .co-------------------------------------------------------------------| .>ch04 .ST 4. USING GOFER - A BASIC INTRODUCTION Using Gofer is rather like using a high-level programmable calculator; Once the interpreter is loaded, the system prints a prompt "?" and waits for you to enter an expression, and then press the enter (return) key. Once the input is complete, Gofer evaluates the expression and prints its value on the terminal, before returning to the original prompt and waiting for the next expression. For example: ? (2+3)*8 40 (5 reductions, 9 cells) ? sum [1..10] 55 (91 reductions, 130 cells) ? In the first example, the user entered the expression "(2+3)*8", which was evaluated by Gofer and the result "40" printed on the terminal. At the end of any calculation, Gofer displays the number of reductions (a measure of the amount of work) and cells (a measure of the amount of memory) that were used during the calculation. These figures can be useful for comparing the performance of different ways of carrying out the same calculation. In the second example, the user typed the expression "sum [1..10]". The notation "[1..10]" represents the list of integers between 1 and 10 inclusive, and "sum" is a standard function which can be used to determine the sum of a list of integers. Thus the result obtained by Gofer is: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55 We could have typed this sum into Gofer directly: ? 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 55 (10 reductions, 23 cells) ? and this calculation is certainly more efficient as it uses only 1/9th of the number of reductions and 1/5th of the number of cells as the original calculation. On the other hand, the original expression is much shorter and you are much less likely to make a mistake typing in the expression "sum [1..200]" than you would be if you tried to enter the sum of the integers from 1 to 200 directly. You will learn more about the kind of expressions that can be entered into Gofer in the rest of this document. .pa .co-------------------------------------------------------------------| .>ch05 .ST 5. STANDARD AND USER-DEFINED FUNCTIONS The function "sum" used in the examples above, and indeed the addition and multiplication functions (+) and (*), are all standard functions which are included as part of a large collection of functions called the `standard prelude' which are loaded into the Gofer system each time that you start the interpreter. Quite a number of useful calculations can be carried out using these functions alone, but for more general use you can also define your own functions and store the definitions in a file so that these functions can be loaded and used by by the Gofer system. For example, suppose that you create a file "fact" containing the following definition: fact n = product [1..n] The "product" function is another standard function which can be used to calculate the product of a list of integers, and so the line above defines a function "fact" which calculates the factorial of its argument. In standard mathematical notation, fact n = n! which is usually defined informally by an equation of the form: n! = 1 * 2 * ... * (n-1) * n Once you become familiar with the notation used by Gofer, you will see that the Gofer definition of the factorial function is really very similar to this informal mathematical definition. In order to use this definition from the Gofer interpreter, we must first load the definitions of the file into the interpreter. The simplest way to do this uses the ":l" command: ? :l fact Reading script file "fact": Parsing...................................................... Dependency analysis.......................................... Type checking................................................ Compiling.................................................... Gofer session for: /gofer/prelude fact ? Notice the list of filenames displayed after "Gofer session for:"; this tells you which files of definitions are currently being used by Gofer, the first of which is the file containing the definitions for the standard prelude. Since the file containing the definition of the factorial function has now been loaded, we can make use of this function in expressions entered to the interpreter: ? fact 6 720 (57 reductions, 85 cells) For another example, recall the standard mathematical formula which tells us that the number of ways of choosing r objects from a collection of n objects is given by n! / (r! * (n-r)!). In Gofer, this function can be defined by: comb n r = fact n /(fact r * fact (n-r)) In order to use this function, we can either edit the file "fact" which contains the definition of the factorial function, adding the definition of "comb" on a new line, or we can include the definition as part of an expression entered whilst using Gofer: ? comb 5 2 where comb n r = fact n /(fact r * fact (n-r)) 10 (110 reductions, 161 cells) ? The ability to define a function as part of an expression like this is often quite useful. However, if the function "comb" were likely to be wanted on a number of occasions, it would be more sensible to add its definition to the contents of the file "fact", instead of having to repeat the definition each time it is used. You will learn more about the functions defined in the standard prelude and find out how to define your own functions in the following sections. .pa .co-------------------------------------------------------------------| .>ch06 .ST 6. FUNCTION NAMES - IDENTIFIERS AND OPERATORS As the examples of the previous section show, there are two kinds of name that can be used for a function; identifiers such as "sum" and operator symbols such as "+" and "*". Choosing the appropriate kind of name for a particular function can often help to make expressions involving that function easier to read. If for example the addition function was represented by the name "plus" rather than the operator symbol "+" then the sum of the integers from 1 to 5 would have to be written as: plus (plus (plus (plus 1 2) 3) 4) 5 In this particular case, another way of writing the same sum is: plus 1 (plus 2 (plus 3 (plus 4 5))) Not only does the use of the identifier "plus" make these expressions larger and more difficult to read than the equivalent expressions using "+"; it also makes it very much harder to see that these two expressions do actually have the same value. Gofer distinguishes between the two types of name according to the way that they are written: o An identifier begins with a letter of the alphabet optionally followed by a sequence of characters, each of which is either a letter, a digit, an apostrophe (') or an underbar (_). Identifiers representing functions or variables must begin with a lower case letter (identifiers beginning with an upper case letter are used to denote a special kind of function called a `constructor function' described in section 11.1). The following identifiers are examples of Gofer variable and function names: sum f f'' integerSum african_queen do'until'zero The following identifiers are reserved words in Gofer and cannot be used as the name of a function or variable: case of where let in if then else data type infix infixl infixr primitive class instance o An operator symbol is written using one or more of the following symbol characters: : ! # $ % & * + . / < = > ? @ \ ^ | - In addition, the tilde character (~) is also permitted, although only in the first position of an operator name. [N.B. Haskell also makes the same restriction for the minus/dash character (-)]. Operator names beginning with a colon are used for constructor functions in the same way as identifiers beginning with a capital letter as mentioned above. In addition, the following operator symbols have special uses in Gofer: :: = .. @ \ | <- -> ~ => All other operator symbols can be used as variables or function names, including each of the following examples: + ++ && || <= == /= // . ==> $ @@ -*- \/ /\ ... ? [Note that each of the symbols in the first line is used in the standard prelude. If you are interested in using Gofer to develop programs for use with a Haskell compiler, you might also want to avoid using the operator symbols := ! :+ and :% which are used to support features in Haskell not currently provided by the Gofer standard prelude.] Gofer provides two simple mechanisms which make it possible to use an identifier as an operator symbol, or an operator symbol as an identifier: o Any identifier will be treated as an operator symbol if it is enclosed in backquotes (`) -- for example, the expressions using the "plus" function above are a little easier to read using this technique: (((1 `plus` 2) `plus` 3) `plus` 4) `plus` 5 In general, an expression of the form "x `op` y" is equivalent to the corresponding expression "op x y", whilst an expression such as "f x y z" can also be written as "(x `f` y) z". [NOTE: For those using Gofer on a PC, you may find that your keyboard does not have a backquote key! In this case you should still be able to enter a backquote by holding down the key marked ALT, pressing the keys '9' and then '6' on the numeric keypad and then releasing the ALT key.] o Any operator symbol can be treated as an identifier by enclosing it in parentheses. For example, the addition function denoted by the operator symbol "+" is often written as "(+)". Any expression of the form "x + y" can also be written in the form "(+) x y". There are two more technical problems which have to be dealt with when working with operator symbols: o Precedence: Given operator symbols (+) and (*), should "2 * 3 + 4" be treated as either "(2 * 3) + 4" or "2 * (3 + 4)"? This problem is solved by assigning each operator a precedence value (an integer in the range 0 to 9). In a situation such as the above, we simply compare the precedence values of the operators involved, and carry out the calculation associated with the highest precedence operator first. The standard precedence values for (+) and (*) are 6 and 7 respectively so that the expression above will actually be treated as "(2 * 3) + 4". o Grouping: The above rule is only useful when the operator symbols involved have distinct precedences. For example, should the expression "1 - 2 - 3" be treated as either "(1 - 2) - 3" giving a result of -4, or as "1 - (2 - 3)" giving a result of 2? This problem is solved by giving each operator a `grouping' (sometimes called its associativity). An operator symbol (-) is said to: o group to the left if "x - y - z" is treated as "(x - y) - z" o group to the right if "x - y - z" is treated as "x - (y - z)" A third possibility is that an expression of the form "x - y - z" is to be treated as ambiguous and will be flagged as a syntax error. In this case we say that the operator (-) is non-associative. The standard approach in Gofer is to treat (-) as grouping to the left so that "1 - 2 - 3" will actually be treated as "(1-2)-3". By default, every operator symbol in Gofer is treated as non-associative with precedence 9. These values can be changed by a declaration of one of the following forms: infixl digit ops to declare operators which group to the left infixr digit ops to declare operators which group to the right infix digit ops to declare non-associative operators In each of these declarations ops represents a list of one or more operator symbols separated by commas and digit is an integer between 0 and 9 which gives the precedence value for each of the listed operator symbols. The precedence digit may be omitted in which case a value of 9 is assumed. There are a number of restrictions on the use of these declarations: o Operator declarations can only appear in files of function definitions which are loaded into Gofer; they cannot be entered directly whilst using the Gofer interpreter. o At most one operator declaration is permitted for any particular operator symbol (even if repeated declarations all specify the same precedence and grouping as the original declaration). o Any file containing a declaration for an operator precedence and grouping must also contain a (top-level) declaration for that operator. In theory, it is possible to use an operator declaration at any point in a file of definitions. In practice, it is sensible to ensure that each operator is declared before the symbol is used. One way to guarantee this is to place all operator declarations at the beginning of the file [this condition is enforced in Haskell]. Note that until an operator declaration for a particular symbol is encountered, any occurrence of that symbol will be treated as a non-associative operator with precedence 9. The following operator declarations are taken from the standard prelude: -- Operator precedence table infixl 9 !! infixr 9 . infixr 8 ^ infixl 7 * infix 7 /, `div`, `rem`, `mod` infixl 6 +, - infix 5 \\ infixr 5 ++, : infix 4 ==, /=, <, <=, >=, > infix 4 `elem`, `notElem` infixr 3 && infixr 2 || and their use is illustrated by the following examples: Expression: Equivalent to: Reasons: ----------- -------------- -------- 1 + 2 - 3 (1 + 2) - 3 (+) and (-) have the same precedence and group to the left. x : ys ++ zs x : (ys ++ zs) (:) and (++) have the same precedence and group to the right x == y || z (x == y) || z (==) has higher precedence than (||). 3 * 4 + 5 (3 * 4) + 5 (*) has higher precedence than (+). y `elem` z:zs y `elem` (z:zs) (:) has higher precedence than elem. 12 / 6 / 3 syntax error ambiguous use of (/); could mean either (12/6)/3 or 12/(6/3). Note that function application always binds more tightly than any infix operator symbol. For example, the expression "f x + g y" is equivalent to "(f x) + (g y)". Another example which often causes problems is the expression "f x + 1", which is treated as "(f x) + 1" and not as "f (x+1)" as is sometimes expected. .pa .co-------------------------------------------------------------------| .>ch07 .ST 7. BUILT-IN TYPES An important part of Gofer is the type system which is used to detect errors in expressions and function definitions. Starting with primitive expressions such as numeric constants, Gofer assigns a type to each expression that describes the kind of value represented by the expression. In general we write object :: type to indicate that a particular expression has the indicated type. For example: 42 :: Int indicating that 42 is an integer (Int is the name for the type of integer values). fact :: Int -> Int indicating that "fact" is a function which takes an integer argument and returns an integer value (its factorial). The most important property of the type system is that it is possible to determine the type of an expression without having to evaluate it. For example, the information given above is sufficient to determine that fact 42 :: Int without needing to calculate 42! first. Gofer has a wide range of built-in types, described in the following sections. In addition, Gofer also includes facilities for defining new types as well as types acting as abbreviations for complicated type expressions as described in section 11. .ST 7.1 Functions -------------- If t1 and t2 are types then t1 -> t2 is the type of a function which, given an argument of type t1 produces a result of type t2. A function of type t1 -> t2 is said to have argument type t1 and result type t2. In mathematics, the result of applying a function f to an argument x is traditionally written as f(x). In many situations, these parentheses are unnecessary and may be omitted when using Gofer. e.g. if f :: t1 -> t2 and x :: t1 then f x is the result of applying f to x and has type t2. If t1, t2, ..., tn are type expressions then: t1 -> t2 -> ... -> tn can be used as an abbreviation for the type: t1 -> (t2 -> ( ... -> tn) ...) In a similar way, an expression of the form f x1 x2 ... xn is simply an abbreviation for the expression ( ... ((f x1) x2) ... xn). These two conventions allow us to deal with functions taking more than one argument rather elegantly. For example, the type of the addition function (+) is: Int -> Int -> Int In other words, "(+)" is a function which takes an integer argument and returns a value of type (Int -> Int). For example, "(+) 5" is the function which takes an integer value n and returns the value of the integer n plus 5. Hence "(+) 5 4", which is equivalent to "5 + 4", evaluates to the integer 9 as expected. .ST 7.2 Booleans ------------- Represented by the type "Bool", there are two boolean values written as "True" and "False". The standard prelude includes several useful functions for manipulating boolean values: (&&), (||) :: Bool -> Bool -> Bool The value of the expression b && d is True if and only if both b and d are True. If b is False then d is not evaluated. The value of the expression b || d is True if either of b or d is True. If b is True then d is not evaluated. not :: Bool -> Bool The value of the expression not b is the opposite boolean value to that of b; not True = False, not False = True. Gofer includes a special form of `conditional expression' which enables an expression to select between two alternatives according to the value of a boolean expression: if b then t else f is an expression which is equivalent to t if b evaluates to True, or to f if b evaluates to False. Note that an expression of this form is only acceptable if b is an expression of type Bool and if the types of t and f are the same, in which case the whole expression also has that type. .ST 7.3 Integers ------------- Represented by the type "Int", the integer type includes both positive and negative integers such as -273, 0 and 383. Like many computer systems, the range of integer values that can be used is restricted and calculations using large positive or negative numbers may lead to (undetected) overflow. A wide range of operators and functions are defined in the standard prelude for use with integers: (+) addition. (*) multiplication. (-) subtraction. (^) raise to power. negate unary negation. An expression of the form "-x" is treated as the expression "negate x". (/) integer division. div " " rem remainder, related to integer division by the law: (x `div` y)*y + (x `rem` y) == x mod modulo, like remainder except that the modulo has the same sign as the divisor. odd returns True if argument is odd, False otherwise. even returns True if argument is even, False otherwise. gcd returns the greatest common divisor of its two arguments. lcm returns the least common multiple of its two arguments. abs returns the absolute value of its argument. signum returns -1, 0 or 1 indicating that its argument is negative, zero or positive respectively. The less familiar operators are illustrated by the following identities: 3^4 == 81, 7 `div` 3 == 2, even 23 == False 7 `rem` 3 == 1, -7 `rem` 3 == -1, 7 `rem` -3 == 1 7 `mod` 3 == 1, -7 `mod` 3 == 2, 7 `mod` -3 == -2 gcd 32 12 == 4, abs (-2) == 2, signum 12 == 1 .ST 7.4 Floating point numbers --------------------------- Represented by the type "Float", elements of this type can be used to represent fractional values as well as very large or very small quantities. Such values are however usually only accurate to a fixed number of digits and rounding errors may occur in some calculations making significant use of floating point quantities. A numeric value in an input expression will only be treated as a floating point number if it either includes a decimal point such as 3.14159, or if the number is too large to be stored as a value of type Int. Scientific notation may also be used to enter floating point quantities; for example 1.0e3 is equivalent to 1000.0, whilst 5.0e-2 is equivalent to 0.05. [N.B. floating point numbers are not included in all implementations of Gofer]. .ST 7.5 Characters --------------- Represented by the type "Char", elements of this type represent individual characters such as those entered at a keyboard. Character values are written as single characters enclosed by apostrophe characters: e.g. 'a', '0', 'Z'. Some special characters must be entered using an `escape code'; each of these begins with a backslash character '\', followed by one or more characters to select the required character. Some of the most useful escape codes are: '\\' backslash '\'' apostrophe '\"' double quote '\n' newline '\b' or '\BS' backspace '\DEL' delete '\t' or '\HT' tab '\a' or '\BEL' alarm (bell) '\f' or '\FF' formfeed Additional escape characters include: '\^c' control character, where c is replaced by one of the characters: "@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_" For example, '\^A' represents control-A '\number' representing the character with ASCII value specified by the given decimal 'number'. '\onumber' representing the character with ASCII value specified by the given octal 'number'. '\xnumber' representing the character with ASCII value specified by the given 'hexadecimal' number. '\name' named ASCII control character, where `name' is replaced by one of the standard ascii names e.g. `\DC3`. In contrast with some common languages (such as C, for example) character values are quite distinct from integers; however the standard prelude does include functions: ord :: Char -> Int chr :: Int -> Char which enable you to map a character to its corresponding ASCII value, or from an ASCII value to the corresponding character: ? ord 'a' 97 (2 reductions, 6 cells) ? chr 65 'A' (2 reductions, 7 cells) ? .ST 7.6 Lists ---------- If a is a type then [a] is the type whose elements are lists of values of type a. There are several ways of writing list expressions: o The simplest list of any type is the empty list, written []. o Non-empty lists can be constructed either by explicitly listing the members of the list (for example: [1,3,10]) or by adding a single element onto the front of another list using the (:) operator (pronounced "cons"). These notations are equivalent: [1,3,10] = 1 : [3,10] = 1 : 3 : [10] = 1 : 3 : 10 : [] (the (:) operator groups to the right so 1 : 3 : 10 : [] is equivalent to (1:(3:(10:[]))) -- a list whose first element is 1, second element is 3 and last element is 10). The standard prelude includes a wide range of functions for calculations involving lists. For example: o length xs returns the number of elements in the list xs. o xs ++ ys returns the list of elements in xs followed by the elements in ys o concat xss returns the list of elements in each of the lists in xss o map f xs returns the list of values obtained by applying the function f to each of the values in the list xs in turn. Here are some examples using these functions: ? length [1,3,10] 3 (15 reductions, 28 cells) ? [1,3,10] ++ [2,6,5,7] [1, 3, 10, 2, 6, 5, 7] (19 reductions, 77 cells) ? concat [[1], [2,3], [], [4,5,6]] [1, 2, 3, 4, 5, 6] (29 reductions, 93 cells) ? map ord ['H', 'e', 'l', 'l', 'o'] [72, 101, 108, 108, 111] (22 reductions, 73 cells) ? Note that all of the elements in a list must be of the same type, so that an expression such as ['a', 2, False] is not permitted. [ASIDE: At this point it might be useful to mention an informal convention that is used by a number of functional programmers when choosing names for variables representing elements of lists, lists themselves, lists of lists and so on. If for example, a typical element of a list is called x, then it is often useful to use the name xs for a list of such values, suggesting that a list contains a number of "x"s. Similarly, a list of lists might be called xss. Once you have understood this convention it is much easier to remember the relationship between the variables in the expression (x:xs) than it would be if different names had been used such as (a:b).] .ST 7.7 Strings ------------ A string is treated as a list of characters and the type String is simply an abbreviation for the type [Char]. Strings are written as sequences of characters enclosed between speech marks. All of the escape codes that can be used for characters may also be used in a string: ? "hello, world" hello, world (0 reductions, 13 cells) ? "hello\nworld" hello world (0 reductions, 12 cells) ? In addition, strings may contain the escape sequence "\&" which can be used to separate otherwise ambiguous pairs of characters within a string: e.g. "\123h" represents the string ['\123', 'h'] "\12\&3h" represents the string ['\12', '3', 'h'] A string expression may be spread over a number of lines using a gap -- a non-empty sequence of space, tab and new line characters enclosed by backslash characters: ? "hell\ \o" hello (0 reductions, 6 cells) ? Notice that strings are printed differently from other values, which gives the programmer complete control over the format of the output produced by a program. The only values that Gofer can in fact display on the terminal are strings. If the type of an expression entered into Gofer is equivalent to String then the expression is printed directly by evaluating and printing each character in the list in sequence. Otherwise, the expression to be evaluated, e, is replaced by the expression show' e where show' is a built-in function (defined as part of the standard prelude) which converts any value to a printable representation. The only way of printing a string value in the same way as any other value is by explicitly using the show' function: ? show' "hello" "hello" (7 reductions, 24 cells) ? The careful reader may have been puzzled by the fact the number of reductions used in the first three examples above was zero. This is in fact quite correct since these expressions are constants and no further evaluation can be carried out. For constant expressions of any other type there will always be at least one reduction needed to print the value since the constant must first be translated to a printable representation using the show' function. Because strings are represented as lists of characters, all of the standard prelude functions for manipulating lists can also be used with strings: ? length "Hello" 5 (22 reductions, 36 cells) ? "Hello, " ++ "world" Hello, world (8 reductions, 37 cells) ? concat ["super","cali","fragi","listic"] supercalifragilistic (29 reductions, 101 cells) ? map ord "Hello" [72, 101, 108, 108, 111] (22 reductions, 69 cells) ? .ST 7.8 Tuples and the unit type ----------------------------- If t1, t2, ..., tn are types and n>=2, then there is a type of n-tuples written (t1, t2, ..., tn) whose elements are also written in the form (x1, x2, ..., xn) where the expressions x1, x2, ..., xn have types t1, t2, ..., tn respectively. e.g. (1, [2], 3) :: (Int, [Int], Int) ('a', False) :: (Char, Bool) ((1,2),(3,4)) :: ((Int, Int), (Int, Int)) Note that, unlike lists, the elements in a tuple may have different types, although the number of elements in the tuple is fixed. The unit type is written () and has a single element which is also written as (). The unit type is of particular interest in theoretical treatments of the type system of Gofer, although you may occasionally find a use for it in practical programs. .pa .co-------------------------------------------------------------------| .>ch08 .ST 8. ERRORS .ST 8.1 Errors detected on input ----------------------------- After an expression has been entered, but before any attempt is made to evaluate it, Gofer carries out a number of checks to make sure that the expression that you typed does not contain any errors. Here are some examples of the kind of problem that might occur: o Syntax errors. The most common situation in which this happens is when you make a typing mistake, either leaving out some characters, or perhaps pressing the wrong keys instead. In the following example, the user has missed out a `[' character: ? sum 1..100] ERROR: Syntax error in input (unexpected `..') ? o Undefined variables. This happens when you enter an expression using a variable or function name that is not defined in any of the files of definitions loaded into Gofer. This can often mean that you have misspelt the name of a function, or that the files defining a function have not yet been loaded. For example: ? sum [1..n] ERROR: Undefined variable "n" ? o Type errors. Certain expressions are sensible only when the functions used in those expressions are applied to values of the appropriate type. For example, whilst the factorial function can be used to calculate the factorial of an integer, it is clearly meaningless to try to determine the factorial of a character value. This kind of problem can be detected using the types of the components of an expression. In the expression "fact 'A'", we can see that the argument 'A' has type Char which does not match the argument type Int of the factorial function. This error will be detected by Gofer if you try to evaluate the expression: ? fact 'A' ERROR: Type error in application *** expression : fact 'A' *** term : 'A' *** type : Char *** does not match : Int ? .ST 8.2 Errors during evaluation ----------------------------- If no errors are detected in an input expression, Gofer then begins to evaluate that expression. Despite all of the checks that are carried out before the evaluation begins, it is still possible for an error to occur during the evaluation of an expression. A typical example of this is an attempt to divide a number by zero. In this case, Gofer prints the part of the expression being evaluated that caused the error, surrounded by braces `{' and `}': ? 3/0 {primDivInt 3 0} (4 reductions, 30 cells) ? [The function "primDivInt" which appears here is a primitive function used to divide one integer (its first argument) by another (the second)]. If an error occurs in just one part of an expression, only the part causing the problem will be displayed: ? 4 + (5/0) {primDivInt 5 0} (5 reductions, 32 cells) ? A standard function called "error" is defined in the standard prelude which is often useful for ensuring that appropriate error messages are produced when an error occurs: ? error "Problem has occurred" {error "Problem has occurred"} (23 reductions, 99 cells) ? .pa .co-------------------------------------------------------------------| .>ch09 .ST 9. MORE ABOUT VALUE DECLARATIONS .ST 9.1 Simple pattern matching ---------------------------- Although the Gofer standard prelude includes many useful functions, you will usually need to define a collection of new functions for specific problems and calculations. The declaration of a function "f" usually takes the form of a number of equations of the form: f ... = (or an equivalent expression, if "f" is written as by an operator symbol). Each of the expressions , , ..., represents an argument to the function "f" and is called a `pattern'. The number of such arguments is called the arity of "f". If "f" is defined by more than one equation then they must be entered together and each one must give the same arity for "f". When a function is defined by more than one equation, it will usually be necessary to evaluate one or more of the arguments to the function to determine which equation applies. This process is called `pattern-matching'. In all of the previous examples we have used only the simplest kind of pattern -- a variable. As an example, consider the factorial function defined in section 5: fact n = product [1..n] If we then wish to evaluate the expression "fact 6" we first match the expression "6" against the pattern "n" and then evaluate the expression obtained from "product [1..n]" by replacing the variable "n" with the expression "6". The process of matching the arguments of a function against the patterns in its definition and obtaining another expression to be evaluated is called a `reduction'. Using Gofer, it is easy to verify that the evaluation of "fact 6" takes one more reduction than that of "product [1..6]": ? fact 6 720 (57 reductions, 85 cells) ? product [1..6] 720 (56 reductions, 85 cells) ? Many kinds of constants such as the boolean values True and False can also be used in patterns, as in the following definition of the function "not" taken from the standard prelude: not True = False not False = True In order to determine the value of an expression of the form "not b", we must first evaluate the expression "b". If the result is "True" then we use the first equation and the value of "not b" will be "False". If the value of "b" is "False", then the second equation is used and the value of "not b" will be "True". Other constants, including integers, characters and strings may also be used in patterns. For example, if we define a function "hello" by: hello "Mark" = "Howdy" hello name = "Hello " ++ name ++ ", nice to meet you!" then: ? hello "Mark" Howdy (1 reduction, 12 cells) ? hello "Fred" Hello Fred, nice to meet you! (13 reductions, 66 cells) ? Note that the order in which the equations are written is very important because Gofer always uses the first applicable equation. If instead we had defined the function with the equations: hello name = "Hello " ++ name ++ ", nice to meet you!" hello "Mark" = "Howdy" then the results obtained using this function would have been a little different: ? hello "Mark" Hello Mark, nice to meet you! (13 reductions, 66 cells) ? hello "Fred" Hello Fred, nice to meet you! (13 reductions, 66 cells) ? There are a number of other useful kinds of pattern, some of which are illustrated by the following examples: o Wildcard: _ matches any value at all; it is like a variable pattern, except that there is no way of referring to the matched value. o Tuples: (x,y) matches a pair whose first and second elements are called x and y respectively. o Lists: [x] matches a list with precisely one element called x. [_,2,_] matches a list with precisely three elements, the second of which is the integer 2. [] matches the empty list. (x:xs) matches a non-empty list with head x and tail xs. o As patterns: p@(x,y) matches a pair whose first and second components are called x and y. The complete pair can also be referred to directly as p. o (n+k) patterns: (m+1) matches an integer value greater than or equal to 1. The value referred to by the variable m is one less than the value matched. A further kind of pattern (called an irrefutable pattern) is introduced in section 9.11. Note that no variable name can be used more than once on the left hand side of each equation in a function definition. The following example: areTheyTheSame x x = True areTheyTheSame _ _ = False will not be accepted by the Gofer system, but should instead be defined using the notation of guards introduced in the next section: areTheyTheSame x y | x==y = True | otherwise = False .ST 9.2 Guarded equations ---------------------- Each of the equations in a function definition may contain `guards' which require certain conditions on the values of the function's arguments to be met. As an example, here is a function which uses the standard prelude function even :: Int -> Bool to determine whether its argument is an even integer or not, and returns the string "even" or "odd" as appropriate: oddity n | even n = "even" | otherwise = "odd" In general, an equation using guards takes the form: f x1 x2 ... xn | condition1 = e1 | condition2 = e2 . . | conditionm = em This equation is used by evaluating each of the conditions in turn until one of them evaluates to "True", in which case the value of the function is given by the corresponding expression e on the right hand side of the `=' sign. In Gofer, the variable "otherwise" is defined to be equal to "True", so that writing "otherwise" as the condition in a guard means that the corresponding expression will always be used if no previous guard has been satisfied. [ASIDE: in the notation of [1], the above examples would be written as: oddity n = "even", if even n = "odd", otherwise f x1 x2 ... xn = e1, if condition1 = e2, if condition2 . . = em, if conditionm Translation between the two notations is relatively straightforward.] .ST 9.3 Local definitions ---------------------- Function definitions may include local definitions for variables which can be used both in guards and on the right hand side of an equation. Consider the following function which calculates the number of distinct real roots for a quadratic equation of the form a*x*x + b*x + c = 0: numberOfRoots a b c | discr>0 = 2 | discr==0 = 1 | discr<0 = 0 where discr = b*b - 4*a*c [ASIDE: The operator (==) is used to test whether two values are equal or not. You should take care not to confuse this with the single `=' sign used in function definitions]. Local definitions can also be introduced at an arbitrary point in an expression using an expression of the form: let in For example: ? let x = 1 + 4 in x*x + 3*x + 1 41 (8 reductions, 15 cells) ? let p x = x*x + 3*x + 1 in p (1 + 4) 41 (7 reductions, 15 cells) ? .ST 9.4 Recursion with integers ---------------------------- Recursion is a particularly important and powerful technique in functional programming which is useful for defining functions involving a wide range of datatypes. In this section, we describe one particular application of recursion to give an alternative definition for the factorial function from section 5. Suppose that we wish to calculate the factorial of a given integer n. We can split the problem up into two special cases: o If n is zero then the value of n! is 1. o Otherwise, n! = 1 * 2 * ... * (n-1) * n = (n-1)! * n and so we can calculate the value of n! by calculating the value of (n-1)! and then multiplying it by n. This process can be expressed directly in Gofer using a conditional expression: fact1 n = if n==0 then 1 else n * fact1 (n-1) This definition may seem rather circular; in order to calculate the value of n!, we must first calculate (n-1)!, and unless n is 1, this requires the calculation of (n-2)! etc... However, if we start with some positive value for the variable n, then we will eventually reach the case where the value of 0! is required -- and this does not require any further calculation. The following diagram illustrates how 6! is evaluated using "fact1": fact1 6 ==> 6 * fact1 5 ==> 6 * (5 * fact1 4) ==> 6 * (5 * (4 * fact1 3)) ==> 6 * (5 * (4 * (3 * fact1 2))) ==> 6 * (5 * (4 * (3 * (2 * fact1 1)))) ==> 6 * (5 * (4 * (3 * (2 * (1 * fact1 0))))) ==> 6 * (5 * (4 * (3 * (2 * (1 * 1))))) ==> 6 * (5 * (4 * (3 * (2 * 1)))) ==> 6 * (5 * (4 * (3 * 2))) ==> 6 * (5 * (4 * 6)) ==> 6 * (5 * 24) ==> 6 * 120 ==> 720 Incidentally, there are several other ways of writing the recursive definition of "fact1" above in Gofer. For example, using guards: fact2 n | n==0 = 1 | otherwise = n * fact2 (n-1) or using pattern matching with an integer constant: fact3 0 = 1 fact3 n = n * fact3 (n-1) Which of these you use is largely a matter of personal taste. Yet another style of definition uses the (n+k) patterns mentioned in section 9.1: fact4 0 = 1 fact4 (n+1) = (n+1) * fact4 n which is equivalent to: fact5 n | n==0 = 1 | n>=1 = n * fact5 (n-1) [COMMENT: Although each of the above definitions gives the same result as the original "fact" function for each non-negative integer, the functions can still be distinguished by the values obtained when they are applied to negative integers: o "fact (-1)" evaluates to the integer 1. o "fact1 (-1)" causes Gofer to enter an infinite loop, which is only eventually terminated when Gofer runs out of `stack space'. o "fact4 (-1)" causes an evaluation error and prints the message {fact4 (-1)} on the screen. To most people, this suggests that the definition of "fact4" is perhaps preferable to that of either "fact" or "fact1" as it neither gives the wrong answer without allowing this to be detected nor causes a potentially non-terminating computation.] .ST 9.5 Recursion with lists ------------------------- The same kind of technique that can be used to define recursive functions with integers can also be used to define recursive functions on lists. As an example, suppose that we wish to define a function to calculate the length of a list. As the standard prelude already includes such a function called "length", we will call the function developed here "len" to avoid any conflict. Now suppose that we wish to find the length of a given list. There are two cases to consider: o If the list is empty then it has length 0 o Otherwise, it is non-empty and can be written in the form (x:xs) for some element x and some list xs. Thus the original list is one element longer than xs, and so has length 1 + len xs. Writing these two cases out leads directly to the following definition: len [] = 0 len (x:xs) = 1 + len xs The following diagram illustrates the way that this function can be used to determine the length of the list [1,2,3,4] (remember that this is just an abbreviation for 1 : 2 : 3 : 4 : []): len [1,2,3,4] ==> 1 + len [2,3,4] ==> 1 + (1 + len [3,4]) ==> 1 + (1 + (1 + len [4])) ==> 1 + (1 + (1 + (1 + len []))) ==> 1 + (1 + (1 + (1 + 0))) ==> 1 + (1 + (1 + 1)) ==> 1 + (1 + 2) ==> 1 + 3 ==> 4 As further examples, you might like to look at the following definitions which use similar ideas to define the functions product and map introduced in earlier sections: product [] = 1 product (x:xs) = x * product xs map f [] = [] map f (x:xs) = f x : map f xs .ST 9.6 Lazy evaluation -------------------- Gofer evaluates expressions using a technique sometimes described as `lazy evaluation' which means that: o No expression is evaluated until its value is needed. o No shared expression is evaluated more than once; if the expression is ever evaluated then the result is shared between all those places in which it is used. The first of these ideas is illustrated by the following function: ignoreArgument x = "I didn't need to evaluate x" Since the result of the function "ignoreArgument" doesn't depend on the value of its argument "x", that argument will not be evaluated: ? ignoreArgument (1/0) I didn't need to evaluate x (1 reduction, 31 cells) ? In some situations, it is useful to be able to force Gofer to evaluate the argument to a function before the function is applied. This can be achieved using the function "strict" defined in the standard prelude; An expression of the form "strict f x" is evaluated by first evaluating the argument "x" and then applying the function "f" to the result: ? strict ignoreArgument (1/0) {primDivInt 1 0} (4 reductions, 29 cells) ? The second basic idea behind lazy evaluation is that no shared expression should be evaluated more than once. For example, the following two expressions can be used to calculate 3*3*3*3: ? square * square where square = 3 * 3 81 (3 reductions, 9 cells) ? (3 * 3) * (3 * 3) 81 (4 reductions, 11 cells) ? Notice that the first expression requires one less reduction than the second. Excluding the single reduction step needed to convert each integer into a string, the sequences of reductions that will be used in each case are as follows: .cc 5 square * square where square = 3 * 3 -- calculate the value of square by reducing 3 * 3 ==> 9 -- and replace each occurrence of square with this result ==> 9 * 9 ==> 81 (3 * 3) * (3 * 3) -- evaluate first (3 * 3) ==> 9 * (3 * 3) -- evaluate second (3 * 3) ==> 9 * 9 ==> Lazy evaluation is a very powerful feature of programming in a language like Gofer, and means that only the minimum amount of calculation is used to determine the result of an expression. The following example is often used to illustrate this point. Consider the task of finding the smallest element of a list of integers. The standard prelude includes a function "minimum" which can be used for this very purpose: ? minimum [100,99..1] 1 (809 reductions, 1322 cells) ? (The expression [100,99..1] denotes the list of integers from 1 to 100 arranged in decreasing order, as described in section 10.1). A rather different approach involves sorting the elements of the list into increasing order (using the function "sort" defined in the standard prelude) and then take the element at the head of the resulting list (using the standard function "head"). Of course, sorting the list in its entirety is likely to require significantly more work than the previous approach: ? sort [100,99..1] [1, 2, 3, 4, 5, 6, 7, 8, ... etc ..., 99, 100] (10712 reductions, 21519 cells) ? However, thanks to lazy-evaluation, calculating just the first element of the sorted list actually requires less work in this particular case than the first solution using "minimum": ? head (sort [100,99..1]) 1 (713 reductions, 1227 cells) ? Incidentally, it is probably worth pointing out that this example depends rather heavily on the particular algorithm used to "sort" a list of elements. The results are rather different if we compare the same two approaches used to calculate the maximum value in the list: ? maximum [100,99..1] 100 (812 reductions, 1225 cells) ? last (sort [100,99..1]) 100 (10612 reductions, 20732 cells) ? This difference is caused by the fact that each element in the list produced by "sort" is only known once the values of all of the preceding elements are also known. Thus the complete list must be sorted in order to obtain the last element. .ST 9.7 Infinite data structures ----------------------------- One particular benefit of lazy evaluation is that it makes it possible for functions in Gofer to manipulate `infinite' data structures. Obviously we cannot hope either to construct or store an infinite object in its entirety -- the advantage of lazy evaluation is that it allows us to construct infinite objects piece by piece as necessary (and to reuse the storage space used by parts of the object when they are no longer required). As a simple example, consider the following function which can be used to produce infinite lists of integer values: countFrom n = n : countFrom (n+1) If we evaluate the expression "countFrom 1", Gofer just prints the list of integer values beginning with 1 until it is interrupted. Once each element in the list has been printed, the storage used to hold that element can be reused to hold later elements in the list. Evaluating this expression is equivalent to using an `infinite' loop to print the list of integers in an imperative programming language: ? countFrom 1 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,^C{Interrupted!} (53 reductions, 160 cells) ? For practical applications, we are usually only interested in using a finite portion of an infinite data structure (just as loops in an imperative programming language are usually terminated after finitely many iterations). For example, using "countFrom" together with the function "take" defined in the standard prelude, we can repeat the calculation from section 4 to find the sum of the integers 1 to 10: ? sum (take 10 (countFrom 1)) 55 (62 reductions, 119 cells) ? [ASIDE: The expression "take n xs" evaluates to a list containing the first n elements of the list xs (or to xs itself if the list contains fewer than n elements). Thus "countFrom 1" generates the infinite list of integers, "take 10" ensures that only the first ten elements are calculated, and "sum" calculates the sum of those integers as before.] A particular advantage of using infinite data structures is that it enables us to describe an object without being tied to one particular application of that object. Consider the following definition for the infinite list of powers of two [1, 2, 4, 8, ...]: powersOfTwo = 1 : map double powersOfTwo where double n = 2*n This list be used in a variety of ways; using the operator (!!) defined in the standard prelude [xs!!n evaluates to the nth element of the list xs], we can define a function to find the nth power of 2 for any given integer n: twoToThe n = powersOfTwo !! n Alternatively, we can use the list "powersOfTwo" to define a function mapping lists of bits (represented by integers 0 and 1) to the corresponding decimal number: simply reverse the order of the digits, multiply each by the corresponding power of two and calculate the sum. Using functions from the standard prelude, this translates directly into the definition: binToDec ds = sum (zipWith (*) (reverse ds) powersOfTwo) For example: ? twoToThe 12 4096 (15 reductions, 21 cells) ? binToDec [1,0,1,1,0] 22 (40 reductions, 85 cells) ? .ST 9.8 Polymorphism ----------------- Given the definition of "product" in section 9.5, it is easy to see that product takes a single argument which is a list of integers and returns a single integer value -- the product of the elements of the list. In other words, "product" has type [Int] -> Int. On the other hand, it is not immediately clear what the type of the function "map" should be. Clearly the first argument of "map" must be a function and both the second argument and the result are lists, so that the type of "map" must be of the form: (a -> b) -> [c] -> [d] \______/ \___/ \___/ type of 1st type of 2nd type of result argument "f" argument "xs" "map f xs" But what can be said about the types a, b, c and d? One possibility would be to choose a = b = c = d = Int which would be acceptable for expressions such as "map fact [1,2,3,4]", but this would not be suitable in an expression such as "map chr [65,75,32]" because the "chr" function does not have type Int -> Int. Notice however that the argument type of "f" must be the same as the type of elements in the second argument (i.e. a = c) since "f" is applied to each element in that list. Similarly, the result type of "f" must be the same as the type of elements in the result list (i.e. b = d) since each element in this list is obtained as a result of applying the function "f" to some value. It is therefore reasonable to treat the "map" function as having any type of the form: (a -> b) -> [a] -> [b] The letters "a" and "b" used in this type expression represent arbitrary types and are called type variables. An object whose type includes one or more type variables can be thought of as having many different types and is often described as having a `polymorphic type' (literally: its type has `many shapes'). The ability to define and use polymorphic functions in Gofer turns out to be very useful. Here are the types of some of the other polymorphic functions which have been used in previous examples which illustrate this point: length :: [a] -> Int (++) :: [a] -> [a] -> [a] concat :: [[a]] -> [a] Thus we can use precisely the same "length" function to determine both the length of a list of integers as well as finding the length of a string: ? length [1..10] 10 (98 reductions, 138 cells) ? length "Hello" 5 (22 reductions, 36 cells) ? .ST 9.9 Higher-order functions --------------------------- In Gofer, function values are treated in much the same way as any other kind of value; in particular, they can be used both as arguments to, and results of other functions. .cc 5 Functions which manipulate other functions in this way are often described as `higher-order functions'. Consider the following example, taken from the standard prelude: (.) :: (b -> c) -> (a -> b) -> (a -> c) (f . g) x = f (g x) As indicated by the type declaration, we think of the (.) operator as a function taking two function arguments and returning another function value as its result. If f and g are functions of the appropriate types, then (f . g) is a function called the composition of f with g. Applying (f . g) to a value is equivalent to applying g to that value, and then applying f to the result [As described, far more eloquently, by the second line of the declaration above!]. Many problems can often be described very elegantly as a composition of other functions. Consider the problem of calculating the total number of characters used in a list of strings. A simple recursive function provides one solution: countChars [] = 0 countChars (w:ws) = length w + countChars ws ? countChars ["super","cali","fragi","listic"] 20 (96 reductions, 152 cells) ? An alternative approach is to notice that we can calculate the total number of characters by first combining all of the words in the argument list into a single word (using concat) and then finding the length of that word: ? (length . concat) ["super","cali","fragi","listic"] 20 (113 reductions, 211 cells) ? Another solution is to first find the length of each word in the list (using the "map" function to apply "length" to each word) and then calculate the sum of these individual lengths: ? (sum . map length) ["super","cali","fragi","listic"] 20 (105 reductions, 172 cells) ? .ST 9.10 Variable declarations -------------------------- A variable declaration is a special form of function definition, almost always consisting of a single equation of the form: var = rhs (i.e. a function declaration of arity 0). Whereas the values defined by function declarations of arity>0 are guaranteed to be functions, the values defined by variable declarations may or may not be functions: odd = not . even -- if an integer is not even then it must be odd val = sum [1..100] Note that variables defined like this at the top level of a file of definitions will be evaluated using lazy evaluation. The first time we refer to the variable "val" defined above (either directly or indirectly), Gofer evaluates the sum of the integers from 1 to 100 and overwrites the definition of "val" with this number. This calculation can then be avoided for each subsequent use of "val" (unless the file containing the definition of "val" is reloaded). ? val 5050 (809 reductions, 1120 cells) ? val 5050 (1 reduction, 7 cells) ? Because of this behaviour, we should probably try to avoid using variable declarations where the resulting value will require a lot of storage space. If we load a file of definitions including the line: longList = [1..10000] and then evaluate the expression "length longList" (eventually obtaining the expected result of 10000), then Gofer will evaluate the definition of "longList" and replace it with the complete list of integers from 1 upto 10000. Unlike other memory used during a calculation, it will not be possible to reuse this space for other calculations without reloading the file defining "longList", or loading other files instead. .ST 9.11 Pattern bindings and irrefutable patterns ---------------------------------------------- Another useful way of defining variables uses `pattern bindings' which are equations of the form: pat = rhs where the expression on the left hand side is a pattern as described in section 9.1. As a simple example of pattern bindings, here is one possible definition for the function "head" which returns the first element in a list of values: head xs = x where (x:ys) = xs [The definition "head (x:_) = x" used in the standard prelude is slightly more efficient, but otherwise equivalent.] [ASIDE: Note that pattern bindings are treated quite differently from function bindings (of which the variable declarations described in the last section are a special case). There are two situations in which an ambiguity may occur; i.e. if the left hand side of an equation is a simple variable or an (n+k) pattern of the kind described in section 9.1. In both cases, these are treated as function bindings, the former being a variable declaration whilst the latter will be treated as a definition for the operator symbol (+).] Pattern bindings are often useful for defining functions which we might think of as `returning more than one value' -- although they are actually packaged up in a single value such as a tuple. As an example, consider the function "span" defined in the standard prelude. span :: (a -> Bool) -> [a] -> ([a],[a]) If xs is a list of values and p is a predicate, then span p xs returns the pair of lists (ys,zs) such that ys++zs == xs, all of the elements in ys satisfy the predicate p and the first element of zs does not satisfy p. A suitable definition, using a pattern binding to obtain the two lists resulting from the recursive call to "span" is as follows: span p [] = ([],[]) span p xs@(x:xs') | p x = let (ys,zs) = span p xs' in (x:ys,zs) | otherwise = ([],xs) For consistency with the lazy evaluation strategy used in Gofer, the right hand side of a pattern binding is not evaluated until the value of one of the variables bound by that pattern is required. The definition: (0:xs) = [1,2,3] will not cause any errors when it is loaded into Gofer, but will cause an error if we attempt to evaluate the variable xs: ? xs {v120 [1, 2, 3]} (11 reductions, 46 cells) ? The variable name "v120" appearing in this expression is the name of a function called a `conformality check' which is defined automatically by Gofer to ensure that the value on the right hand side of the pattern binding conforms with the pattern on the left. Compare this with the behaviour of pattern matching in function definitions such as: ? example [1] where example (0:xs) = "Hello" {v126 [1]} (4 reductions, 22 cells) ? where the equivalent of the conformality check is carried out immediately even if none of the values of the variables in the pattern are actually required. The reason for this difference is that the arguments supplied to a function must be evaluated to determine which equation in the definition of the function should be used. The error produced by the example above was caused by the fact that the argument [1] does not match the pattern used in the equation defining "example" (represented by an internal Gofer function called "v126"). A different kind of behaviour can be obtained using a pattern of the form ~pat, known as an irrefutable (or lazy) pattern. This pattern can initially be matched against any value, delaying the check that this value does indeed match pat until the value of one of the variables appearing in it is required. The basic idea (together with the method used to implement irrefutable patterns in Gofer) is illustrated by the identity: f ~pat = rhs is equivalent to f v = rhs where pat=v The following examples, based very closely on those given in the Haskell report [5], illustrate the use of irrefutable patterns. The variable "undefined" used in these examples is included in the standard prelude and causes a run-time error each time it is evaluated (technically speaking, it represents the bottom element of the relevant semantic domain, and is the only value having all possible types): (\ (x,y) -> 0) undefined = {undefined} (\~(x,y) -> 0) undefined = 0 (\ [x] -> 0) [] = {v113 []} (\~[x] -> 0) [] = 0 (\~[x, (a,b)] -> x) [(0,1),undefined] = {undefined} (\~[x,~(a,b)] -> x) [(0,1),undefined] = (0,1) (\ (x:xs) -> x:x:xs) undefined = {undefined} (\~(x:xs) -> x:x:xs) undefined = {undefined}:{undefined}:{undefined} Irrefutable patterns are not used very frequently, although they are particularly convenient in some situations (see section 12 for some examples). Be careful not to use irrefutable patterns where they are not appropriate. An attempt to define a map function "map'" using: map' f ~(x:xs) = f x : map' f xs map' f [] = [] turns out to be equivalent to the definition: map' f ys = f x : map f xs where (x:xs) = ys and will not behave as you might have intended: ? map' ord "abc" [97, 98, 99, {v124 []}, {v124 []}, {v^C{Interrupted!} (35 reductions, 159 cells) ? .ST 9.12 Type declarations ----------------------- The type system used in Gofer is sufficiently powerful to enable Gofer to determine the type of any function without the need to declare the types of its arguments and the return value as in some programming languages. Despite this, Gofer allows the use of type declarations of the form: var1, ..., varn :: type which enable the programmer to declare the intended types of the variables var1, ..., varn defined in either function or pattern bindings. There are a number of benefits of including type declarations of this kind in a program: o Documentation: The type of a function often provides useful information about the way in which a function is to be used -- including the number and order of its arguments. o Restriction: In some situations, the type of a function inferred by Gofer is more general than is required. As an example, consider the following function, intended to act as the identity on integer values: idInt x = x Without an explicit type declaration, Gofer treats "idInt" as a polymorphic function of type a -> a and the expression "idInt 'A'" does not cause a type error. This problem can be solved by using an explicit type declaration to restrict the type of "idInt" to a particular instance of the polymorphic type a -> a: idInt :: Int -> Int Note that a declaration such as: idInt :: Int -> a is not a valid type for the function "idInt" (the value of the expression "idInt 42" is an integer and cannot be treated as having an arbitrary type, depending on the value of the type variable "a"), and hence will not be accepted by Gofer. o Consistency check: As illustrated above, declared types are always checked against the definition of a value to make sure that they are compatible. Thus Gofer can be used to check that the programmer's intentions (as described by the types assigned to variables in type declarations) are consistent with the definitions of those values. o Overloading: Explicit type declarations can be used to solve a number of problems associated with overloaded functions and values. See section 14 for further details. .pa .co-------------------------------------------------------------------| .>ch10 .ST 10. INCREASING YOUR POWER OF EXPRESSION This section describes a number of useful extensions to the basic range of expressions used in the previous sections. None of these add any extra computational power to Gofer -- anything that can be done with these constructs could also be done with the constructs already described. They are however included in Gofer because they allow many expressions and function definitions to be written more clearly and concisely than the equivalent expressions without these notations. .ST 10.1 Arithmetic sequences ------------------------- A number of useful lists can be generated using the notation of arithmetic sequences (so named because of their similarity to arithmetic progressions in mathematics). The following list summarises the four forms of sequence expression that can be used in Gofer, together with their translation using the standard functions enumFrom, enumFromTo, enumFromThen and enumFromThenTo: [ n .. ] enumFrom n Produces the (potentially infinite) list of values starting with the value of n and increasing in single steps. e.g. [1..] = [1, 2, 3, 4, 5, 6, 7, 8, 9, etc... [ n .. m ] enumFromTo n m Produces the list of elements from n upto and including m in single steps. If m is less than n then the list is empty. e.g. [-3..3] = [-3, -2, -1, 0, 1, 2, 3] [1..1] = [1] [9..0] = [] [ n, m .. ] enumFromThen n m Produces the (potentially infinite) list of values whose first two elements are given by the values n and m. If m is greater than n then the following elements of the list are increasing in steps of the same size. A similar result is obtained if m is less than n in which case the elements of [n,m..] will be decreasing. If n and m are equal then [n,m..] is an infinite list in which each element is equal to n. e.g. [1,3..] = [1, 3, 5, 7, 9, 11, 13, etc... [0,0..] = [0, 0, 0, 0, 0, 0, 0, etc... [5,4..] = [5, 4, 3, 2, 1, 0, -1, etc... [ n, n' .. m ] enumFromThenTo n n' m Produces the list of elements from [n,n'..] upto the limit value m. If m is less than n and [n,n'..] is increasing, or m is greater than n and [n,n'..] is decreasing the resulting list will be empty. e.g. [1,3..12] = [1, 3, 5, 7, 9, 11] [0,0..10] = [0, 0, 0, 0, 0, 0, 0, etc... [5,4..1] = [5, 4, 3, 2, 1] In the standard prelude, the functions enumFrom, enumFromTo, enumFromThen and enumFromThenTo are overloaded and may also be used to enumerate lists of characters or floating point values: ? ['0'..'9'] ++ ['A'..'Z'] 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ (397 reductions, 542 cells) ? [1.2, 1.35 .. 2.00] [1.2, 1.35, 1.5, 1.65, 1.8, 1.95] (56 reductions, 133 cells) ? Arithmetic sequences such as those described above play the same role in functional programming languages as the iterative `for' constructs in traditional imperative languages. A good example of this is the example in section 4 used to calculate the sum of the integers from 1 upto 10 -- "sum [1..10]". An equivalent program in an imperative language might look something like (especially if you think of C!): int i; int total=0; for (i=1; i<=10; i++) total = total + i; return total; The advantages of the functional notation in this case are clear: o It is more compact. o It separates the task of generating the sequence of integers [1..10] from the task of finding their sum. o It does not require the declaration or use of auxiliary variables such as "i" and "total" in the above. .ST 10.2 List comprehensions ------------------------- List comprehensions provide another very powerful and compact notation for describing certain kinds of list expression. The basic form of a list comprehension is: [ | ] There are three kinds of qualifier that can be used in Gofer: o Generators: A qualifier of the form pat<-exp is used to extract each element that matches the pattern pat from the list exp in the order that they elements appear in that list. A simple example of this is the expression [x*x | x<-[1..10]] which denotes the list of the squares of the integers between 1 and 10 inclusive and evaluates to [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] as expected. Formally, we can define the meaning of a list comprehension with a single generator by the equation: [ e | pat <- exp ] = loop exp where loop [] = [] loop (pat:xs) = e : loop xs loop (_:xs) = loop xs If pat is an irrefutable pattern (for example, a variable) then this is equivalent to: [ e | pat <- exp ] = map f exp where f pat = e The full definition is needed for those cases where the pattern pat may not match all of the elements in the list exp. This is the case in expressions such as [ y | (3,y)<-[(1,2),(3,4),(5,6)] ] which evaluates to the singleton list [4]. o Filters: A boolean valued expression may also be used as a qualifier in which case it is often called a filter. We can define the meaning of a list comprehension with a single filter by the equation: [ e | condition ] = if condition then [e] else [] Whilst this form of list comprehension is occasionally useful as it stands, it is more common to use filters in conjunction with generators as described below. o Local definitions: A qualifier of the form pat=expr can be used to introduce a local definition within a list comprehension. Its meaning can be defined formally using the equation: [ e | pat = exp ] = [ let pat=exp in e ] As in the case of filters, local definitions are more commonly used within lists of more than one qualifier as described below. Particular care should be taken to distinguish a filter of the form pat==expr from a local definition of the form pat=expr. [ASIDE: I originally suggested this form of qualifier in a message sent to the Haskell mailing list, only to discover that a similar (and more comprehensive) suggestion had been made by Kevin Hammond almost a year earlier. There was a certain amount of controversy surrounding the choice of an appropriate syntax and semantics for the construct and consequently, this feature is not currently part of the Haskell standard. The syntax and semantics above is implemented by Gofer in the hope that it will give functional programmers an opportunity to experiment with this facility in their own programs.] The real power of this notation is that it is possible to use several qualifiers, separated by commas on the right of the vertical bar `|' symbol in a list comprehension. Formally, if qs1 and qs2 are two such lists of qualifiers, then we can define the meaning of multiple qualifiers using: [ e | qs1, qs2 ] = concat [ [ e | qs2 ] | qs1 ] The following examples illustrate how this definition works in practice: o Variables generated by later qualifiers vary more quickly than those generated by earlier qualifiers: ? [ (x,y) | x<-[1..3], y<-[1..2] ] [(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)] (107 reductions, 246 cells) ? o Later qualifiers may use the values generated by earlier ones: ? [ (x,y) | x<-[1..3], y<-[1..x]] [(1,1), (2,1), (2,2), (3,1), (3,2), (3,3)] (107 reductions, 246 cells) ? [ x | x<-[1..10], even x ] [2, 4, 6, 8, 10] (108 reductions, 171 cells) ? o Variables defined in later qualifiers hide those introduced by earlier ones. The following expressions are valid list comprehensions, but this style of definition in which names are reused can result in programs which are difficult to understand, and is not recommended: ? [ x | x<-[[1,2],[3,4]], x<-x ] [1, 2, 3, 4] (18 reductions, 53 cells) ? [ x | x<-[1,2], x<-[3,4] ] [3, 4, 3, 4] (18 reductions, 53 cells) ? o Changing the order of qualifiers has a direct effect on efficiency. The following two examples produce the same result, but the first uses more reductions and cells because it repeats the evaluation of "even x" for each possible value of "y". ? [ (x,y) | x<-[1..3], y<-[1..2], even x ] [(2,1), (2,2)] (110 reductions, 186 cells) ? [ (x,y) | x<-[1..3], even x, y<-[1..2] ] [(2,1), (2,2)] (62 reductions, 118 cells) ? The following example illustrates a similar kind of behaviour with local definitions; in the first case the expression "fact x" is evaluated twice for each possible value of "x", whilst the second expression uses a local definition to ensure that the evaluation is not repeated: ? [ fact x + y | x<-[1..3], y<-[1..2] ] [2, 3, 3, 4, 7, 8] (246 reductions, 398 cells) ? [ factx + y | x<-[1..3], factx = fact x, y<-[1..2] ] [2, 3, 3, 4, 7, 8] (173 reductions, 294 cells) ? .ST 10.3 Lambda expressions ------------------------ In addition to named function definitions, Gofer also allows the definition and use of unnamed functions using a `lambda expression' of the form: \ -> [ASIDE: This is a slight generalisation of the form of lambda expression used in most theoretical treatments of functional programming and dating back to the pioneering work of logicians including Alonzo Church and Haskell Curry, from whom the programming language takes its name. The `\' character used at the beginning of a Gofer lambda expression has been chosen for its resemblance to the greek letter lambda that might be used if the standard character set were a little larger.] This expression denotes a function taking a number of parameters (one for each pattern) and producing the result specified by the expression to the right of the -> symbol. For example, (\x->x*x) represents the function which takes a single integer argument `x' and produces the square of that number as its result. Another example is the lambda expression (\x y->x+y) which takes two integer arguments and outputs their sum; this expression is in fact equivalent to the (+) operator: ? (\x y->x+y) 2 3 5 (3 reductions, 7 cells) ? A lambda expression of the form illustrated above is equivalent to the following expression using a local definition: (let newName = in newName) where "newName" is a new variable name, chosen to avoid conflicts with other variables that are already in use. This name will be printed if you enter an expression involving a lambda expression without supplying the full number of parameters for that function: ? (\x y -> x+y) 42 v117 42 (2 reductions, 14 cells) ? Lambda expressions are particularly useful for certain styles of functional programming; an example of this is the continuation-based approach to I/O described in section 12. .ST 10.4 Case expressions --------------------- A case expression can be used to evaluate an expression and, depending on the result, return one of a number of possible values. As such, case statements are a straightforward generalisation of conditional expressions. Indeed, an expression of the form "if e then t else f" is in fact equivalent to the case expression: case e of True -> t False -> f In general, a case expression takes the form "case exp of alts" where exp is the expression to be evaluated and alts is a list of alternatives, each of which is of the form: pat -> rhs for a simple alternative or: pat | condition1 -> rhs1 using guard expressions as | condition2 -> rhs2 described in section 9.2 for . function definitions . | conditionn -> rhsn In Gofer, a case expression of the form case e of alts is implemented by choosing a new function name "newName" as in the previous section and using the alternatives in alts to construct an appropriate definition for this function (essentially by replacing each `->' symbol with a `=' symbol). The complete case expression is then treated as being equivalent to the expression "newName e". A simple example of this is the "scanl" function whose definition in the standard prelude: scanl f q xs = q : (case xs of [] -> [] x:xs -> scanl f (f q x) xs) is equivalent to: scanl f q xs = q : scanl' xs where scanl' [] = [] scanl' (x:xs) = scanl f (f q x) xs This latter form is precisely the definition used in [1] (but using the name "scan" where Gofer uses "scanl"). Evaluating a case expression in which none of the alternatives match the value of the discriminant results in an error such as the following: ? case [1,2] of [] -> "empty list" {v117 [1, 2]} (6 reductions, 31 cells) ? The function name "v117" which appears here is the name of the function which is used internally by Gofer to implement the case expression whilst the expression "[1, 2]" gives the discriminant value which could not be matched. By combining case expressions with the lambda expressions introduced in the previous section, any function declaration can be translated into a single equation of the form = . For example, the standard function "map" whose definition is usually written as: map f [] = [] map f (x:xs) = f x : map f xs can also be defined by the equation: map = \f xs -> case xs of [] -> [] (y:ys) -> f y : map f ys This kind of translation is used in the implementation of many functional programming languages, including Gofer. See Simon Peyton Jones book [2] for more details of this. .ST 10.5 Operator sections ---------------------- As we have seen, most functions in Gofer taking more than one argument are treated as a function of a single argument, whose result is a function which can then be applied to the remaining arguments. Thus "(+) 1" denotes the function which takes an integer argument "n" and returns the integer value "1+n". Functions of this kind involving operator symbols are sufficiently common that Gofer provides a special syntax for them. Using e to denote an atomic expression and the symbol "*" to represent an arbitrary infix operator, there are functions (e *) and (* e), known as `sections of the operator (*)' defined by: (e *) x = e * x (* e) x = x * e or, using lambda expressions as introduced in section 10.3: (e *) = \x -> e * x (* e) = \x -> x * e For example: (1+) is the successor function which returns the value of its argument plus 1, (1.0/) is the reciprocal function, (/2) is the halving function, (:[]) is the function which maps any value to the singleton list containing that element. In Gofer, the expressions "(e *)" and "(* e)" are actually treated as abbreviations for "(*) e" and "flip (*) e" respectively, where "flip" is the function defined by: flip :: (a -> b -> c) -> b -> a -> c flip f x y = f y x There is an important special case which occurs with an expression of the form (- e); this is interpreted as "negate e" and not as the section which subtracts the value of "e" from its argument. The latter function can be written as the section (+ (- e)) or as "subtract e" where "subtract" is the function defined in the standard prelude using: subtract = flip (-) .ST 10.6 Explicitly typed expressions ---------------------------------- As described in section 9.12, it is often useful to be able to declare the type of a variable defined in a function or pattern binding. For much the same reasons, Gofer allows expressions of the form: :: so that the type of an expression can be specified explicitly. Note that the :t command can be used to find the type of a particular expression that is inferred by Gofer: ? :t \x -> [x] \x -> [x] :: a -> [a] ? :t sum . map length sum . map length :: [[a]] -> Int ? The types inferred in each case can be modified by including explicit types in these expressions: ? :t (\x -> [x]) :: Char -> String \x -> [x] :: Char -> String ? :t sum . map (length :: String -> Int) sum . map length :: [String] -> Int ? Note that an error occurs if the type declared in an explicitly typed expression is not compatible with the type inferred by Gofer: ? :t (\x -> [x]) :: Int -> a ERROR: Declared type too general *** Expression : \x -> [x] *** Declared type : Int -> a *** Inferred type : Int -> [Int] ? Explicitly typed expressions are most commonly used together with overloaded functions and values as described in section 14. .pa .co-------------------------------------------------------------------| .>ch11 .ST 11. USER-DEFINED DATATYPES AND TYPE SYNONYMS .ST 11.1 Datatype definitions ------------------------- In addition to the wide range of built-in datatypes described in section 7, Gofer also allows the definition of new datatypes using declarations of the form: data DatatypeName a1 ... an = constr1 | ... | constrm where DatatypeName is the name of a new type constructor of arity n>=0, a1, ..., an are distinct type variables representing the arguments of DatatypeName and constr1, ..., constrm (m>=1) describe the way in which elements of the new datatype are constructed. Each constr can take one of two forms: o Name type1 ... typer where Name is a previously unused constructor function name (i.e. an identifier beginning with a capital letter). This declaration introduces Name as a new constructor function of type: type1 -> ...-> typer -> DatatypeName a1 ... an. o type1 CONOP type2 where CONOP is a previously unused constructor function operator (i.e. an operator symbol beginning with a colon). This declaration introduces (CONOP) as a new constructor function of type: type1 -> type2 -> DatatypeName a1 ... an. [N.B. only the type variables a1, ..., an may appear in the type expressions in each constr in the definition of DatatypeName.] As a simple example, the following definition introduces a new type Day with elements Sun, Mon, Tue, Wed, Thu, Fri and Sat: data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat Simple functions manipulating elements of type Day can be defined using pattern matching: what_shall_I_do Sun = "relax" what_shall_I_do Sat = "go shopping" what_shall_I_do _ = "looks like I'll have to go to work" Another example uses a pair of constructors to provide a representation for temperatures which may be given using either of the centigrade or fahrenheit scales: data Temp = Centigrade Float | Fahrenheit Float freezing :: Temp -> Bool freezing (Centigrade temp) = temp <= 0.0 freezing (Fahrenheit temp) = temp <= 32.0 The following example uses a type variable on the left hand side of the datatype definition to implement a Set type constructor for representing sets using a list of values: data Set a = Set [a] For example, Set [1,2,3] is an element of type Set Int, representing the set of integers {1, 2, 3} whilst Set ['a'] represents a singleton set of type Set Char. As this example shows, it is possible to use the same name simultaneously as both a type constructor and as a constructor function. Datatype definitions may also be recursive, using the name of the datatype being defined on the right hand side of the datatype definition (mutually recursive datatype definitions are also permitted). The following example is taken from the Haskell report [5] and defines a type representing binary trees with values of a particular type at their leaves: data Tree a = Lf a | Tree a :^: Tree a For example, (Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10 has type Tree Int and represents the binary tree: ,--- 12 ,--| | | ,--- 23 | `--| | `--- 13 --| `--- 10 As an example of a function defined on trees, here are two definitions using recursion and pattern matching on tree valued expressions which calculate the list of elements at the leaves of a tree traversing the branches of the tree from left to right. The first definition uses a simple definition, whilst the second uses an `accumulating parameter' giving a more efficient algorithm: leaves, leaves' :: Tree a -> [a] leaves (Lf l) = [l] leaves (l:^:r) = leaves l ++ leaves r leaves' t = leavesAcc t [] where leavesAcc (Lf l) = (l:) leavesAcc (l:^:r) = leavesAcc l . leavesAcc r Using the binary tree above as an example: ? leaves ((Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10) [12, 23, 13, 10] (24 reductions, 73 cells) ? leaves' ((Lf 12 :^: (Lf 23 :^: Lf 13)) :^: Lf 10) [12, 23, 13, 10] (20 reductions, 58 cells) ? .ST 11.2 Type synonyms ------------------ Type synonyms are used to provide convenient abbreviations for type expressions. A type synonym is introduced by a declaration of the form: type Name a1 ... an = expansion where Name is the name of a new type constructor of arity n>=0, a1, ..., an are distinct type variables representing the arguments of Name and expansion is a type expression. Note that the only type variables permitted in the expansion type are those on the left hand side of the synonym definition. Using this declaration any type expression of the form: Name type1 ... typen is treated as an abbreviation of the type expression obtained from expansion by replacing each of the type variables a1, ..., an with the corresponding type type1, ..., typen. The most frequently used type synonym is almost certainly the String type which is a synonym for [Char]: type String = [Char] [ASIDE: This definition is actually built in to the Gofer system, but the effect is the same as if this declaration were included in the standard prelude.] Note that the types of expressions inferred by Gofer will not usually contain any type synonyms unless an explicit type signature is given, either using an explicitly typed expression (section 10.6) or a type declaration (section 9.12): ? :t ['c'] ['c'] :: [Char] ? :t ['c'] :: String ['c'] :: String ? Unlike the datatype declarations described in the previous section, recursive (and mutually recursive) synonym declarations are not permitted. This rules out examples such as: type BadSynonym = [BadSynonym] and ensures that the process of expanding all of the type synonyms used in any particular type expression will always terminate. The same property does not hold for the illegal definition above, in which any attempt to expand the type BadSynonym would lead to the non-terminating sequence: BadSynonym ==> [BadSynonym] ==> [[BadSynonym]] ==> .... .pa .co-------------------------------------------------------------------| .>ch12 .ST 12. DIALOGUES: INPUT AND OUTPUT The Gofer system implements a subset of the facilities for programs involving I/O described in the Haskell report [5]. In particular, this makes it possible for Gofer programs to be run interactively, and to make limited use of text files for both reading and writing. A significant factor in the design of the Haskell I/O facilities is that it allows the use of such programs without loss of referential transparency. .ST 12.1 Basic description ---------------------- Programs using the I/O facilities in Gofer are modelled by functions of type Dialogue, defined by the type synonym: type Dialogue = [Response] -> [Request] In other words, a Gofer program produces a list of output values, each of which may be thought of as a request for some particular input or output action, and obtains the corresponding list of operating system responses as its input. Note that the input list of responses will be evaluated lazily; i.e. we can ensure that we do not attempt to obtain the response to a given request until that request has been completed. The current range of requests supported by Gofer is described by the following datatype definition, taken from the standard prelude: data Request = -- file system requests: ReadFile String | WriteFile String String | AppendFile String String -- channel system requests: | ReadChan String | AppendChan String String -- environment requests: | Echo Bool Each response is an element of the type defined by the following datatype definition, using an auxiliary datatype IOError to describe a variety of error conditions that may occur: data Response = Success | Str String | Failure IOError data IOError = WriteError String | ReadError String | SearchError String | FormatError String | OtherError String The following list describes the kind of I/O behaviour specified by each form of Request and indicates the possible Response values that may be obtained in each case: o ReadFile string: Read contents of file named by "string". Possible responses to this request are: o Str contents if the request is successful, where "contents" is a string (evaluated lazily) containing the contents of the file specified by the ReadFile request. o Failure (SearchError name) occurs if file "name" cannot be accessed. o Failure (ReadError name) occurs if some other error occurs whilst opening the file "name". o WriteFile name string: Write the given "string" to the file "name". If the file does not already exist, it is created before attempting to write the value to file. If the file already exists then it will be truncated to zero length before the write begins. No response is obtained until the string argument has been fully evaluated and its contents written to file. Possible responses are: o Success if the write to file was completed successfully. o Failure (WriteError msg) if an error was detected whilst trying to perform the output. If the problem occurred whilst attempting to open the specified file, then "msg" contains the filename, otherwise it contains a printable representation of the evaluation error which occurred. o AppendFile name string: Similar to the WriteFile request except that the value of the given "string" is appended onto the file "name" if that file already exists. The responses that may be obtained from this request are the same as those for WriteFile. o ReadChan name: Read from the input stream "name". Note that it is an error to attempt to read from the same channel more than once in the same program. Possible responses are: o Str contents if the request is successful, where "contents" is a string (evaluated lazily) containing the list of characters entered on the input stream. o Failure (SearchError name) if the named channel cannot be found. The only input channel known to Gofer is the standard input channel "stdin". For convenience, the standard prelude defines the variable stdin bound to this string. o Failure (ReadError name) if a ReadChan request for the named channel has already been given by a previous request. o AppendChan name string: Output "string" on channel "name". No response is obtained until the string has been fully evaluated and written to the named channel. Possible responses are: o Success if the append to channel was completed successfully. o Failure (SearchError name) if the named channel cannot be found. The only output channels known to Gofer are "stdout", "stderr" and "stdecho" (which is actually just another name for "stdout" in Gofer). For convenience, the standard prelude defines variables stdout, stderr and stdecho bound to the corresponding string values. o Failure (WriteError msg) if an error is detected whilst trying to perform the output. The string "msg" contains a printable representation of the evaluation error which occurred. o Echo status: Set the echo status on the standard input channel stdin to the given boolean value. If the echo status is True, then user input will be echoed onto the screen as it is typed and the usual line editing facilities (such a backspace or delete) provided by the host system can be used to edit the input lines as they are entered. If the echo status is False, then individual characters may be read from the standard input channel without any echo or line editing features. Note that at most one Echo request can be used in a program, and must precede any ReadChan request for stdin. If not set by an explicit Echo request, the echo status defaults to True. Possible responses are: o Success if the request was completed successfully. o Failure (OtherError msg) if the request could not be completed either because a readChannel request for stdin has already been processed, or because a previous Echo request has already been given. The corresponding values of "msg" are "stdin already in use" and "repeated Echo request" respectively. A simple example of a program using these facilities to output a short message on the standard output stream is: helloWorld :: Dialogue helloWorld resps = [AppendChan stdout "hello, world"] Any expression entered into Gofer of type "Dialogue" will be treated as a Gofer program using I/O and will be executed accordingly: ? helloWorld hello, world (1 reduction, 28 cells) ? Notice that without the explicit type declaration, the type that would be inferred for helloWorld would be a -> [Request], and hence helloWorld would not be executed as a Dialogue program. This point can be illustrated using lambda expressions: ? \resps -> [AppendChan stdout "hello, world"] v128 (1 reduction, 7 cells) ? (\resps -> [AppendChan stdout "hello, world"]) :: Dialogue hello, world (1 reduction, 28 cells) ? In many cases the structure of an expression is enough to fully determine its type as Dialogue (or equivalently as [Response] -> [Request]), in which case no explicit types are required to ensure that the expression is treated as a Gofer program using I/O: ? \~[Success] -> [AppendChan stdout "hello, world"] hello, world (1 reduction, 29 cells) ? Note the use of the irrefutable pattern ~[Success] for the lambda expression in the last example; without this, the usual rules of pattern matching as described in section 9 would force Gofer to try to match the pattern [Success] against the list of responses, before the corresponding request had been produced: ? \ [Success] -> [AppendChan stdout "hello, world"] Aborting Dialogue: {error "Attempt to read response before request complete"} (50 reductions, 229 cells) ? The next example takes a single string as a parameter and displays the contents of the corresponding file: showFile :: String -> Dialogue showFile name ~(read:_) = [ReadFile name, AppendChan stdout result] where result = case read of Str contents -> contents Failure _ -> "Can't open " ++ name With a few modifications, we can implement a similar program which prompts for, and reads, a filename from the standard input and then reads and displays the contents of that file as before. This program is based on a similar example in the Haskell report [5]: main ~(Success : ~(Str userInput : ~(r3 : _))) = [ AppendChan stdout "Please type a filename: ", ReadChan stdin, ReadFile name, AppendChan stdout (case r3 of Str contents -> contents Failure _ -> "Can't open " ++ name) ] where (name : _) = lines userInput .ST 12.2 Continuation style I/O --------------------------- As an alternative to the `stream-based' approach to programs using the I/O facilities in Gofer, the standard prelude defines a family of functions which enables such programs to be written in a `continuation' style. The basic idea is to define a function corresponding to each different kind of request, whose parameters include the values required to make the request together with two continuations. The continuations are functions describing "what to do next", one of which is used if the request is successful, the other if the request fails. As an example, the ReadFile request is represented by the function "readFile" whose definition is equivalent to: readFile name fail succ ~(r:rs) = ReadFile name : rest rs where rest = case r of Str s -> succ s Failure ioerror -> fail ioerror The first thing to happen when a dialogue expression of the form "readFile name fail succ" is evaluated is that the corresponding request "ReadFile name" is added to the list of I/O requests. A new dialogue value "rest" is chosen, depending on the response to the ReadFile request, and the program continues by passing the remaining part of the response list to "rest". The functions "succ" and "fail" (called the success and failure continuations respectively) describe the way in which the new dialogue "rest" is obtained. The following example (edited a little to fit within the margins of this document) shows how the readFile function described above can be used to print the contents of a file called "test" on the display: ? readFile "test" (\ioerror resps -> []) (\s resps->[AppendChan stdout s]) This is a test message (4 reductions, 52 cells) ? The success continuation "(\s resps->[AppendChan stdout s])" used here receives the contents of the file "test" in the the parameter "s" and uses an AppendChan request to output that string on the display. As this example shows, the stream based approach of the previous section can be combined with the continuation based style of I/O without any difficulty. The failure continuation "(\ioerror resps -> [])" ignores the error condition "ioerror" which caused the request to fail and gives a dialogue which terminates immediately without any action. For example, assuming that the file "Test" cannot be found: ? readFile "Test" (\ioerror resps -> []) (\s resps->[AppendChan stdout s]) (4 reductions, 24 cells) ? In practice, it is usually a good idea to produce some kind of diagnostic message when an error occurs: ? readFile "Test" (\ioerror resps -> [AppendChan stdout (show' ioerror)]) (\s resps -> [AppendChan stdout s]) SearchError "Test" (11 reductions, 59 cells) ? In each of the examples above, the failure continuation has type "FailCont" as defined by the following type synonym in the standard prelude: type FailCont = IOError -> Dialogue Similarly, the success continuation, which takes a string representing an input string and produces a new Dialogue has type "StrCont": type StrCont = String -> Dialogue A third kind of continuation is needed for those requests which return a response of the form "Success" if successful (e.g. output requests). In this case the continuation is simply another dialogue: type SuccCont = Dialogue The following list gives the type of each of the six functions corresponding to the six different kinds of I/O request described in the previous section. Full definitions for each of these functions are given in appendix B: readFile :: String -> FailCont -> StrCont -> Dialogue writeFile :: String -> String -> FailCont -> SuccCont -> Dialogue appendFile :: String -> String -> FailCont -> SuccCont -> Dialogue readChan :: String -> FailCont -> StrCont -> Dialogue appendChan :: String -> String -> FailCont -> SuccCont -> Dialogue echo :: Bool -> FailCont -> SuccCont -> Dialogue As an illustration of the use of these functions, we show how each of the example programs from the previous section can be rewritten using the continuation based style of I/O, starting with the program "helloWorld": helloWorld :: Dialogue helloWorld = appendChan stdout "hello, world" abort done In this case, the explicit type declaration is not actually required since the type of the expression is completely determined by the type of "appendChan". The failure continuation "abort" is equivalent to the function "(\ioerror resps -> [])" described above and terminates the program if an error occurs without any further action. In a similar way, "done" is the trivial dialogue which terminates immediately without any action. Both of these values are defined in the standard prelude: done :: Dialogue done resps = [] abort :: FailCont abort ioerror = done Using the same approach, the "showFile" and "main" programs from the previous section are written as: showFile :: String -> Dialogue showFile name = readFile name (\ioerror -> appendChan stdout ("Can't open " ++ name) abort done) (\contents-> appendChan stdout contents abort done) main :: Dialogue main = appendChan stdout "Please type a filename: " abort (readChan stdin abort (\userInput -> let (name : _) = lines userInput in readFile name (\ioerror -> appendChan stdout ("Can't open " ++ name) abort done) (\contents -> appendChan stdout contents abort done))) .ST 12.3 Interactive programs ------------------------- One of the principal motivations for including facilities for I/O in Gofer programs was to provide a way of using interactive programs as described in [1]. An interactive program is represented by a function of type String -> String mapping an input string of characters entered at the keyboard into an output string to be displayed on the screen. There are two functions defined in the standard prelude which can be used to `execute' functions of this kind as interactive programs: o "interact f" executes f::String->String as an interactive program with echo on. This means that characters are read from the keyboard a line at a time. The usual editing characters such as backspace can be used to correct mistakes which are noticed before the return key is pressed at the end of each line. The input stream can be terminated by typing an end of file character at the beginning of a line: ? interact (map toUpper) This text was entered using the interact function THIS TEXT WAS ENTERED USING THE INTERACT FUNCTION ^Z (874 reductions, 1037 cells) ? o "run f" behaves like "interact f" except that echo is turned off. In this case, the only way of terminating the input stream without reaching the end of the string produced by "f" is to use the interrupt key: ? run (map toUpper) ALTHOUGH THIS IS ENTERED IN LOWER CASE, IT STILL APPEARS IN UPPER CASE ! {Interrupted!} (1227 reductions, 1463 cells) ? [ASIDE: of these two functions, only "interact" is also included in the standard prelude for Haskell, although "run" may also be added to a Haskell system using the definition below.] The definitions of "interact" and "run" provide further examples of Gofer programs using simple I/O facilities: interact :: (String -> String) -> Dialogue interact f = readChan stdin abort (\s -> appendChan stdout (f s) abort done) run :: (String -> String) -> Dialogue run f = echo False abort (interact f) [EXERCISE for the interested reader: construct alternative definitions for these functions using the stream based approach from section 12.1.] .pa .co-------------------------------------------------------------------| .>ch13 .ST 13. LAYOUT .ST 13.1 Comments ------------- Comments provide an informal but useful way of annotating a program with a description of its purpose, structure and development. Following the definition of Haskell, two styles of comment are supported by Gofer: o A one line comment begins with the two characters "--" and is terminated at the end of the same line. Note that an operator symbol cannot begin with "--" as this will be treated as the beginning of a comment. It is however possible to use the two characters "--" at any other position within an operator symbol. Thus a line such as: (xs ++ ys) -- xs includes a comment and will actually be treated as if the line had been written: (xs ++ ys) Whereas the line: xs >--> ys >--> zs does not contain any comments (although it will cause an error unless ">-->" has been defined using an appropriate infixl or infixr declaration). o A nested comment begins with the characters "{-", ends with the characters "-}" and may span any number of lines. [N.B. the initial "{-" string cannot overlap with the terminating "-}" string so that the shortest possible nested comment is "{--}", and not "{-}"]. An unterminated nested comment will be treated as an error. As the name suggests, comments of this kind may be nested so that "{- {- ... -} ... {- ... -} -}" is treated as a single comment. This makes nested comments particularly convenient for enclosing parts of a program which may already contain other nested comments. Both kinds of comment may be used in expressions entered directly into the Gofer system, or more usually, in files of definitions loaded into Gofer. The two styles of comment may be mixed within the same expression or program, remembering that the string "--" has no special significance within a nested comment and that the strings "{-" and "-}" have no special significance in a single line comment. Thus: [ 2, -- {- [ 2, {- 3, -- -} -- -} 3, 4 ] 4 ] are both equivalent to the list expression [2,3,4]. .ST 13.2 The layout rule -------------------- In a tradition dating back at least a quarter of a century to Landin's ISWIM family of languages, most Gofer programs use indentation to indicate the structure of a program. For example, in a definition such as: f x y = g (x + w) where g u = u + v where v = u * u w = 2 + y it is clear from the layout that the definition of w is intended to be local to f rather than to g. Another example where layout plays an important role is in distinguishing the two definitions: example x y z = a + b example x y z = a + b where a = f x y where a = f x b = g z y b = g z There are three situations in Gofer where indentation is typically used to determine the structure of a program: o At the top-level of a file of definitions. o In a group of local declarations following either of the keywords "let" or "where". o In a group of alternatives in a case expression, following the keyword "of". In each case, Gofer actually expects to find a list of items enclosed between braces `{' and `}' with individual items separated from one another by semicolons `;'. However, if the leading brace is not found then Gofer uses the layout rule described below to arrange for `{', `}' and `;' tokens to be inserted into the input stream automatically according to the indentation of each line. In this way, the first example above will in fact be treated as if the user had entered: f x y = g (x + w) where {g u = u + v where {v = u * u }; w = 2 + y } or, equivalently, just: f x y = g (x + w) where {g u = u + v where {v = u * u}; w = 2 + y} where the additional punctuation using the `{', `}' and `;' characters makes the intended grouping clear, regardless of indentation. .cc 2 The layout rule used in Gofer is the same as that of Haskell, and can be described as follows: o An opening brace `{' is inserted in front of the first token at the beginning of a file or following one of the keywords "where", "let" or "of", unless that token is itself an opening brace. o A `;' token is inserted in front of the first token in any subsequent line with exactly the same indentation as the token in front of which the opening brace was inserted. o The layout rule ends and a `}' token is inserted in front of the first token in a subsequent line whose indentation is strictly less than that of the token in front of which the opening brace was inserted. o A closing brace `}' will also be inserted at any point where an otherwise unexpected token is encountered. This part of the rule makes it possible to use expressions such as: let a = fact 12 in a+a without needing to use the layout characters explicitly as in: let {a = fact 12} in a+a. o Lines containing only whitespace (blanks and tabs) and comments do not affect the use of the layout rule. o For the purposes of determining the indentation of each line in a file, tab stops are assumed to be placed every 8 characters, with the leftmost tab stop in column 9. Each tab character inserts one or more spaces as necessary to move to the next tab stop. o The indentation of the end of file token is zero. The following (rather contrived) program, is based on an example in the Haskell report [5], and provides an extended example of the use of the layout rule. A file containing the following definitions: data Stack a = Empty | MkStack a (Stack a) push :: a -> Stack a -> Stack a push x s = MkStack x s size :: Stack a -> Int size s = length (stkToList s) where stkToList Empty = [] stkToList (MkStack x s) = x:xs where xs = stkToList s pop :: Stack a -> (a, Stack a) pop (MkStack x s) = (x, case s of r -> i r where i x = x) top :: Stack a -> a top (MkStack x s) = x will be treated by Gofer as if it has been written: {data Stack a = Empty | MkStack a (Stack a) ;push :: a -> Stack a -> Stack a ;push x s = MkStack x s ;size :: Stack a -> Int ;size s = length (stkToList s) where {stkToList Empty = [] ;stkToList (MkStack x s) = x:xs where {xs = stkToList s }};pop :: Stack a -> (a, Stack a) ;pop (MkStack x s) = (x, case s of {r -> i r where {i x = x}}) ;top :: Stack a -> a ;top (MkStack x s) = x } Note that some of the more sophisticated forms of expression cannot be written on a single line (and hence entered directly into the Gofer system) without explicit use of the layout characters `{', `}' and `;': ? len [1..10] where len [] = 0; len (x:xs) = 1 + len xs 10 (81 reductions, 108 cells) ? f True where f x = case x of True->n where {n=not x}; False->True False (4 reductions, 11 cells) ? One situation in which the layout rule can cause problems is with top-level definitions. For example, the two lines: f x = 1 + x g y = 1 - y will be treated as a single line "f x = 1 + x g y = 1 - y", which will cause a syntax error. This kind of problem becomes rather more difficult to spot if the two definitions are not on subsequent lines, particularly if they are separated by several lines of comments. For this reason, it is usually a good idea to ensure that all of the top-level definitions in a file start in the same column (the first column is usually the most convenient). COBOL and Fortran programmers are not likely to find this problem too distressing :-) .pa .on .co-------------------------------------------------------------------| .>ch14 .ST 14. OVERLOADING IN GOFER One of the biggest differences between Gofer and most other programming languages (with the exception of Haskell) is the approach to overloading; enabling the definition and use of functions in which the meaning of a function symbol may depend on the types of its arguments. Like Haskell, overloading in Gofer is based around a system of type classes which allow overloaded functions to be grouped together into related groups of functions. Whilst the precise details of the approach to type classes used by Gofer are quite different from those of Haskell, both rely on the same basic ideas and use a similar syntax for defining and using type classes. It would therefore seem possible that experience gained with the overloading system in one language can readily by applied to the other. The differences embodied in the Gofer system of classes stem from my own, theoretically based investigations into `qualified types' some of which is detailed in references [8-12]. In my personal opinion, the Gofer system has some significant advantages over the Haskell approach (see [12] for details) and one of the principal motivations behind the implementation to Gofer was to provide a way of testing such claims. One fact which I believe has already been established using Gofer is that the use and implementation of overloaded functions need not have the significant effect on performance that was anticipated with early implementations of Haskell. This section outlines the system of type classes used in Gofer, indicating briefly how they can be used and how they are implemented. .ST 14.1 Type classes and predicates -------------------------------- A type class can be thought of as a family of types (or more generally as a family of tuples of types) whose elements are called instances of the class. If C is the name of an n-parameter type class then an expression of the form C t1 t2 ... tn where t1, t2, ..., tn are type expressions is called a predicate and represents the assertion that the specified tuple of types is an instance of the class C. Given a polymorphic function (e.g. map::(a->b)->[a]->[b]), we are free to use the function at any type which can be obtained by substituting arbitrary types for each of the type variables in its type. In Gofer, a type expression may be qualified by one or more predicates which restrict the range of types at which a value can be used: e.g. a function of type C a => a -> a -> a can be treated as a function of type t -> t -> t for any instance t of the class C. The predicate C a in the type expression in the previous example is called the context of the type. Contexts may contain more than one predicate in which case the predicates involved must be separated by commas and the context enclosed in parentheses as in (C a, D b). The empty context is written () and any type expression t is equivalent to the qualified type () => t. For uniformity, a context with only one element may also be enclosed by parentheses. For technical reasons, type synonyms are not currently permitted in predicates. This is consistent with the use of predicates in Haskell, but may be relaxed, at least in certain cases, in later versions of Gofer. .ST 14.2 The type class Eq ---------------------- The type class Eq is a simple and useful example, whose instances are precisely those types whose elements can be tested for equality. The declaration of this class given in the standard prelude is as follows: class Eq a where (==), (/=) :: a -> a -> Bool x /= y = not (x == y) There are three parts in any class declaration. For this particular example we have: o The first line (called the `header') of the declaration introduces a name Eq for the class and indicates that it has a single parameter, represented by the type variable a. o The second line of the declaration (the `signature part') indicates that there are functions denoted by the operator symbols (==) and (/=) of type a -> a -> Bool for each instance a of class Eq. Using the notation introduced in the previous section, both of these operators have type: Eq a => a -> a -> Bool These functions are called the `members' (or `member functions') of the class. [This terminology, taken from Haskell, is rather unfortunate; thinking of a type class as a set of types, the elements of the class are called `instances', whilst the `members' of the class correspond more closely to the instance variables that are used in the terminology of object-oriented programming.] The intention is that the (==) function will be used to implement an equality test for each instance of the class, with the (/=) operator providing the corresponding inequality function. The ability to include related groups of functions within a single type class in this way is a useful tool in program design. o The third line of the class declaration (the `default definitions') provides a default definition of the (/=) operator in terms of the (==) operator. Thus it is only necessary to give a definition for the (==) operator in order to define all of the member functions for the class Eq. It is possible to override default member definitions by giving an alternative definition as appropriate for specific instances of the class. .ST 14.2.1 Implicit overloading --------------------------- Member functions are clearly marked as overloaded functions by their definition as part of a class declaration, but this is not the only way in which overloaded functions occur in Gofer; the restriction to particular instances of a type class is also carried over into the type of any function defined either directly or indirectly in terms of the member functions of that class. For example, the types inferred for the following two functions: x `elem` xs = any (x==) xs xs `subset` ys = all (`elem` ys) xs are: elem :: Eq a => a -> [a] -> Bool subset :: Eq a => [a] -> [a] -> Bool [ASIDE: On the other hand, if none of the functions used in a particular expression or definition are overloaded then there will not be any overloading in the corresponding value. Gofer does not support the concept of implicit overloading used in some languages where a value of a particular type might automatically be coerced to a value of some supertype. An example of this would be the automatic translation of a badly typed expression "1.0 == 1" to a well-typed expression of the form "1.0 == float 1" for some (potentially overloaded) coercion function "float" mapping numeric values to elements of type Float.] Note also that the types appearing in the context of a qualified type reflect the types at which overloaded functions are used. Thus: f x ys = [x] == ys has type Eq [a] => a -> [a] -> Bool, and not Eq a => a -> [a] -> Bool, which is the type that would be assigned to "f" in a Haskell system. .ST 14.2.2 Instances of class Eq ---------------------------- Instances of a type class are defined using declarations similar to those used to define the corresponding type class. The following examples, taken from the standard prelude, give the definitions for a number of simple instances of the class Eq: instance Eq Int where (==) = primEqInt instance Eq Bool where True == True = True False == False = True _ == _ = False instance Eq Char where c == d = ord c == ord d instance (Eq a, Eq b) => Eq (a,b) where (x,y) == (u,v) = x==u && y==v instance Eq a => Eq [a] where [] == [] = True [] == (y:ys) = False (x:xs) == [] = False (x:xs) == (y:ys) = x==y && xs==ys The interpretation of these declarations is as follows: o The first declaration makes Int an instance of class Eq. The function "primEqInt" is a primitive Gofer function which tests the equality of two integer values and has type Int -> Int -> Bool. o The second declaration makes Bool an instance of class Eq with a simple definition involving pattern matching. o The third declaration makes Char an instance of class Eq. This definition indicates that a pair of characters are equal if they have the same ASCII value, which is obtained using the "ord" function. Note that the two occurrences of the symbol (==) in the equation: c == d = ord c == ord d have different meanings; the first denotes equality between characters (elements of type Char), whilst the second denotes equality between integers (elements of type Int). o The fourth declaration provides an equality operation on pairs. Given two elements (x,y) and (u,v) of type (a,b) for some a, b, it must be possible to check that both x==u and y==v before we can be sure that the two pairs are indeed equal. In other words, both a and b must also be instances of Eq in order to make (a,b) an instance of Eq. This requirement is described by the first line in the instance declaration using the expression: (Eq a, Eq b) => Eq (a,b) o The fifth declaration makes [a] an instance of Eq, whenever a is itself an instance of Eq in a similar way to the previous example. The context Eq a is used in the last equation in the declaration: (x:xs) == (y:ys) = x==y && xs==ys which contains three occurrences of the (==) operator; the first and third are used to compare lists of type [a], whilst the second is used to compare elements of type a, using the instance Eq a. Combining these five declarations, we obtain definitions for (==) on an infinite family of types including Int, Char, Bool, (Int,Bool), (Char,Int), [Char], (Bool,[Int]), [(Bool,Int)], etc...: ? 2 == 3 -- using Eq Int False (2 reductions, 10 cells) ? (["Hello"],3) == (["Hello"],3) -- using Eq ([[Char]],Int) True (31 reductions, 65 cells) ? On the other hand, any attempt to use (==) to compare elements of some type not covered by a suitable instance declaration will result in an error. For example, the standard prelude does not define the equality operation on triples of values: ? (1,2,3) == (1,2,3) ERROR: Cannot derive instance in expression *** Expression : (==) d125 (1,2,3) (1,2,3) *** Required instance : Eq (Int,Int,Int) ? This can be solved by including an instance declaration of the following form into a file of definitions loaded into Gofer: instance (Eq a, Eq b, Eq c) => Eq (a,b,c) where (x,y,z) == (u,v,w) = x==u && y==v && z==w Giving: ? (1,2,3) == (1,2,3) True (6 reductions, 20 cells) ? In general, an instance declaration has the form: instance context => predicate where definitions of member functions The context part of the declaration gives a list of predicates which must be satisfied for the predicate on the right hand side of the `=>' sign to be valid. Constant predicates (i.e. predicates not involving any type variables) required by an instance declaration (such as the predicate Eq Int required by the third declaration) need not be included in the context. If the resulting context is empty (as in the first three declarations above) then it may be omitted, together with the corresponding `=>' symbol. .ST 14.2.3 Testing equality of represented values --------------------------------------------- Instances of Eq can also be defined for other types, including user-defined datatypes, and unlike the instances described above, the definition of (==) need not be used to determine whether the values being compared have the same structure; it is often more useful to check that they represent the same value. As an example, suppose that we introduce a type constructor Set for representing sets of values, using a list to store the values held in the set: data Set a = Set [a] As usual, we say that two sets are equal if they have the same members, ignoring any repetitions or differences in the ordering of the elements in the lists representing the sets. This is achieved using the following instance declaration: instance Eq a => Eq (Set a) where Set xs == Set ys = xs `subset` ys && ys `subset` xs where xs `subset` ys = all (`elem` ys) xs A couple of examples illustrate the use of this definition: ? Set [1,2,3] == Set [3,4,1] False (49 reductions, 89 cells) ? Set [1,2,3] == Set [1,2,2,2,1,3] True (157 reductions, 240 cells) ? .ST 14.2.4 Instance declarations without members -------------------------------------------- It is possible to give an instance declaration without specifying any definitions for the member functions of the class. For example: instance Eq () In this case, the definition of (==) for the instance Eq () is left completely undefined, and hence so is the definition of (/=), which is defined in terms of (==): ? () == () {undefined_member (==)} (3 reductions, 34 cells) ? () /= () {undefined_member (==)} (4 reductions, 36 cells) ? .ST 14.2.5 Equality on function types --------------------------------- If an expression requires an instance of a class which cannot be obtained using the rules in the given instance declarations, then an error message will be produced when the expression is type-checked. For example, in general there is no sensible way to determine when a pair of functions are equal, and the standard prelude does not include a definition for an instance of the form Eq (a -> b) for any types a and b: ? (1==) == (\x->1==x) ERROR: Cannot derive instance in expression *** Expression : (==) d148 ((==) {dict} 1) (\x->(==) {dict} 1 x) *** Required instance : Eq (Int -> Bool) ? If for some reason, you would prefer this kind of error to produce an error message when an expression is evaluated, rather than when it is type-checked, you can use an instance declaration to specify the required behaviour. For example: instance Eq (a -> b) where (==) = error "Equality not defined between functions" Evaluating the previous expression once this instance declaration has been included now produces the following result: ? (1==) == (\x->1==x) {error "Equality not defined between functions"} (42 reductions, 173 cells) ? A limited form of equality can be defined for functions of type (a->b) if a has only finitely many elements, such as the boolean type Bool: instance Eq a => Eq (Bool -> a) where f == g = f False == g False && f True == g True [ASIDE: This instance declaration would not be accepted in a Haskell program which insists that the predicate on the right of the `=>' symbol contains precisely one type constructor symbol.] Using this instance declaration once for each argument, we can now test two functions taking boolean arguments for equality (assuming of course that their result type is also an instance of Eq). ? (&&) == (||) False (9 reductions, 21 cells) ? not == (\x -> if x then False else True) True (8 reductions, 16 cells) ? (&&) == (\x y-> if x then y else False) True (16 reductions, 30 cells) ? .ST 14.2.6 Non-overlapping instances -------------------------------- Other instance declarations for types of the form a -> b can be used at the same time, so long as no pair of declarations overlap. For example, adding the following instance declaration instance Eq a => Eq (() -> a) where f == g = f () == g () enables us to evaluate expressions such as: ? (\()->"Hello") == const "Hello" True (30 reductions, 55 cells) ? If however, we try to use instance declarations for types of the form (a -> b) and (Bool -> a) at the same time, then Gofer produces an error message similar to the following: ERROR "file" (line 37): Overlapping instances for class "Eq" *** This instance : Eq (a -> b) *** Overlaps with : Eq (Bool -> a) *** Common instance : Eq (Bool -> a) ? indicating that, given the task of testing two values of type (Bool->a) for equality, there are (at least) two definitions of (==) that could be used, with potentially different results being obtained in each case. Here is a further example of the use of non-overlapping instances of a class to define a function "cat" (inspired by the unix (tm) command of the same name) which uses the I/O facilities of Gofer to print the contents of one or more files on the terminal: class Cat a where cat :: a -> Dialogue instance Cat [Char] where cat n = showFile n done instance Cat [[Char]] where cat = foldr showFile done showFile name cont = readFile name abort (\s->appendChan stdout s abort cont) Given these declarations, an expression of the form: cat "file" can be used to display the contents of the named file, whilst a list of files can be printed one after the other using an expression of the form: cat ["file1", "file2", ..., "filen"]. .ST 14.3 Dictionaries ----------------- In order to understand some of the messages produced by Gofer, as well as some of the more subtle problems associated with overloaded functions, it is useful to have a rough idea of the way in which overloaded functions are implemented. The basic idea is that a function with a qualified type context => type where context is a non-empty list of predicates is implemented by a function which takes an extra argument for each predicate in the context. When the function is used, each of these parameters is filled by a `dictionary' which gives the values of each of the member functions in the appropriate class. None of these extra parameters is entered by the programmer. Instead, they are inserted automatically during type-checking. For the class Eq, each dictionary has at least two elements containing definitions for each of the functions (==) and (/=). A dictionary for an instance of Eq can be depicted by a diagram of the form: +--------+--------+--------- | | | | (==) | (/=) | ..... | | | +--------+--------+--------- In order to produce useful error messages and indicate the way in which dictionary expressions are being used, Gofer uses a number of special notations for printing expressions involving dictionaries: (#1 d) selects the first element of the dictionary d (#2 d) selects the second element of the dictionary d (#n d) selects the nth element of the dictionary d (note that (#0 d) is equivalent to the dictionary d). {dict} denotes a specific dictionary (the contents are not displayed). dnnn a dictionary variable representing an unknown dictionary is printed as a lower case letter `d' followed by an integer; e.g. d231. Note that, whilst these notations are used in output produced by Gofer and in the following explanations, they cannot be entered directly into Gofer expressions or programs -- even if you use a variable such as "d1" in an expression, Gofer will not confuse this with a dictionary variable with the same name (although Gofer might confuse you by using the same name in two different contexts!). Using these notations, the member functions (==) and (/=) of the class Eq behave as if they were defined by the expressions: (==) d1 = (#1 d1) (/=) d1 = (#2 d1) To understand how these definitions work, we need to take a look at a specific dictionary. Following the original instance declaration used for Eq Int, the corresponding dictionary is: d :: Eq Int +------------+------------+ | | | | primEqInt | defNeq d | | | | +------------+------------+ Note that the dictionary variable d is used as a name for the dictionary in this diagram, indicating how values within a dictionary can include references to the same dictionary. [ASIDE: It turns out that predicates play a very similar role for dictionaries as types play for normal values. This motivates our use of the notation d :: Eq Int to indicate that d is a dictionary for the instance Eq Int. One difference between these, particularly important for theoretical work, is that dictionary values are uniquely determined by predicates; if d1::p and d2::p for some predicate p, then d1 = d2.] The value held in the first element of the dictionary is the primitive equality function on integers, "primEqInt". The following diagram shows how the dictionary is used to evaluate the expression "2 == 3". Note that this expression will first be translated to "(==) d 2 3" by the type checker. The evaluation then proceeds as follows: (==) d 2 3 ==> (#1 d) 2 3 ==> primEqInt 2 3 ==> False The second element of the dictionary is a little more interesting because it uses the default definition for (/=) given in the original class definition which, after translation, is represented by the function "defNeq" defined by: defNeq d1 x y = not ((==) d1 x y) Notice the way in which the extra dictionary parameter is used to obtain the appropriate overloading. For example, evaluation of the expression "2 /= 3", which becomes "(/=) d 2 3" after translation, proceeds as follows: (/=) d 2 3 ==> (#2 d) 2 3 ==> defNeq d 2 3 ==> not ((==) d 2 3) ==> not ((#1 d) 2 3) ==> not (primEqInt 2 3) ==> not False ==> True [Clearly there is some scope for optimisation here; whilst the actual reduction sequences used by Gofer are equivalent to those illustrated above, the precise details are a little different.] If an instance is obtained from an instance declaration with a non-empty context, then the basic two element dictionary used in the examples above is extended with an extra dictionary value for each predicate in the context. As an example, the diagram below shows the dictionaries that will be created from the instance definitions in section 14.2.2 for the instance Eq (Int, [Int]). The functions "eqPair" and "eqList" which are used in these dictionaries are obtained from the definitions of (==) given in the instance declarations for Eq (a,b) and Eq [a] respectively: eqPair d (x,y) (u,v) = (==) (#3 d) x u && (==) (#4 d) y v eqList d [] [] = True eqList d [] (y:ys) = False eqList d (x:xs) [] = False eqList d (x:xs) (y:ys) = (==) (#3 d) x y && (==) d xs ys The dictionary structure for Eq (Int, [Int]) is as follows. Note that the Gofer system ensures that there is at most one dictionary for a particular instance of a class, and that the dictionary d1 :: Eq Int in this system is automatically shared between d2 and d3: d3 :: Eq (Int, [Int]) +------------+------------+------------+------------+ | | | | | | eqPair d3 | defNeq d3 | d1::Eq Int |d2::Eq [Int]| | | | | | +------------+------------+-----+------+-----+------+ | | +--------------+ | | | | d2 :: Eq [Int] V | +------------+------------+------------+ | | | | | | | eqList d2 | defNeq d2 | d1::Eq Int | | | | | | | +------------+------------+-----+------+ | | d1 :: Eq Int V | +------------+------------+ | | | | | | primEqInt | defNeq d1 |<--------------------------+ | | | +------------+------------+ Once again, it may be useful to see how these definitions are used to evaluate the expression "(2,[1]) == (2,[1,3])" which, after translation, becomes "(==) d3 (2,[1]) (2,[1,3])": (==) d3 (2,[1]) (2,[1,3]) ==> (#1 d3) (2,[1]) (2,[1,3]) ==> eqPair d3 (2,[1]) (2,[1,3]) ==> (==) (#3 d3) 2 2 && (==) (#4 d3) [1] [1,3] ==> (==) d1 2 2 && (==) (#4 d3) [1] [1,3] ==> (#1 d1) 2 2 && (==) (#4 d3) [1] [1,3] ==> primEqInt 2 2 && (==) (#4 d3) [1] [1,3] ==> True && (==) (#4 d3) [1] [1,3] ==> (==) (#4 d3) [1] [1,3] ==> (==) d2 [1] [1,3] ==> (#1 d2) [1] [1,3] ==> eqList d2 [1] [1,3] ==> (==) (#3 d2) 1 1 && (==) d2 [] [3] ==> (==) d1 1 1 && (==) d2 [] [3] ==> (#1 d1) 1 1 && (==) d2 [] [3] ==> primEqInt 1 1 && (==) d2 [] [3] ==> True && (==) d2 [] [3] ==> (==) d2 [] [3] ==> False .ST 14.3.1 Superclasses ------------------- In general, a type class declaration has the form: class context => Class a1 ... an where type declarations for member functions default definitions of member functions where Class is the name of the new type class which takes n arguments, represented by distinct type variables a1, ..., an. As in the case of instance declarations, the context that appears on the left hand side of the `=>' symbol specifies a list of predicates that must be satisfied in order to construct any instance of "Class". The predicates in the context part of a class declaration are called the superclasses of Class. This terminology is taken from Haskell where all classes have a single parameter and each of the predicates in the context part of a class declaration has the form C a1; in this situation, any instance of Class must also be an instance of each class C named in the context. In other words, each such C contains a superset of the types in Class. As an example of a class declaration with a non-empty context, consider the following declaration from the standard prelude which introduces a class Ord whose instances are types with both strict (<), (>) and non-strict (<=), (>=) versions of an ordering defined on their elements: class Eq a => Ord a where (<), (<=), (>), (>=) :: a -> a -> Bool max, min :: a -> a -> a x < y = x <= y && x /= y x >= y = y <= x x > y = y < x max x y | x >= y = x | y >= x = y min x y | x <= y = x | y <= x = y Notice that this definition provides default definitions for all of the member functions except (<=), so that in general only this single function needs to be defined to construct an instance of class Ord. There are two reasons for defining Eq as a superclass of Ord: o The default definition for (<) relies on the use of (/=) taken from class Eq. In order to guarantee that this is always valid we must ensure that every instance of Ord must also be an instance of Eq. o Given the definition of a non-strict ordering (<=) on the elements of a type, it is always possible to construct a definition for the (==) operator (and hence for (/=)) using the equation: x==y = x<=y && y<=x There will therefore be no loss in generality by requiring Eq to be a superclass of Ord, and conversely, no difficulty in defining an instance of Eq to accompany any instance of Ord for which an instance of Eq has not already be provided. As an example, the following definitions provide an alternative way to implement the equality operation on elements of the Set datatype described in section 14.2.3, in terms of the subset ordering defined in class Ord: instance Ord (Set a) => Eq (Set a) where x == y = x <= y && y <= x instance Eq a => Ord (Set a) where Set xs <= Set ys = all (`elem` ys) xs This definition is in fact no less efficient or effective than the original version. Dictionaries for superclasses are dealt with in much the same way as the instance specific dictionaries described above. For example, the general layout of a dictionary for an instance of Ord is illustrated in the following diagram: +--------+--------+--------+--------+--------+--------+--------+----- | | | | | | | | | (<) | (<=) | (>) | (>=) | max | min | Eq a | ..... | | | | | | | | +--------+--------+--------+--------+--------+--------+--------+----- Note the use of the seventh element of this dictionary which points to the dictionary for the appropriate instance of Eq. This is used in the translation of the default definition for (<) which is equivalent to: defLessThan d x y = (<=) d x y && (/=) (#7 d) x y .ST 14.3.2 Combining classes ------------------------ In general, a dictionary is made up of three separate parts: +-------------------+-------------------+-------------------+ | Implementation | Superclass | Instance specific | | of class members | Dictionaries | Dictionaries | | | | | +-------------------+-------------------+-------------------+ Each of these may be empty. We have already seen examples in which there are no superclass dictionaries (e.g. instances of Eq) and in which there are no instance specific dictionaries (e.g. Eq Int). Classes with no member functions (corresponding to dictionaries with no member functions) are sometimes useful as a convenient abbreviation for a list of predicates. For example: class C a where cee :: a -> a class D a where dee :: a -> a class (C a, D a) => CandD a makes CandD a an abbreviation for the context (C a, D a). Thinking of single parameter type classes as sets of types, the type class CandD corresponds to the intersection of classes C and D. Just as the type inferred for a particular function definition or expression does not involve type synonyms unless explicit type signatures are used, the Gofer type system will not use a single predicate of the form CandD a instead of the two predicates C a and D a unless explicit signatures are used: ? :t dee . cee \d129 d130 -> dee d130 . cee d129 :: (C a, D a) => a -> a ? :t dee . cee :: CandD a => a -> a \d129 -> dee (#2 d129) . cee (#1 d129) :: CandD a => a -> a ? In Haskell, all instances of a class such as CandD must have explicit declarations, in addition to the corresponding declarations for instances for C and D. This problem can be avoided by using the more general form of instance declaration permitted in Gofer; a single instance declaration: instance CandD a is all that is required to ensure that any instance of CandD can be obtained, so long as corresponding instances for C and D can be found. .ST 14.3.3 Simplified contexts -------------------------- Consider the function defined by the following equation: eg1 x = [x] == [x] || x == x This definition does not restrict the type of x in any way except that, if x :: a, then there must be instances Eq [a] and Eq a which are used for the two occurrences of the (==) operator in the equation. We might therefore expect the type of eg1 to be: (Eq [a], Eq a) => a -> Bool with translation: eg1 d1 d2 x = (==) d1 [x] [x] || (==) d2 x x However, as can be seen from the case where a=Int illustrated in section 14.3, given d1::Eq [a] we can always find a dictionary for Eq a by taking the third element of d1 i.e. (#3 d1)::Eq a. Since it is more efficient to select an element from a dictionary than to complicate both type and translation with extra parameters, the type assigned to "eg1" by default is: Eq [a] => a -> Bool with translation: eg1 d1 x = (==) d1 [x] [x] || (==) (#3 d1) x x In general, given a set of predicates corresponding to the instances required by an expression, Gofer will always attempt to find the smallest possible subset of these predicates such that all of the required dictionaries can still be obtained, whilst minimising the number of dictionary parameters that are used. The original type and translation for eg1 given above can be produced by including an explicit type signature in the file containing the definition of eg1: eg1 :: (Eq [a], Eq a) => a -> Bool eg1 x = [x] == [x] || x == x But even with this definition, Gofer will still always try to minimise the number of dictionaries used in any particular expression: ? :t eg1 \d153 -> eg1 d153 (#3 d153) :: Eq [a] => a -> Bool ? As another example, consider the expression "(\x y-> x==x || y==y)". The type and translation assigned to this term can be found directly using Gofer: ? :t (\x y-> x==x || y==y) \d121 d122 x y -> (==) d122 x x || (==) d121 y y :: (Eq b, Eq a) => a -> b -> Bool ? Note that the translation has two dictionary parameters d121 and d122 corresponding to the two predicates Eq a and Eq b respectively. Since both of these dictionaries can be obtained from a dictionary for the predicate Eq (a,b), we can use an explicit type signature to produce a translation which needs only one dictionary parameter: ? :t (\x y-> x==x || y==y) :: Eq (a,b) => a -> b -> Bool \d121 x y -> (==) (#3 d121) x x || (==) (#4 d121) y y :: Eq (a,b) => a -> b -> Bool ? .cc 8 .ST 14.4 Other issues ----------------- .ST 14.4.1 Unresolved overloading ----------------------------- Consider the use of the (==) operator in the following three situations: o In the expression "2 == 3", it is clear that the appropriate value for the equality operator in this case is primIntEq as defined by the instance declaration for Eq Int. The expression can therefore be translated to "primEqInt 2 3". o In the function definition "f x = x==x", we cannot completely determine the appropriate value for (==) because it depends on the type assigned to the variable "x", which may itself vary with different uses of the function "f". It is however possible to add an extra parameter to the definition, giving "f d x = (==) d x x" and taking the type of "f" to be Eq a => a -> Bool. In this way, the problem of finding the appropriate definition for the (==) operator is deferred until the function is actually used. o In the expression "[]==[]", the appropriate value for (==) must be obtained from the dictionary for some instance of the form Eq [a], but there is not sufficient information in the expression to determine what the value of the type variable a should be. Looking back to the instance declaration for Eq [a], we find that the definition of (==) depends on the value of the dictionary for the instance Eq a. In this particular case, it is clear that the expression will always evaluate to True, regardless of the value of this dictionary. Unfortunately, the only way that this can be detected is by evaluating the expression to see if the calculation can be completed without reference to the dictionary value (see the comments in the aside at the end of this section). Attempting to evaluate this expression in Gofer will therefore result in an error message indicating that the expression does not contain sufficient information to resolve the use of overloading in the expression: ? [] == [] ERROR: Unresolved overloading *** type : Eq [a] => Bool *** translation : \d129 -> (==) d129 [] [] ? Note that the expression has been converted into a lambda expression using the dictionary variable d129 to represent the dictionary for the unknown instance Eq [a]. One simple way to resolve the overloading in an expression of this kind is to use an explicit type signature. For example, if we specify that the second empty list is an empty list of type [Int]: ? [] == ([]::[Int]) True (2 reductions, 9 cells) ? The same problem occurs in Haskell, where it is described using the idea of an `ambiguous type' -- i.e. a type expression of the form context => type where one or more of the type variables appearing in the given context do not appear in the remaining part of the type expression. Further examples of unresolved overloading occur with other classes. As an example consider the class Reader defined by: class Reader a where parse :: String -> a unparse :: a -> String whose member functions provide methods for obtaining the string representation of an element of an instance type, and for converting such representations back into the original values. (The standard Haskell Text class contains similar functions.) Now consider the expression "parse . unparse" which maps values from some instance of Reader to values of another instance via an intermediate string representation. ? parse . unparse ERROR: Unresolved overloading *** type : (Reader a, Reader b) => a -> b *** translation : \d129 d130 -> parse d130 . unparse d129 ? One of the first things that might surprise the reader here is that the value produced by "parse . unparse" does not have to be of the same type as the argument; for example, we would not usually expect to have any sensible interpretation for a floating point number obtained from the string representation of a boolean value! This can be fixed by using an explicit type declaration, although the expression still produces unresolved overloading: ? (parse . unparse) :: Reader a => a -> a ERROR: Unresolved overloading *** type : Reader a => a -> a *** translation : \d130 -> parse d130 . unparse d130 ? Notice however that the type of this expression is not ambiguous so that the unresolved overloading in this example can be eliminated when the function is actually used: ? ((parse . unparse) :: Reader a => a -> a) 'a' 'a' (4 reductions, 11 cells) ? A more serious problem occurs with the expression "unparse . parse" which maps string values to string values via some intermediate type. Clearly this will lead to a problem with unresolved overloading: ? unparse . parse ERROR: Unresolved overloading *** type : Reader a => String -> String *** translation : \d130 -> unparse d130 . parse (#0 d130) ? Notice that the type obtained in this case is ambiguous; the type variable a which appears in the predicate Reader a does not appear in the type String -> String. There are a number of ways of resolving this kind of ambiguity: o Using an explicitly typed expression: Assuming for example that Char is an instance of Reader, we can write: ? unparse . (parse :: String -> Char) v113 {dict} . v112 {dict} (5 reductions, 42 cells) ? without any ambiguity. If such type signatures are used in a number of places, it might be better to define an auxiliary function and use that instead: charParse :: String -> Char charParse = parse ? unparse . charParse v113 {dict} . charParse (4 reductions, 37 cells) ? In such situations, it is perhaps worth asking if overloaded functions are in fact the most appropriate solution for the problem at hand! o Using an extra dummy parameter in a function definition. In a definition such as: f = unparse . parse we can introduce an additional dummy parameter `x' which is not used except to determine the type of the result produced by parse in f: f x = unparse . (parse `asTypeOf` (\""->x)) where the standard prelude operator `asTypeOf` defined by: asTypeOf :: a -> a -> a x `asTypeOf` _ = x is used to ensure that the type of parse in the definition of f is the same as that of the function (\""->x) -- in other words, the type must be String -> a where a is the type of the variable x. The resulting type for f is: f :: Reader a => a -> String -> String Notice how the addition of the dummy parameter has been used to eliminate the ambiguity present in the original type. This kind of `coding trick' is rather messy and is not recommended for anything but the simplest examples. [ASIDE: The idea of evaluating an expression with an ambiguous type to see if it does actually need the unspecified dictionaries could have been implemented quite easily in Gofer using an otherwise unused datatype Unresolved and generating instance declarations such as: instance Eq Unresolved where (==) = error "unresolved overloading for (==)" (/=) = error "unresolved overloading for (/=)" for each class. Given a particular expression, we can then use the type Unused in place of any ambiguous type variables in its type. The evaluation of the expression could then be attempted, either completing successfully if the dictionaries are not required, but otherwise resulting in a run-time error. This approach is not used in Gofer; instead, the programmer is notified of any unresolved polymorphism when the program is type checked, avoiding the possibility that a program might contain an undetected ambiguity.] .ST 14.4.2 `Recursive' dictionaries ------------------------------- Unlike Haskell, there are no restrictions on the form of the predicates that may appear in the context part of a Gofer class or instance declaration. This has a number of potentially useful applications because it enables the Gofer programs to use mutually `recursive' systems of dictionaries. One example of this is the ability to implement a large family of related functions using a group of classes instead of having to use a single class. The following example illustrates the technique with an alternative definition for the class Eq in which the (==) and (/=) operators are placed in different classes: class Neq a => Eq a where (==) :: a -> a -> Bool class Eq a => Neq a where (/=) :: a -> a -> Bool x/=y = not (x == y) [ASIDE: These declarations clash with those in the standard prelude and hence cannot actually be used in Gofer unless a modified version of the standard prelude is used instead.] If we then give instance declarations: instance Eq Int where (==) = primEqInt instance Neq Int and try to evaluate the expression "2==3" then the following system of dictionaries will be generated: d1 :: Eq Int d2 :: Neq Int +-----------+-----------+ +-----------+-----------+ | | | | | | +-->| primEqInt |d2::Neq Int+----->| defNeq d2 |d1::Eq Int +---+ | | | | | | | | | +-----------+-----------+ +-----------+-----------+ | | | +------------------------------<-------------------------------+ where the function "defNeq" is derived from the default definition in the class Neq and is equivalent to: defNeq d x y = not ((==) (#2 d) x y) Incidentally, if the instance declaration for Neq Int above had been replaced by: instance Neq a then the effect of these declarations would be similar to the standard definition of the class Eq, except that it would not be possible to override the default definition for (/=). In other words, this approach would give the same effect as defining (/=) as a top-level function rather than a member function in the class Eq: class Eq a where (==) :: a -> a -> Bool (/=) :: Eq a => a -> a -> Bool x /= y = not (x == y) There are other situations in which recursive dictionaries of the kind described above can be used. A further example is given in the following section. Unfortunately, the lack of restrictions on the form of class and instance declarations can also lead to problems in some (mostly pathological) cases. As an example, consider the class: class Bad [a] => Bad a where bad :: a -> a Without defining any instances of Bad, it is not possible to construct any dictionaries for instances of Bad: ? bad 2 ERROR: Cannot derive instance in expression *** Expression : bad d126 2 *** Required instance : Bad Int ? If however we add the instance declarations: instance Bad Int where bad = id instance Bad [a] where bad = id then any attempt to construct a dictionary for Bad Int will also require a dictionary for the superclass Bad [Int] and then for the superclass of that instance Bad [[Int]] etc... Since Gofer has only a finite amount of space for storing dictionaries, this process will eventually terminate when that space has been used up: ? bad 2 ERROR: Dictionary storage space exhausted ? [ASIDE: depending on the configuration of your particular version of Gofer and on the nature of the class and instance declarations that are involved, an alternative error message "ERROR: Too many type variables in type checker" may be produced instead of the message shown above.] From a practical point of view, this problem is unlikely to cause too many real difficulties: o Class declarations involving predicates such as those in the declaration of Bad are unlikely to be used in realistic programs. o All dictionaries are constructed before evaluation begins. This process is guaranteed to terminate because each new dictionary that is created uses up part of the space used to hold Gofer dictionaries. The construction process will either terminate successfully once complete, or be aborted as soon as all of the dictionary space has been used. It remains to see what impact (if any) this has on realistic programs, and if later versions of Gofer should be modified to impose some syntactic restrictions (as in Haskell) or perhaps some form of static checking of the contexts appearing in class and instance declarations. .ST 14.4.3 Classes with multiple parameters --------------------------------------- Gofer is the first language to support the use of type classes with multiple parameters. This again is an experimental feature of the language, intended to make it possible to explore the claims from a number of researchers about the use of such classes. Initial experiments suggest that multiple parameter type classes are likely to lead to large numbers of problems with unresolved overloading. Ultimately, this may mean that such classes are only of practical use in explicitly typed languages, or alternatively that a more powerful and general defaulting mechanism (similar to that used in Haskell with numeric classes) is required to support user controlled overloading resolution. The following declaration introduces a class Iso whose elements are pairs of isomorphic types: class Iso b a => Iso a b where iso :: a -> b The single member function "iso" represents the isomorphism mapping elements of type a to corresponding elements of type b. Note the `superclass' context in this declaration which formalises the idea that if a is isomorphic to b then b is also isomorphic to a. The class Iso therefore provides further examples of the recursive dictionaries described in the previous section. The fact that any type is isomorphic to itself can be described by the following instance declaration: instance Iso a a where iso x = x For example, the dictionary structure created in order to evaluate the expression "iso 2 = 3" is: d :: Iso Int Int +--------------+--------------+ | | | +-->| id |d::Iso Int Int+--+ | | | | | | +--------------+--------------+ | | | +------------------<-----------------+ ? iso 2 == 3 False (4 reductions, 11 cells) ? Our first taste of the problems to come occurs when we try to evaluate the expression "iso 2 == iso 3": ? iso 2 == iso 3 ERROR: Unresolved overloading *** type : (Eq a, Iso Int a) => Bool *** translation : \d130 d132 -> (==) d130 (iso d132 2) (iso d132 3) ? In this case, the "iso" function is used to map the integers 2 and 3 to elements of some type a, isomorphic to Int, and the values produced are then compared using (==) at the instance Eq a; there is no way of discovering what the value of a should be without using an explicit type signature. Further instances can be defined. The following two declarations are needed to describe the (approximate) isomorphism between lists of pairs and pairs of lists: instance Iso [(a,b)] ([a],[b]) where iso xs = (map fst xs, map snd xs) instance Iso ([a],[b]) [(a,b)] where iso (xs,ys) = zip xs ys Unfortunately, even apparently straightforward examples give problems with unresolved overloading, forcing the use of explicit type declarations: ? iso [(1,2),(3,4)] ERROR: Unresolved overloading *** type : Iso [(Int,Int)] a => a *** translation : \d126 -> iso d126 [(1,2),(3,4)] ? (iso [(1,2),(3,4)]) :: ([Int],[Int]) ([1, 3],[2, 4]) (22 reductions, 64 cells) ? A second example of a multiple parameter type class is defined as follows: class Ord a => Collects a b where emptyCollection :: b addToCollection :: a -> b -> b listCollection :: b -> [a] The basic intuition is that the predicate Collects a b indicates that elements of type b can be used to represent collections of elements of type a. A number of people have suggested using type classes in this way to provide features similar to the (similarly named, but otherwise different) classes that occur in object-oriented languages. Obvious implementations involve the use of ordered lists or binary search trees defined by instances of the form: data STree a = Empty | Node a (STree a) (STree a) instance Collects a [a] where .... instance Collects a (STree a) where .... Once again, there are significant problems even with simple examples using these functions. As an example, the standard way of defining a function of type: Collects a b => [a] -> b mapping a list of values to a collection of those values using the higher order function "foldr": listToCollection = foldr addToCollection emptyCollection actually produces a function with ambiguous type: ? :t foldr addToCollection emptyCollection \d139 d140 -> foldr (addToCollection d140) (emptyCollection d139) :: (Collects c b, Collects a b) => [a] -> b ? which cannot be resolved, even with an explicit type declaration. .ST 14.4.4 Overloading and numeric values ------------------------------------- One of the most common uses of overloading is to allow the use of the standard arithmetic operators such as (+), (*) etc. on the elements of a range of numeric types including integers and floating point values in addition to user defined numeric types such as arbitrary precision integers, complex and rational numbers, vectors and matrices, polynomials etc. In Haskell, these features are supported by a number of built-in types and a complex hierarchy of type classes describing the operations defined on the elements of each numeric type. As an experimental language, intended primarily for the investigation of general purpose overloading, Gofer has only two built-in numeric types; Int and Float (the second of which is not supported in all implementations). Similarly, although the Gofer system could be used to implement the full hierarchy of Haskell numeric classes, the standard prelude uses a single numeric type class Num defined by: class Eq a => Num a where -- simplified numeric class (+), (-), (*), (/) :: a -> a -> a negate :: a -> a fromInteger :: Int -> a The first four member functions (+), (-), (*), (/) are the standard arithmetic functions on instances of Num, whilst "negate" denotes unary negation. The final member function, fromInteger is used to coerce any integer value to the corresponding value in another instance of Num. An expression such as "fromInteger 3" is called an overloaded numeric constant and has type Num a => a indicating that it can be used as a value of any instance of Num. See below for examples. Both Float and Int are defined as instances of Num using primitive functions for integer and floating point arithmetic: instance Num Int where (+) = primPlusInt (-) = primMinusInt (*) = primMulInt (/) = primDivInt negate = primNegInt fromInteger x = x instance Num Float where (+) = primPlusFloat (-) = primMinusFloat (*) = primMulFloat (/) = primDivFloat negate = primNegFloat fromInteger = primIntToFloat These definitions make it possible to evaluate numeric expressions involving both types: ? 2 + 3 5 (3 reductions, 6 cells) ? 3.2 + 4.321 7.521 (3 reductions, 13 cells) ? Note however that any attempt to evaluate an expression mixing different arithmetic types is likely to cause a type error: ? 4.2 * 4 ERROR: Type error in application *** expression : 4.2 * 4 *** term : 4.2 *** type : Float *** does not match : Int ? Further problems occur when we try to define functions intended to be used with arbitrary instances of Num rather than specific numeric types. As an example of this, the standard prelude function "sum", roughly equivalent to: sum [] = 0 sum (x:xs) = x + sum xs has type [Int] -> Int, rather than the more general Num a => [a] -> a which could be used to find the sum of a list of numeric values in any instance of Num. The problem in this particular case is caused by the integer constant 0 in the first line of the definition. Replacing this with the expression fromInteger 0 leads to the following definition for a generic sum function of the required type: genericSum :: Num a => [a] -> a genericSum [] = fromInteger 0 genericSum (x:xs) = x + genericSum xs For example: ? genericSum [1,2,3] 6 (10 reductions, 18 cells) ? genericSum [1.0,2.0,3.0] 6.0 (11 reductions, 27 cells) ? The fromInteger function can also be used to solve the previous problem: ? 4.2 * fromInteger 4 16.8 (3 reductions, 13 cells) ? In Haskell, any integer constant k appearing in an expression is treated as if the programmer had actually written "fromInteger k" so that both of the preceding problems are automatically resolved. Unfortunately, this also creates some new problems; applying the function fromInteger to each integer constant in the previous examples causes problems with unresolved overloading: ? fromInteger 2 + fromInteger 3 ERROR: Unresolved overloading *** type : Num a => a *** translation : \d143 -> (+) d143 (fromInteger d143 2) (fromInteger d143 3) ? Once again, Haskell provides a solution to this problem in the form of a `default mechanism' for numeric types which, once the following problem has been detected, will typically `default' the unknown type represented by the type variable a above to be Int, so that the result is actually equivalent to the following: ? (fromInteger 2 + fromInteger 3) :: Int 5 (4 reductions, 8 cells) ? There are a number of problems with the Haskell default mechanism; both theoretical and practical. In addition, if a default mechanism of some form is used then it should also be capable of dealing with arbitrary user-defined type classes, rather than a small group of `standard' classes, in order to provide solutions to the unresolved overloading problems described in previous sections. Therefore, for the time being, Gofer does not support any form of default mechanism and overloaded numeric constants can only be obtained by explicit use of the fromInteger function. .ST 14.4.5 Constants in dictionaries -------------------------------- The Gofer system constructs new dictionaries as necessary, and deletes them when they are no longer required. At any one time, there is at most one dictionary for each instance of a class. Coupled with lazy evaluation, this has a number of advantages for classes in which member functions are defined by variable declarations as in section 9.10. As an example, consider the class Finite defined by: class Finite a where members :: [a] The only member in this class is a list enumerating the elements of the type. For example: instance Finite Bool where members = [False, True] instance (Finite a, Finite b) => Finite (a,b) where members = [ (x,y) | x<-members, y<-members ] In order to overcome any problems with unresolved overloading, explicit type signatures are often needed to resolve overloading: ? members :: [Bool] [False, True] (6 reductions, 26 cells) ? length (members :: [((Bool,Bool),(Bool,Bool))]) 16 (103 reductions, 195 cells) ? In some cases, the required overloading is implicit from the context and no additional type information is required, as in the following example: ? [ x && y | (x,y) <- members ] [False, False, False, True] (29 reductions, 90 cells) ? We can also use the technique of passing a `dummy' parameter to resolve overloading problems in a function definition: size :: Finite a => a -> Int size x = length (members `asTypeOf` [x]) which calculates the number of elements of a finite type, given an arbitrary element of that type: ? size (True,False) 4 (31 reductions, 60 cells) ? Now consider the expression "size (True,False) + size (True,False)". At first glance, we expect this to repeat the calculation in the previous example two times, requiring approximately twice as many reductions and cells as before. However, before this expression is evaluated, Gofer constructs a dictionary for Finite (Bool,Bool). The evaluation of the first summand forces Gofer to evaluate the value for "members" in this dictionary. Since precisely the same dictionary is used to calculate the value of the second summand, the evaluation of "members" is not repeated and the complete calculation actually uses rather fewer reductions and cells: ? size (True,False) + size (True,False) 8 (51 reductions, 90 cells) ? On the other hand, repeating the original calculation gives exactly the same number of reductions and cells as before, because the dictionaries constructed at the beginning of each calculation are not retained for use in subsequent calculations. We can force Gofer to construct specific dictionaries whilst reading from a file of definitions, so that they are not deleted at the end of each calculation, using an explicitly typed variable definition such as: boolBoolMembers = members :: [(Bool,Bool)] This forces Gofer to construct the dictionary Finite (Bool,Bool) when the file of definitions is loaded and prevents it from being deleted at the end of each calculation. Having loaded a file containing this definition, the first two attempts to evaluate "size (True,False)" give: ? size (True,False) 4 (31 reductions, 60 cells) ? size (True,False) 4 (20 reductions, 32 cells) ? .ST 14.4.6 The monomorphism restriction ----------------------------------- This section describes a technique used to limit the amount of overloading used in the definition of certain values to avoid a number of technical problems. This particular topic has attracted quite a lot of attention within the Haskell community where it is affectionately known as the `dreaded monomorphism restriction'. Although the initial formulation of the rule was rather cumbersome and limiting, the current version used in both Gofer and Haskell is unlikely to cause any problems in practice. In addition, many of the examples used to motivate the need for the monomorphism restriction in Haskell occur as a result of the use of implicitly overloaded numeric constants, described in section 14.4.4, and hence do not occur in Gofer. The monomorphism restriction takes its name from the way in which it limits the amount of polymorphism that can be used in particular kinds of declaration. Although we touch on this point in the following discussion, the description given here uses an equivalent, but less abstract approach, based on observations about the implementation of overloaded functions. Basic ideas: ------------ As we have seen, the implementation of overloading used by Gofer depends on being able to add extra arguments to a function definition to supply the required dictionary parameters. For example, given a function definition such as: isElement x [] = False isElement x (y:ys) = x==y || isElement x ys we first add a dictionary parameter for the use of the overloaded (==) operator on the right hand side, obtaining: isElement x [] = False isElement x (y:ys) = (==) d x y || isElement x ys Finally, we have to add the variable d as a new parameter for the function isElement, on both the left and right hand sides of the definition: isElement d x [] = False isElement d x (y:ys) = (==) d x y || isElement d x ys The monomorphism restriction imposes conditions which prevent this last step from being used for certain kinds of value binding. .cc 5 Declaration groups: ------------------- Before giving the full details, it is worth pointing out that, in general, the monomorphism restriction affects groups of value declarations rather than just individual definitions. To illustrate this point, consider the function definitions: f x y = x==y || g x y g x y = not (f x y) Adding an appropriate dictionary parameter for the (==) operator gives: f x y = (==) d x y || g x y g x y = not (f x y) The next stage is to make this dictionary variable into an extra parameter to the function f wherever it appears, giving: f d x y = (==) d x y || g x y g x y = not (f d x y) But now the right hand side of the second definition mentions the dictionary variable d which must therefore be added as an extra parameter to g: f d x y = (==) d x y || g d x y g d x y = not (f d x y) In other words, if dictionary parameters are added to any particular function definition, then each use of that function in another definition will also be require extra dictionary parameters. As a result, the monomorphism restriction has to be applied to the smallest groups of declarations such that any pair of mutually recursive bindings are in the same group. As the example above shows, if one (or more) of the bindings in a given declaration group is affected by the monomorphism restriction so that the appropriate dictionary parameters cannot be added as parameters for that definition, then the same condition must also be imposed on all of the other bindings in the group. [Adding the extra parameter to f in the example forces us to add an extra parameter for g; if extra parameters were not permitted for g then they could not be added to f.] .cc 5 Restricted bindings: -------------------- There are three main reasons for avoiding adding dictionary parameters to a particular value binding: o Dictionary parameters unnecessary. If the dictionary values are completely determined by context then it is not necessary to pass the appropriate values as dictionary parameters. For example, the function definition: f x = x == 0 || x == 2 can be translated as: f x = (==) {dict} x 0 || (==) {dict} x 2 where, in both cases, the symbol {dict} denotes the dictionary for Eq Int. As a further optimisation, once the dictionary is fully determined, this can be simplified to: f x = primEqInt x 0 || primEqInt x 2 o Dictionary parameters cannot be added in a pattern binding. One potential solution to this problem would be to replace the pattern binding by an equivalent set of function bindings. In practice, we do not use this technique because it typically causes ambiguity problems, as illustrated by the pattern binding: (plus,times) = ((+), (*)) Translating this into a group of function bindings gives: newVariable = ((+), (*)) plus = fst newVariable -- fst (x,_) = x times = snd newVariable -- snd (_,y) = y The type of newVariable is (Num a, Num b) => (a->a->a, b->b->b) so that the correct translation of these bindings using two dictionary variables gives: newVariable da db = ((+) da, (*) db) plus da db = fst (newVariable da db) times da db = snd (newVariable da db) and hence the correct types for plus and times are: plus :: (Num a, Num b) => a -> a -> a times :: (Num a, Num b) => b -> b -> b both of which are ambiguous. o Adding dictionary parameters may translate a variable definition into a function definition, loosing the benefits of shared evaluation. As an example, consider the following definition using the function "size" and the class Finite described in the previous section: twiceSize x = n + n where n = size x Since the variable n is defined using a local definition, we would not expect to have to evaluate size x more than once to determine the value of twiceSize. However, adding extra dictionary parameters without restriction gives: twiceSize d x = n d + n d where n d = size d x Now that n has been replaced by a function, the evaluation will be repeated, once for each occurrence of the expression "n d". In order to avoid this kind of problem, the monomorphism restriction does not usually allow extra parameters to be added to a variable definition. Thus the original definition above will be translated to give: twiceSize d x = n + n where n = size d x Note that the same rule is applied to variable definitions at the top-level of a file of definitions, resulting in an error if any dictionary parameters are required for the right hand side of the definition. As an example of this: twiceMembers = members ++ members which produces an error message of the form: ERROR "ex" (line 157): Unresolved top-level overloading *** Binding : twiceMembers *** Inferred type : [_7] *** Outstanding context : Finite _7 ? [COMMENT: A type expression of the form _n (such as _7 in this particular example) represents a fixed (i.e. monomorphic) type variable.] In the case of a variable declaration, the monomorphism restriction can be overcome by giving an explicit type signature including an appropriate context, to indicate that the variable defined is intended to be used as an overloaded value. In this case, we need only include the declaration: twiceMembers :: Finite a => [a] in the file containing the definition for twiceMembers to suppress the previous error message and allow the function to be used as a fully overloaded variable. Note that the monomorphism restriction interferes with the use of polymorphism. For example, the definition: aNumber = length (twiceMembers::[Bool]) + length (twiceMembers::[(Bool,Bool)]) where twiceMembers = members ++ members will not be accepted because the monomorphism restriction forces the local definition of "twiceMembers" to be restricted to a single overloading (the dictionary parameter supplied to each use of members must be constant throughout the local definition): ERROR "ex" (line 12): Type error in type signature expression *** term : twiceMembers *** type : [(Bool,Bool)] *** does not match : [Bool] ? Once again, this problem can be fixed using an explicit type declaration: aNumber = length (twiceMembers::[Bool]) + length (twiceMembers::[(Bool,Bool)]) where twiceMembers :: Finite a => [a] twiceMembers = members ++ members Formal definition: ------------------ The examples above describe the motivation for the monomorphism restriction, captured by the following definition: Dictionary variables will not be used as extra parameters in the definition of a value in a given declaration group G if: either: G includes a pattern binding or: G includes a variable declaration, but does not include an explicit type signature for any of the variables in the group. If neither of these conditions hold, then equivalent sets of dictionary parameters will be added to each declaration in the group. .pa .>appx_a .ST APPENDIX A: SUMMARY OF GRAMMAR This section gives a summary of the grammar for the language used by Gofer. The non-terminals and describe the syntax of expressions that can be entered into the Gofer interpreter and that of files of definitions that can be loaded into Gofer respectively. The following notational conventions are used in the Grammar which is specified using a variant of BNF: o are used to distinguish names of nonterminals from keywords. o vertical | bars are used to separate alternatives. o {braces} enclose items which may be repeated zero or more times. o [brackets] are used for optional items. o (parentheses) are used for grouping. o "quotes" surround characters which might otherwise be confused with the notations introduced above. The following terminal symbols are used but not defined by the grammar: VARID identifier beginning with lower case letter as described in section 6. CONID like VARID, but beginning with upper case letter. VAROP operator symbol not beginning with a colon, as described in section 6. CONOP constructor function operator, like VAROP, but beginning with a colon character. INTEGER integer constant, as described in section 7.3. FLOAT floating point constant, as described in section 7.4. CHAR character constant, as described in section 7.5. STRING string constant, as described in section 7.7. Top-level grammar ----------------- ::= "{" "}" module ::= [] top-level expression ::= ; multiple declarations | data = datatype declaration | type = synonym declaration | infixl [] {, } fixity declarations | infixr [] {, } | infix [] {, } | primitive :: primitive bindings | class declaration | instance declaration | value declarations ::= CONID {VARID} type declaration lhs ::= "|" multiple constructors | CONOP infix constructor | CONID {} constructor, n>=0 ::= , multiple bindings | primitive binding Type expressions ---------------- ::= [ => ] [qualified] type ::= "(" [ {, }] ")" general form | singleton context ::= CONID {} predicate ::= [ -> ] function type ::= CONID {} datatype or synonym | ::= VARID type variable | "(" ")" unit type | "(" ")" parenthesised type | "(" , {,} ")" tuple type | "[" "]" list type Class and instance declarations ------------------------------- ::= class [ =>] [] ::= where "{" "}" class body ::= ; multiple declarations | {, } :: member functions | [] default bindings ::= instance [ =>] [] ::= where "{" "}" instance body ::= ; multiple declarations | [] member definition Value declarations ------------------ ::= ; multiple declarations | {, } :: type declaration | [] function binding | [] pattern binding ::= = simple right hand side | {} guarded right hand sides ::= "|" = guarded right hand side ::= where "{" "}" local definitions ::= function of arity 0 | infix operator | "(" ")" section-like notation | "(" ")" | function with argument | "(" ")" parenthesised lhs Expressions ----------- ::= \ {} -> lambda expression | let "{" "}" in local definition | if then else conditional expression | case of "{" "}" case expression | :: typed expression | ::= operator application | ::= - negation | ::= function application | ::= variable | constructor | INTEGER integer literal | FLOAT floating point literal | CHAR character literal | STRING string literal | "(" ")" unit element | "(" ")" parenthesised expr. | ( ) sections | ( ) | "[" "]" list expression | "(" , {, } ")" tuple ::= [ {, } ] enumerated list | "|" list comprehension | .. arithmetic sequence | , .. | .. | , .. ::= , multiple qualifiers | <- generator | = local definition | boolean guard ::= ; multiple alternatives | [] alternative ::= -> single alternative | {} guarded alternatives ::= "|" -> guarded alternative Patterns -------- ::= operator application | + (n+k) pattern | ::= application | ::= variable | @ as pattern | ~ irrefutable pattern | _ wildcard | constructor | INTEGER integer literal | CHAR character literal | STRING string literal | "(" ")" unit element | "(" ")" parenthesised expr. | ( ) sections | ( ) | "[" [ {, } ] "]" list | "(" , {, } ")" tuple Variables and operators ----------------------- ::= | "(" - ")" variable ::= | | - operator ::= VARID | "(" VAROP ")" variable identifier ::= VAROP | ` VARID ` variable operator ::= CONID | "(" CONOP ")" constructor identifier ::= CONOP | ` CONID ` constructor operator .pa .>appx_b .ST APPENDIX B: CONTENTS OF STANDARD PRELUDE .in ../standard.prelude .pa .>appx_c .ST APPENDIX C: RELATIONSHIP WITH HASKELL 1.1 The language supported by Gofer is both syntactically and semantically similar to that of the functional programming language Haskell as defined in the report for Haskell version 1.1 [5]. This section details the differences between the two languages, outlined briefly in section 2. .cc 5 Haskell features not included in Gofer: --------------------------------------- o Modules o Arrays o Derived instances for standard classes -- the ability to construct instances of particular classes automatically. o Default mechanism for eliminating unresolved overloading involving numeric and standard classes. Since Gofer is an experimental system, it can be used with a range of completely different prelude files; there is no concept of `standard classes'. o Overloaded numeric constants. In the absence of a defaulting mechanism as mentioned in the previous item, problems with unresolved overloading make implicitly typed programming involving numeric constants impractical in an interpreter based system. o Full range of numeric types and classes. Gofer has only two primitive numeric types Int and Float (the second of which is not supported in the PC version). Although is would be possible to modify the standard prelude so that Gofer uses the same class hierarchy as Haskell, this is unnecessarily sophisticated for the intended uses of Gofer. o Datatype definitions in Haskell may involve class constraints such as: data Ord a => Set a = Set [a] It is not clear how such constraints should be interpreted (particularly in the light of the extended form of constraints used by Gofer) in such a way to make them useful whilst avoiding unwanted ambiguity problems. .cc 5 Gofer features not supported in Haskell: ---------------------------------------- o Type classes may have multiple parameters. o Predicates in type expressions may involve arbitrary type expressions, not just type variables as used in Haskell. o Instances of type classes can be defined at non-overlapping, but otherwise arbitrary types, as described in section 14.2.5. o List comprehensions may include local definitions, specified by qualifiers of the form = as described in section 10.2. o No restrictions are placed on the form of predicates that appear in the context for a class or instance declaration. This has a number of consequences, including the possibility of using (mutually) recursive groups of dictionaries, but means that decidability of the predicate entailment relation may be lost. This is not a great problem in practice, since all dictionary construction is performed before evaluation and supposedly non-terminating dictionary constructions will actually generate an error due to the limited amount of space available for holding dictionaries (see section 14.4.2). .cc 5 Other differences: ------------------ o Whilst superficially similar the approach to type classes in Gofer is quite different from that used in Haskell. In particular, the approach used in Gofer ensures that all necessary dictionaries are constructed before the evaluation of an expression begins, rather than being built (possibly several times) during the evaluation as is the case with Haskell. See section 14 and reference [11] for further details. o Input/Output facilities - Gofer supports only a subset of the requests available in Haskell. In principle, it should not be too difficult to add most of the remaining forms of request (with the exception of those associated with binary files) to Gofer. The principal motivation for including the I/O facilities in Gofer was to make it possible to experiment with simple interactive programs. o In Gofer, unary minus has greater precedence than any operator symbol, but lower than that of function application. In Haskell, the precedence of unary minus is the same as that of the infix (subtraction) operator of the same name. o In Haskell, the character `-' can only be used as the first character of an operator symbol. In Gofer, this character may appear in any position in an operator (except for symbols beginning with "--", which indicates the start of a comment). The only problems that I am aware of with this is that a lambda expression such as "\-2->2" will be parsed as such by a Haskell system, but cause a syntax error in Gofer. This form of lambda expression is sufficiently unusual that I do not believe this will cause any problems in practice; in any case, the parsing problem can be solved by inserting a space: "\ -2->2". o Pattern bindings are not currently permitted in either instance or class declarations. This restriction has been made simply for ease of implementation, is not an inherent problem with the type class system and is likely to be relaxed in later versions of Gofer if appropriate. I have yet to see any examples in which the lack of pattern bindings in class and instance declarations causes any kind of deficiency. o Qualified type signatures are not permitted for the member functions in Gofer class declarations. Once again, this restriction was made for ease of implementation rather than any pressing technical issues. It is likely that this restriction will be relaxed in future versions of Gofer, although I am not convinced that proper use can be made of such member functions without some form of nested instance declarations (yuk!). o The definition of the class Text given in the standard prelude does not include the Haskell functions for reading/parsing values from strings; the only reason for omitting these functions was to try to avoid unnecessary complexity in the standard prelude. The standard prelude can be modified to include the appropriate additional definitions if these are required. .cc 5 Known problems in Gofer: ------------------------ o The null escape sequence "\&" is not generated in the printable representations of strings produced by both the primitive function primPrint (used to implement the show' function) and the version of show defined in the standard prelude. This means that certain strings values are not printed correctly e.g. show' "\245\&123" produces the string "\245123". This is unlikely to cause too many problems in practice. o Unification of a type variable a with a type expression of the form T a where T is a synonym name whose expansion does not involve a will fail. It is not entirely clear whether this behaviour is correct or not. o Formfeeds '\f' and vertical tabs '\v' are not treated as valid whitespace characters in the way suggested by the Haskell report. o Inability to recover from program stack overlow errors in some situations. This problem only affects the PC implementation of Gofer. o Implementation of ReadFile may lose referential transparency; the response to a particular ReadFile request may be affected by a later WriteFile or AppendFile request for the same file. Whilst this problem can be solved for UNIX based implementations, I have not yet found a portable solution suitable for all of the systems on which Gofer can be used. .cc 5 Areas for possible future improvement: -------------------------------------- o Relaxing the restriction on type synonyms in predicates. o General purpose automatic default mechanism for eliminating certain forms of unresolved overloading. o Improved checking and use of superclass and instance constraints during static analysis and type checking. o Simple facility to force dictionary construction at load-time. o Provision for shell escapes :! etc within the Gofer interpreter. o Debugging facilities, including breakpoints and tracing from within interpreter. o Separate interpreter and compiler programs for creating standalone applications using Gofer. .pa .>appx_d .ST APPENDIX D: USING GOFER WITH BIRD+WADLER Bird and Wadler's textbook [1] gives an excellent introduction to functional programming, providing an insight into both basic techniques and matters of programming style as well as describing the underlying mathematics and its use for program development and derivation. Most of the programs in that book can be used with Gofer although there are a number of differences between the two notations. Fortunately, it is not difficult to translate from one notation to the other. The following points are particularly useful for this: o Type constructors in Gofer begin with capital letters (e.g. Bool, Char etc..) where lower case is used in [1] (e.g. bool, char, etc..). Note that Gofer has no general numeric type "num" as used in [1]; Use either Int, Float, or overloading in Gofer as appropriate. o Datatype definitions in [1] are written in the form lhs::=constrs. The equivalent definition in Gofer is: data lhs = constrs. Similarly, a type synonym definition in [1] of the form lhs == rhs can be written in Gofer as: type lhs = rhs. o The differences between the syntax used for guarded equations in Gofer compared with the notation used in [1] have already been discussed in section 9.2. For example: Using the notation of [1]: Using Gofer: filter p (x:xs) filter p (x:xs) = x : filter p xs, if p x | p x = x : filter p xs = filter p xs, otherwise | otherwise = filter p xs o In Gofer, list comprehension qualifiers are separated by commas rather than semicolons as used in [1]. o A number of the function names and types in the standard prelude are different: [1] Gofer [1] Gofer --- ----- --- ---- (#) length takewhile takeWhile (~) not dropwhile dropWhile (/\) (&&) zipwith zipWith (\/) (||) swap flip (!) (!!) in elem (--) (\\) scan scanl hd head some any tl tail listmin minimum decode chr listmax maximum code ord See appendix B for a complete list of standard functions in Gofer. The version of foldl using "strict" which appears in [1] is available in Gofer as the function "foldl'". The role of "zip" and "zipwith" in [1] is filled by the "zip" and "zipWith" families of functions in Gofer. An expression of the form "zip (xs,ys)" in [1] is equivalent to "zip xs ys" in Gofer etc... o Gofer does not enforce the condition assumed in [1] that the left hand sides of each of the equations defining a function must be disjoint. o The equality operator in Gofer is written as "==" and the single equality character "=" is a reserved symbol used to separate left and right hand sides of equations. Many C programmers will be familiar with this kind of notation (together with the kinds of problems it can create!). o Some of the identifiers used in [1] are reserved words in Gofer. Examples that are particularly likely to occur include "in" and "then". .pa .>appx_e .ST APPENDIX E: PRIMITIVES [WARNING: The features described in this appendix are typically only needed when alternative versions of the standard prelude are created. These features should only be used by expert users; misuse may lead to failure and runtime errors in the Gofer interpreter. It is not usually a good idea to use primitive functions directly in your programs.] A number of primitive functions are builtin to the Gofer interpreter, and may be bound to function symbols using a declaration of the form: primitive name1 code1, name2 code2, ...., namen coden :: type where each name is an identifier (or an operator symbol enclosed by parentheses) and each code is a string literal taken from the table below. The type specified to the right of the :: symbol must be a valid type for the functions being defined -- WARNING: GOFER DOES NOT ATTEMPT TO CHECK FOR SUITABILITY OF THE DECLARED TYPE. The following definition, taken from the standard prelude, illustrates the use of this feature to bind a function named primPrint to the primitive function with code name string "primPrint" and type Int -> a -> String -> String: primitive primPrint "primPrint" :: Int -> a -> String -> String The primitive functions currently available are: category code name string type -------- ---------------- ---- integer primPlusInt Int -> Int -> Int arithmetic primMinusInt Int -> Int -> Int primMulInt Int -> Int -> Int primDivInt Int -> Int -> Int primModInt Int -> Int -> Int primRemInt Int -> Int -> Int primNegInt Int -> Int -> Int floating primPlusFloat Float -> Float -> Float point primMinusFloat Float -> Float -> Float arithmetic primMulFloat Float -> Float -> Float primDivFloat Float -> Float -> Float primNegFloat Float -> Float -> Float coercion primIntToChar Int -> Char -- chr in the standard prelude functions primCharToInt Char -> Int -- ord in the standard prelude primIntToFloat Int -> Float -- implements fromInteger equality primEqInt Int -> Int -> Bool and <= primLeInt Int -> Int -> Bool primitives primEqFloat Float -> Float -> Bool primLeFloat Float -> Float -> Bool .cc 5 generic primGenericEq a -> a -> Bool ordering primGenericNe a -> a -> Bool primitives primGenericGt a -> a -> Bool primGenericLe a -> a -> Bool primGenericGe a -> a -> Bool primGenericLt a -> a -> Bool These functions implement the standard generic (i.e. non overloaded) ordering primitives. They are not currently used in the standard prelude. A simplified prelude may be created by binding the standard operator symbols (==), (/=), (>), (<=), (>=) and (<) to these functions respectively. output primPrint Int -> a -> String -> String This function is used to implement the show' function in the standard prelude and is not usually used directly. primPrint d e s produces a textual representation of the value of the expression e as a string, followed by the string s. The integer parameter d is used as an indicator of the current precedence level. The primPrint function is the standard method of printing the value of an expression whose type is not equivalent to the type String used by the top-level of the Gofer interpreter. sequencing primStrict (a -> b) -> a -> b The primStrict function (bound to the identifier "strict" in the standard prelude) forces the evaluation of its second argument before the function supplied as the first argument is applied to it. See section 9.4 for an illustration. .pa .>appx_f .ST APPENDIX F: INTERPRETER COMMAND SUMMARY Command Description ------- ----------- Analyse expression for errors, typecheck and evaluate. If the expression has type Dialogue, execute as a program using the I/O facilities as described in section 12. If the expression has type String, evaluate and print result as a lazy list of characters. In any other case, the standard prelude function show' is applied to the expression and used to print the value of the result in the form of a string, as in the previous case. :t Analyse expression for errors, typecheck and print the :type translation and inferred type of the term. :T :q Exit Gofer interpreter. :quit :Q :? Display summary of interpreter commands. :h :H :l f1 .. fn Removes any previously loaded files of definitions and attempts to load the contents of the files f1 upto fn one after the other. :L Remove any previously loaded files of definitions. Only those functions and values defined in the standard prelude will still be be available. :load Equivalent forms of the :l command. :L :a f1 .. fn Load the contents of the files f1 upto fn in addition to any previously loaded files. If any of the files of definitions which have already been loaded have been modified since they were last read then they are automatically reloaded before any of the files f1 upto fn are read. If successful, a command of the form ":l f1 ..fn" is equivalent to the sequence of commands: :l :a f1 . . :a fn :also Equivalent forms of the :a command. :A :r Repeat the last load command, attempting to reload any files which have subsequently been modified. Since later files may depend on the definitions in earlier ones, once one file has been reloaded, all subsequent files will also need to be reloaded. :reload Equivalent forms of the :r command. :R :e file Suspend current Gofer session and start an editor program to modify or view the named file. The Gofer session will be resumed when the editor program terminates, and any script files that have been changed will be reloaded automatically. Note that a separate editor program is required and that Gofer must be properly installed to use this feature. The default editor is usually vi (Calvin version 2.0 is a good substitute for a PC), although this may have been changed when your system was installed. In any case, you can always substitute an editor of your choice by setting the environment variable EDITOR to the name of your favourite editor program. There are a number of factors which will affect your choice of editor. On a slow machine, with only a limited amount of memory, you will probably need to choose a relatively small editor which can be loaded reasonably quickly and does not require too much memory. On a more powerful system, you may find it more convenient to use Gofer from a window based environment, running your editor in one window with Gofer in another. :e Using the :e command without specifying a particular file to be edited starts up an editor program as described above either for the file of definitions most recently loaded into Gofer or, if an error occurred whilst loading a file of definitions, for the file of definitions in which the error was last detected. With many editor programs, it is even possible to start the editor at the line where the error occurred. As before, it is possible to change the default behaviour of Gofer in this case by setting the environment variable EDITLINE to a command string which can be used to start the editor program with a given file at a specific line number. The positions in the string at which the file name and line number values should be inserted should be indicated by the strings "%s" and "%d" respectively, and may appear in either order. The default command string, which is used if EDITLINE is not set is "vi +%d %s". :edit Equivalent forms of the :e command. :E .pa .>appx_g .ST APPENDIX G: BIBLIOGRAPHY [1] Introduction to functional programming, Richard Bird and Philip Wadler, Prentice Hall International, 1989. [2] The Implementation of functional programming languages, Simon L. Peyton Jones, Prentice Hall International, 1987. [3] Lambda Lifting: Transforming Programs to Recursive Equations, Thomas Johnsson, in Lecture Notes in Computer Science 201, Springer Verlag, 1985. [but try to get a copy of the version of this paper included in Johnsson's thesis which benefits from an extended typeface and is a little easier to read!] [4] How to make ad-hoc polymorphism less ad-hoc, Philip Wadler and Stephen Blott, University of Glasgow, in the proceedings of the 16th ACM annual symposium on Principles of Programming Languages, Austin, Texas, January 1989. [5] Report on the programming language Haskell, a non-strict purely functional language (Version 1.1), Paul Hudak, Philip Wadler et al. Technical report Yale University/Glasgow University. August, 1991. [6] Introduction to Orwell 6.00, Philip Wadler and Quentin Miller, University of Oxford, 1990. [7] Lazy ML user's manual, Lennart Augustsson and Thomas Johnsson, 1990. [8] Computing with lattices: An application of type classes, Mark P. Jones, Technical report PRG-TR-11-90, Programming Research Group, Oxford University Computing Laboratory, June 1990. [9] Towards a theory of qualified types, Mark P. Jones, Technical report PRG-TR-6-91, Programming Research Group, Oxford University Computing Laboratory, April 1991. [10] Type inference for qualified types, Mark P. Jones, Technical report PRG-TR-10-91, Programming Research Group, Oxford University Computing Laboratory, June 1991. [11] A new approach to type classes, Mark P. Jones, distributed to Haskell mailing list 1991. [12] Practical issues in the implementation of qualified types, Mark P. Jones, Forthcoming 1991.