5 ms·

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 th

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.
- anfelor 4y ago
  Thanks for confirming, and that is a good point! However, I think that for monomorphizing compilers, programmers often write code in such a way as to avoid triggering a larger rec-compilation. With monomorphization this might be easier to achieve since you need to control how your datastructures are instantiated. But with functions you would need to control how the functions are passed. For example, a use of a Haskell-style `lens` package would probably trigger a re-compilation of `lens -> kan-extensions -> profunctors -> comonad -> base`. Programmers can work around that, but it may place restrictions on what they can easily do with the language.
  - fourteenminutes 4y ago
    Yes - that’s a great observation. The scheme here means that you can end up with compilation dependencies that aren’t reflected in your explicit dependency graph, exactly e.g. via the path you describe. The same is true of monomorphization in presence of typeclasses (or traits, concepts, etc). I have some ideas about how to do such incremental compilations optimally, but they haven’t been written down. Anyway, I totally agree with you. I don’t mean to suggest this is the best way to do things - if anything Rust/C++/etc have taught us excessive monomorphization is probably not the way to go for developer experience reasons. You may be able to imagine some interesting derivative of the scheme presented here with something like Swift’s “witness table”-based compilation of protocols, which may be much more compile-time performant, and support separate compilation. But, I don’t even have a sketch of that. This is only one technique and the design space is very wide.
- anfelor 4y ago
  Another question: In the section on eliminating heap-allocated captures, you discuss creating a datatype for captures that is passed by-value. But what if that datatype is recursive? For example, how would you compile a CPS-transformed `reverse`: fun reverse(xs : list<a>, k : list<a> -> list<a>) match xs Cons(x, xx) -> reverse(xx, \ys -> k(Cons(x, ys))) Nil -> k(Nil) Here, the `k` that is recursively passed depends on the previous `k`. As such `k` should be as large as the input list and can not be stack-allocated?
a1369209993 4y ago
> 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) https://en.wikipedia.org/wiki/UUID#Version_4_(random) Not sure about the other problems, though.
coldtea 4y ago
>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? Couldn't you just prefix or namespace them behind the scenes when you compile each of them with e.g. a hash of the code for the function (or the library they are in), or some similar way to get a unique id/hash/uuid per unit of code (e.g. library, file) that needs to have distinct names of function with other such units across the whole program? You could also keep the association with the original name to show when you print error messages or debug or whatever.

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.

anfelor 4y ago
Thanks for confirming, and that is a good point! However, I think that for monomorphizing compilers, programmers often write code in such a way as to avoid triggering a larger rec-compilation. With monomorphization this might be easier to achieve since you need to control how your datastructures are instantiated. But with functions you would need to control how the functions are passed. For example, a use of a Haskell-style `lens` package would probably trigger a re-compilation of `lens -> kan-extensions -> profunctors -> comonad -> base`. Programmers can work around that, but it may place restrictions on what they can easily do with the language.
- fourteenminutes 4y ago
  Yes - that’s a great observation. The scheme here means that you can end up with compilation dependencies that aren’t reflected in your explicit dependency graph, exactly e.g. via the path you describe. The same is true of monomorphization in presence of typeclasses (or traits, concepts, etc). I have some ideas about how to do such incremental compilations optimally, but they haven’t been written down. Anyway, I totally agree with you. I don’t mean to suggest this is the best way to do things - if anything Rust/C++/etc have taught us excessive monomorphization is probably not the way to go for developer experience reasons. You may be able to imagine some interesting derivative of the scheme presented here with something like Swift’s “witness table”-based compilation of protocols, which may be much more compile-time performant, and support separate compilation. But, I don’t even have a sketch of that. This is only one technique and the design space is very wide.
anfelor 4y ago
Another question: In the section on eliminating heap-allocated captures, you discuss creating a datatype for captures that is passed by-value. But what if that datatype is recursive? For example, how would you compile a CPS-transformed `reverse`: fun reverse(xs : list<a>, k : list<a> -> list<a>) match xs Cons(x, xx) -> reverse(xx, \ys -> k(Cons(x, ys))) Nil -> k(Nil) Here, the `k` that is recursively passed depends on the previous `k`. As such `k` should be as large as the input list and can not be stack-allocated?

a1369209993 4y ago

> 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) https://en.wikipedia.org/wiki/UUID#Version_4_(random) Not sure about the other problems, though.

coldtea 4y ago

>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? Couldn't you just prefix or namespace them behind the scenes when you compile each of them with e.g. a hash of the code for the function (or the library they are in), or some similar way to get a unique id/hash/uuid per unit of code (e.g. library, file) that needs to have distinct names of function with other such units across the whole program? You could also keep the association with the original name to show when you print error messages or debug or whatever.