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 Expression

• 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

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

 

LISP Data Type 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

Special Form Function: DEFINE

• DEFINE – Two forms:

1.To bind a symbol to an expression

e.g., (DEFINE pi 3.141593)

Example use: (DEFINE two_pi (* 2 pi))

These symbols are not variables – they are like the names bound by Java’s final declarations

2.To bind names to lambda expressions (LAMBDA is implicit)

e.g., (DEFINE (square x) (* x x))

Example use: (square 5)

– The evaluation process for DEFINE is different! The first parameter is never evaluated. The second parameter is evaluated and bound to the first parameter.

Output Function

• 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

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))

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

(LIST ′apple ′orange ′grape) returns

(apple orange grape)

Predicate Functions

• 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)

• LIST? takes one parameter; it returns #T if the parameter is a list; otherwise #F

(LIST? ‘()) yields #T

• NULL? takes one parameter; it returns #T if the parameter is the empty list; otherwise #F

(NULL? ‘(())) yields #F

Tail Recursion in Scheme

• Definition: A function is tail recursive if its recursive call is the last operation in the function
• A tail recursive function can be automatically converted by a compiler to use iteration, making it faster
• Scheme language definition requires that Scheme language systems convert all tail recursive functions to use iteration

Functional Form

• Composition

–If h is the composition of f and g, h(x) = f(g(x))

(DEFINE (g x) (* 3 x))

(DEFINE (f x) (+ 2 x))

(DEFINE h x) (+ 2 (* 3 x)))  (The composition)

–In Scheme, the functional composition function compose can be written:

(DEFINE (compose f g) (LAMBDA (x) (f (g x))))

((compose CAR CDR) ‘((a b) c d)) yields c

(DEFINE (third a_list)

((compose CAR (compose CDR CDR)) a_list))

is equivalent to CADDR

Comparing Functional and Imperative Language

• Imperative Languages:

–Efficient execution

–Complex semantics

–Complex syntax

–Concurrency is programmer designed

• Functional Languages:

–Simple semantics

–Simple syntax

–Less efficient execution

–Programs can automatically be made concurrent