Abstract
Some algorithms make critical internal use of updatable state, even though their external specification is purely functional. Based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, named, mutable objects, in the context of a non-strict, purely-functional language. The security of the encapsulation is assured by the type system, using parametricity. The same framework is also used to handle input/output operations (state changes on the external world) and calls to C.
Similar content being viewed by others
References
Arvind, RS Nikhil & KK Pingali [Oct 1989], “I-structures — data structures for parallel computing,”TOPLAS 11, 598–632.
L Augustsson, M Rittri & D Synek [Jan 1994], “On generating unique names,”Journal of Functional Programming 4, 117–123.
E Barendsen & JEW Smetsers [Dec 1993], “Conventional and uniqueness typing in graph rewrite systems,” inProc 13th Conference on the Foundations of Software Technology and Theoretical Computer Science, Springer Verlag LNCS.
PS Barth, RS Nikhil & Arvind [Sept 1991], “M-structures: extending a parallel, non-strict functional language with state,” inFunctional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 538–568.
RS Bird [1984], “Using circular programs to eliminate multiple traversals of data,”Acta Informatica 21, 239–250.
WN Chin [March 1990], “Automatic methods for program transformation,” PhD thesis, Imperial College, London.
DK Gifford & JM Lucassen [Aug 1986], “Integrating functional and imperative programming,” inACM Conference on Lisp and Functional Programming, MIT, ACM, 28–38.
A Gill, J Launchbury & SL Peyton Jones [June 1993], “A short cut to deforestation,” inProc Functional Programming Languages and Computer Architecture, Copenhagen, ACM, 223–232.
CV Hall [June 1994], “Using Hindley-Milner type inference to optimise list representation,” inACM Symposium on Lisp and Functional Programming, Orlando, ACM, 162–172.
P Hancock [1987], “A type checker,” inThe implementation of functional programming languages, SL Peyton Jones, ed., Prentice Hall, 163–182.
John Hughes [Apr 1989], “Why functional programming matters,”The Computer Journal 32, 98–107.
AJ Kfoury [June 1992], “Type reconstruction in finite rank fragments of second-order lambda calculus,”Information and Computation 98, 228–257.
AJ Kfoury & JB Wells [June 1994], “A direct algorithm for type inference in the rank-2 fragment of the second-order lambda calculus,” inACM Symposium on Lisp and Functional Programming, Orlando, ACM, 196–207.
DJ King & J Launchbury [Jan 1995], “Structuring depth-first search algorithms in Haskell,” in21st ACM Symposium on Principles of Programming Languages, San Francisco, ACM.
J Launchbury [June 1993], “Lazy imperative programming,” inProc ACM Sigplan Workshop on State in Programming Languages, Copenhagen (available as YALEU/DCS/RR-968, Yale University), pp46–56.
J Launchbury & SL Peyton Jones [June 1994], “Lazy functional state threads,” inSIGPLAN Symposium on Programming Language Design and Implementation (PLDI'94), Orlando, ACM.
S Marlow & PL Wadler [1993], “Deforestation for higher-order functions,” inFunctional Programming, Glasgow 1992, J Launchbury & PM Sansom, eds., Workshops in Computing, Springer Verlag, 154–165.
NJ McCracken [June 1984], “The typechecking of programs with implicit type structure,” inSemantics of data types, Springer Verlag LNCS 173, 301–315.
R Milner & M Tofte [1990],The definition of Standard ML, MIT Press.
JC Mitchell & AR Meyer [1985], “Second-order logical relations,” inLogics of Programs, R Parikh, ed., Springer Verlag LNCS 193.
E Moggi [June 1989], “Computational lambda calculus and monads,” inLogic in Computer Science, California, IEEE.
Rishiyur Nikhil [March 1988], “Id Reference Manual,” Lab for Computer Science, MIT.
PW O'Hearn & RD Tennent [Jan 1993], “Relational parametricity and local variables,” in20th ACM Symposium on Principles of Programming Languages, Charleston, ACM, 171–184.
M Odersky, D Rabin & P Hudak [Jan 1993], “Call by name, assignment, and the lambda calculus,” in20th ACM Symposium on Principles of Programming Languages, Charleston, ACM, 43–56.
SL Peyton Jones [1987],The Implementation of Functional Programming Languages, Prentice Hall.
SL Peyton Jones [Apr 1992], “Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine,”Journal of Functional Programming 2, 127–202.
SL Peyton Jones & J Launchbury [Sept 1991], “Unboxed values as first class citizens,” inFunctional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 636–666.
SL Peyton Jones & PL Wadler [Jan 1993], “Imperative functional programming,” in20th ACM Symposium on Principles of Programming Languages, Charleston, ACM, 71–84.
CG Ponder, PC McGeer & A P-C Ng [June 1988], “Are applicative languages inefficient?,”SIGPLAN Notices 23, 135–139.
JH Reppy [June 1991], “CML: a higher-order concurrent language,” inACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), ACM.
DA Schmidt [Apr 1985], “Detecting global variables in denotational specifications,”TOPLAS 7, 299–310.
V Swarup, US Reddy & E Ireland [Sept 1991], “Assignments for applicative languages,” inFunctional Programming Languages and Computer Architecture, Boston, Hughes, ed., LNCS 523, Springer Verlag, 192–214.
P Thiemann [1993], “Safe Sequencing of Assignments in Purely Functional Programming Languages,” Tech. Report. Wilhelm-Schickard-Institut WSI-93-i6, Tübingen, Germany.
M Tofte [Nov 1990], “Type inference for polymorphic references,”Information and Computation 89.
PL Wadler [1990], “Deforestation: transforming programs to eliminate trees,”Theoretical Computer Science 73, 231–248.
PL Wadler [1992a], “Comprehending monads,”Mathematical Structures in Computer Science 2, 461–493.
PL Wadler [Jan 1992b], “The essence of functional programming,” inProc Principles of Programming Languages, ACM.
PL Wadler [June 1990], “Comprehending monads,” inProc ACM Conference on Lisp and Functional Programming, Nice, ACM.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Launchbury, J., Peyton Jones, S.L. State in Haskell. LISP and Symbolic Computation 8, 293–341 (1995). https://doi.org/10.1007/BF01018827
Issue Date:
DOI: https://doi.org/10.1007/BF01018827