Transcript Functional Programming Language – Scheme

Programming Languages and
Design
Lecture 4
Functional Programming – Scheme
Instructor: Li Ma
Department of Computer Science
Texas Southern University, Houston
September, 2010
Review of Previous Lectures
 Introduction to programming languages
Fundamental concepts
Computation models/Programming paradigms
Language Design Issues and Questions
Program processing
 Syntax specifications of programming languages
 Semantic specifications of programming
languages
2
Today’s Lecture
 Review the categories of programming languages
 Functional Programming
 Properties
 Lambda calculus
 Scheme
 Function definitions and examples
 References
 “Programming Language Pragmatics”, Michael Scott, Chapter 10
 “Foundations of Programming Languages: Design and
Implementation”, S. H. Roosta, Chapter 12 & 13 (§13.2)
3
Categories of Programming
Languages
 All languages fall into one of the following two
categories:
 Imperative languages require programmers to describe, stepby-step, how an algorithm should do its work
 Real world analogy » A recipe is a type of imperative program that
tells a cook how to prepare a dish
 Declarative languages allow programmers to describe what an
algorithm should do without having to specify exactly how it
should do
 Real world analogy » The recent Pfand law is a declarative program
that tells retailers that they must institute a recycling program for the
einweg Flasche and Dosen that they sell, without telling them
exactly how to do it
4
Imperative Languages
 The von Neumann languages
 include Fortran, Pascal, Basic, C
 are a reflection of the von Neumann computer architectures on
which their programs run
 A single CPU sequentially carries out instructions
 are also called the procedural languages
 A sequence of statements represent commands
 Execute statements which alter the program’s state
(variables/memory)
 Sometimes called computing by side effects
 Example: summing the first n integers in C
 for(sum=0,i=1;i<=n;i++) { sum += i; }
5
Imperative Languages (cont’)
 The object-oriented languages
 include Smalltalk, C++, Java, CLOS
 are similar to the von Neumann languages with the addition of
objects
 Objects:
 Contain their own internal state (member variables) and functions
which operate on that state (methods)
 Computation is organized as interactions between objects (one
object calling another’s methods)
 Most object-oriented languages provide facilities based on
objects that encourage object-oriented programming
 Encapsulation, inheritance, and polymorphism
6
Declarative Languages
 The functional languages
 include LISP/Scheme, ML, Haskell
 are a reflection of Alonzo Church’s theory of recursive functions
(lambda calculus)
 Computation carried out as functions return values based on the
(possibly recursive) evaluation of other functions
 Mechanism known as reduction
 No side effects!
 Permits equational reasoning, easier formal proofs of program
correctness, etc.
 Example: summing the first n integers in SML
 fun sum (n) = if n <= 1 then n else n + sum(n-1)
7
Declarative Languages (cont’)
 The logic languages
 include Prolog, SQL, Microsoft Excel
 are also called descriptive language
 Only describe known facts and relationships about a problem
 Not prescribe the sequence of steps to solve the problem
 are a reflection of the theory of propositional logic
 Computation is an attempt to find values which satisfy a set of
logical relationships
 Mechanism most commonly used to find these values is known as
resolution and unification
 Example: summing the first n integers in Prolog
 sum(1,1).
 sum(N,S) :- N1 is N-1, sum(N1,S1), S is S1+N.
8
Languages for Programming
Paradigms
 Different languages provide facilities to
encourage different programming models
Imperative/procedure programming
 Fortran, Pascal, Basic, C
Object-Oriented programming
 Smalltalk, C++, Java, CLOS
Functional programming
 LISP/Scheme, ML, Haskell
Logic programming
 Prolog, SQL, Microsoft Excel
9
Functional Programming
 Based on mathematical functions
 Take argument, return value
 Only function call, no assignment
 Functions are first-class values
 Use a function as an argument to another function
 Functions can return functions
 No side effects
 No change for internal state of computation
 Dynamic memory management
 Requires garbage collection
 Reclaim the inaccessible storage
10
Lambda Calculus
 Mathematical functional language
 Used for studying functional programming language
concepts
 All functional programming languages can be viewed as
syntactic variation of lambda calculus
 Language constructs
 Variables: x
 Primitive functions: *
 Function abstraction:  (x) x*x or  x.x*x
 Function call: f (x) or f x
 Example
 ( (x) x*x*x) (2) yields 8
11
Scheme
 A dialect of LISP (from MIT, 1975)
 Lists as built-in data type
A sequence of expressions separated by spaces and
surrounded by parentheses
 Same syntax for lists and programs
 Functions are (first-class) data
 Dynamic typing, need type checking
 Recursion is used for loops of read-evaluateprint
12
Scheme Syntax
 The basic object in Scheme is symbolic
expression (S-expression)
 An S-expression is defined recursively
An atomic symbol is an S-expression
If expression1 and expression2 are S-expressions, so
is (expression1 expression2)
S-expression ::= literals
| symbols
| (s-expression . . .)
 Special forms for specific language constructs
13
Atomic Data Types
 Numbers
3.14, 42, -4101
 Booleans
#t, #f
 Characters, Strings
#\a, #\newline, “Hello World”
 Symbols
f, x, +, *, foo, bar, null?, set!
14
Variable Definitions
 Variable definitions
