5 ms·

My favorite solution to the expression problem is the tagless-final style. It can be implemented in both ML-likes and Haskell-likes leveraging either expressive

My favorite solution to the expression problem is the tagless-final style. It can be implemented in both ML-likes and Haskell-likes leveraging either expressive module systems or type class systems to combine the benefits of both shallow and deep embedding of DSL's. It requires one to bend their mind to really understand but once it clicks it is extremely powerful. Perhaps that "click" is the mind snapping once sufficiently bent. http://okmij.org/ftp/tagless-final/ http://okmij.org/ftp/tagless-final/ "The so-called ``tagless-final'' style is a method of embedding domain-specific languages (DSLs) in a typed functional host language such as Haskell, OCaml, Scala or Coq. It is an alternative to the more familiar embedding as a (generalized) algebraic data type. It is centered around interpreters: Evaluator, compiler, partial evaluator, pretty-printer, multi-pass optimizer are all interpreters of DSL expressions. Doing a tagless-final embedding is literally writing a denotational semantics for the DSL -- in a host programming language rather than on paper."

Twisol 6y ago
Tagless-final is also closely related to the technique of object algebras [0], which I use pretty often -- at least at the design stage, before flattening out some of the degrees of freedom. See this other blog post [1] for more about both. [0] "Extensibility for the masses", https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf [1] "From Object Algebras to Finally Tagless Interpreters", https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...
- bitdizzy 6y ago
  Lovely! I think it speaks to the value of an idea that it is developed independently more than once. It should be noted as it is in the abstract of your first reference that these are elaborations on the core idea of Church encodings (and Boehm-Berarducci encodings).
- dwenzek 6y ago
  There is also that video [0] discussing object algebras as a solution to the expression problem. [0] "Who's Afraid of Object Algebras?" https://www.infoq.com/presentations/object-algebras/ https://www.infoq.com/presentations/object-algebras/

Twisol 6y ago

Tagless-final is also closely related to the technique of object algebras [0], which I use pretty often -- at least at the design stage, before flattening out some of the degrees of freedom. See this other blog post [1] for more about both. [0] "Extensibility for the masses", https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf [1] "From Object Algebras to Finally Tagless Interpreters", https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-object-algebras-to-finally-tagless-interpreters-2/ https://oleksandrmanzyuk.wordpress.com/2014/06/18/from-objec...

bitdizzy 6y ago
Lovely! I think it speaks to the value of an idea that it is developed independently more than once. It should be noted as it is in the abstract of your first reference that these are elaborations on the core idea of Church encodings (and Boehm-Berarducci encodings).
dwenzek 6y ago
There is also that video [0] discussing object algebras as a solution to the expression problem. [0] "Who's Afraid of Object Algebras?" https://www.infoq.com/presentations/object-algebras/ https://www.infoq.com/presentations/object-algebras/