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(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