The Yale Haskell Users Manual

Version Y2.0.5

June 23, 1993 The Yale Haskell Group

Department of Computer Science

Yale University New Haven, CT 06520

1 Introduction

This manual describes version Y2.0.5 of the Yale Haskell system. The Haskell language is fully defined in the “Haskell Report” [3]. This document refers to version 1.2 of the Haskell report; we advise that copies of older versions be replaced by this new report as there are many significant differences.

1.1 About Yale Haskell

The Yale Haskell system is an integrated Haskell programming environment. It is embedded in a Lisp environment and retains many of the advantages of this style of program development. Our Haskell system provides tightly coupled editing, compilation, and execution of Haskell programs. Incremental compilation allows rapid prototyping and testing in an interactive environment.

Yale Haskell can be used either directly via a command interface or as an inferior process under the Emacs editor. Within the Emacs enviroment Haskell expressions can be evaluated during the editing of a Haskell source file. A tutorial on the Haskell language is also part of the Emacs environment.

We provide an interface between Haskell and the underlying Lisp which allows the user to mix Lisp and Haskell code. This release includes an extensive X window interface, based on the CLX system.

The Haskell compiler itself is written in a small Lisp dialect similar to Scheme or EuLisp which runs on top of Common Lisp. Haskell programs are translated into Lisp and then compiled by the underlying Lisp compiler.

Yale Haskell can be built on top of most Common Lisp systems. We distribute both the source to our system for use with local commercial Lisp products and a precompiled executable built on CMU Common Lisp.

We do not yet generate stand alone compiled Haskell programs; all program execution takes place within the underlying Lisp environment. Our system also requires a significant amount of memory to run. Users with limited memory may find the system sluggish.

1.2 The 2.0.5 Release

This release incorporates many changes from previous versions of our system. The type checker, pattern matcher, and optimizer have been completely rewritten. The optimizer is considerably more powerful than in previous releases; see the separate document which explains the implementation of the optimizer.

We have implemented a number of enhancements to the Haskell language. These include:

• The I/O system is implemented using a monad, similar to the Glasgow Haskell system.

• Strictness annotations in type declarations can be used to define non-lazy structures. This is similar to what the hbc system supports.

• Annotations can be used to control the optimizer.

• A Lisp interface is supplied. This is similar to the C interface in the Glasgow compiler.

• We support separate compilation using unit files. These are similar to localized makefiles and tell the compiler about compiler settings and dependencies among units.

This release has been ported to CMU Common Lisp, Lucid Lisp, AKCL, Allegro Common Lisp, and Harlequin Lispworks. Because of licensing restrictions, only the CMU based system is being released in binary form. We expect to have a Macintosh version (using MCL) available soon.

We supply many Haskell programs and utilities in our distribution. The directory $HASKELL/progs contains many examples of Haskell programming. Within this directory, prelude contains the version of the prelude used by the system, demo contains many sample programs, lib contains a number of useful libraries, including the X window interface. All documentation is in

$HASKELL/doc.

A number of aspects of the system are as yet incomplete or incompatible with standard Haskell. These include:

• Stream I/O has been eliminated — see section 5.

• Some error messages are rather cryptic.

• A few errors are not recovered from correctly, causing the compiler to crash later during compilation.

• Some I/O requests are not implemented or are not meaningful in the Haskell environment we supply.

• We do not handle interface files yet.

1.3 Haskell Mailboxes

There are a number of mailboxes associated with Haskell and the Yale Haskell Project, as described below.

   • haskell-requests@cs.yale.edu

Use this address to communicate with us about our compiler. We also maintain the Haskell mailing list.

   • haskell-bugs@cs.yale.edu

Send bug reports to this address.

   • haskell@cs.yale.edu

This is a mailing list for general issues concerning the language. Messages sent to this address will be forwarded to all members of the Haskell discussion list, which has a USA distribution managed by Yale and an European distribution managed by the University of Glasgow. Please do not send bug reports or other messages specifically about the Yale implementation to this list!

1.4 Using this Manual

Casual users of Yale Haskell need only read either section 2 about the Emacs interface or section 3 about the command interface. First time users need to configure their environment for the Haskell system; this is described in section 10. Section 8, about compilation errors, may also be useful for novice users. We advise users unfamiliar with the language to try the tutorial from the Emacs interface. If you want to use programs larger than a single source file, section 4 describes how to do this.

2 Using Haskell From Emacs

We supply two different programming environments with Yale Haskell: an editor based environment built on the Emacs editor and a command interpreter. Both provide the same functionality but the Emacs environment is much more convenient and is the recommended way of using Yale Haskell. If you plan to use the command interpreter, you can skip this section.

2.1 The Haskell Emacs Mode

Before using the Haskell Emacs mode, you must first configure your .emacs file as described in section 10. Once your .emacs file has been modified to recognize Haskell programs, the Emacs editor will enter Haskell mode whenever a file with extension .hs or .lhs is visited. Haskell mode provides commands to control the Haskell compiler as an inferior process under Emacs. There are two basic commands: evaluating and printing expressions (C-c e) and running dialogues (C-c r). They operate as follows:

