Technical reports

Implementation and programming techniques for functional languages

Stuart Charles Wray

June 1986, 117 pages

This technical report is based on a dissertation submitted January 1986 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Christ’s College.

DOI: 10.48456/tr-92

Abstract

In this thesis I describe a new method of strictness analysis for lazily evaluated functional languages, and a method of code generation making use of the information provided by this analysis. I also describe techniques for practical programming in lazily evaluated functional languages, based on my experience of writing substantial functional programs.

My new strictness analyser is both faster and more powerful than that of Mycroft. It can be used on any program expressed as super-combinator definitions and it uses the additional classifications absent and dangerous as well as strict and lazy. This analyser assumes that functional arguments to higher order functions are completely lazy.

I describe an extension of my analyser which discovers more strictness in the presence of higher order functions, and I compare this with higher order analysers based on Mycroft’s work. I also describe an extension of my analyser to lazy pairs and discuss strictness analysers for lazy lists.

Strictness analysis brings useful performance improvements for programs running on conventional machines. I have implemented my analyser in a compiler for Ponder, a lazily evaluated functional language with polymorphic typing. Results are given, including the surprising result that higher order strictness analysis is no better than first order strictness analysis for speeding up real programs on conventional machines.

I have written substantial programs in Ponder and describe in some detail the largest of these which is about 2500 lines long. This program is an interactive spreadsheet using a mouse and bitmapped display. I discuss programming techniques and practical problems facing functional languages with illustrative examples from programs I have written.

Full text

PDF (4.4 MB)

BibTeX record

@TechReport{UCAM-CL-TR-92,
  author =	 {Wray, Stuart Charles},
  title = 	 {{Implementation and programming techniques for functional
         	   languages}},
  year = 	 1986,
  month = 	 jun,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-92.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-92},
  number = 	 {UCAM-CL-TR-92}
}