Background

• The little programming language of Chapter 7 isn't extensible

• So add a way to define and call functions

• And then look at design tactics this opens up

Definition

• In Python

def same(num):
    return num

• In our little language

["func", ["num"], ["get", "num"]]

• Keyword "func"
• (Possibly empty) list of parameter names
• Body

Saving Functions

• A function is just another object

• Assign it to a variable so we can call it later

["set", "same", ["func", ["num"], ["get", "num"]]]

Anonymous Functions

• An anonymous function is one that doesn't have a name

• JavaScript and other languages use them frequently

• Python supports limited lambda expressions

double = lambda x: 2 * x
double(3)

Implementing Call

["call", "same", 3]

1. Evaluate arguments.

2. Look up the function.

3. Create a new environment.

4. Call do to run the function's action and captures the result.

5. Discard environment created in step 3.

6. Return the result.

Eager and Lazy

• Eager evaluation: arguments are evaluated before call

• Lazy evaluation: pass expression sub-lists into the function to be evaluated on demand

  • Gives the called function a chance to inspect or modify expressions before using them

• Python and most other languages (including ours) are eager

• R is lazy

• A design choice

The Environment

• A variable x in a function shouldn't clobber a variable with the same name in its caller

• Use a list of dictionaries to implement a call stack

• Each dictionary called a stack frame

• Look down the stack to find the name

• If not found, add to the current (top-most) frame

Implementing Definition

def do_func(env, args):
    assert len(args) == 2
    params = args[0]
    body = args[1]
    return ["func", params, body]

• Should check that parameters are strings

Implementing Call

def do_call(env, args):
    # Set up the call.
    assert len(args) >= 1
    name = args[0]
    values = [do(env, a) for a in args[1:]]

    # Find the function.
    func = env_get(env, name)
    assert isinstance(func, list) and (func[0] == "func")
    params, body = func[1], func[2]
    assert len(values) == len(params)

    # Run in new environment.
    env.append(dict(zip(params, values)))
    result = do(env, body)
    env.pop()

    # Report.
    return result

A Test

["seq",
  ["set", "double",
    ["func", ["num"],
      ["add", ["get", "num"], ["get", "num"]]
    ]
  ],
  ["set", "a", 1],
  ["repeat", 4, ["seq",
    ["set", "a", ["call", "double", ["get", "a"]]],
    ["print", ["get", "a"]]
  ]]
]

2
4
8
16
=> None

Dynamic Scoping

• Searching active stack for a variable is called dynamic scoping

• Have to trace execution to figure out what a variable might refer to

["seq",
  ["def", "lower", [], ["get", "x"]],
  ["def", "one", [], ["seq", ["set", "x", 1], ["call", "lower"]]],
  ["def", "two", [], ["seq", ["set", "x", 2], ["call", "lower"]]],
  ["print", ["call", "one"]],
  ["print", ["call", "two"]]
]

1
2
=> None

Lexical Scoping

• Almost all languages used lexical scoping

• Decide what a name refers to based on the structure of the program

• More efficient for the computer: doesn't have to search each time

• More efficient for the person: limits scope of reasoning

• More complicated to implement

• But enables a very powerful programming technique

Closures

def make_hidden(thing):
    def _inner():
        return thing
    return _inner

has_secret = make_hidden(1 + 2)
print("hidden thing is", has_secret())

hidden thing is 3

• The inner function captures the variables in the enclosing function

• A way to make data private

A More Useful Example

def make_adder(to_add):
    def _inner(value):
        return value + to_add
    return _inner

adder_func = make_adder(100)
print(adder_func(1))

101

Objects

def make_object(initial_value):
    private = {"value": initial_value}

    def getter():
        return private["value"]

    def setter(new_value):
        private["value"] = new_value

    return {"get": getter, "set": setter}

object = make_object(00)
print("initial value", object["get"]())
object["set"](99)
print("object now contains", object["get"]())

initial value 0
object now contains 99

Objects

Summary