Twelf

Key takeaways

Twelf belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Twelf to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Twelf from memory before moving on to harder problems.

Reference excerpt

Twelf is an implementation of the logical framework LF developed by Frank Pfenning and Carsten Schürmann at Carnegie Mellon University. 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 (relations) 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.

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. Here is a definition of addition:

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: the constant plus_zero indicates that M + 0 = 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

Logic programming Twelf signatures can be executed via a search procedure. 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 uses of Prolog's cut rule can be obtained by declaring that certain operators belong to deterministic type families, which avoids recalculation. Also, like λProlog, Twelf generalizes Horn clauses to hereditary Harrop formulas, which allow for logically well-founded operational notions of fresh-name generation and scoped extension of the clause database.

Formalizing mathematics Twelf is mainly used today as a system for formalizing mathematics, especially the metatheory of programming languages. As such, it is closely related to Rocq 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's built-in notion of binding and substitution facilitates the encoding of programming languages and logics, most of which make use of binding and substitution, which can often be directly encoded through higher-order abstract syntax (HOAS), where the meta-language's binders represent the object-level binders. Thus 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 Standard ML, a foundational typed assembly language system from CMU, and a foundational proof carrying code system from Princeton.

Implementation Twelf is written in Standard ML, and binaries are available for Linux and Windows. As of August 2026, it is no longer undergoing active development. The Twelf wiki, however, is still maintained.

System for Totality in the Edinburgh Logical Framework (STELF) The System for Totality in the Edinburgh Logical Framework (STELF) is a version of Twelf rewritten in OCaml, with a new syntax. It is currently undergoing development, on Github. The above code would be written as

And also

Note that the each %. in the above is only required in the above if it is entered at the REPL (in which case it must be entered to signal the end of the command).

Worked examples

Example 1 — a first encounter with Twelf

Start with the simplest possible case. Write down what Twelf claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Twelf before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Twelf ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Twelf

In research: Twelf appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Twelf in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Twelf is common in secondary-school and first-year university syllabi. It links to neighbouring topics Dependently typed languages, Logic in computer science, Logic programming languages, so understanding it makes those chapters shorter.
In everyday life: Look for Twelf outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Twelf in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Twelf means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Twelf out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Twelf in simple terms?

Twelf is an implementation of the logical framework LF developed by Frank Pfenning and Carsten Schürmann at Carnegie Mellon University. It is used for logic programming and for the formalization of programming language theory.

Why does Twelf matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Twelf?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Twelf.