PNLC

A toy functional language 2026-02-15

Project Readme • Project Files • GitHub Repo

PNLC is λ‑calculus in prefix notation plus normal-order semantics plus continuation-based I/O plus a small prelude. Arguably, the prelude is the language, because without it you’re left with little more than a λ‑calculus interpreter. The readme goes into more detail.

I/O works using continuations and I’m reasonably confident it’s pure. The top-level term must evaluate to an action wrapping a continuation that will become the new top-level term after the interpreter performs the action. A program terminates by evaluating to a special action that expects no continuation. In any case, the prelude provides pure monadic wrappers for use in user programs.

At some point I went down a rabbit hole on recursion schemes. “unfoldr is dual to foldr” they say, but looking at their types the duality is not immediately apparent.

foldr :: (a -> b -> b) -> b -> [a] -> b
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

Well, foldr is the list catamorphism and unfoldr is the list anamorphism. Looking at their types ana and cata are evidently dual, and it turns out that foldr and unfoldr are pragmatic specializations of them to lists.

cata :: Functor f => (f a -> a) -> Fix f -> a
ana :: Functor f => (a -> f a) -> a -> Fix f
data ListF a b = Cons a b | Nil deriving Functor -- satisfying Fix (ListF a) ~= [a]
foldr   :: (ListF a b -> b) -> Fix (ListF a) -> b ~= (Maybe (a, b) -> b) -> [a] -> b ~= (a -> b -> b) -> b -> [a] -> b
unfoldr :: (b -> ListF a b) -> b -> Fix (ListF a) ~= (b -> Maybe (a, b)) -> b -> [a]