Graph reduction

Graph reduction is a technique for implementing functional programming languages. This video shows an interpreter I wrote for a small functional language based on lambda calculus. The interpreter visualises the state of the program's expression graph, and shows the changes that occur to it during evaluation. The interpreter was written in C and OpenGL.

Colour codes are: Red - values (numbers and booleans), Blue - symbols (function references and variables), Cyan - lambda abstractions (function definitions), Green - function applications, Magenta - current reduction node.

Category:

Science & Technology

Tags:

• graph
• reduction
• functional
• programming
• lambda
• calculus

[23Alfred42]

This is amazing! How long did it take to write it in C?

Good job, man!

[kellypmk]

The actual coding took about three days, though I'd previously implemented both the graph reduction and a 2d version of the layout algorithm separately in other projects, so it was mainly an exercise in re-implementing these algorithms and adding OpenGL rendering. I might write a paper on the implementation at some stage.

[daavidb]

@kellypmk Please make a video of the 2d version (or set up a web page). 3d might be "pretty" but 2d would be much more informative for people like me trying to understand how graph reduction works.

[kellypmk]

@daavidb This was just a three-day hack I put together to show off at university open days and similar events. My aim was to make something that looked cool rather than to give a clear and precise explanation of the graph reduction process.

[kellypmk]

@daavidb For a better introduction to graph reduction, check out Simon Peyton Jones's book "The Implementation of Functional Programming Languages"

[kellypmk]

@daavidb You can get this book online for free, but for some reason youtube is giving me errors when I try to post the URL in my response. But if you google the title you will find it.

[baliulia]

totally cool.

[mclaudtt]

Beautiful science. It's nice to see such a visual understanding of theory and also great programming skills. Very glad for you!

[addmoreice]

wonderful visual. would help those who have no knowledge of graph reduction if you explained how applying a functional expression is equivalent to reducing the graph though.