Lrc: A Purely Functional, Higher-Order Attribute Grammar based System
A system developed at Utrecht University by: Matthijs Kuiper, Doaitse Swierstra, Marteen Pennings, Harald Vogt, Joćo Saraiva

(this page was produced/processed by DocProc : a tool generated by Lrc. The Lrc logo (left) was also produced by another tool/AG library included in Lrc)

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]


Pagina mantida por:

Joćo Saraiva

jas@di.uminho.pt
Page produced by a Tool generated by LRC from the XML document lrc.xml

Last Change on Tue Aug 27 14:54:46 2002