University of Toronto - Winter 2007
Department of Computer Science

CSC 324: Principles of Programming Languages

Assignment 4
Clarification Page

Communications

March 12: Recall that your assignment will be marked for correctness, style, and documentation. Please consult the following ML coding guideline. Also recall that if your code does not pass the ML type-checker, you will receive no marks for correctness.


Corrections or Clarifications

Question-Specific Clarifications


Question 1a
March 16 (Update to March 12 Clarification):
There have been a lot of questions about special cases for substitute, so I thought it would be a good idea to post a lengthy, final clarification. All of the potential problems arise when performing substitution inside of an Abs. Let's look at what might go wrong. First, a bit of terminology. We call the expressions created with Abs abstractions (hence the Abs). An abstraction is simply a function of one variable. We say that the abstraction binds this variable in the body of the abstraction, where the name of the bound variable is the first argument to Abs and the body is the second argument to Abs. So, what could go wrong with substitute? Let's look at some examples:

Case 1) The variable we are substituting by an expression occurs as the bound variable in an abstraction.
substitute("x", (Const 1) App(Abs("x", Plus(Var "x", Const 1)), (Const 3)))
The original expression represents (3 + 1), but if we perform substitution, we obtain the expression:
App(Abs("x", Plus(Const 1, Const 1)), (Const 3)))
which represents (1 + 1).

Case 2) The expression we are substituting for a variable contains a variable bound by an abstraction.
substitute("x", (Var "y"), App(Abs("y", Plus(Var "x", Var "y")), (Const 1)))
The original expression represents (x + 1), but if we perform substitution we obtain the expression:
App(Abs("y", Plus(Var "y", Var "y")), (Const 1))
which represents (1 + 1)

Case 3) The same variable is bound by several abstractions (this is not explicitly related to substitution, but is the same sort of problem):
App(Abs("y", App(Abs("y", Plus(Var "y", Var "y")), (Const 1))), (Const 2))
Does this represent (1 + 2) (1 + 1) (2 + 1) or (2 + 2)? It's hard to say. Most programming languages (including scheme) use the most recent binding, so all of the Var "y" expressions would be bound by the inner abstraction, and we would have (1 + 1), but it could theoretically be any of the above. You should assume that none of these cases occur. Consider the ML function substitute(n, e1, e2). We can represent this assumption as its preconditions as:
  1. n is not bound by any abstraction in e2.
  2. No variable occuring in e1 is bound by an abstraction in e2.
  3. Abstractions in e2 have fresh variable names (No Name is bound than one abstraction in e2 and no name bound by an abstraction occurs outside the body of the abstraction).
There is probably a simpler single precondition that subsumes all of these, but I feel that these are much clearer, as they point out all 3 problem cases. There are ways to deal with this problem rather than ignoring it, of course. We could dynamically rename variables to avoid problems 1) and 2), for instance. This is well beyond the scope of this assignment, however.

IMPORTANT: Just because you can ignore these cases doesn't mean you shouldn't state the above preconditions for substitute (and similarly for eval in the case of precondition 3). You will lose marks if you don't mention them (think of this as free marks for reading the newsgroup and the clarifications page).

March 12: In the examples for substitute, all comments of the form:
(* Substitute every "x" in the expression Var "x" by Var "y" *)
Should read:
(* Substitute every Var "x" in the expression Var "x" by Var "y" *)
This is in accordance with the text immediately before the examples.

March 12: You should assume the following two preconditions for substitute:
The name passed to substitute does not occur as the bound variable in any abstraction in the last argument to substitute. That is, the first argument of substitute should not occur as the first argument of any Abs in a subexpression of the third argument of substitute.

All variables introduced by function abstraction are fresh. That is, if an expression e contains subexpression of the form (Abs(n, e1)) then (Var n) does not occur outside of e1.

Thus, the following example is not a valid uses of substitute (and thus you don't need to worry about what happens in cases such as this):
substitute("x", Var "y", Abs("x", Plus( Var "x", Var "z")))
Similarly, the following is not a valid expression (and you don't need to worry about expressions such as this):
App(Abs("x", Plus(Var "x", Var, "z")), Mult(Var "x", Const 3))



Question 3
March 14 You do not have to implement the functions and hand in the code. The only thing you have to hand in in the file a4-3.sml is the type information that would be returned from a correct implementation of the function specification. This information is of course not legitimate sml code and if we actually loaded it, we would get all sorts of errors. (Naming the file with an ".sml" extension is misleading in this regard.)

Back to the main page