[HN Gopher] A Lambda Calculus with Coroutines and Heapless, Dire...
___________________________________________________________________
A Lambda Calculus with Coroutines and Heapless, Directly-Called
Closures
Author : UncleOxidant
Score : 71 points
Date : 2023-02-25 18:12 UTC (4 hours ago)
(HTM) web link (ayazhafiz.com)
(TXT) w3m dump (ayazhafiz.com)
| ajkjk wrote:
| This page crashes on my Android phone once Mathjax loads.
| stefncb wrote:
| It happens for me too, but only some of the time.
| convolvatron wrote:
| 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 wrote:
| > 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 wrote:
| its entirely possible I just missed the point. ok, so its
| pure, is it linear? (that is arguments passed by copied
| values).
| burakemir wrote:
| 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 wrote:
| 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-ge...
| Joker_vD wrote:
| 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 wrote:
| 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.
| a1369209993 wrote:
| > 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?
|
| https://en.wikipedia.org/wiki/UUID#Version_4_(random)
|
| Not sure about the other problems, though.
___________________________________________________________________
(page generated 2023-02-25 23:00 UTC)