1. Emacs prompts you for a Haskell expression. For C-c e, the value of expression must in class Text. For C-c r, the value must be of type Dialogue.

2. An inferior Haskell process is started if one is not already running.

3. All .hs and .lhs buffers are saved.

4. The file containing the cursor is compiled by the Haskell compiler if necessary.

5. The expression is evaluated or run in the context of the module containing the cursor (there may be more than one module in a file). The Haskell dialogue buffer, named *haskell*, pops up to display the result.

All interaction with the Haskell process occurs in the Haskell dialogue buffer. This buffer receives status and error messages and well as I/O operations on stdin and stdout. The cursor moves to this buffer automatically if a running program requests input.

2.2 Scratch Pads

While developing Haskell programs it is often convenient to temporarily add definitions to a module. A scratch pad is a special buffer associated with a module (not with a file!) in which you may place definitions for use during the editing session. Changes to the scratch pad definitions do not require full recompilation of the module and are especially useful when large programs are being developed. The scratch pad is also a good place to enter and test new functions before moving them into the source file. When you use either the C-c e or C-c r commands in a scratch pad, you may reference the definitions in the pad as well as those in the associated module.

To avoid global recompilation, there are a number of restrictions on definitions which may be placed in a scratch pad:

• A scratch pad may not contain any import or fixity declarations. Only names visible in the associated module or within the pad itself can be referenced.

• No definition in a pad can be exported from the associated module.

• The pad cannot redefine anything in the associated module.

When Haskell is not started from within a Haskell source file, a scratch pad onto an empty program (*Main-pad*) is created. You can use this pad to play with the system without creating a .hs file.

2.3 Emacs Commands

This section describes in detail the commands available when running Haskell mode.

In the following, the current module is determined by the type of buffer containing the cursor. In a .hs buffer, the current module is the module definition containing the cursor. In a pad, it is the module associated with the pad. In the *haskell* buffer, the most recently used module is remembered.

A dialogue is any Haskell expression that is of type Dialogue.

The minibuffer commands M-p and M-n allow you to search back and forth through the history of the last 30 expressions you have typed in when Haskell prompts you for something to evaluate.

haskell-eval (C-c e) This command prompts you for a Haskell expression to be evaluated. Evaluation occurs in the context of the current module. The result is then printed; the value must be in class Text.

haskell-run (C-c r) This command prompts you for a Haskell dialogue and runs it. Its behavior

     is similar to haskell-eval.

haskell-run-main (C-c m) This command runs the dialogue named main in the current module.

haskell-run-file (C-c C-r) Runs all the dialogues in the current file.

haskell-get-pad (C-c p) Pops up the buffer containing the scratch pad for the current module, and makes it the current buffer.

haskell-printers (C-c C-p) This command pops up a buffer that lets you set Haskell compiler print options from a menu. Use ? to get further help.

You can specify printer settings for a particular program within its unit file. See section 4.

haskell-optimizers (C-c C-o) This command pops up a buffer that lets you set Haskell compiler optimizer settings from a menu. Use ? to get further help.

You can specify optimizer settings for a particular program within its unit file. See section 4.

haskell-compile (C-c c) The Lisp code produced by the Yale Haskell compiler can either be interpreted or compiled. Since compiling the generated Lisp code into machine language takes much longer than generating it from the Haskell source program, you probably don’t want to do this during program development. Commands such as C-c e and C-c r do not compile the code generated or write any compiled code into files. When you are ready to create fully compiled code and save it in output files, use the C-c c command. This command recursively compiles all imported compilation units.

haskell-exit (C-c q) This command terminates the Haskell subprocess. It leaves all buffers open.

haskell-switch (C-c h) Pops up the *haskell* buffer and makes it the current buffer. haskell-interrupt (C-c i) This command sends an interrupt to the Haskell subprocess. You can

use it to terminate execution of a running program (for example, if it gets stuck in an infinite loop) and return to the command loop.

haskell-please-recover (C-c d) Sometimes Lisp errors may cause the synchronization between Emacs and Haskell to be lost. This command attempts to reset both the Emacs interface and the Haskell subprocess to a known state.

We have observed symptoms of an apparent race condition or synchronization problem in the Emacs subprocess package on the NeXT. If, when you first start the Haskell subprocess, it does not indicate “ready” on the mode line, you can unwedge it by issuing the C-c d command.

haskell-command (C-c :) You can submit commands directly to the command interface with this command. See section 3 for more information about the command interface.

haskell Starts up a Haskell subprocess, popping up the *haskell* buffer. You normally don’t need to do this explicitly since any of the commands that cause code to be evaluated or compiled will also start up a Haskell subprocess if there isn’t already one running.

haskell-mode Puts the current buffer into the Haskell editing mode.

