Christian Lindig

fon +49 681 302 5590
fax +49 681 302 4397
pgp 3CB9047D
Christian Lindig
Schloss Dagstuhl
Office Saarbrücken
Saarland University, Postfach 15 11 50
Building E1.1, Room 227
66041 Saarbrücken, Germany

Software

All software listed below was developed on Linux and Mac OS X and is released under an Open Source license. The source code of most projects is hosted at Google Code from where you can download it with Subversion.

Quick C--

Quick C-- is an implementation of the portable assembly language C--. It is intended for compiler writers to be used as a target language. C-- aims to solve the following problems:

The design of C-- is discussed in several papers that you can find on www.cminusminus.org.

Just to give you an idea, below is Hello World implemented in C--. You will probably agree that this is pretty close to assembler code and therefore best created by a compiler and not by a human.

target byteorder little;

import bits32 printf;
export main, my_data;

section "data" {
  my_data: bits8 [] "hello, world!\n\0";
}

foreign "C" main("unsigned" bits32 iargc, "address" bits32 iargv) {
  foreign "C" printf("address" my_data);
  foreign "C" return(0);
}

Quest

Quest is a tool for testing calling conventions in a C compiler. It grew out of my observation that calling conventions are difficult to get right and I suspected that many compilers would have these difficulties. Indeed, Quest found bugs in GCC and other compilers:

Quest generates C code which includes assertions. When compiled and run, failing assertions indicate compiler bugs. This can be done without any manual supervision. The code generation process is controlled by pluggable random generators which may be extended or replaced by the user.

Quest is described in the following paper: Christian Lindig. Random Testing of C Calling Conventions. In Jong Deok Choi and Raimondas Lencevicius, editors, Sixth International Symposium on Automated and Analysis-Driven Debugging, ACM Press, Monterey, CA, USA, September 2005. Download PDF

OCaml Burg

OCamlBurg generates tree-matching code for Objective Caml from a specification. It was used to implement the code-generation phase of the Quick C-- compiler. OCamlBurg belongs to the same family of tool as Lex and Yacc, which also generate code from specifications. And just like these, OCamlBurg is most useful for compiler writers.

Assume you have a numeric expression that you want to evaluate. Further assume that the expression is represented as a tree and that you have numerical operations to implement the evaluation. To make things interesting, you don't just have add, multiply, and so on, but several of them, each with its own associated cost. Selecting the right operations for evaluation is now no longer straight forward. OCamlBurg generates code that selects the optimal operations for a given expression.

Below is an example specification for OCamlBurg. There are four rules for Add nodes. Besides the base case x+y with cost 2 (in square brackets) there are additional rules for special cases. For example, adding zero can be optimized to an operation with cost 1, and adding two zeroes can be evaluated at immediately. In the example the evaluation is carried out immediately. In a real compiler the actions in curly braces would actually emit instructions that then would perform the evaluation when executed.

%term int string            -- terminal types must be declared
%type number {: int     :}  -- type declarations for nonterms are optional
%type str    {: string  :}

%%

number : Add(x:number,  y:number)                    [2]    {: x + y :}
number : Add(x:number,  Add(y:number, z:number))     [2]    {: x + y + z:}
number : Add(x:number,  Const(0))                    [1]    {: x     :}
number : Add(Const(0),  Const(0))                    [0]    {: 0     :}
number : Sub(n:number, m:number)                            {: n-m :}
number : Mul(n:number, m:number)                            {: n*m :}
number : Div(n:number, m:number)    {: if m = 0 then assert false else n/m :}
number : Const(x: int)                               [1]    {: x :}
number : Const(0)                                    [0]    {: 0 :}

-- Terminal variables are bound in cost expressions
str    : Str(x: string)          {: String.length x :}      {: x :}
str    : Cons(x: string, y:string)                   [2]    {: x ^ y :}

-- recursive chain rules
-- "number" is an abbreviation for "number:number"
str    : n:number                    [1]   {: string_of_int n      :}
number : str                         [1]   {: int_of_string str    :}

The example code is included in the distribution of OCamlBurg. You can find it also discussed here.

Concept Analysis

Formal Concept Analysis is a theory to study binary relations. A binary relation can be also represented as a cross table and hence, formal concept analysis can be thought of as a theory and tool to study cross tables. A formal concept corresponds to a maximum rectangle in such a cross table. These form a hierarchy which gives insight into the table.

Colibri/ML and Colibri/Java are based on my papers Fast Concept Analysis and Mining Patterns and Violations Using Concept Analysis.

Ample

Ample is a defect localization tool for Java. From many passing and a single failing unit test it suggests a location for the defect that caused the unit test to fail. The paper Lightweight Defect Localization for Java explains how it works and how it stacked up against the competition. This is joint work with Valentin Dallmeier.

OCaml Annot

OCaml Annot (on Google Code) is a command-line application to parse type annotations produced by the OCaml compiler. Typically this is used from inside an editor to observe the inferred types for source code expressions.

This project was taken over by Anil Madhavapeddy anil@recoil.org who has published updates of OCaml Annot on GitHup.

Code Contributions

Projects where I contributed some code:

Logos

I designed the logos for the programming systems Standard ML of New Jersey, Mozart/Oz, and Gecode.

Papers

Most Recent Papers

Aspect Mining

Compiler

Formal Concept Analysis

Program Analysis

Functional Programming

Software Engineering Education

Other Papers