The implementation of functional languages on an object-oriented architecture

  • Mohammed Khan

    Student thesis: Doctoral Thesis


    This thesis concerns the investigation of different implementation strategies for functional languages on a novel platform, the Rekursiv, that provides hardware support for an object- oriented language (Lingo) which was used as the implementation language for this work.

    The objective is to evaluate the performance of two different implementation techniques - fixed combinators and supercombinators - for functional languages by interpreting the functional program in two object-oriented styles with different representations for combinators on two different environments:

    • A purpose-built object-oriented machine; Harland’s Rekursiv.
    • A RISC machine; an IBM RS6000 running a Smalltalk-80 interpreter.

    Interpreters are implemented in Smalltalk (for the RS6000) and Lingo (for the Rekursiv) for an applicative language Alcal (a A-calculus language). The interpreters are then used to generate a combinator graph using the fixed SKI set of combinators proposed by Turner, and also Hughes-style program specific supercombinators (Alifting) which are not limited to a fixed set of primitive combinators.

    A number of experiments are conducted, based on the implementation of the lazy functional language, Alcal, on the RS6000 in Smalltalk-80 and on the Rekursiv architecture in Lingo. Lingo and Smalltalk allow the creation of objects that contain executable statements, so an object-oriented ‘active graph’ implementation is proposed.

    Using these prototypes, the performance of the Rekursiv implementation against the RISC implementation has been evaluated. This includes the proportion of time spent on overhead activities and a statistical performance analysis of the benchmark results to analyse some of the claims made by the designer of the Rekursiv architecture.

    Relative to a baseline benchmark written in C, the implementations on the Rekursiv are found to be several times faster than those on the RISC machine. An analysis of variance demonstrates a more subtle interplay between benchmark programs, implementation techniques, representation of combinators and hardware platform.
    Date of AwardMar 1993
    Original languageEnglish

    Cite this