define a form as function name?

Question

I'd like to know what this code means in Scheme:

(define ((K x) y) x)

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

The whole file is here.

Is this legal Scheme? Is (K x) a parametrized function, something like generic functions in Java? I looked up the MIT Scheme reference, there seems to be nothing mentioned for definition of this kind.

Answer 1

Trying it in MIT Scheme works

(define ((K x) y) x)
;Value: k

((k 3) 4)
;Value: 3

Apparently, these are the definitions for K and S combinators from a combinatorial logic SKI calculus.

We can define the same function explicitly,

(define k (lambda (x) (lambda (y) x)))
;Value: k

((k 3) 4)
;Value: 3

Apparently, MIT-Scheme does that for us, just as in case of regular definitions like (define (fun foo) bar) being translated to (define fun (lambda (foo) bar)).

The S combinator would be defined explicitly as

(define S (lambda (x) (lambda (y) (lambda (z) 
  ((x z) (y z))))))

(define ((add a) b) (+ a b))
;Value: add

(define (add1 a) (+ a 1))
;Value: add1

(((s add) add1) 3)
;Value: 7

This is how currying languages (like e.g. Haskell) work, where every function is a function of one argument. Haskell is very close to the combinatorial logic in that respect, there's no parentheses used at all, and we can write the same definitions simply as

_K x y = x
_S x y z = x z (y z)

So that _S (+) (1+) 3 produces 7.