I take notes here when I learn CS61A: Structure and Interpretation of Computer Programs.

Language Elements

  • Expression: Describes a computation and evaluates to a value.
    • Primitive expression: a single evaluation step - look up the value of a name or take the literal value. For example, 2, max, "Hello!".
    • Call (compound) expression: expression that involve a call to some function.
  • Statement: Execute some action.
    • Simple statement: one line, one action. Like = assignment, return, etc.
    • Compound statement: a statement composed of other statements, like def, if etc.

      Compound statements typically span multiple lines and start with a one-line header ending in a colon, which identifies the type of statement. Together, a header and an indented suite of statements is called a clause (header + suite = clause). A compound statement consists of one or more clauses:

      <header>:
  <statement>
  <statement>
  ...
<separating header>:
  <statement>
  <statement>
  ...
...
  • Language Elements
    • primitive expressions and statements, which represent the simplest building blocks that the language provides
    • means of combination, by which compound elements are built from simpler ones
    • means of abstraction, by which compound elements can be named and manipulated as units
  • Function type
    • Pure function: Only produces a return value, always evaluates to the same results given the same argument values.
    • Non-pure function: may produce side effects, may evaluates to different results given the same inputs, and may change the environment (print in console, render an image etc.) print is a non-pure function.
  • Evaluation Order
    • Normal order: evaluate leftmost, outmost functions first (evaluate function before its argument) may result in doing extra work by requiring function arguments to be evaluated more than once
    • Applicative order: evaluate function arguments before this function is applied; may result in programs that do not terminate
    • In practice, most functional programming languages uses lazy evaluation. With lazy evaluation, we evaluate a value when it is needed, and after evaluation all copies of that expression are updated with the new value. In effect, a parameter passed into a function is stored in a single location in memory so that the parameter need only be evaluated once. That is, we remember all the locations where we a certain argument will be used, and when we evaluate a function, we replace the argument with the value.
    • Importantly, in Python (and many other languages), the arguments of functions are evaluated first before being passed into the function. Compare:
      # This prints 0
x = 0
if x == 0:
  print(0)
else
  print(1/x)
# This results in an error
def if_func(cond, true_rlt, false_rlt):
  if cond:
    print true_rlt
  else
    print false_rlt
if_func(x, 0, 1/x)
    • Expression Tree
  • First-class element

    In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status. Some of the “rights and privileges” of first-class elements are:

    • They may be bound to names.
    • They may be passed as arguments to functions.
    • They may be returned as the results of functions.
    • They may be included in data structures.
      Python awards functions full first-class status, and the resulting gain in expressive power is enormous.

Environment Diagram

How to Do It?

  • Start with the global diagram and work line by line
  • Constants: (numbers, strings, etc), they are self-evaluating so don’t do any work.
  • Assignment (=,def or import a function):
    • Primitives: evaluates the assigned value creates a binding between the name and the value in the current frame.
    • Objects (including functions)
      1. Draw an binding arrow from the name in the current frame pointing to the value. The value, for function, is the function signature (e.g., for functions defined with def use func <name>(<formal parameters>) [parent = <label>])
      2. Specify the parent frame in Rectangular bracket besides the function signature.
      3. If two names are associated to the same object - make sure do not make a new copy of the object; instead, let both of the names point to the same object.
  • Call expression (skip this for built-in functions like max)
    1. Creates a new frame that extends the current frame. Draw a new box, name it with the original function name (no matter what name it currently is referred to).
    2. Indicate its parent in the rectangular bracket. (The parent is always where the function is defined.)
    3. Create binding for passed in parameters (See the assignment section above).
    4. Work through each lines of the function, working in the new local frame.
    5. Indicate the return value, even it is None. All non-global frames should have a return value indicated.
  • List: represented on the object heap as a row of indexed boxes - one box per element
    • each box contains either a primitive value, or points to a compound value/function/object

Special Cases

  • Nested Functions
    • Remember, if a function is defined in another function, then its parent frame should be that function’s frame, not global. The parent is always where the function is defined.
    • Follow the evaluation order. Once the function is done, go back to the frame from which you made the function call.
  • Lambda
    • Use a Greek letter λ as function name and annotates it line number when presenting it in the object pile.
    • Assigning a lambda to a variable is simply giving the lambda an alias. It does not give it an intrinsic name. So, when called, the frame this lambda created would be known as λ, not that variable name; the parent of the frame is also the frame where this lambda is defined, not where it is assigned to a variable.

Examples

  • Calling a lambda with a given name.
  • Defining and calling a usual function.
  • Defining and chaining-calling a function that returns itself.
  • Defining and chaining-calling a nested function that, along with its parent, return each other.
  • Calling a Curried Function
  • List

Function

  • In Python, function is a first class element.
  • Higher-order functions are those that return or take in as argument(s) other functions, or both.
  • Utilize higher-order functions can reduce code repetition (think about the calculate area example).

Why Nesting?

  • The concept of private functions - some small functions are never used in other places other than as a helper for a bigger function. These functions should be nested - to reduce name collision, to be more elegant etc.
  • Some helper function needs to have access to variables in its main function - then this helper should be nested to access the variables instead of passing the variable by argument into the helper.
  • Great example at DeNero 1.6.3

Function Currying

Currying is the practice of transforming a multi-argument function into a single higher-order function.

from operator import add

def curry2(f):
  def g(x):
    def h(y):
      return f(x,y)
    return h
  return g
# Alternative way using lambda
curry2_alt = lambda f: lambda x: lambda y: f(x, y)

adder_maker = curry2(add)
three_adder = adder_maker(3)

add(3,4) #7
three_adder(4) #7
curry2(add)(3)(4) #7

print(three_adder) # <function h>

# Usually this is simply done via functools
import functools
four_adder = functools.partial(add, 4)
four_adder(5) # 9

Self-Reference

Recursion

  • Call order in recursion. Here is a beautifully constructed example:
A Picture Showing the Inverse Cascade Algorithm

  • Relation between recursion and iteration:

    • Iteration is a special case of recursion.
    • Conversion can be tricky.
      • Recursive algorithms conserve and pass on the state of last loop by arguments, and update them by calling the function with the new arguments again.
      • Iterative algorithms conserve and the state of last loop in variables, and update them by running a while loop.

  • Some variants of recursion

    • Mutual recursion: when two functions calls each other.
    • Tree recursion: when a function calls itself more than one time.

  • Recursion equation - when order does and does not matter:

    • Partition model: when order does not matter. In this case, f(n,k) = f(n-k,k) + f(n,k-1).
    • Stairway model: when order does matter. In this case, g(n,k)=g(n-1,k)+g(n-2,k)...+g(n-k,k).

  • Recursion on different data types

Type Base Case Current Item Recursive Case
int == 0, == 1 n % 10 n // 10
list == [] li[0] li[1:],li[:-1]
str ==' ', len(s) == 1 s[0] s[1:],s[:-1]
Tree t.is_leaf() t.label t.branches
Link t == Link.empty t.first t.rest

Data Abstraction

Constructor and Selector

Example: Implement Tree and Rationals