Read Section 1.3: Formulating Abstractions with Higher-Order Functions

Encompasses Lecture 3 & 4

Lambdas exist in scheme (obviously):

(define (plus4 x) (+ x 4))
;; is the same as
(define plus4 (lambda (x) (+ x 4)))

let can be used to bind expressions to names in. Scoping rules apply, so you could create multiple scopes which use the same name. As usual, LEGB scope applies.

let simply replaces the values of the bindings into the body of the function (using applicative order), so bindings can’t refer to other bindings made in the let, since those names aren’t defined while the let is being evaluated. let* nests multiple let definitions to do that:

(let* ((a 3) (b (+ a 5)))
  (* a b))
;; becomes
(let ((a 3))
  (let ((b (+a 5)))
      (* a b)))

That way, a is defined in the body of b.

Since you typically can’t refer to the names of procedures in the body in let statements, that makes recursive function definitions not possible. There’s another variant of let called letrect, which lets you do that.

‘Higher Order’ means:

• Takes procedure as argument or
• Returns procedure as its value

A data type is first class in a language if things of that type can be:

• the value of a variable
• the argument to a procedure
• can be the value returned by a procedure
• can be a member of an aggregate (e.g. array)
• (sometimes included in the definition) can be anonymous - not bound to a name (i.e. lambads)

Widespread use of first class types:

• Basically every language supports numbers as first class.
• Character/Strings are sometimes first class (e.g. not in C).
• Data aggregates are rarely first class (you typically get a pointer to the data structure)
• Not many languages gives you functions as first class, though that’s changing with newer languages.

Procedures as Returned values:

(define (make-adder num)
    (lambda (x) (+ x num)))
make-adder
> ((make-adder 10) 5)
15

Can also define those to names, like:

(define plus7 (make-adder 7))

For a compiler, its relatively easy to allow a function as an argument, but more complicated to allow a function as a return argument. e.g. Pascal allows them as arguments but not return values.