This is the problem I'm having. I've written a Combinatory Logic interpreter in the oscin.es library. It works with combinators (defined as upper-case letters) and unknowns (lower-case letters). You can write things like this:
interpret('Txy')
And get this:
'yx'
I write this as:
interpret('Txy')
//=> 'yx'
Because I've written this in JavaScript:
function T (a) { return function _T (b) {
return b(a)
}}
And there's some magic baked into the unknowns such that y(x)
evaluates to yx
.
It breaks the moment I write something recursive. For example:
interpret('Mx')
//=> 'xx'
interpret('MM')
//=> RangeError: Maximum call stack size exceeded
I want it to return 'MM'.
And much worse:
interpret('Uxy')
//=> y(xxy)
interpret('UUx')
//=> RangeError: Maximum call stack size exceeded
I very much want it to return 'x(UUx)' so I can investigate fixed points. But I don't want to change the behaviour of things like:
interpret('BCTxyz')
//=> 'zxy'