Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm doing some independent research/study with a professor who's a very functional guy. The goal is to examine more of what's happening behind the scenes with functional languages than we normally would during the course of the class I'm also taking with him (in which we're writing interpreters). The independent course will go beyond the interpreter level and look at how we might translate some of the concepts to a hardware machine.

Specifically, my professor mentioned two books, Functional Programming: Application and Implementation by Peter Henderson -- which covers the SECD machine (an idealized machine for functional computing), and The Implementation of Functional Programming Languages by Simon Peyton Jones -- which covers the SKI machine (and of course combinators).

From the poking around I've done, these two books seem pretty legendary in the functional programming world -- which is great (I still think K&R is one of the best C books). But, both books are also more than 30 years old. I'm curious if there has been any further research or instructive literature produced regarding these topics. It would also be interesting to know if any of these concepts are making their way into modern compilers and close-to-the-kernel interpreters.

share|improve this question

closed as off-topic by gnat, MichaelT, ozz, Jim G., maple_shaft Sep 26 '13 at 11:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions asking us to recommend a tool, library or favorite off-site resource are off-topic for Programmers as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it." – maple_shaft
If this question can be reworded to fit the rules in the help center, please edit the question.

Are you specifically looking for research on call-by-value languages? – dan_waterworth Jan 31 '13 at 9:03
Perhaps. I guess I'm most interested in modern manifestations of SECD machines. Has anyone implemented SECD hardware? Are pure functional languages using only combinators being actively researched and developed and written about? Has anyone written modern literature or updates to these two > 35 year-old texts which seem to introduce an interesting sub-genre of computer science/engineering? If research on call-by-value languages seems relevant, I'd love to hear about it. – David Cowden Jan 31 '13 at 17:38
You might find this interesting, although it was created for lazy languages. – dan_waterworth Feb 1 '13 at 18:56

Here is a more recent paper by Simon Peyton Jones on the Spineless Tagless G-machine, which was (and still is) used as an intermediate language in the Glasgow Haskell Compiler:

Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine (1992).

share|improve this answer

"... The independent course will go beyond the interpreter level and look at how we might translate some of the concepts to a hardware machine"

What do you mean by hardware machine?

I ask you this in particular because a long time ago, I was subscribed to the ACM, and I remember that I saw some articles, or references to articles on how to implement combinators directly on hardware.

I roughly remember who and which articles at this time, (I have his name in the tip of the tongue, whose last name may start with H,) about someone who wrote some articles in how to implement combinators in hardware, and some article on how to build an optimal combinator basis for a program. It maybe was from the UK or some of north of European country.

That was on late 80's or early 90's, later, on 2000, when I was not interested in hardware anymore, I took a course on computer architecture where I was tough to program in a low level language similar to Verilog to program a FPGA (Field Programmable Gate Array), where I noticed the importance of that work.

On that basis, with the clear warning that I am sustaining my suggestion o a very vague memories, I think that a good project could be to:

1) Search for the article about how to find an optimal combinator basis for a particular program, and about implementing combinators in hardware.

2) Search how to implement combinators in a very-low-level language like Verilog.

3) Build a program which translates SKI to Verilog, just to gain some experience with such task.

4) Analyze what is the better way to implement combinators in FPGAs.

5) Use what you learned from the articles to design an appropriate basis.

6) build a compiler for a simple functional language to those combinators, you can learn how to do that from an article by David Turner (I can't remember that title too, but you should not have any problem to find it, I should sleep better ;) )

7) play with a FPGA, by programming one, or just simulating it, and compiling simple programs, first one that just make a simple computation, with no recursive call, then a simple program using a fixed point combinator. (you should analyze and search in literature which fixed point combinator is more adequate to implement in hardware)

8) Once you have a good experience, you can implement a more serious compiler for a simple but more general functional language (no types yet!)

9) To program an FPGA is not as simple as translating your program into a very-low-level language like Verilog, timing is very important. I remember that in the course that I took where I learned to program FPGA's one had to spent time analyzing the time charts in the simulator to prevent that a computation could not be synchronized.

if your project is for research (you are graduate student or working on research) you should analyze your generated code with some model checking technique, that means that you should also generate something like a temporal logic interpretation of your programs to be able to check it. When you finish this, you are ready for your PhD exam!

share|improve this answer
Is the last name Henderson? – David Cowden Sep 21 '13 at 19:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.