A Haskell to Lisp Interface

John Peterson

Department of Computer Science

Yale University New Haven, CT 06520

1 Introduction

Recent work has shown how purely functional languages such as Haskell can be integrated with imperative languages by using monads to encapsulate the state of the imperative computation. This preserves the referential transparancy of the functional language and avoids placing constraints on the use of side effects. This is especially important for I/O operations which are inherently action oriented.

In addition to the problem of combining the functional and imperative programming worlds, mixed language programming with Haskell requires solutions to a number of other problems. Entities visible from the Haskell program must be named in the Haskell name space and given type signatures in the Haskell type system. Data structures must be shared or transmitted between different languages. We use interface files, similar to those used by Haskell to support separate compilation, to connect namespaces and describe data types and structures.

This paper describes an interface between Haskell and Lisp based on monads and interface files. Data structure conversion between lazy Haskell objects and non-lazy Lisp structures can be performed automatically. In addition, Lisp objects can be manipulated directly by a Haskell program without conversion. This interface is used within the Yale Haskell system to implement primitive data types and operations as well as to implement the I/O system. It has also been used to build an interface between Haskell and the X window system through the CLX library.

Some aspects of this interface are described elsewhere, such as the precise syntax of annotations, the compilation system, and the use of monads.

2 Interface Files

The Haskell language uses interface files to describe the properties of a module necessary to compile referenced to objects in the module. This concept can easily be extended to use interface files to describe code which is not itself written in Haskell. For standard Haskell, an interface file gives names and type signatures for the definitions within a module. To use such a file as an interface to Lisp code we add a mapping from names in the Haskell name space onto symbols in the Lisp namespace. As long as the type signature in the interface correctly describes the corresponding Lisp object, the Haskell system does not need any further information about the Lisp code.

Here is a simple example involving integer addition. The following interface defines a module named Add containing a single entity: a function which adds two integers.

interface Add where
add :: Int -> Int -> Int

This interface can be extended with an annotation which tells the Haskell code generator that calls to the add function (as defined in the Haskell name space) should be implemented by a call to a Lisp function. This annotation, LispName, takes a single argument: a string containing the Lisp object to be used as the add function. Since in Lisp, + is used for addition, the following interface would work:

