Notes from SKI Calculus talk

[Lyle Kopnicky]

Hi folks,

Here is the walkthrough of the SKI Calculus, in both Markdown & HTML (choose your format). I've also attached some Haskell code to let you play with it.

I've also attached the Racket code, in which I've corrected the Jot parser.

Screencast to follow.

- Lyle

[markus]

Lyle --

> Here is the walkthrough of the SKI Calculus, in both Markdown & HTML
> (choose your format). I've also attached some Haskell code to let you
> play with it.

Just glancing through it while waiting for tests to run, this line (&
the following example) caught my eye:

Voilà! So S (K S) S is our composition operator

I think you may mean S (K S) K, since it looks to me like S (K S) S
would have the wrong shape (I may of course be mistaken).

-- Markus

[Lyle Kopnicky]

Indeed, thanks for pointing that out, Markus! Looks like I had it right in the derivation above, then typoed it.

On Oct 12, 2012 2:51 PM, "markus" <mar...@reality.com> wrote:

[markus]

L --

> Indeed, thanks for pointing that out, Markus! Looks like I had it
> right in the derivation above, then typoed it.

Yeah, and it looks like you had it right beyond that too, so it was just
those too lines. Certainly an easy mistake to make; I suspect it's a
good thing very little production software is written entirely with
combinators. :)

I should have said, by the way, that that's a very nice writeup. It
brought back pleasant memories of last year's ICFPC[1] among other
things.

-- M

[1]
http://icfpc2011.blogspot.jp/2011/06/task-description-contest-starts-now.html

[Bart Massey]

On Friday, October 12, 2012 10:17:21 PM UTC-7, Markus wrote:

Certainly an easy mistake to make; I suspect it's a
good thing very little production software is written entirely with
combinators.  :)

Or at least directly in SKI. Actually, if you build up a nice combinator language in Haskell where the combinators have semantically richer meanings, I've found it's pretty nice. --Bart

[Lyle Kopnicky]

On Fri, Oct 12, 2012 at 10:14 PM, markus <mar...@reality.com> wrote:

I should have said, by the way, that that's a very nice writeup.  It
brought back pleasant memories of last year's ICFPC[1] among other
things.

Thanks, Markus! Yeah, I had taken a peek at that IFCP contest description last year, after it was over, and it sounded fun. Somebody did a great job with the cards.

- Lyle

[Lyle Kopnicky]

 I'd very much like to see that. I'm imagining combinators that swap or uncurry various arguments. I'm thinking of the arrow combinators.

- Lyle

[Tom Harke]

Isn't the point of lambda-lifting to convert arbitrary functional code
into combinators? Didn't compilers first convert your production
software into combinators (at least in the old days)? So you could
take any interesting library, perform the lifting, and adopt the
lifted variant as your combinator library. Not sure it would be
pretty.

> --
> You received this message because you are subscribed to the Google Groups
> "pdxfunc" group.
> To post to this group, send email to pdx...@googlegroups.com.
> To unsubscribe from this group, send email to
> pdxfunc+u...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/pdxfunc?hl=en.



--
Tom Harke
tom....@acm.org

[Lyle Kopnicky]

Thanks for the pointers about lambda-lifting; I had forgotten about that.

It seems to me that your lambda-lifted code will only produce combinators as good as the functions you cared to write.

[Lyle Kopnicky]

Screencast is now available at:

http://www.youtube.com/watch?v=FC6kl_kLFEo

- Lyle

[Tom Harke]

Right. Tying things back to SKI, the amazing thing is not that we can
program with combinators, but that S & K suffice.

[markus]

> Right. Tying things back to SKI, the amazing thing is not that we can
> program with combinators, but that S & K suffice.

True; that is about as amazing as things get. Taking it one more
step--say, if it were found that "I" sufficed--would topple from
"amazing" to "unbelievable."

-- Markus

[David Lazar]

On Tue, Oct 16, 2012 at 4:07 PM, Tom Harke <tom....@gmail.com> wrote:
> Right. Tying things back to SKI, the amazing thing is not that we can
> program with combinators, but that S & K suffice.

It can be simplified further.

Let the X combinator be defined as X = λf. f S (λx y z. x).
With X, we can implement S and K:

S = X (X X)
K = X X

Now we have a Turing-complete language with only one combinator :-).

There's a nice paper about X here:

http://www.staff.science.uu.nl/~fokke101/article/combinat/index.html

Cheers,
David

[Lyle Kopnicky]

Yes, I discussed in the talk how iota is a single combinator that can do it all.

- Lyle 

[Lyle Kopnicky]

Nice, very similar to the iota combinator, where

    iota = \f. f S K

and

    I = iota iota

    K = iota (iota (iota iota))

    S = iota (iota (iota (iota iota)))

- Lyle

[markus]

> > Right. Tying things back to SKI, the amazing thing is not
> that > we can program with combinators, but that S & K
> suffice.

> True; that is about as amazing as things get. Taking it one
> more
> step--say, if it were found that "I" sufficed--would topple
> from
> "amazing" to "unbelievable."

> Yes, I discussed in the talk how iota is a single combinator that can
> do it all.

Iota is certainly impressive, but I stand by my assertion that "I" would
be unbelievable. :)

-- Markus

P.S. Hmmm. Although (my attempts at wit not withstanding) AFAIK the
integer powers of I are powerless to construct structure, it occurs to
me that in an impressive range of domains the fractional powers are a
powerful tool for exploring it. There's probably even enough for a
fairly nice talk in there -- though I can't off hand imagine a venue for
it. :)