If you have not already done so, please take the quiz before continuing with lab.

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention. There are more exercises here than most students will be able to do during lab, so feel free to skip the many challenge problems.

Reminder: While we've looked at how to define filter, map, foldr, etc., many of these are also built-in to DrScheme. Feel free to use them.

lambda

Let's start with some review.

(lambda (x …) body) creates a function, just like (define (f x …) body). However, the latter form also names the function.

In fact, we can separate the naming and definition of a function: 

      (define (f x y) (+ x y))

      =

      (define f (lambda (x y) (+ x y)))

Neither form is better style, but you should understand this equivalence.

Exercises
  1. Evaluate each of the following. Try to understand each example before using DrScheme. Use DrScheme's stepper to help you. 
    (lambda (x) (+ 3 x))
((lambda (x) (+ 3 x)) 5)

(lambda (x) (+ 3 5))
((lambda (x) (+ 3 5)) 'silly)

(lambda (x) x)
((lambda (x) x) 5)

; Which x is which?
(define strange
    (lambda (x)
        (x (lambda (x) x))))
(strange (lambda (x) x))
  2. In last week's lab, we defined 
    (define (double-num n) (* 2 n))
(define (double-nums a-lon) (map double-num a-lon))
    Define double-nums using lambda, without any named function like double-num.
  3. Define a function make-greater-filter that, given a number n, returns another function that, given a list of numbers, will return all those greater than n. 
    (define greater-6-filter (make-greater-filter 6))
(greater-6-filter (list 4 10 2 13))
(greater-6-filter (list 162 23 -1 7 0))
  4. Challenge: What do the following functions do, how can you use them, and what are their types? 
    (define curry
    (lambda (f)
        (lambda (x)
            (lambda (y)
                (f x y)))))
(define uncurry
    (lambda (f)
        (lambda (x y)
            ((f x) y))))
  5. Challenge: What does the following do? Try stepping through it. 
    (define brainteaser
    (lambda (a-lon)
        (foldr a-lon
               (lambda (num k) (lambda (n) (k (+ num n))))
               (lambda (n) n))))
((brainteaser (list 2 4 6 8)) 0)
    Aaaack!!! Why would anyone do this?!? Take COMP 311 and learn about continuations and why they can be useful.

It doesn't seem possible to define a recursive function without giving it a name. But you can! However, it's quite tricky. See COMP 311 for details.

Derivatives

Last lab focused on abstracting list-processing functions. But, the ideas of abstractions are not limited to any one type of data or operation. This week, we'll focus more on common mathematical functions.

One common mathematical problem is to find the slop of some function f and some point x. Given f, its derivative f′ is a function such that f′(x) is the slope of f at x. Finding the derivative of a function exactly in symbolic form is somewhat difficult, and is part of calculus. Finding a numeric approximation of the derivative is much simpler, and what we'll do.

Consider the following picture:

Given f and x, the value of the derivative can be approximated as the slope between f(x-eps) and f(x+eps), assuming eps is a small value. I.e., we can use the equation

(f(x+eps) - f(x-eps)) / (2×eps).
Exercises
  1. Use that equation to define 
    ; deriv-at-point : (num -> num) num num -> num
(define (deriv-at-point f x eps) …)
  2. We might want to evaluate the same f′ at many different x values. Choose a small value for eps, and develop the program 
    ; deriv : (num -> num) -> (num -> num)
(define (deriv f) …)

; And then we can use it:
(define g (deriv f))
(g 3)
(g 10)
(g 5)
    Write a version using a locally named function and another version with lambda and no local.

Taylor Series

Read sections 23.1 and 23.3 of the online textbook. The code you'll use in lab is provided below and is a slight modification of that in the book. 

      ; series : natural (natural -> number) -> number
      ; Returns the sum of the first n numbers in the sequence a-term, i.e.,
      ; (+ (a-term 0) … (a-term (sub1 n))).
      (define (series n a-term)
        (cond
          [(= n 0) (a-term n)]
          [else (+ (a-term n) (series (- n 1) a-term))]))

      ; e-power : natural -> number
      ; Returns the x-th power of the constant e, as approximated by n terms of
      ; a Taylor series.
      (define (e-power x n)
        (local ((define (e-taylor i)
                   (exact->inexact (/ (expt x i) (! i))))
                (define (! n)
                   (cond
                      [(= n 0) 1]
                      [else (* n (! (sub1 n)))])))
            (series n e-taylor)))
Exercises
  1. Experiment with using (e-power x n), for various values of n, and compare the results with (expt e x). (Note that e is a built-in constant.)
  2. Step through (e-power x 2), for some x, to make sure you understand the computation. (Skip over the less interesting steps like the factorial computation.)
  3. e-power's body locally defines two named functions. Rewrite this body to change one or both to unnamed lambda functions. Make sure it still works. Is is possible to unname both local functions?
  4. Change e-power to use lambda even more, using the equality 
    (define (f args) body)
=
(define f (lambda (args) body))
    Make sure it still works.
  5. Develop the function my-cos, which computes the Taylor series for the cosine It will be similar to the code for e-power. Compare your results to the built-in cos. The mathematical series is
    cos(x) = x0/0! - x2/2! + x4/4! + …
    Hint: While mathematicians use (-1)i to compute the sign; programmers can use cond.
  6. Modify your previous definition to use lambda where appropriate.

If we end up wanting to define lots of Taylor series, we might prefer to have an abstraction specifically "tailored" for Taylor series, similar to series. The difference is that to describe each term, we provide a function of two arguments, a number x and index i. Of course, we still need to provide an x sometime, so the result of the function is itself a function of x. 

      ; taylor-series : natural (number natural -> number) -> (number -> number)
      ; Returns a function to compute the sum of the first n numbers in the
      ; sequence a-term, i.e.,
      ; (+ (a-term x 0) … (a-term x (sub1 n))).
      (define (taylor-series n a-term)
         …)
Exercises
The answers to both of these are fairly simple. The difficulty is in the thought process.
  1. Semi-challenge: Define taylor-series in the style of the definition of series.
  2. Semi-challenge: Define taylor-series using series.