6 ms·

A Lambda Calculus with Coroutines and Heapless, Directly-Called Closures

129 points by UncleOxidant 4y ago

ajkjk 4y ago
This page crashes on my Android phone once Mathjax loads.
- stefncb 4y ago
  It happens for me too, but only some of the time.
convolvatron 4y ago
ok. so normally we would put these on the heap and garbage collect them. instead, we're going to run on a stack, which remove the gc overhead, but couples our ability to reclaim frames to the control flow. I skimmed the article, but I didn't understand the goal here. clearly that would work better for _some_ workloads
- kerkeslager 4y ago
  > couples our ability to reclaim frames to the control flow. I'm not sure what you mean here. Are you referring to the fact that we (probably*) have to be purely functional for this to work? * Saying "probably" here because there may be some subsets of side-effects which work fine in this model, which I just don't feel like thinking through at the moment.
  - convolvatron 4y ago
    its entirely possible I just missed the point. ok, so its pure, is it linear? (that is arguments passed by copied values).
    - kerkeslager 4y ago
      I don't know if the OP's implementation uses arguments by copied values or not, but I will say that there's a fairly simple transformation that converts purely functional code into continuation-passing style (CPS), where instead of returning, you take a continuation, and pass what you would normally return, into the continuation like this: (def avg (a b) (/ (+ a b) 2)) ...becomes: (def avg (a b cont) (+ a b (lambda (s) (/ s 2 cont)))) Note that in the converted code + and / also don't return values, instead calling the continuations they're passed on their results. Pervasive CPS means that everything is a tail call, which means that you can tail call optimize (TCO) everything. The trivial implementation of TCO probably uses copy, but you can notably store values created in the current frame on the stack instead of the heap, and then pass by reference. Any unreferenced values can be removed, and the referenced values can be compacted within the frame to reduce stack space. However, in practice, it's faster to wait until you run out of stack space and then go back and compact everything in one go (this approach was pioneered by Chicken Scheme, I think). If you think through how this stack compaction might work, you'll quickly see that this is equivalent to a mark-sweep-compact garbage collector. If your language is purely functional (Chicken Scheme isn't) then you have an additional property, which is that objects can only be referenced by objects higher on the stack. This means that if you start from the top of the stack, you can mark and sweep in a single pass, because when you arrive at a node, if it hasn't been marked by any of the objects higher in the stack, it's not referenced and can be swept. If your stack is stored in reverse order in memory (that is, the top of the stack is the earliest in memory) this mark/sweep pass is extremely cache friendly. You can also build up a backreference table during this pass, which means you only need one additional pass to compact. Again, the inverted stack is cache friendly, because even though you're passing over the stack in reverse order, backpatched references are likely to be local to the things they reference, which pulls objects into cache before they are referenced. That's an absurdly long way to say I don't know the answer the question, but that's all to say that there are good reasons why an implementation of a heapless architecture might pass by reference rather than by copy.
burakemir 4y ago
This covers a lot of ground! The author is interested in concurrency, in particular coroutines. They follow a standard approach of PL research to extend a lambda calculus, discussing typing and compilation. This will seem academic but there are certainly many PL researchers who have deep expertise in compiler design and implementation and who also deeply care about communicating these ideas in a precise, formalized manner. To put this in perspective: even after so many years, decades of research, industry and hobby projects turned million of professional users (before thinking about a type system)... the question of exposing concurrency to programmers is far from settled even if it is so important. There are many approaches and different perspectives on what matters more. Formalizing these approaches has likely been done before, but in practical terms we don't care about abstract properties but about performance. That is why I like the article, implementation concerns are important, but the ability to fully specify behavior is also important. Keep it up.
anfelor 4y ago
Thank you for this cool blog post! > Each syntactic function (a lambda \x -> ...) gets a unique name > Determine the stack size of its captures based on the largest captures of any lambda in the lambda set it's involved in. If I understand these two points correctly, this would require a whole-program optimization and would mean that libraries need to be recompiled alongside the current program. For example, if there are libraries `foo` and `bar` to be used by a program `baz`, it seems that the names of functions in `foo`, `bar` and `baz` need to be distinct. But how do you ensure this if `foo` and `bar` are compiled separately? Similarly, I cannot compile `foo` without knowing about `baz`, because any higher-order function in `foo` needs to know what kind of lambda set it will have in `baz`. That would seem to imply a big increase in compile-times when working with a larger codebase. I don't know if this is well-known, but one thing I find helpful during compilation is to have the procedure that compiles an expression take a parameter indicating where the expression should be compiled, rather than (in this case) always compiling to the stack and storing the result elsewhere later. This eliminates a lot of trivially-reducable load and stores. This sounds a lot like Destination-Driven Code Generation as used in V8. This is a fun presentation about it: https://raw.githubusercontent.com/eatonphil/one-pass-code-generation-in-v8/main/One-pass%20Code%20Generation%20in%20V8.pdf https://raw.githubusercontent.com/eatonphil/one-pass-code-ge...
- Joker_vD 4y ago
  Interesting presentation, thanks. That problem with compilation of conditional statements makes me suspect that older languages didn't have first-class Boolean values but restricted Boolean expressions to only appear as tests for conditional/looping constructs exactly because of it.