haskell-tutorial Starts the online Haskell tutorial.

2.4 The Haskell Tutorial

An online supplement to the Hudak and Fasel tutorial (supplied in the $HASKELL/doc directory and published in Sigplan Notices) is available. Start this tutorial using the command M-x haskell-tutorial. The tutorial explains how to use the Emacs commands as well as presenting an introduction to the Haskell language.

3 The Command Interface

This section gives brief descriptions of all commands used by the command interface. Users of the Emacs environment can skip this section.

When you run the Haskell executable $HASKELLPROG directly, it puts you into a command loop. The command interface also provides an incremental compilation ability through program extensions. An extension is a Haskell program which is scoped within an existing module.

The command interface reads both Haskell program extensions and system commands. Commands start with a : and control the compiler and the environment. Commands which refer to an extension always deal with the most recently entered extension within the context of the current module. The current module name is used as the system prompt.

Any input line which does not begin with : is assumed to be a line of Haskell source code and is added to the current extension. There are two abbreviations provided within extensions. A line beginning with = prints an expression. This expands into a definition of a dialogue to accomplish the printing when executed. Lines beginning with @ run user dialogues. All other lines are treated as ordinary Haskell source code.

Command arguments are separated by whitespace. All commands may be abbreviated using the shortest unique prefix of the command name. For a description of them see Figure 1.

3 THE COMMAND INTERFACE 6 Commands:

:?  Prints a help file.
:eval  Evaluate any executable definitions in the current

extension. The extension may still be saved.

:save  Save the current extension. If any errors are

found, nothing will be saved.

:clear  Remove all saved extensions in the current module
:Main  Enter the empty Main module.
:quit  Exit the Haskell system.
:module module Set the current module. The :run command also

sets the current module. Initially, an empty module Main which imports the prelude is available.

:compile file  Like :r except than no execution occurs.
:load file  Load a Haskell program into memory without compiling

generated Lisp code or creating a compiled output file.

:run file  Load and run main in a file.
:cd dir  Set the current directory (absolute path only).
:list  List the current extension.
:kill  Kill (erase) current extension.
:p?  List available printers.
:p= printers  Set printers.
:p+ printers  Turn on printers.
:p- printers  Turn off printers.
:o?  List available optimizers.
:o= optimizers Set optimizers.
:o+ optimizers Turn on optimizers.
:o- optimizers Turn off optimizers.
:(exp)  Evaluate a Lisp expression exp.

Figure 1: Command interface directives

The :eval, :save, :clear and :kill commands terminate the current extension. All other commands allow the current extension to be continued.

Any command using a file refers to the most recently referenced file when no file is provided. Files extensions are implicit in the commands and need not be supplied.

To interrupt a running Haskell program, use ^C (or whatever interrupt character is used by your system).

3.1 An Example

Haskell Y2.0 Command Interface. Type :? for help

Initially, Haskell evaluates in a module containing only the Prelude

Main> fact 0 = 1
Main> fact n = n*fact(n-1)

Main> :save This makes fact an addition to Main
Main> = fact 4 This will print 4 ! when evaluated. No need to save this.

Main> :eval
24
Main> :cd $HASKELL/progs/demo

Main> :run fact An interactive factorial supplied in demo
Evaluating main. The name of the variable in fact being evaluated

Type in N: 4
24

Extensions to the original Main are now lost.

Main> adds (x:xs) (y:ys) = x+y : adds xs ys
Main> :s
Main> f = 0 : 1 : adds f tail f
Main> :s
[TYPE-ERROR] Phase error in phase TYPE:
Type conflict: type [a] does not match [a] -> [a]
Error occurred at line 2 in file interactive.
While type checking
adds f tail
Argument type mismatch
Types: Num b => [b]
       [c] -> [c]
Cannot save: errors encountered.
Main> f = 0 : 1 : adds f (tail f)
Main> :s

Main> = take 5 f Since f is infinite, print only the first 5 elements

Main> :e
[0,1,1,2,3]

4 The Compilation System

The compilation system is responsible for gathering all components of a program for compilation. When a single file contains the entire program, this task is trivial. However, when a program contains more than one file, you must group them into a compilation unit. You can also use compilation units to specify various compilation options, even for programs that consist of only one source file.

4.1 Compilation Units

A Haskell program consists of a collection of modules. The Haskell report does not define how this collection is to be assembled; this is left to the implementation.

Yale Haskell defines the following objects:

Module The syntax for a module (actually, a module implementation) is as described in the Haskell report. Modules cannot span file boundaries.

File Each file must contain one or more modules.

Compilation Unit A compilation unit is described by a .hu file. This file defines a set of source file names and a set of imported compilation units. It may also specify various compilation options.

Program A program consists of the modules in a compilation unit combined with all modules found in imported compilation units.

The set of modules in a program must satisfy two criteria:

1. No module may appear more than once. It is an error for two modules in a program to have the same name.

