hn-classics/_stories/1992/10794273.md

---
created_at: '2015-12-26T15:17:02.000Z'
title: 'Implementing functional languages: a tutorial (1992)'
url: http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/
author: rspivak
points: 118
story_text: 
comment_text: 
num_comments: 10
story_id: 
story_title: 
story_url: 
parent_id: 
created_at_i: 1451143022
_tags:
- story
- author_rspivak
- story_10794273
objectID: '10794273'
year: 1992

---
[Source](http://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/?from=http%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fum%2Fpeople%2Fsimonpj%2Fpapers%2Fpj-lester-book%2F "Permalink to Implementing functional languages: a tutorial - Microsoft Research")

# Implementing functional languages: a tutorial - Microsoft Research

Try Microsoft Edge A fast and secure browser that's designed for Windows 10 No thanks Get started

This site uses cookies for analytics, personalized content and ads. By continuing to browse this site, you agree to this use. [Learn more][1]

[ ![][2] Microsoft ][3]

Research

* [Microsoft 365][4]
* [Azure][5]
* [Office 365][6]
* [Dynamics 365][7]
* [SQL][8]
* [Windows 10][9]
* More
    * Products & Services
        * [Windows Server][10]
        * [Enterprise Mobility + Security][11]
        * [Power BI][12]
        * [Teams][13]
        * [Visual Studio][14]
        * [Surface for Business][15]
    * Emerging Technologies
        * [AI][16]
        * [Internet of Things][17]
        * [Azure Cognitive Services][18]
        * [Quantum][19]
        * [Research][20]
    * Developer & IT
        * [Docs][21]
        * [TechNet][22]
        * [Developer Network][23]
        * [Windows Dev Center][24]
        * [Windows IT Pro Center][25]
        * [FastTrack][26]
    * Partner
        * [Partner Network][27]
        * [Solution Providers][28]
        * [Partner Center][29]
        * [Cloud Hosting][30]
    * Industries
        * [Education][31]
        * [Financial services][32]
        * [Government][33]
        * [Health][34]
        * [Manufacturing & resources][35]
        * [Retail][36]
    * Other
        * [Security][37]
        * [Licensing][38]
        * [AppSource][39]
        * [Azure Marketplace][40]
        * [Events][41]
    * [View all][42]

[ Research ][43] [Research Home][43]

Research areas

* Intelligence
    * [Artificial Intelligence][44]
    * [Computer vision][45]
    * [Graphics & multimedia][46]
    * [Human-computer interaction][47]
    * [Human language technologies][48]
    * [Search & information retrieval][49]
* Systems
    * [Data visualization, analytics & platform][50]
    * [Hardware, devices & quantum computing][51]
    * [Programming languages & software engineering][52]
    * [Security, privacy & cryptography][53]
    * [Systems & networking][54]
* Theory
    * [Algorithms][55]
    * [Mathematics][56]
* Other Sciences
    * [Ecology & environment][57]
    * [Economics][58]
    * [Medical, health & genomics][59]
    * [Social sciences][60]
    * [Technology for emerging markets][61]

[Products & Downloads][62]

Programs & Events

* [Academic Programs][63]
* [Events & Conferences][64]

[People][65] [Careers][66]

Blogs & Podcasts

* [Microsoft Research Blog][67]
* [The Microsoft Research Podcast][68]
* [The AI Blog][69]

Labs & Locations

* Microsoft Research
    * [MSR AI][70]
    * [Asia Lab (Chinese)][71]
    * [Asia Lab (English)][72]
    * [Cambridge Lab][73]
    * [India Lab][74]
    * [Montreal Lab][75]
    * [New England Lab][76]
    * [New York City Lab][77]
    * [Redmond Lab][78]
* Other labs/locations
    * [Applied Sciences Lab][79]
    * [Advanced Technology Lab Cairo][80]
    * [Quantum][81]
* About
    * [Research at Microsoft][82]

#  Implementing functional languages: a tutorial 

January 1, 1992 

* [ Download PDF ][83]
* [ View Link ][84]
* [ BibTex ][85]

##  Authors 

* SL Peyton Jones 
* DR Lester 
* [Simon Peyton Jones][86]

## Publication Type

Book 

## Book Title

Implementing functional languages: a tutorial 

## Publisher

Prentice Hall 

* [ Abstract ][87]
* [ Related Info ][88]

## Abstract

This book gives a practical approach to understanding implementations of non-strict functional languages using lazy graph reduction. The book is intended to be a source of practical labwork material, to help make functional-language implementations `come alive’, by helping the reader to develop, modify and experiment with some non-trivial compilers.

The unusual aspect of the book is that it is meant to be _executed_ as well as _read_. Rather than merely presenting an abstract description of each implementation technique, we present the code for a complete working prototype of each major method, and then work through a series of improvements to it. All of the code is available in machine-readable form.

## Overview of the book

The principal content of the book is a series of implementations of a small functional language called the _Core language_. The Core language is designed to be as small as possible, so that it is easy to implement, but still rich enough to allow modern non-strict functional languages to be translated into it without losing efficiency. It is described in detail in Chapter 1, in which we also develop a parser and pretty-printer for the Core language.

Appendix B contains a selection of Core-language programs for use as test programs thoughout the book.

The main body of the book consists of four distinct implementations of the Core language.

* Chapter 2 describes the most direct implementation, based on _template instantiation_.
* Chapter 3 introduces the _G-machine_, and shows how to compile the program to sequences of instructions (G-code) which can be further translated to machine code.
* Chapter 4 repeats the same exercise for a different abstract machine, the _Three Instruction Machine_ (TIM), whose evaluation model is very different from that of the G-machine. The TIM was developed more recently than the G-machine, so there is much less other literature about it. Chapter 4 therefore contains a rather more detailed development of the TIM’s evaluation model than that given for the G-machine.
* Finally, Chapter 5 adds a new dimension by showing how to compile functional programs for a _parallel G-machine_.

For each of these implementations we discuss two main parts, the _compiler_ and the _machine interpreter_. The compiler takes a Core-language program and translates it into a form suitable for execution by the machine interpreter.

The machine interpreter simulates the execution of the compiled program. In each case the interpreter is modelled as a _state transition system_ so that there is a very clear connection between the machine interpreter and a `real’ implementation.

One important way in which the Core language is restrictive is in its lack of local function definitions. There is a well-known transformation, called _lambda lifting_, which turns local function definitions into global ones, thus enabling local function definitions to be written freely and transformed out later. In Chapter 6 we develop a suitable lambda lifter. This chapter is more than just a re-presentation of standard material. _Full laziness_ is a property of functional programs which had previously been seen as inseparable from lambda lifting. In Chapter 6 we show that they are in fact quite distinct, and show how to implement full laziness in a separate pass from lambda lifting.

## Typographical errors

Here are some typographical errors, spotted by various readers. Page numbers refer to the online versions (which differ from the printed version).

* Page 128, second to last paragraph of section 3.7, first sentence. “addis” should be “is a”.
* Page 134, the code for i’. The “n” under the big brace symbol should say “n pairs”.
* Page 135. Equation 3.36 should have “NConstr”, not “Constr”.
* Page 230, second paragraph. “There one final gloss…” should be “There is one final gloss…”.
* Page 278, the definition of nfib. Replace “n==0” by “n<=1”.

Now, alas, out of print. However the full text of the book is available above. You can order a nicely-bound copy from <http://www.cafepress.com/haskell_books>. Thanks to John Meacham for setting this up.

There is also a [tutor’s guide ][89]available.

 

## Related Info

##  Research Areas 

* [ Programming languages and software engineering ][90]

##  Follow Microsoft Research 

* * [Follow @MSFTResearch][91]
* ##  Share this page 
* * [Tweet][92]
* #### What's new
* [Surface Book 2][93]
* [Surface Pro][94]
* [Xbox One X][95]
* [Xbox One S][96]
* [VR & mixed reality][97]
* [Windows 10 apps][98]
* [Office apps][99]

#### Store & Support

* [Account profile][100]
* [Download Center][101]
* [Sales & support][102]
* [Returns][103]
* [Order tracking][104]
* [Store locations][105]
* [Support][106]
* [Buy online, pick up in store][107]

#### Education

* [Microsoft in education][31]
* [Office for students][108]
* [Office 365 for schools][109]
* [Deals for students & educators ][110]
* [Microsoft Azure in education][111]

#### Enterprise

* [Microsoft Azure ][112]
* [Enterprise][113]
* [Data platform][114]
* [Find a solutions provider][115]
* [Microsoft partner resources ][116]
* [Microsoft AppSource ][117]
* [Manufacturing & resources][35]
* [Financial services][32]

#### Developer

* [Microsoft Visual Studio][14]
* [Windows Dev Center][24]
* [Developer Network][23]
* [TechNet][118]
* [Microsoft Virtual Academy][119]
* [Microsoft developer program][120]
* [Channel 9][121]
* [Office Dev Center][122]

#### Company

* [Careers][123]
* [About Microsoft][124]
* [Company news][125]
* [Privacy at Microsoft][126]
* [Investors][127]
* [Diversity and inclusion][128]
* [Accessibility][129]
* [Security][130]
* [Sitemap][131]
* [Contact us][132]
* [Privacy & cookies ][133]
* [Terms of use][134]
* [Trademarks][135]
* [About our ads][136]
* © Microsoft 2018

![][137]

[1]: https://go.microsoft.com/fwlink/?linkid=845480
[2]: https://img-prod-cms-rt-microsoft-com.akamaized.net/cms/api/am/imageFileData/RE1Mu3b?ver=5c31
[3]: https://www.microsoft.com
[4]: https://www.microsoft.com/en-us/microsoft-365
[5]: https://azure.microsoft.com
[6]: https://products.office.com/en-us/business/office
[7]: https://dynamics.microsoft.com/en-us/
[8]: https://www.microsoft.com/sql-server/
[9]: https://www.microsoft.com/en-us/windowsforbusiness
[10]: https://www.microsoft.com/cloud-platform/windows-server
[11]: https://www.microsoft.com/cloud-platform/enterprise-mobility-security
[12]: https://powerbi.microsoft.com/en-us/
[13]: https://products.office.com/en-us/microsoft-teams/group-chat-software
[14]: https://www.visualstudio.com/
[15]: https://www.microsoft.com/en-us/surface/business/overview
[16]: https://www.microsoft.com/ai/
[17]: https://www.microsoft.com/internet-of-things
[18]: https://azure.microsoft.com/services/cognitive-services/
[19]: https://www.microsoft.com/quantum/
[20]: https://www.microsoft.com/research/
[21]: https://docs.microsoft.com/en-us/
[22]: https://technet.microsoft.com/en-us/ms376608.aspx
[23]: https://msdn.microsoft.com/en-us
[24]: https://developer.microsoft.com/en-us/windows
[25]: https://www.microsoft.com/en-us/itpro/windows
[26]: https://fasttrack.microsoft.com/office
[27]: https://partner.microsoft.com/
[28]: https://www.microsoft.com/solution-providers/
[29]: https://partnercenter.microsoft.com/partner/home
[30]: https://www.microsoft.com/en-us/cloudandhosting
[31]: https://www.microsoft.com/en-us/education
[32]: https://enterprise.microsoft.com/en-us
[33]: https://enterprise.microsoft.com/en-us/industries/government/
[34]: https://enterprise.microsoft.com/en-us/industries/health/
[35]: https://enterprise.microsoft.com/en-us/industries/discrete-manufacturing/
[36]: https://enterprise.microsoft.com/en-us/industries/retail-and-consumer-goods/
[37]: https://www.microsoft.com/security/
[38]: https://www.microsoft.com/licensing/
[39]: https://appsource.microsoft.com/
[40]: https://azuremarketplace.microsoft.com/marketplace/
[41]: https://events.microsoft.com/
[42]: https://www.microsoft.com/en-us/sitemap.aspx
[43]: http://www.microsoft.com/en-us/research/
[44]: http://www.microsoft.com/en-us/research/research-area/artificial-intelligence/
[45]: http://www.microsoft.com/en-us/research/research-area/computer-vision/
[46]: http://www.microsoft.com/en-us/research/research-area/graphics-and-multimedia/
[47]: http://www.microsoft.com/en-us/research/research-area/human-computer-interaction/
[48]: http://www.microsoft.com/en-us/research/research-area/human-language-technologies/
[49]: http://www.microsoft.com/en-us/research/research-area/search-information-retrieval/
[50]: http://www.microsoft.com/en-us/research/research-area/data-visualization-analytics-platform/
[51]: http://www.microsoft.com/en-us/research/research-area/hardware-devices-quantum-computing/
[52]: http://www.microsoft.com/en-us/research/research-area/programming-languages-software-engineering/
[53]: http://www.microsoft.com/en-us/research/research-area/security-privacy-cryptography/
[54]: http://www.microsoft.com/en-us/research/research-area/systems-and-networking/
[55]: http://www.microsoft.com/en-us/research/research-area/algorithms/
[56]: http://www.microsoft.com/en-us/research/research-area/computational-sciences-mathematics/
[57]: http://www.microsoft.com/en-us/research/research-area/ecology-environment/
[58]: http://www.microsoft.com/en-us/research/research-area/economics/
[59]: http://www.microsoft.com/en-us/research/research-area/medical-health-genomics/
[60]: http://www.microsoft.com/en-us/research/research-area/social-sciences/
[61]: http://www.microsoft.com/en-us/research/research-area/technology-for-emerging-markets/
[62]: http://www.microsoft.com/en-us/research/products/
[63]: http://www.microsoft.com/en-us/research/academic-programs/
[64]: http://www.microsoft.com/en-us/research/events-conferences/
[65]: http://www.microsoft.com/en-us/research/people/
[66]: http://www.microsoft.com/en-us/research/careers/
[67]: http://www.microsoft.com/en-us/research/blog
[68]: http://www.microsoft.com/en-us/research/blog/category/podcast/
[69]: https://blogs.microsoft.com/next/
[70]: http://www.microsoft.com/en-us/research/lab/microsoft-research-ai/
[71]: http://www.msra.cn
[72]: http://www.microsoft.com/en-us/research/lab/microsoft-research-asia/
[73]: http://www.microsoft.com/en-us/research/lab/microsoft-research-cambridge/
[74]: http://www.microsoft.com/en-us/research/lab/microsoft-research-india/
[75]: http://www.microsoft.com/en-us/research/lab/microsoft-research-montreal/
[76]: http://www.microsoft.com/en-us/research/lab/microsoft-research-new-england/
[77]: http://www.microsoft.com/en-us/research/lab/microsoft-research-new-york/
[78]: http://www.microsoft.com/en-us/research/lab/microsoft-research-redmond/
[79]: http://www.microsoft.com/en-us/research/lab/applied-sciences-group/
[80]: http://www.microsoft.com/en-us/research/group/advanced-technology-lab-cairo-2/
[81]: http://www.microsoft.com/en-us/research/lab/quantum/
[82]: http://www.microsoft.com/en-us/research/about/
[83]: https://www.microsoft.com/en-us/research/wp-content/uploads/1992/01/student.pdf
[84]: http://www.cafepress.com/haskell_books
[85]: https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/bibtex/
[86]: https://www.microsoft.com/en-us/research/people/simonpj/
[87]: http://www.microsoft.com#%21abstract
[88]: http://www.microsoft.com#%21related_info
[89]: https://www.microsoft.com/en-us/research/wp-content/uploads/1992/01/tutor.pdf
[90]: https://www.microsoft.com/en-us/research/research-area/programming-languages-software-engineering/
[91]: https://twitter.com/MSFTResearch
[92]: https://twitter.com/share
[93]: https://www.microsoft.com/en-us/surface/devices/surface-book-2/overview
[94]: https://www.microsoft.com/en-us/surface/devices/surface-pro/overview
[95]: https://www.xbox.com/en-us/xbox-one-x
[96]: https://www.xbox.com/en-us/xbox-one-s?xr=shellnav
[97]: https://www.microsoft.com/en-us/store/b/virtualreality
[98]: https://www.microsoft.com/en-us/windows/windows-10-apps
[99]: https://store.office.com/en-us/appshome.aspx?
[100]: https://account.microsoft.com/
[101]: https://www.microsoft.com/en-us/download
[102]: https://go.microsoft.com/fwlink/p/?LinkID=824761&clcid=0x409
[103]: https://go.microsoft.com/fwlink/p/?LinkID=824764&clcid=0x409
[104]: https://account.microsoft.com/orders
[105]: https://www.microsoft.com/en-us/store/locations/find-a-store
[106]: https://support.microsoft.com/en-us
[107]: https://www.microsoft.com/en-us/store/b/buy-online-pick-up-in-store?icid=uhf_footer_bopuis
[108]: https://www.microsoft.com/en-us/education/products/office/default.aspx
[109]: https://products.office.com/en-us/academic/compare-office-365-education-plans
[110]: https://www.microsoft.com/en-us/store/b/student
[111]: https://azure.microsoft.com/en-us/community/education/
[112]: https://azure.microsoft.com/
[113]: https://enterprise.microsoft.com/en-us/
[114]: https://www.microsoft.com/en-us/sql-server/
[115]: https://www.microsoft.com/en-us/solution-providers
[116]: https://partner.microsoft.com/en-us/
[117]: https://go.microsoft.com/fwlink/?LinkID=808093
[118]: https://technet.microsoft.com/en-us
[119]: https://mva.microsoft.com/
[120]: https://developer.microsoft.com/en-us/store/register
[121]: https://channel9.msdn.com/
[122]: https://developer.microsoft.com/office
[123]: https://careers.microsoft.com/
[124]: https://www.microsoft.com/en-us/about
[125]: https://news.microsoft.com/
[126]: https://privacy.microsoft.com/en-us
[127]: https://www.microsoft.com/investor/default.aspx
[128]: https://www.microsoft.com/en-us/diversity/
[129]: https://www.microsoft.com/en-us/accessibility/home
[130]: https://www.microsoft.com/en-us/security/default.aspx
[131]: https://www.microsoft.com/en-us/sitemap1.aspx
[132]: https://support.microsoft.com/en-us/contactus
[133]: https://go.microsoft.com/fwlink/?LinkId=521839
[134]: https://go.microsoft.com/fwlink/?LinkID=206977
[135]: https://www.microsoft.com/trademarks
[136]: https://choice.microsoft.com
[137]: https://www.facebook.com/tr?id=435868603227390&ev=PageView&noscript=1