This page collects notes about Scheme (an Lisp in general).

Sources

Most information is taken from: Structure and Interpretation of Computer Programs

See also my notes on Structure and Interpretation of Computer Programs

My Github repository with examples

Evaluation Rules

1. If self-evaluating: return value
2. If name: return value of associated name in environment
3. If special form: do something special
4. If combination:
   1. evaluate all subexpressions (in any order)
   2. apply operator on arguments and return result

Application Rules

1. If primitive procedure, just do it
2. If compound procedure, then evaluate body of procedure with each formal parameter replaced with corresponding actual argument value.

Linear Recursion and Iteration

See SICP Section 1.2.1 and stack overflow

It’s confusing that both the recursive and the iterative implementation call themselves. There is a distinction between

• Recursive process and
• Recursive function

A recursive function calls itself. But it can be implemented as recursive or iterative process.

Recursive Process

(define (factorial n)
(if (= n 1)
    1
    (* n (factorial (- n 1))))) ;; 'factorial' is part of bigger expression

Iterative Process

(define (factorial n)
  (fact-iter 1 1 n)) ;; inital values need to be provided

(define (fact-iter product counter max-count) ;; max-cout: intermediate result
  (if (> counter max-count)
       product
       (fact-iter (* counter product)
                  (+ counter 1)
                  max-count))) ;; max-cout: supply intermediate result to next call

• Iterative algorithms have constant space
• Develop iterative algorithm:
  • figure out a way to accumulate partial answers
  • write out table to analyze precisely
    • initialization of first row
    • update rules for other rows
    • how to know when to stop
• Iterative algorithms have no pending operations when the procedure calls itself

Expressions

• In Scheme everything is an expression
• Expressions can be nested arbritarly

Sequences as Conventional Interfaces

“The key to organizing programs so as to more clearly reflect the signal-flow structure is to concentrate on the “signals” that flow from one stage in the process to the next. If we represent these signals as lists, then we can use list operations to implement the processing at each of the stages.”

“The value of expressing programs as sequence operations is that this helps us make program designs that are modular, that is, designs that are constructed by combining relatively independent pieces. We can encourage modular design by providing a library of standard components together with a conventional interface for connecting the components in flexible ways.”

SICP: Section 2.2.3 Sequences as Conventional Interfaces

Lazy Evaluation

Normal-order (lazy) evaluation doesn’t work well in some cases:

• Tail recursion (Iterative Process): the stack frame can’t be reused because computation of a promise is not executed until it’s needed. The delayed promises let the stack grow until their computation is forced.
• Side effects: Setting variables to values calculated by promises is difficult because it’s not clear when the promise is forced to calculate the value. The time decoupling mechanism of promises (streams) doesn’t work well with statefull models where time is of essence.

Quotation

“Allowing quotation in a language wreaks havoc with the ability to reason about the language in simple terms, because it destroys the notion that equals can be substituted for equals. For example, three is one plus two, but the word “three” is not the phrase “one plus two”. Quotation is powerful because it gives us a way to build expressions that manipulate other expressions”

SICP: Section 2.3.1 Quotation

Backquote

Preceding a list with a backquote symbol (`) is much like quoting it, except that anything in the list that is flagged with a comma is evaluated.

SICP: Section 5.5.2 Compiling Expressions