notes228.doc

.co This is the source form of the release notes for Gofer 2.28
.co
.co Mark P Jones January 1993
.co-------------------------------------------------------------------|
.>release.228
-----------------------------------------------------------------------
       __________   __________   __________   __________   ________
      /  _______/  /  ____   /  /  _______/  /  _______/  /  ____  \
     /  / _____   /  /   /  /  /  /______   /  /______   /  /___/  /
    /  / /_   /  /  /   /  /  /  _______/  /  _______/  /  __   __/
   /  /___/  /  /  /___/  /  /  /         /  /______   /  /  \  \ 
  /_________/  /_________/  /__/         /_________/  /__/    \__\

  Functional programming environment, Version 2.28

  Copyright Mark P Jones 1993.

  Release notes
-----------------------------------------------------------------------

This document is intended to be used as a supplement to the original
user manual ``An introduction to Gofer version 2.20'' and release
notes for Gofer 2.21 (previously supplied in a file called `update').

If you would like to be informed when bug-fixes or further versions
become available, please contact me at jones-mark@cs.yale.edu (if you
have not already done so) and I will add your name to the list.

Please contact me if you have any questions about the Gofer system, or
if you need some advice or help to complete a port of Gofer to a new
platform.


ACKNOWLEDGMENTS:
A lot of people have contributed to the development of Gofer 2.28 with
their support, encouragement, suggestions, comments and bug reports.
There are a lot of people to thank:

                 Ray Bellis            Brent Benson
               David Bolton           Rodney Brown
                Dave Cattrall         Manuel Chakravarty
                Rami El Charif        Stuart Clayman
                Andy Duncan            Bernd Eckenfels
             Stephen Eldridge         Jeroen Fokker
                Andy Gill             Annius Groenink
            Dipankar Gupta           Guenter Huebel
                 Jon Hallett           Kevin Hammond
               Peter Hancock             Ian Holyer
              Andrew Kennedy          Marnix Klooster
                 Tom Lane           Hiroyuki Matsuda
               Aiden McCaughey        Tobias Nipkow
              Rainer Orth               Will Partain
               Simon Peyton Jones        Ian Poole
                Mark Raemer             Dave Rushall
              Julian Seward            Carol Tumey
               Goran Uddeborg          Gavin Wraith
               Bryan Scattergood     Matthew Smith
             Bernard Sufrin           Philip Wadler

This list isn't complete, and I apologize in advance if I have
inadvertently left your name out.
.pa
.ti Release Notes v2.28
.co-------------------------------------------------------------------|
.ST 1. MINOR ENHANCEMENTS AND BUGFIXES

The following sections list the minor enhancements and bugfixes that
have been made to Gofer since the release of Gofer version 2.23.  More
significant changes are described in later sections.


.ST 1.1  Enhancements
-----------------
  o  For systems without the restrictions of older PCs, Gofer now uses
     multiple hash tables to speed the lookup of globally defined
     functions.  Loading large programs into Gofer is now much faster
     as a result.  In one example, the time taken to load a 13,000 line
     program spread across 40 individual script files was reduced by a
     factor of five!

  o  For the most most part, internal errors (which shouldn't normally
     appear anyway) no longer terminate the interpreter.

  o  Better handling for programs with objects whose type involves more
     than 26 type variables (though whether anyone has real practical
     applications for such beasts, I'm rather doubtful).

  o  The Gofer system now supports I/O requests GetProgName, GetArgs
     and GetEnv.  The first two requests don't have any sensible
     interpretation within the interpreter, so GetProgName always
     returns "", while GetArgs returns [].  These I/O requests are most
     useful when producing standalone applications with the Gofer
     compiler where they do indeed give the name of the program and the
     list of command line arguments as expected.

  o  Added primitives for direct comparison of characters.  The
     original definitions of character equality and ordering in terms
     of the equality and ordering on integers was elegant, but for some
     examples, a substantial number of the total reductions in a given
     program was taken up with calls to ord, an unnecessary
     distraction.

  o  Small improvements in the speed of execution of the runtime machine,
     particularly when Gofer is compiled using the GNU C compiler.
 
  o  Enabled the use of GNU C specific options to store frequently used
     global variables in CPU registers.  This is perhaps most useful
     for speeding up the performance of standalone applications
     produced using the Gofer compiler.

  o  Changed definitions in standard preludes to provide overloaded
     versions of sum, product, sums, products, abs, signum and (^).
     Also added a genericLength function as in Haskell.  Finally,
     added Text as a superclass of Num, again for Haskell compatibility.

  o  Added a new primitive function: openfile :: String -> String that
     can be used to read the contents of a file (named by the argument
     string) as a (lazy) stream of characters.  (The implementation is
     in terms of a primitive which can also be used to implement the
     hbc openFile function, provided that you also define the Either
     datatype used there.)

  o  Added support for a simple selection of operators for monadic I/O,
     mutable variables etc. based on Lambda var (developed at Yale) and
     the Glasgow I/O system.  I will provide more documentation on this
     as soon as there is a better consensus on the names of the
     datatypes and functions that should be included in systems like
     this.
 
  o  The error function is now implemented using a primitive function.

  o  Added support for floating point primitives:

         pi          :: Float

         sin, asin,
         cos, acos,
         tan, atan,
         log, log10,
         exp, sqrt   :: Float -> Float

         atan2       :: Float -> Float -> Float
         truncate    :: Float -> Int

  o  Added support for the use of GNU readline (or equivalent) library
     to be used to enhance the user interface with command line
     editing.  See the source makefile for instructions on how to use
     this.

  o  Added floating point support to PC version of Gofer (even the
     version for humble 8086 PCs will now support floating point).
     Thanks to Jeroen Fokker for this!

  o  I/O datatype definitions and otherwise symbol are now builtin to
     the Gofer system.

  o  Other minor tweaks and improvements.


.ST 1.2  Bug fixes
--------------
Nobody really likes to dwell on bugs, especially when they have been
eliminated.  But for those of you who want to know, here is a summary of
the bugs discovered and fixed in Gofer 2.28:

  o  End of file does not imply end of line (only significant on
     certain systems ... I has made an assumption which happens to hold
     under DOS and Unix, but was not true for other systems).

  o  Code generator produced incorrect code for some conditional
     expressions involving local variables (fairly obscure).

  o  Some conditional expressions entered into the interpreter were
     evaluated incorrectly, leading to unexpected evaluation errors.

  o  A small potential space leak concerned with saving the names of
     files passed to the editor from within Gofer was eliminated.

  o  A subtle bug, which only occurred when a garbage collection
     occurred in the middle of an attempt to update a cell with an
     indirection has been fixed.

  o  Fixing the definitions of the div and quot operators to agree with
     Haskell 1.2 (these had been changed in the transition from 1.1 to
     1.2 without my noticing).

  o  Corrected bug in string matching code (part of the :names command)
     which previously allowed "*e*p" to match with "negate"!

  o  Nested comments were not always handled correctly when they
     occurred at the very end of a script file.

  o  Added new clauses to parser to improve and correct error messages
     produced by some examples.

  o  Other miscellaneous tweaks and fixes.

There are no other currently known bugs in Gofer.  But someone is bound
to find a new one within hours of the release of 2.28 if past
experience is anything to go by.  If that someone is you, please let me
know!


.co-------------------------------------------------------------------|
.ST 2. USER INTERFACE EXTENSIONS

The user interface of the previous release has been extended a little
to support a range of new features, intended to make the Gofer
environment more convenient for program development.  Further details
are given in the following sections.

.ST 2.1  Customizing the Gofer system
---------------------------------
Often there will be several people using Gofer on the same system.  Not
everyone will want to be using the system in the same way.  For example,
some users may wish to use their own version of the prelude or start the
interpreter with particular command line options.

It has always been possible to do this by installing Gofer in an
appropriate manner.  But, having had more than a couple of enquiries
about this, I wanted to take some time to spell the process out more
clearly.  The following description will be biased towards those people
using Gofer on Unix-like systems, but the same basic principles can be
applied with other operating systems too.

The Gofer interpreter and prelude files will typically be installed in
a given directory, accessible to all users on the system.  For the sake
of this example, let's assume that this is /usr/local/lib/Gofer.  Each
user could take a copy of the Gofer interpreter into their own file
space, but a much better option is for each user to use a short script
file stored somewhere on their path.  For example, the path on my Unix
account includes a subdirectory called bin and I store the following
script file `gofer' in this directory:

    #!/bin/sh
    #
    # A simple shell script to invoke the Gofer interpreter and set
    # the path to the prelude file.  Ultimately, you might want to
    # copy this file into your own bin directory so that you can record
    # your favourite command line settings or use a different prelude
    # file ...
    #
    GOFER=/usr/local/lib/Gofer/standard.prelude
    export GOFER
    exec /usr/local/lib/Gofer/gofer $*

I happen to use the standard prelude file and the default settings for
all the command line options.  If, for example, I wanted to use a
different prelude file, a smaller heap and omit the printing of
statistics about the number of reductions and cells used in an
evaluation, I can modify the script to reflect this:

    #!/bin/sh
    #
    # A modified version of the above script
    #
    GOFER=/usr/local/lib/Gofer/simple.prelude
    export GOFER
    exec /usr/local/lib/Gofer/gofer -h20000 -s $*

Of course, it is also possible to keep both of these short scripts in
my bin directory, so that I have the choice of starting up Gofer in
several different configurations, depending on the kind of work I'm
going to be doing with it.


.ST 2.2  Command line options
--------------------------
Gofer 2.28 supports a number of options which can be set, either on the
command line when Gofer interpreter is started, or using the :set
command within in the interpreter.  Using the :set command without any
arguments produces a list of all the command line options available:

   ? :set
   TOGGLES: groups begin with +/- to turn options on/off resp.
   s    Print no. reductions/cells after eval
   t    Print type after evaluation
   d    Show dictionary values in output exprs
   f    Terminate evaluation on first error
   g    Print no. cells recovered after gc
   c    Test conformality for pattern bindings
   l    Literate scripts as default
   e    Warn about errors in literate scripts
   i    Apply fromInteger to integer literals
   o    Optimise use of (&&) and (||)
   u    Catch ambiguously typed top-level vars
   .    Print dots to show progress
   w    Always show which files loaded
   1    Overload singleton list notation
   k    Show kind errors in full

   OTHER OPTIONS: (leading + or - makes no difference)
   hnum Set heap size (cannot be changed within Gofer)
   pstr Set prompt string to str
   rstr Set repeat last expression string to str

   Current settings: +sfceow1 -tdgliu.k -h100000 -p? -r$$
   ?

Most of these are the same as in the previous release of Gofer.  The
following sections outline the few changes that have been made.  The
`1' and `k' toggles are for use with constructor classes and will be
described in Section 4.


.ST 2.2.1  Print dots to show progress
----------------------------------
One of the first differences that you might notice when running the
new version of Gofer is that the rows of dots printed when loading a
script file:

    ? :l examples
    Reading script file "examples":
    Parsing....................................
    Dependency analysis........................
    Type checking..............................
    Compiling..................................

    Gofer session for:
    /usr/local/lib/Gofer/standard.prelude
    examples
    ?

are no longer printed while script files are loaded.  The rows of dots
are useful for showing progress on slow machines (like the PC on which
Gofer was originally developed) where it is reassuring to know that the
system has not crashed, and is simply working its way through one
particular phase of the system.  However, on a faster system, the dots
are not necessary and printing them can impose a surprising overhead on
the time it takes to load files.  As a default, Gofer now simply prints
the names of each phase (Parsing, Dependency Analysis, Type checking
and Compiling) and, when that phase is complete, backspaces over it to
erase it from the screen.  If you are fortunate enough to be using a
fast machine, you may not always see the individual words as they flash
past.  After loading a file, your screen will typically look something
like this:

    ? :l examples
    Reading script file "examples":
                   
    Gofer session for:
    /usr/local/lib/Gofer/standard.prelude
    examples
    ?

On some systems, the use of backspace characters to erase a line may
not work properly.  One particular example of this occurs if you try to
run Gofer from within emacs.  In this case, you may prefer to use the
original setting, printing the lines of dots by giving the command:

    :set +.

The default setting is (as illustrated above, :set -.).  In practice,
you will probably want to include the appropriate setting for this
option in your startup script (see Section 2.1).


.ST 2.2.2  Always show which files loaded
-------------------------------------
Some people may feel that the list of filenames printed by Gofer after
successfully loading one or more script files is redundant.  This is
particularly likely if you are using the (usually default) :set -.
option since the list of files loaded will probably still be on the
screen.  The list of filenames can be suppressed using the :set -w
option as follows:

    ? :l examples
    Reading script file "examples":
                   
    Gofer session for:
    /usr/local/lib/Gofer/standard.prelude
    examples
    ? :set -w
    ? :l examples
    Reading script file "examples":
    ?

The default setting can be recovered using a :set +w command.

Note that you can also use the :info command (without any arguments) as
described in Section 2.3.2 to find out the list of files loaded into the
current Gofer session.  This should be particularly useful if you choose
the :set -w option.


.ST 2.2.3  Set repeat string
------------------------
The previous expression entered into the Gofer system can be recalled
as part of the next expression using the symbol $$:

    ? map (1+) [1..10]
    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    (101 reductions, 189 cells)
    ? filter even $$
    [2, 4, 6, 8, 10]
    (130 reductions, 215 cells)
    ?

This feature was provided and documented in the previous release of
Gofer.  However, it is possible that you may prefer to use a different
character string.  This is the purpose of the -rstr option which sets
the repeat string to str.  For example, user's of SML might be more
comfortable using:

    ? :set -rit
    ? 6*7
    42
    (3 reductions, 7 cells)
    ? it + it
    84
    (4 reductions, 11 cells)
    ?

Another reason for making this change might be that you have a program
which uses the symbol $$ as an operator.  Each occurrence of the $$ symbol
in a script file will be interpreted as the correct operator, whatever
the value of the repeat string.  But, if the default :set -r$$ setting is
used, any occurrence of $$ in an expression entered directly to the
evaluator will be taken as a reference to the previous expression.

Note that the repeat string must be either a valid Haskell identifier or
symbol, although it will always be parsed as an identifier.  If the
repeat string is set to a value which is neither an identifier or symbol
(for example, :set -r0) then the repeat last expression facility will be
disabled altogether.


.ST 2.2.4  Other changes
--------------------
Comparing the list of command line options in Section 2.2 with the list
produced by previous versions of Gofer will reveal some other small
differences not already mentioned above.  The changes are as follows:

  o  The default setting for the d toggle (show dictionaries in output
     expressions) has been changed to off (:set -d).  For a lot of
     people, the appearance of dictionary values was rather confusing
     and of little use.  If you still want to see how dictionary values
     are used, you will need to do :set +d or add the +d argument to
     your startup script.

  o  The default setting for the e toggle (warn about errors in
     literate scripts) has been changed to :set +e for closer
     compatibility with the literate script convention outline in the
     Haskell report, version 1.2.  In addition, the setting of the l
     toggle is now used only as a default if no particular type of
     script file is specified by the file extension of a give script.
     See Section 2.4 below for further details.

  o  The default setting for the f toggle (terminate evaluation on
     first error) has been changed to :set +f.  The old setting of
     :set -f is, in my opinion, better for debugging purposes, but
     does not give the behaviour that those using Haskell might
     expect.  This has caused a certain amount of confusion and was
     the motivation for this change.

  o  The following three command line options, provided in previous
     versions of Gofer, have now been removed:

         TOGGLES:
         a    Use any evidence, not nec. best
         E    Fail silently if evidence not found

         OTHER OPTIONS:
         xnum Set maximum depth for evidence search

     These options were only ever used for my own research and were
     (intentionally) undocumented, so it seemed sensible to remove them
     from the distributed system.  A quick patch to the source code and
     a recompilation is all that is necessary to reinstate these
     options; useful if somebody out there found out about these
     options and actually uses them (if you do, I'd love to know
     why!).


.ST 2.3  Commands
-------------
The full list of commands that can be used from within the Gofer
interpreter are summarized using the command :? as follows:

    ? :?
    LIST OF COMMANDS:  Any command may be abbreviated to :c where
    c is the first character in the full name.

    :load <filenames>   load scripts from specified files
    :load               clear all files except prelude
    :also <filenames>   read additional script files
    :reload             repeat last load command
    :project <filename> use project file
    :edit <filename>    edit file
    :edit               edit last file
    <expr>              evaluate expression
    :type <expr>        print type of expression
    :?                  display this list of commands
    :set <options>      set command line options
    :set                help on command line options
    :names [pat]        list names currently in scope
    :info <names>       describe named objects
    :find <name>        edit file containing definition of name
    :!command           shell escape
    :cd dir             change directory
    :quit               exit Gofer interpreter
    ?

Almost all of these commands are the same as in the previous release.
The only new features are listed in the following sections.


.ST 2.3.1  Shell escapes
--------------------
The shell escape command :! is used to enable you to run other programs
from within the Gofer interpreter.  For example, on a Unix system, you
can print a list of all the files in the current directory by typing:

    ? :!ls
    <list of all files in current directory gets printed here>
    ?

The same thing can be achieved on a PC running DOS by typing:

    ? :!dir
    <list of all files in current directory gets printed here>
    ?

This is the same as in previous releases of Gofer; the only difference
is that there is no longer any need to type a space between the :!
command and the shell command that follows it.  In fact, there is no
longer any need to type the leading colon either.  Thus the two commands
above could equally well have been entered as:

    !ls
    !dir

To start a new shell from within Gofer, you can use the command :! or the
abbreviated form ! -- in Unix and DOS you can return to the Gofer system
by entering the shell command `exit'.  This is likely to be different if
you use Gofer on other systems.


.ST 2.3.2  Information about named values
-------------------------------------
The :info command is a new feature which is useful for obtaining
information about the values currently loaded into a Gofer session.  It
can be used to display information about all kinds of different values
including:

  o  Datatypes:  The name of the datatype and a list of its associated
     constructor functions is printed:

         ? :info Request
         -- type constructor
         data Request

         -- constructors:
         ReadFile :: String -> Request
         WriteFile :: String -> String -> Request
         AppendFile :: String -> String -> Request
         ReadChan :: String -> Request
         AppendChan :: String -> String -> Request
         Echo :: Bool -> Request
         GetArgs :: Request
         GetProgName :: Request
         GetEnv :: String -> Request

         ?

  o  Type synonyms:  Prints the name and expansion of the synonym:

         ? :info Dialogue
         -- type constructor
         type Dialogue = [Response] -> [Request]

         ?

     If the type synonym is restricted (see Section 3.1) then the
     expansion is not included in the output:

         ? :info Stack      
         -- type constructor
         type Stack a = <restricted>

         ?

  o  Type classes: Lists the type class name, superclasses, member
     functions and instances:

         ? :info Eq
         -- type class
         class Eq a where
             (==) :: Eq a => a -> a -> Bool
             (/=) :: Eq a => a -> a -> Bool

         -- instances:
         instance Eq ()
         instance Eq Int
         instance Eq Float
         instance Eq Char
         instance Eq a => Eq [a]
         instance (Eq a, Eq b) => Eq (a,b)
         instance Eq Bool

         ?

     Note that the member functions listed for the class include the
     class predicate as part of the type; the output is not intended
     to be thought of as a syntactically valid class declaration.

     Overlapping instance declarations (see Section 3.2) are listed in
     increasing order of generality.

  o  Other values: for example, named functions and individual
     constructor and member functions:

         ? :info map : <=
         map :: (a -> b) -> [a] -> [b]

         (:) :: a -> [a] -> [a]   -- data constructor

         (<=) :: Ord a => a -> a -> Bool   -- class member

         ?

As the last example shows, the :info command can take several arguments
and prints out information about each in turn.  A warning message is
displayed if there are no known references to an argument:

    ? :info (:)
    Unknown reference `(:)'
    ?

This illustrates that the arguments are treated as textual names for
operators, not syntactic expressions (for example, identifiers). The
type of the (:) operator can be obtained by giving the command :info :
as above.  There is no provision for including wildcard characters of
any form in the arguments of :info commands.

If a particular argument can be interpreted as, for example, a
constructor function, or a type constructor depending on context, both
possibilities are displayed.  For example, loading a program containing
the definition:

    data Set a = Set [a]

We obtain:

    ? :info Set        
    -- type constructor
    data Set a

    -- constructors:
    Set :: [a] -> Set a

    Set :: [a] -> Set a   -- data constructor

    ?

If no arguments are supplied to :info, a list of all the script files
currently loaded into the interpreter will be displayed:

    ? :info

    Gofer session for:
    /usr/local/lib/Gofer/standard.prelude
    examples
    ?


.ST 2.4  Literate scripts
---------------------
Support for literate scripts -- files in which program lines begin with
a `>' character and all other lines are treated as comments -- was
provided in previous versions of Gofer.  The command line option
:set +l was used to force Gofer to treat each input file as a literate
script, while :set -l (the default) was used to treat each input file
as a standard script of definitions.

In practice, this turned out to be somewhat inconvenient, particularly
when loading combinations of files, some as literate scripts, some
without.  For example, quite a few people kept two versions of the
prelude, one as a literate script, one not, so that they wouldn't have
to fiddle with the settings or using the :set commands to load files.

Gofer version 2.28 now uses a more sophisticated scheme to determine
how an input script file should be treated, based on the use of file
extensions.  More specifically, any script file with a name ending in
one of the following suffixes:

    .hs     .has    .gs     .gof    .prelude

will always be loaded as a normal (i.e. non-literate) script file,
regardless of the setting of the l command line option.  In a similar
way, files with names ending in one of the following suffixes:

    .lgs    .lhs    .verb   .lit

will always be treated as literate scripts.  The command line option l
is only used for files with names not ending in one of the above
suffixes.

For example, the commands:

    :set -l
    :load prog1.gs prog2 prog3.lgs

will load prog1.gs and prog2 as non-literate scripts, and then load
prog3.lhs as a literate script.


.ST 2.5  Prelude files
------------------
The Gofer system comes with a standard prelude, and a small number of
alternative preludes.  These have always been there, but a lot of
people don't seem to have noticed these, so I thought I'd say a few
words about the different preludes included with Gofer: Remember that
you can always change the prelude you are using by setting the GOFER
environment variable or by modifying a startup script as described in
Section 2.1:

    standard.prelude    The standard Gofer prelude, using type classes
                        and providing the familiar range of operators
                        and functions.

    nofloat.prelude     A simplified version of the standard.prelude
                        which does not include any floating point
                        operators.  This is likely to be of most use
                        for those using Gofer on PCs where memory is
                        at a premium; compiling a version of the
                        interpreter (or compiler runtime library)
                        without floating point support can give an
                        important saving.

    simple.prelude      A prelude file based on the standard prelude
                        but without type classes.  Let me emphasize
                        that point: YOU CAN USE GOFER WITHOUT HAVING
                        TO LEARN ABOUT TYPE CLASSES :-)  Some people
                        seem to take to the use of type classes right
                        from the beginning.  For those that have
                        problems understanding the technical details
                        or even the motivation, the simple.prelude
                        can be used to get you familiar with the syntax
                        of the language and the basic principles.
                        Then you can move up to the standard.prelude
                        when you're ready.  The principle differences
                        can be described by listing the types of
                        commonly used operators in the simple.prelude:

                              (==) :: a -> a -> Bool
                              (<=) :: a -> a -> Bool
                              (<)  :: a -> a -> Bool
                              (>=) :: a -> a -> Bool
                              (>)  :: a -> a -> Bool
                              (/=) :: a -> a -> Bool
                              show :: a -> String
                              (+)  :: Int -> Int -> Int
                              (-)  :: Int -> Int -> Int
                              (*)  :: Int -> Int -> Int
                              (/)  :: Int -> Int -> Int

                        The resulting language is closer to the system
                        in Bird and Wadler (and can be made closer
                        still by editing the simple.prelude to use
                        zipwith instead of zipWith etc...).

    cc.prelude          An extended version of the standard.prelude
                        including support for a number of useful
                        constructor classes.  Most of the examples
                        and applications described in Section 4 are
                        based on this prelude.

    min.prelude         A minimal prelude file.  If you really want to
                        build a very small prelude for a particular
                        application, start with this and add the extra
                        things that you need.

As you can see, the standard extension for prelude files is .prelude
and any file ending with this suffix will be read as a non-literate
script (as described in Section 2.4).  Note that, even if you are using
a computer where the full name of a prelude file is not stored (for
example, on a DOS machine the standard.prelude file becomes
STANDARD.PRE) you should still specify the prelude file by its full
name to ensure that the Gofer system treats it correctly as a prelude
file.

You are also free to construct your own prelude files, typically by
modifying one of the supplied preludes described above.  Anyone who
created prelude files for use with previous releases of Gofer will need
to edit these files to ensure that they will work correctly.  Note in
particular that there is no longer any need to include definitions of
the I/O datatypes in programs.  Furthermore, the error function should
now be bound to the primitive "primError" rather than using the old
definition of error s | False = error s.


.co-------------------------------------------------------------------|
.ST 3. LANGUAGE DIFFERENCES

This section outlines a number of small differences and extensions to
the language used by Gofer.  These features are not included in the
definition of Haskell, so you shouldn't be thinking that programs
written using these features can ultimately be used with a full Haskell
system.  The use of constructor classes -- a more substantial change is
described in Section 4.

.ST 3.1  Restricted type synonyms
-----------------------------
Gofer 2.28 supports a form of restricted type synonym that can be used
to restrict the expansion of the synonym to a particular set of
functions.  Outside of the selected group of functions, the synonym
constructor behaves like a standard datatype.  More precisely, a
restricted type synonym definition is a top level declaration of the
form:

    type T a1 ... am = rhs in f1, ..., fn

where T is the name of the restricted type synonym constructor and rhs
is a type expression typically involving some of the (distinct) type
variables a1, ..., am.  The same kind of restrictions that apply to
normal type synonym declarations are also applied here.  The major
difference is that the expansion of the type synonym can only be used
within the binding group of one of the functions f1, ..., fn (all of
which must be defined by top-level definitions in the file containing
the restricted type synonym definition).  In the definition of any
other function, the type constructor T is treated as if it had been
introduced by a definition of the form:

    data T a1 ... am = ...

The original motivation for restricted type synonyms came from my work
with constructor classes as described in Section 4 and you will several
examples of this in the ccexamples.gs file in the demos/Ccexamples
directory of the standard distribution.  For a simpler example,
consider the following definition of a datatype of stacks in terms of
the standard list type:

    type Stack a = [a] in emptyStack, push, pop, top, isEmpty

The definitions for the five functions named here are as follows:

    emptyStack :: Stack a
    emptyStack  = []

    push       :: a -> Stack a -> Stack a
    push        = (:)

    pop        :: Stack a -> Stack a
    pop []      = error "pop: empty stack"
    pop (_:xs)  = xs

    top        :: Stack a -> a
    top []      = error "top: empty stack"
    top (x:_)   = x

    isEmpty    :: Stack a -> Bool
    isEmpty     = null

The type signatures here are particularly important.  For example,
since emptyStack is mentioned in the definition of the restricted type
synonym Stack, the definition of emptyStack is type correct.  The
declared type for emptyStack is Stack a which can be expanded to [a],
agreeing with the type for the empty list [].  However, in an expression
outside the binding group of these functions, the Stack a type is quite
distinct from the [a] type:

    ? emptyStack ++ [1]
    ERROR: Type error in application
    *** expression     : emptyStack ++ [1]
    *** term           : emptyStack
    *** type           : Stack a
    *** does not match : [Int]

    ?

The `binding group' of a value refers to the set of values whose
definitions are in the same mutually recursive group of bindings.  In
particular, this does not extend to the type class system so we can
define instances such as:

    instance Eq a => Eq (Stack a) where
        s1 == s2 | isEmpty s1 = isEmpty s2
                 | isEmpty s2 = isEmpty s1
                 | otherwise  = top s1 == top s2 && pop s1 == pop s2

As a convenience, Gofer allows the type signatures of functions
mentioned in the type synonym declaration to be specified within the
definition rather than in a different point in the script.  Thus the
example above could equally well have been written as:

    type Stack a = [a] in
        emptyStack :: Stack a,
        push       :: a -> Stack a -> Stack a,
        pop        :: Stack a -> Stack a,
        top        :: Stack a -> a,
        isEmpty    :: Stack a -> Bool

    emptyStack  = []

    push        = (:)

    pop []      = error "pop: empty stack"
    pop (_:xs)  = xs

    top []      = error "top: empty stack"
    top (x:_)   = x

    isEmpty     = null

However, the first form is necessary when you want to define two or
more restricted type synonyms simultaneously.  For example:

    type Pointer = Int in allocate, deref, assign
    type Heap a  = [a] in newHeap, allocate, deref, assign
    newHeap  :: Heap a
    allocate :: Heap a -> (Heap a, Pointer)
    deref    :: Heap a -> Pointer -> a
    assign   :: Heap a -> Pointer -> a -> Heap a
    etc ...

The use of restricted type synonyms doesn't quite provide proper
abstract data types.  For example, if you try:

    ? push 1 emptyStack
    [1]
    (5 reductions, 11 cells)
    ?

then the structure of the stack as a list of values is revealed by the
printing mechanism.  This happens because Gofer uses the show' function
to print out a value (in this case of type Stack Int) which looks inside
the structure of the object to see how it is represented.  This happens
to be most convenient for use in an interpreter as an aid to debugging.
For the purists (and the preservation of abstraction), Gofer could be
modified to apply the (overloaded) show function to printed values.
This would force the programmer to define the way in which stack values
are printed (distinct from lists) and preserve the abstraction.  Without
having set up this machinery, we get:

    ? show (push 1 emptyStack)
    ERROR: Cannot derive instance in expression
    *** Expression        : show (push 1 emptyStack)
    *** Required instance : Text (Stack Int)

    ?

The Gofer compiler described in Section 5 does not implement show' and
hence enforces the abstraction.


.ST 3.2  Overlapping instance declarations
--------------------------------------
This section describes a somewhat technical extension, aimed at those
who work with type classes.  Many readers may prefer to skip to the
next section at this point.

The definition of Haskell and previous versions of Gofer insist that no
two instance declarations for a given class may contain overlapping
predicates.  Thus the declarations:

    class CX a where c :: a -> Int

    instance CX (a,Int) where c (x,y) = y
    instance CX (Int,a) where c (x,y) = x

are not allowed because the two predicates overlap:

    ERROR "misctest" (line 346): Overlapping instances for class "CX"
    *** This instance   : CX (Int,a)
    *** Overlaps with   : CX (a,Int)
    *** Common instance : CX (Int,Int)

As the error message indicates, given an expression c (1,2) it is not
clear whether we should use the first or the second instance
declarations to evaluate this, with potentially different results, 2 or
1 respectively.

On the other hand, there are cases where this sort of thing might be
quite reasonable.  For example, the standard function show prints lists
of characters as strings, but any other kind of list is printed using
the [ ... ] notation with the items separated by commas:

    ? show "Hello"
    "Hello"
    ? show [True,False,True]
    [True,False,True]
    ? show [1..10]
    [1,2,3,4,5,6,7,8,9,10]
    ?

Haskell deals with this by an encoding using the showList function, but
a more obvious approach might be to define two instances:

    instance Text a => Text [a] where ... print using [ ... ] notation
    instance Text [Char] where ...        print as string

Other examples might include providing optimized versions of primitives
for particular frequently use operators, or providing a default
behaviour as in:

    class Eq a where (==) = error "no definition of equality specified"

Haskell requires the context of an overloaded function to be reduced to
a form where the only predicates that it contains are of the form C a.
This means that the inferred type of an object may be simplified before
the full type of that object is known.  For example, we might define a
function:

     f x = show [x,x]

The inferred type in Haskell is f :: Text a => a -> String and the
decision about which of the two instance declarations above should be
used has already been forced on us.  To see this, note that f 'a' would
evaluate to the string "['a', 'a']".  But if we allowed the second
instance declaration above to be used, show ['a', 'a'] would evaluate
to "aa".  This breaks a fundamental property of the language where we
expect to be able to replace one subexpression with another equal term
and obtain the same result.

In Gofer, the type system is a little different and the inferred type
is f :: Text [a] => a -> String.  The decision about which instance
declaration to use is postponed until the type assigned to 'a' is
known.  Thus both f 'a' and show ['a', 'a'] evaluate to "aa" without
any contradiction.

Although the type system in Gofer has always been able to support the
use of certain overlapping instance declarations, previous versions of
the system imposed stronger static restrictions which prohibited their
use.  Gofer 2.28 relaxes these restrictions by allowing a program to
contain overlapping instance declarations so long as:

  o  One of the instance predicates being declared is a substitution
     instance of the other.  Thus:

         instance Eq [Char] where ...    -- OK
         instance Eq a => Eq [a] where ...

     is permitted because the second predicate, Eq [a], is more general
     than the first, Eq [Char], which can be obtained by substituting
     Char for the type variable a.  However, the example at the
     beginning of this section:

         instance CX (a,Int) where ...   -- ILLEGAL
         instance CX (Int,a) where ...

     is not allowed since neither (a,Int) or (Int,a) is a substitution
     instance of the other (even though they have a common instance
     (Int,Int)).

  o  The two instances declared are not identical.  This rules out
     examples like:

         instance Eq Char where ...    -- ILLEGAL
         instance Eq Char where ...

The features described here are added principally for experimentation.
I have some particular applications that I want to try out (which is
why I actually implemented these ideas) but I would also be very
interested to hear from anyone else that makes use of this extension.


.ST 3.3  Parsing Haskell syntax
---------------------------
From correspondence that I have received, quite a few people use Gofer
to develop programs which, ultimately, will be compiled and executed
using a Haskell system.  Although the syntax of the two languages is
quite similar, it has been necessary to comment out module headers and
other constructs in Haskell programs before they could be used with
previous version of Gofer.

The new version of the Gofer system is now able to parse these
additional constructs (and will generate an error message if a syntax
error occurs).  However: NO ATTEMPT IS MADE TO INTERPRET OR USE THE
INFORMATION PROVIDED BY THESE ADDITIONAL CONSTRUCTS.  This feature is
provided purely for the convenience of those people using Gofer and
Haskell in the manner described above.  Gofer does not currently
support any notion of modules beyond the use of separate script files.

The following changes have been made:

  o  The identifiers:

         deriving     default      module      interface
         import       renaming     hiding      to

     are now reserved words in Gofer.  Any program that uses one of
     these as an identifier with an older version of Gofer will need
     to be modified to use a different name instead.

  o  Module headers and import declarations may be included in a Gofer
     program using the syntax set out in version 1.2 of the Haskell
     report.  Several modules may be included in a single file (but of
     course, Gofer makes no distinction between the sections of code
     appearing in different `modules').

  o  Datatype definitions may include deriving clauses such as:

         data Maybe a = Just a | Nothing deriving (Eq, Text)

     although no derived instances will actually be generated.
     If you need these facilities, you might consider writing out
     the instances of the type classes concerned yourself in a
     separate file which can be loaded when you run your program
     with Gofer, but which are omitted when you compile it with a
     proper Haskell system.

  o  Programs may include default declarations, although, once again,
     these are ignored; for example, there is no restriction on the
     forms of type that can be included in a default declaration, nor
     will an error occur if a single module includes multiple default
     declarations.


.ST 3.4  Local definitions in comprehensions
----------------------------------------
We all make mistakes.  The syntax for Gofer currently permits a local
definition to appear in a list comprehension (and indeed, in the monad
comprehensions described in the next section):

    [ (x,y) | x <- xs, y = f x, p y ]

This example is implemented by translating it to something equivalent
to:

    map h xs where h []     = []
                   h (x:xs) = let y = f x
                              in  if p y then (x,y) : h xs
                                         else h xs

It is cumbersome to rewrite this using list comprehensions without
local definitions:

    concat [ let y = f x in [ (x,y) | p y ] | x <- xs ]

so we might resort to the `hack' of writing:

    [ y | x <- xs, y <- [f x], p y ]

which works (but doesn't extend to recursive bindings, and is really an
inappropriate use for a list; a list is used to represent a sequence of
zero or more objects, so using a list when you know that there is
always going to be exactly one element seems unnecessary).  So, to
summarize, I still think that local definitions can be useful in
comprehensions.

So where is the mistake I mentioned?  The problem is with the SYNTAX.
First, it is rather easy to confuse the comprehension above with the
comprehension:

    [ (x,y) | x <- xs, y == f x, p y ],

leading to errors which are hard to detect.  The second is that the
syntax is too restrictive; you can only give relatively simple local
declarations -- mutually recursive definitions and function bindings
are not permitted.

Gofer 2.28 now supports a new syntax for local definitions in
comprehensions.  The old syntax is still supported, for compatibility
with previous releases, but will be deleted in the next public release
(assuming I remember).  Local declarations can now be included in a
comprehension using a qualifier of the form let { decls }.  So the
comprehension at the beginning of this section can also be written:

    [ (x,y) | x <- xs, let {y = f x}, p y ]

Note that the braces cannot usually be omitted in Gofer due to an
undocumented extension to the syntax of Gofer function declarations.
The braces would not be needed if this syntax were added to a standard
Haskell system.

This extension means that it is now possible to write comprehensions
such as:

    [ (x,y,z) | x <- xs, let { y   = f x z;
                               z   = g x y;
                               f n = h n [] }, p x y z ]
     
Once again, this is still an experimental feature.  I suspect it will
be of most use to anyone making substantial use of monad comprehensions
as described in the next section.


.co-------------------------------------------------------------------|
.ST 4. CONSTRUCTOR CLASSES

[This is a long section; if you are not interested in experimenting
with Gofer's system of constructor classes, you can skip straight ahead
to the next section without missing anything.  Of course, if you don't
know what a constructor class is, you might want to read at least some
of this section before you can make that decision.]

One of the biggest changes in Gofer version 2.28 is the provision of
support for constructor classes.  This section provides an overview of
constructor classes which should hopefully, in conjunction with the
example supplied with the full distribution, be enough to get you
started.  More technical details about constructor classes can be
obtained by contacting me.

Some of the following introduction here (particularly sections 4.1 and
4.2) may seem somewhat familiar to those of you have already read one
of the papers that I have written on the subject although I have added
some more information about the Gofer implementation.

Others may find that this section of the documentation seems rather
technical; try not to be put off at first sight.  Looking through the
examples and the documentation, you may find it is easier to understand
than you expect!

A final comment before starting: there is, as yet, no strong consensus
on the names and syntax that would be best for monad operations,
comprehensions etc.  If you have any opinions, or proposals which
differ from what you see here, please let me know ... I'd be very
interested to hear other people's opinions on this.


.ST 4.1  An overloaded map function
-------------------------------
Many functional programs use the map function to apply a function to
each of the elements in a given list.  The type and definition of this
function as given in the Gofer standard prelude are as follows:

    map          ::  (a -> b) -> ([a] -> [b])
    map f []      =  []
    map f (x:xs)  =  f x : map f xs

It is well known that the map function satisfies the familiar laws:

    map id         = id
    map f . map g  =  map (f . g)

A category theorist will recognize these observations as indicating
that there is a functor from types to types whose object part maps any
given type a to the list type [a] and whose arrow part maps each
function f::a -> b to the function map f :: [a] -> [b].  A functional
programmer will recognize that similar constructions are also used with
a wide range of other data types, as illustrated by the following
examples:

    data Tree a  =  Leaf a  |  Tree a :^: Tree a

    mapTree            :: (a -> b) -> (Tree a -> Tree b)
    mapTree f (Leaf x)  = Leaf (f x)
    mapTree f (l :^: r) = mapTree f l :^: mapTree f r

    data Maybe a =  Just a  |  Nothing

    mapMaybe           :: (a -> b) -> (Maybe a -> Maybe b)
    mapMaybe f (Just x) = Just (f x)
    mapMaybe f Nothing  = Nothing

Each of these functions has a similar type to that of the original map
and also satisfies the functor laws given above.  With this in mind, it
seems a shame that we have to use different names for each of these
variants.

A more attractive solution would allow the use of a single name map,
relying on the types of the objects involved to determine which
particular version of the map function is required in a given
situation.  For example, it is clear that map (1+) [1,2,3] should be
a list, calculated using the original map function on lists, while
map (1+) (Just 1) should evaluate to Just 2 using mapMaybe.

Unfortunately, in a language using standard Hindley/Milner type
inference, there is no way to assign a type to the map function that
would allow it to be used in this way.  Furthermore, even if typing
were not an issue, use of the map function would be rather limited
unless some additional mechanism was provided to allow the definition
to be extended to include new datatypes perhaps distributed across a
number of distinct program files.


.ST 4.1.1  An attempt to define map using type classes
--------------------------------------------------
The ability to use a single function symbol with an interpretation that
depends on the type of its arguments is commonly known as overloading.
In Gofer, overloading is implemented using type classes -- which can be
thought of as sets of types.  For example, the Eq class defined by:

    class Eq a where
        (==), (/=) :: a -> a -> Bool

(together with an appropriate set of instance declarations) is used to
describe the set of types whose elements can be compared for equality.
The standard prelude for Gofer includes integers, floating point
numbers, characters, booleans, lists (in which the type of the members
is also in Eq) and so forth.  There is no need for all the definitions
of equality to be combined in a single script file; new definitions of
equality are typically included each time a new datatype is defined.

Functions such as nub, defined in the standard prelude as:

    nub       :: Eq a => [a] -> [a]   -- remove duplicates from list
    nub []     = []
    nub (x:xs) = x : nub (filter (x/=) xs)

can be used with any choice of type for the type variable a so long as
it is an instance of Eq.  Only a single definition of the nub function
is required.

Unfortunately, the system of type classes is not sufficiently powerful
to give a satisfactory treatment for the map function; to do so would
require a class Map and a type expression m(t) involving the type
variable t such that S = { m(t) | t is a member of Map } includes (at
least) the types:

    { (a -> b) -> ([a] -> [b]),
      (a -> b) -> (Tree a -> Tree b),
      (a -> b) -> (Maybe a -> Maybe b), ....
                                    | a and b arbitrary types }

.cc 5
The only possibility is to take m(t) = t and choose Map as the set of
types S for which the map function is required:

    class Map t where map :: t

    instance Map ((a -> b) -> ([a] -> [b])) where ...
    instance Map ((a -> b) -> (Tree a -> Tree b)) where ...
    instance Map ((a -> b) -> (Maybe a -> Maybe b)) where ...

This syntax is permitted in Gofer (but not in Haskell) but it does not
give a sufficiently accurate characterization of the type of map to be
of much use.  For example, the principal type of \i j -> map j . map i
is:

    (Map (a -> c -> e), Map (b -> e -> d)) => a -> b -> c -> d

(a and b are the types of i and j respectively).  This is complicated
and does not enforce the condition that i and j have function types.
Furthermore, the type is ambiguous (the type variable e does not appear
to the right of the => symbol or in the assumptions).  Under these
conditions, we cannot guarantee a well-defined semantics for this
expression.  Other attempts to define the map function, for example
using multiple parameter type classes, have also failed for essentially
the same reasons.


.ST 4.1.2  A solution using constructor classes
-------------------------------------------
A much better approach is to notice that each of the types for which
the map function is required is of the form:

    (a -> b) -> (f a -> f b).

The variables a and b here represent arbitrary types while f ranges
over the set of type constructors for which a suitable map function has
been defined.  In particular, we would expect to include the list
constructor (which we write as [] in Gofer), Tree and Maybe as elements
of this set.  Motivated by our earlier comments we will call this set
Functor.  With only a small extension to the Gofer syntax for type
classes this can be described by:

    class Functor f where
        map :: (a -> b) -> (f a -> f b)

    instance Functor [] where
        map f []        = []
        map f (x:xs)    = f x : map f xs

    instance Functor Tree where
        map f (Leaf a)  = Leaf (f a)
        map f (l :^: r) = map f l :^: map f r

    instance Functor Maybe where
        map f (Just x) = Just (f x)
        map f Nothing  = Nothing

.cc 5
Functor is our first example of a constructor class.  The following
extract illustrates how the definitions for Functor work in practice:

    ? map (1+) [1,2,3]
    [2, 3, 4]
    (15 reductions, 44 cells)
    ? map (1+) (Leaf 1 :^: Leaf 2)
    Leaf 2 :^: Leaf 3
    (10 reductions, 46 cells)
    ? map (1+) (Just 1)
    Just 2
    (4 reductions, 17 cells)
    ?

Furthermore, by specifying the type of map function more precisely,
we avoid the ambiguity problems mentioned above.  For example, the
principal type of \i j -> map j . map i is simply:

    Functor f => (a -> b) -> (b -> c) -> f a -> f c

which is not ambiguous, and makes the types of i and j as (a -> b)
and (b -> c) respectively.

[You can try these examples yourself using the Gofer system.  The first
thing you need to do is start Gofer using the file cc.prelude instead
of the usual Gofer standard.prelude.  The cc.prelude includes the
definition of the functor class and the instance for Functor [].  The
remaining two instance declarations are included (along with lots of
other examples) in the file ccexamples.gs in the demos/Ccexamples
subdirectory of the standard distribution.]


.ST 4.1.3  The kind system
----------------------
Each instance of Functor can be thought of as a function from types to
types.  It would be nonsense to allow the type Int of integers to be an
instance of Functor, since the type (a -> b) ->(Int a -> Int b) is
obviously not well-formed.  To avoid unwanted cases like this, we have
to ensure that all of the elements in any given class are of the same
kind.

To do this, we formalize the notion of kind, writing * for the kind of
all types and k1 -> k2 for the kind of a constructor which takes
something of kind k1 and returns something of kind k2.  This notion
comes is motivated by some theoretical work by Henk Barendregt on the
subject of `Generalized type systems'; Do not confuse this with the use
of the symbol * in a certain well-known functional language where it
represents a type variable.  These things are completely different!

Rather than thinking only of types we work with constructors which
include types as a special case.  Constructors take the form:

    Constructor  ::=  ConstructorConstant
                  |   Constructor1 Constructor2
                  |   variable

This corresponds very closely to the way that most type expressions
are already written in Gofer.  For example, Tree a is an application
of the constructor constant Tree to the variable a.  Gofer has some
special syntax for tuple, list and function types.  The corresponding
constructors can also be written directly in Gofer.  For example:

    a -> b   =  (->) a b
    [a]      =  [] a
    (a,b)    =  (,) a b
    (a,b,c)  =  (,,) a b c
    etc ...

Each constructor constant has a corresponding kind.  For example:

    Int, Float, ()    ::  *
    [], Tree, Maybe   ::  * -> *
    (->), (,)         ::  * -> * -> *
    (,,)              ::  * -> * -> * -> *

Applying one constructor C :: k1 -> k2 to a construct C' :: k1 gives
a constructor expression C C' with kind k2.  Notice that this is just
the same sort of thing you would expect from applying a function of
type a -> b to an value of type b; kinds really are very much like
`types for constructors'.

Instead of checking that type expressions contain the correct number of
arguments for each type constructor, we need to check that any type
expression has kind *.  In a similar way, all of the elements of a
constructor class must have the same kind; for example, a constructor
class constraint of the form Functor f is only valid if f is a
constructor expression of kind * -> *.  Note also that our system
includes Gofer/Haskell type classes as a special case; a type class is
simply a constructor class for which each instance has kind *.  Multiple
parameter classes can also be dealt with in the same way, using a tuple
of kinds (k1,...,kn) to indicate the kind of constructors required for
each argument.

The language of constructors is essentially a system of combinators
without any reduction rules.  As such, standard techniques can be
used to infer the kinds of constructor variables, constructor constants
introduced by new datatype definitions and the kind of the elements
held in any particular constructor class.  The important point is that
there is no need -- and indeed, in our current implementation, no
opportunity -- for the programmer to supply kind information
explicitly.  We regard this as a significant advantage since it means
that the programmer can avoid much of the complexity that might
otherwise result from the need to annotate type expressions with
kinds.


.ST 4.2  Monads as an application of constructor classes
----------------------------------------------------
Motivated by the work of Moggi and Spivey, Wadler has proposed a style
of functional programming based on the use of monads.  While the theory
of monads had already been widely studied in the context of abstract
category theory, Wadler introduced the idea that monads could be used
as a practical method for modeling so-called `impure' features in a
purely functional programming language.

The examples in this and following sections illustrate that the use of
constructor classes can be particularly convenient for programming in
this style.  You will also find a lot more examples prepared for use
with Gofer in the file ccexamples in the demos/Ccexamples subdirectory
of the standard distribution.


.ST 4.2.1  A framework for programming with monads
----------------------------------------------
The basic motivation for the use of monads is the need to distinguish
between computations and the values that they produce.  If m is a monad
then an object of type (m a) represents a computation which is expected
to produce a value of type a.  These types reflect the fact that the
use of particular programming language features in a given calculation
is a property of the computation itself and not of the result that it
produces.

Taking the approach outlined by Wadler in his paper `The Essence of
Functional Programming' (POPL '92), we introduce a constructor class of
monads using the definition:

    class Functor m => Monad m where
        result    :: a -> m a
        join      :: m (m a) -> m a
        bind      :: m a -> (a -> m b) -> m b

        join x     = bind x id
        x `bind` f = join (map f x)

The expression Functor m => Monad m defines Monad as a subclass of
Functor ensuring that, for any given monad, there will also be a
corresponding instance of the overloaded map function.  The use of a
hierarchy of classes enables us to capture the fact that not every
instance of Functor can be treated as an instance of Monad in any
natural way.

[If you are familiar with either my previous papers or Wadler's
writings on the use of monads, you might notice that the declaration
above uses the name `result' in place of `return' or `unit' that have
been previously used for the same thing.  The latter two choices have
been used elsewhere for rather different purposes, and there is
currently no clear picture of which names should be used.  The
identifier `result' is the latest in a long line of attempts to find a
name which both conveys the appropriate meaning and is not already in
use for other applications.]

By including default definitions for bind and join we only need to give
a definition for one of these (in addition to a definition for result)
to completely define an instance of Monad.  This is often quite
convenient.  On the other hand, it would be an error to omit
definitions for both operators since the default definitions are
clearly circular.  We should also mention that the member functions in
an instance of Monad are expected to satisfy a number of laws which are
not reflected in the class definition above.

The following declaration defines the standard monad structure for the
list constructor [] which can be used to describe computations
producing multiple results, corresponding to a simple form of
non-determinism:

    instance Monad [] where
        result x        = [x]
        []     `bind` f = []
        (x:xs) `bind` f = f x ++ (xs `bind` f)

As a second example, the monad structure for the Maybe datatype, which
might be used to describe computations which fail to produce any value
at all if an error condition occurs, can be described by:

    instance Monad Maybe where
        result x         = Just x
        Just x  `bind` f = f x
        Nothing `bind` f = Nothing

Another interesting use of monads is to model programs that make use of
an internal state.  Computations of this kind can be represented by
functions of type s-> (a,s) (often referred to as state transformers)
mapping an initial state to a pair containing the result and final
state.  In order to get this into the appropriate form for the Gofer
system of constructor classes, we introduce a new datatype:

    data State s a = ST (s -> (a,s))

The functor and monad structures for state transformers are as follows:

    instance Functor (State s) where
        map f (ST st) = ST (\s -> let (x,s') = st s in (f x, s'))

    instance Monad (State s) where
        result x      = ST (\s -> (x,s))
        ST m `bind` f = ST (\s -> let (x,s') = m s
                                      ST f'  = f x
                                  in  f' s')

Notice that the State constructor has kind * -> * -> * and that the
declarations above define State s as a monad and functor for any state
type s (and hence State s has kind * -> * as required for an instance
of these classes).  There is no need to assume a fixed state type.

From a user's point of view, the most interesting properties of a monad
are described, not by the result, bind and join operators, but by the
additional operations that it supports.  The following examples are
often useful when working with state monads.  The first can be used to
`run' a program given an initial state and discarding the final state,
while the second might be used to implement an integer counter in a
State Int monad:

    startingWith          :: State s a -> s -> a
    ST m `startingWith` s0 = result where (result,_) = m s0

    incr :: State Int Int
    incr  = ST (\s -> (s,s+1))

To illustrate the use of state monads, consider the task of labeling
each of the nodes in a binary tree with distinct integer values.  One
simple definition is:

    label     :: Tree a -> Tree (a,Int)
    label tree = fst (lab tree 0)
     where lab (Leaf n)  c  =  (Leaf (n,c), c+1)
           lab (l :^: r) c  =  (l' :^: r', c'')
                               where (l',c')  = lab l c
                                     (r',c'') = lab r c'

This uses an explicit counter (represented by the second parameter to
lab) and great care must be taken to ensure that the appropriate
counter value is used in each part of the program; simple errors, such
as writing c in place of c' in the last line, are easily made but can
be hard to detect.

An alternative definition, using a state monad and following the
layout suggested in Wadler's POPL paper, can be written as follows:

    label     :: Tree a -> Tree (a,Int)
    label tree = lab tree `startingWith` 0
     where lab (Leaf n)  = incr                  `bind` \c ->
                           result (Leaf (n,c))
           lab (l :^: r) = lab l                 `bind` \l' ->
                           lab r                 `bind` \r' ->
                           result (l' :^: r')

While this program is perhaps a little longer than the previous
version, the use of monad operations ensures that the correct counter
value is passed from one part of the program to the next.  There is no
need to mention explicitly that a state monad is required: The use of
startingWith and the initial value 0 (or indeed, the use of incr on its
own) are sufficient to determine the monad State Int needed for the
bind and result operators.  It is not necessary to distinguish between
different versions of the monad operators bind, result and join or to
rely on explicit type declarations.


.ST 4.2.2  Monad comprehensions
---------------------------
Several functional programming languages provide support for list
comprehensions, enabling some common forms of computation with lists to
be written in a concise form resembling the standard syntax for set
comprehensions in mathematics.  In his paper `Comprehending Monads'
(ACM Lisp and Functional Programming, 1990), Wadler made the
observation that the comprehension notation can be generalized to
arbitrary monads, of which the list constructor is just one special
case.

In Wadler's notation, a monad comprehension is written using the syntax
of a list comprehension but with a superscript to indicate the monad in
which the comprehension is to be interpreted.  This is a little awkward
and makes the notation less powerful than might be hoped since each
comprehension is restricted to a particular monad.  Using the
overloaded operators described in the previous section, Gofer provides
a more flexible form of monad comprehension which relies on overloading
rather than superscripts.  At the time of writing, this is the only
concrete implementation of monad comprehensions known to us.

In our system, a monad comprehension is an expression of the form
[e | qs ] where e is an expression and gs is a list of generators of
the form p <- exp.  As a special case, if gs is empty then the
comprehension [ e | qs ] is written as [ e ].  The implementation of
monad comprehensions is based on the following translation of the
comprehension notation in terms of the result and bind operators
described in the previous section:

    [ e ]                = result e
    [ e | p <- exp, qs ] = exp `bind` \p -> [ e | qs ]

In this notation, the label function from the previous section can
be rewritten as:

    label     :: Tree a -> Tree (a,Int)
    label tree = lab tree `startingWith` 0
     where lab (Leaf n)  = [ Leaf (n,c) | c <- incr ]
           lab (l :^: r) = [  l :^: r   | l <- lab l, r <- lab r ]

Applying the translation rules for monad comprehensions to this
definition yields the previous definition in terms of result and bind.
The principal advantage of the comprehension syntax is that it is often
more concise and, in the author's opinion, sometimes more attractive.


.ST 4.2.3  Monads with a zero
-------------------------
Assuming that you are familiar with Gofer's list comprehensions, you
will know that it is also possible to include boolean guards in
addition to generators in the definition of a list comprehension.  Once
again, Wadler showed that this was also possible in the more general
setting of monad comprehensions, so long as we restrict such
comprehensions to monads that include a special element zero satisfying
a small number of laws.  This can be dealt with in our framework by
defining a subclass of Monad:

    class Monad m => Monad0 m where
        zero   :: m a

For example, the List monad has the empty list as a zero element:

    instance Monad0 [] where zero = []

Note that not there are also some monads which do not have a zero
element and hence cannot be defined as instances of Monad0.  The
State s monads described in Section 4.2.1 are a simple example of
this.

Working in a monad with a zero, a comprehension involving a boolean
guard can be implemented using the translation:

    [ e | guard, qs ]  =  if guard then [ e | qs ] else zero

Notice that, as far as the type system is concerned, the use of
zero in the translation of a comprehension involving a guard automatically
captures the restriction to monads with a zero:

    ? :t \x p -> [ x | p x ]
    \x p -> [ x | p x ] :: Monad0 b => a -> (a -> Bool) -> b a
    ?

The inclusion of a zero element also allows a slightly different
translation for generators in comprehensions:

    [ e | p <- exp, qs ]  =  exp `bind` f
                             where  f p  =  [ e | qs ]
                                    f _  =  zero

This corresponds directly to the semantics of standard Gofer list
comprehensions, but only differs from the semantics of the translation
given in the previous section when p is an irrefutable pattern; i.e.
when p is a pattern which may not match the value (or values) generated
by exp.  You can see the difference by trying the following example
in Gofer:

    ? [ x | [x] <- [[1],[],[2]]]
    [1, 2]
    (9 reductions, 31 cells)
    ? map (\[x] -> x) [[1],[],[2]]
    [1, 
    Program error: {v157 []}
    (8 reductions, 66 cells)

    ?

In order to retain compatibility with the standard list comprehension
notation, Gofer always uses the second translation above for generators
if the pattern p is refutable.  This may sometimes give inferred types
which are more restrictive than you expect.  For example, tuples are
not irrefutable patterns in Gofer or Haskell, and so the function:

    ? :t \xs -> [ x | (x,y) <- xs ]
    \xs -> [ x | (x,y)<-xs ] :: Monad0 a => a (b,c) -> a b
    ?

is restricted to monads with a zero because the expanded translation
above is used.  You can always avoid this problem by using the lazy
pattern construct (i.e. the tilde operator, ~p) as in:

    ? :t \xs -> [ x | ~(x,y) <- xs ]
    \xs -> [ x | ~(x,y)<-xs ] :: Monad a => a (b,c) -> a b
    ?

[At one stage, I was using a different form of brackets to represent
monad comprehensions, implemented using the original translation to
avoid changing the semantics of list comprehensions.  But I finally
decided that it would be better to use standard comprehension notation
with lazy pattern annotations where necessary since this is less
cumbersome than writing \xs -> [| x | (x,y) <- xs |] in place of the
comprehension above.  Please let me know what you think!]


.ST 4.2.4  Generic operations on monads
-----------------------------------
The combination of polymorphism and constructor classes in our system
makes it possible to define generic functions which can be used on a
wide range of different monads.  A simple example of this is the
`Kleisli composition' for an arbitrary monad, similar to the usual
composition of functions except that it also takes care of `side
effects'.  The general definition is as follows:

   (@@)   :: Monad m => (a -> m b) -> (c -> m a) -> (c -> m b)
   f @@ g  = join . map f . g

For example, in a monad of the form State s, the expression f @@ g
denotes a state transformer in which the final state of the computation
associated with g is used as the initial state for the computation
associated with f.  More precisely, for this particular kind of monad,
the general definition given above is equivalent to:

    (@@)  :: (b -> State s c) -> (a -> State s b) -> (a -> State s c)
    f @@ g = \a -> STM (\s0 -> let ST g'  = g a
                                   (b,s1) = g' s0
                                   ST f'  = f b
                                   (c,s2) = f' s1
                               in  (c,s2))

The biggest advantage of the generic definition is that there is no
need to construct new definitions of (@@) for every different monad.
On the other hand, if specific definitions were required for some
instances, perhaps in the interests of efficiency, we could simply
include (@@) as a member function of Monad and use the generic
definition as a default implementation.

Generic operations can also be defined using the comprehension
notation:

    mapl             :: Monad m => (a -> m b) -> ([a] -> m [b])
    mapl f []         = [ [] ]
    mapl f (x:xs)     = [ y:ys | y <- f x, ys <- mapl f xs ]

This is the same as mapping a function down the elements of a list
using the normal map function except that, in the presence of side
effects, the order in which the applications are carried out is
important.  For mapl, we start on the left (i.e. the front of the list)
and work towards the right.  There is a corresponding dual which works
in the reverse direction:

    mapr             :: Monad m => (a -> m b) -> ([a] -> m [b])
    mapr f []         = [ [] ]
    mapr f (x:xs)     = [ y:ys | ys <- mapr f xs, y <- f x ]

These general functions have applications in several kinds of monad
with examples involving state and output.

The comprehension notation can also be used to define a generalization
of Haskell's filter function which works in an arbitrary monad with a
zero:

    filter           :: Monad0 m => (a -> Bool) -> m a -> m a
    filter p xs       = [ x | x<-xs, p x ]

There are many other general purpose functions that can be defined
in the current framework and used in arbitrary monads.  To give you
some further examples, here are generalized versions of the foldl and
foldr functions which work in an arbitrary monad:

    mfoldl           :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
    mfoldl f a []     = result a
    mfoldl f a (x:xs) = f a x `bind` (\fax -> mfoldl f fax xs)

    mfoldr           :: Monad m => (a -> b -> m b) -> b -> [a] -> m b
    mfoldr f a []     = result a
    mfoldr f a (x:xs) = mfoldr f a xs `bind` (\y -> f x y)

[Generalizing these definitions (and those of mapl, mapr) to work with
a second arbitrary monad (in place of the list monad) is left as an
entertaining exercise for the reader :-)]

As a final example, here is a definition of a `while' loop for an
arbitrary monad:

    while    :: Monad m => m Bool -> m b -> m ()
    while c s = c  `bind` \b ->
                if b then s         `bind` \x ->
                          while c s
                     else result ()


.ST 4.2.5  A family of state monads
-------------------------------
We have already described the use of monads to model programs with
state using the State datatype in Section 4.2.1.  The essential
property of any such monad is the ability to update the state and we
might therefore consider a more general class of state monads given by:

    class Monad (m s) => StateMonad m s where
        update :: (s -> s) -> m s s
        set    :: s -> m s s
        fetch  :: m s s
        set new = update (\old -> new)
        fetch   = update id

An expression of the form update f denotes the computation which
updates the state using f and result the old state as its result.  For
example, the incr function described above can be defined as:

    incr :: StateMonad m Int => m Int Int
    incr  = update (1+)

in this more general setting.  The class declaration above also
includes set and fetch functions which set the state to a particular
value or return its value.  These are easily defined in terms of the
update function as illustrated by the default definitions.

The StateMonad class has two parameters; the first should be a
constructor of kind (* -> * -> *) while the second gives the state
type (of kind *); both are needed to specify the type of update.
The implementation of update for a monad of the form State s is
straightforward and provides us with our first instance of the
StateMonad class:

    instance StateMonad State s where
        update f = ST (\s -> (s, f s))

A rather more interesting family of state monads can be described using
the following datatype definition:

    data STM m s a = STM (s -> m (a,s)) -- a more sophisticated example,
                                        -- where the state monad is
                                        -- parameterized by a second,
                                        -- arbitrary monad.

Note that the first parameter to StateM has kind (* -> *), a
significant extension from Haskell (and previous versions of Gofer)
where all of the arguments to a type constructor must be types.  This
is another benefit of the kind system.

The functor and monad structure of a StateM m s constructor are given
by:

    instance Monad m => Functor (STM m s) where
        map f (STM xs) = STM (\s -> [ (f x, s') | ~(x,s') <- xs s ])

    instance Monad m => Monad (STM m s) where
        result x        = STM (\s -> result (x,s))
        STM xs `bind` f = STM (\s -> xs s `bind` (\(x,s') ->
                                     let STM f' = f x
                                     in  f' s'))

Note the condition that m is an instance of Monad in each of these
definitions.  If we hadn't used the lazy pattern construct ~(x,s') in
the instance of Functor, it would have been necessary to strengthen
this further to instances of Monad0 -- i.e. monads with a zero.

The definition of StateM m as an instance of StateMonad is also
straightforward:

    instance StateMonad (STM m) s where
        update f = STM (\s -> result (s, f s))

The following two functions are also useful for work with STM m s
monads.  The first, protect, allows an arbitrary computation to be
embedded in a state based computation without access to the state.
The second, execute, is similar to the startingWith function in
Section 4.2.1, running a state based computation with a given initial
state and returning a computation as the result.

protect          :: Monad m => m a -> STM m s a
protect m         = STM (\s -> [ (x,s) | x<-m ])

execute          :: Monad m => s -> STM m s a -> m a
execute s (STM f) = [ x | ~(x,s') <- f s ]

Support for monads like StateM m s seems to be an important step
towards solving the problem of constructing monads by combining
features from simpler monads, in this case combining the use of state
with the features of an arbitrary monad m.  I hope that the system of
constructor classes in Gofer will be a useful tool for people working
in this area.


.ST 4.2.6  Monads and substitution
------------------------------
The previous sections have concentrated on the use of monads to
describe computations.  Monads also have a useful interpretation as a
general approach to substitution.  This in turn provides another
application for constructor classes.

Taking a fairly general approach, a substitution can be considered as a
function s::v-> t w where the types v and w
represent sets of variables and the type t a represents a set
of terms, typically involving elements of type a.  If t is
a monad and x::t v, then x `bind` s gives the result of
applying the substitution s to the term x by replacing
each occurrence of a variable v in x with the corresponding
term s v in the result.  For example:

    instance Monad Tree where
        result             = Leaf
        Leaf x    `bind` f = f x
        (l :^: r) `bind` f = (l `bind` f) :^: (r `bind` f)

With this interpretation in mind, the Kleisli composition (@@) in
Section 4.2.4 is just the standard way of composing substitutions,
while the result function corresponds to a null substitution.  The fact
that (@@) is associative with result as both a left and right identity
follows from the standard algebraic properties of a monad.


.ST 4.3  Constructor classes in Gofer
---------------------------------
The previous two sections should have given you some ideas about the
motivation and use for constructor classes.  It remains to say a few
words about the way that constructor classes fit into the general Gofer
framework.  In practice, this means giving a more detailed description
of the way that the kind system works.

.ST 4.3.1  Kind errors and the k command line option
------------------------------------------------
As has already been mentioned, Gofer 2.28 uses kind information to
check that type expressions are well-formed rather than simply checking
that each type constructor is applied to an appropriate number of
arguments.  For example, having defined a tree datatype:

    data Tree a = Leaf a | Tree a :^: Tree a

the following definition will be rejected as an error:

    type Example  =  Tree Int Bool

as follows:

    ERROR "file" (line 42): Illegal type "Tree Int Bool" in
                            constructor application

The problem here is that the Tree constructor has kind * -> * so that
it expects to take one argument (a type) and deliver a type as the
result.  On the other hand, in the definition of Example, the Tree
constructor is treated as having (at least) two arguments; i.e. as
having a kind of the form (* -> * -> k) for some kind k.  Rather than
confuse a user who is not familiar with the use of kinds, Gofer
normally just prints an error message like the one above for examples
like this.

If you would like Gofer to give a more detailed description of the
problem, you can use the :set +k command line option as follows:

    ? :set +k
    ? :r
    Reading script file "file":
       
    ERROR "file" (line 42): Kind error in constructor application
    *** expression     : Tree Int Bool
    *** constructor    : Tree
    *** kind           : * -> *
    *** does not match : * -> a -> b

    ? 

When the k command line option has been selected, the :info command
described in Section 2.3.2 also includes kind information about the
kinds of type constructors defined in a program.  For example, given
the definition of Tree above and the datatypes:

    data STM m s x = STM (s -> m (s, x))
    data Queue a   = Empty | a :< Queue a | Queue a :> a

The :info command gives the following kinds (editing the output to
remove details about constructor functions for each datatype):

    ? :info Tree STM Queue
    -- type constructor with kind * -> *
    data Tree a

    -- type constructor with kind (* -> *) -> * -> * -> *
    data STM a b c

    -- type constructor with kind * -> *
    data Queue a

    ?

In addition to calculating a kind of each type constructor introduced
in a datatype declaration, Gofer also determines a kind for each
constructor defined by means of a type synonym.  For example, the
following definitions:

    type Subst m v = v -> m v
    type Compose f g x = f (g x)
    type Pointer a = Int
    type Apply f x = f x
    type Fusion f g x = f x (g x)
    type Const x y   = x

are treated as having kinds:

    ? :info Subst Compose Pointer Apply Fusion Const
    -- type constructor with kind (* -> *) -> * -> *
    type Subst a b = b -> a b

    -- type constructor with kind (* -> *) -> (* -> *) -> * -> *
    type Compose a b c = a (b c)

    -- type constructor with kind * -> *
    type Pointer a = Int

    -- type constructor with kind (* -> *) -> * -> *
    type Apply a b = a b

    -- type constructor with kind (* -> * -> *) -> (* -> *) -> * -> *
    type Fusion a b c = a c (b c)

    -- type constructor with kind * -> * -> *
    type Const a b = a

    ?

Note however type synonyms are only used as abbreviations for other
type expressions.  It is not permitted to use a type synonym
constructor in a type expression without giving the correct number of
arguments.

    ? undefined :: Const Int

    ERROR: Wrong number of arguments for type synonym "Const"
    ?

Assuming that you are familiar with polymorphic functions in Gofer, you
might be wondering why some of the kinds given for the type synonyms
above are not also polymorphic in some sense.  After all, the standard
prelude function const, is defined by

    const x y = x

with type a -> b -> a, which looks very similar to the definition of
the Const type synonym above, except that the kinds of the two
arguments have both been fixed as *.  In fact, the right hand side of
a type synonym declaration is always required to have kind *, so this
would mean that the most general kind that could be assigned to the
Const constructor would be * -> a -> *.

Gofer does not currently support the use of polymorphic kinds (let's
call them polykinds from now on).  First of all, it is not clear what
practical applications polykinds might offer (I have yet to find an
example where they are useful).  Furthermore, some of the deeper
theoretical issues about type inference and related topics have not yet
been studied and I suspect that polykinds would introduce significant
complications without any significant benefits.

The current approach is to replace any unknown part of an inferred kind
with the kind *.  Any polymorphism in the kind of a constructor
corresponds much more closely to the idea of a value that is not
actually used at all than in the language of normal expressions and
their types so this is unlikely to cause any problems.  And of course,
in Haskell and previous versions of Gofer, any variable used in a type
expression was assumed to be a type variable with kind *, so all of the
kinds above are consistent with this interpretation.

The rest of this section is likely to get a bit hairy.  Read on at your
peril, or skip to the start of Section 4.3.2.  Only those with a strong
interest in the type theory and pragmatics of constructor classes will
miss anything.

The same approach is used to determine the kinds of constructor
variables in type expressions.  In theory, this can sometimes lead to
problems.  In practice, this only happens in very contrived examples
and I doubt that any problems will occur for serious applications.  The
following example illustrates the kind of `problem' that can occur.
Suppose that we use a script containing the definitions:

    undefined :: a             -- the `bottom' value
    undefined  = undefined

    strange   :: f Tree -> f a
    strange    = undefined
    
The type signature for the `strange' function is indeed very strange;
the constructor variables f and a have kinds (* -> *) -> * and (* -> *)
respectively.  What's more, the type is very restrictive.  Without
including additional primitive constructs in the language, I very much
doubt that you will be able to find an alternative definition for
strange which is not semantically equivalent to the definition above.
And of course, the definition above doesn't really have any practical
applications anyway.  [In case you don't get my point, I'm trying to
show that this really is a very contrived example.]  I would be very
surprised to see a genuine example of a polymorphic operator which
involves constructor variables of higher kinds in a non-trivial way
that does not also include overloading constraints as part of the
type.  For example, it is not at all difficult to think of an
interesting value of type Monad m => a -> m a, but much harder to think
of something with type a -> m a (remember this means for all a and for
all m).

The definitions of undefined and strange above will be accepted by the
Gofer system as will the following definition:

    contrived = strange undefined

The type of contrived will now be  f a  where f :: (* -> *) -> * and
a :: (* -> *).  However, if we modify the definition of contrived to
include a type signature:

    contrived :: f a
    contrived  = strange undefined

then we get a type checking error:

    ? :l file
    Reading script file "file":
    Type checking      
    ERROR "file" (line 24): Type error in function binding
    *** term           : contrived
    *** type           : a b
    *** does not match : c d
    *** because        : constructor variable kinds do not match

    ?

The problem is that for the declared type signature, the variables f and
a are treated as having kinds (* -> *) and * respectively.  These do not
agree with the real kinds for these variables.

To summarize, what this all means is that it is possible to define
values whose principal types cannot be expressed within the language of
Gofer types in the current implementation.  The values defined can
actually be used within a program, but it would not, for example, be
possible to allow such values to be exported from a module in a Haskell
system unless kind annotations were added to the inferred types.


.ST 4.3.2  The kind of values in a constructor class
------------------------------------------------
The previous section indicated that, if the :set +k command line option
has been set, the :info command will include information about the
kinds of type constructor constants in its output.  This will also
cause the :info command to display information about the kinds of
classes and constructor classes.  Notice for example in the following
how the output distinguishes between Eq, a type class, and Functor, a
constructor class in which each instance has kind (* -> *):

    ? :info Eq Functor
    -- type class
    class Eq a where
        (==) :: Eq a => a -> a -> Bool
        (/=) :: Eq a => a -> a -> Bool

    -- instances:
    instance Eq ()
    ...

    -- constructor class with arity (* -> *)
    class Functor a where
        map :: Functor a => (b -> c) -> a b -> a c

    -- instances:
    instance Functor []
    ...

    ?


.ST 4.3.3  Implementation of list comprehensions
--------------------------------------------
The implementation of overloaded monad comprehensions is cute, but also
has a couple of potential disadvantages.  These are discussed in this
section.  As you will see, they really aren't very much to worry
about.

First of all, the decision to overload the notation for singleton lists
so that [ exp ] == result exp can sometimes cause a few surprises:

    ? map (1+) [1]
    ERROR: Unresolved overloading
    *** type        : Monad a => a Int
    *** translation : map (1 +) [ 1 ]

    ?

Note that this will only occur if you are actually using a prelude
which includes the definition of the Monad class given in Section 4.2
This can be solved using the command line toggle :set -1 which forces
any expression of the form [ exp ] to be treated as a singleton list
rather than being interpreted in an arbitrary monad.  You really
have to write `result' if you do want an arbitrary monad:

    ? :set -1
    ? map (1+) [1]
    [2]
    (7 reductions, 18 cells)
    ? map (1+) (result 1)
    ERROR: Unresolved overloading
    *** type        : Monad a => a Int
    *** translation : map (1 +) (result 1)

    ?

This should probably be the default setting, but I have left things as
they are for the time being, partly so that other people might get the
chance to find out about this and decide what setting they think would
be best.  As usual, the default setting can be recovered using the
:set +1 command.

A second concern is that the implementation of list comprehensions may
be less efficient in the presence of monad comprehensions.  Gofer
usually uses Wadler's `optimal' translation for list comprehensions as
described in Simon Peyton Jones book.  In fact, this translation will
always be used if either the prelude being used does not include the
standard Monad class or the type system is able to guarantee that a
given monad comprehension is actually a list comprehension.

If you use a prelude containing the Monad class, you may notice some
small differences in performance in examples such as:

    ? [ x * x | x <- [1..10] ]
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    (98 reductions, 203 cells)

    ? f [1..10] where f xs = [ x * x | x <- xs ]
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    (139 reductions, 268 cells)

    ?

The second expression is a little more expensive since the local
definition of f is polymorphic with f :: (Num b, Monad a) => a b -> a b
and hence the implementation of the comprehension in f does not use the
standard translation for lists.  To be honest, the difference between
these two functions really isn't anything to worry about in the context
of an interpreter like Gofer.  And of course, if you really want to
avoid this problem, an explicit type signature will do the trick (as in
other cases where overloading is involved):

    ? f [1..10] where f   :: Num b => [b] -> [b];
                      f xs = [ x * x | x <- xs ]
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    (99 reductions, 205 cells)

    ? f [1..10] where f   :: [Int] -> [Int]
                      f xs = [ x * x | x <- xs ]      
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    (99 reductions, 203 cells)

    ?

As the last example shows, there is only one more reduction in this
case and that is the reduction step that deals with the application of
f to the argument list [1..10].


.co-------------------------------------------------------------------|
.ST 5. GOFC, THE GOFER COMPILER

This release of Gofer includes gofc, a `compiler' for Gofer programs
which translates a large class of Gofer programs into C code which can
then be compiled and executed as a standalone application.

Before anybody gets too excited, there are a couple of points which I
should mention straight away:

  o  To make use of gofc, you will need a C compiler.  This is why I
     do not intend to distribute any binary versions of gofc; if you
     have the C compiler needed to compile the output of gofc then
     you should also be able to compile gofc from the sources.

  o  First of all, the Gofer compiler was written by modifying the
     Gofer interpreter.  Most of the modifications and changes were
     made in just a few days.  The compiler and interpreter still
     share a large proportion of code.  As such, and in case it isn't
     obvious: PLEASE DO NOT expect to gain the same kind of performance
     out of gofc as you would from one of the serious Haskell
     projects.  A considerably greater amount of time and effort has
     gone into those systems.

  o  The compiler is actually over a year old, but this is the first
     time it has been released.  Although I have worked with it a bit
     myself, it hasn't had half the amount of testing that Gofer user's
     have given the interpreter over the last year and a half.  It may
     not be as reliable as the interpreter.  If you have problems with
     a compiled program, try running it with the interpreter too just
     to check that you haven't found a potential bug in gofc.

That having been said, I hope that the Gofer compiler will be useful to
many Gofer users.  One possible advantage is that the executables may
be smaller than with some other systems.  And of course, the fact that
gofc runs on some home computers may also be useful.  Finally, gofc
provides a simplified system for experimenting with the runtime details
of an implementation.  For example, the source code for the runtime
system is set up in such a way as to make it possible to experiment
with alternative garbage collection schemes.


.ST 5.1  Using gofc
---------------
Compiling a program with gofc is very much like starting up the Gofer
interpreter.  The compiler starts by reading the prelude and then
loads the script files specified by the command line.  These scripts
must contain a definition for the value main :: Dialogue which will be
the dialogue expression that is evaluated when the compiled program is
executed.

For example, if the file apr1.gs contains the simple program:

    main :: Dialogue
    main  = appendChan "stdout" "Hello, world\n" exit done

then this can be compiled as:

    machine% gofc apr1.gs
    Gofer->C Version 1.01 (2.28)  Copyright (c) Mark P Jones 1992-1993
    
    Reading script file "/usr/local/lib/Gofer/standard.prelude":
    Reading script file "apr1.gs":
                   
    Writing C output file "apr1.c":
    [Leaving Gofer->C]
    machine% 

The output is written to the file apr1.c -- i.e. the name obtained by
removing the .gs suffix and replacing it with a .c suffix.  Other
filename suffixes that are treated in a similar way are:

    .prj    .gp                   for Gofer project files

    .prelude                      for Gofer prelude files

    .gof    .gs                   for Gofer scripts

    .has    .hs                   for Haskell scripts

    .lhs    .lit                  for literate scripts
    .lgs    .verb

If no recognized suffix is found then the name of the output file is
obtained simply by appending the .c suffix to the input name.

For the benefit of those using Unix systems, let me point out that this
could cause you problems if you are not careful; if you take an input
file called `prog' and compile it to `prog.c' using gofc, make sure
that you do not compile the C program in such a way that the output is
also called `prog' since this will overwrite your original source code!
For this reason, I would always suggest using file extensions such as
the .gs example above if you are using gofc.

If you run gofc with multiple script files, then the name of the output
file is based on the last script file to be loaded.  For example, the
command `gofc prog1.gs prog2.gs' produces an output file `prog2.c'.

Gofc also works with project files, using the name of the project file
to determine the name of the output file.  For example, the miniProlog
interpreter can be compiled using:

    machine% gofc + miniProlog
    Gofer->C Version 1.01 (2.28)  Copyright (c) Mark P Jones 1992-1993

    Reading script file "/usr/local/lib/Gofer/standard.prelude":
    Reading script file "Parse":
    Reading script file "Interact":
    Reading script file "PrologData":
    Reading script file "Subst":
    Reading script file "StackEngine":
    Reading script file "Main":
                   
    Writing C output file "miniProlog.c":
    [Leaving Gofer->C]
    machine% 

This is another case where it might well have been sensible to have
used a .prj or .gp for the project file miniProlog since compiling the
C code in miniProlog.c to a file named `miniProlog' will overwrite the
project file!  Choose filenames with care!

You can also specify Gofer command line options as part of the command
line used to run gofc.  Think of it like this; use exactly the same
command line to start Gofc as you would have done to start Gofer (ok,
replacing the command `gofer' with `gofc') so that you could start your
program immediately by evaluating the main expression.  To summarize
what happens next:

  o  Gofc will load the prelude file.  Do not worry if the prelude
     (or indeed, later files) contain lots of definitions that your
     program will not actually use; only definitions which are actually
     required to evaluate the main expression will be included in the
     output file.

  o  Gofc will load the script files specified.  If an error is found
     then an error message will be printed and the compilation will be
     aborted.  You would probably be sensible to run your program
     through the interpreter first to tidy up any errors and avoid this
     problem.

  o  Gofc will look for a definition of `main' and check that it has
     type Dialogue.  You will get an error if an appropriate main
     value cannot be found.

  o  Gofc determines the appropriate name for the output file.

  o  Gofc checks to make sure that you haven't used a primitive
     function that is not supported by the runtime system (see
     Section 5.2 for more details).

  o  Gofc outputs a C version of the program in the output file.

Once you have compiled the Gofer program to C, you need to compile
the C code to build the executable application program.  This will
vary from one system to another and is documented elsewhere.


.ST 5.2  Primitive operations
-------------------------
The Gofer compiler accepts the same source language as the
interpreter.  However, there is a small collection of Gofer primitives
which are only implemented in the interpreter.  The most likely
omission that you will notice is the primPrint function which is used
to define the show' function in the standard prelude.  Omitting this
function is not an indication of laziness on my part; it is impossible
to implement primPrint in the current runtime system because there is
insufficient type information available at program runtime.

.cc 5
For example, if you try to compile the program:

    main :: Dialogue
    main  = appendChan "stdout" (show' 42) exit done

the compiler will respond with the error message:

    ERROR: Primitive function primPrint is not
           supported by the gofc runtime system
           (used in the definition of show')
    Aborting compilation

The solution is to use type classes.  This is one of the reasons for
including them in the language in the first place.  This example can
be compiled by changing the original program to:

    main :: Dialogue
    main  = appendChan "stdout" (show 42) exit done

(Remember that show is the overloaded function for converting values of
any type a that is an instance of the Text class to a string value.)


.ST 5.3  Debugging output
---------------------
Another potentially useful feature of gofc is it's ability to dump a
listing of all the supercombinator definitions that are created by
loading a particular combination of script files.  For the time being,
this is only useful for the purpose of debugging, but with only small
modifications, it might be possible to use this as input to an
alternative backend/code generator system (the format of the output
combinators already uses explicit layout characters to make the task of
parsing easier in an application like this).

To illustrate how this option might be used, suppose that we were working
on a program containing the definition:

    hidden xs = map (\[x] -> x) xs

and that somewhere during the execution of our program, this function is
applied to a list value [[1],[1,2]]:

    ? hidden [[1],[1,2]]
    [1, 
    Program error: {v132 [1, 2]}
    (13 reductions, 75 cells)

    ?

The variable v132 which appears here is the name used internally to
represent the lambda expression in the definition of hidden.  For this
particular example, it is fairly easy to work this out, but in general,
it may not be so straightforward.  Running the program through gofc and
using the +D toggle as follows produces an output file containing Gofer
SuperCombinators, hence the .gsc suffix:

    machine% gofc +D file
    Gofer->C Version 1.01 (2.28)  Copyright (c) Mark P Jones 1992-1993

    [Writing supercombinators to "file.gsc"]
    Reading script file "/usr/local/lib/Gofer/standard.prelude":
    Reading script file "file":
    [Leaving Gofer->C]
    machine% 

Note that there is no need in this situation for the files loaded to
contain a definition for main :: Dialogue, although the compiler must
be loaded using exactly the same prelude and order of files as in the
original Gofer session to ensure that the same names are used.  Scanning
the output file, we find that the only mention of v132 is in the
definitions:

    v132 o1 = case o1 of {
                (:) o3 o2 -> case o2 of {
                               [] -> o3;
                             }
              }

    hidden o1 = map v132 o1;

This shows fairly clearly where the function v132 comes from.  Of
course, this is far from perfect, but it might help someone to track
down a bug that little bit faster one day.  It's better than nothing.

Of course, the debugging output might also be of interest to anyone
that wants to find out more about the implementation of Gofer and
examine the supercombinator definitions generated when list
comprehensions, overloading, local function definitions etc.  have all
been eliminated.  For example, the standard prelude definitions of map
and filter become:

    map o2 o1 = case o1 of {
                  [] -> [];
                  (:) o4 o3 -> o2 o4 : map o2 o3;
                }

    filter o2 o1 = case o1 of {
                     [] -> [];
                     (:) o4 o3 -> let { o5 = filter o2 o3;
                                  } in  | o2 o4 -> o4 : o5;
                                        | otherwise -> o5;
                   }

This is one of the tools I'll be using if anyone ever reports another
bug in the code generator...


.co-------------------------------------------------------------------|
.ST 6. SOME HISTORY

Ever since the first version of Gofer was released I've had requests
from Gofer users around the world asking how Gofer got its name and how
it came into being.  This section is an attempt to try and answer those
questions.

.ST 6.1  Why Gofer?
---------------
Everything has to have a name.  You may type in an `anonymous function'
as a lambda expression but Gofer will still go ahead and give it a
name.  To tell the truth, I always intended the name `Gofer' to be
applied to my particular implementation of a functional programming
environment, not to the language on which it is based.  I wanted that
to be an anonymous language.  But common usage has given it the same
name, Gofer.

If you take a look in a dictionary (as some puzzled Gofer users have)
you'll find that `gofer' means:

     ``an employee whose duties include running errands''

(although you'd better choose a dictionary printed since the 70s for
this).  I'd not thought about this when I chose the name (and I would
have used a lower case g instead of an upper case G if I had).  In
fact, Gofer was originally conceived as a system for machine assisted
equational reasoning.  One of the properties of functional languages
that I find particularly attractive is that they are:

    GOod For Equational Reasoning.
    ^^   ^   ^          ^
So now you know.  The fact that you can also tell someone who is having
a problem with their C program to ``Gofer it!'' (unsympathetic, I know)
is nothing more than a coincidence.  Fairly recently, somebody wrote to
ask if Gofer stood for ``GOod Functional programming EnviRonment''. I
was flattered; I wish I'd thought of that one.

Some people have asked me why I didn't choose a title including the
name `Haskell', a language on which Gofer is very strongly based.
There are two reasons for this.  To start with, the original version of
Gofer was based on a different syntax, Orwell + type classes.  The
Haskell influence only crept in when I started on version 2.xx.
Secondly, it's only right to point out that there is quite a large gap
between a system like Gofer and the full blown Haskell systems that
have been developed.  Using a name which doesn't involve `Haskell'
directly seemed the right thing to do.  Some people tell me that it was
a mistake.  One of the objectives of Haskell was to create a standard
language for non-strict functional programming.  Gofer isn't intended
as an alternative to Haskell and I hope it will continue to grow closer
as time passes.

While I'm on the subject of names, I should also talk about an
additional source of confusion that may sometimes crop up.  While Gofer
is a functional programming system, there is also a campus wide
information system called `Gopher' (sharing it's name with the North
American rodents).  I would guess that the latter has many more users
than the former.  So please be careful to spell Gofer with an `f' not
a `ph' to try and minimize the confusion.

It has occurred to me that I should try and think of another name for
Gofer to avoid the confusion with Gopher.  I hope that won't be
necessary, but if you have a really good suggestion, let me know!  One
possibility might be to call it `Gordon'.  The younger generation of
brits might know what the connection is.  Others may need to ask their
children...

.ST 6.2  The history of Gofer
-------------------------
Here is a summary of the way that I first learnt about functional
programming, and how it started me on the path to writing Gofer.
This, slightly sentimental review is mostly for my own entertainment.
If you're the sort of person that likes to read the acknowledgments
and bibliographic notes in a thesis: this is for you.  If not, you
can always stop reading :-)

My first exposure to lazy functional programming languages was using a
language called `Orwell' developed and used at the Programming Research
Group in Oxford.  I've been interested in using and implementing lazy
functional programming languages ever since.

One of the properties of programming in Orwell that appealed to me was
the ability to use equational reasoning -- a very simple style of
mathematical reasoning -- to establish properties of programs and prove
that they would behave in particular ways.  Even more interesting,
equational reasoning can be used to calculate efficient implementations
of programs from a formal specification of what was intended.

Probably the first non-trivial functional program that I wrote was a
simple Prolog interpreter.  (This was originally written in Orwell and
later transcribed to be compiled using the Chalmers Haskell B compiler,
hbc.  The remnants of this program live on in the mini Prolog
interpreter that is included with the Gofer distribution and, I
believe, with at least a couple of the big Haskell systems.) Using a
sequence of something like a dozen or so transformations (most of which
were fairly mundane), I discovered that I could turn a relatively
abstract specification of a Prolog inference engine into a program that
could be interpreted as the definition of a low level stack-based
machine for executing Prolog queries.  Indeed, I used the result as the
core of a C implementation of mini Prolog.

The transformations themselves were simple enough but managing the
complexity of the calculations was tough.  It was not uncommon to find
that some of the intermediate steps in a calculation would span more
than 200 characters.  Even with a relatively small number of
transformation steps, carrying out proofs like this was both tedious
and prone to mistakes.  A natural application for a computer!

Here's an outline of what happened next:

   eqr   1989.  Eqr was a crude tool for machine assisted equational
         reasoning.  It worked well enough for the job I had intended
         to use it for, but it also had a number of problems.  I
         particularly missed the ability to use and record type
         information as part of an automated derivation.

   1.xx  1990.  Gofer 1.xx was intended to be the next step forward
         providing machine support for *typed* equational reasoning.
         It was based on Orwell syntax and was later extended to
         support Haskell style type classes.  It had a lexer, parser,
         type checker and simple top-level interactive loop.  It
         couldn't run programs or construct derivations.

   2.xx  January 1991.  A complete rewrite.  I remember those early
         days, several months passed before I ever got compile some of
         the earliest code.  The emphasis switched to being able to run
         programs rather than derive them when I came up with a new
         implementation technique for type classes in February 1991.
         If I wanted to see it implemented, I was going to have to do
         it myself.  Around about May, I realized I had something that
         might be useful to other people.

   2.20  The first public release, announced in August 1991 and
         distributed shortly after that in September.

   2.21  November 1991, providing a more comprehensive user
	 interface, access to command line options and fixing a
	 small number of embarrassing bugs in the original release.

   2.23  August 1992, having been somewhat preoccupied with academic
	 studies for some time, the main purpose of this release
	 was to correct a number of minor bugs which had again been
	 discovered, either by myself or by one or more of the many
	 Gofer users out there.

   2.28  January 1993.  The most substantial update to Gofer since
	 the original release.  I had been doing a lot of work and
	 experimentation with Gofer during the time between the
	 release of versions 2.21 and 2.23, but I didn't have the
	 time to get these extensions suitable for public distribution.
	 By the time I came to release version 2.23, I also had
	 several other distinct versions of Gofer (each derived
	 from the source for version 2.21) including a compiler
	 and a prototype implementation of constructor classes
	 which was called `ccgofer'.   Work on version 2.28 started
	 with efforts to merge these developments back into a single
	 system (I was tired of trying to maintain several different
	 versions, even though I was the only one using them).
	 The rough outline of changes was as follows (with the
	 corresponding version numbers for those who wonder why
	 2.28 follows 2.23):

            2.24   enhancements and bug fixes
            2.25   merging in support for the Gofer compiler
            2.26   a reimplementation of constructor classes
            2.27   reworked code generator and other minor fixes
            2.28   preparation for public release
.co-------------------------------------------------------------------|