- fourteenminutes 4y ago
  Author here. Yes, the scheme requires whole-program compilation, which is unfortunate. If you’re okay with statically-linked dependencies there is only the large problem of making a compiler that is adept to incremental re-compilation. However, any monomorphizing compiler faces such a challenge, so the problem is not unique.
  - 4y ago
shpongled 4y ago
Super cool - I have gone done the rabbit hole of trying to compile functional languages/lambda calculus with continuations a few times. I will be bookmarking and returning to this when the I get the itch again!
js8 4y ago
Won't really read this, but I am wondering how it's related to https://en.m.wikipedia.org/wiki/Lambda-mu_calculus https://en.m.wikipedia.org/wiki/Lambda-mu_calculus (and if the author is aware).
somewhereoutth 4y ago
Unfortunately the link crashes my browser (Chrome/Chromium, but a little out of date). I'd be very interested to read about this, not least as I'm extending the untyped LC with a notion of a 'tag' term, and a branch on tag operation, thus resulting in dynamic dispatch without (formal) types. Any pointers to a suitable graph reduction engine gratefully received, I've built my own naive implementation (in Javascript!) but of course it is rather slow.
twoodfin 4y ago
There’s an interesting question embedded here about the relative effectiveness of modern CPU branch predictors vs. (unconditional) branch target predictors. Total speculation mode, but I’d guess that if you have >1 static conditions (on runtime values) that determine the target, you’re indeed better off encoding those as explicit branches. Both predictors are fundamentally pattern matchers, and it should be easier to identify patterns in independent conditions separately rather than in combination.

129 points by UncleOxidant 4y ago

ajkjk 4y ago

This page crashes on my Android phone once Mathjax loads.

stefncb 4y ago
It happens for me too, but only some of the time.

convolvatron 4y ago

ok. so normally we would put these on the heap and garbage collect them. instead, we're going to run on a stack, which remove the gc overhead, but couples our ability to reclaim frames to the control flow. I skimmed the article, but I didn't understand the goal here. clearly that would work better for _some_ workloads

kerkeslager 4y ago
> couples our ability to reclaim frames to the control flow. I'm not sure what you mean here. Are you referring to the fact that we (probably*) have to be purely functional for this to work? * Saying "probably" here because there may be some subsets of side-effects which work fine in this model, which I just don't feel like thinking through at the moment.
- convolvatron 4y ago
  its entirely possible I just missed the point. ok, so its pure, is it linear? (that is arguments passed by copied values).
  - kerkeslager 4y ago
    I don't know if the OP's implementation uses arguments by copied values or not, but I will say that there's a fairly simple transformation that converts purely functional code into continuation-passing style (CPS), where instead of returning, you take a continuation, and pass what you would normally return, into the continuation like this: (def avg (a b) (/ (+ a b) 2)) ...becomes: (def avg (a b cont) (+ a b (lambda (s) (/ s 2 cont)))) Note that in the converted code + and / also don't return values, instead calling the continuations they're passed on their results. Pervasive CPS means that everything is a tail call, which means that you can tail call optimize (TCO) everything. The trivial implementation of TCO probably uses copy, but you can notably store values created in the current frame on the stack instead of the heap, and then pass by reference. Any unreferenced values can be removed, and the referenced values can be compacted within the frame to reduce stack space. However, in practice, it's faster to wait until you run out of stack space and then go back and compact everything in one go (this approach was pioneered by Chicken Scheme, I think). If you think through how this stack compaction might work, you'll quickly see that this is equivalent to a mark-sweep-compact garbage collector. If your language is purely functional (Chicken Scheme isn't) then you have an additional property, which is that objects can only be referenced by objects higher on the stack. This means that if you start from the top of the stack, you can mark and sweep in a single pass, because when you arrive at a node, if it hasn't been marked by any of the objects higher in the stack, it's not referenced and can be swept. If your stack is stored in reverse order in memory (that is, the top of the stack is the earliest in memory) this mark/sweep pass is extremely cache friendly. You can also build up a backreference table during this pass, which means you only need one additional pass to compact. Again, the inverted stack is cache friendly, because even though you're passing over the stack in reverse order, backpatched references are likely to be local to the things they reference, which pulls objects into cache before they are referenced. That's an absurdly long way to say I don't know the answer the question, but that's all to say that there are good reasons why an implementation of a heapless architecture might pass by reference rather than by copy.

burakemir 4y ago

This covers a lot of ground! The author is interested in concurrency, in particular coroutines. They follow a standard approach of PL research to extend a lambda calculus, discussing typing and compilation. This will seem academic but there are certainly many PL researchers who have deep expertise in compiler design and implementation and who also deeply care about communicating these ideas in a precise, formalized manner. To put this in perspective: even after so many years, decades of research, industry and hobby projects turned million of professional users (before thinking about a type system)... the question of exposing concurrency to programmers is far from settled even if it is so important. There are many approaches and different perspectives on what matters more. Formalizing these approaches has likely been done before, but in practical terms we don't care about abstract properties but about performance. That is why I like the article, implementation concerns are important, but the ability to fully specify behavior is also important. Keep it up.

anfelor 4y ago

Thank you for this cool blog post! > Each syntactic function (a lambda \x -> ...) gets a unique name > Determine the stack size of its captures based on the largest captures of any lambda in the lambda set it's involved in. If I understand these two points correctly, this would require a whole-program optimization and would mean that libraries need to be recompiled alongside the current program. For example, if there are libraries `foo` and `bar` to be used by a program `baz`, it seems that the names of functions in `foo`, `bar` and `baz` need to be distinct. But how do you ensure this if `foo` and `bar` are compiled separately? Similarly, I cannot compile `foo` without knowing about `baz`, because any higher-order function in `foo` needs to know what kind of lambda set it will have in `baz`. That would seem to imply a big increase in compile-times when working with a larger codebase. I don't know if this is well-known, but one thing I find helpful during compilation is to have the procedure that compiles an expression take a parameter indicating where the expression should be compiled, rather than (in this case) always compiling to the stack and storing the result elsewhere later. This eliminates a lot of trivially-reducable load and stores. This sounds a lot like Destination-Driven Code Generation as used in V8. This is a fun presentation about it: https://raw.githubusercontent.com/eatonphil/one-pass-code-generation-in-v8/main/One-pass%20Code%20Generation%20in%20V8.pdf https://raw.githubusercontent.com/eatonphil/one-pass-code-ge...

Joker_vD 4y ago
Interesting presentation, thanks. That problem with compilation of conditional statements makes me suspect that older languages didn't have first-class Boolean values but restricted Boolean expressions to only appear as tests for conditional/looping constructs exactly because of it.
fourteenminutes 4y ago
Author here. Yes, the scheme requires whole-program compilation, which is unfortunate. If you’re okay with statically-linked dependencies there is only the large problem of making a compiler that is adept to incremental re-compilation. However, any monomorphizing compiler faces such a challenge, so the problem is not unique.
- 4y ago

shpongled 4y ago

Super cool - I have gone done the rabbit hole of trying to compile functional languages/lambda calculus with continuations a few times. I will be bookmarking and returning to this when the I get the itch again!

js8 4y ago

Won't really read this, but I am wondering how it's related to https://en.m.wikipedia.org/wiki/Lambda-mu_calculus https://en.m.wikipedia.org/wiki/Lambda-mu_calculus (and if the author is aware).

somewhereoutth 4y ago

Unfortunately the link crashes my browser (Chrome/Chromium, but a little out of date). I'd be very interested to read about this, not least as I'm extending the untyped LC with a notion of a 'tag' term, and a branch on tag operation, thus resulting in dynamic dispatch without (formal) types. Any pointers to a suitable graph reduction engine gratefully received, I've built my own naive implementation (in Javascript!) but of course it is rather slow.

twoodfin 4y ago

There’s an interesting question embedded here about the relative effectiveness of modern CPU branch predictors vs. (unconditional) branch target predictors. Total speculation mode, but I’d guess that if you have >1 static conditions (on runtime values) that determine the target, you’re indeed better off encoding those as explicit branches. Both predictors are fundamentally pattern matchers, and it should be easier to identify patterns in independent conditions separately rather than in combination.