Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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. Intriguingly, this parametricity requires the provision of a (single) constant with a rank-2 polymorphic type.

REFERENCES

• 1: Erik Barendsen , Sjaak Smetsers, Conventional and Uniqueness Typing in Graph Rewrite Systems, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.41-51, December 15-17, 1993
• 2: David K. Gifford , John M. Lucassen, Integrating functional and imperative programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.28-38, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319848]
• 3: J Launchbury{June 1993}, "Lazy imperative programming,' in Proc A CM Sigplan Workshop on State in Programming Languages, Copenhagen (available as YALEU/DCS/RR- 968, Yale University), pp46-56.
• 4: J Launchbury Lc SL Peyton Jones{Feb 1994}, "Lazy functional state threads," Technical report FP- 94-05, Department of Computing Science, University of Glasgow (FTP:ftp. dcs. glasgow, ac. uk: pub/glasgow-fp/tech-report s / FP-94-05: sta~e, ps. Z).
• 5: Nancy McCracken, The typechecking of programs with implicit type structure., Proc. of the international symposium on Semantics of data types, p.301-315, July 1984, Sophia-Antipolis, France
• 6: John C. Mitchell , Albert R. Meyer, Second-Order Logical Relations (Extended Abstract), Proceedings of the Conference on Logic of Programs, p.225-236, June 17-19, 1985
• 7: Rishiyur Nikhil{March 1988}, "Id Reference Manual," Lab for Computer Sci, MIT.
• 8: Martin Odersky , Dan Rabin , Paul Hudak, Call by name, assignment, and the lambda calculus, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.43-56, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158521]
• 9: Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
• 10: Simon L. Peyton Jones , John Launchbury, Unboxed values as first class citizens in a non-strict functional language, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.636-666, June 1991, Cambridge, Massachusetts, United States
• 11: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 12: Carl G. Ponder , Patrick McGeer , Anthony P-C. Ng, Are applicative languages inefficient?, ACM SIGPLAN Notices, v.23 n.6, p.135-139, June, 1988 [doi>10.1145/44546.44559]
• 13: David A. Schmidt, Detecting global variables in denotational specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.299-310, April 1985 [doi>10.1145/3318.3323]
• 14: Vipin Swarup , Uday S. Reddy , Evan Ireland, Assignments for applicative languages, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.192-214, June 1991, Cambridge, Massachusetts, United States
• 15: Mads Tofte, Type inference for polymorphic references, Information and Computation, v.89 n.1, p.1-34, Nov. 1990 [doi>10.1016/0890-5401(90)90018-D]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Algorithms, Languages