程序代写代做代考 scheme DrRacket Lambda Calculus interpreter lec13

lec13

CS 314 Principles of Programming Languages

Prof. Zheng Zhang
Rutgers University

Lecture 13: Functional Programming

October 17, 2018

Computational Paradigms

Imperative:

Sequence of state-changing actions.
• Manipulate an abstract machine with:

1. Variables naming memory locations
2. Arithmetic and logical operations
3. Reference, evaluate, assign operations
4. Explicit control flow statements

• Fits the von Neumann architecture closely
• Key operations: Assignment and Control Flow

2

Computation Paradigms

Functional:

Composition of operations on data.
• No named memory locations
• Value binding through parameter passing
• Key operations: Function application and Function abstraction
• Basis in lambda calculus 


3

Pure Functional Languages

4

1. Referential transparency: the value of a function application is
independent of the context in which it occurs

• value of foo(a, b, c) depends only on the values of foo, a, b and c
• it does not depend on the global state of the computation

⇒ all vars in function must be local (or parameters)

Fundamental concept: application of (mathematical) functions to values

2. The concept of assignment is NOT part of function programming
• no explicit assignment statements
• variables bound to values only through the association of actual

parameters to formal parameters in function calls
• thus no need to consider global states

Pure Functional Languages

5

3. Control flow is governed by function calls and conditional
expressions
⇒ no loop

⇒ recursion is widely used

4. All storage management is implicit
• needs garbage collection

5. Functions are First Class Values
• can be returned from a subroutine
• can be passed as a parameter
• can be bound to a variable

Pure Functional Languages

6

1. A set of function definitions
2. An expression to be evaluated

A program includes:

E.g. in scheme,

> (define length
(lambda (x)

(if (null? x)
0
(+ 1 (length (rest x))))))

> (length ‘(A LIST OF 5 THINGS))

5

Pure Functional Languages

7

1. A set of function definitions
2. An expression to be evaluated

A program includes:

E.g. in scheme,

> (define length
(lambda (x)

(if (null? x)
0
(+ 1 (length (rest x))))))

> (length ‘(A LIST OF 5 THINGS))

5

Pure Functional Languages

8

1. A set of function definitions
2. An expression to be evaluated

A program includes:

E.g. in scheme,

> (define length
(lambda (x)

(if (null? x)
0
(+ 1 (length (rest x))))))

> (length ‘(A LIST OF 5 THINGS))

5

LISP

9

• Functional language developed by John McCarthy in the mid 50’s
• Semantics based on Lambda Calculus
• All functions operate on lists or symbols called: “S-expression”
• Only five basic functions: 


list functions con, car, cdr, equal, atom, 

& one conditional construct: cond

• Useful for LISt-Processing (LISP) applications
• Program and data have the same syntactic form 


“S-expression”
• Originally used in Artificial Intelligence

SCHEME

10

• Developed in 1975 by Gerald J. Sussman and Guy L. Steele
• A dialect of LISP
• Simple syntax, small language
• Closer to initial semantics of LISP as compared to COMMON LISP
• Provide basic list processing tools
• Allows functions to be first class objects

SCHEME

11

• Expressions are written in prefix, parenthesized form
(function arg1 arg2 … argn)
(+ 4 5)
(+ (* 3 4) (- 5 3))

• Operational semantics:
In order to evaluate an expression
1. Evaluate function to a function value
2. Evaluate each argi in order to obtain its value
3. Apply function value to these values

S-expression

12

S-expression ::= Atom | ( S-expression ) | S-expression S-expression
Atom ::= Name | Number | #t | #f | ε

#t
()
(a b c)
(a (b c) d)
((a b c) (d e (f)))
(1 (b) 2)

Lists have nested structure!

Lists in Scheme

13

The building blocks for lists are pairs or cons-cells. 

Proper lists use the empty list “( )” as an “end-of-list” marker.

(a b)

a

b ( )

a

b

c ( )

( )

d

e ( )

(a (b c) (d e) )

a b

(a . b)

Special (Primitive) Functions

14

• eq?: identity on names (atoms)
• null?: is list empty?
• car: select first element of the list 


(contents of address part of register)
• cdr: select rest of the list 


(contents of decrement part of register)
• (cons element list): constructs lists by adding element to the

front of list
• quote or ‘: produces constants

Do not evaluate the ‘ the content
after ‘. Treat them as list of literals.

Quotes Inhibit Evaluation

15

> ( cons ‘a (cons ‘b ‘(c d)) ) 

(a b c d)

;; Now if we quote the second argument
> ( cons ‘a ‘(cons ‘b ‘(c d)) )
(a cons ‘b ‘(c d)) 


;; If we unquote the first argument
> ( cons a (cons ‘b ‘(c d)) )
a: undefined;
cannot reference undefined identifier
context …

Special (Primitive) Functions

