Review - Scheme Scoping and Tail Calls


Solutions to the tail calls are at the end of lab 10, the first scoping question is 4a of the Fall 2012 final, and the environment diagram questions are here.

Tail Calls

Write a tail recursive function last, which takes in a list and returns the last element of the list.

(define (last s) 'Your-Code-Here) (last '(1 2 3 4 5)) ; 5

Write the tail recursive version of a function that returns the nth fibonacci number. It might be beneficial to try writing a normal recursive solution and/or a iterative Python version first.

(define (fib n) 'Your-Code-Here) (fib 10) ; 55

Write a tail-recursive function reverse that takes in a Scheme list a returns a reversed copy. Hint: use a helper function!

(define (reverse lst) 'Your-Code-Here) (reverse '(1 2 3 4)) ; (4 3 2 1) (reverse '(1)) ; (1)

Write a tail-recursive function that inserts number n into a sorted list of numbers, s. Hint: Use the built-in scheme function append.

(define (insert n s) 'Your-Code-Here) (insert 3 '(1 2)) ; (1 2 3) (insert 2 '(1 3 4)) ; (1 2 3 4) (insert 1 '(2)) ; (1 2)

Scoping

Write the value of the scheme expression (f 7) after evaluating the define expressions below:
(define j (mu (c k) (if (< c n) (j (+ c 2) (- k 1)) k))) (define (f n) (define c n) (j 0 0))

Draw the environment diagram for the following code, first with Lexical Scoping, and then with Dynamic Scoping.

1.

x = 10
def foo(x):
    return x * bar(2)
def bar(y):
    return y + x
foo(3)

2.

def make_counter(x):
    def count(m):
        nonlocal x
        if m == 'inc':
            x += 1
        elif m== 'count':
            return x
    return count
c1 = make_counter(5)
c2 = make_counter(7)
c1('inc')
c1('inc')
c1('count')