1. 16
  1. 7

    I think what made “constructor substitution” click for me was this diagram.

    In OO, constructor substitution is called the “visitor pattern”: a TreeVisitor specifies what to do at each Node and Leaf; a ListVisitor specifies what to do at each Cons and Nil. There was a recent post about this, (same author) The visitor pattern is essentially the same thing as Church encoding.

    There’s a neat practical application: if you’re going to produce a tree and then immediately consume it, you can take a short cut by letting the tree-producer call the visitor directly. Instead of new Node(left, right), you write visitor.handleNode(left, right), so no actual nodes get allocated.

    Lark, a parser-generator for Python, uses this technique to make the API nice. By default, you don’t have to write any grammar actions; it defines the classes and builds the tree for you. If you want more control, you can write a visitor that transforms the Lark tree into your own custom classes. Then to eliminate the overhead, you can pass your visitor into the parser and it will construct your tree by calling into the visitor directly.