5 Written: Scope

This is your first written assignment. You answers can be plaintext, handwritten and scanned, marked up in LaTeX, etc. I do want you to submit them electronically, since it makes keeping track of the handin process much easier.

Each of these questions has a fully correct answer that isn’t longer than about 3-4 sentences (unless you decide to write code for the first question). If you need to make additional assumptions in your answer beyond what the problem states (e.g. "this only works in programs containing the number 5"), note that in your response. Be concrete and clear. These are due by midnight on Friday, March 6.

Unbound Identifiers

Describe an algorithm that calculates the set of identifiers in a Paret program that don’t have a corresponding binding position. That is, its signature is:

Expr -> Set<String> # (List<String> would also be fine)

Your algorithm should not reference interp or subst. The output should include identifiers without a binding even if running the program wouldn’t produce an error (for example, "x" should be included for (if true 5 x)). Feel free to describe the algorithm precisely in English or pseudocode, or actually write the code. Either way, provide a few interesting test cases with it. Assume the version of Paret from the functions interpreter.

Environment Size

Our interpreters have constructed closures by closing over the whole of the current environment at the point where the closure is created. Could they ever close over a smaller environment (e.g. with fewer mappings from identifiers to values), without changing the interpreter’s behavior? Either explain why not, or describe in which cases they can, and how the environment can be smaller.

Environments, Variables, and Loops

We saw in class and the reading that when creating closures in a loop, a typical for-loop leads to surprising output because of the shared variable. Does this problem occur when creating closures inside a call to map? Why or why not?

Scope and Changing Ids

Consider the function change over expressions:

data Expr:
  | e-num(n :: Number)
  | e-id(x :: String)
  | e-plus(left :: Expr, right :: Expr)
  | e-lam(arg :: String, body :: Expr)
  | e-app(fun-exp :: Expr, arg-exp :: Expr)
end

fun change-var(x :: String, s1 :: String, s2 :: String) -> String:
  if x == s1: s2
  else if x == s2: s1
  else: x
  end
end

fun change(expr :: Expr, s1 :: String, s2 :: String) -> Expr:
  c = lam(e): change(e, s1, s2) end
  cv = lam(x): change-var(x, s1, s2) end
  cases(Expr) expr:
    | e-num(n) => e-num(n)
    | e-id(x) => e-id(cv(x))
    | e-plus(e1, e2) => e-plus(c(e1), c(e2))
    | e-lam(arg, body) => e-lam(cv(arg), c(body))
    | e-app(fun-exp, arg-exp) => e-app(c(fun-exp), c(arg-exp))
  end
end

• Describe what change does in English.

• Assuming an environment-based interpreter, is there any expr for which the result of

  interp(change(expr, "x", "y"))

  differs from the result of

  interp(expr)

  ? Either explain why the results will always be the same, or provide examples and describe the cases that would produce different results.