LIFE

LIFE (Logic, Inheritance, Functions and Equations) is an experimental programming language designed by Hassan Aït-Kaci. It started at MCC in Austin, Texas, in the late 1980s and was developed further at Digital Equipment Corporation’s Paris Research Laboratory (DEC PRL) in the early 1990s. LIFE takes Prolog as its base and changes three things. Records with named fields and a hierarchy of types (ψ-terms) replace Prolog’s fixed-arity terms. Functions can be called inside logical expressions. When a function’s arguments are not yet known, the call is suspended and resumed later (residuation). The result fits logic, functional and object-oriented programming into one unification-based framework.

LIFE was a research language and never a commercial product. Its ideas matter more than its user base: the order-sorted feature terms at its core became a standard tool in computational linguistics, and according to the HOPL history of Oz, Oz’s record data type was “inspired by LIFE”.

A note on the date. The encyclopedia catalogue gives LIFE’s year as 1986. That is the year of LOGIN, LIFE’s direct predecessor, published by Aït-Kaci and Roger Nasr in the Journal of Logic Programming. The earliest dated document that describes LIFE itself is a February 1988 MCC technical report, so this page uses 1988.

History & Origins

The ψ-term calculus

LIFE grew out of Aït-Kaci’s 1984 PhD thesis at the University of Pennsylvania, A Lattice-Theoretic Approach to Computation Based on a Calculus of Partially-Ordered Type Structures. The thesis defined ψ-terms: record-like structures whose head symbol is a sort drawn from a partial order, whose subterms are named by features (attribute labels) rather than by position, and which can share substructure through tagged variables. Unifying two ψ-terms takes the greatest lower bound of their sorts and merges their features. This makes inheritance part of unification itself.

Three languages, one molecule

At MCC, Aït-Kaci and his colleagues explored the idea by combining ψ-terms with other programming styles, one pair at a time. In the later DEC PRL report Towards a Meaning of LIFE, he and Andreas Podelski drew the result as a triangle, the “LIFE molecule”:

LIFE first appears in LIFE, a Natural Language for Natural Language by Aït-Kaci and Patrick Lincoln, MCC Technical Report ACA-ST-074-88, dated February 1988. The paper argues that computational linguists lose too much effort to programming overhead “even [in idioms] as ‘advanced’ as Lisp or Prolog”, and presents LIFE as a remedy. A revised version appeared in 1989 in the French computational linguistics journal T. A. Informations. Its acknowledgements credit Roger Nasr with a “momentous contribution to the conception and architecture of LIFE”.

The first implementation, Still Life, was a partial interpreter for LIFE written in Prolog by David Plummer.

DEC Paris Research Laboratory

By early 1989 Aït-Kaci had moved to DEC’s Paris Research Laboratory in Rueil-Malmaison. On 6 April 1989 he gave a talk at MIT titled “An Overview of LIFE”, noting that “this work was done while I was at MCC in Austin, Texas.”

At PRL, Aït-Kaci set up the Paradise project to develop LIFE’s theory, implementation and applications. Its members included Andreas Podelski, Kathleen Milsted, Peter Van Roy, Richard Meyer, Bruno Dumant and Abder Aggoun. Podelski and Aït-Kaci gave LIFE a formal semantics in Towards a Meaning of LIFE (PLILP, Passau, August 1991; extended in the Journal of Logic Programming 16, 1993). That work recast LIFE as an instance of the Höhfeld–Smolka constraint logic programming scheme, over what they called Order-Sorted Feature (OSF) logic.

Wild_Life, a LIFE interpreter in C, grew out of Richard Meyer’s original implementation and was completed by the PRL group; the CMU AI Repository credits it to Peter Van Roy, Richard Meyer and Jean-Claude Hervé. Version 0.91, the first full implementation of the language, came out in December 1992 according to Van Roy (the CMU archive dates it 11 February 1993). Version 1.0 followed in March 1994, alongside a prepublication edition of The Wild LIFE Handbook, and the 1.01 “portability” release in April 1994. PRL also joined the European ACCLAIM project (1992–1995) on concurrent constraint languages, where LIFE was one of three core languages alongside SICS’s AKL and DFKI’s Oz.

Closure and afterlife

Digital’s financial troubles reached PRL in 1993. Aït-Kaci left the lab that May, and Van Roy took over the group, now renamed Proteus. Work on LIFE continued until DEC closed the laboratory at the end of September 1994. In a June 1994 message, Van Roy announced that the LIFE project at PRL was discontinued, that a new LIFE effort was starting at Simon Fraser University in Vancouver under Aït-Kaci, and that the partial compiler Half-Life was available on request.

Simon Fraser’s Intelligent Software Group later released Wild_Life 1.02, with bug fixes and experimental extensions copyrighted 1994–95. Hassan Aït-Kaci died in April 2020, and a memorial workshop was held in his honour at Université Claude Bernard Lyon 1 on 26 September 2025.

Design Philosophy

The PRL papers describe LIFE as “a trinity” of three components:

• Relations, taken from Prolog: Horn clauses, unification and backtracking, which can “construct missing information as needed”.
• Functions, taken from functional programming: higher-order functions, data constructors and pattern matching. Functions are deterministic and are called by matching (entailment), not unification.
• Types, from the ψ-calculus: sorts in a partial order with multiple inheritance, and records whose features act like object attributes.

What joins them is residuation. If a function is called before its arguments are known well enough to match, LIFE suspends the call. The call resumes automatically once later unifications provide the missing information. As a result, programmers can mix functional and logical code freely without managing evaluation order by hand.

Key Features

ψ-terms: records with inheritance

