search

joaoraf / kiama

Automatically exported from code.google.com/p/kiama
GNU Lesser General Public License v3.0
7 stars 2 forks source link

readme

Overview

Kiama is a Scala library for language processing. It enables convenient analysis and transformation of structured data. The programming styles supported by the library are based on well-known formal language processing paradigms, including attribute grammars, tree rewriting, abstract state machines, and pretty printing.

Kiama is a project of the Programming Languages Research Group in the Department of Computing at Macquarie University and is led by Tony Sloane (inkytonik on GMail and Twitter). Other participants at Macquarie are Dominic Verity, Matthew Roberts and the PLRG group students.

Collaborators on the Kiama project have included the Software Engineering Research Group at the Delft University of Technology in The Netherlands, notably Eelco Visser and Lennart Kats.

Latest News

How to find out about Kiama

Examples

A traditional approach to language processing is to represent the data to be processed as a hierarchical structure (a tree). Kiama provides different ways to operate on such trees to carry out typical language processing tasks.

Context-sensitive attribute equations

Attribute equations define properties of tree nodes in terms of constants or the properties of other nodes. In this example, the local and global minima of a binary tree (locmin and globmin) are defined using simple local equations. The arrow notation denotes accessing an attribute (property) of a node. The attr function provides caching and circularity checking to the equations. The parent field provides access to the parent of a node.

val locmin : Tree ==> Int =
    attr {
        case Fork (l, r) => (l->locmin) min (r->locmin)
        case Leaf (v)    => v
    }

val globmin : Tree ==> Int =
    attr {
        case t if t isRoot => t->locmin
        case t             => t.parent[Tree]->globmin
    }

Circular attribute equations

Sometimes it is useful to define attributes using a mutual dependency. With attr this approach would lead to an error since it would not be possible to calculate the values of such attributes. The circular function goes further by implementing mutually dependent attributes via an iteration to a fixed point. In this example, we are calculating variable liveness information for a imperative language statements using the standard data flow equations.

val in : Stm ==> Set[Var] =
    circular (Set[Var]()) {
        case s => uses (s) ++ (out (s) -- defines (s))
    }

 val out : Stm ==> Set[Var] =
    circular (Set[Var]()) {
        case s => (s->succ) flatMap (in)
    }

Rewrite rules and higher-order rewriting strategies

While attributes provide a way to decorate a tree with information, rewriting is concerned with transforming trees, perhaps for translation or for optimisation. Kiama contains a strategy-based rewriting library heavily inspired by the Stratego program transformation language. In this example, we are implementing an evaluation strategy for lambda calculus, using generic strategies such as innermost rewriting.

val beta =
    rule {
        case App (Lam (x, t, e1), e2) =>  Let (x, t, e2, e1)
    }

val lambda =
    beta + arithop + subsNum + subsVar + subsApp + subsLam + subsOpn

def innermost (s : => Strategy) : Strategy =
    all (innermost (s) <* attempt (s <* innermost (s)))

lazy val s : Strategy =
    innermost (lambda)

Pretty-printing

Kiama's pretty-printing library provides a flexible way to describe how you want your output to be produced within constraint of line length. For example, the following describes how to pretty-print the constructs of a simple imperative language, where group, nest and line cooperate to produce nicely indented code that breaks lines at sensible place when needed.

def show (t : ImperativeNode) : Doc =
    t match {
        case Num (d)      => value (d)
        case Var (s)      => s
        case Neg (e)      => parens ("-" <> show (e))
        case Add (l, r)   => showbin (l, "+", r)
        case Sub (l, r)   => showbin (l, "-", r)
        case Mul (l, r)   => showbin (l, "*", r)
        case Div (l, r)   => showbin (l, "/", r)
        case Null ()      => semi
        case Seqn (ss)    => group (braces (nest (line <> ssep (ss map show, line)) <> line))
        case Asgn (v, e)  => show (v) <+> "=" <+> show (e) <> semi
        case While (e, b) => "while" <+> parens (show (e)) <> group (nest (line <> show (b)))
    }

def showbin (l : ImperativeNode, op : String, r : ImperativeNode) : Doc =
    parens (show (l) <+> op <+> show (r))

Supporters

Work on this project has been supported by the following Universities, funding agencies and companies.

Delft University of Technology, The Netherlands

Eindhoven University of Technology, The Netherlands

Netherlands Organization for Scientific Research

YourKit

YourKit is kindly supporting open source projects with its full-featured Java Profiler. YourKit, LLC is the creator of innovative and intelligent tools for profiling Java and .NET applications. Take a look at YourKit's leading software products: YourKit Java Profiler and YourKit .NET Profiler.

CloudBees

CloudBees provides generous support to FOSS projects for continuous builds and other services, for which we are very grateful. Kiama nightly builds are built on a CloudBees Jenkins instance, part of their DEV@cloud service.