|
1- What is lrc?
Lrc is a system for generating efficient incremental attribute evaluators. Lrc can be used to generate language based editors and other advanced interactive environments.
2- Features of lrc
The following features distinguish lrc from other attribute grammar systems.
- accepts higher order attribute grammars and normal attribute grammars
- processes attribute grammars that are written in the Synthesizer Specification Language
- generates purely functional evaluators (C and Haskell-based)
- generates evaluators that use function memoing to realise efficient incremental reevaluation
- generates editors with advanced interactive interfaces
- can bootstrap itself
3- History
The Lrc system is a generator for purely functional language-based systems developed at the
department of Computer Science
at Utrecht University. Matthijs Kuiper started constructing Lrc during his research on parallel attribute evaluation and he is the main developer of the system.
After having introduced higher-order attribute grammars, Harald Vogt, Doaitse Swierstra and Matthijs Kuiper extended the Lrc system to process higher-order attribute grammars.
Maarten Pennings conducted the first implementation experiments on incremental evaluation.
Joćo Saraiva worked on deriving purely functional attribute evaluators for higher-order attribute grammars, and added a Haskell back-end to the Lrc system.
In 1998, Matthijs Kuiper moved to
Ordina Institute
where he continued the development of Lrc. Matthijs Kuiper developed a new advanced graphical user interface for Lrc, and he is using Lrc in several industrial renovation projects.
In 1999, Joćo Saraiva finished his PhD thesis and returned to the
department of informatics
at Minho University where he is now using the Lrc system both in research and teaching activities. A set of generic, off-the-shelf attribute grammar components have been incorporated to the system.
4- Features of LRC In More detail
Input:
- Higher-Order Attribute Grammar
Attribute Grammar Specification Language: SSL
Features of the higher-order attribute grammar formalism:
- The Abstract Syntax Tree is not fixed during Evaluation
- Semantic Functions are Redundant:
Every Inductive Function can be Written in the AG formalism
No (foreign/alien) declarative language (and its processor) has to be included in the AG system
- Provides a Component-based style of Programming for the AG formalism
There are two Ordered Scheduling Algorithms defined in LRC:
Kastens and Pennings Algorithms
- They statically schedule the traversal functions
Thus, the AG writer does not concern himself in breaking-up his (elegant) algorithm into traversal functions and to glue such functions.
- They statically detect circularities
Termination of programs is statically guaranteed (for ordered AGs)
But, Semantic functions are not considered/analised by the standard AG techniques...
Output:
- Language-based Processors (
eg
, compilers, document processors, textual database processors, etc)
- Programming Environments (C based)
- Advanced Interfaces are easily specified (within the AG formalism)
- The Interface is incrementally computed
- Purely, Strict Functional Evaluators (C and Haskell based)
- Incremental Evaluators (C based)
- Tree's are collapse into DAGs using the
Hash Consing Techniques
- No repeated value is stored on the heap: Optimal Memory Consumption
- Efficient Equality Test Between Terms: A simple Pointer Comparison Suffixes
- Incremental Computation is obtained through Function Memoization
4.1- Other Features
- It is partially bootstrapped
- LRC front-end is written in LRC itself (The largest HAG ever written)
The scheduling algorithm induces a
11 traversal attribute evaluator
It would be very complicated to hand-write such an evaluator
- It produces portable C and Haskell code.
- LRC itself and the generated tools can be installed in any system with an ANSI C compiler and the Tcl/Tk toolkit.
- It generates deforested attribute evaluators (Haskell-based)
- It generates sliced attribute evaluators (Haskell-based)
(or, it extracts Aspects from an Attribute Grammar)
- It generates readable attribute evaluators
- It generates a colored LaTeX view of the Haskell based evaluators
5- Downloads
An older implementation of the Lrc system is public domain and it is available at the (former)
Lrc Homepage
This version of the system is not maintened/updated anymore. The new Lrc system (version 4.7) will be available here soon.
6- Interactive Interfaces in LRC
- Lrc Includes a Modern GUI, ie:
- Buttons, that can be pressed
- Menus, that can be selected
- etc
- The interface of the tools is defined within the AG formalism
- The interface is one attribute of the AG
- Therefor, under an incremental model of attribute evaluation, the interface is incrementally computed
- And, the interface is incrementally displayed
The Interactive Interfaces of Lrc are briefly described in this
text
.
7- Component-based programming in LRC
The Lrc system provides a component-based style of programming within the (higher-order) attribute grammar formalism. This style of AG programming is described in the paper:
- Joćo Saraiva,
Component-based Programming for Higher-Order Attribute Grammars
, proceedings of the ACM SIGPLAN SIGSOFT Conference on Generative and Component-Based Software Engineering (GPCE/PLI'02), Pittsburgh, USA, October 2002. (to appear)
ps
,
abstract
,
bibentry
7.1- Modular Specifications
- Different semantic domains (i.e., Aspects) can be splitted into different modules
- They are fused by production to form a monolithic AG
- The AG can be parameterized with the semantic functions
The semantic functions are expressed by higher-order attributes that are inherited by the HAG
- AG components can be plugged-into larger AGs through higher-order attributes
7.2- Library of AG Components
There are pre-defined in LRC a set of Attribute Grammar Components:
- Text Processor
- Document Processor
- Bibliographic Textual Database Processor
- Table Formatter
- Pretty Printing Combinators
- Html Combinators
- Simple Expression Evaluator
They are easily plugged-in into any AG specification within the AG formalism. For example, the document processor AG re-uses all the other components.
If you have a nice generic AG specification, let us know so that we could add it to the LRC component library.
8- Applications of LRC
- Used to Specify the Front-End of Lrc
- Used in Several Industrial Renovation Projects at Ordina Institute:
Ordina Institute.
- Used to Support Compiler Construction Courses
- University of Minho
- Utrecht University
9- Example: The BibTex Processor
The bibtex language is becoming a
de facto
standard for bibliographic databases. We have defined a simple programming environment for bibtext in Lrc. (The main part of this tool was defined in two days: in order to be included in the introduction of my thesis.)
bibtex will be available soon
10- Example: The Students Spreadsheet
- This tool was proposed as the
(second)
project the students had to develop in the Course on Language Processing in the scholar year 2000/2001.
- It re-uses the following AG components:
- Interactive Interface Combinators
- Simple Expression Evaluator
(first project)
- Table Formatter Combinators
- Html Combinators
The Attribute Grammar for this tool does not include a single semantic function definition. Every computation is defined within the AG formalism. Therefor, the ordered scheduling algorithm statically guarantees the termination of this tool for all possible (finite) inputs
Indeed, attribute grammar programming is programming with attributes and their equations !
The students spreadsheet will be available soon
Bibliografia
- Joćo Saraiva and Matthijs Kuiper
Lrc - A Generator for Incremental Language-Oriented Tools
7th International Conference on Compiler Construction, CC/ETAPS'98, Kay Koskimies, LNCS 1383
1998
- Doaitse Swierstra and Pablo Azero and Joćo Saraiva
Designing and Implementing Combinator Languages
Third Summer School on Advanced Functional Programming, LNCS 1608
1998
- Joćo Saraiva and Doaitse Swierstra
Data Structure Free Compilation
8th International Conference on Compiler Construction, CC/ETAPS'99, Stefan Jahnichen, LNCS 1575
1999
- Joćo Saraiva and Doaitse Swierstra and Matthijs Kuiper
Functional Incremental Attribute Evaluation
9th International Conference on Compiler Construction, CC/ETAPS'00, David Watt, LNCS 1781
2000
- Joćo Saraiva and Pablo Azero
Component-based Programming for Attribute Grammars
Joint Conference on Declarative Programming, Luis M. Perreira e Paulo Quaresma
2001
- Maarten Pennings
Generating Incremental Evaluators
1994
- Joćo Saraiva
Purely Functional Implementation of Attribute Grammars
1999
[PS]
|
