Lazy Imperative ProgrammingJohn Launchbury
Computing Science Department
Glasgow University
jl@dcs.glasgow.ac.uk

Abstract[Wad92]. From this work it became clear that lazy evaluation and imperative actions could coexist quite happily,
In this paper we argue for the importance of lazy state, that with each being able to pass values to the other.
is, sequences of imperative (destructive) actions in which The Glasgow Haskell compiler incorporates extensions to
the actions are delayed until their results are required. This the lazy functional language Haskell. These extensions imenables state-based computations to take advantage of the plement imperative actions [PW93]. However, the implecontrol power of lazy evaluation. We provide some examples mentation has an important shortcoming: all imperativeof its use, and describe an implementation within Glasgow actions are performed before any results are returned. This
Haskell.
parallels strict evaluation where all the arguments to a function are evaluated before a result is given, even if the valuesof the arguments are not required. In non-strict languages(as implemented by lazy evaluation, for example) functions
1 Introduction
may return results without requiring the successful evaluation of arguments whose values are not required.
There has long been a tension between functional programming languages and their more traditional imperative coun- In this paper we see how to retain the philosophy of nonterparts. On the one hand, functional languages are com- strict computation, even in the presence of imperative acmonly more expressive and easier to reason about than tions. To see the relevance of this, it is worth distinguishimperative languages, but on the other hand, certain al- ing between two distinct classes of state-based computation.
gorithms and interactions seem to rely fundamentally on Sometimes it is necessary to manipulate the global worldstate-based computation. It is clearly worth attempting to state, such as when accessing les or communicating withthe outside world, whether as an interactive program or by
combine the strengths of each.
communicating with other programs. These are externallySome languages like Scheme and ML have incorporated im- state-based computations. Other times however, computaperative actions as side e ects. This approach only makes tions require purely local state. This may be either for easesense in a call-by-value language where the order of eval- of programming, passing a name-supply around for examuation is statically de ned. In lazy functional languages ple, or because a given algorithm relies on constant-time
like Haskell or Miranda, evaluation order is dynamically de- update to achieve a given asymptotic complexity. In bothtermined, so can be immensely dicult to predict. If such cases the state is purely internal to the computation, and islanguages obtained imperative actions as side-e ects of eval- utterly invisible to the outside world.
uation then serious reasoning diculties would result. Determining which side e ects are to be performed, and worse, As the state from an internally state-based computationin which order, would rely on determining the exact order may be discarded at the end of the computation, it makesof evaluation|the very thing that laziness tends to hide! sense to ask whether all the imperative actions should alConsequently lazy evaluation and side e ects do not mix. ways be performed: any that do not a ect the nal value
could be discarded freely. This may be generalised by makThere is a way forward however. The recent work of Moggi ing the state thread entirely lazy. Hughes argues that the[Mog89] showed how monads could be used to structure true power of laziness is to decouple control from calculation
denotational semantics, including the handling of state in [Hug89], and we show the same arguments apply to interimperative languages. Wadler recognised that the same nally state-based computations. We provide some examples
principles apply for functional programs and, in particu- of this, and give an implementation of lazy-state in Glasgow
lar, showed how the state monad could be used to incorpo- Haskell.
rate imperative operations in a purely functional language

The contribution of this paper, therefore, is to show that,ccall putchar c

1. lazy state provides a much better t with lazy eval- is a call to the C function which outputs a character on theuation than does strict state; in particular, the usual standard output. No particular value is returned, so its type
expressiveness associated with lazy evaluation also ap- is IO (). On the other hand,plies to internally state-based computations;
ccall getchar

2. lazy state may be implemented to provide constanttime access and update: the only penalty compared has type IO Char: it is a computation which returns a charwith strict state is in the creation of extra unevalu- acter value.
ated closures|exactly the usual penalty paid by movFinally, the meaning of a Haskell program is given by a
ing from strict to lazy function application.
de nition of mainIO, an identi er of type IO (). To execute
As this paper builds directly on the work by Peyton Jones a program, mainIO is applied to the external world state,
returning an updated world state as a result.
and Wadler [PW93], it makes sense to review that rst.

2 Imperative Haskell

3 Delayed Side E ects

