Haskell

3 readers

1 users here now

**The Haskell programming language community.** Daily news and info about all things Haskell related: practical stuff, theory, types, libraries, jobs, patches, releases, events and conferences and more... ### Links - Get Started with Haskell

founded 1 year ago

[Well-Typed] The Haskell Unfolder Episode 17: circular programs (www.youtube.com)

submitted 11 months ago by jaror@kbin.social to c/haskell@kbin.social

2 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] jaror@kbin.social 1 points 11 months ago (1 children)

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.

[–] SageBinder@mathstodon.xyz 1 points 11 months ago

@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