Functional Programming - 3. A Simple Subset of Scheme

Functional Programming

3. A Simple Subset of Scheme

3.1 Scheme

Scheme is a language developed by Guy L. Steele and Gerald Jay Sussman of MIT over the (1975-1980) period (See History of the Scheme programming language). It was influenced by Lisp, the premier AI language of the time.

The standard text for Scheme is The Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman. For years it was the introductory programming text for MIT and many other top CS schools.

Scheme has evolved into the Racket family of languages, which is what we are using for this course.

3.2 Restricted Scheme

We now define a restricted subset of Scheme that is a rough analog of the untyped lambda calculus (to be discussed later). The reason for doing this is that we want to force ourselves to understand the low-level nature of the language, and then implement the features that are used in regular programming. We will use the full Scheme/Racket language later.

Restricted Scheme consists of exactly the following permitted terms. In the definitons below,

<id> stands for any valid identifier
<term> stands for any valid term, an <id> is a term
<lambda-term> stands for any valid lambda abstraction, or identifier bound to a lambda abstraction, or builtin operator for the lists or integers.
<list> stands for a list

In restricted Scheme you have only the following programming constructs:

Definition: (define <id> <term>) binds the identifier <id> to the value of <term> so that use of <id> is equivalent to that value. Definitions are part of the environment, and may not appear inside terms.
Abstraction: (lambda (<id-1> <id-2> ... <id-n>) <term>) binds all the free occurrences of the n (possibly 0) identifiers <id-1> <id-2> ... <id-n> in <term> and returns an n-ary function.
Application: (<n-ary-lambda-term> <term-1> <term-2> ... <term-n>) is is the term resulting from substituting <term-1> <term-2> ... <term-n> for the formal parameters of <n-ary-lambda-term>. Note, application evaluates each term before substitution.
Boolean: There are two logical values # t (true) and # f (false).
(not <term>) returns the negation of the value of <term>.
(and <term-1> <term-2> ... <term-n>) is logical and (conjunction)
(or <term-1> <term-2> ... <term-n>) is logical or (disjunction)
Predicates, which by convention have names ending in ?, return Boolean values.
Conditional: (if <test> <consequent> <alternate>) has the value <consequent> if <test> is true (# t) and the value <alternate> if <test> is false (# f). Note, conditional is a special form, and the consequent and alternate are not evaluated before evaluating <test>.
Lists:
- List Construction: Lists are defined recusively. The constant '() or (quote ()) is the empty list. To construct larger lists we use cons:
  (cons <term> <list>) is the list consisting of <term> prepended to the front of the list <list>.
- List Operations: If <list> is non-empty, then
  (first <list>) has the value of the first element of the list.
  (rest <list>) has the value of the list without the first element.
  (note first and rest are also called car and cdr, respectively).
  Axiom: (cons (first L) (rest L)) is the same as L for non-empty L.
- Predicates:
  Listness: (list? <obj>) is true if <obj> is a list
  Emptyness: (null? <list>) is true if <list> is the empty list. It is false if <list> is not empty OR not a list (be careful).
Integers:
- Integer constants: represented as signed decimal numbers.
- Integer operators: +, -, *, quotient, remainder, modulo, min, max. Note, no division / as it does not guarantee an integer result.
- Comparison predicates: =, <, >, <=, >=.
- Numberness: (number? <obj>) returns true if <obj> is a number.
Quotation: (quote <external-representation>) constructs the value that has the given external representation. Quote is a shorthand for the actual value that would result if we provided the term that constructed the value. For example, (quote (1 2 3)) has the same value as (cons 1 (cons 2 (cons 3 '())
Evaluation: (eval (quote <term>)) computes the value of <term> in the current environment. A different environment can be supplied, but we need not worry about that here.

The term is not often given as a quoted constant, as in (eval '( (lambda (x) (+ x x)) 3)) but instead is constructed explicitly as in (eval (cons (lambda (x) (+ x x)) '(3)) ) which is how we can write programs that generate code and evaluate it dynamically.

3.3 Some Illustrative Examples

Try these inside the Scheme environment, observe what happens, and make sure you understand why. It cannot be stressed too much: it is important to actually sit down and experiment with the language. code/LambdaScheme/LambdaScheme01.rkt

#lang racket

; Integers:

(quotient 9 4)

(remainder 9 4)

(modulo 9 5)

(modulo 9 -4)

(modulo -9 5)

(modulo -9 -4)

(= 2 3)

(not (= 2 3))

(< 3 4)

; Lists:

(define L '(1 2 3))

(first L)

(car L)

(rest L)

(cdr L)

(first (rest L))

(car (cdr L))

(cadr L)

(cons (first L) (rest L))

(cons 42 L)

(cons L L)

(cons 1 1)

(cons 1 (cons 2 (cons 3 '())))

(cons (cons (cons (cons 1 '()) '()) '()) '())

(list? L)

(null? L)

(null? (rest '(2)))

(list? 1)

(null? 1)

(define LL '( (1 2 3) (4 5 6 (7 8) )))

(car (car LL))

(caar LL)

(car (cdr LL))

(cadr LL)

(car (cdr (cdr LL)))

(caddr LL)

(cdr (cdr (car (cdr LL))))

(cddadr LL)

(car (cdr (cdr (car (cdr LL)))))

(caddadr LL)

; If you want the list consisting of the value of a and the value of b, then you

; need to assemble it. So you start with the empty list

'()

; (this is a constant, so has a quote). Then you use the inductive definition

; of list, and build the list containing b, by doing

(cons b '())

; finally you add a to the front, by doing

(cons a (cons b '()))

; Definition and Quotation:

(quote 1)

'1

(quote ())

'()

(define X (+ 1 2))

X

(define Y '(+ 1 2))

Y

(eval Y)

; Abstraction:

; the constant function of no arguments

(define f1 (lambda () 42))

f1

(f1)

; the unary function that doubles its argument

(define f2 (lambda (x) (+ x x)))

(f2 3)

; the identity function

(define ident (lambda (x) x))

(ident 42)

; the function that builds a list around its argument

(define list1 (lambda (x) (cons x '()) ) )

(list1 3)

; a binary function that does addition

(define add (lambda (x y) (+ x y)))

(add 40 2)

; Scheme doesn't do Currying automatically

(add 40)

; (addn n) builds a function that adds n to it's argument

(define addn (lambda (n) (lambda (x) (+ x n))))

addn

(addn 3)

(define plus3 (addn 3))

plus3

(plus3 40)

; Conditionals and Recursion:

; in an imperative language, we would do something like this to

; find the min of a list

; def lmin(L):

; min_val = None

; for x in L:

; if min_val is None or x < min_val:

; min_val = x

; return min_val

; functionally, we do it like this

; try tracing it in DrRacket

(define lmin (lambda (L)

(if (null? (rest L))

(first L)

(min (first L) (lmin (rest L)))

)))

(lmin '(1 -3 4))

; sum over a list: note the base case, and induction/recursion

(define lsum (lambda (L)

(if (null? L)

0

(+ (first L) (lsum (rest L)))

)))

(lsum '(1 -3 4))

; Evaluation

(quote (+ 3 4))

(eval (quote (+ 3 4))

(define exp (cons (lambda (x) (+ x x)) '(3)))

exp

(eval exp)

3.4 Scheme Naming Conventions

Every language has it's conventions for naming. The Scheme ones are a bit richer since identifiers can contain special characters. These conventions are taken from the Scheme r6rs document (part of the plt DrScheme distribution).

By convention, the names of procedures that store values into previously allocated locations end in ! (bang or exclamation). For example, update-previous!. Note, we do not permit this operation in our restricted Scheme subset.

Procedures that convert between types usually contain -> in their name, separating the source and destinations. For example list->string and char->integer.

The names of predicates that always return a boolean value end in ? when the name contains any letters (such as converged?). If no letters, then the predicate looks more like a standard comparison operation (like <=) and no question mark is necessary.

By convention, the components of compound names are separated by dashes - (not underscore _). In particular, prefixes that are actual words or can be pronounced as though they were actual words are followed by a hyphen, except when the first character following the hyphen would be something other than a letter, in which case the hyphen is omitted. Short, unpronounceable prefixes (like fn, fop) are not followed by a hyphen.

3.5 Iterated Function Composition

Here is an example of a function composition operator that takes a function and applies it a specified number of times to the input argument. Functions that take other functions as arguments are often called operators.

Aside from the obvious use of doing compositions like repeated squarings, the compose operator can be used to implement any iteration one generally associates with a for loop. One can think of the loop body as a state transition function that is applied to the current state of the loop and delivers the next state of the loop. You start the loop with an initial state, and each iteration is a composition.

Important Note: Converting a loop into an iterated composition is a last-resort technique. There is almost always a "better, more functional" way to construct your solution. an equivalent

The function sum-of-n below implements a "loop" that sums up the first n integers.

code/LambdaScheme/Composition.rkt

#lang racket

; suppose that we want to compose a function fn with itself n times

; applying it to argument x.

; For example, function g composed 3 times on argument y is

; g(g(g(y))) (in normal math notation), or

; (g (g (g y))) as a Scheme expression

; Function g composed 0 times on y is just y.

(define fcompose (lambda (fn n x)

(if (<= n 0)

; base case, the identity function, just return x

x

; recursion, compute one application and then send it

; to n-1 applications

; note that fcompose is in tail-recursive position, so

; this code is run as a loop with constant stack space

; watch how the stack grows if instead this non-tail recursive

; formulation is used: (fn (fcompose fn (-n 1) x))

(fcompose fn (- n 1) (fn x))

)

))

; compute powers of two

(define times2 (lambda (x) (* 2 x)))

(fcompose times2 5 1)

(fcompose times2 0 1)

(define power2 (lambda (x) (fcompose times2 x 1)))

(power2 4)

(power2 0)

; compute y ^ n

(define yexpn (lambda (y n)

(fcompose (lambda (p) (* y p)) n 1)

))

(yexpn 2 5)

(yexpn 5 3)

; sum up the first n integers 1, 2, ..., n

; we keep a state consisting of a list (sum i) of two elements

; where sum is the sum so far, and i is the next element of the

; sequence.

; This corresponds to a loop body that looks something like this:

; sum = sum + i

; i = i + 1

; making lists with cons car and cdr is really annoying to read

(define loop-body-ugly (lambda (state)

; new state is updated sum and next i. Create a 2 element list

(cons (+ (car state) (cadr state))

(cons (+ 1 (cadr state)) '() ))

))

; which is why first, second, third, fourth are defined

; and there is a list function which takes an arbitrary number of

; arguments and wraps them into a list

(define loop-body (lambda (state)

; new state is updated sum and next i. Create a 2 element list

(list

(+ (first state) (second state))

(+ 1 (second state)))

))

; run the loop 10 times, starting with initial state sum=0 i=1

(fcompose loop-body 10 '(0 1))

; a function to run the loop n times, starting with initial state sum=0 i=1

; this is exactly the loop

; sum = 0

; i = 1

; for (index = 0; index < n; index++) {

; sum = sum + i

; i = i + 1

; }

(define sum-of-n (lambda (n)

(first (fcompose loop-body n '(0 1)))

))

(sum-of-n 10)

(sum-of-n 0)

(sum-of-n 3)

3. A Simple Subset of Scheme
Notes on Functional Programming / Version 2.10 2014-02-24