Re: [Chicken-users] Syntax of case expressions

[Alaric Snell-Pym]

On 3 Mar 2008, at 12:33 pm, Tobia Conforto wrote:

> LOL at the S combinator, the most obscure invention of computer
> science (or was it lambda calculus?) to date.  I've never fully
> understood it.

Ah, that's easy...

The idea of combinators, as I understand it, is that you can get rid
of lambdas by rewriting them all into applications of a small set of
basic constant lambdas, which are then known as combinators.

There's a few sets of basic combinators you can work with, but IIRC
the S/K/I set is popular, although I vaguelly recall you can get by
with just two.

Now, this stuff all applies to the *pure* lambda calculus, where the
only type is a closure, and syntax consists merely of lambdas,
symbols that refer to things bound by lambdas, and applications.

We can define S, K, and I as:

(define (I x) x)
(define (K x y) x)
(define (S x y z) (x z (y z)))

Well, pure lambda calculus has only single-arg lambdas, and you
curry, so that's really:

(define ((K x) y) x)
(define (((S x) y) z) (x z (y z)))

Ah yes, you can define I interms of K and S:

(define I ((S K) K))

((S K) K) = (lambda (z) ((K z) (K z)))

((K z) (K z)) = z (by the definition of K). So ((S K) K) = (lambda
(z) z) = I.

"combinator" seems to have come to mean any function whose arguments
are all functions, I gather.

The rest gets hairy, but any lambda expression can, it appears, be
turned into a string of Ss and Ks.

http://en.wikipedia.org/wiki/K_combinator#Completeness_of_the_S-K_basis

http://en.wikipedia.org/wiki/SKI_combinator_calculus

But it implies that any program can be rewritten as a bunch of Ss and
Ks, with nesting of parantheses as required.

This has been (ab)used to produce a fantastically unpleasant
language, Unlambda:

http://en.wikipedia.org/wiki/Unlambda

Here is a typical Unlambda program:

`r```````````.H.e.l.l.o. .w.o.r.l.di

That's Hello World, in case you'd not guessed.

"Unlambda's one flow control construction is call with current
continuation, denoted c"

Heheheh. Feeling ill yet?

> Anyways, I was joking.

Oh, good ;-)

> A shortest code programming contest, on the other hand...

If scored on shortness and clarity - let's call the combination
"conciseness" - I'm all up for that :-)

> Tobia


ABS

--
Alaric Snell-Pym
Work: http://www.snell-systems.co.uk/
Play: http://www.snell-pym.org.uk/alaric/
Blog: http://www.snell-pym.org.uk/?author=4