Class 06: Laboratory Session: Scheme

Held Friday, February 5

Summary

• Higher-order functions
• Anonymous functions
• Lab: Scheme
• Assignment 1 (design) due.
• Assignment 2 (design) distributed. Due Friday, February 12, 1999.

Contents

Notes

• You had been asked to think of a more efficient version of reverse. Did anyone come up with one?

Higher-order functions

• One of the more important aspects of functional programming languages is the ability to write so-called higher order functions. These are functions that take functions as arguments or build and return functions.
• Why are higher order functions useful? For a number of reasons, most of which relate to good program design.
• For example, good program design suggest that when you have multiple functions that have a similar structure, you build general functions that extract out the common parts.
• Consider these two related functions (each with an extra helper function):

  ;;; Square a value
  (define (square x) (* x x))
  ;;; Square all the elements of a list
  (define (squareall l)
    (if (null? l) nil
        (cons (square (car l)) (squareall (cdr l)))))
  ;;; Add one to a value
  (define (increment x) (+ x 1))
  ;;; Increment all the elements of a list
  (define (incrementall l)
    (if (null? l) nil
        (cons (increment (car l)) (incrementall (cdr l)))))
  

• What's the ``common part''?
  • We test whether the parameter is null.
  • If so, we return nil.
  • If not, we apply a function to the car and then recurse on the rest.
• So, why not write a function that does just that

  ;;; Apply a function to each element of a list
  (define (applyall fun l)
    (if (null? l) nil
        (cons (fun (car l)) (applyall fun (cdr l)))))
  

• In fact, applyall is so important that a number of variants are included as part of the Scheme standard.
  • map is the most common. It does not have a specified order. It can also work on multiple lists. Read the Scheme report for more information.

Anonymous functions

• Recall that a key attribute of high-level languages is abstraction from the underlying machine.
• One aspect of abstraction is that we don't need to name all of the intermediate values we use.
• For example, in evaluating (2+(X*Y-Z/Q/R)), the machine needs to store the results of intermediate computations in termporary locations. However, the high-level language lets us abstract away from those temporary locations and speak only in terms of the more abstract expression.
• Is there something similar we'd like to do for functions? Yes. Often, we need a function only for inclusion within another function (typically, a higher-order function).
• Many functional languages provide lambda abstractions which let us describe functions without naming them.
• "The function with argument x and body b" is typically written lambda x.b (sorry, no greek characters on my keyboard).
• In Scheme, this would be written (lambda (x) b).
• How is this useful? Suppose we wanted to add two to all of the elements of a list. We can now write

  (map (lambda (x) (+ x 2)) l)
  

• We can also use lambdas to build new functions from old. Consider function composition (normally written with a smaller circle).

  (define (compose f g) (lambda (x) (f (g x))))
  

• Scheme (and Scheme programmers) uses lambdas freely. Note that we can even write function definitions in terms of lambda. The following two definitions are equivalent.

  (define (fun args) body)
  (define fun (lambda (args) body))
  

Lab

You are not required to turn in anything for the lab. However, you are expected to consider as many of these questions as you can. You are encouraged to work with other students. Those who survived the Scheme-based introduction are encouraged to act as TAs.

Use map to square all the elements of some sequence.

Use map to increment all the elements of some sequence.

Write a function, makepairs that, given two lists, makes the list of pairs of elements from those two lists. For example (makepairs '(1 2 3) '(a b c)) should create the list ((1 a) (2 b) (3 c)). You should write makepairs recursive. Do not use map to write this function.

Rewrite makepairs without recursive calls, using map.

Write a function, mappairs, that applies a binary function to each pair in a list of pairs, creating a list of results. jor example, (mappairs * '((1 2) (2 3) (3 4))) should give (2 6 12).

Write a function, sum, that sums the elements in a list. For example, (sum '(1 2 3)) should give 6.

Using all of these functions, write innerProduct that computes the inner product of two vectors.

If you still have time, start work on assignment two.

History

• Created Tuesday, January 19, 1999 as a blank outline.
• Filled in some details on Wednesday, February 3, 1999.
• Filled in some more details on Friday, February 5, 1999.