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

## William Tanksley — 2009-02-09 17:29:48

    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 <slava@...>

    Reply-to: factor-talk@...

    To: factor-talk@...

    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