Functional Programming in Scheme - University of Alaska system

Functional Programming in Scheme

CS331 Chapter 10

Functional Programming

? Online textbook: ? Original functional language is LISP

? LISt Processing ? The list is the fundamental data structure ? Developed by John McCarthy in the 60's

? Used for symbolic data processing ? Example apps: symbolic calculations in integral and differential

calculus, circuit design, logic, game playing, AI ? As we will see the syntax for the language is extremely simple

? Scheme

? Descendant of LISP

1

Functional Languages

? "Pure" functional language

? Computation viewed as a mathematical function mapping inputs to outputs

? No notion of state, so no need for assignment statements (side effects) ? Iteration accomplished through recursion

? In practicality

? LISP, Scheme, other functional languages also support iteration, assignment, etc.

? We will cover some of these "impure" elements but emphasize the functional portion

? Equivalence

? Functional languages equivalent to imperative ? Core subset of C can be implemented fairly straightforwardly in Scheme ? Scheme itself implemented in C ? Church-Turing Thesis

Lambda Calculus

? Foundation of functional programming ? Developed by Alonzo Church, 1941 ? A lambda expression defines

? Function parameters ? Body

? Does NOT define a name; lambda is the nameless function. Below x defines a parameter for the unnamed function:

(x x x)

2

Lambda Calculus

? Given a lambda expression

(x x x)

? Application of lambda expression

((x x x)2) 4

? Identity

(x x)

? Constant 2: (x 2)

Lambda Calculus

? Any identifier is a lambda expression ? If M and N are lambda expressions, then the

application of M to N, (MN) is a lambda expression ? An abstraction, written (x M ) where x is an identifier and M is a lambda expression, is also a lambda expression

3

Lambda Calculus

LambdaExpression ident | (MN) | ( ident M ) M LambdaExpression N LambdaExpression

Examples

x (x x) ((x x)(y y))

Lambda Calculus

First Class Citizens ? Functions are first class citizens

? Can be returned as a value ? Can be passed as an argument ? Can be put into a data structure as a value ? Can be the value of an expression

((x x x)(y 2)) (x 22) 4 ((x?(y?x+y)) 2 1) = ((y?2+y) 1) = 3

4

Lambda Calculus

Functional programming is essentially an applied lambda calculus with built in

- constant values - functions

E.g. in Scheme, we have (* x x) for x*x instead of x?x*x

Functional Languages

? Two ways to evaluate expressions ? Eager Evaluation or Call by Value

? Evaluate all expressions ahead of time ? Irrespective of if it is needed or not ? May cause some runtime errors

? Example

(foo 1 (/ 1 x))

Problem; divide by 0

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download