Is ```sii``sii
the smallest Unlambda program that doesn't halt?
In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (call/cc) and $D$ (delay)? Is it $SII(SII)$?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs ```sii``sii
the smallest Unlambda program that doesn't halt?
In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (call/cc) and $D$ (delay)? Is it $SII(SII)$?
Intuitively speaking, a non-terminating program needs either:
Unlambda lacks a combinator of the first type, but has two combinators of the second type: $S$ and $C$.
In the SKI-calculus, following the intuition above, a non-terminating term needs to somehow apply $S$ with the first argument being $S$. So it would have to be of the form $Swx(Syz)$, i.e. ```swx``syz
in Unlambda). This suggests that $SII(SII)$ is minimal. (Note that I've only given an intuition, I haven't proved it!)
However Unlambda also includes c
(call/cc), and this is a very powerful operator in terms of replicating its argument. A term of the form $Cfx$ applies its own continuation $\phi$ to the function $f$; if $f \phi$ itself arranges not to destroy its context, then the term won't terminate. For example, $CI(CI)$ is non-terminating (exercise: work it out). ``ci`ci
is known as the Yin-Yang puzzle. To see it in action, make it print a trace of its execution: ``.@`ci`.*`ci
.
Because $S$ requires 3 arguments and $C$ requires 2, intuitively, there can't be a non-terminating 3-combinator term, so the 4-combinator term we found above is minimal.
Here's a quick-and-dirty bash script that enumerates all possible Unlambda terms of up to 4 combinators (i.e. 3 application nodes) and prints out the ones that take more than 1 second to terminate. I omitted the I/O primitives which reduce like i
, as well as e
(exit) which obviously wouldn't help to make a program non-terminating. This is an experimental way to list the non-terminating terms — the terms not printed here are guaranteed to be terminating (assuming a correct implementation), and the terms printed here are likely to be non-terminating.
for a in s k i c d v; do
for b in s k i c d v; do
for c in s k i c d v; do
for d in s k i c d v; do
for p in @$a$b @@$a$b$c @$a@$b$c @@@$a$b$c$d @@$a@$b$c$d @@$a$b@$c$d @$a@@$b$c$d @$a@$b@$c$d; do
p=${p//\@/\`}
timeout 1 unlambda <<<$p || echo $p
done
done
done
done
done
The result of the experiment is that only the following terms are potentially non-terminating:
```scc?
``c?`c?
where each ?
can be independently i
, c
or d
. In other words, the non-terminating combinator terms are $SCCx$ and $Cx(Cy)$ (or so the experiment suggests, but it happens to be correct).
Exercises: