More Scheme

Lis(t) P(rocessing)

Scheme List Definition

A Scheme list is either:

-   nil

-   Composed of a first element (car) and the rest (cdr) of the Scheme list

Creating Scheme Lists

- (cons 1  __________________________________)

- (cons 1 (cons 2 _________________________))

- (cons 1 (cons 2 (cons 3 nil))

Scheme Lists vs. Linked Lists

Checking Equivalence

: (equal? e1 e2) checks if e1 and e2 evaluate to equivalent values

- Like == in Python

- (null? expr) is like (equal? expr nil)

: (eq? e1 e2) checks if e1 and e2 evaluate to identical values

- Like is in Python

- Only matters for lists

: (= e1 e2) only works for numbers

List Constructor

-   If we know each element we want to put in a list, we can use the list constructor

-   The list constructor takes in any number of elements and puts each element as a single element in a list

Quoting

-   The quote special form takes in a single argument and returns an unevaluated version of the argument

-   Quoting a symbol gives a symbol back

-   Quoting the representation of a list gives a list

Using List Constructors

3 Levels Of Scheme Lists

1. Constructor : cons, list, quote

2. Use : Box and pointer diagrams - what’s the car and cdr?

3. Representation : How is the list displayed? 

When to use each constructor

- cons:

   When you want to add an element on to the start of a list

   Ex: add an element to the start of the list returned by a recursive call

- list:

   When you have multiple elements you want to put into a list all at once

   Ex: want to create a two element list containing x and y

- quote:

   When you know the exact structure of the list and the values it contains

   Ex: create a list to pass in as an argument in an interactive session

Tail Recursion

-   An expression in a tail context is evaluated as the last step the function call

: That means nothing is evaluated/applied after it is evaluated

-   Function calls in a tail context are called tail calls

-   If all recursive calls are in tail contexts, we say that function is tail recursive

: If a language supports tail call optimization, a tail recursive function will only ever open a constant number of frames

Identifying Tail Contexts

: An expression is in a tail context only if it is the last thing evaluated in every possible scenario, regardless of the other values

Writing Tail Recursive Functions

1. Identify recursive calls that are not in a tail context. Tail contexts are:

- The last body subexpression in a lambda (a function)

- The consequent and alternative in a tail context if

- All non-predicate sub-expressions in a tail context cond

- The last sub-expression in a tail context and, or, begin, or let

2. Create a helper function with arguments to accumulate the computation that prevents it from being tail recursive