Liah Hansen about

Scheme - Sum of Biggest Squares, Lambda Calculus (Noisebridge Notes)

I just got home from the Noisebridge Schemers meetup. We started off talking about problem 1.2 (1985 version) / 1.3 (1996 version). Here's the problem:

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers

Here is our first implementation:

(define ssq2(a, b, c)
  (and (a<=b) (a<=c))(sum_of_squares b c)
  (and (b<=a) (b<=c))(sum_of_squares a c)
  (and (c<=a) (c<=b))(sum_of_squares a b)
)

We talked about how writing this function in scheme involves thinking in a different way than if we were to write it in Ruby. In Ruby we might sort the arguments using a sort method, then eliminate the smallest one. Ruby gives us sort and min/max methods for free. In Scheme it isn't quite so easy. In Scheme we think about the problem more in terms of a tree whereas in Ruby we manipulate our data in memory using methods. To illustrate this point, we considered the following code which is how we might think about the problem in a Rubyish way. It assumes that there is a sort method that takes a greater than or less than symbol to determine whether to sort ascending or descending.

(define(ssq2 a b c)
  (+ (* (car(sort(list a b c) >)
        (car(sort(list a b c) >)))
      (* car(cdr(sort(list a b c) >)))
         (car(cdr(sort(list a b c) >)))))

Here is my implementation in Ruby using a Scheme-like design.

def sum_square_two_biggest(a,b,c)
  if a<=b && a<=c
    sum_of_squares b c
  elsif b<=c && b<=a
    sum_of_squares c a
  else
    sum_of_squares a b
  end 
end

This is an asci art tree that demonstrates how a Schemer might think about the problem. The left branches are the result of the node being true.

                a<b
              /      \
            /           \
          |                |   
        b<c                  a<c     
      |     |              |       |
      |     a<c            |       c<b
      |     |    \         |     |      |      
   a<b<c   a<c<b   c<a<b  b<a<c   c<b<a   b<c<a   

We talked about functional programing and how using set! breaks functional programming. Don't use set! if you want to use applicative evaluation as it forces evaluation immediately. On the other hand, using define expands into a lambda expression and does not break functional programming rules.

Lambda example:

((lambda(n) (+ n 1)) 41)

=> 42

Lambda calculus example:

(λx|x) a
=> a

(λx|x)(λy|yy)
=> (λy|yy)
(λy|yy)(λx|x)
=> (λx|x)(λx|x)
=> (λx|x)

Book recommendation for lambda calculus: algorithmics by david harel

blog comments powered by Disqus