Reviving the Gofer Standard Prelude (circa. 1994)

Gofer (“GOod For Equational Reasoning”) was an early implementation of a Haskell 1.x-ish language by Mark Jones, originally released in 1991 (and written as a secret side project by Mark). It was famously used to develop type classes, do-notation and useful libraries involving them. It supported numerous interesting extensions (constructor classes , m*n+k patterns…). By 1994, it was rewritten to match the Haskell standard at the time, resulting in Hugs. Gofer was the first Haskell system I used (I used MacGofer, on a 68k Macintosh, to implement my comp1A assignments, including a CGI maze solving game with AI).

Gofer also supported easy addition of custom preludes, and comes with a number of interesting ones. I’ve started packaging up these prelude experiments with Cabal, and you can now get the gofer standard prelude from Hackage. The minimal prelude, constructor classes prelude, nofloat prelude, and the simplified preludes are still to come.

Looking at the Gofer 2.30 (~ Haskell 1.2) (.ps.gz) prelude, there are some interesting differences from the Haskell Prelude of today.

No monads!

One major difference is the entire absence of monads of any kind. Instead, to remain referentially transparent in IO, the gofer standard prelude used continuation-based IO (the successor to the very early stream-based IO model of Miranda).

Programs are represented as functions of the type:

    type Dialogue    =  [Response] -> [Request]

where Responses are values from the operating system, that are returned when the program makes requests of the kernel. The different kinds of requests we can make using the Gofer standard prelude:

    data Request  =
     -- file system requests
         ReadFile      String
       | WriteFile     String String
       | AppendFile    String String
    -- channel system requests
       | ReadChan      String
       | AppendChan    String String
    -- environment requests
       | Echo          Bool
       | GetArgs
       | GetProgName
       | GetEnv        String

and that’s it. Responses are similarly represented as:

    data Response =
       Success
     | Str     String
     | Failure IOError
     | StrList [String]

Each request/response pair is captured in a continuation passing manner, letting us build up transactions between the OS and the system. The standard continuations were:

    type SuccCont    =                Dialogue
    type StrCont     =  String     -> Dialogue
    type StrListCont =  [String]   -> Dialogue
    type FailCont    =  IOError    -> Dialogue

and with that we can write, say, readFile,

    readFile :: String -> FailCont -> StrCont -> Dialogue

which takes a filename to open, and can either fail or succeed with a string, so we plug in the two continuations to use in either case.

    readFile name fail succ resps =
         ReadFile name :
             case resp of
                  Str val     -> succ val resps
                  Failure msg -> fail msg resps

So add the ReadFile request into the stream, and associate with it a response to either succeed or fail, calling the appropriate continuations to take action.

No seq

There was no `seq` or ($!) to guide evaluation, but there was something close to it:

    primitive strict "primStrict" :: (a -> b) -> a -> b

which takes a function from a -> b, an a, and forces the result. We can port this to Haskell 98 or later, by rewriting it in terms of `seq`. For example, in Gofer, foldl’ was written as:

    foldl'           :: (a -> b -> a) -> a -> [b] -> a
    foldl' f a []     =  a
    foldl' f a (x:xs) =  strict (foldl' f) (f a x) xs

rather than the current definition of:

foldl' f z0 xs0 = lgo z0 xs0
    where lgo z []     = z
          lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs

or the version used for stream fusion using bang patterns, and slightly modified strictness (which optimises slightly better):

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f z0 xs0 = go z0 xs0
  where
    go !z []     = z
    go !z (x:xs) = go (f z x) xs

Note that the definition used these days has had the static argument transformation applied manually, yielding a non-recursive top level function, which will be easier to inline.

Strict folds and scans

Gofer also had a number of strict list functions that are either missing, or used differently now.

scanl'           :: (a -> b -> a) -> a -> [b] -> [a]
scanl' f q xs     = q : (case xs of
                         []   -> []
                         x:xs -> strict (scanl' f) (f q x) xs)

which doesn’t exist anymore.

sum, product    :: Num a => [a] -> a
sum              = foldl' (+) (fromInteger 0)
product          = foldl' (*) (fromInteger 1)

are defined to be strict, tail recursive loops. (These days we use the lazy foldl, and rely on rewrite rules to transform strict Num types into foldl’ – not an entirely satisfactory situation). These would be better definitions.

Some functions on triples also are not part of the standard:

fst3           :: (a,b,c) -> a
fst3 (x,_,_)    = x

snd3           :: (a,b,c) -> b
snd3 (_,x,_)    = x

thd3           :: (a,b,c) -> c
thd3 (_,_,x)    = x

Funky undefined

One of the cutest things is the definition of bottom, aka undefined: the computation that represents many kinds of failure (non-termination, error, etc):

undefined              :: a
undefined | False      = undefined

Hell yeah.

Missing list functions

Some other useful functions that no longer exist:

copy             :: Int -> a -> [a]      -- make list of n copies of x
copy n x          = take n xs where xs = x:xs

sums, products    :: Num a => [a] -> [a]
sums             = scanl (+) (fromInteger 0)
products         = scanl (*) (fromInteger 1)

--   takeUntil p xs  returns the list of elements upto and including the
--                   first element of xs which satisfies p
takeUntil           :: (a -> Bool) -> [a] -> [a]
takeUntil p []       = []
takeUntil p (x:xs)
    | p x         = [x]
    | otherwise   = x : takeUntil p xs

All which seem fairly reasonable.

On using a custom Prelude with GHC

You can cabal install the gofer prelude from Hackage, which I uploaded this morning:

$ cabal update
$ cabal install gofer-prelude 
Resolving dependencies...
Downloading gofer-prelude-2.30...
Configuring gofer-prelude-2.30...
Preprocessing library gofer-prelude-2.30...
Building gofer-prelude-2.30...
[1 of 1] Compiling Prelude.Gofer    ( Prelude/Gofer.hs, dist/build/Prelude/Gofer.o )
/usr/bin/ar: creating dist/build/libHSgofer-prelude-2.30.a
Installing library in /home/dons/.cabal/lib/gofer-prelude-2.30/ghc-6.10.1
Registering gofer-prelude-2.30...
Reading package info from "dist/installed-pkg-config" ... done.
Writing new package config file... done.

Documentation for the Prelude will be online shortly, here. To use it, load it up in GHCi, and hide the Haskell Prelude,

$ ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help
Prelude> :m – Prelude
> :m + Prelude.Gofer
Prelude.Gofer> :t takeUntil
takeUntil :: (a -> GHC.Bool.Bool) -> [a] -> [a]
Prelude.Gofer> :t undefined
undefined :: a
Prelude.Gofer> undefined
*** Exception: Prelude/Gofer.hs:1048:0-34: Non-exhaustive patterns in function undefined

Interestingly, Gofer exported very few data types, with only Int and Float available by default (no Integer). The port of the gofer prelude to GHC reuses GHC’s implementations of these data types, and other primitives on them, as well as reimplementing strict and error in terms of GHC’s seq and error.

In addition, to write a new Prelude in GHC, you have to disable the old one, with -XNoImplicitPrelude which turns off all the Prelude types , and makes the syntax for enumerations, list comprehensions, do-notation, arrows and numeric literals rebindable.

These syntactic features desugar to various functions (fromRational, fromInteger, fail, (>>), (>>=)), so we have to ensure the Gofer versions of these functions are in scope instead.

Enjoy your flashback to Haskell of 15 years ago!