A circular program is a program that depends on its own result. It may be surprising that this works at all, but laziness makes it possible if output becomes available sooner than it is required. In this final episode of 2023, which will be longer than usual (probably 45-60 minutes), we will take a look at several examples of circular programs: the classic yet somewhat contrived RepMin problem, the naming of bound variables in a lambda expression, and breadth-first labelling.
This was a fun episode. I was introduced to breadth first labeling and attribute grammars by Doaitse Swierstra at the Applied Functional Programming summer school in Utrecht. He was an inspiring figure.
The biggest disadvantage of circular programs is that it is very easy to get into infinite loops when you make mistakes. I wish there was an easy way to guarantee statically that circular programs are terminating (perhaps using types).
There is also a recent paper about implementing breadth-first traversals without relying on laziness: https://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/traversals.pdf. Unfortunately, that does not contain any benchmarks.
@jaror Not sure if this is directly related to circular programs, but you may be interested in Aaron Stump’s work on DCS: https://gitlab.com/astump97/dcs/-/blob/main/talks/upenn-fall2023/upenn-talk.pdf?ref_type=heads
