CODEWITHSUNDEEP
iteratorcursorocamltraversalabstract-syntax-tree
zpavlinovic
zpavlinovic

Reputation: 1547

OCaml tree iterator

Imagine having an AST of some programming language and you want to execute command by command using a keystroke, so you can observe what is happening to the state. Also, you would like to repeat visiting a subtree if you have while loops, for example. What would be the easiest way to implement this in OCaml?

I have a dirty solution where I explicitly keep control of the program, where control is defined as the current block, current command, and parent control so I can return easily back. However, is there a nicer way of doing this? Maybe continuations? I also found this work, but am not sure is that the best and cleanest way to go.

Upvotes: 2

Views: 629

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66818

I've always heard that the suavest way to handle this kind of traversal is with a zipper. Here's an OCaml mailing list message that shows how to make a zipper for a tree structure:

Using zippers to handle huge trees

(For what it's worth, it's not so different from what you describe. But I hear zippers are nice because they have a clean structure that you can derive straightforwardly from the data structure.)

Update

(You can figure out the structure of a zipper by taking the derivative of the type you wish to traverse: The Derivative of a Type Is its Type of One-Hole Contexts, Derivatives of Containers. This is old news for some, but I still find it impressive and pleasantly mind-bending.)

Upvotes: 3

Thomash
Thomash

Reputation: 6379

Jean-Christophe's papers are always very good and they usually correspond to the cleanest way to do things in OCaml. Zippers are good too (they are mentionned in the paper by the way) but a little less performant according to Jean-Christophe.

Upvotes: 3

Related Questions