The Implementation of Functional Programming Languages (1987) | Hacker News Reader

The Implementation of Functional Programming Languages (1987)

research.microsoft.com

190 pointstbirdz45 comments

I've read (part of) this book and used it to implement a toy compiler. It helped me a lot in getting a better understanding of Haskell and other functional languages. This is really an amazing book, well worth investing some time into. It starts from simple definitions and concepts and builds up on them - very easy to follow even with little to no previous knowledge of the field.

I'm on a mobile device so can't view the book. Is familiarity with Haskell is one of the prerequisites to follow this? Thanks!

It wouldn't hurt, but given this paper predates Haskell by 3 years I think you're safe.

Would be more a history lesson of what eventually led to Haskell. IIRC Miranda might be a more apt comparison.

Me too. Wrote a toy language partially referring to this back in '06. I still look back on that time fondly. It was one of those periods in my career where I was learning so many new concepts at once and it all felt like play. Much of my professional life really does feel like play still, but that was a sort of golden age. Ahh, memories.

Although this is quite an old book, the topic is still very relevant even today. The ideas are timeless and worth reading. I'm impressed by the authors that made their books survive in a very long time.

The Prentice-Hall Series in Computer Science has a lot of timeless content. C.A.R. Hoare was an outstanding editor.

Once you get to the final chapters, where an intermediate representation of lambda calculus is presented (G-code), read this accompanying paper [1] and wonder where we could be now if the market and hardware manufacturers took a π degree turn to fully support functional paradigms.

[1] https://www.doc.ic.ac.uk/~wl/icprojects/papers/reduceron08.p...

I just realized that π looks like a u turn. I wish they had told us at school.

> π degree turn

So a bit over 3 degrees?

I think that's half of a τ turn. http://tauday.com/tau-manifesto

I am very suprised to see the association of the word microsoft, 1987 and functional programming. As far as I remember, Simon Peyton Jones research (and this book) has made him famous. I was very sad that such a talent was hired by the "devil" microsoft.

That is old story. He has managed to do great things inside Microsoft and since the departure of Balmer, my opinion about Microsoft is a lot more balanced. The association seems an anachronism.

Microsoft has been very involved in the development of Haskell for quite a while now, and functional languages in general, with projects like F# and F*. Several of the big names in the Haskell community work or have worked for MSR.

This looks pretty promising from the table of contents! It was also written by one of the main authors of GHC, the most widely-used Haskell compiler.

This is an amazing book. We need more people with writing capabilities like SPJ. Reading this book is almost like inventing compilers for lazy functional languages yourself. There really is no substitute other than actually doing it yourself.

1987 was the year I first got access to Usenet (via FidoNet). It's interesting to think how long it would take to download a 30MB book at the time. Of course it would have been considerably smaller since it would have probably been a text file or perhaps LaTeX.

When a CS book is relevant this long, I feel like these kind of ruminations put me in the right headspace to receive it.

That was right around the time that T1 drops were coming to hospitals and universities (my father was faculty at Harvard/BIDMC at the time). In the latter part of the '87s I was still a few embryonic cells, but as a true nerd, I'd barrage my fathers colleagues with questions about technology and infrastructure in my teenage years. This was the era of UUCP and .TeX files, with a bit of PS here and there (for final presentation; not for transfer). A few years later, Gopher would have been the prime medium of exchange before the NCSA implementation of HTTP went around like wildfire.

Side-note: I was listening to an interview with an EE who drafted textbooks at (I want to say, though I might be wrong) UC Berkeley during the 70s. He mentioned the reason why his original first few editions had no diagrams was because getting access to the resource (they only had one resource on staff for the dept for this purpose) to assist in typesetting was so hard, you'd have months, sometimes years of wait-time. I wish I still had contact with the greybeards who were publishing then of my fathers generation to ask them what the procedure was when they would submit papers for publication and/or press.

Edit: https://www.academia.edu/13067316/T1_Historical_Timeline_of_... So presumably that NSFnet timeline (~1986) is when you had academics gaining access to static routed internet, ARIN giving out netblock allocations, etc. I'd imagine post-docs and grad students fighting over VAX/VMS time like modern day post-docs battle over NMR access these days.

Well, there's a perfectly fine 6MB djvu file - only one fifth the infinite download time!

Also, as the page states it can be text-searched. A version not consisting on scanned pages would be neat, but I guess the author lost the sources long time ago.

Anyone got this in EPUB format?

Calibre is free and converts easily between all the major formats, I use it on OS X.

