Q/A.
> It says in the handout the substitution rules in MinML can be assumed 
> to cause no capture, but I cannot get example test code below to work,
> due to a weird capture/scope problem.
It's due to a normal scope problem, not a weird capture problem, I think.
 
> (fun m(n:int):int is
>  (fun a(m:int):int is
>   if m = n+1 then 1
>   else (fun n(a:int):int is
>         (fun f(n:int):int is
>          if n = m then 0 else a+f(n+1) fi end)(0) end)
>        (a(m+1)) fi end)(1) end)
> (10);
> 
> When I try to apply substitution rule recursively from top to replace
> occurrence of variable 'n' and function call 'm', this causes
> 'm' inside "if m = n+1" to be replaced by the function 'm', instead of
> the parameter inside the second function 'a', since both of them
> are defined as Vars inside the exp tree.
> 
> I am not sure about what really happens, since the step output becomes
> so messed up, but if I rename function and variable name as follows,
> the evaluation works perfectly:
> 
> (fun M(n:int):int is
>  (fun A(m:int):int is
>   if m = n+1 then 1
>   else (fun N(a:int):int is
>         (fun F(p:int):int is
>          if p = m then 0 else a+F(p+1) fi end)(0) end)
>        (A(m+1)) fi end)(1) end)
> (10);
> 
> So, am I supposed to worry about that kind of special case when I
> am recursing down to do the substitution, or is this code mistake,
> or am I missing something very important here?
Yes, your program should handle the cases where identifiers are used 
repeatedly. The first code is a good target example which your solution 
should evaluate succesfully. 

The point you are missing is that a substitution should not work once
it encounters a new declaration of the same identifier on which the substitution
is already defined. For example, suppose that G(f) and G(x) are well-defined,
that is, they do not raise an exception. If G is applied to 
'fun f(x:int):int is e end', its effect on f and x must be 'turned off' when
it is applied to 'e'. Your implementation should take into account this fact;
otherwise, the above example would fail to be evaluated in your program.

Gla

--------

1. Running a correct version of SML
The following examples shows how to invoke a correct version of SML.

On SCS machines,

[ux7.sp.cs.cmu.edu:156 ] setenv SML_VERSION 110.9.1
[ux7.sp.cs.cmu.edu:157 ] which sml
/usr/local/bin/sml
[ux7.sp.cs.cmu.edu:158 ] sml
Standard ML of New Jersey v110.9.1 [FLINT v1.41], October 19, 1998 [CM;
autoload
 enabled]
- Compiler.Control.lazysml := true;
val it = () : unit
- CM.make();
...
- use "test.sml";
...

On Andrew machines,

unix6.andrew.cmu.edu% setenv SML_VERSION 110.9.1
unix6.andrew.cmu.edu% /afs/cs.cmu.edu/local/sml/common/005/bin/sml
Standard ML of New Jersey v110.9.1 [FLINT v1.41], October 19, 1998 [CM;
autoload
 enabled]
- Compiler.Control.lazysml := true;
val it = () : unit

2. Course newsgroup
is cyrus.academic.cs.15-312.announce and
cyrus.academic.cs.15-312.discuss.
You can post a message on either of these by sending an email to
post+academic.cs.15-312.announce@andrew.cmu.edu and
post+academic.cs.15-312.discuss@andrew.cmu.edu.

3. Homework handin
If you cannot find your handin directory, let me know.
The first homework is due at 6:00pm this Friday. Soon after the
deadline, the permission on your directory will be reset so that you
cannot write onto the handin directory any further. So, make sure that
you can copy your files by the deadline.

