[SOLVED] CS compiler data structure PowerPoint Presentation

PowerPoint Presentation

Time and space complexity in functional programming
CS 345
Lecture 10

Functional programming
invites certain problems!
Recursion can cause
Stack overflow!
Always passing data around as arguments to functions (instead of mutating it) leads to
Copies, copies everywhere!
Only using recursive data structures (linked lists) leads to
0(n) lookup times compared to O(1) lookup times in arrays!

Functional languages also offer
unique solutions to these problems
To the problem of stack overflow:

Tail call recursion, and
tail call optimization
To the problem of excessive data copying, and O(n) lookup times:

Persistent data structures

Recursion can be space inefficient

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(*5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (*3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Optimize by rewriting with an accumulator
(fact 5 1)
(fact 4 5)
(fact 3 20)
(fact 2 60)
(fact 1 120)
120

Tail recursive re-writes (can) always have this structure:
When you reach the base case, return the accumulator:

(define (func count acc)
(if (= count 1)
acc

The recursive case will always start with a recursive call to the function (avoid suspended operations):

(define (func count acc)
(if (= count 1)
acc
(func

The next item in the recursion will always count down the recursions in one way (- count 1) or another (cdr ls):

(define (func count acc)
(if (= count 1)
acc
(func (- count 1)

The last item in the recursion must be an evaluation that accumulates your desired total into the accumulator:

(define (func count acc)
(if (= count 1)
acc
(func (- count 1) (some-evaluation acc))

Avoid an awkward function signature
with an internal (i.e. nested) definition:
(fact 5 1)
(fact 4 5)
(fact 3 20)
(fact 2 60)
(fact 1 120)
120

Functional language compilers recognize tail recursion and re-use one stack frame for the tail call

Tail recursionrefers to the special case where the return value of the recursive branch is nothing more than the value of the next recursive call(tail call).

TAIL CALL: (fact (- num 1) (* num acc))

How does a compiler recognize tail calls?
From the syntax of the function definition.
Non tail recursive:
(define (func ls)
(if(empty? ls)
0
(+ (car ls) (func(cdr ls)))))

Not tail recursive, because after the recursive branch returns, there is still something left to evaluate.
Tail recursive:
(define (func ls acc)
(if (empty? ls)
acc
(func(cdr ls)(+ acc (car ls)))))

Tail recursive, because no previous calls are left waiting for their arguments. The last recursive call is the last thing to evaluate.

Tail recursive or non tail recursive?
Non tail recursive

(define (g n)
(if (= n 1)
2
(+ (g (- n 1)) 3)))

Tail recursive or non tail recursive?
Tail recursive

(define (sum x y)
(if (= x 0)
y
(sum (- x 1) (+ y x))))

Tail recursive or non tail recursive?
Tail recursive

(define (all-pos ls)
(cond ((empty? ls) #t)
((negative? (car ls)) #f)
((positive? (car ls)) (all-pos (cdr ls)))))

Tail recursive or non tail recursive?
Tail recursive

(define (bar f base ls)
(if (empty? ls)
base
(bar f (f (car ls) base) (cdr ls))))

foldl left!

Tail recursive or non tail recursive?
Non tail recursive

(define (foo f base ls)
(if (empty? ls)
base
(f (car ls) (foo f base (cdr ls)))))
fold right!

Tail recursive version of repeated

Trace
((repeated add-one 2) 3)

((lambda (x) ((repeated add-one (- 2 1)) (add-one x))) 3)

((repeated add-one 1) (add-one 3))

((repeated add-one 1) 4)

((lambda (x) ((repeated add-one (- 1 1)) (add-one x))) 4)

((repeated add-one 0) (add-one 4))

((repeated add-one 0) 5)

((lambda (x) x) 5)

5

Compare
((repeated add-one 2) 3)
((lambda (x) (add-one ((repeated add-one 1) x))) 3)
(add-one ((repeated add-one 1) 3))
(add-one ((lambda (x) (add-one ((repeated add-one 0) x))) 3))
(add-one (add-one ((repeated add-one 0) 3)))
(add-one (add-one ((lambda(x) x) 3)))
(add-one (add-one 3))
(add-one 4)
5

Lets do this one together

Lets do this one together, too
A tail-recursive function that returns the maximum value in a list

(define (my-max ls)
(

A tail-recursive function that returns the maximum value in a list

Participation Quiz
Write a function called find-pred:

(define (find-pred pred ls)

Inside the body of find-pred, write a tail-recursive version of the function.

The pred should be something like < or > : in other words, a function that itself takes two arguments and returns a boolean.

If you call (find-pred > (list 4 6 3 9 2)), it should return 9.

If you call (find-pred < (list 4 6 3 9 2)), it should return 2./docProps/thumbnail.jpeg