16

• ‘( ) is an empty list 


• (car ‘(a b c)) =

• (car ‘((a) b (c d))) =

• (cdr ‘(a b c)) =

• (cdr ‘((a) b (c d))) =

a

( a )

(b c)

(b (c d))

Special (Primitive) Functions

17

• car and cdr can break up any list:
(car (cdr (cdr ‘((a) b (c d))))) =

(cdr ‘((a) b (c d))) =

• cons can construct any list:
(cons ‘a ‘( ) ) =

(cons ‘d ‘(e)) =

(cons ‘(a b) ‘(c d)) =

(cons ‘(a b c) ‘((a) b)) =

(c d)

(b (c d))

(a)

( d e )

((a b) c d)

((a b c) (a) b)

Other Functions

18

• +, -, *, / numeric operators, e.g.,
๏ (+ 5 3) = 8, (- 5 3) = 2
๏ (* 5 3) = 15, (/ 5 3) = 1.6666666

• = < > comparisons for numbers
• Explicit type determination and type functions: 


⇒ All return Boolean values: #f and #t
๏ (number? 5) evaluates to #t
๏ (zero? 0) evaluates to #t
๏ (symbol? ‘sam) evaluates to #t
๏ (list? ‘(a b)) evaluates to #t
๏ (null? ‘( )) evaluates to #t

Note: SCHEME is a strongly typed language.

Other Functions

19

• (number? ‘sam) evaluates to #f
• (null? ‘(a) ) evaluates to #f
• (zero? (- 3 3) ) evaluates to #t
• (zero? ‘(- 3 3)) ⇒ type error
• (list? (+ 3 4)) evaluates to #f
• (list? ‘(+ 3 4)) evaluates to #t

READ-EVAL-PRINT Loop

20

The Scheme interpreters on the ilab machines are called mzscheme,
racket, and DrRacket. “drracket” is an interactive environment, the
others are command-line based.
For example: Type racket, and you are in the READ-EVAL PRINT
loop. Use “Control D” to exit the interpreter.

READ-EVAL-PRINT Loop

21

The Scheme interpreters on the ilab machines are called mzscheme,
racket, and drracket. “drracket” is an interactive environment, the
others are command-line based.

READ: Read input from user:
A function application

EVAL: Evaluate input: 

(f arg1 arg2 … argn)

1. evaluate function to a function value
2. evaluate each argi in order to obtain its value
3. apply function value to these values

You can write your Scheme program in file .rkts and then read
it into the Scheme interpreter by saying at the interpreter prompt:

(load “.rkts”)

PRINT: Print resulting value: 

The result of function application

READ-EVAL-PRINT Loop Example

22

1. Read the function application 

(cons ‘a (cons ‘b ‘(c d)))

2. Evaluate cons to obtain a function
3. Evaluate ‘a to obtain a itself
4. Evaluate (cons ‘b ‘(c d))

(i) Evaluate cons to obtain a function
(ii) Evaluate ‘b to obtain b itself
(iii) Evaluate ‘(c d) to obtain (c d) itself
(iv) Apply cons function to b and (c d) to obtain (b c d)

5. Apply cons function to ‘a and (b c d) to obtain (a b c d)
6. Print the result of the application: (a b c d)

> (cons ‘a (cons ‘b ‘(c d)))
(a b c d)

Defining Global Variables

23

The define constructs extends the current interpreter
environment by the new defined (name, value) association

> (define foo ‘(a b c))

> (define bar ‘(d e f))

> (append foo bar)
(a b c d e f)

> (cons foo bar)
((a b c) d e f)

> (cons ‘foo bar)
(foo d e f)

Defining Scheme Functions

24

(define (lambda () ) )

Example: Given function pair? (true for non-empty lists, false o/w)
and function not (boolean negation):

(define atom?
( lambda (object) 

(not (pair? object) ) 

) 

)

Evaluating (atom? ‘(a)):

1. Obtain function value for atom?
2. Evaluate ‘(a) obtaining (a) 

3. Evaluate (not (pair? object))
a) Obtain function value for not
b) Evaluate (pair? object)
i. Obtain function value for pair?
ii. Evaluate object obtaining (a)
iii. Evaluates to #t
c) Evaluates to #f
4. Evaluates to #f

Conditional Execution: if

25

1. Evaluate
2. If the result is a “true value” (i.e., anything but #f), then

evaluate and return
3. Otherwise, evaluate and return

(if )

(define abs-val
( lambda (x)
( if ( >= x 0) x (- x) ) 

) 

)

(define rest-if-first
( lambda (e l)
( if ( eq? e (car l) ) ( cdr l ) ‘() ) 

)
)

Next Lecture

26

• Read Scott, Chapter 9.1 – 9.3 (4th Edition)
• Chapter 11.1 – 11.3 (4th Edition)

Things to do: