# Typed Combinatoral Calculus

## Christopher Diggins — 2006-12-20 20:51:11

    I am still wrestling with establishing the correct types for the

    classic combinatory logic combinators (i.e. S,K,I,W,B,C,M, etc.). So

    far I am torn between two approaches to implementing these

    combinators, one being the method used by Brent Kerby in his paper

    http://tunes.org/~iepos/joy.html where

      [A] i == A

      [B] [A] k == A

      [C] [B] [A] s == [[C] B] [C] A

      ...

    And an alternative system where:

      A i == A

      B [A] k == A

      C [B] [A] s == [[C] B] [C] A

      ...

    I have posted the problem on Lambda-the-Ultimate.org (

    http://lambda-the-ultimate.org/node/1922 )

    Any thoughts or ideas about which system I should choose would be much welcome.

    --

    http://www.cdiggins.com

## William Tanksley, Jr — 2006-12-20 21:44:16

    Christopher Diggins <cdiggins@...> wrote:

     > I am still wrestling with establishing the correct types for the

    > classic combinatory logic combinators (i.e. S,K,I,W,B,C,M, etc.). So

     Since you seem to understand combinator notation, I wonder if you

    could answer a question I've been struggling with.

    In the paper at

    http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03 (html

    abstract with a link to a postscript), the author mentions an 'X

    combinator' and describes A and P combinators, which together make up

    a complete combinatorial basis with the minimal possible number of

    combinators.

    My question: what are the "stack effects" of the A, P, and/or X

    combinators (as described in Okasaki's paper), expressed in Brent's

    notation? If I knew that, I'd be able to implement it, and thereby

    could express a concatenative language in binary notation. Obviously

    the Fields medal would be mine, as would a Nobel Peace prize. I'd be

    sure to mention you vaguely in my acceptance speeches.

    Many thanks to anyone who can help!

     > http://www.cdiggins.com

     -Billy

## William Tanksley, Jr — 2006-12-20 21:32:07

    Christopher Diggins <cdiggins@...> wrote:

     > I am still wrestling with establishing the correct types for the

    > classic combinatory logic combinators (i.e. S,K,I,W,B,C,M, etc.). So

    > far I am torn between two approaches to implementing these

    > combinators, one being the method used by Brent Kerby in his paper

    > http://tunes.org/~iepos/joy.html where

    >   [A] i == A

    >   [B] [A] k == A

    >   [C] [B] [A] s == [[C] B] [C] A

    >   ...

    > And an alternative system where:

    >   A i == A

    >   B [A] k == A

    >   C [B] [A] s == [[C] B] [C] A

    >   ...

     If I read your notation right, in the alternate system the i

    combinator is a no-op. Is that right?

    Note that Brent's notation is slightly different, a fact that confused

    me when reading your email; none of his combinator notations use

    non-quoted arguments. I believe that's because his emphasis was on

    transparent quotations: his combinators cannot take apart lists, so

    mathematical reductions can be done inside quotations without ever

    affecting the results of a computation. The notation used in your

    alternate system implies that there are two types of entity:

    don't-care and quotation.

    It also seems to me that your K combinator and his K combinator do the

    same thing -- only the type of the dropped parameter is different.

    Your S combinators are different, but I don't know how to analyze the

    differences (not only are the types different, but the resulting list

    structure appears to be different as well).

     > Any thoughts or ideas about which system I should choose would be much welcome.

     Tough to say. I think I'd go for 'i' being the execution combinator,

    since it's that way in Joy. If that argument didn't carry any weight

    :-), I'd claim not to like explicit no-op instructions.

     > http://www.cdiggins.com

     -Billy

## Christopher Diggins — 2006-12-20 23:16:31

    On 12/20/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Christopher Diggins <cdiggins@...> wrote:

    > > I am still wrestling with establishing the correct types for the

    > > classic combinatory logic combinators (i.e. S,K,I,W,B,C,M, etc.). So

    > > far I am torn between two approaches to implementing these

    > > combinators, one being the method used by Brent Kerby in his paper

    > > http://tunes.org/~iepos/joy.html where

    >

    > > [A] i == A

    > > [B] [A] k == A

    > > [C] [B] [A] s == [[C] B] [C] A

    > > ...

    > > And an alternative system where:

    > > A i == A

    > > B [A] k == A

    > > C [B] [A] s == [[C] B] [C] A

    > > ...

    >

    > If I read your notation right, in the alternate system the i

    > combinator is a no-op. Is that right?

    >

    > Note that Brent's notation is slightly different, a fact that confused

    > me when reading your email; none of his combinator notations use

    > non-quoted arguments. I believe that's because his emphasis was on

    > transparent quotations: his combinators cannot take apart lists, so

    > mathematical reductions can be done inside quotations without ever

    > affecting the results of a computation. The notation used in your

    > alternate system implies that there are two types of entity:

    > don't-care and quotation.

     I see. So it is perhaps a disctinction born out of practical reasons?

     > It also seems to me that your K combinator and his K combinator do the

    > same thing -- only the type of the dropped parameter is different.

     Good catch. That was my mistake, also my "s" definition was wrong. So

    here is my corrected proposed alternative:

    A i == A

    B A k == A

    C [B] [A] s == [C B] C A

     > Your S combinators are different, but I don't know how to analyze the

    > differences (not only are the types different, but the resulting list

    > structure appears to be different as well).

     Corrected it above.

     > > Any thoughts or ideas about which system I should choose would be much welcome.

    >

    > Tough to say. I think I'd go for 'i' being the execution combinator,

    > since it's that way in Joy.

     In Cat I am considering having two execution operators:

    apply : ('a ('a -> 'b) -> 'b)

    eval : ('A ('A -> 'B) -> 'B)

    Notice the new type variable labeling scheme based on the ML syntax

    and a suggestion of yours. Uppercase variables represent stacks, while

    lowercase variables represent single types.

    I am concerned that the i combinator should behave differently and

    would thus confuse the meaning of i as an execution operator. Manfred

    said that "i" stood for interpret, but I wonder if he intended it to

    also stand for the "i" combinator.

     > If that argument didn't carry any weight

    > :-), I'd claim not to like explicit no-op instructions.

     In a typed language there are bound to be different kinds of no-ops.

    There is the true nullary no-op:

    define nullop : ( -> ) { [] eval }

    But there is also the unary no-op, aka the identity function:

    define id : ('a -> 'a) { [] eval }

    The difference is that nullop can be evaluated with an empty stack,

    but id can't. A subtle effect of this difference is that "id" could be

    replaced with "dup pop" without changing the meaning of a program, but

    nullop could not.

    In general though so far it appears that the two systems are different

    but equally valid.

