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