important aspect of the IO monad is that all the imImperative features were introduced to Glasgow Haskell for An
perative
actions are forced. Consequently, IO expressions
expressing input and output, so the type constructor for have a very
poor match with lazy evaluation. Consider thestate-based computations is called IO. A state-based com- following expression
1:
putation that produces a purely functional value of type atherefore has type IO a. A value of type IO a is not a side`thenIO` \a->e ecting computation. Rather it is a recipe for performing fooIO
bazIO `thenIO` \b->certain actions and returning an appropriate result. In fact,
elements of the IO type are all functions, awaiting an ar- returnIO (a||b)gument representing the world state. When applied to aworld state, evaluation of the function produces a result Whenever this expression is performed (applied to the worldstate) both fooIO and bazIO are performed, returning
paired with another world state.
(boolean) values bound to a and b respectively. Only thenBy making IO a an abstract data type with limited built in are these values or -ed together to produce the nal result.
operations, it is possible to guarantee that all references to Contrast this with the behaviour of the purely functional
the state are single threaded. Then no state argument ever expression foo||baz. In a non-strict language, foo would
needs to be passed explicitly: the real external world may be evaluated and only if it returns False would baz be evalbe used instead and all updates may be performed in-place. uated.
The main two operations provided on the IO type are the However, as the IO type is provided for external state comfamiliar monadic combining forms.
putations, this behaviour is quite reasonable. On the mainline of IO actions, every imperative action has to be performed before the program terminates: the meaning of a
returnIO :: a -> IO a
program is de ned to be the total e ect it has on the world.
thenIO :: IO a -> (a->IO b) -> IO b
This means that whenever an IO operation is speci ed, it
The former packages up its value into a computation which might as well be performed immediately. There is no bendoes nothing except return the value. The latter is a form e t in delaying it, since it has to be performed before theof function application. It performs the rst computation, program terminates.
yielding a value of type a. This result is passed to the On the other hand, the example does provide an argument
function argument which, on receiving a value of type a, that expressions which use state purely internally should do
returns a computation designed to produce a value of type so in a lazy way. That is, if we had a way of encapsulatingb. No value is returned until both arguments to thenIO have the state in the example above, then bazIO should only
been performed.
be performed if a is False. The result of an encapsulated
Other IO primitives may be built using the ccall construct 1 The lambda bindings \a-> and \b-> are in scope to the end of theexpression.
which allows calls to any C function. For example,

expression should be de ned by the purely functional values someStateOps will be performed, and in the order origiit returns, and not by any imperative actions it performs. nally speci ed, before any state operations in exampleB are
If a function uses state to produce a result, and hides that performed.
state from everything else (including other invocations of
the same function), then there is no reason to perform all of
the state operations. Rather, only those which are required 3.2 Discarding Stateby data dependency should be performed.
We de ne lazy sequences to be state transformers where the
There is one important caveat. The order in which imper- state is an abstract data type representing the encapsulated
ative actions are performed is important. We must ensure, state.
therefore, that the order in which they are performed remains unchanged; that is, if the value from any action is type Seq a = ST World arequired, all earlier actions must rst be performed.
We achieve this encapsulation with the function newSeq.

3.1 Passing State Around

newSeq :: Seq a -> aGiven that the IO type is strict in its state actions, we will newSeq takes a sequence expression, opens up a new, empty
use a di erent name for lazy state operations. The only imperative context, sequences the imperative computation,
restriction on when such operations are performed is that and extracts the nal value discarding the nal state.
they must be performed in sequence, so we name the typeThe evaluation of such a computation mirrors usual lazy
constructor for such actions Seq.
evaluation:
only those computations and state actions that
Seq is built upon the standard monad of state transformers.
occur
up
to
where the result is suciently de ned
A state transformer is a function which, when given a state (according tothethepoint
external
demand) are performed; the res, produces a pair of results: a value and a new state.
mainder are suspended. If more of the result is demanded
then more computations or imperative actions may be pertype ST s a = s -> (a,s)
formed until the value is suciently de ned to satisfy its
consumers. As usual, only computations required by dataWe provide the standard unit return and the sequence com- dependency are performed (recall that imperative actions
have the extra data-dependency of a single-threaded state).
binator called bind.
When, eventually, all references to the nal value are discarded, all the remaining actions become garbage, and are
return :: a -> ST s anever performed.
bind:: ST s a -> (a->ST s b) -> ST s b
For the present, we will continue to take it on faith that lazy
return a s = (a,s)
imperative actions can be performed in a truly imperatively
bind m k s = k a t where (a,t) = m smanner (by destructive update), and will turn to examinesome examples, showing the sort of behaviour we want to
By single-threading the state, the state monad ensures that achieve.
state operations are sequenced. It does not demand thatall state operations are performed. Consider the following
3.3 Monad Syntax
example.
For the rest of the paper we use syntactic sugar to refer toexampleA :: ST s Bool
monad
operations. We extend Haskell expressions with an
exampleA s = someStateOps `bind` \v ->expressionof the form {Q} which is expanded as follows2:
return True
Q ::= E | E;Q | x<-E;Q