A ψ-term has a sort, optional features and optional shared variables. A first-order Prolog term f(a, b) is treated as shorthand for the ψ-term f(1 => a, 2 => b). Unification merges features from both sides:

1
2
3
4

> A = person(name => "Ada", age => 36), A = person(city => "London")?

*** Yes
A = person(age => 36,city => "London",name => "Ada").

Sorts are declared in a hierarchy with <| (subsort) and := (definition by enumeration). Predicates can then range over whole types as well as individual values. The following program comes from Towards a Meaning of LIFE:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

student := {peter;paul;mary}.
student <| person.
grade := {goodgrade;badgrade}.
goodgrade := {a;b}.
badgrade := {c;d;f}.
goodgrade <| goodthing.

likes(X:person,X).
likes(person,goodthing).
likes(peter,mary).

got(peter,c).
got(paul,f).
got(mary,a).

happy(X:person) :- got(X,Y),likes(X,Y).
happy(X:person) :- likes(X,Y),got(Y,goodthing).

The clause likes(person,goodthing) says that every person likes every good thing. It is a single fact over two types, and inheritance makes it apply to mary and a. The paper says the query happy(X:student)? returns Mary twice, then Peter, then fails. Wild_Life gives exactly that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

> happy(X:student)?

*** Yes
X = mary.
--1> ;
*** Yes
X = mary.
--1> ;
*** Yes
X = peter.
--1> ;
*** No

Functions and residuation

Functions are written with ->. When a function’s arguments are unbound, LIFE suspends the call until they are bound. Here is a factorial written for this page:

1
2

fact(0) -> 1.
fact(N:int) -> N * fact(N - 1).

1
2
3
4

> Y = fact(N), N = 4?

*** Yes
N = 4, Y = 24.

fact(N) cannot be evaluated when it is first reached, because N is unknown. It is suspended, and it runs as soon as N = 4 is unified. Prolog would raise an instantiation error here.

The paper’s lefun.life example shows the same mechanism working inside unification:

1
2
3
4
5
6

p(X, Y) :- q(X, Y, Z, Z), r(X, Y).
q(X, Y, X+Y, X*Y).
q(X, Y, X+Y, (X*Y)-14).
r(3, 5).
r(2, 2).
r(4, 6).

The first clause of q leaves a suspended equation X+Y = X*Y. Then r proposes values, and the equation rejects the pairs that do not satisfy it. The query p(X,Y)? returns X = 2, Y = 2 and then X = 4, Y = 6, which satisfies the second clause’s X+Y = X*Y - 14.

Other features

• Higher-order functions and keyword currying. Because arguments are features, a function can be partially applied on any argument by name, not only from left to right.
• Sort constraints. Sort definitions can carry attached constraints. These “daemons” run whenever an object of that sort is created by unification.
• Prolog compatibility. Van Roy’s summary notes that LIFE “derives its syntax and resolution method from Prolog, and it is straightforward to modify Prolog programs to run under LIFE.” Wild_Life keeps its syntax close to Edinburgh Prolog.
• Environment. Wild_Life added an X Window System interface, whose events feed into the residuation mechanism, plus incremental file I/O and an Emacs mode.

Implementations

The revised version of the natural-language paper, updated after Wild_Life existed, offers one performance comparison, for its English parser. Under Still Life on a Sun-3, it says, simple sentences took a few seconds and long ones over a minute. Wild_Life was “about 50 times faster than Still Life”, and on a DECstation 3100 the parser’s performance “matches that of compiled Common Lisp on a Sun 3”. These are the authors’ informal observations on their own parser, not a controlled benchmark, and they compare different machines. Van Roy’s 1994 announcement likewise describes Half-Life as “competitive in performance with emulated SICStus Prolog” without published figures.

An earlier email of Van Roy’s, from March 1994, reports Wild_Life running on Alpha/OSF-1, MIPS/Ultrix, SPARC/SunOS, SPARC/Solaris, SGI/IRIX, PC/Linux and PA-RISC/HP-UX by March 1994, with partial ports to RS/6000/AIX, NetBSD and DOS, many contributed by outside users.

Evolution

LIFE developed through papers more than releases. The surface language stayed close to its 1988 form, while the theory under it was reworked several times: first as the ψ-calculus, then as OSF logic within the Höhfeld–Smolka constraint logic programming scheme (1991–93), and later as a feature constraint system with entailment developed with Gert Smolka (1992). Work on the implementation moved from the Prolog prototype to the C interpreter and then toward compilation. The compiler was never finished, because PRL closed. After Wild_Life 1.02, no further official release is known.

Current Relevance

LIFE is a historical research language with no active development. The Wild_Life 1.02 sources survive. Dennis J. Darland has kept a port on GitHub (djdarland/WildLIFE) since 2019, which builds on modern Linux and with some effort on macOS. The code still carries DEC’s 1990s licence, which allows only non-commercial research and educational use. No Docker image exists.

Why It Matters

• Inheritance through unification. LIFE showed that multiple inheritance could live inside a logic language’s core operation instead of being added on top. Order-sorted feature structures of this kind became central to unification-based grammar formalisms in computational linguistics.
• Functions in logic programs. Residuation offered a principled way to mix deterministic functions with nondeterministic relations, without forcing the programmer to manage evaluation order.
• A link to Oz. Through the ACCLAIM project, LIFE’s records inspired Oz’s record data type, according to the Oz designers’ HOPL history of Oz. Van Roy, who moved from PRL to Saarbrücken (DFKI) to work on Oz, describes Oz as eventually combining “most of the good ideas of AKL and LIFE”.

LIFE is a good example of a research language whose influence came through its ideas rather than its users: a small group’s attempt to make Prolog a language that is also functional and object-oriented.