From CS 61A Wiki
Jump to: navigation, search
An expression describes a computation and evaluates to a value.

Primitive expressions

A primitive expression is a single evaluation step: you either look up the value of a name, or take the literal value. For example, variable names, numbers, and strings are primitive expressions.

The following are all primitive expressions: 1, 1.2, 'test', True, x.

Variable lookup

A name evaluates to the value bound to that name in the earliest frame of the current environment in which that name is found. In other words, to lookup a name in an environment, start looking in the local frame, then in the parent frame (if it exists), until you get to the global frame. Example:

x = 1
def outer():
    def inner():
        return x    return inner

to lookup x, look in the local frame inner. Since it is not there, look in the parent frame outer. Since it is not there, look in the parent frame (the global frame) and find x = 1.

Call expressions

A call expression is an expression that involves a function call. A call expression invokes a function and evaluates to the function's return value. To evaluate a function call:

  • evaluate the operator, then from left to right the operands
  • apply the function (the value of the operator) to the arguments (the values of the operands)

In general, the operator is the stuff before the set of matching parentheses, and the operands are the stuff inside the set of matching parentheses.

Simple example

>>> from operator import add, mul
>>> add(mul(2, 3), 1)7

Here is the full list of steps:

  1. evaluate operator of add(mul(2, 3), 1) and find that it is function add
  2. evaluate operand mul(2, 3)
    1. evaluate operator mul and find that it is function mul
    2. evaluate operand 2 (primitive)
    3. evaluate operand 3 (primitive)
    4. apply function mul to 2 and 3, returns 6
  3. evaluate operand 1 (primitive)
  4. apply function add to 6 and 1, returns 7

More complicated example

>>> from operator import add
>>> curry = lambda f: lambda x: lambda y: f(x, y)
>>> curry(add)(1)(2)3

Here is the full list of steps:

  1. evaluate operator curry(add)(1)
    1. evaluate operator curry(add)
      1. evaluate operator curry and find that it is func λ(f)
      2. evaluate operand add and find that it is a function
      3. apply func λ(f) to add, returns func λ(x)
    2. evaluate operand 1 (primitive)
    3. apply func λ(x) to 1, returns func λ(y)
  2. evaluate operand 2 (primitive)
  3. apply func λ(y) to 2, returns 3