6 ms·

Nice to see a pretty advanced language at frontpage of HN! From what I understand, GRIN does some parts of supercompilation [1] during optimization process. Su

by thesz 2mo ago

Nice to see a pretty advanced language at frontpage of HN! From what I understand, GRIN does some parts of supercompilation [1] during optimization process. Supercompilation can prove equivalence of functional programs [2] modulo termination. So you can have something interesting and useful in almost no time. ;) [1] https://themonadreader.wordpress.com/wp-content/uploads/2014/04/super-final.pdf [2] https://www.researchgate.net/publication/225252220_Proving_the_Equivalence_of_Higher-Order_Terms_by_Means_of_Supercompilation It appears that Fuse does not have user-defined operators. Am I right? If so, it is a major obstacle in creating embedded languages.

codebje 2mo ago
Can you expand on your understanding of GRIN doing parts of supercompilation? As I understand it, GRIN doesn't do any supercompilation; it's a structural transformation optimiser built for functional languages, analyzing program flow across function calls for the whole program at once. As I understand supercompilation, it's an extension of partial evaluation - optimisation is done on a graph of possible execution traces. The downsides should be obvious: execution traces rapidly grow massive, compilation resources grow superlinearly, and there are many cases in which the result is worse than the original. What value would Fuse get from equivalence of terms, do you think?
- thesz 2mo ago
  > Can you expand on your understanding of GRIN doing parts of supercompilation? GRIN, if I am not mistaken, performs partial evaluation. For example, it constrains, for each eval site, a set of tags and set of heaps allocations an eval site can receive. This is close to a partial evaluation step of a supercompilation. GRIN does not perform unification, though, it is not described in the original thesis, but data flow graph matching would be close to unification, reducing code size. > The downsides should be obvious: execution traces rapidly grow massive, compilation resources grow superlinearly, and there are many cases in which the result is worse than the original. This can be constrained. Supercompilation usually gets ran to a fixed point, where no partial evaluation steps can be performed that are not unifiable with previously encountered evaluation steps. But supercompilation can be stopped at any point. I believe you can read on that in Simon Peyton-Jones works, I am unable to find a link to that paper right now, I have troubles with the internet connection. EDIT: here it is: https://simon.peytonjones.org/improving-supercompilation/ https://simon.peytonjones.org/improving-supercompilation/ EDIT: Note "tag-bags," it rhymes with the tag sets of GRIN. > What value would Fuse get from equivalence of terms, do you think? I think that equivalence of terms is an efficient way to verify properties of programs. Myself, I am looking at consensus protocol implementation verification.
  - codebje 2mo ago
    Thanks for the link to SPJ's notes, I'll read that tomorrow. Equivalence of terms is an efficient tool for verification; I suspect that isn't really in the set of goals for Fuse, though.
the_unproven 1mo ago
This is great, I haven't been introduced in the notion of supercompiliation. Reading the papers you've listed and going through GRIN's paper [1] it ticks the boxes in terms of laziness and graph reduction. To keep the implementation of Fuse simple I've decided on using strict evaluation of GRIN programs instead of laziness, with my assumption that it would harder to debug/reason on the program. However, this was one of my next improvements: switching to a lazy evaluation with similar semantics to Haskell programs. > It appears that Fuse does not have user-defined operators. Am I right? Not yet, but I left this mechanism completely open. As operators are defined as type classes with their signs as method definitions. [1] http://nbviewer.jupyter.org/github/grin-compiler/grin/blob/master/papers/The%20GRIN%20Project.pdf

by thesz 2mo ago

codebje 2mo ago

Can you expand on your understanding of GRIN doing parts of supercompilation? As I understand it, GRIN doesn't do any supercompilation; it's a structural transformation optimiser built for functional languages, analyzing program flow across function calls for the whole program at once. As I understand supercompilation, it's an extension of partial evaluation - optimisation is done on a graph of possible execution traces. The downsides should be obvious: execution traces rapidly grow massive, compilation resources grow superlinearly, and there are many cases in which the result is worse than the original. What value would Fuse get from equivalence of terms, do you think?

thesz 2mo ago
> Can you expand on your understanding of GRIN doing parts of supercompilation? GRIN, if I am not mistaken, performs partial evaluation. For example, it constrains, for each eval site, a set of tags and set of heaps allocations an eval site can receive. This is close to a partial evaluation step of a supercompilation. GRIN does not perform unification, though, it is not described in the original thesis, but data flow graph matching would be close to unification, reducing code size. > The downsides should be obvious: execution traces rapidly grow massive, compilation resources grow superlinearly, and there are many cases in which the result is worse than the original. This can be constrained. Supercompilation usually gets ran to a fixed point, where no partial evaluation steps can be performed that are not unifiable with previously encountered evaluation steps. But supercompilation can be stopped at any point. I believe you can read on that in Simon Peyton-Jones works, I am unable to find a link to that paper right now, I have troubles with the internet connection. EDIT: here it is: https://simon.peytonjones.org/improving-supercompilation/ https://simon.peytonjones.org/improving-supercompilation/ EDIT: Note "tag-bags," it rhymes with the tag sets of GRIN. > What value would Fuse get from equivalence of terms, do you think? I think that equivalence of terms is an efficient way to verify properties of programs. Myself, I am looking at consensus protocol implementation verification.
- codebje 2mo ago
  Thanks for the link to SPJ's notes, I'll read that tomorrow. Equivalence of terms is an efficient tool for verification; I suspect that isn't really in the set of goals for Fuse, though.

the_unproven 1mo ago

This is great, I haven't been introduced in the notion of supercompiliation. Reading the papers you've listed and going through GRIN's paper [1] it ticks the boxes in terms of laziness and graph reduction. To keep the implementation of Fuse simple I've decided on using strict evaluation of GRIN programs instead of laziness, with my assumption that it would harder to debug/reason on the program. However, this was one of my next improvements: switching to a lazy evaluation with similar semantics to Haskell programs. > It appears that Fuse does not have user-defined operators. Am I right? Not yet, but I left this mechanism completely open. As operators are defined as type classes with their signs as method definitions. [1] http://nbviewer.jupyter.org/github/grin-compiler/grin/blob/master/papers/The%20GRIN%20Project.pdf