Because the nal value True does not depend on the state,
the computations in someStateOps are not performed. In{E}= E
deed, not even the initial state is demanded.
{E;Q}= E `bind` \_->{Q}{x<-E;Q} = E `bind` \x->{Q}If, however, exampleA is sequenced together with othercode, exampleB say, which does require the state in order 2 Haskell actually uses these symbols as layout markers. We will
to de ne the nal value, then all the state operations in not do so here|every use of {, }, and ; will be for monad syntax.

scanLeft :: (a->b->b) -> (b,[a]) -> ([b],b)scanLeft f (init,xs) = newSeq {v <- newVar init;
ys <- scan xs
where
scan
[]
= return []scan (x:xs) = {val <- readVar v;
writeVar v (f x val);
rest <- scan xs;
return (val:rest)};
final <- readVar v;
return (ys,final)}

Figure 1: Imperative Scan Left
To see this in action, consider the following example:{x <- op1;(y,z) <- op2 x;
op3 z x;return y}This is translated into the following expression:
op1`bind`
op2 x`bind`
op3 z x `bind`
return y\x->\(y,z)->\_->

Given an initial value x say, newVar x is a sequence operation which when performed, allocates a variable in thestate having initial value x, and returns a reference to thevariable. Similarly, if v is a variable (a state reference),then when readVar v is performed (applied to the state)
it returns the value of v in the state. As may be expected,
writeVar updates the value of the variable.
Using these we will implement a function scanLeft. Givena function, a starting value, and a list, scanLeft applies
the function repeatedly across the list, working from left toright, and returns a list of partial results, paired with thenal answer. For example,

That is, the semicolon is translated into the monad sequence scanLeft (+) (0, [1,2,3,4]) = ([0,1,3,6], 10)
operation `bind`, and if an explicit pattern is given, it isconverted into the pattern on the trailing lambda expres- It is important that the result of scanLeft is generated
sion, so causing those names to be in scope across the re- by demand. If only an initial portion of the result list is
mainder of the expression. If no pattern is written, then any required, then that is all that should be computed. In partrailing lambda is given the wildcard pattern which matches ticular, even if only some front portion of the input list isde ned (and the rest unde ned), an equivalent front portion
everything but binds nothing.
of the result list should still be de ned. For example,

3.4 Scan Left?

scanLeft (+) (0, 1:(2:(3: )))= (0:(1:(3: )), )?

?

The rst example exhibits the use of an updatable variable.
This is an example that is commonly written in a purely There are two parts to the code given in Figure 1. The
functional style, so the value of this example is not about rst interfaces the main loop with the outside (functional)
whether to use a state-based computation, but rather to world. It creates a new imperative context, and within thisdemonstrate that the use of state does not restrict which generates a variable v to hold the running total. The main
results may be returned.
loop of the function is called. This returns the list of partial
results and, after reading the nal value of v, the function
For now, we will assume we have the following operations returns
on variables, and treat Var a simply as an abstract data final. a pair consisting of the list ys and the nal resulttype of variables of type a.
The main loop updates the value of the variable v for each
newVar:: a -> Seq (Var a)element of the list, returning a list made up of the value of
readVar :: Var a -> Seq av at the start of the loop followed by the list returned by
writeVar :: Var a -> a -> Seq ()the rest of the loop.

