Home

The L10 Logic Programming Language

L10 is a forward chaining logic programming language. That means you can write programs like this:

path: string -> string -> rel.
path N M, path M P -> path N P. 
example = (path "a" "b", path "b" "c", path "c" "d").
#query after: path + -.

The intended behavior of this program is that you seed the path relation by declaring some facts (the definition of example declares three such paths). The implementation will then use the rule on line 2 to learn new facts (like path "a" "c", path "b" "d", etc. etc.) from existing facts until it has learned all there is to know (this is called "saturation").

Therefore, you can ask an L10 implementation questions like this:

"What are all X such that path "a" X holds?"

(The third line of this example, {-# QUERY after path + - #-}, expresses exactly this query and names it after. Given the example facts, the after query will respond that this is true for X = "b", "c", and "d".

Features

The above example is just about the simplest example possible! L10 differs from Datalog implementations because it has types and structured terms. L10 also has a unique and logically-motivated concept called worlds; worlds are used to justify locally stratified negation and demand-driven saturation. We are also exploring the use of worlds as a basis for distributed and parallel logic programming on top of the X10 language, a distributed programming language being developed by IBM Research.

The language specification says a little bit more about the surface syntax of the language, and there are a number of examples.

Implementations

There are three existing or currently planned implementations of the L10 language, all of which are implemented in the Standard ML programming language. The most interesting one is the Elton compiler, a compiler from L10 to Standard ML. The Elton compiler can be used much like ML's versions of Lex and Yacc, but instead of generating a lexer or a parser, you generate a deductive database.

Smlten - Standard ML Interpreter (Working)

The interpreter was the first working implementation of the L10 langauge. Smlten is does not execute L10 programs in parallel, but it is being used to develop and simulate ideas for parallel execution that can then be executed into the compiler to X10 (Elten).

Elton - Compiler to Standard ML (Working)

Elton works much like ML Lex or ML Yacc - you feed Elton an L10 program and it outputs a series of signatures and structures that can be incorporated into a standard ML development. The Elton interpreter is entirely sequential.

See the Elton compiler page for more information.

Elten - Compiler to X10 (Planning stages)

Elten and Elton will behave much the same way, except that while Elton emits Standard ML code for incorporation into a Standard ML development, Elten will emit X10 code for incorporation into an X10 development. In addition, Elten will be designed to handle databases that exist at different places within the PGAS model that underlies the X10 programming language.

See the Elten compiler page for more information.