(define x 3)
(define y 5)
; associate the value 3 with the name x
; associate the value 5 with the name y
 This is not an assignment!
A new variable is defined
Like ‘int x = 3;’ in C
15
Functions
 Function definition
(define (double x) (+ x x))
 Function application (call)
(* 3 4)
; return 12
(+ 2 x y)
(double 3)
; return 6
(* (+ 3 4) (double 3))
; return 42
16
Anonymous Functions
 Anonymous function definitions
Use lambda calculus or other predefined functions
 Other way for function definitions
(define double (lambda (x) (+ x x)))
(define (second lst) (car (cdr lst)))
 Function application/call
(double 3)
; return 6
((lambda (x) (+ x x)) 3)
(second ‘((A) (B) (C)))
; return 6
; return (B)
17
Lists
 Quotes (not to be evaluated)
(quote x), ’x
 Empty list
’(), often assigned to the variable nil
 Nonempty list
’(1 2 3), ’(a b 3), ’(1 (2 3) 4)
18
List Representation (1)
 The list ’(1 2) is stored as
cons
/
\
1
cons
/
\
2
()
19
List Representation (2)
 The list ’(1 (2 3) 4) is stored as
cons
/
\
1
cons
/
\
cons
cons
/
\
/
\
2 cons 4
()
/
\
3
()
20
List Functions
 Predefined functions
car, cdr, cons
 Examples
(car ’(1 2)) returns 1
(cdr ’(1 2)) returns (2)
(cons 1 ’(2)) returns (1 2)
(cons 1 2) returns (1 . 2)
21
Lists vs. S-Expressions
List Syntax
S-Expression Syntax
(1 2 3)
(1 . (2 . (3 . ())))
((1 2))
((1 . (2 . ())) . ())
(1 . 2) is NOT a list!!
22
More Examples (1)
Expression
(- 24 (* 4 3))
(car (cdr ’(1 2 3)))
(cadr ’(1 2 3))
(cons 1 ’())
(cons 1 2)
(cons ’() ’())
(car ’(()))
Value
12
2
2
(1)
(1 . 2)
(())
()
23
More Examples (2)
Expression
(define x 3)
(+ x 2)
’x
(double x)
’(double x)
(* (- x) 7)
Value
5
x
6
(double x)
-42
24
More List Functions
Expression
(null? ’())
(null? ’(a b))
(list 1)
(list ’a ’b ’c)
(append ’(1) ’(2))
(map double ’(1 2 3))
Value
#t
#f
(1)
(a b c)
(1 2)
(2 4 6)
25
Higher-Order Functions
(define (twice f x) (f (f x)))
or
(define twice (lambda (f x) (f (f x))))
(twice double 2) ; returns 8
(twice (lambda (x) (* x x)) 2) ; returns 16
26
Higher-Order Functions (cont’)
;; Curried version of twice
(define (twice f) (lambda (x) (f (f x))))
(define quadruple (twice double))
(quadruple 2) ; returns 8
((twice double) 2) ; returns 8
((twice quadruple) 2) ; returns 32
((twice (twice double)) 2) ; returns 32
27
Curried Function in C Syntax
(int (*) (int))
twice (int (*f) (int)) {
int foo (int x) {
return f(f(x));
}
return foo;
}
(twice(double)) (2);
28
Conditionals
 if-then-else
(if (= x y) 1 2)
; in C: (x == y) ? 1 : 2
 cond
(cond ((= x y) 1)
((< x y) 2)
(else 3))
 Anything non-#f is considered true
(if 1 2 3) ; returns 2, so true
29
Equality
Expression
(eq? x x)
(eq? ’x ’x)
(eq? ’() ’())
(eq? 2 2)
(eq? (list 1) ’(1))
Value
#t
#t
#t
undefined
#f
(eqv? 2 2)
(equal? (list 1) ’(1))
#t
#t
30
Recursion
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
(fac 5) ; returns 120
(fac 1000) ; that’s 2568 digits
31
Map Function
(define (mymap f l)
(if (null? l) ’()
(cons (f (car l))
(mymap f (cdr l)))))
(mymap double ’(1 2 3 4 5))
; returns (2 4 6 8 10)
(mymap (lambda (x) (+ x 1)) ’(1 2))
; returns (2 3)
32
Let
 Defines local name binding
(let ((x 3)
(y 5))
(* x y))
 Syntactic sugar for function call
((lambda (x y) (* x y)) 3 5)
33
Quicksort
 Problem: sort list of numbers
 Algorithm:
If list is empty, we are done
Choose pivot n (e.g., first element)
Partition list into lists A and B with elements < n in A
and elements > n in B
Recursively sort A and B
Append sorted lists and n
34
Quicksort (cont)
(define (quicksort ls)
(if (null? ls) ’()
(let ((p (car ls)))
(append
(quicksort (gt p (cdr ls)))
(list p)
(quicksort (le p (cdr ls)))))))
35
Partitioning
(define (gt p ls)
(filter (lambda (x) (> p x)) ls))
(define (le p ls)
(filter (lambda (x) (<= p x)) ls))
36
Filtering a List
(define (filter pred ls)
(cond ((null? ls) ’())
((pred (car ls))
(cons (car ls)
(filter pred (cdr ls))))
(else (filter pred (cdr ls)))))
37