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!

6 thoughts on “Reviving the Gofer Standard Prelude (circa. 1994)

  1. Thanks for this piece of archeology!

    Gofer was also my gateway drug leading to Haskell addiction. And you examples bring up some good old memories. In school we had an assignment to write a hangman program in Gofer using the continuation-based IO. I remember it as being quite painful. I’m glad it didn’t scare me away though. Not long after I found a tutorial on monadic IO which was some very welcome news.

    It’s funny how the Gofer prelude still has its place somewhere in the back of my head. Even to this day I sometimes look for functions like sum, product and copy in the Haskell Prelude only to find that they aren’t there.

    Thanks again.

  2. Fun stuff, thanks.

    It seems to me that the definition of scanl’ in gofer was sort of bugged, in that it’s still too lazy to be of any use. No strictness is actually forced because it’s buried under a lazy cons.

    > scanl’ (+) 0 [1..] !! 1000000
    *** Exception: stack overflow

    My understanding is that seq has to be used at the top level of the expression to have effect.
    If I use something like this instead

    scanl” f q (x:xs) = y `seq` (q : scanl” f y xs)
    where y = f q x
    scanl” f q [] = [q]

    it works, although this seems a little too eager since we are forcing a value we may never use.

  3. That makes sense, although then I think strict in Hugs would be the same as $! in Haskell. This doesn’t match the description of strict that you give since the argument is forced, not the result of the evaluation of the function.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s