### October 2006

Monthly Archive

October 16, 2006

Posted by Philip Schatz under

Uncategorized
Leave a Comment
**Reminder:** I have **no idea** what is on the exam. Like everyone else, I’m just speculating…

Possible Flow Analyses : Prof Jan Vitek‘s cs510 class has some interesting slides (see any similarities?) Particularly useful ones:

- Slide 53+ : The Overall Pattern
- Slide 63: A nice table of the analyses
- Slide 82+: Interprocedural Analyses (100-102 are caveats)

Possible compiler optimization/analysis that might be on the midterm:

Possible Language additions:

- Introduce “loop” primitive
- Create overloaded function (like + : ((int * int) -> int) | ((string * string) -> string))
- Adding OO constructs to the language (using records, maybe)
- Call-cc

As always, please post your speculations as well. Anyone interested in group ~~cramming~~ studying, say this evening 8:00p in LWSN common? (214) for oh for-8096

October 15, 2006

Posted by wmrh under

Uncategorized
1 Comment
I went through the lecture slides and jotted down some notes on anything that I was still confused about. Please feel free to comment on, answer the questions in, or added on to this list of questions:

Lecture 3:

slide 17:

Problem: In class, Prof. Jagannathan challenged us to come up with a case where the BFH fails.

Solution (?): given the bool and color datatypes, supply the following patterns:

p1 = (x, red)

p2 = (false, blue)

p3 = (true, green)

The tree generated by the BFH will have 10 nodes.

The optimal tree has 8 nodes.

Is this due to the prescence of variables in the bool position?

Lecture 4:

slide 26: Could “fn f => (f(13), f(true))” work if we could promise that the f passed in will always be over type variables, not concrete types? Is this the kind of power that explicit type variable systems (which he refers to on slide 9) have?

slide 36:

Question posed: “What about lists?”

Answer (?): A box just a pointer, so we would just make a pointer to the list, similar to how we box other non-word-sized data structures

Lecture 7:

slide 10: Question posed: “How might we identify loops in Core-ML?”

Answer (?): Label any recursive call as effectively being a loop

Lecture 8:

slide 11: Shouldn’t the third line of the first example be:

“in if b then g(13, k) else g(15, k’)” ?

Lecture 10:

slide 3: Given that direction is a component of program analysis, how can flow-independent analysis exist?

~Bill Harris

October 12, 2006

Posted by Philip Schatz under

project
[5] Comments
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

October 9, 2006

Posted by Philip Schatz under

project
Leave a Comment
Just thought this was funny.

October 9, 2006

Posted by Philip Schatz under

project
Leave a Comment
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 ; )
*)*

October 4, 2006

Posted by Philip Schatz under

project
[13] Comments
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:

`LetRec`

: Simple `let fun ...`

without applications.
`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!
`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
`Fn`

`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
`Ith, SetIth`

: These are needed for refs
- Retest Binops and Tuples. Create a test and run it in SML/NJ and compare.
**Note:** Assignments in MiniML don’t return unit.
`If`

`Constructor`

`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!