Deriving the Y Combinator in 7 Easy Steps.

Here is an easy to remember definition of Y in Scheme:

(define (Y f)
    (f (lambda (x) ((Y f) x))))

An anonymous recursive function that computes the factorial of 10 with the help of Y:

((Y (lambda (f)
  (lambda (n)
(if (= n 0)
    1
    (* n (f (sub1 n)))))))

  10)

=> 3628800

As you can see the combinator is bound to the identifier Y. But if we can bind a function to an identifier, why we need Y in the first place?. We don’t. We need Y when the language don’t allow binding functions to names and as a consequence do not have a convenient way to make recursive calls. Assuming that our implementation of Scheme is very primitive and do not provide these conveniences, we can define the factorial function as:

(((lambda (f)
  (f (lambda (x) ((Y f) x)))) ;; The Y combinator.

    (lambda (f)
      (lambda (n)
        (if (= n 0)
        1
        (* n (f (sub1 n)))))))

  10)

=> 3628800

Started adding Backus' FP primitives to Niue. Progress is slow, sleep is overtaking me :–). A stack language is an apt vehicle for FP as you get function composition and implicit argument passing for free. Here is the famous inner-product example in Niue:

[ transpose '* apply-to-all '+ reduce ] 'inner-product ;

1 2 3 6 5 4 inner-product .
=> 28

This is how the call to inner-product got expanded:

1 2 3 6 5 4
transpose ( => 1 6 2 5 3 4 )
'* apply-to-all ( => (1 * 6) (2 * 5) (3 * 4) => 6 10 12 )
'+ reduce ( => (6 + 10 + 12) => 28 )

An interesting “language implementation exercise”!

Reading the Turing Award lecture(pdf) by John Backus. This is probably one of the most accessible introductions to functional programming.

Did some FP exercises in Python:

# function is defined as inner_product:
# [a,b,c] * [x,y,z] = [(a * x) + (b * y) + (c * z)]
def inner_product(x, y): return reduce(add, map(mult, zip(x, y)))

# where mult and add are defined as:
def mult(x): return x[0] * x[1]
def add(x, y): return x + y
# in a FP language, + and * are first-class functions, so we don't
# need to specially def them.

#test
>>> inner_product([1, 2, 3], [6, 5, 4])
28

Contrast this with the imperative equivalent, where we have to say how to do it, not what to do:

def inner_product(x, y):
  c = 0
  n = len(x)
  for i in range(n):
      c = c + x[i] * y[i]
  return c

The imperative inner_product operates on “state” and one should mentally execute the code to understand it. In contrast, the functional version specifies how we want to transform the data to produce an expected result. This is closer to how we visualize the solution for a given problem. For instance, consider how the FP inner_product evaluated the sample input:

1. Transform the lists into pairs: zip([1, 2, 3], [6, 5, 4]) => [(1,6), (2, 5), (3, 4)]
2. Multiply each pair: map(mult, [(1,6), (2, 5), (3, 4)]) => [6, 10, 12]
3. Add the products to get the final result: reduce(add, [6, 10, 12]) => 28

Here is a function to multiply matrices, in functional style:

def matrix_mult(m, n):
    return map(lambda(e):
               map(lambda(k): reduce(add, map(mult, k)), e), # inner_product() without zip :-)
               cross_zip(m, n))

# where cross_zip is defined as:
def cross_zip(x, y):
    n = zip(*y)
    return map(lambda(e): map(lambda(k): zip(e, k), n), x)

# test
> m = [[1, 2, 3], [4, 5, 6]]
> n = [[10, 20], [30, 40], [50, 60]]
> print matrix_mult(m, n) 
[[220, 280], [490, 640]]
> m = [[0, -1, 2], [4, 11, 2]]
> n = [[3, -1], [1, 2], [6, 1]]
> print matrix_mult(m, n)
[[11, 0], [35, 20]]
> print matrix_mult(n, m)
[[-4, -14, 4], [8, 21, 6], [4, 5, 14]]
> m = [[8, 9], [5, -1]]
> n = [[-2, 3], [4, 0]]
> print matrix_mult(m, n)
[[20, 24], [-14, 15]]

Next step: redefine matrix_mult() directly in terms of inner_product() …