oc-FP: An OCAML implementation of John Backus’ FP system

Christophe Deleuze

1 John Backus’ FP system

In its 1977 ACM Turing award lecture [1], John Backus presents a functional style of programming, which he calls “FP”. He explains how classical imperative programming languages suffer from what he calls “the Von Neumann bottleneck” and describes a programming style based on combining functions through functional forms. An excerpt from the abstract is:

Functional programs deal with structured data, are often nonrepetitive and nonrecursive, are hierarchically constructed, do not name their arguments, and do not require the complex machinery of procedure declarations to become generally applicable.

Moreover, such programs are actually objects of an algebra whose composition laws are functional forms. Various properties on programs can thus be proved by use of college algebra.

I won’t detail these points, these are clearly explained in Backus’ paper, which is really worth a read for anyone with an interest on programming. The first few sections are particularly enlighting and easy to follow.

In addition to the FP system, Backus describes “FFP systems” similar to FP systems but where in addition to new functions, new functional forms can also be defined. He then describes a new class a computing systems that uses the functional style both in its programming language and in its state transition rules, wich he calls “applicative state transition” (AST) systems.

This manual describes “oc-fp” which is an implementation of FP in the Objective Caml^{1} language. This is a preliminary, wildly incomplete implementation. In particular, it doesn’t include the FFP and AST functionalities and may lack some primitive functions.

oc-fp is distributed under the General Public Licence (GPL)^{2}.

2 User manual

Refer to Backus’ paper (which you can find online [1]) for the language description.

Some syntax details differ from Backus’ original description, mainly because of lack of the proper symbol in the ascii character set. These differences are listed in table 1. Note that ÷ is a character from the isolatin1 set. Emacs users can compose it with the C-x 8 / / key sequence.

A few more toplevel commands are available, these are:

Show name show current definition bound to name, or all definitions if name is “all”.

Undef name remove definition bound to name.

Quit quit the system.

Save "file" save current definitions to file.

Load "file" load definitions in file.

Comments begin with the character ’#’ and extend to the end of line.

1http://caml.inria.fr

2http://www.gnu.org/gpl.html http://christophe.deleuze.free.fr/D/fp.html  April 2, 2004

form or function name Backus’ syntax  our syntax
apply to all  α  @
division  ÷  div or ÷
select n^{th}  n  ns
reverse select  nr  nr
composition  f ∘ g ∘ ... ∘ h f o g o ...  o h
condition  p → f; g  p -> f; g
construction  [f,g,...,h]  [ f,g,...,h ]
constant  n̄  ~n
definition  Def f ≡ defs  Def f = defs

Table 1: Syntax differences with original Backus description

3 Installation

oc-FP is available as a gzipped tar of OCaml source files on oc-FP home page^{3}. Compiling from sources requires Objective Caml 3.06 or later.

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, 21(8):613–641, August 1978.

   http://www.stanford.edu/class/cs242/readings/backus.pdf

3http://christophe.deleuze.free.fr/D/fp.html