In a strict imperative framework such as the IO monad (and The same idea is applicable to graphs. Instead of expressing
most imperative languages), no value could be returned un- an algorithm as part of a depth- rst traversal, it is possible
til the whole of the list was traversed. Using lazy sequences, to imagine a decomposition similar to that used for many
however, this is not the case. If only the head of the list is tree algorithms. First, the graph is traversed to produce arequired then very little of the computation is performed: depth- rst spanning forest (not all the nodes may be reachthe variable is allocated and initialised, it is read, and the able from the start node), and secondly the forest is tralist returned with that value in the head. If even less is re- versed to compute the required information. Again, this isquired, merely whether the nal list is empty for example, only practicable if the forest is produced on demand, as it isthen the variable is not even allocated as only xs needs to consumed.
be examined in order to give the structure of ys.
A forest is a list of general trees, each tree consisting of a
As we said above, this example is usually written in a purely node with a value, together with a forest of sub-trees.
functional style. It is important, however, that the same
behaviour may be obtained even when state is used: re- type Forest a = [Tree a]
expressing the algorithm within the state monad need not data Tree a = Node a (Forest a)change its semantics.
The next example is quite di erent in that its use of state 3.5.2 Representing Graphs
is crucial to obtaining linear eciency.
There are a number of ways to represent (directed) graphs.
Becausewe want to be explicit about sharing, we repre3.5 Depth First Searchsent graphs by adjacency lists. We use a standard Haskell
array indexed by vertices, each element being
How can we implement depth rst search of a graph e- a(monolithic)
list
of
the
verticesreachable in one step from that vertex.
ciently (that is, 0 (V + E ) where V is the number of vertices, and E the number of edges), while still retaining the One way to build such a graph is from an association list
usual expressiveness and exibility a orded by lazy func- of vertices representing the (directed) edges, together withtional languages? This problem was the motivating appli- a pair of verticies indicating the range of valid vertices3 .
cation for this work on lazy imperative actions, and we describe it in some detail here.
type Graph = Array Vertex [Vertex]

3.5.1 Decomposing Graph Algorithms

type Vertex = Int
out :: Graph -> Vertex -> [Vertex]
out g v = g ! v

One major shortcoming of graph algorithms which rely on
depth- rst search (DFS) is that they are presented dynam->
ically, within the process of performing the search. This buildG :: (Vertex,Vertex)[Assoc Vertex Vertex] -> Graphmeans that reasoning about the results of the search depend buildG is es
on tracing the computation dynamically. Furthermore, as= accumArray (flip (:)) [] is es
the code for a particular algorithm is mixed in with thetraversal code DFS code is largely unreusable.
verticesG g = [low..high]where (low,high) = bounds g
The same may be said for many implementations of tree
algorithms, but in lazy functional languages it is common
to express many tree traversal problems rst by a attening This representation takes a linear amount of space with reof the tree into a list, and then by traversing the list. The spect to the size of the graph i.e. the sum of the number ofattening is performed using one of a variety of standard vertices and number of edges. Access to each list of edges
functions (preorder, postorder etc.), and the list processing takes constant time.
likewise is often de ned in terms of standard components.
Complex algorithms can often be expressed as the composi- Note that as the graph is represented as a purely functionaltion of well-understood simpler components. The intermedi- value, it will not be subject to imperative actions and, in
ate list provides a channel of communication between these particular, will not be altered in any way by the depth rst
standard components. This technique is particularly viable search. We may pass the same graph around and freely
if the list may be consumed as it is produced, otherwise a perform many separate searches on it if we wish.
large intermediate structure is created. The \co-routining" 3 Vertex does not have to be Int as above, but only needs to be in
the Haskell index class Ix.
behaviour of lazy evaluation is able to do this.

dfs:: Graph -> [Vertex] -> [Tree Vertex]

dfs g vs = newSeq {marks <- newArr (bounds g) False;
search vswhere search []= return []search (v:vs) = {visited <- readArr marks v;
if visited thensearch vs
else{writeArr marks v True;as <- search (out g v);
bs <- search vs;return ((Node v as) : bs)}}}

Figure 2: Lazy Depth First Search

