The Illinois functional programming interpreter

ABSTRACT

The Illinois Functional Programming (IFP) language is a modified version of Backus' FP(1). IFP has the same side-effect free combinator style of Backus FP, while introducing an ALGOL-like syntax and structure. While IFP superficially appears to be an inefficient language to execute, its simplicity makes it quick to interpret. Functions are always monadic and there are no variable or parameter names. Furthermore, combinator-style languages allow common housekeeping operations to be condensed into efficient machine-language primitives.By reference-counting, the interpreter can often convert call-by-value to destructive call-by-reference while preserving referential transparency. The interpreter has an expression cache which can improve the asymptotic time of some combinatorial functions. IFP function definitions are stored as UNIX files, so much of UNIX's functionality is immediately borrowed into the IFP environment, e.g. ls, more, and grep.Benchmarks indicate that IFP is an order of magnitude faster than Berkeley FP[2], and is competitive with interpreted von-Neumann languages such as BASIC. The interpreter can parallel process on shared-memory multiprocessors, e.g. the Encore Multimax. IFP currently runs on machines as varied as the IBM PC, VAX, and CRAY-XMP.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: 2. Baden, Scott. Berkeley FP User's Manual, Rev. 4.1. UNIX Programmers Manual (July 27, 1983).
• 3: 3. Robison, Arch D. Illinois Functional Programming: A Tutorial. BYTE (February 1987) vol. 12, 2, pp. 115-125.
• 4: Kenneth E. Iverson, A programming language, John Wiley & Sons, Inc., New York, NY, 1962
• 5: Ronald G. Loeliger, Threaded Interpretive Languages, McGraw-Hill, Inc., New York, NY, 1981
• 6: 6. Hilden, J. Elimination of Recursive Calls Using a Small Table of "Randomly" Selected Function Values. BIT (1976) vol. 16-1, pp. 60-73.
• 7: Robert M. Keller , M. R. Sleep, Applicative caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.88-108, Jan. 1986 [doi>10.1145/5001.5004]
• 8: 8. Foderaro, John K., Keith L. Sklower and Kevin Layer. The FRANZ LISP Manual. UNIX Programmer's Manual - Supplementary Documents (June 1983).
• 9: 9. Robison, Arch D. A Functional Programming Interpreter. M.S. Thesis, University of Illinois at Urbana-Champaign (January 1987).

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FP
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Interpreters

General Terms:
Design, Languages