Questions on processing DSL in tagless-final

Learning
1

Hi, I am thinking to use tagless-final style to rewrite a small project on DSL. Actually it’s a set of DSLs with small variants. For each of them, I have already check interpret pp functions for them. As you might see, there is lots of code duplication.

I start to read Oleg tutorials and papers (http://okmij.org/ftp/tagless-final/). I have two questions to ask before reading many details in them.

  1. The program of that DSL is written in text and I have a parser to get an Ast.t for it in my parser.
    if I use tagless-final style, what will the parser be? Instead of an Ast.t, the parser builds a function e.g. fun () -> plus (int 1) (int 1) where the plus and int can be defined in some Semantics module? If I hope to get a syntax tree, it seems I need a representation of the Ast.t?

  2. I have some processing functions e.g. constant_folding : Ast.t -> Ast.t which I can get another valid(need checking…) Ast.t. How should I write this kind of function in the tagless-final style?

2
  1. I think that your intuituion about fun () -> plus (int 1) (int 1) is right
  2. http://okmij.org/ftp/tagless-final/course/lecture.pdf page 15
1 Like
3

Oleg addresses the so-called de-serialization problem at Sect. 2.3 of http://okmij.org/ftp/tagless-final/course/lecture.pdf . It all boils down to how abstract your AST is. I tend to think that, in most situations, the AST will be complex enough that you will need a pass transforming the AST in your DSL. Considering that you may have to perform quite a bit of analyses on the structure during this pass and that the corresponding function will be partial (due to possible non-syntactic errors in the AST), I think it makes sense for the AST to inhabit an algebraic type (“initial” style), and only the DSL to be in final style.

1 Like