10
$\begingroup$

I'm thinking of writing a toy language based on lambda calculus. I want it to be lazily evaluated. I/O is not a concern for now; main will be a pure function that converts some input to some output (e.g. main :: int -> int will take an integer from stdin, apply the function on it, and print the result to stdout).

I have done some research on how to run a lazy lambda calculus, but all of my search efforts ended at:

  • G-machine or TIM, as in this "tutorial" which is nice and well documented but from 1990s, or
  • STG which is famous for being the model of GHC Haskell, but with hardly any material that talks about what it really is and how it can be implemented.

Requirements for my language are:

  • I want it to run arbitrary lambda terms. This rules out HVM for example (issue #44).
  • Being able to use integer values and/or data constructors would be nice (as in the Core language as defined in the "tutorial" above).

Are there any other kinds of backends or runtimes for lazily evaluated lambda calculus, developed in 2000s or later and satisfying the requirements?

$\endgroup$
5
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – PLDI Community Account Bot
    May 17 at 5:22
  • 2
    $\begingroup$ This isn't 2000s or later, but there's The Book. microsoft.com/en-us/research/wp-content/uploads/1987/01/… $\endgroup$
    – Pseudonym
    May 17 at 5:54
  • $\begingroup$ @Pseudonym I think I've seen that before. And its later sections describe the G-machine, which I'm already aware of. $\endgroup$
    – Bubbler
    May 17 at 6:01
  • $\begingroup$ There is also this sequel to Simon Peyton Jones's book, the confusingly titled paper Implementing functional languages: a tutorial. $\endgroup$
    – Alex Nelson
    May 17 at 14:15
  • 2
    $\begingroup$ @AlexNelson That one I already linked in the main post. $\endgroup$
    – Bubbler
    May 17 at 23:06

1 Answer 1

Reset to default
8
$\begingroup$

I guess, the best-known modern optimizing back-end for lazy functional languages specifically (and strict ones too) is GRIN.

On the other hand, Pure Language for example is implemented directly on top of LLVM. I mean, they use Runtime Support Library of course, like GHC does and pretty much any other high-level language (not necessarily functional).

If you're OK with compiling to another high-level language (aka "transpiling") you can target existing lazy language, say, Haskell (or GHC Core specifically) or Lazy Racket not to wrestle with types.

As a kinda intermediate option you can take a look at GraalVM's Truffle Framework. You'll need to implement a tree-walking interpreter for your language (in Java) and a couple of classes to handle lazy evaluation, and you'll get a JIT-compiler for free. :)

$\endgroup$
2
  • $\begingroup$ GRIN looks like something I'd look into next. Looking at the list of references on the GRIN paper, it feels like we lost 20 years in this area :( $\endgroup$
    – Bubbler
    May 18 at 6:15
  • $\begingroup$ @Bubbler well it's well known that programming practice lags behind theoretical developments for about 20 years... 😂 $\endgroup$
    – Alex Chichigin
    May 21 at 7:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .