When is a Functional Program Not a Functional Program?

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationProceedings of the Fourth ACM SIGPLAN International Conference on Functional Programming
Place of PublicationNew York, NY, USA
Number of pages7
ISBN (Print)1-58113-111-9
Publication statusPublished - 1999


Dive into the research topics of 'When is a Functional Program Not a Functional Program?'. Together they form a unique fingerprint.

Cite this