## Christopher Diggins — 2006-12-21 06:07:50

    I am still struggling with the different notations. I am actually interested

    in the problem that you proposed and am looking into a solution. In the mean

    time, I've started making a chart of various combinators and their

    implementations in Joy. It is currently under development but I've posted it

    nonetheless at http://www.fundamentals-of-programming.com/combinators.html in

    case it may help you solve your problem. I figure once I fill in all the

    gaps, the solutions should start becoming apparent.

    Are you aware of Jot and Iota? http://ling.ucsd.edu/~barker/Iota/

    They are both two symbol (i.e. binary) flat languages. Perhaps just writing

    either or in postfix would be the solution to your problem?

    If II hope this helps. I'll keep you informed of my progress.

     On 12/20/06, William Tanksley, Jr <wtanksleyjr@...> wrote:

    >

    >   Christopher Diggins <cdiggins@... <cdiggins%40gmail.com>> wrote:

    > > I am still wrestling with establishing the correct types for the

    > > classic combinatory logic combinators (i.e. S,K,I,W,B,C,M, etc.). So

    >

    > Since you seem to understand combinator notation, I wonder if you

    > could answer a question I've been struggling with.

    >

    > In the paper at

    > http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp03 (html

    > abstract with a link to a postscript), the author mentions an 'X

    > combinator' and describes A and P combinators, which together make up

    > a complete combinatorial basis with the minimal possible number of

    > combinators.

    >

    > My question: what are the "stack effects" of the A, P, and/or X

    > combinators (as described in Okasaki's paper), expressed in Brent's

    > notation? If I knew that, I'd be able to implement it, and thereby

    > could express a concatenative language in binary notation. Obviously

    > the Fields medal would be mine, as would a Nobel Peace prize. I'd be

    > sure to mention you vaguely in my acceptance speeches.

    >

    > Many thanks to anyone who can help!

    >

    > > http://www.cdiggins.com

    >

    > -Billy

    >

    >

    --

    http://www.cdiggins.com

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2006-12-21 16:23:09

    Christopher Diggins <cdiggins@...> wrote:

     > I am still struggling with the different notations. I am actually interested

    > in the problem that you proposed and am looking into a solution. In the mean

    > time, I've started making a chart of various combinators and their

    > implementations in Joy. It is currently under development but I've posted it

    > nonetheless at http://www.fundamentals-of-programming.com/combinators.html in

    > case it may help you solve your problem. I figure once I fill in all the

    > gaps, the solutions should start becoming apparent.

     Cool!

     > Are you aware of Jot and Iota? http://ling.ucsd.edu/~barker/Iota/

    > They are both two symbol (i.e. binary) flat languages. Perhaps just writing

    > either or in postfix would be the solution to your problem?

     Yes, I saw them... I tried to figure them out, but I have no clue how

    to read the notation that describes them. It just makes no sense to

    me. Jot is close to what I want, but of course isn't concatenative,

    and because I can't read its notation I can't figure out what its

    stack effect should be.

     > If II hope this helps. I'll keep you informed of my progress.

     Thanks!

    -Billy