HN Explorer

Ask HN: Easiest way to code AST transformations

2 points by scotty79 ↗ HN
When writing macros the main idea is to convert the tree that represents the code into a modified tree.

What is the best way to describe such alterations in non ad-hoc, more declarative manner?

The only thing that comes to my mind is something with a functionality of XSLT.

Do you know of some more light weight libraries in any language with similar capabilities as XSLT when it comes to transforming trees into other trees?

4 comments

[ 51.8 ms ] story [ 89.1 ms ] thread
gus_massa
Have you read about macros in Scheme/Racket? For example, with define-syntax-rule you can define a rule to transform code that looks like code.

  (define-syntax-rule (repeat3 body ...)
    (begin
      body
      body
      body))
and you just use it

  (repeat3 (print "Hello!"))
expands to

  (begin
    (print "Hello!")
    (print "Hello!")
    (print "Hello!"))
and the output is

  Hello!Hello!Hello!
scotty79
That seems like a simple substitution.

The body in your example is AST sub tree. What I want to do, is check it for occurence of some (multi-node) patterns and alter it so that those patterns transform into some other target patterns.

I would like to be able to specify those patterns in declarative manner.

Same way I describe transformations in xslt to transform one xml file into different similar xml file.

I could, in lisp macro, convert ast of `body` to xml tree, write xslt, apply it to that xml, convert back resulting xml into lisp ast and return if from macro.

But that seems like a bit of overkill. I'm searching for something that does descrptive tree transformations similar to xslt but more lightweight. More suitable for use in writing macros.

billconan
I need to simplify parse tree into an AST tree, I'm building a gui tool for drawing state machines, which will be translated to rust code that can do the job,
sargstuff
So, outlining the problem with the provided information:

1) Use gui interface to "draw" a grammer diagram describing the AST/modified

   tree (aka transition diagram / BNF / EBNF / w3 grammer specificatation(s)

   XSLT to use isn't in original request. XSLT grammer for "gui" is version dependent.  

   w3 specification(s) http://www.w3.org  Note:  things other XSLT too! 

   Example program(s) for the 'gui' edit: 

   https://tikzit.github.io/index.html or https://latex-cookbook.net/graph/

   Perhaps bootup a livecd (https://www.tug.org/texlive)
   or online https://www.overleaf.com/
   Use tikzi library from github or graph.tex from latex-cookbook
2) Take latex drawing & transform to lex/yacc description.

   https://github.com/rajnitish/Latex-to-Html-Lex-Yacc/blob/master/parser
3) Rust grmtools, https://softdevteam.github.io/grmtools/master/book has relevant libraries/tools to make use of files generated in step 2.

----------------

Automation idea: No programmer history/preferences for OS/language/environment specified.

So, shell script to "automate"/glue this all togehter as one command line program left as a reader exercise. ;)