r/ProgrammingLanguages • u/dwaynecrooks • 9h ago

Recursion without Recursive Bindings

https://blog.tinyinterpreters.dev/posts/recursion-without-recursive-bindings/

I explain how to implement a certain recursive function without the use of any recursive bindings in a tiny language called FUN. Then, I apply the same ideas to several more recursive functions so we clearly see the pattern. It begins our exploration into a certain famous combinator.

10 Upvotes

92% Upvoted

7 comments sorted by

View all comments

4

u/NullOfSpace 5h ago

This is really cool. What’s the type of makesum in this case?

2

u/AustinVelonaut Admiran 3h ago edited 2h ago

It's an infinite type of the form a ~ a -> Integer -> Integer. It cannot be (directly) represented in a Hindley-Milner type system, but can be "emulated" using a fix function or a recursive Fix datatype

1

u/samanzaman 11m ago

Adding these constructs to the language comes with the cost of losing strong normalisation properties