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.
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.
It's called Curried Function Shorthand and described here.
