Mimir:Draft1 Chapter4

From Openitware
Jump to: navigation, search

Back to Table of Contents


Chapter 4: Functional Programming


"Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot." - Eric Raymond

In computer science, functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming emphasizes functions that produce results that depend only on their inputs and not on the program state—i.e. pure mathematical functions. It is a declarative programming paradigm, which means programming is done with expressions. In functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) both times. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.

What is a functional language?

The functional programming paradigm is based on mathematical functions. The objective of the design of a functional programming language is that it allows the program to heavily rely on mathematical functions. Contrary to imperative languages, a purely functional programming language does not use variables or assignments. This frees the programmer any concerns about memory allocation, or state of the program. One main difference due to the non-existence of variables is that iterative constructs are not possible since they are controlled by variables. Thus, repetition (i.e. loops) must be obtained through recursion rather than iteration. This also makes testing easier since each function can be tested without any concerns for its context.


Lisp was invented by Artificial Intelligence (AI) pioneer John Mc Carthy in the late 1950s. McCarthy published its design in a paper in Communications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" (interesting that "Part II" was never published). LISP was intended as a mathematical formalism for reasoning about the use of recursion equations as a model for computation. Of computer languages still in widespread use today, only Fortran is older.

The Lisp family of languages has evolved with the field of computer science, both by putting the best ideas from the field into practical use, and by contributing many such ideas. The association of Lisp with research, however, has not always been beneficial. Lisp has always been among the main tools of AI since the beginning. When the commercial AI market failed to deliver on its promises, Lisp was blamed as a scapegoat. In the late 1980s, many companies abandoned Lisp in favor of other languages, starting the so called "AI winter". Although Lisp survived the crisis, some of the resulting prejudice and lack of information is still present in the computing field.

With growing popularity of LISP, many dialects were developed and were being used by LISP users by 1980's. The LISP community started a consolidation effort to design the Common Lisp dialect, which became the standard and commercial version of LISP.

Mathematical Programming Language

Describes how a Functional Language is derived from mathematical functions.

What is a mathematical function?

f(x) = x + 1;

g(x) = (x + 32) * 5 / 9

  • Lambda expression

LISP, the first Functional Language

LISP data types and objects

LISP has two categories of data objects:

  • Atoms
  • Lists

LISP Interpreter and the Polish notation

(function_name argument1 argument2 ... argumentn)

(+ 2 2) -> returns 4

(+ 2 4 6 8 10) -> returns 30

Common Functions

Assignment: set (remind readers to quote arguments with ' to prevent evaluation)

Math functions: +, -, *, /

List functions: list, cons, append, car, cdr

Defining functions: defun

Conditional functions: cond, null

Recursive functions: differentiate recursive from iterative


A quick summary of the chapter should go here

Key Terms

LISP: LISt Processing.





Recursion (Recursive Functions):

Symbolic expressions (S-expressions):

Lambda expressions:

...other key terms:

Problem Sets

Basics 1. Evaluate the following expressions:

(+ 2 2)

(- 4 2)

(* 5 2)

(/ 10 5)

(/ 11 2)

(+ 1 2 3 4 5 6 7 8 9)

(* 1 2 3 4 5)

(* (+ 2 3) (/ 24 6))

(/ (* (- 212 32) 5) 9)

2. Evaluate the following forms:

(car '(a b c))

(cdr '(m n o p))

(car '((a b) (c d))

(cdr '((a b) (c d))

(car (cdr (car (cdr '((a b) (c d) (e f))))))

(car (car (cdr (cdr '((a b) (c d) (e f))))))

(car (cdr (car '(cdr ((a b) (c d) (e f))))))

(car (cdr '(car (cdr ((a b) (c d) (e f))))))

(car '(cdr (car (cdr ((a b) (c d) (e f))))))

3. Using only CAR and CDR, try to pick the atom PEAR our of the following lists:

(apple orange pear grape)

((apple orange) (pear grape))

(((apple) (orange) (pear) (grape)))

(apple (orange) ((pear)) (((grape))))

((((apple))) ((orange)) (pear) grape)

((((apple) orange) pear) grape)

4. Understanding APPEND and LIST

First let's define two lists, ab-list and cd-list as follows:

(setq ab-list '(a b) cd-list '(c d))

(append ab-list cd-list)

(list ab-list cd-list)

(append ab-list ab-list)

(list ab-list ab-list)

(append 'ab-list ab-list)

(list 'ab-list ab-list)

(list (car ab-list) cd-list)

(append (car ab-list) cd-list)

5. Defining your own function:

    (defun double (num)
       (* num 2))
    (defun half (num)
       (/ num 2))
    (defun Celcius (temp)
       (/ (* (- 212 32) 5) 9))

6. Conditionals. Evaluate these expressions:

  (setq bmi 25)
  (cond ((> bmi 30) 'obesity)
        ((> bmi 25) 'overweight)
        ((> bmi 20) 'normal-weight)
        (t 'underweight))
  (setq distance 40)
  (cond ((> distance 40) 'very-long-commute)
        ((> distance 30) 'long-commute)
        ((> distance 20) 'average)
        ((> distance 10) 'short-commute)
        (t 'no-commute))

7. Recursion

  (defun (factorial n) 
     (cond ((= n 0) 1)
           (t (* n (factorial (- n 1))))))