Project 4-Up! Cps Optimization

Due: Oct 25, 2006

“While CPS’ed programs make control-flow explicit, the resulting output is inefficient, and still far removed from the format necessary to enable efficient code generation. For this project, you will simplify CPS programs. While there are many optimizations possible, we will concentrate on particularly important one:
Continuations that are not exported via a Non-Tail call, and which are instantiated
at most once via a Goto, can be inlined at the point of call.”

http://www.cs.purdue.edu/homes/suresh/502-Fall2006/project/cps-opt.tgz

 

Statistics

Just thought this was funny.

 

More tests!

These are just some straightforward tests. If anyone has others, please post. Sign up for an account: http://www.wordpress.com . It’s quick and spam-free!

(* The following are a list of my tests
 * Each are one line (except a few at the bottom
 * and DO NOT EXECUTE THE ENTIRE FILE at once.
 *)
let fun f(x) = x in 13 end
let fun f(x) = x in f(13) end
(*make sure applying f not just returning 13*)
let fun f(x) = 7 in f(13) end
(*tail and nontail*)
let fun f(x) = let fun g(y) = x in g end in (f(13)) 7 end
(*binop*)
let val x = 4 + 2 in x end
let fun f(x) = 7 in f(13) + 5 end
let fun f(x) = 7 in 5 + f(13) end
let fun f(x) = let fun g(y) = x + y in g end in (f(13)) 7 end (*20*)
let fun f(x) = let fun g(y) = y + x in g end in (f(13)) 7 end (*20*)
(*anon funcs*)
val _ = (fn(x) => x) 13
let fun f(x) = (fn(y) => y + x) in (f(13)) 7 end
(*Unary funcs*)
val _ = ~(1 + 3)
(*tuple*)
let fun f(x) = 1 + x in (f(13), f(14), f(7), f(5)) end
(*Subscripts*)
val _ = #2 (5, 6, 7)
(*refs and order-of-eval-in-tuples/binops*)
val _ = ! (ref 0)
let val r = ref 0 val _ = (r := 1) val _ = (r := 2) in !r end
(* Should the following return 1 or 2? *)
let val r = ref 1
    fun setTwo(x) =
      let val _ = (r := 2)
      in 0
      end
in !r + setTwo()
end
(* Should the following return 1 or 2? *)
let val r = ref 1
    fun setTwo(x) =
      let val _ = (r := 2)
      in 0
      end
in setTwo() + !r
end

let val r = ref 1
    fun two(x) = (r := 2)
    fun five(x) = (r := 5)
in (!r, two(), !r, five(), !r)
end

(*ifthenelse*)
let fun fact(n) = if n < 1 then 1 else n * fact(n-1) in fact(4) end
(*Datatypes*)
let fun iotaHelper(x) =
      (case x
         of (0,l) => l
          | (n,l) => iotaHelper(n-1,Cons(n,l)))
in iotaHelper(3,Nil)
end
(* Non-exhaustive Case tests: *)
let fun test(p) =
      case p
        of 0 => 0 

in (test 0)
end
(* at this point you can try test-map.mml
 * SUGGESTION: change the noisy flag to false (cps-interp.sml line 382)
 * Otherwise, you'll be sitting around for hours ; )
 *)

 

My $.03 on Project 3

Anyone else done with Project 3? If not and you want to meet, give me a call: (214) 404-8096. Until then I’ll post some thoughts on the project.
Allthe work is in cps.sml’s cps function. Basically, you’re just connecting work you recursively did with the current computation (whether it’s a binop, apply, tuple, etc)

The cps function has 3 args: ce, ko, and kl. Now you may be wondering “Well when the heck do I use ko and kl??” That’s easy:

• ko : this will be NONE when there is nothing left to do after computing ce
• kl : this is ALWAYS appended to, and NEVER removed from. You will have to append every continuation created to it

Suggested ordering for implementing the body of cps:

1. LetRec : Simple let fun ... without applications.
2. App : Get Tail and NonTail working. This should be the first time you’ll create a continuation. So you’ll need: Label, Id, RetVal, Ret. make sure you prepend the cont you created before returning!
3. BinOp, UnOp : The tough part’s done (assuming you tested app thoroughly) so these should two should be a breeze. Notes: Take advantage of buildSimpleCont. You can’t test if you are evaluating binops correctly until you have ref‘s done
4. Fn
5. Tuple : Here, I used List.foldr 3 times Notes: Take advantage of buildSimpleCont. You can’t test if you are evaluating tuples in the right order until you can create side-effects
6. Ith, SetIth : These are needed for refs
7. Retest Binops and Tuples. Create a test and run it in SML/NJ and compare. Note: Assignments in MiniML don’t return unit.
8. If
9. Constructor
10. Error

Once you decide to try out test-map.mml I’d suggest unsetting the noisy flag (cps-interp.sml line 382). Otherwise you’ll be sitting around for hours waiting for the compiler to print.

Some tests to get started:

let fun f(x) = x in 13 end
let fun f(x) = x in f(13) end
(*make sure applying f not just returning 13*)
let fun f(x) = 7 in f(13) end
(*tail and nontail*)
let fun f(x) = let fun g(y) = x in g end in (f(13)) 7 end

Happy coding!

 

Some insight for absolute ML beginner

Here’s some random stuff I found useful after discussing with Phil on “how to start writing ML.”

1. use eval_be to handle binary operations and eval_ue for unary operations.

2. use conv() to handle A.Const_e and A.DataCon_e

3. patMatch() basically handle two cases: “Let val …” and “case … of …” both of these requires pattern matching (that’s why it is there).

4. Before you handling A.Let_e(A.Val_d(…)) in patMatch, it is a good idea to study how A.Case_e() works in patMatch. That should give you some hint on how to proceed.

5. Don’t worry about the A.Id_t(“pat”) or A.Id_t(“patType”) that you found in interp.sml. They are not used at all.

6. http://www.standardml.org/Basis/list-pair.html contains useful function to use when handling A.Tuple_p and A.Record_p in pat_compile. Specifically you need to walk down the tuple/records and perform matching one by one. ListPair is different from List where ListPair walk down two lists simultaneously (your root and p) whereas List do the same thing on one list.

7. Lastly, the assignment statement “x := 3” returns a unit “()”.

 

But first, a Shameless Plug (in)

A lot of time with SML, at least initially, will probably be spent fighting with the compiler. Specifically the cryptic compiler errors that are spit out. For those that are not fearful of IDE’s here’s a nifty plugin for eclipse that parses your SML and puts thosse infamous squigglys under the BAD parts of code. It works (hehe) and has been tested but I offer little support for the plugin. Attached is the zip file that you extract unto your eclipse/plugins dir.

The plugin creates a SML perspective and does all the nifty syntax highlighting for your sml (and sig) files. If you have smlnj installed, you can also optionally run the program from withing eclipse, or use MLton to typecheck every time you save (useful, but possibly time consuming). If there is interest, I’ll post how to do all of those.

Unlike the java editor however, it has no debugging/breakpoint support. After all, it’s only written by two people (but eclipse hackers are welcome to contribute!)

So, without further ado, here’s the link to the zip file:

http://www.cs.purdue.edu/homes/schatzp/cs502/ml-dev_2006-08-26.zip

And the user guide (a little older):

http://www.cse.iitd.ernet.in/~csu02132/mldev/userguide/

 

Interpreter Binary

If anyone wants to check their project, pasting the code into smlnj is the best way, but if you’re on a linux machine you can run my compiled binary. It has a debug option that will print out the expression tree on every iteration of eval (type “:d” into the interpreter to toggle)

Changes to get interpreter to work on MLton:

1. Run MLton versions of ml-lex and ml-yacc (smlnj uses Unsafe structure)
2. Change some matches in typecheck.sml
3. Add mlb, and main SML file that just runs the interpreter

The following tar.gz file has the MLton modifications and my compiled interpreter:

http://www.cs.purdue.edu/homes/schatzp/cs502/cs502-interp_mltonized_2006-08-26.zip