Which of these possible passes to tackle?

[rrnewton]

See also #4 about what language we should compile. And see #5 about non-AST tree benchmarks.

Does not keep environment

• Basic desugaring and other simple passes: e.g. (let->((lambda
• Substitution -- needs only fixed old/new arguments.

  Keeps environment:

I.e. needs to maintain a dictionary/finite-map structure as it walks down the tree.

• Constant prop / constant folding
• Beta reduction (representative of simplification/inlining)
• Type checking (Sarah is working on this)
• Interpreter

  Needs state:

• Renaming / gensym
• Hygenic macro expansion (stateful and more interesting)

  Other:

• Program analysis, abstract interpreters, or basic dataflow analyses

[rrnewton]

I propose substitution as the first pass we implement widely. It's a basic building block that is used in many places. Opinions?

[milindkulkarni]

I think that makes sense.

On Oct 11, 2016, at 4:09 PM, Ryan Newton notifications@github.com wrote:

I propose substitution as the first pass we implement widely. It's a basic building block that is used in many places. Opinions?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/iu-parfunc/tree-velocity/issues/3#issuecomment-253030917, or mute the thread https://github.com/notifications/unsubscribe-auth/ACDCg2s-TFNNMArJQ-calFUnXT5ywizkks5qy-0XgaJpZM4KT9K1.

---

Milind Kulkarni Associate Professor School of Electrical and Computer Engineering Purdue University http://www.engineering.purdue.edu/~milind

[rrnewton]

Even though it's simple, I'm finding some interesting aspects to this subst pass over Racket core data:

• the core datatype is small but not trivial, there are some almost-the-same cases to handle
• there are subtrees that don't need to be processed. E.g. you don't need to run subst over module import specs
• there is the question of whether subst needs to be rigid in checking invariants / well-formedness of its input data. Especially when implementing a transform in Racket, it is easy to write it to be overly permissive and accept bad/non-gramattical inputs.

My inclination is to allow sloppiness in the last point. In a real compiler checking well-formedness would happen in some earlier pass. Most of our implementations will use strong types for the input ASTs, so their grammatical structure will be ensured anyway.

[rrnewton]

I think another "pass" that provides a useful microbenchmark is just "countNodes". Subst captures the common pattern of tree-in-tree-out. countNodes represents a fold over an input tree.

Other patterns include:

• zip two trees together (e.g. like in type unification)
• duplicate a tree (1 in, 2 out)

[milindkulkarni]

Yeah, the kd-tree pass Laith is doing is an example of a fold, too.