Remotable Functional Visitors
A design pattern

paper table of contents

introduction
  * abstraction of trees
  * common example: constraint generation
  * use cases: name analysis, reusable damas-milner





  * the visitor pattern and its uses
  * problem with visitors
    implicit state transitions
          * the AST represents updatable state
          * visitors change this state
          * no explicit pre and post conditions
            on visits; not enforced
            source of bugs
          * memory retainment / parallelism
  * functional visitors
      algebra, with functions
      explicit state transitions
  * problems with functional visitors
      behaves poorly with non-local data-exchange
        * local exchange between parent and direct children in the AST
        * direct communication to remote nodes in the AST hard
        * exchange def-site, use-site
  * fixed traversal order
      * complex traversals
          * imperative visitors: easy, iterate differently over the nodes
          * functional visitors: need to guarantee the state transitions
      * traversal on a different data structure
          * merge results back in the tree
          * common situation (a.k.a. "abstraction")

imperative visitors
  * example
     * introduce the repmin problem
     * variation on repmin, instead of on a tree on a list
         advantage: standard traversal for on a tree
  
    explain encoding of visitors
      generic zipper with IO refs in the data structure
    explain a concrete visitor for RepMin
    particular nice parts
      * ease of accessing the state of Nodes
    specific pain points
      * update of the variable in the leafs
      * questionable which traversals can be
        combined or run in parallel

functional visitors
  * give example for repmin on list
  * indicate problems
      * exchange data between tree and list
      * in general: visit order over the tree is fixed
          to deviate: traverse a different structure
  * explain that a more rigorous solution is needed
  
  * implementations of functional visitors
      (initial algebras, comonadic)

other examples
  name analysis
  extensible damas-milner

functional visitors
  * interface
  * encoding to Haskell
  * semantics
  * Haskell code
  * special domain-specific language

the analysis
  * graph
  * effects

related work
  * attribute grammars
      * reference attributes
      * door attributes
      * forwarding
  * zippers
      in between functional and imperative visitors