The BOHM machine

Asperti, Giovannetti, and Naletto are still working on the implementation of Lamping's graph reduction algorithm for optimal reduction of functional languages (the Bologna Optimal Higher-order Machine [AG98]). We have almost completed a new ``light'' version, essentially inspired by Girard's Light Linear Logic. The light version provides a much sharper syntactical control over the shape of sharing graphs than that provided by the rough encoding of intuitionistic implication into linear logic, with a significant impact on the efficiency of the reduction.

BOHM is a simple interpreter written in C, and it runs on most systems having a C compiler, including Personal Computers. BOHM's source language constitutes the full core of a typical (dynamically-typed) lazy functional language, including a few data-types, conditional expressions, recursive values and multiple recursion and lazy pattern matching.

BOHM's performance has been compared with two standard and fully developed implementations of functional languages: Caml-light (Rocquencourt, France) and Yale Haskell (UK). It is always comparable with that of Yale Haskell (i.e. approximately ten time slower than Caml-light), while it can run surprisingly faster on many interesting examples. Two typical cases are the incremental modification of arrays represented as functions from indices to values, and the direct evaluation of Denotational Semantics for imperative languages.

[[BOHM]] Asperti, A., Giovannetti, C., Naletto, A.: ``The Bologna Optimal Higher-order Machine''. Internal Report UBLCS-95-9, Laboratory for Computer Science, University of Bologna, Italy.

[[AG98]] A. Asperti, S. Guerrini The Optimal Implementation of Functional Programming Languages. To appear in the ``Cambridge Tracts in Theoretical Computer Science'' Series, Cambridge University Press, 1998.