Just FYI, I know I was glad to have it linked to me when I asked a similar question a few months ago.

Fwiw the djvu-version might be easier to convert than the pdf version. It also renders ok on my phone with the djvu-plugin for fbreader (android).

Bryan O'Sullivan (Haskell, Facebook) mentioned in a talk that he got into the whole Haskell ecosystem while interning for Simon P.J. (the author of this book) and this book helped him get started back then.

Here's an implementation of a toy compiler targeting LLVM (with very basic Erlang interop), which was created with the help of that book: https://github.com/pkaleta/kivi

I would think that, while tempting, you'd want to avoid recursion in your implementation.

Why?

I'm not an expert... but you don't want your C/C++ code stack overflowing or running out of memory in an uncontrolled way. Your C/C++ can do graph reduction by working on a structure in a loop. Then you'll be able to better monitor resources.

Eh, clarity of code is more important, in my opinion. If you run out of stack, get a better computer.

Stack doesn't generally scale up with RAM. GCC and Clang can both do some tail call optimization, and I find rewriting code to use an accumulator isn't very hard on the eyes.

s/computer/compiler/

This is why TCO (Tail call optimization) exists... but of course not all recusion is tail recursion, but I think it can always be written this way, and should always be for arbitrary depth recursion.

Yes, you can always convert direct style code to continuation passing style code. And continuation passing only uses tail calls. This is one of the big advantages of CPS. Of course if you don't have a tail call optimization, then you overflow the stack pretty quick.

Elimination, not Optimization. Either you can rely on it as part of the spec (Elimination) or you can't (Optmization)

There is normally no deep recursion in compiling a program. The compiler would recurse over recursive program constructs, like nested if statements. Programmers normally do not nest constructs very deep.

This may be true for human programmers, but compilers also must compile machine generated code, which often looks very different. As an example, I can't remember the source on this, but I have read somewhere that the original C++ compiler (cfront) compiled C++ into C code, and this generated code exposed many bugs in the C compilers of the time, as it was very different than how a human would have written that code.

Running out of stack space compiling a machine generated program would be a bug in the automatic source code generator then.

In the same sense that running out of stack space compiling a human generated program is a bug in the programmer.

If human-generated programs compete head-to-head with robot-generated programs for blowing up the implementation, that human has a worse bug than the robot.

I just watched a talk where Kernighan brought up this exact anecdote.

When I write a program I aspire to impose no arbitrary limits apart from those imposed by the architecture. So I'd like my compiler to be able to handle programs as complex as the user wants, with the only limit being the available virtual memory and disk space. If you use recursion for 'outer loop' stuff, you impose the extra limitation of the size of the stack, which is much smaller than available virtual memory.

I work with partial evaluation, where intermediate representations during compilation can get quite large, and have seen stack overflows in the compiler for real.

It would be nice if stacks were arbitrarily large anyway.

A program is so syntactically nested that the compiler blows an 8 megabyte stack (default on x86 Linux, easily extended with ulimit) is a silly program. There is no need to support such a thing in a language implementation.

Note that if the language supports macros, you can't eliminate recursion from compile time; macro expanders can express recursion. (The same remark applies though: if user-defined macros blow a generous stack that is many megabytes long, oh well!)

If you are doing some kind of abstraction interpretation or static analysis, you may have many many implementation stack frames for each logical stack frame.

Then add in very deep inlining.

And as I say I've seen it for real, in a real compiler, with a real program, while doing a real job. I could send the author an email and tell him his program is silly, but I'd rather be able to compile it.

One thing.

Sometimes linear constructs can appear nested in the handling of the syntax.

You want to avoid right recursion in an LR parser for list-like constructs, especially if they can be reasonably expected to grow large. These constructs appear "flat" to the programmer, but the parser will push tokens onto the stack and not reduce anything until the end of the construct is reached.

"Normally" is the operative word.

I've seen output from compilers to JavaScript that convert huge switches into if cascades which are in fact quite deep: think tens to hundreds of thousands of cases converted to an if cascade.

Or put another way, not all programs are written by programmers.

The `Letrec' construct (see: chapter 3) addresses your concerns. It extends the language from a standard S-K-I lambda calculus into a language that "copes" with recursion, especially with TCO.

If you've done some Scheme (or Lisp (or Haskell (or Curry))) then you will find this very readable. Section 2.4 has a good explanation of the Y combinator. I'm going to try and get through the whole book.

Reply on news.ycombinator.com