interface Add where
add :: Int -> Int -> Int
{-# add :: LispName("+") #-}

This indicates to the Haskell code generator that calls to the Haskell add function should be translated to calls to the Lisp +. The following program uses add:

module Main where
import Add
main = print (add 1 2)

A number of things happen behind the scenes for this example to work. First, there is an implicit conversion of the datatype Int to its equivalent Lisp representation. Second, there is an implicit conversion of the function calling protocols between the Lisp and Haskell worlds — Haskell’s call protocol supports currying and laziness, while the Lisp protocol does not. When the interface is compiled a wrapper function is generated which takes care of the call conversion. By default, the system determines the arity of the function from its type signature and passes the correct number of arguments to the Lisp function. Also by default, the Lisp function is assumed to be strict: all parameters are evaluated before being passed to the Lisp code.

In this particular example, the default behavior makes everything work as it should. In more complicated situations, you must provide some additional information explicitly; this is described in detail in the next section.

In most cases, you need to load the file (or files) containing the Lisp functions being called. The recommended way to do this is by naming the Lisp files in the .hu file for the compilation unit. Alternatively, you can load the file into the system by hand using the Lisp evaluator which is accessable through the command interface to Haskell.

The file containing Lisp code can be loaded into any Common Lisp package. Lisp objects referenced in annotations are, by default, in the MUMBLE-USER package. This package is used for the implementation of the compiler and code in this package is in a Scheme-like dialect of Lisp. Real Common Lisp code should be placed in a different package, usually the user package. Using a package prefix in the LispName annotation ensures that the the correct Lisp function is referenced. Finally, the Lisp definition need not be a function: a macro may also be used.

The following example elaborates on the previous addition example. One way of greatly increasing the performance of the Lisp code is to add type declarations. With appropriate declarations, the file of Lisp code might look like this:

(in-package 'user)
(defun add (x y) (the fixnum (+ (the fixnum x) (the fixnum y))))

The interface file might be done like this:

interface Add where
add :: Int -> Int -> Int
{-# add :: LispName("user::add") #-}

3 Data Conversions

In the previous example, the Lisp and Haskell programs shared a common representation of the data types used. In the case of more complex structures, conversions are required to transform lazy Haskell structures into the their non-lazy Lisp equivalants and perform other changes in representation. Yale Haskell does this automatically for the following data types: Bool, Int, Integer, Float, Double, lists, Char, and String.

For example, an interface such as

interface Concat where
stringConcat :: String -> String -> String
-- assume string-concat is defined in the Lisp world
{-# stringConcat :: LispName("user::string-concat") #-}

works as expected even though Haskell and Lisp use different string representations.

Occasionally, the automatic conversions are not needed. Conversion to Lisp form evaluates a data structure completely; this may not be desired in all cases. You can suppress the automatic conversions by using the annotation NoConversion on the appropriate functions.

No user defined types are converted in any way by the Lisp interface.

Another conversion issue involves the strictness of function arguments. In Haskell, arguments are passed lazily. At the Lisp level, such lazy arguments are represented using delay objects. However, the default behavior is to evaluate the delays and pass the resulting value — rather than the delay object — to the Lisp function. This behavior can be overridden with an explicit strictness signature. A strictness signature is a string of N (non-strict) and S (strict) characters separated by commas. The strictness property also defines how many arguments are passed to the Lisp function. The function force can be used to evaluate lazy function arguments (or lazy components of a data structure).

For example, the following interface defines the if function:

interface If where
myIf :: Bool -> a -> a -> a
{-# myIF :: LispName("user::my-if"), Strictness("S,N,N") #-}

The corresponding Lisp code would be

(in-package 'user)
(defun my-if (test x y)
  (if test (mumble-user::force x) (mumble-user::force y)))

Since the test is declared strict it does not need to be forced. The use of explicit mumble-user package prefixes is necessary since the code has been placed in the user package.

4 Managing Side Effects

So far, only pure Lisp functions have been considered. Impure functions which either modify or read the global program state must be called through the I/O monad. The Haskell I/O system in Yale Haskell has been defined in terms of a monad which sequences I/O operations. New Lisp functions can be added to the I/O monad simply by defining them with IO in the result type. It is the responsibility of the user to properly declare impure Lisp functions to the Haskell system — failure to do so has unpredictable consequences.

Writing a string to the terminal is an example of a function which must use the monad. Since this function does not return a useful value to the Haskell program, its result type should be given as IO () (this is the same as Dialogue). The interface would be:

interface WriteString where
writeString :: String -> IO ()
{-# writeString :: LispName("lisp:write-string")

5 Abstract Data Types

Data types used by the Lisp world may be returned to Haskell functions by Lisp primitives. These types can be used to represent objects cannot be defined in the Haskell type system, or whose internal structure is not directly visible to the Haskell program. When such structures are mutable, only functions in the monad can be used to reference this internal state. Conceptually, the Haskell system views the object as a reference which names part of the global state. Thus the object itself remains referentially transparent even though it contains mutable structure.

A good example of this is a Lisp hash table. The following interface defines a simple hash table library using strings as both the keys and values in the hash table.

interface Hash where
data HashTable  -- an abstract data type
newTable :: IO HashTable
getTable :: HashTable -> String -> IO String
putTable :: HashTable -> String -> String -> IO ()
{-# newTable :: LispName("user::new-hash-table")
    getTable :: LispName("user::get-hash-table")
    putTable :: LispName("user::put-hash-table") #-}

The Lisp code would look like this:

(in-package 'user)
(defun new-hash-table () (make-hash-table :test #'equal)
(defun get-hash-table (table key) (gethash key table ""))
(defun upate-hash-table (table key value) (setf (gethash key table) value))

Objects of type HashTable can be used freely in the Haskell program. However, only calls to the monad via readTable and putTable can be used to reveal the mutable component of the table. Even though readTable itself has no side effect, it must be declared using the IO type since the value it returns depends on the result of changes to the program state.

6 Sharing Data Structures

Abstract data types allow only a limited form of sharing between Lisp and Haskell. An abstract data type does not allow direct access to the internal structure of an object through pattern matching or construction. You can accomplish a more general sharing of objects by defining an object in terms of a set of functions which construct new values and select components from existing values of that type.

An operational view of a data constructor is simply a set of functions which test for, build, and select fields from a value. Thus a constructor of arity k is represented by k + 2 functions: a test predicate, a constructor function that accepts k arguments, and k component selectors. Data types with only one constructor do not need a test predicate; this is only necessary when more than one constructor is associated with a data type.

You can define the basic operations on a data type in either the Lisp or the Haskell world. You can import a data type defined in Lisp into Haskell using the ImportLispType annotation. This annotation can be placed either in a Haskell interface file or in an ordinary Haskell source code file. In either case, the annotation must be in the same module which defines the data type.

An ImportLispType annotation defines data types by giving the appropriate Lisp functions which operate on the type. For each constructor in the data type, you need to list the functions that implement the k + 2 functions. The functions are ordered: the first is the test predicate, then the constructor function, and then the k selectors.

As an example, Haskell lists could are implemented using the following type declaration:

data List a = Null | Cons a (List a)
{-# ImportLispType(List(Null("lisp:null","'()"),
                        Cons("lisp:consp","lisp:cons","lisp:car","lisp:cdr")))
     #-}

The Lisp expressions in quotes need not be symbols: constants such as '() and even anonymous function definitions can be used. Note specifically that a nullary constructor must be a Lisp value, rather than the name of a function that is called with no arguments.

This definition of a list retains the laziness of Haskell. That is, the components of the list must be delays. The Haskell compiler inserts delays into any list created by cons in the above declaration and expects that car and cdr return delays. Any use of this structure from Lisp must use delays in the same manner.

Lazy structures can be avoided using strictness annotations. If the definition of the list type had been

data List a {-# STRICT #-} = Null | Cons a (List a)

then the elements of the structure would not be delayed. This declaration could be used to allow Haskell to directly make use of ordinary Lisp lists.

The next example elaborates on hash tables. We make a number of improvements in the previous hash table example. First, the tables are polymorphic in their data values. We still use strings as hash table keys but the values stored in the hash tables are unrestricted. Second, we make hash table construction non-strict in the data value. Implementationally, the values associated with the keys in the Lisp hash table are delay objects which are forced only when they are extracted from the table. Finally, we introduce a shared data type to indicate lookup failure. We implement this as nil for unsuccessful lookup. Since the values in the hash table are delay objects, the use of nil cannot be confused with actual data values. We also add a printer for hash tables.

interface HashPrims where
import HashTable(Maybe,HashTable)
newTable :: IO (HashTable a)
getTable :: HashTable a -> String -> IO (Maybe a)
putTable :: HashTable a -> String -> a -> IO ()
{-# newTable :: LispName("user::new-hash-table")
    getTable :: LispName("user::get-hash-table-table")
    putTable :: LispName("user::put-hash-table"),Strictness("S,S,N")  #-}
module HashTable(Maybe(..),HashTable,newTable,getTable,putTable) where
import HashPrims
data Maybe a = None | Just a deriving Text
{-# ImportListType(Maybe(None("lisp:null","'()"),
                         Just("user::not-null",
                              "lisp:identity","lisp:identity"))) #-}
data HashTable a = HashTable a
instance Text(HashTable a) where
  showsPrec x p = showString "<Hashtable>"
(in-package 'user)
(defun new-hash-table () (make-hash-table :test #'equal)
(defun get-hash-table (table key) (gethash key table '()))
(defun put-hash-table (table key value) (setf (gethash key table) value))
(defun not-null (x) (not (null x)))

There are a number of subtle points to this example. By declaring the data structures in an ordinary Haskell module Text instances can be attached. This would not be possible if the declaration were placed in the interface file. Since Haskell does not allow abstract data types to be declared directly, the Hashtable type is declared with a constructor but this constructor is not exported. The strictness signature for putHash prevents evaluation of the value argument. Instead, this argument is passed as a delay object. The delay is passed out into the Maybe structure. Since this structure was not declared strict, the delay extracted from the hashtable becomes the delay within the Maybe structure. The representation of Maybe only works because a delay can never be nil, allowing proper discrimination between the None and Just constructor.

Analagous to ImportLispType is ExportLispType. This annotation causes the Haskell code generator at create the test, construction, and selection functions itself. These functions can then be called from Lisp code. Again, watch out because nullary constructors are defined as variables rather than functions of zero arguments.

7 Conclusions

This Haskell to Lisp interface could easily be extended to other languages. In particular, most Lisp systems contain a C code interface which can be reached through this interface.

This interface provides both a link between the purely functional and imperative worlds and allows them to easily share data structures. Since Lisp is an untyped language, the burden is on the user to correctly describe the type of Lisp objects to the Haskell system.