2. All modules referenced in import statements must be declared in the program. The module Prelude is implicitly added to every program by the system.

Compilation units in Yale Haskell are defined by files with the .hu extension. The contents of the .hu file are similar to command line arguments used with other compilers. Some of the functionality of the make utility is also provided since the compiler will compile any uncompiled units needed and determine whether a source file has been updated after the last compile.

Yale Haskell places one significant restriction on compilation units: each compilation unit must itself be a valid program. The effect of this restriction is that compilation units cannot be mutually dependent. If two modules are mutually recursive, each importing the other, you must place them in the same compilation unit. Within a compilation unit, there are no restrictions on the importing of modules.

4.2 Compilation Unit Files

Compilation units are defined in files with a .hu extension. A .hu file contains a list of file names and compiler options, one per line. File names and options may appear in any order inside the .hu file.

Specifically,

• A file name with a .hs, .lhs, or .hi extension specifies a constituent Haskell source file of the compilation unit.

• A file name with a .hu extension specifies a compilation unit to import. This means that, if you want to import a unit that consists of a single source file, you must create a unit file for it.

:input filename Specify different filename defaults for source files.
:output filename Specify different filename defaults for output files.
:import filename Specify different filename defaults for imported units.
:stable  Don’t try to recompile this unit if already compiled or loaded.
:prelude  Don’t implicitly import the standard prelude.
:p= printers  Specify printers for this unit.
:o= optimizers  Specify optimizers for this unit.
:o= all  Turn on all optimizers.
:chunk-size n  Set chunk size for Lisp compiler.

Figure 2: Compilation unit options

• A file name with a .scm or .lisp extension specifies a file containing Lisp code. When you compile or load the compilation unit, these Lisp files are compiled or loaded (as appropriate) individually in the order in which they are listed in the unit file, before any of the files containing Haskell code are processed. (This is useful in conjunction with a .hi file to include Lisp code in your Haskell program.)

• Compiler options are prefixed with a colon. The compiler options that you can include in a .hu file are summarized in Figure 1.

You must supply extensions for all of the file names. The directory for both source files and imported units (as well as that for the output files of the compilation) defaults to the same directory as the .hu file.

Compiling a unit with the C-c c or :compile normally writes two output files: an object code file and an interface file. Both of these files contain Lisp code. The name of the interface file is suffixed with -hci. The extension used for the output files varies depending on the underlying Lisp implementation. For example, compiling foo.hu in the CMU-based system produces foo-hci.scm and foo.sparcf as output.

If the unit contains many source files, or very long files, the code file is automatically split up into smaller chunks to make it easier for the Lisp compiler to process. The individual pieces are

given names like foo-part1.sparcf.

4.3 Recompilation as Needed

Compilation units serve to break a program into separately compilable pieces. To run the program, all component pieces must be compiled and loaded into the system. Yale Haskell attempts to reduce the amount of processing needed when compiling a program by saving previously compiled units in files and only recompiling them when they change.

Once compiled, a compilation unit may become outdated in one of several ways:

• A source file within the compilation unit changes.

• An imported unit becomes outdated.

• The definition of the unit changes.

In addition to these three possibilities, a unit must certainly be compiled if no compiled version exists.

The compilation system will not compile a unit based on outdated imported information; it will attempt to bring the imported units up-to-date by compiling them if necessary.

You can suppress the automatic recompilation behavior by specifying the :stable option in the unit file. If you do this, compilation takes place only if the unit has not already been loaded and there is no previously-compiled version which can be loaded.

4.4 Using Compilation Units

Some care must be taken when using compilation units from either the Emacs interface or the command interface. The program being compiled must be specified by a compilation unit. To avoid creating .hu files for one file programs, the compiler can be called with a single source file. Otherwise, the system needs to know about the compilation unit in use.

In the command interface, the file used by the :compile and :load commands is actually a compilation unit. The .hu extension is not needed: the system will look for a .hu before looking for a source file. In a program consisting of a unit U with two source files A and B, you need to load unit U after editing either A or B. Trying to compile A or B directly will result in an error.

The Emacs interface assumes that the unit file associated with a source file has the same name but an extension of .hu. If the name is different, add a comment line containing unit: file at the start of the file, as in: -- unit: myunit

5 The I/O Monad

The I/O system in Yale Haskell is implemented using a monad. We have built the continuation I/O functions defined in the report directly on the monad, allowing the continuation I/O to be freely mixed with monadic I/O calls without conversion. We do not support stream based I/O as defined in the Haskell report but programs using only the continuation style of I/O will run unchanged. Although it would be possible to support stream I/O by supplying a suitable stream interpreter within the monad, we feel this style is obsolete and should not be used.

Monadic I/O has a number of advantages over stream I/O. The most important advantage is that new I/O operations can be added to the monad in a modular manner. This is not possible with streams since all possible I/O operations must be encoded in a single datatype. The monad also enhances polymorphism and can be easier to use.

