ABSTRACT

• We propose an algebra of languages and transformations as a means for extending languages syntactically. The algebra provides a layer of high-level abstractions built on top of languages (captured by context-free grammars) and transformations (captured by constructive catamorphisms).

• The algebra is self-contained in that any term of the algebra specifying a transformation can be reduced to a constant catamorphism, before the transformation is run. Thus, the algebra comes "for free" without sacrificing the strong safety and efficiency properties of constructive catamorphisms.

• The entire algebra as presented in the paper is implemented as the Banana Algebra Tool which may be used to syntactically extend languages in an incremental and modular fashion via algebraic composition of previously defined languages and transformations. We demonstrate and evaluate the tool via several kinds of extensions.

BANANA ALGEBRA

L  :  l                      // constant language (context-free grammar); l = { ... }
   |  v                      // language variable
   |  L \ L                  // language restriction
   |  L + L                  // language addition
   |  L [m / n]              // language renaming
   |  src ( X )              // extract source language from transformation
   |  tgt ( X )              // extract target language from transformation
   |  let v = L in L         // local language definition 
   |  letx w = X in L        // local transformation definition
   |  "file.l"               // include language from file

X  :  (| L -> L [T] c |)     // constant transformation (catamorphism); x = (| ... |)
   |  w                      // transformation variable
   |  X \ L                  // transformation restriction
   |  X + X                  // transformation addition
   |  X o X                  // transformation composition
   |  X [m / n]              // transformation renaming (source language)
   |  idx ( L )              // identity transformation of language
   |  let v = L in X         // local language definition
   |  letx w = X in X        // local transformation definition
   |  "file.x"               // include transformation from file

The syntax of the "Banana Algebra" (as a language, written in itself): banana.l :-)

EXAMPLE EXTENSIONS

Lambda Calculus:
   [ l.l ]                    // the basic lambda calculus
   [ l.x ]                    // the identity transformation on the lambda calculus
   [ ln.l ]                   // numeral extension
   [ ln2l.x | ln2id2l.x ]     // numeral extension to basic lambda calculus
   [ lb.l ]                   // boolean extension
   [ lb2l.x ]                 // boolean extension to basic lambda calculus
   [ lnb2l.x ]                // numeral and boolean extensions to basic calculus

ABC:
   [ abc.l ]                  // the ABC programming language
   [ repeat.x ]               // repeat-until extension
   [ uminus.x ]               // uminus extension
   [ uminus_repeat.x ]        // uminus and repeat-until extensions to ABC

Java:
   [ java.l ]                 // the Java programming language
   [ repeat.l ]               // repeat-until extension
   [ repeat2java.x ]          // repeat-until extension to Java

Banana Algebra (itself):
   [ banana.l | tau.l ]       // the Banana Algebra language (itself)
   [ cfg.l | cata.l ]         // the constant layer of the Banana Algebra 
   [ overwrite.l ]            // the overwrite extension to Banana Algebra
   [ overwrite.x ]            // the overwrite extension to Banana Algebra

FUN:
   [ lambda.l ]               // the basic lambda calculus
   [ lambda-to-fun ]          // various extensions (lambda to Fun)...

DOWNLOAD TOOL

• The Banana Algebra Tool (by Jacob Andersen & Claus Brabrand, 2008). Thanks to Sharjeel Imam for experimental extensions.

• Note: The tool requires the following underlying technologies (which also have to be installed at an appropriate visible location):
  • O'Caml: The Objective Caml compiler.
  • XSLT: Extensible Stylesheet Transformation.
  • XSugar: xsugar-all.jar (slightly modified version for The Banana Algebra Tool)

PRESENTATION

• "Banana Algebra: Syntactic Language Extension via an Algebra of Languages and Transformations"
          ((( Presentation for LDTA'09 conference, York, England (March 28, 2009) )))

PUBLICATIONS

• "Syntactic Language Extension via an Algebra of Languages and Transformations" ((( bibtex )))
          ((( Jacob Andersen and Claus Brabrand ( LDTA'09, York, England ) )))
• "Syntactic Language Extension via an Algebra of Languages and Transformations"
          ((( Jacob Andersen and Claus Brabrand (Technical Report, IT University of Copenhagen, December 2008) )))