Q. 
I have another question, though...
In the ps file, it says the signiture for the type synthesis module should
be like figure 3, but the file typing-sig.sml does not include most of
that signiture.  In specific, am I free to make the environment type
something other than string -MinML.typ, like (string, MinML.typ) list?
A.
typing-sig.sml must contain only the signature for the two functions,
namely, typeOf() and typeOpt(); you MUST NOT modify or add to typing-sig.sml.
The reason is that the user of your type checker would be interested only
in these two functions, not the details on the actual implementation.
This implies, therefore, that you can define the signature for other functions
in whatever way you want. For example, in a very extreme implementation, the
two functions may have been defined on their own (without ever employing
other functions or type env at all.

However, we provided you with the signature for the type synthesis module
just to give a guideline to write your own type checker. The interface
for functions ++ and typing is well defined enough to eliminate the need
to modify it. So, I encourage you to have your implementation match the
signature provided in the handout. 

As for type env, I agree that you can come up with a better alternative.
Surely, env = (string, MinML.typ) list would be the better choice. But,
this homework is intended to help you make sense of the meaning of each
concept found in type checkers. For example, the natural semantics of 
environment is a function from identifier to type, not a list of identifier
and type. And, it should be clear that string -MinML.typ is no harder to
implement than (string, MinML.typ) list. How ? And, Okay ?

Q.
Also, the typing rules in figure 2 give inference rules for true and
false, even though in our function, we only need to have a case for Bool
to return the type.  Does our function have to mimec the figure 2 exactly?
A.
Correct, you need to have only one case for Bool, not two cases for true
and false separately.

A.
Change in "parse.sml"
  fun reserved s = List.exists (fn x => x = s)
         ["int","bool","->","true","false","=","+","-","*","~","if",
          "then","else","fi","fun","end","(",")",":",";"]
to
  fun reserved s = List.exists (fn x => x = s)
         ["int","bool","->","true","false","=","+","-","*","~","if",
          "then","else","fi","fun","end","(",")",":",";","is"]
                                                          ^^
A.
I will have office hours today from 3:00pm to 4:30pm (Wean 8207), and
tomorrow, I will keep my official office hours only (from 1:30pm to 3:00pm).

A. If you dropped this course, let me know. Otherwise, you will receive
an unpleasant email saying that your first homework score is zero :)

A.
Only for those who registered for recitation A: the recitation location for
the next week will be announced as soon as I find it.

Q.
Do we have to implement variable renaming?  The homework handout
mentions that we don't have to bother with avoiding variable capture,
but it also says to carefully follow the definition of substition as
well.
A.
You don't have to implement variable renaming; you may assume that there 
does not occur any variable capture, that is, we will consider only
closed expressions.

A.
One student asked me about applying substitution to function expressions, 
and I discovered my explanation was wrong. 
Suppose that we want to apply substitution G to
expression 'fun f(i:t1):t2 is e end'. His question was about whether we have
to apply G to 'e' or not. The answer is yes; so, the result of this substitution
would be something like 'fun f(i:t1):t2 is G(e) end' (but not exactly). 

The reason is that expression 'e' may contain some variable which was declared
elsewhere. See the following example:
'apply(fun f(i:int):int is apply(fun g(j:int):int is j + i end, 1) end, 2)'
, which would be reduced to
'apply(fun g(j:int):int is j + 2 end'

You can assume that G is undefined for the identifiers 'f' and 'i' because we 
assume that input expressions are all closed. But, you must take into account
the fact that the identifiers 'f' and 'i' may appear in 'e' as in recursive
functions.

Q/A.
> First off, am I correct in my value function, which says Int's Bool's and
> Fun's are values, and nothing else?
Correct!

> Then in my step function, if you pass step a value, it should raise the
> Stuck exception right?
Correct!!

> However if you have let's say an If expression, If(c,e1,e2) and c is not a
> value, do you return If(step(c),e1,e2)?  It would seem to me then that you
> would always end up raising stuck at the bottom of the recursion.
No!!!
Compare these two evaluations: the first is wrong, the second is right.
IF(e, e1, e2) -> If(step(e), e1, e2) -> step(step(step(e)), e1, e2)
IF(e, e1, e2) -> If(step(e), e1, e2) -> step(If(step(e), e1, e2))
Now, can you see why the answer is 'No!!!' ?
(The reason is that eval() is a single-step evaluator, not a multi-step
evaluator.)

Q. 
On page 9 of the assignment, it says: "Your algorithm should follow the
definition of substitution from the course notes very closely."
Unfortunately, I cannot find this in the course notes anywhere. Am I just
overlooking it, in which case what is the URL of the appropriate pdf or
postscript, or is it just not posted? Thanks,
A.
Course handout, "MinML abstract syntax", page 4.