3.5.3 Depth First Searchthat sequence operations are not necessarily strict: the only
imperative actions that are performed are those required
Given the standard von Neumann model, it seems impos- by data dependency (including retaining the same relative
sible to produce a linear time depth rst search without linear order).
using some element of update-in-place. However, there is The de nition of depth rst search is given in Figure 2. The
only one place in which this is required, namely in setting function dfs is given a list of vertices to search (this is usefula mark whenever a particular node has been visited. Of- for a number of algorithms), and begins with the rst. Onceten this mark variable is de ned to be an extra eld in the thehas been searched, following all the edges from theoriginal graph, but there are a couple of related reasons vertex,rstandthe descendents of these, etc., the rest of the
why this is undesirable. First, the process of performing a vertices are all
explored.
search has a side e ect on the graph, and this may need to
be explicitly removed before another search can commence. Each (recursive) call of search returns a forest. The call
Secondly, the component of the algorithm which is necessar- search (out g v) which is given the edges leading from v
ily imperative is not identi ed as such, but rather is mixed produces a forest which is built into a tree with v at the
root|all these nodes are reachable from v. The second
up with the rest of the data.
recursive call (search vs) produces a forest of those vertices
An alternative is to have an array of marks, one for each notreachable from v and not previously visited. The tree
vertex. At the start of a search we will allocate a new ar- rooted
v is added to the front of this forest giving the
ray initialised everywhere to False, and make it available completeat depthrst forest.
for reference and update throughout the search. Once thesearch is completed the array may be discarded.
The operations on updatable arrays correspond to those on 3.5.4 Exploring the Forest
variables:
We will give two examples of the use of dfs. The rst detects
thepresence of cycles in a graph, and the second identi es
newArr :: (Ix ix) =>strongly-connectedcomponents.
(ix,ix) -> ele -> Seq (ArrRef ix ele)
readArr :: (Ix ix) =>ArrRef ix ele -> ix -> Seq ele

Detecting Cycles

Traditionally, in order to nd whether a graph contains acycle, a depth rst traversal is performed looking for backedges (edges up to a predecessor in the particular depth rst
writeArr :: (Ix ix) =>tree). As soon as a back edge is found the search is stopped.
ArrRef ix ele -> ix -> ele -> Seq ()The same e ect is obtained using the function dfs. We conThe only way a value may be obtained from an array ref- struct a depth- rst forest from the graph, and then traverse
erence is by using the sequence operations. Again we stress this forest looking for back edges (we need to refer to theoriginal graph to obtain these edges). We can express forest. map postorder . dfs g) [low..high]traversal by mapping a tree-traversal down the list of trees. whereg = buildG (low,high) edges
Thus we de ne a tree traversal function, treeCycle say,g' = buildG (low,high) (map switch edges)
which takes a graph and a sub-tree of the graph. It traverses
switch (v:=w) = (w:=v)
the tree and returns True as soon as it spots a back edgein the original graph, otherwise it continues to traverse the postorder (Node a ts)
rest of the tree, and eventually returns False.
= concat (map postorder ts) ++ [a]Assuming this, the cycle-detection program is simply,
We have seen two examples of using dfs. Many other DFS
cycle g = or (map (treeCycle g)based algorithms can be implemented with similar ease.
(dfs g (verticesG)))

As soon as a tree is found for which the graph has a back 4 Implementing Lazy Stateedge, the or function returns True, discarding the rest of
the forest which is therefore never produced. Furthermore,assuming the data dependency of the tree traversal matches Can lazy state be implemented safely and eciently? By
that of the DFS generation (left branches rst) then only safely we mean guaranteeing that the relative ordering of
the portion of each DFS tree that is actually traversed will imperative actions remains unchanged, and by eciently
we mean using true destructive update to obtain constantbe produced.
time update and access.
Thus we have taken full advantage of lazy-evaluation's ability to provide dynamic control between separate functions: It turns out that not only is the answer yes, but that the imwithout lazy state it would not have been possible to de- plementation is surprisingly easy and can be done at source
couple the traversal of the graph with its mark bits, from level within Glasgow Haskell. Again we start with a review
the detection of back edges, while still retaining the ability of the current implementation of IO.
to halt the DFS as soon as a back edge is found.

Strongly-Connected Components

4.1 Implementation of IO

