<p>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; <code>main</code> will be a pure function that converts some input to some output (e.g. <code>main :: int -&gt; int</code> will take an integer from stdin, apply the function on it, and print the result to stdout).</p>
<p>I have done some research on how to run a lazy lambda calculus, but all of my search efforts ended at:</p>
<ul>
<li>G-machine or TIM, as in <a href="https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/" rel="noreferrer">this &quot;tutorial&quot;</a> which is nice and well documented but from 1990s, or</li>
<li>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.</li>
</ul>
<p>Requirements for my language are:</p>
<ul>
<li>I want it to run arbitrary lambda terms. This rules out <a href="https://github.com/HigherOrderCO/HVM" rel="noreferrer">HVM</a> for example (<a href="https://github.com/HigherOrderCO/HVM/issues/44" rel="noreferrer">issue #44</a>).</li>
<li>Being able to use integer values and/or data constructors would be nice (as in the Core language as defined in the &quot;tutorial&quot; above).</li>
</ul>
<p>Are there any other kinds of backends or runtimes for lazily evaluated lambda calculus, developed in 2000s or later and satisfying the requirements?</p>

<backend><runtime><functional-programming><lambda-calculus>
Runtime/Backend for a lazy, pure functional, lambda-calculus-based language?
CC BY-SA 4.0
2023-05-17T23:06:21.390Z
@AlexNelson That one I already linked in the main post.
Bubbler
CC BY-SA 4.0
2023-05-17T05:22:44.283Z
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.
Community Compiler
CC BY-SA 4.0
2023-05-17T05:54:48.047Z
This isn't 2000s or later, but there's The Book. https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf
Pseudonym
CC BY-SA 4.0
2023-05-17T06:01:28.597Z
@Pseudonym I think I've seen that before. And its later sections describe the G-machine, which I'm already aware of.
Bubbler
CC BY-SA 4.0
2023-05-17T14:15:05.683Z
There is also this sequel to Simon Peyton Jones's book, the confusingly titled paper [Implementing functional languages: a tutorial](https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/).
Alex Nelson
<p>I guess, the best-known modern optimizing back-end for lazy functional languages specifically (and strict ones too) is <a href="https://grin-compiler.github.io/" rel="noreferrer">GRIN</a>.</p>
<p>On the other hand, <a href="https://agraef.github.io/pure-lang/" rel="noreferrer">Pure Language</a> 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).</p>
<p>If you're OK with compiling to another high-level language (aka &quot;transpiling&quot;) you can target existing lazy language, say, Haskell (or GHC Core specifically) or Lazy Racket not to wrestle with types.</p>
<p>As a kinda intermediate option you can take a look at <a href="https://www.graalvm.org/latest/graalvm-as-a-platform/language-implementation-framework/" rel="noreferrer">GraalVM's Truffle Framework</a>. 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. :)</p>

CC BY-SA 4.0
2023-05-17T08:01:14.913Z
2023-05-17T14:02:31.447Z
2023-05-17T14:02:31.447Z
Alex Chichigin
CC BY-SA 4.0
2023-05-18T06:15:58.747Z
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 :(
Bubbler
CC BY-SA 4.0
2023-05-21T07:34:16.343Z
@Bubbler well it's well known that programming practice lags behind theoretical developments for about 20 years... 
Alex Chichigin
# Runtime/Backend for a lazy, pure functional, lambda-calculus-based language?
Posted by: username_0 on 2023-05-17
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"](https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-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](https://github.com/HigherOrderCO/HVM) for example ([issue #44](https://github.com/HigherOrderCO/HVM/issues/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?
**Tags:** backend runtime functional-programming lambda-calculus
> **Comments:**
> **username_1**: 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.  
> **username_2**: This isn't 2000s or later, but there's The Book. https://www.microsoft.com/en-us/research/wp-content/uploads/1987/01/slpj-book-1987-small.pdf  
> **username_0**: @Pseudonym I think I've seen that before. And its later sections describe the G-machine, which I'm already aware of.  
> **username_3**: There is also this sequel to Simon Peyton Jones's book, the confusingly titled paper [Implementing functional languages: a tutorial](https://www.microsoft.com/en-us/research/publication/implementing-functional-languages-a-tutorial/).  
> **username_0**: @AlexNelson That one I already linked in the main post.  
---
## 1 answers
### Answer by username_4 on 2023-05-17. Score: 9 | Accepted answer
I guess, the best-known modern optimizing back-end for lazy functional languages specifically (and strict ones too) is [GRIN](https://grin-compiler.github.io/).

On the other hand, [Pure Language](https://agraef.github.io/pure-lang/) 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](https://www.graalvm.org/latest/graalvm-as-a-platform/language-implementation-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. :)
> **Comments:**
> **username_0** (2023-05-18): 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 :(  
> **username_4** (2023-05-21): @Bubbler well it's well known that programming practice lags behind theoretical developments for about 20 years...   
---
