Geekly Articles each Day
📜 ⬆️ ⬇️

Introduction to Template Haskell. Part 2. Citation Tools

This text is a translation of the Template Haskell documentation written by Bulat Ziganshin. Translation of the entire text is divided into several logical parts to facilitate perception. Further italics in the text - notes of the translator. Other parts:


Citation monad


Since the templates must return their values ​​wrapped in the monad Q , for this there is a set of auxiliary functions that “raise” (wrap in Q ) the constructors of the Exp , Lit , Pat types: lamE (respectively LamE ), varE , appE , varP , etc. d. Their signatures also use renumbered raised types: ExpQ = Q Exp , LitQ = Q Lit , PatQ = Q Pat ... (all of them can be found in the Language.Haskell.TH.Lib module). Using these functions, you can significantly reduce the code, less often using do-syntax.
In TH, there is also a lift function, which raises to Q Exp value of any type from the Lift class.
In some rare cases, you may not need to generate a unique name, but use the exact name of the identifier from an external (relative to the pattern) code. For these purposes, there is a (pure) function mkName ∷ String → Name . There is also an auxiliary function dyn s = return (VarE (mkName s)) , which returns the Exp value representing the variable with the given name ( dyn ∷ String → Q Exp ).

Quote brackets


Constructing Exp values ​​that represent an abstract syntax tree is a time consuming and boring job. But fortunately, Template Haskell has quoting brackets that translate a specific Haskell code into a structure that represents it.
They are of four types:

Accordingly, there should be a syntactically correct expression / declaration / type / pattern inside the brackets.
For example a quote [| λ _ → 0 |] [| λ _ → 0 |] is a structure (return $ LamE [WildP] (LitE (IntegerL 0))) . The quotation is of type Q Exp (and not just Exp ), so it must be computed inside the citation monad, which allows Template Haskell to replace all identifiers appearing within the quotation with unique ones generated with newName . For example, quote [| λx → x |] [| λx → x |] will be converted to this code:
 do id ← newName "x" return $ LamE [VarP id] (VarE id)

Further, inside the citing brackets, we can use inset (splicing), so that it turns out that TH acts as a macro preprocessor, processing part of the code written explicitly and part of the generated one. For example, quote [| 1 + $(fx) |] [| 1 + $(fx) |] calculate (fx) , which must be of type Q Exp , the result (structure of type Exp ), the result will be presented in the form of a usual Haskell-code and will insert ( paste ) it in place of $(fx) , and then continue quoting — converting the resulting code into a structure that represents it. Thanks to automatic renaming (actually, for this purpose everything is done inside the monad Q ) , inside the quotation there will be no conflicts of local variable names between different inserts of the same code. The following definition demonstrates this well:
 summ ∷ Int → Q Exp summ n = summ' n [| 0 |] summ' ∷ Int → Q Exp → Q Exp summ' 0 code = code summ' n code = [| λx → $(summ' (n-1) [| $code + x |]) |]

This pattern generates a lambda expression with n parameters that summarizes them. For example, $(summ 3) converted to (λx1 → λx2 → λx3 → 0 + x1 + x2 + x3) . Notice that the generated code uses different identifiers for the arguments of nested lambda expressions, although the pattern has one name: [| λx → … |] [| λx → … |] . As can be seen in this example, nesting of quotes and inserts can be any, but it is important that they alternate - you cannot quote inside the quotation and paste inside the insert.
Such “quasi-quoting” is a convenient way to represent Haskell programs. And it has some limitations: each occurrence of a variable is associated with the value that is in the scope that is available before the templates are expanded. This rule has three cases:
  1. Quoting brackets prohibit the “capture” of local variables used in one quotation from another (just as in a regular Haskell program, you cannot use variable closures outside of it). This is due, as mentioned above, to automatic unification of identifiers. Only quote [p| … |] [p| … |] does not rename those variables that the generated sample introduces (since these variables will be linked when matching with the sample and if they have new arbitrary names, it is not clear how to access them) .
  2. The global identifiers used in the quotation “capture” all the necessary identifiers available in the environment where the quotation is defined (again, as in ordinary Haskell), so the quotation value can be easily used in other modules that do not have access to all these internal definitions. or even have their own definitions for the same ids. This rule uses the internal GHC mechanism for references to characters from other modules (that is, qualifies them) . For example, quote [| map |] [| map |] will be converted to “ GHC.Base.map ”, and a quote like [t| [String] → Bool |] [t| [String] → Bool |] converted to “ [GHC.Base.String] → GHC.Bool.Bool ”. If you need identifiers precisely from the scope in which the template will be pasted, use the $(dyn "…") wrapper for them. It should be understood that this way you can accidentally use an identifier defined locally by someone else and a conflict will arise or the template will generate the wrong code, which is why it is written in the dyn documentation that this is not a hygienic function.
  3. Also, inside the citing brackets, you can use local variables of the function. At the compilation stage, these are variables (just related identifiers), but during the execution of the code, these are just constants, so TH simply substitutes the corresponding values ​​in their places. So, the expression let x = 5 in [| … x … |] let x = 5 in [| … x … |] will be converted to let x = 5 in [| … $(lift x) … |] let x = 5 in [| … $(lift x) … |] - that is, you do not need to manually wrap the local variable identifier in type Q Exp .

Inserting and quoting are mutually inverse operations: one converts the Exp structure into a Haskell code, and the other Haskell code into an Exp structure, so they mutually annihilate:
 $( [|  |] ) ≡  [| $(  ) |] ≡

This allows thinking only in terms of the generated Haskell code, developing TH programs, and not thinking about the internal structures that represent its syntax.
Consider for example the calculation of the “ $(summ 3) ” $(summ 3) . We will simply replace the use of the template with its definition:
  $(summ 3) $(summ' 3 [| 0 |]) $([| λx → $(summ' (3-1) [| $([| 0 |]) + x |]) |])

Now we can remove the extra $([| … |]) brackets $([| … |]) , replacing the “ x ” along the way with a unique identifier:
  λx1 → $(summ' (3-1) [| 0 + x1 |])

Again substitute the definition of summ' :
  λx1 → $([| λx → $(summ' (2-1) [| $([| 0 + x1 |]) + x |]) |])

Next, we will repeat the last two steps, while it is possible:
  λx1 → λx2 → $( summ' (2-1) [| 0 + x1 + x2 |] ) λx1 → λx2 → $([| λx → $(summ' (1-1) [| $([| 0 + x1 + x2 |]) + x |]) |]) λx1 → λx2 → λx3 → $(summ' (1-1) [| 0 + x1 + x2 + x3 |]) λx1 → λx2 → λx3 → $( [| 0 + x1 + x2 + x3 |]) λx1 → λx2 → λx3 → 0 + x1 + x2 + x3

Interestingly, in this definition, the left part of the lambda expression ( λx1 → λx2 → … ) is recursively constructed as the recursion unfolds, and the right part ( 0 + x1 + … ) at the same time accumulates in the remaining part of the pattern. The same technique is used in the printf sample template.
')

Example: printf


Now we will analyze the definition of the printf template, which was mentioned in the first part of the article. The following is a code with explanations, as well as a Main module that uses it. You can ghc -XTemplateHaskell --make Main.hs it with ghc -XTemplateHaskell --make Main.hs

Source: https://habr.com/ru/post/132679/

More articles:


All Articles