Very interesting article!

Posted Mar 6, 2025 2:08 UTC (Thu) by bredelings (subscriber, #53082)
Parent article: Two new graph-based functional programming languages

I didn't realize that people were still working on that stuff! I had contented myself with the spineless-tagless-g-machine.

Is there some promise of doing optimal reduction by using interaction nets? I seem to recall that optimal reduction was even better than specializing each function for the data it was applied to, but in practice determining the optional reduction order had too much overhead. But perhaps using interaction nets changes that...

Very interesting article!

Posted Mar 6, 2025 14:08 UTC (Thu) by daroc (editor, #160859) [Link]

So Taelin goes into more detail about that in his discussion of the history of the project, actually. Long story short: interaction nets are not optimal for every possible program, but there is a large subset of programs for which they are provably optimal. Bend, as a language, has a certain number of contortions in its type system to ensure that any programs you write with it fall inside the subset that can be evaluated optimally.

(Specifically, programs that are well-typed with elementary affine types can be executed optimally; they don't require the use of Lamping's oracle, which eliminates the brackets and lenses from his original algorithm.)

And some of Bend's benchmarks do demonstrate an asymptotic speedup compared to the same algorithm written in Haskell and executed either lazily or strictly. The challenge now is improving Bend's code generation, libraries, runtime, etc. in order to make things usefully faster in practice, as opposed to just in theory.