Turing-Complete Two Symbol Regular Languages
A short while back (in February) on the concatenative mailing list Brent Kerby developed a flat two-combinator concatenative language in Joy. This was in response to insightful questions by William Tanksley Jr. This work was inspired by work by Chris Okasaki, J. Fokker and others but followed in the footsteps of Chris Barker’s Jot language which is to the best of my knowledge the first turing-complete two symbol regular language.
I’ll return to Brent’s formulation, since he did all the work of converting the language into a point-free form. Brent’s flat two-combinator basis was:
[B] [A] q == [[B]] [A B] [B] [A] k == A
In Cat this can be constructed as follows:
define q { [dup] dip swap compose [qv] dip }
define k { swap pop eval }
The types for q and k expressed using the Cat type system are:
q : (('A -> 'B) ('C -> 'A) -> ( -> ('A -> 'B) ('C -> 'B)))
k : (('A -> 'B) ('C -> 'D) -> ('C -> 'D))
What is interesting about these two-combinators is that you can construct virtually everything else you want. The following was adapted from Brent’s post and translated into Cat:
define pop { [] k }
define eval { [] q k }
define qv { [] q pop }
define swat { q qv k }
define dip { qv [unit] qv eval qv eval }
define dup { [] q qv swat eval }
define swap { qv dip }
define compose { swap swat }
define rcurry { qv swat }
define curry { swap rcurry }
... ad infinitum
Some names have been changed to distinguish between list and function operations in Cat. The following are how some of the Joy functions map to Cat function operations.
rcurry == cons compose == cat qv == unit i == eval
William Tanksley Jr. also developed an alternative flat two-combinator basis: http://tech.groups.yahoo.com/group/concatenative/message/3197
For those interested in more reading about concatenative languages I’d suggest the following readings:
The Jot definition is cute. Pretty costly when you could just use just * S and K if the only purpose is to avoid parentheses. Burying them inside a form that is used to select one or the other and then apply it interesting but not exactly convenient.
You can help me understand how this translates to Cat, though. My sense is that a combinator like K and the combinator that is the result of (K x) are each usable as operands and might be applied to additional operands of their own at some future point, ultimately achieving (K x) y = x if that happens. So these forms are all first-class results. I’m not sure how this works in Cat because the k definition you exhibit doesn’t seem to be Curried. Is there more transformation to accomplish that?
Comment by orcmid — April 28, 2007 @ 12:26 am
This is a great question. I am actually unsure of the answer, and I’ll need to do some experimentation and get back to you. Brent Kerby’s papers and posts are probably going to be more informative for the time being.
Comment by cdiggins — April 28, 2007 @ 6:49 pm