Technical reports

The implementation of functional languages using custom hardware

William Robert Stoye

December 1985, 151 pages

This technical report is based on a dissertation submitted May 1985 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Magdalene College.

DOI: 10.48456/tr-81

Abstract

In recent years functional programmers have produced a great many good ideas but few results. While the use of functional languages has been enthusiastically advocated, few real application areas have been tackled and so the functional programmer’s views and ideas are met with suspicion.

The prime cause of this state of affairs is the lack of widely available, solid implementations of functional languages. This in turn stems from two major causes: (1) Our understanding of implementation techniques was very poor only a few years ago, and so any implementation that is “mature” is also likely to be unuseably slow. (2) While functional languages are excellent for expressing algorithms, there is still considerable debate in the functional programming community over the way in which input and output operations should be represented to the programmer. Without clear guiding principles implementors have tended to produce ad-hoc, inadequate solutions.

My research is concerned with strengthening the case for functional programming. To this end I constructed a specialised processor, called SKIM, which could evaluate functional programs quickly. This allowed experimentation with various implementation methods, and provided a high performance implementation with which to experiment with writing large functional programs.

This thesis describes the resulting work and includes the following new results: (1) Details of a practical turner-style combinator reduction implementation featuring greatly improved storage use compared with previous methods. (2) An implementation of Kennaway’s director string idea that further enhances performance and increases understanding of a variety of reduction strategies. (3) Comprehensive suggestions concerning the representation of input, output, and nondeterministic tasks using functional languages, and the writing of operating systems. Details of the implementation of these suggestions developed on SKIM. (4) A number of observations concerning fuctional programming in general based on considerable practical experience.

Full text

PDF (7.2 MB)

BibTeX record

@TechReport{UCAM-CL-TR-81,
  author =	 {Stoye, William Robert},
  title = 	 {{The implementation of functional languages using custom
         	   hardware}},
  year = 	 1985,
  month = 	 dec,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-81.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-81},
  number = 	 {UCAM-CL-TR-81}
}