John Longley
ABSTRACT
In an impure functional language, there are programs whose behaviour is completely functional (in that they behave extensionally on inputs), but the functions they compute cannot be written in the purely functional fragment of the language. That is, the class of programs with functional behaviour is more expressive than the usual class of pure functional programs. In this paper we introduce this extended class of "functional" programs by means of examples in Standard ML, and explore what they might have to offer to programmers and language implementors.After reviewing some theoretical background, we present some examples of functions of the above kind, and discuss how they may be implemented. We then consider two possible programming applications for these functions: the implementation of a search algorithm, and an algorithm for exact real-number integration. We discuss the advantages and limitations of this style of programming relative to other approaches. We also consider the increased scope for compiler optimizations that these functions would offer.
- 1.A. Bucciaxelli and T. Ehrhard. Sequentiality and strong stability. In Proc. 6th Annual Symposium on Logic in Computer Science, pages 138-145. IEE;E, 1991.Google Scholar
- 2.T. Ehrhard. Projecting sequential algorithms on strongly stable functions. Annals of Pure and Applied Logic, 77:201-244, 1996.Google ScholarCross Ref
- 3.S. Peyton Jones and J. Hughes (eds.). Report on the programming language Haskell 98. Available electronically from www.haskell.org, February 1999.Google Scholar
- 4.J.R. Longley. The sequentially realizable functionals. Technical Report ECS-LFCS-98-402: Department of Computer Science, University of Edinburgh, 1998. Submitted to Annals of Pure and Applied Logic.Google Scholar
- 5.J.R. Longley. When is a functional program not a functional program?: a walkthrough introduction to the sequentially realizable functionals. ML source file, available from http://www, dcs. ed.ac .uk/hom/jrl/, 1998.Google Scholar
- 6.R. MiMer, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML: revised 1997. MIT Press, 1997. Google ScholarDigital Library
- 7.J. van Oosten. A combinatory algebra for sequential functionals of finite type. Technical Report 996, University of Utrecht, 1997. To appear in Proc. Logic Colloquium, Leeds.Google Scholar
- 8.S. Peyton Jones and S. Marlow. Stretching the storage manager: weak pointers and stable names in Haskell. Draft paper, 1999.Google Scholar
- 9.G.D. Plotldn. LCF considered as a programming language. Theoretical Computer Science, 5:223-255, 1977.Google ScholarCross Ref
- 10.D.S. Scott. A type-theoretical alternative to ISWIM, CUCH, OWHY. Theoretical Comp. $ci. , 121:411-440, 1993. First written in 1969 and widely circulated in unpublished form since then. Google ScholarDigital Library
- 11.A.K. Simpson. Lazy functional algorithms for exact real functionals. In Mathematical Foundations of Computer Science, pages 456-464. Springer LNCS 1450, 1998. Google ScholarDigital Library
Index Terms
- When is a functional program not a functional program?
Recommendations
When is a functional program not a functional program?
In an impure functional language, there are programs whose behaviour is completely functional (in that they behave extensionally on inputs), but the functions they compute cannot be written in the purely functional fragment of the language. That is, the ...
Language and program design for functional dependencies
HASKELL '08Eight years ago, functional dependencies, a concept from the theory of relational databases, were proposed as a mechanism for avoiding common problems with multiple parameter type classes in Haskell. In this context, functional dependencies give ...
Comments