Introduction

Note that the Scheme syntax does not include define as is the case with SIMFOL and Lisp. That is because functions are first class objects in Scheme, meaning that they may be assigned values, passed as parameters, and returned as values by other functions, just like other objects.

Scheme Examples

(set f (lambda(x) (* x x)))
closure


(f 5)
25


((lambda(x y) (+ x (* 2 y))) 6 4)
20


These first two examples show why define is unnecessary and also that, in Scheme, one may evaluate anonymous functions, that is, functions which need not be named by the programmer.

Generic Sorting of two objects

Here, we will see that it is possible to sort 2 objects according to whatever comparison function gets passed in.

(set list2 (lambda(x y) (cons x (cons y '()) )))
closure


(set sort2 (lambda(x y comp) (if (comp x y) (list2 (x y)) (list2 (y x)))))
;; comp is the comparison function to be passed in
closure


(sort2 4 5 <) ;; sort according to less-than
(4 5)


(sort2 4 5 >) ;; or according to greater than
(5 4)

(set length (lambda(l) (if (null? l) 0 (+ 1 (length (cdr l))))))
closure

(sort2 '(1 2 3) '(4 5) (lambda(l1 l2) (< (length l1) (length l2))))
;; sort two lists by having the shorter list appear first, and then the longer
((4 5) (1 2 3))

Defining a mapcar function

Most Lisp implementations include a function called mapcar . This function is used to iterate a given function over a list. That is suppose let (x1 x2 ... xn) represent a list L.
Then (mapcar f L) returns the list (f(x1) f(x2) ... f(xn)) .

Here's how to define mapcar in Scheme:

(set mapcar (lambda(f L) (if (null? L) '() (cons (f (car L)) (mapcar f (cdr L))))))
closure


Defining a function to emulate car-cdr recursion

Because functions in Scheme are first class objects , they may be assigned values, passed as arguments to functions, and returned as values by functions. These values are often lambda expressions. We thus have the ability to program at a higher level by creating functionals , which when given different parameters perform like different functions. This is what we seek to do with combine which we hope to emulate car-cdr recursion. The idea is to abstract away all of the patterns common to those Lisp functions that we wrote to do car-cdr recursion. We see that each has a base case return value for the null list case. Each also applies some method for "building" the result -- whether it be consing, summing, multiplying, etc. Finally, the elements we build with depend on car, so we supply the function of car to be used for this purpose.

We are then left with:

(set combine (lambda(basecase total f)
 (lambda(L)
  (if (null? L) basecase 
      (total  (f (car L)) ( (combine basecase total f) (cdr L)))))))
 

Some examples:

(set length (combine 0 + (lambda(x) 1)))
(set mapc(lambda(f)  (combine '() cons f)))
(set append (lambda(l1 l2)  ( (combine l2 cons (lambda(x) x)) l1)))

Back to the COMS 362 page