[Haskell-cafe] Generic Traversal of ASTs

[Simon Thompson]

Hi Richard - one thread of the history of work is in the “strategic programming” work of Stratego (untyped) and Strafunski (implemented in Haskell) by Eelco Visser and Ralf Lämmel (resp.).

  https://strategoxt.org/Stratego/StrategoLanguage.html

  https://link.springer.com/chapter/10.1007/978-3-540-25935-0_13

  https://www.researchgate.net/publication/220802944_A_Strafunski_Application_Letter

We explicitly used this approach in our first implementation of Wrangler (with Strafunski), and continue in other work to take this approach. For example “stop_top_down” is used heavily.

HTH

Simon

On 24 May 2021, at 21:51, Richard Yu <richardyu042 at gmail.com<mailto:richardyu042 at gmail.com>> wrote:


CAUTION: This email originated from outside of the organisation. Do not click links or open attachments unless you recognise the sender and know the content is safe.


I have a question about generic traversal/transformation of nested data structures. From what I understand the main options available are SYB, Uniplate, GHC.Generics and Data.Lens (although I am under the impression this requires record types). The data structure I am attempting to traverse is similar to this simplified version:

data SExpr = Expr | Const
data Const = B bool | I int
data Expr  = Lambda String SExpr | If Expr ...

I have attempted to use Uniplate and GHC.Generics to traverse the built AST and modify for example, the string of a Lambda type, but have not been able to figure out how to get any of the libraries to typecheck. The examples or docs I found were not quite enough. Does anyone know of examples that might help or explain how I should be using the generic libraries?
In addition if I moved to writing the AST with GADTs, do some generic traversal strategies/libraries stop working?


Many thanks,
Richard





_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

Simon Thompson | Professor of Logic and Computation
School of Computing | University of Kent | Canterbury, CT2 7NF, UK
s.j.thompson at kent.ac.uk<mailto:s.j.thompson at kent.ac.uk> | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt<http://www.cs.kent.ac.uk/~sjt>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210525/c71beada/attachment.html>