[stack] [Fwd: [Factor-talk] Another simple turing-complete subset of Factor]

This was posted to the Factor mailing list, but it's of interest to some
here as well.

If you have no idea what he's talking about, you can catch up if you've
got some interest in combinator calculus, or some desire to develop an
interest. This is how I started, so if it worked for me...

The mandatory page to skim is this:
http://tunes.org/~iepos/joy.html
Don't expect to completely understand it, but do try.

Once you have this, search through the archives of this message group
for postings by iepos (AKA Brent Kerby); he answers some questions here
from time to time.

You may also (or instead) need to find out what the Factor words "bi"
and "bi*" do. There's an intro article at
http://elasticdog.com/2008/12/beginning-factor-shufflers-and-combinators/ , or the Factor documentation is at http://docs.factorcode.org/ (you'll need to know about 'cleave' and 'spread').

Once you've understood what he's talking about, the next question is
whether it's possible to build a two-combinator complete basis (the
smallest possible complete concatenative basis) that includes one of the
spread/cleave/apply combinators.

Fun? Yes. Useful? Not to my knowledge.

-Wm

-------- Forwarded Message --------
From: Slava Pestov <[email protected]>
Reply-to: [email protected]
To: [email protected]
Subject: [Factor-talk] Another simple turing-complete subset of Factor
Date: Sun, 8 Feb 2009 20:42:02 -0600

Hi all,

I realized that the three words bi-curry bi* drop are sufficient to
form a turing complete concatenative language. Here is how we can
build common words out of them,

: dip [ ] bi* ;
: nip [ drop ] dip ;
: call [ [ ] ] dip [ drop ] bi* ;
: bi@ dup bi* ;
: bi bi-curry [ call ] bi@ ;
: dup [ ] [ ] bi ;
: 2bi bi-curry bi ;
: curry [ [ ] ] dip [ ] bi-curry drop ;
: swap [ nip ] [ drop ] 2bi ;

Using drop, dup, swap and dip, any stack shuffle can be formed, and
using curry and call, we can do Church encoding of booleans, and cook
up if, etc.

Slava