fun f(x:int) : int =
let a = x + 2 in
let x = a*a in
x+1
|
int f(int x) {
int a = x+2;
{int x = a*a;
return x+1;
}
}
|
fun f(x:int) : int =
let a = x + 2 in
let x2 = a*a in
x2+1
|
int f(int x) {
int a = x+2;
{int x2 = a*a;
return x2+1;
}
}
|
Examine the file cfold.sml. The module interface ("signature") declares two functions; the first is rename_prog that takes one parameter of type Absyn.prog and returns a result of the same type. This is to be the alpha-converter. Inside the module implementation ("structure") you'll see that rename_prog is implemented to return the original program; you should make it do alpha-conversion.
The suggested method is to take a variable named (for example) foo and, if its definition is in the scope of another variable named foo, rename it to foo'. However, you'll need to add enough primes (apostrophes) to its name to avoid all clashes with variables in scope. Then, keep track of the current renaming of foo, and in the body of the let...in expression that binds foo, rename all the applied occurrences.
The algorithm, therefore, is to do a recursive traversal of each function body, keeping track of two different things:
type env = Symbol.symbol Symbol.tableEach env maps a symbol to a symbol option, that is, either NONE or SOME(id) for some symbol id.
The invariants are:
Now, before you start traversing each individual function definition, you need to record in the environment all the global variables that are in scope. The globals are the library functions and the functions declared in this program. There is exactly one library function named printint, and you can find the names of the functions in this program by traversing the list of fundecs. All these names need to be added to the initial environment, each name mapping to itself (since it can't occur within the scope of an identically named variable, it doesn't need to be renamed).
The formal parameter of each function, and the bound variable of each let, may need to be renamed. Every variable occurring in an expression must be mapped to its current renaming.
Beware! In the expression let id = e1 in e2, the expression e1 is not in the scope of the new definition! Thus, you must traverse e1 using the environment that was in effect before the let was encountered. The expression e2 is in the scope of the new id.
To add a prime to a variable name, you can convert the symbol to a string using Symbol.name, then add an apostrophe using string concatenation, s ^ "'", then convert back to a symbol using Symbol.symbol.
Implementation. Download as2.zip and examine compile.sml. This is a driver that parses a Fun program and hands it to your alpha-converter. It also prints and runs the program, both before and after alpha-conversion. Since alpha-conversion is supposed to produce an equivalent program, you should expect to get the same result by running the program.
You can assume the input program is well formed; for example, it is illegal for a Fun program to have two different top-level function declarations with the same name, but you can assume that won't happen. (It is not illegal for two different functions to have a formal parameter or local variable with the same name.) I have put in the stub of a function bind that you might want to apply whenever you come across the binding occurrence of a variable (a function parameter x, let x = ..., or in the first pass, even a function name x). This takes a current environment and the name x (of the variable being bound here), and returns a new environment and a new variable such that:
let x = 6 in E(where E is some arbitrary expression) and substitutes 6 for every free occurrence of x within E. By free occurrence we mean those that are not within the scope of some inner binding of x. At that point, there is no use to bind 6 to x, so we can delete the let, yielding E[6/x] (which means, E with 6 substituted for x). [Do I need to say that your program should work for any integer literal, not just 6? I hope not.]
let x = y in Eto E[y/x].
Implementation. Replace the stub function cfold_prog in cfold.sml with an optimization function. You will find it handy to have an environment that maps each variable to its current rewriting, that is,
type env' = Absyn.exp Symbol.table
You can assume that the alpha-converter has been run before cfold_prog, so therefore there will never be a variable nested within the scope of another variable with the same name.
Write a very short Fun function
slower(x: int) : int = ...that performs one multiplication and one addition; but if you were to apply general beta reduction, it would do two multiplications and one addition. Show the function slower' that results from doing the transformation.
Write a very short Fun function
wrong(x: int) : int = ...that produces a different answer if you apply general beta reduction to it. (Hint: use ref) Show the function wrong' that results from doing the transformation.
Upload here. Submit a README file along with your cfold.sml file. Into it put: