This webpage was created to accompany the submission of the paper
A Lightweight Functional Embedding of Attribute Grammars.
Here you can get the complete code (compiled under GHC 6.10.4) of
all the examples presented in the paper and the entire
implementation of the generic zipper library that is used throughout
the paper.
1. Introduction
In the introduction we review the
repmin problem, and we
present three different solutions for it (
Download Source).
Go to the top of the page
2. Huet's Standard Zipper
In this section of the paper, we present the zipper data structure
that allows us to navigate on binary leaf trees, and we use such
mechanism to navigate on a concrete tree (
Download Source).
Go to the top of the page
3. The repmin First Class Attribute Grammar
In the paper, we start by showing how the zipper data structure
defined in
section 2 (
Download Source) can be
used to implement an attribute grammar for solving the
repmin problem (
Download Source). We also draw some considerations
on how function memoization can improve our implementation. The
memoization primitive that we mention in the paper is implemented in
a small library (
Download
Source).
Go to the top of the page
4. The Generic Zipper
We then describe the use of a generalized form of the standard
zipper data structure introduced in
section
2. The code of the example that we use for this purpose, in the
paper, can be obtained here (
Download Source). It relies on the generic zipper
library that is introduced in
section 6 (
Download Source).
Go to the top of the page
5. The Algol 68 Scope Rules
The generic zipper framework described in the previous section (
Download Source) is
used here to implement an attribute grammar for a more realistic
programming problem: we implement a semantic analyzer for the Algol
68 scope rules (
Download
Source).
Go to the top of the page
6. A Library for Generic Zippers
Finally, we describe the implementation of the generic zipper, and
make it available as a library (
Download Source). The OCAML version of the repmin AG that we
mention in the paper can be found here (
Download Source).
Go to the top of the page
A zip file containing all the modules presented in this page can be downloaded
here.