[Main website]

feature/attribute-grammar

:ROAM_ALIASES: AG

Bottom-up and Top-down navigation inside the AST.

It can be used for:

  • code analysis
  • code transformation
  • macro expansion

In Lisp many macro are a case analysis of the input synatx, so AG are useful.

In Nanopass there are transformations from one language to another, so AG transforming the tree are useful.

The DokMelody IDE should show the source data, the resulting data, and which part of source data generated the corresponding part of result data, and the part of code generating it.

TODO check the link with CHR, maybe they are based on pattern an AST and rewrite rule

TODO join the best idea of Nanopass (e.g. compact syntax based on small symbol of common types, and diffs by languages, and clear transformation to one language to another) with AG (e.g. top-down attributes, add additional attributes to the same AST).

TODO there are various types of AG semantic (e.g. with rewriting, with references, incremental, …), then study the best approach.

I’m designing them indok/example/attribute-grammars

AG semantic

[1]T. Kaminski e E. Van Wyk, «Integrating Attribute Grammar and Functional Programming Language Features», in Software Language Engineering, vol. 6940, A. Sloane e U. Aßmann, A c. di Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pagg. 263–282.

  • descrive molto bene le featueres di Silver che sono presenti anche nei linguaggi funzionali e che rendono le AG di Silver comode per programmare un po’ tutto
  • c’e` anche un discorso semantico del linguaggio
  • da usare per capire cosa serve anche sotto Dok

[1]A. Dijkstra, «Stepping through Haskell», [s.n.], S.l., 2005.

[1]A. Dijkstra, J. Fokker, e S. D. Swierstra, «The Structure of the Essential Haskell Compiler, or Coping with Compiler Complexity», in Implementation and Application of Functional Languages, vol. 5083, O. Chitil, Z. Horváth, e V. Zsók, A c. di Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pagg. 57–74.

UHC AG implementation of Haskell: a big compiler structured used AG

“Incremental Context-Dependent Analysis for Language-Based Editors” by Demers data una grammar crea un editor con incremental update, e deriva pretty printing, errors, etc..

TODO integrate with other papers:

  • AG
  • HOAG
  • RAG
  • Rewriting RAG

Efficient execution of AG code

[1]H. Alblas, «OPTIMAL INCREMENTAL SIMPLE MULTI-PASS AlTRIBUTE EVALUATION», INFORMATION PROCESSING LETTERS, pag. 7, 1989.

[1]J. A. B. V. Saraiva, «Purely functional implementation of attribute grammars = Zuiver functionele implementatie van attributengrammatica’s», Utrecht, 1999.

  • more important paper on Saraiwa method
  • attribute grammars
  • incremental evaluation
  • LRC system

[1]S. D. Swierstra, «Strictification of lazy functions», pagg. 1–12.

  • analyze FP code, with lazy semantic, using an AG
  • it can strictify some classes of FP programs
  • there are other papers citing this, with improved tecniques
  • it can do memoization and incremental update

Pettoross 1988 uses a different tecninque of strictification, based on HOAG.

In general optimizing RAG is more difficult because it does not suffice any more only static analysis but some relationships and dependencies are discovered at run-time. A naive but rather efficient tecnique is into memoization and caching of already computed attributes.

[1]J. Saraiva, «Strictification of Computations on Trees 1 The Class of Functions Considered», pagg. 1–15. transform generic AG from lazy to strict and ordered, and it applies deforestation. It is used in LRC.

This is the page with links to LRC project http://www3.di.uminho.pt/~jas/

[1]U. Utrecht e R. Magnifi-, Generating incremental attribute evaluators. 1994. a detailed analys of how evaluate AG

https://github.com/christoff-buerger/racr library compiling AG to scheme code with support of incremental rewriting.

INRIA worked on FLC-2: attribute grammars that can be used as standalone program.

@inproceedings{saraiva1999generic, title={Generic attribute grammars}, author={Saraiva, Joao and Swierstra, Doaitse}, booktitle={Second Workshop on Attribute Grammars and their Applications, WAGA}, volume={99}, pages={185–204}, year={1999} } “Generic Attribute Grammars” describes how to derive lamda functions from an HOAG with support of GENERICS, and derive a strict version. This paper describe the algorithm, but not the delta update version. This paper allows to share common parts visited by the same visitor.

[1]M. C. Pennings, «Generating incremental attribute evaluators = Het genereren van incrementele attribuut evaluatoren», Utrecht, 1994.

[1]J. Fokker e S. D. Swierstra, «Abstract Interpretation of Functional Programs using an Attribute Grammar System», Electronic Notes in Theoretical Computer Science, vol. 238, n. 5, pagg. 117–133, ott. 2009. simplify call of functions in Haskell-like code, using AG:

  • evaluate at compile-time the code
  • reduce the possible TAG that can be present at run-time
  • TODO compare with SmartEiffel approach
  • TODO there are papers saying that Abstract Interpretation can be used also for deriving good order of evaluations of params, on a call-by-need way but without using thunks at run-time. Similar to AG evaluation order.

[1]P. Correnson, «Symbolic composition», Bulletin of Sociological Methodology/Bulletin de Méthodologie Sociologique, vol. 37, n. 1, pagg. 55–57, dic. 1992.

  • synthesis of various approach
  • the syntax-tree result of the parsing is not materialized, but it is fused and processed on-demand
  • reduce materialization of data

Links to this note