The I/O monad has been built into the prelude. Names used here are compatible with the Glasgow Haskell system. The following have been added to PreludeIO:

type IO a = SystemState -> IOResponse a
type Dialogue = IO ()
thenIO :: IO a -> (a -> IO b) -> IO b
seqIO :: IO a -> IO b -> IO b
returnIO :: a -> IO a
doneIO :: IO ()

An I/O operation returning type a would have type IO a. The type Dialogue is defined in terms of the monad instead of requests and responses. The SystemState and IOResponse data types are abstract datatypes used internally by the I/O system; you should not use these directly.

The function thenIO is used for sequencing within the monad. It passes the result of one I/O operation on to another. When no result needs to be passed out of an I/O operation, seqIO (same as thenIO_in the Glasgow system) can be used. The returnIO function performs no I/O operation and returns the supplied value. doneIO is a special case of returnIO which is essentially an empty dialogue.

A good tutorial-level introduction can be found in ??. This paper is available in the pub/haskell/papers area for ftp. Be warned that the function names differ slightly: bindIO instead of thenIO and unitIO instead of returnIO. Examples of the monadic style of I/O can be found in PreludeIO and in the Lisp interface examples.

6 Annotations

The Yale compiler recognizes a number of annotations in the source program. Annotations are used for strictness properties, optimizer control, and the interface to the Lisp environment.

6.1 Annotation Syntax

