Introduction

• The design of the imperative languages is based directly on the von Neumann architecture
• The design of the functional languages is based on mathematical functions

Mathematical Functions

• A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set
• A lambda expression specifies the parameter(s) and the mapping of a function in the following form

  l(x) x * x * x

for the function  cube(x) = x * x * x

Lambda Expressions

• Lambda expressions describe nameless functions
• Lambda expressions are applied to parameter(s) by placing the parameter(s) after the expression

  e.g.,   (l(x) x * x * x)(2)

which evaluates to 8

Functional Forms

• A higher-order function, or functional form, is one that either takes functions as parameters or yields a function as its result, or both

Function Composition

• A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second

  Form: h º f ° g

which means h (x) º f ( g ( x))

For f (x) º x + 2  and  g (x) º 3 * x,

h º f ° g yields (3 * x)+ 2

LISP Data Types and Structures

• Data object types: originally only atoms and lists
• List form: parenthesized collections of sublists and/or atoms

  e.g., (A B (C D) E)

• Originally, LISP was a typeless language
• LISP lists are stored internally as single-linked lists

LISP Interpretation

• Lambda notation is used to specify functions and function definitions. Function applications and data have the same form.

  e.g., If the list (A B C) is interpreted as data it is

a simple list of three atoms, A, B, and C

If it is interpreted as a function application,

it means that the function named A is

applied to the two parameters, B and C

• The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation

Output Functions

• Usually not needed, because the interpreter always displays the result of a function evaluated at the top level (not nested)
• Scheme has PRINTF, which is similar to the printf function of C
• Note: explicit input and output are not part of the pure functional programming model, because input operations change the state of the program and output operations are side effects

Numeric Predicate Functions

• #T (or #t) is true and #F (or #f) is false (sometimes () is used for false)
• =, <>, >, <, >=, <=
• EVEN?, ODD?, ZERO?, NEGATIVE?
• The NOT function inverts the logic of a Boolean expression

Control Flow

• Selection- the special form, IF

  (IF predicate then_exp else_exp)

    (IF (<> count 0)

(/ sum count)

)

• Recall from Chapter 8 the COND function:

(DEFINE (leap? year)

(COND

((ZERO? (MODULO year 400)) #T)

((ZERO? (MODULO year 100)) #F)

(ELSE (ZERO? (MODULO year 4)))

))

List Functions

• QUOTE – takes one parameter; returns the parameter without evaluation

QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function.  QUOTE is used to avoid parameter evaluation when it is not appropriate

QUOTE can be abbreviated with the apostrophe prefix operator

‘(A B) is equivalent to (QUOTE (A B))

• Examples:

  (CAR ′((A B) C D)) returns (A B)

(CAR ′A) is an error

(CDR ′((A B) C D)) returns (C D)

(CDR ′A) is an error

(CDR ′(A)) returns ()

(CONS ′() ′(A B)) returns (() A B)

(CONS ′(A B) ′(C D)) returns ((A B) C D)

(CONS ′A ′B) returns (A . B)  (a dotted pair)

• LIST is a function for building a list from any number of parameters

   (LIST ′apple ′orange ′grape) returns

(apple orange grape)

Predicate Function: EQ?

• EQ? takes two expressions as parameters (usually two atoms); it returns #T if both parameters have the same pointer value; otherwise #F

  (EQ? ‘A ‘A) yields #T

(EQ? ‘A ‘B) yields #F

(EQ? ‘A ‘(A B)) yields #F

(EQ? ‘(A B) ‘(A B)) yields #T or #F

(EQ? 3.4 (+ 3 0.4))) yields #T or #F

• EQV? is like EQ?, except that it works for both symbolic and numeric atoms; it is a value comparison, not a pointer comparison

   (EQV? 3 3) yields #T

(EQV? ‘A 3) yields #F

(EQV 3.4 (+ 3 0.4)) yields #T

(EQV? 3.0 3) yields #F  (floats and integers are different)