'An Introduction to Combinator Compilers and Graph Reduction Machines' by David Graunke

Graph reducing interpreters combined with compilation to combinators creates a "virtual machine" compilation target for pure lazy functional programs that is extremely concise, simple in its semantics, and naturally parallelizable. In their simple forms these techniques are a useful introduction to compiling and interpeting functional languages. In much more sophisticated forms, they illustrate how large-scale compilers are implemented in used in languages like Idris.

We'll walk through the process of compiling programs in the lambda calculus to pure combinators and a simple implementation of the most straightforward graph reduction algorithm. With that context, we'll look at the history of graph reduction, from a surge of interest and excitement in the 80s and 90s to serious reservations in the 2000s. We'll look at concrete examples of combinator compilation and graph reduction, and compare with alternative techniques in Haskell's Spineless Tagless G-Machine.

[DunktLOL]

Thanks for this presentation, very content dense but digestible enough. Here from Bend/HVM

[gralha_]

I've recently seen a optimal reduction VM that avoids using graphs and is able to achieve much better performance (close to C levels), called HVM.
It also supports easy parallelization, just like the graph reduction VMs mentioned here. It's real promising and looks to me like the future of the types of tech explained in this video.

[IanDutfield]

Inspirational. Thanks. It's still abstract, weird, and yet amazing. I like how you addressed the implementations and the challenges. I think there is more to be discovered here for those that dare to push forward.

[kenc.]

Super interesting talk David! Thanks for putting it together. I came across the Reduceron paper last year and was intrigued too. I can't shake the feeling that there is a much better hardware solution waiting for us somewhere in the future, but I'm a software guy! I'm definitely going to spend some more time looking into combinators though. Cheers!

[johnwerner]

Thanks great lecture. You're a natural teacher. I'm much closer to getting the SKI calculus.

[derelbenkoenig]

Around 26:00 In the graph for the expression (S + I 5) were the positions of the (+) and the (I) flipped or am I just confused?