Annotations are a special form of comments. They begin with {-# and end with #-}. Within these delimiters, annotations are separated by semicolons in the same manner as declarations. Layout is in effect allowing the semicolons to be omitted.

Each annotation has a name and possibly a set of arguments, enclosed in parentheses and separated by commas. The exact syntax of the arguments varies with the type of annotation.

Annotations generally refer to some object in the program. Sometimes this object is implicit in the placement of the annotation. Otherwise, the object being annotated is explicitly named using :: syntax, similar to signature declarations. More than one annotation can be attached to a value by separating annotations by commas.

For example, in

{-# a,b :: Inline, Complexity(4)
    g :: LispName("foo")
    LispFile("blah") #-}

there are three annotations. The values a and b are annotated with Inline and Complexity annotations. The Complexity, LispName, and LispFile annotations all have a single argument. The LispFile annotation does not refer to a named object directly and does not need the :: syntax.

Annotations are generally placed among declarations. As with type declarations, also a form of annotation, annotations for an object must be placed in the same scope in which the object is declared.

6.2 Strictness Annotations

Strictness annotations can be placed on data types and functions. You can declare a slot of a data constructor to be strict by placing {-#STRICT#-} immediately after the slot type in the data declaration. For example, in the type declaration

type T a b = C1 a {-#STRICT#-} b | C2 a b {-#STRICT#-}

the first argument to C1 and the second to C2 is strict.

You can force all the slots for a datatype to be strict by placing the {-#STRICT#-} immediately before the = in the data declaration.

You can also specify strictness of function arguments with an annotation. This is not normally necessary since the strictness analyzer computes the strictness for each function defined in a program. Should you wish to do this, use the Strictness annotation:

   {-# f :: Strictness("N,S,N") #-}

This declares that f is strict in its second argument. The strictness is denoted by a string of S (strict) and N (non-strict), separated by ,.

6.3 Optimizer Annotations

The optimizer makes use of two annotations. The Inline annotation declares that the value of a variable should be inlined at each reference. You should use this sparingly to avoid code bloat. See 9 for some hints about when to use this. The syntax is:

   {-# f :: Inline #-}

The Complexity annotation indicates the approximate time of evaluation of a function. The optimizer uses this information to avoid delaying relatively trivial expressions. This annotation takes an integer argument, like:

   {- f :: Complexity(3)}

The optimizer currently ignores the magnitude of the complexity argument, but this may change in future releases. We suggest that you use values between 1 and 10.

6.4 Other Annotations

The Lisp interface uses many other annotations; these are described in a separate document.

7 Interfacing with Other Languages

Yale Haskell provides a simple method for calling functions written in other languages. Since the Yale Haskell system runs within a Lisp environment, the “foreign function” mechanism is currently designed for a Haskell-to-Lisp interface. This could easily be extended to other languages callable from Lisp.

This interface is based on interface files which describe Lisp code instead of Haskell functions. Full details are found in a separate document.

8 Errors and Debugging

8.1 Type Errors

Type errors can be difficult to deal with. If the error becomes especially difficult to uncover, turn on the type printer. Do this from Emacs via C-c C-p and selecting the printer for type or use :p+ type in the command interface.

We suggest that top level declarations be affixed with type signatures. This practice has a number of advantages:

• Incorrect definitions of a function are caught by the type signature instead of causing a type error at a call site.

• Unwanted overloading is eliminated.

• The signatures provide an additional level of documentation.

When dealing with an ordinary type signature mismatch, check that the proper number and types of arguments are being passed to the function. Also examine infix operators and make sure that their precedences are what you expect.

The pattern binding rule can be the source of unexpected errors. This rule restricts overloading of variables bound in pattern bindings. Global overloaded constants, structures which contain overloaded functions, and functions without arguments (that is, defined by a pattern binding) can cause an error when they have no explicit type signature.

The class system causes type checking to fail in a different way for overloaded function parameters than for non-overloaded parameters. For example,

length True

gives a standard type mismatch error. An overloaded function, like +, handles type mismatches differently. The + function accepts any type of argument in class Num. An error in a call to +, as in:

True + False

results in a message indicating that Bool is not in class Num. Such messages usually result from ordinary type mismatches.

Another source of subtle type errors are overloaded numeric constants. An integer constant has the typing Num a => a. When integers are used unexpectedly, the type unification algorithm complains that the parameter type is not in class Num. For example, in:

length 3

the type error generated indicates that lists (the expected argument type to length) are not a member of class Num.

Application is represented internally by a type constructor named Arrow. When a functional object is used in a situation in which it is constrained by a class, an “instance not found” for type Arrow is generated. For example, in:

(max 1) + 1

the argument to + must be in class Num. The value of max 1 is a function since both arguments have not been supplied. Since functions are not in class Num an error message indicating that Arrow is not a member of Num is generated. The omission of a function argument is the most common way of generating this error. Tuples and lists also have internal type names used in error messages: Tuplek

and List.

Another typing error that can be difficult to understand is the ambiguous context. These are often generated when a specific type constructor does not instantiate all type parameters in a data type. For example, the typing of [] is (List a). By itself, [] does not require a specific element type in the list. However, instance declarations for the list data type often place constraints on the list components. For example, [a] is in class Text only when a is. In

print []

an ambiguous context occurs since print requires that the list elements, whose type remains unknown, be in Text. This can be avoided using a type signature:

print ([] :: [Int])

since this removes the type variable a from the signature of [].

Another common type-related error can occur in instance declarations. Instance declarations require the user to explicitly state the entire context associated with an instance. If the body of an instance requires a more general context than declared in the context component of the instance declaration, an insufficient context error message will occur.

8.2 Runtime Errors

When the Haskell error function is called at runtime, the system displays the message associated with the error and aborts execution. There is currently no way to examine the system state when this occurs. Some constructs, such as case statements, add error calls to the program.

Add explicit “error handlers” to non-exhaustive case statements and function definitions; this is good coding practice and eases debugging. It is also good coding practice to avoid non-disjoint patterns whenever possible (such patterns also tend to translate into less efficient code than patterns written disjointly).

Using Int arithmetic can lead to serious runtime errors when overflows occur. Only unsafe Int operations are currently provided. If you run into memory protection problems, illegal instructions, or other mysterious errors when the program executes, check for potential overflow problems. Changing Int to Integer should fix this problem.

If you think your program is in an infinite loop, use C-c i from the Emacs or ^C from the command interface to interrupt the Haskell process.

9 Performance Issues

Many different factors affect the speed of the compiled Haskell code and the compilation time. This section deals with both of these issues.

9.1 Improving Compilation Time

The best way to reduce the time of compilation is to break your program into small compilation units. This is not only good programming style, but also helps to isolate compilation errors and allows you to take advantage of the separate compilation capability of the system. In particular, you should place common datatype declarations in a separate file whenever possible — this conforms with good application of abstract datatype principles, if nothing else.

We have found that the time required for the Lisp compiler to process the code usually far outweighs the time required to translate Haskell to Lisp. Some Lisp compilers seem to have particular problems with the large number of lexical closures that can appear in the generated code. Typical symptoms of this trouble are when the Lisp compiler takes a very, very long time and/or runs out of memory. Large compilation units are split into smaller chunks (as described in section 4) before processing them with the Lisp compiler in an attempt to avoid these problems. However, if you still run into trouble, here are some other things that you can try:

• Specify a smaller :chunk-size in the unit file. The default value is 300 for most Lisp systems, so you might try a value of 100 or less.

• Disable the lisp optimizer.

• Flatten the structure of your code so that you have more top-level definitions and fewer large, deeply nested functions.

• Consider using annotations to force more things to be strict. See section 6.

• Some Haskell constructs expand into unexpectedly large amounts of code. Derived instances for types with many data constructors are a particular problem. Calls to overloaded functions incur a substantial amount of overhead that you can avoid in many cases by providing type declarations.

9.2 Generating Faster Code

Two factors affect the speed of the compiled code: the efficiency with which Haskell constructs are translated into Lisp code and the speed of the primitives used. The math primitives are the most visible. The performance of the primitives reflects the underlying Lisp system. Some facts about the primitives:

• Int arithmetic is very fast. It is usually done inline with a single instruction.

• Integer arithmetic is somewhat slower. It is done out of line and is about 20 times slower in the Int range.

• Char operations are fast.

• Array access is constant time but array updating requires copying the entire array. Bounds checking is performed on all array accesses.

Other aspects of the performance reflect the Haskell compiler itself. The following performance aspects relate to the current compiler and may be improved in future releases:

• Strictness analysis[1] eliminates delay structures from scalar variables when possible but does not deal with structure components. There is a significant time and space penalty for lazy constructors compared to those in a strict language. You may wish to consider adding strictness annotations to some of your data structures; see section 6.

• Calls to known (first order) functions are optimized to take advantage of uncurrying and strictness optimizations. No additional overhead is incurred by the system. Calling unknown (higher order) functions is much slower since these optimizations cannot be applied.

Most functions from the standard prelude that accept functional arguments have inline annotations to enable the higher-order calls to be removed. You may wish to use inline annotations for this purpose in your own code.

• Simple functions such as . or && are inlined even without an inline annotation. A heuristic is used to select functions for automatic inlining.

• Since the class system is implemented using higher-order functions, overloading can add a significant overhead. There is generally no penalty for using overloaded operators on fixed types. When the data type associated with an operator is unknown at compile time, roughly 100 extra instructions are necessary for a strict binary operation. In the case of an extremely simple operation, like Int +, this is a factor of around 100 in the execution time. The penalty for overloading more complex operations is much less.

• Irrefutable pattern matching is slower than refutable pattern matching.

9.3 Optimizer Options

By default, the compiler attempts to do only a minimal amount of optimization at both the Haskell and Lisp levels. Although you can enable more optimizations from the command interface or the Emacs optimizers menu, as well locally within a unit file, leaving the optimizers turned off makes the compilation process go faster.

Once you have debugged your code, we recommend that you add an option to the unit file for your program to enable various compiler optimizations. You can either use :o=all to enable all of the optimizers, or list them individually, as in :o=inline foldr. Here is a list of the various optimizers and what they do.

inline If this option is enabled, the optimizer marks functions that have “trivial” definitions as inlinable, and also inlines references to both variables and functions that have already been noted as inlinable. If it’s disabled, the optimizer is much more conservative about inlining.

constant This option controls whether the optimizer attempts to detect function applications that evaluate to constant values, specifically applications of data constructors to constant arguments. If enabled, the optimizer hoists such applications to top level to avoid repeated evaluations.

foldr If this optimization is enabled, the optimizer performs foldr/build deforestation as described in [2]. The purpose of this optimization is to avoid constructing intermediate lists by pipelining multiple list traversal operations (such as mapping) within a single loop.

lisp If this optimization is enabled, appropriate flags are set to encourage the Lisp compiler to produce the best possible machine code at the expense of additional compilation time. If this option is disabled, the Lisp compiler performs a moderate level of optimization.

For more details about how the optimizer works, refer to the notes on the implementation supplied as a separate document.

9.4 Memory Management Issues

If you are attempting to compile or run large programs, you may need to change the heap size or other memory management parameters of the underlying Lisp system. Unfortunately, the different Lisp implementations use different storage allocation and garbage collection strategies, and provide various switches and parameters that are too diverse for us to be able to provide a single interface that works across all the Lisp implementations we support. If you need to tweak these parameters, you’ll need to issue the appropriate commands directly to the underlying Lisp. And, if these hints aren’t sufficient, refer to the documentation for the particular Lisp implementation you are using.

In all of the Lisps we currently support, you can do (lisp:room '#t) to get information about current memory usage.

9.4.1 CMU Common Lisp

CMU Common Lisp uses a simple stop-and-copy garbage collector. There is no fixed limit on the heap size — it is adjusted automatically at each GC — but you can control the interval between garbage collections by setfing the Lisp variable ext:*bytes-consed-between-gcs*. If you set this variable, it doesn’t actually take effect until the next GC occurs. You can force a GC by executing

(ext:gc).

9.4.2 Lucid Common Lisp

Lucid uses a ephemeral garbage collector with several spaces in addition to a stop-and-copy collector. It allocates memory to these spaces by 64k segments, and will increase the heap size as necessary, subject to a limit on total memory usage.

To set the memory management parameters, call the function lcl:change-memory-management. This function accepts numerous keyword arguments to control the various parameters. The ones you are most likely to need to alter are the :expand argument (which forces an immediate expansion of the heap) and the :growth-limit argument (which sets the maximum memory usage). You can do (lcl:change-memory-management :help '#t) to get a summary of all the different arguments.

9.4.3 Allegro Common Lisp

Allegro CL manages its heap in two spaces, called the newspace and oldspace. New objects are allocated from the newspace, which is managed using a stop-and-copy garbage collector. After surviving a certain number of GCs, objects in newspace migrate to oldspace, which is GCed less frequently. Both newspace and oldspace grow automatically.

You can’t set the absolute size of the newspace, but you can adjust the size of the newspace by specifying how many free bytes are to remain after a GC by setfing (sys:gsgc-parameter :free-bytes-new-other). There are also a bunch of other parameters that let you control the increment by which the newspace is grown, how many generations are required to promote objects to oldspace, and the like. Refer to the Allegro manuals for more details.

9.4.4 Harlequin Lispworks

Lispworks uses a generational garbage collector with three generations. The first and second generations are managed with a stop-and-copy collector, but the oldest generation is not normally garbage collected at all. Again, the system attempts to grow the heap automatically when necessary. You can’t set the absolute heap size, but you can control the interval between garbage collections by specifying the :minimum-for-sweep keyword argument to the lw:set-gc-parameters function. This function accepts other arguments to control the amount by which the heap is enlarged and when objects are promoted to the next generation.

9.4.5 AKCL

AKCL divides dynamic memory into two parts: cells and relocatable blocks. Cells are the fundamental representations of objects, and some types of objects (such as vectors) include a pointer to a relocatable block. The garbage collector for cells works strictly by building a free list and never relocates cells or deallocates pages already allocated for a specific type of cell. However, garbage collection does compact storage allocated for relocatable blocks.

AKCL provides no mechanism for setting the total size of the heap. In essence, each of the different types of objects has its own heap that is managed separately from the others.

If AKCL runs out of memory for a specific type of object, its default behavior is to increase the number of pages allocated for that type of object by 50%. You can also tell it explicitly to allocate more memory for a particular type of object. For example, if you want to tell it to allocate 500 pages (2K each) for cons cells, you can do (sys:allocate 'cons 500). Similarly, you can do something like (sys:allocate-relocatable-pages 100) to control how much memory is available for relocatable blocks. Use the lisp:room function to find out the current allocation statistics and the different classes of cells.

9.4.6 Macintosh Common Lisp

We don’t fully support MCL yet. Sorry.

10 Installation Procedures

10.1 Haskell Users

All users of the Haskell system need to modify their .cshrc file to define the environment variable HASKELL and read the Haskell shell init file. The variable HASKELL points to the directory in which the system has been installed. The following lines go in .cshrc:

setenv HASKELL <directory containing Haskell>
source $HASKELL/haskell-setup

Remember to reload your .cshrc before you run Haskell for the first time.

Users of the Emacs Haskell mode need to make a few changed to their .emacs file.

• Add the Haskell Emacs tools directory to the search path:

     (setq load-path
           (cons (concat (getenv "HASKELL") "/emacs-tools")
                 load-path))

• Change the value of the Emacs variable auto-mode-alist:

     (setq auto-mode-alist
           (append '(("\\.hs$" . haskell-mode) ("\\.lhs$" . haskell-mode))
                    auto-mode-alist))

This will cause entry into the Haskell mode whenever a Haskell source file is edited.

• Make Emacs load the Haskell mode from the start:

     (load-library "haskell")

10.2 Init Files

It is possible to customize the Haskell environment using init files which are read to the Haskell system at startup. These can be used to control the underlying Lisp environment. The files $HASKELL/.yhaskell and ~/.yhaskell are read into the Lisp system on startup. These files are dependent on the particular Lisp being used and are not further described here.

10.3 Installing the Distribution

If you are using the executable distribution, installation of the Yale Haskell system is simple. After unpacking the tar file, the system should be immediately runnable by a user who has made the necessary modifications to .cshrc and .emacs.

To rebuild the system from the source distribution, see the instructions in the README file in the appropriate subdirectory of $HASKELL/com.

Compiling the Yale Haskell system from the source distribution takes a few hours and requires a substantial amount of virtual memory, particularly for processing the standard prelude. We recommend that you have at least 50 megabytes (and preferably more) of swap space available to do this. Once the system has been built, we’ve been able to run reasonably-sized programs on workstations with around 20 megabytes of swap space.

You will also need some disk space to rebuild the system. On a Sparc, the Lucid version requires about 15 megabytes, the CMU and AKCL versions about 25 megabytes. This is in addition to the disk space required to install the Lisp system.

We have noticed that the AKCL version is noticibly slower than versions built with the other Lisps. We recommend that you use a “real” Lisp to build Yale Haskell if at all possible.

References

[1] Chuck Consel. Fast strictness analysis via symbolic fixpoint iteration. Technical Report YALEU/DCS/RR-867, Yale University Department of Computer Science, September 1991.

[2] Andrew Gill, John Launchbury, and Simon L Peyton Jones. A short cut to deforestation. In Functional Programming and Computer Architecture, 1993.

[3] Paul Hudak, Simon Peyton Jones, Philip L. Wadler, Brian Boutel, Jon Fairbairn, Joseph H. Fasel, Maria M. Guzman, Kevin Hammond, John Hughes, Thomas Johnsson, Dick Kieburtz, Rishiyur Nikhil, and John Peterson. Report on the programming language haskell: a non-strict, purely functional language, version 1.1. Technical Report YALEU/DCS/RR-777, Yale University Department of Computer Science, August 1991.