| Print dvi | usdvi |
| Download tgz |

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 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  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.

form or function name Backus' syntax our syntax
apply to all a @
division div or
select nth 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

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 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.

3  Installation

oc-FP is available as a gzipped tar of OCaml source files from the top right ``Download'' link on this page. Compiling from sources requires Objective Caml 3.06 or later.


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. [ url ]