Twelf

Twelf is an implementation of the logical framework LF. It is used for logic programming and for the formalization of programming language theory.

Introduction

At its simplest, a Twelf program (called a "signature") is a collection of declarations of type families and constants that inhabit those type families. For example, the following is the standard definition of the natural numbers, with z standing for zero and s the successor operator.

nat : type. z : nat. s : nat -> nat.

Here nat is a type, and z and s are constant terms. As a dependently-typed system, types can be indexed by terms, which allows the definition of more interesting type families (relations). Here is a definition of addition:

plus : nat -> nat -> nat -> type. plus_zero : {M:nat} plus M z M. plus_succ : {M:nat} {N:nat} {P:nat} plus M (s N) (s P) <- plus M N P.

The type family plus is read as a relation between three natural numbers M, N and P, such that M + N = P. We then give the constants that define the relation: plus_zero indicates that any natural number M plus zero is still M. The quantifier {M:nat} can be read as "for all M of type nat".

The constant plus_succ defines the case for when the second argument is the successor of some other number N (see pattern matching). The result is the successor of P, where P is the sum of M and N. This recursive call is made via the subgoal plus M N P, introduced with <-. The arrow can be understood operationally as Prolog's :-, or as logical implication ("if M + N = P, then M + (s N) = (s P)"), or most faithfully to the type theory, as the type of the constant plus_succ ("when given a term of type plus M N P, return a term of type plus M (s N) (s P)").

Twelf features type reconstruction and supports implicit parameters, so in practice one usually does not need to explicitly write {M:nat} (etc.) above.

These simple examples do not display LF's higher-order features, nor any of its theorem checking capabilities. See the Twelf distribution for its included examples.

Uses

Twelf is used in several different ways.

Logic programming

Twelf signatures can be executed via a search procedure, so Twelf can be used as a logic programming language. Its core is more sophisticated than Prolog, since it is higher-order and dependently typed, but it is restricted to pure operators: there is no cut or other extralogical operators (such as ones for performing I/O) as are often found in Prolog implementations, which may make it less well-suited for practical logic programming applications. Some of the use of cut rule as used in Prolog is obtained through the ability to declare that certain operators belong to deterministic type families, which avoids recalculation.

Formalizing mathematics

Twelf's main use today is as a system for formalizing mathematics (especially the metatheory of programming languages). Used this way it is closely related to Coq and Isabelle/HOL/HOL Light. However, unlike those systems, Twelf proofs are typically developed by hand. Despite this, for the problem domains at which it excels, Twelf proofs are often shorter and easier to develop than in the automated, general-purpose systems.

Twelf is particularly well suited to the encoding of programming languages and logics, because it has a built-in notion of binding and substitution. Most logics and programming languages of interest make use of binding and substitution. When implemented in Twelf, binders can often be directly encoded using the technique of higher-order abstract syntax (HOAS), in which the meta-language (Twelf) binders are used to represent the object-level binders. As a consequence, standard theorems such as type-preserving substitution and alpha conversion come "for free".

Twelf has been used to formalize many different logics and programming languages (examples are included with the distribution). Among the larger projects are a proof of safety for the Standard ML programming language, [cite conference
first = Daniel
last = Lee
coauthors = Karl Crary, Robert Harper
title = Towards a Mechanized Metatheory of Standard ML
booktitle = Proceedings of the 2007 Symposium on the Principles of Programming Languages
date = January 2007
location = Nice, France
url = http://www.cs.cmu.edu/~dklee/papers/tslf-popl.pdf
accessdate = 2007-02-08
format=PDF] a foundational typed assembly language system from CMU, [cite conference
first = Karl
last = Crary
title = Toward a Foundational Typed Assembly Language
booktitle = Proceedings of the 2003 Symposium on the Principles of Programming Languages
year = 2003
accessdate = 2007-02-08
url = http://www.cs.cmu.edu/~crary/papers/2003/talt/talt.pdf] and a foundational proof carrying code system from Princeton.

Implementation

Twelf is written in Standard ML and binaries are available for Linux and Microsoft Windows. It is under active development (mostly at Carnegie Mellon University) as of 2006.

It is unclear under what conditions the software can be legally used.The nsis section's license text (in nsis/LICENSE) says "This software is protected by copyright and international treaties. Unauthorized reproduction or distribution of this software, or any portion of it, may result in severe civil and criminal penalties, and will be prosecuted to the maximum extent possible under law." Technically, this would mean that the software cannot be legally used, since copyright forbids copying unless the right is granted and this license grants no such rights. Yet presumably the authors wish for people to copy and use it, since they distribute it on the web. [ftp://ftp.netbsd.org/pub/NetBSD/packages/pkgsrc/lang/twelf/README.html] [http://www.freebsd.org/copyright/LEGAL]

References

External links

* [http://twelf.plparty.org/ Twelf Project wiki]