To demonstrate the exibility of dfs we provide a second
IO type constructor abstractly.
example of its use, this time the strongly connected com- So far we have viewed the
5.
Now
we
see
its
de
nitionponents algorithm due to Kosaraju in 1978 (unpublished)[Sha81]. This example does not take particular advantageof laziness, but does show a reuse the DFS code.
type IO a= World# -> IORes adata IORes a = MkIORes a World#
For the purposes of this algorithm, we originally specify agraph as a pair of bounds for the vertices (low and high),
together with a list of edges. The algorithm performs a Elements of type IO a are functions which take a world
depth rst search of the graph, generating a forest of ver- token (of type World#) and return a pair of values, the rst
tices. This is attened to a list (using postorder and then of type a, the second a new world token.
reversing the list) which is used as the seed order for a sec- Here World# is an unboxed data type [PL91]. The # sux is
ond depth rst search, this time of the reversed graph. Each a lexical convention only with no semantic content, but untree within the resulting depth rst forest corresponds to a boxed types are very di erent beasts from normal types. In
strongly connected component. We squash each into a list particular, unboxed types have no bottom element, so canof vertices. The complete implementation is given below4. not be unde ned. Consequently, any computation involving
elements of unboxed values has to produce the value explicscc :: (Vertex,Vertex)->
itly, before the next stage of the computation may proceed.
[Assoc Vertex Vertex] -> [[Vertex]]
The bene t of using these types is that they expose to thecompiler issues both of data representation and of evaluascc (low,high) edges
tion order, without leaving the purely functional framework.
= (map postorder . dfs g' . reverse . concat
The fact that the world is unboxed forces thenIO to be strict
4 The implementation of postorder is not actually linear because ofin the world token:

repeated appends, but it may be converted by standard compilation
5 The Glasgow Haskell compileris currentlystill under development,
techniques. We have not done so here as it is a little less clear thanso actual names may be subject to changes.
the naive version, and not relevant to our main interest.

returnIO x w# = MkIORes x w#
thenIO m k w# = case (m w#) of
MkIORes a v# -> k a v#

we adopt here is for each state thread to have its own unique

identi er, and for all operations on state-references to checkthat the reference is being used within the correct world.

which in turn forces all the imperative actions speci ed by data World= MkWorld WorldToken World#
to be performed before k is evaluated.
type WorldToken = Int
The only truly primitive IO operation is ccall which, once
applied to the world token, is implemented by the relevant Whenever an new imperative thread is created, a state token(of type World) will be created, having a unique world token
C call.
number.
There are, of course, some common C accesses which areprovided within the standard IO prelude. These include
operations for allocating, reading from, and writing to, ar- 4.3 Independent Threads
rays. We use these in Section 4.4.
Implementing an independent thread comes down to implementing
newSeq. This could be done by de ning it as a
4.2 Boxing the Worldprimitive within the compiler, and arguably that is the corplace. Nonetheless, we can obtain some useful insightSo far we have left the nature of the world token type World# rect
bydening it at the \system programmer level" Haskell.
unspeci ed. In fact, the only part of the compiler whichknows the de nition on World# is the code generator. Ev- The IO monad provides a (potentially dangerous) primitive
erything else views it as an abstract data type (albeit un- value world# representing the world. We will use this asboxed), representing the total state of the world. Only the the world token for the thread. However, we also need tocode generator takes advantage of the fact that the real ex- generate a unique identi er. The problem is well known: it
ternal world may be used, and so instantiates World# to the is just gensym.
one point type.
Again, we could implement gensym using slightly dirty
For sequences, we want a little more information to be con- tricks with the dangerous performIO. Interestingly, howtained in the world token. For a start it must be boxed: ever, Odersky has recently shown that the lambda calculus
in the IO monad, the world token is passed around as an may be safely extended with a gensym operator [Ode93].
unboxed value, and the typechecker ensures that such un- The term  t :e introduces a new name t within e . The only
boxed arguments are only ever used in strict computations, operation provided on names is equality. The resulting calthus forcing imperative actions in the IO monad to occur culus is Church-Rosser.
immediately. Boxing the world token means that rather The concrete syntax Odersky proposes for  t :e isthan passing around a token (in e ect, granting permission new t -> e. As this provides exactly what we want, we
to perform an imperative action), we pass pointers to sus- will adopt his syntax.
pended computations which, when evaluated, yield such a
token. It is this that allows us to de ne the lazy sequencer
newSeq :: Seq a -> abind.
newSeq m = fst (new t -> m (MkWorld t world#))
However, we want more than this. The philosophy behindsequences is that they run in their own local state, independent of any other computations, whether state-based 4.4 Arrays
or purely functional. We must ensure, therefore, that thesequence operations we provide may only be used in this In order to implement arrays we use the primitive operations
way. Cross references between supposedly independent supplied in Glasgow Haskell. The detail of this does notstate threads must be banned. Otherwise the result of a need to be understood merely to appreciate what is goingprogram could depend on the order of evaluation|the very on. The implementation is given in Figure 3.
thing we are trying to avoid.
perform any array operation, we pattern match against
The best solution to this is almost certainly a stronger type To
thestructure of the state token. As usual the forces thesystem, perhaps like the e ects system [TJ92]. This would computations
ning that value to be performed. Heredetermine that no supposedly pure calculation made refer- this has the e deectof forcing all previous imperative actions
ence to anything other than its own internal state.
to be performed, as the token is only available after the
However, in the absence of such an extension, the solution appropriate state changes have occurred.

mdata ArrRef ix ele = MkArrRef WorldToken (ix,ix) (MutArr# ele)
newArr:: (Ix ix) => (ix,ix) -> ele ->Seq (ArrRef ix ele)
readArr :: (Ix ix) => ArrRef ix ele -> ix ->Seq elewriteArr :: (Ix ix) => ArrRef ix ele -> ix -> ele -> Seq ()newArr ixs@(ix_start, ix_end) init (MkWorld w v#)= case ((index ixs ix_end) + 1) of
MkInt n# -> case (newArr# n# init) v# of
MkSeqRMutArr# arr# new# -> (MkArrRef w ixs arr#, MkWorld w new#)readArr (MkArrRef t ixs arr#) n (MkWorld w v#)= worldCheck t w (case index ixs n of
MkInt n# -> case (rdArr# n# arr#) v# of
MkSeqR r new# -> (r, MkWorld w new#) )writeArr (MkArrRef t ixs arr#) n ele (MkWorld w v#)= worldCheck t w (case index ixs n of
MkInt n# -> case (wrArr# n# arr# ele) v# of
MkSeqR r new# -> ((), MkWorld w new#) )worldCheck :: WorldToken -> WorldToken -> a -> aworldCheck t w val | t==w = val| True = error "Illegal State Access"Figure 3: Array Operations

type Var a = ArrRef Int a
newVar:: a -> Seq (Var a)
readVar :: Var a -> Seq awriteVar :: Var a -> a -> Seq ()newVar init
= newArr (0,0) init
readVar v= readArr v 0
writeVar v val = writeArr v 0 val

Figure 4: Variable Operations

In the case of newArray, the size of the array is computed 5 Conclusion
using the standard Ix class method index which maps arbitrary Ix types onto the integers. We then call the prim- This paper may be viewed as providing another step in imitive IO operation newArr# providing it with the appropri- proving the interface between the functional and imperaate world token. This returns an unboxed array together
worlds, as here we allow data dependency to deterwith a new world token. The rst is packaged up with tiveminewhich imperative actions are performed and which are
the MkArrRef constructor, and the second with the current delayed
6.
world identi er using MkWorld.
has two signi cant advantages: the rst is semanNotice that the current world identi er is also packaged with Thistic
andsecond practical. The semantic advantage isthe array, so that each array is tagged with an identi er a purelythe
functional
program may be re-expressed in terms
representing the world to which it belongs.
of the state monad without changing its semantics. The
When an array is read, again the state token is forced. Then practical advantage is that the power of lazy evaluation for
the world token number built into the array reference is decoupling calculation and control may be used even acrosschecked to con rm that the array was created within the functions which used internal state.
same world in which it is now being accessed. It is this check This paper builds directly on top of the IO work at Glas(and the corresponding check in writeArr) which ensures gow
as reported by Peyton Jones and Wadler [PW93], andthat references cannot pass between apparently independent summarised
Section 2. There are also strong similarities
threads. If ever any other primitive operations on Seq are with the varinworkof Odersky, Rabin and Hudak [ORH93],
provided then a similar check should be included.
which itself was in uenced by Swarup, Reddy and Ireland
If the check is successful, then again primitive IO opera- [SRI91]. Like Peyton Jones and Wadler, var provides only
tions are used to read the array, and the result packaged for strict imperative actions: no purely functional result isreturned until the structure and content of the state is reappropriately. Writing to the array is comparable.
Following ML, we implement variables as arrays with a sin- solved.
One surprising aspect of this work is that it may all be
gle element. The detail is given in Figure 4.
implemented at source level within Glasgow Haskell (albeit
at a level typically reserved for systems programming). In
particular, no changes to the compiler were required. This
provides considerable evidence for the power and exibility
4.5 Converting IO to Seqof the built in IO monad and unboxed values.
A number of obvious developments present themselves. AlThere is a fair degree of mess within the de nitions of the ready the Var type allows all the exibility of pointers: aarray primitives. Much of this can often be encapsulated in value of type Var (Var Int) is a pointer to an integer varithe following generic conversion function.
able, so it makes sense to augment the variables and arrayswith unique tags to allow for pointer equality to be de ned.
Thus the instance of == on Var would simply compare the
cnvIOToSeq :: IO a -> Seq atags of the variables and no more.
cnvIOToSeq m (MkWorld w v#)
Sometimes, data-dependency requires that all the impera= case (m v#) of
tive
actions within a state thread be performed before any
MkIORes r new# -> (r, MkWorld w new#)result is returned. In this case it makes sense to performthe operations strictly rather than lazily. This corresponds
A partial application of cnvIOToSeq to an IO operation m to replacing lazy function application with strict applicayields a function expecting a value of type World. When tion when the function is provably strict. In this case it is
the results of the operation are required, the World value achieved by replacing the `bind` combinator with a version
is forced (the pattern matching demands to view the outer 6
However, it is important to recall that when imperative actions
constructor). As before, this may provoke a cascade of ear- are forced,
occur in the same order in which they were speci ed.
lier computations to be performed, many having imperative There may they
be room for the clever work found in imperative language
e ects. When at last the World token is visible, all previous implementations whereby imperative actions are reordered according
imperative e ects will have been performed. Now the IO to actual dependency, but that is beyond the scope of the work here.
Currently, for example, if after specifying a computation which setsaction m is applied to the world token, its imperative e ect up
a mutable array, only one element is read, then all the preceeding
performed, and an IO result is returned. The components imperative
actions will be performed, not merely those required toof this are extracted, and the new world token is boxed.
determine the particular element value.

which performs a case analysis, rather than constructing a [Ode93] M.Odersky, Making Gensym Safe for Functional
Programming, Dept. of Computer Science, Yale
let binding. It should be easy to obtain the necessary inUniv, unpublished.
formation from existing strictness analysers.
[PL91] S.Peyton Jones and J.Launchbury, Unboxed Values as First Class Citizens, proc. ACM Functional
6 Acknowledgements
ProgrammingLanguages and Computer Architecture, Boston, LNCS 523, S-V, 1991.
I would like to thank Andy Gill, David King, Will Partain,
Simon Peyton Jones and Phil Wadler for the discussions [PW93] S.Peyton Jones and P.Wadler, Imperative Functional Programming, proc. ACM Principles
we have had about this work. Simon in particular providedofProgramming Languages 93, Charlston,
many incisive observations which improved both the content
N.Carolina,
1993.
and presentation immensely. The approach to graph algorithms brie y described here is the result of joint research [Sha81] Sharir, A Strong Connectivity Algorithm & its Apwith David King.
plication in Data Flow Analysis, in Computers
and Mathematics with Applications 7:1, pp. 6772, 1981.
References[SRI91] V.Swarup, U.Reddy and E.Ireland, Assignments
for Applicative Languages, proc. FPCA 91, LNCS
[Hug89] J.Hughes, Why Functional Programming Matters,
523, London, 1991.
The Computer Journal, Vol 32, No. 2, CUP, April
1989.
[TJ92] J-P.Talpin and P.Jouvelot, Polymorphic type, region and e ect inference, Jounal of Functional[Mog89] E.Moggi, Computational Lambda Calculus andProgramming,
Vol 2, Part 3, CUP, July 1992.
Monads, proc. IEEE. Logic in Computer Science,
Asilomar, California, 1989.
[Wad92] P.Wadler, Comprehending Monads, MSCS, vol 2,
pp 461-493, CUP, 1992.
[ORH93] M.Odersky, D.Rabin and P.Hudak, Call by Name,
Assignment, and the Lambda Calculus, proc.
ACM Principles of Programming Languages 93,
Charlston, N.Carolina, 1993.

View publication stats