Pi (π)

π - the Greek letter, pronounced “pi” and subtitled “a pattern language” - is a research programming language designed by Roman Knöll with Mira Mezini at the Software Technology Group of the Technische Universität Darmstadt and published at OOPSLA 2009. It has exactly one language construct. A pattern is a piece of syntax written like the right-hand side of an EBNF rule, whose non-terminals are the pattern’s parameters, together with a meaning written in terms of already existing patterns. Declaring a pattern extends the language on the spot: the new symbol can be used in the very next instruction anywhere a symbol of its type is allowed, and it is indistinguishable from the built-in ones - because the built-in ones (the “core pattern set”, including the pattern-declaration instruction itself) are patterns too. The authors’ claim was that variables, operators, control structures, functions, macros, libraries, domain-specific languages and even whole programming languages are all the same thing seen at different scales, and that a language dedicated to that single idea would be a natural tool for designing other languages.

π should not be confused with the π-calculus, with the Brainfuck-derived esoteric language also named “Pi”, or with the unrelated compiled “Pi” language of the 2020s. It is not the programming language of the Raspberry Pi either.

History and Origins

Out of Pegasus

The Software Technology Group at TU Darmstadt, led by Mira Mezini, spent the second half of the 2000s on naturalistic programming: writing programs in something close to English or German. Knöll and Mezini’s paper “Pegasus: first steps toward a naturalistic programming language” appeared in the OOPSLA 2006 companion, and the Pegasus project’s website still describes it as “the first both theoretically grounded and practically usable natural-language programming system”, able to generate Java and VRML and to drive a robot from German or English text. Alongside Pegasus the group designed pegasus_f, a “naturalistic” language with a fixed formal syntax that borrowed natural-language devices such as anaphoric references (“the folders”, “it”, “them”), coordination (“enter (it), take (the folders) and leave”) and vague quantifiers (“several folders”).

Two observations from that work led to π, as the site’s “who?” page explains. First, written natural language - and mathematics, and formal logic - constantly introduces new notation for old ideas, so a naturalistic language needed a way to define new syntax from inside itself; the group added a pattern-definition feature to pegasus_f. Second, the tools they were using to build experimental languages were “unsatisfactory”: every new construct meant reshaping a grammar to suit a particular parser generator, writing helper code to dissect the parse tree and then attaching semantics to its nodes, a process the paper calls “very tedious and error-prone”. “Eventually,” the page says, “we found the idea of patterns as such so attractive that we decided to design a completely new language which would be based only on the paradigm of patterns, namely π.”

Building the interpreter (2008-2009)

The interpreter was written in Java 6. The oldest sources bundled in the released jar - the classes that implement parameterised symbols for the pattern-declaration construct - are dated 4 October 2008, and most of the code was compiled on 30 March 2009. The parser was the hard part, and it was written by Felix Wolff as a separate library: an ANTLR-generated reader for EBNF grammars plus an Earley chart parser over grammars in the “nihilist normal form” of Aycock and Horspool’s 2002 paper “Practical Earley Parsing”, which Marc Wagner of Saarland University had suggested to the team. The paper notes that chart parsers had been “used since the 70s almost exclusively in computational linguistics but not in programming”; for a language whose grammar changes with every declaration they had three decisive advantages - the grammar can be updated cheaply, any context-free syntax is accepted (no LL or LR restrictions to contort a pattern’s syntax around), and all readings of an ambiguous input are returned so that a later dispatch stage can choose among them.

Onward! 2009 and after

“π - a Pattern Language” was accepted for Onward!, the “new ideas, new paradigms” track that was held as part of OOPSLA until 2009 (from 2010 both moved under the SPLASH umbrella), and was presented at OOPSLA 2009 in Orlando, Florida; the website dates the talk 27 October 2009 and adds that “the feedback is really encouraging for us”. The paper was published in the OOPSLA proceedings (ACM SIGPLAN Notices 44(10)); the author’s version and the slides (as PDF and as a QuickTime movie, the latter “recommended”) went up on pi-programming.org, a small six-page iWeb site - “what?”, “why?”, “demo!”, “get!”, “how?”, “who?” - whose text is largely lifted from the paper. Its “what?” page lists the language’s chosen relatives: the book A Pattern Language by Christopher Alexander, and the film Pi by Darren Aronofsky.

The jar was uploaded on 30 October 2009. On 22 January 2010 the site announced version 0.8, saying that “several of the remaining problems described in the article have been solved now” and asking for feedback “of any kind”; the “get!” page, however, still called π “currently in an alpha stage”, admitted that “some users have reported problems starting the π-console”, and listed the restrictions of 0.8: to work with a new interpreter core the “extended Earley parser” had been replaced by a standard and “a lot slower” one, and reflection-completeness was not yet fully realised. The site’s pages were last edited on 2 July 2011 and carry a 2011 copyright. Knöll’s next Onward! paper, “Naturalistic types” with Vaidas Gasiunas and Mezini (Portland, October 2011), returned to the Pegasus side of the research, and π has not been heard from since.

Design Philosophy

The paper opens with semiotics: a symbol, the thought it evokes and the thing it refers to form the classical “semiotic triangle”, and programming, the authors say, is nothing but “communicating behavior from a sending system to a receiving system” by exchanging symbols. Parameterising a symbol - print( … ) with a hole for a string, or Σ with holes for bounds and a summand - gives a generic symbol; a parameterised symbol with a meaning is a pattern. “Every programming language has and uses patterns,” the slides say, “but only a pattern language could create new patterns.”

From this the paper derives six criteria that a pattern language should meet:

1. Full syntactic extensibility - arbitrary new context-free syntax can be defined, so that the language has “some facility of the form syntax ➞ meaning”.
2. Syntactic homogeneity - new syntax is seamless; the paper borrows Brabrand and Schwartzbach’s description of the ideal macro language, in which new constructs “appear to the programmer as if they were part of the original language”.
3. Full semantic grounding - every symbol’s meaning is definable, non-circularly, by other symbols of the language on top of a minimal predefined core.
4. Reflection completeness - every entity of the language and of the interpreter is referenceable from inside the language.
5. Meta-completeness - the language that talks about the language is the same language, with no cascade of meta-levels (“for instance, LISP is meta-complete”); this includes syntactic grounding, every part of the grammar being expressible as syntax patterns.
6. Full semantic extensibility - “fulfilled by nearly all programming languages”, listed for completeness.

The intellectual patrons are named on every page. Christopher Alexander supplies the word “pattern” and the epigraph “It is good to design a thing, but it can be far better (and far harder) to design a pattern”. Guy Steele’s 1998 OOPSLA keynote “Growing a Language” supplies the goal - “a main goal in designing a language should be to plan for growth” - and its observation that in Lisp “new words defined by the user look like primitives and … all primitives look like words defined by the user”. π is described as “post-paradigmatic”: it favours no paradigm except pattern-oriented programming itself, and its authors saw “functional” meanings (an expression) and “imperative” meanings (a block with side effects) as “two sides of the same coin”.

The closing “plea” of the paper is unusually candid about being a manifesto. It argues for “a renaissance of the origins” of language design, for “the importance of syntax”, against “meta-ization” and “tool-erism” (fixing languages with ever more external tools instead of designing better languages), and for what the slides call the “democratization” of language design - the paper’s hope that with a pattern language “language design becomes a community-process” in which syntax “is exposed to evolutionary mechanisms”, and that programmers would “stop copy & paste or using IDE-source-templates. Instead, start with an example, parameterize it and give it a unique syntax and name.”

Key Features

The pattern-declaration instruction

A pattern has a syntax, an optional name, a type and a meaning. The full form of the declaration instruction, in the Unicode notation the language uses throughout, is

1

declare_pattern name ≔ syntax ⇒ type ➞ meaning ;

The paper’s first complete program declares two patterns and uses them immediately (> and ? : are predefined; %W- forbids whitespace at that point in the syntax):

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

declare_pattern maximum ≔
   "max" "(" integer:a "," integer:b ")"
   ⇒ integer ➞ ( a > b ) ? a : b;

print( max (13^2, 101) );

declare_pattern absolute_value ≔
   "|" integer:i "|" ⇒ integer ➞
   ( i ≥ 0 ) ? i : -i;

if ( max (13^2, |-171|) > 169 )
   print ("yes!");

Exponentiation itself is not built in; the paper defines it, in the “imperative” style, from the core integer patterns:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

declare_pattern
   integer_potentiation ≔
   integer:i %W- "^" %W- integer:j
   ⇒ integer ➞
   {
      int result = i;
      for (int k = 1; k <= j-1; k++)
         result *= i;
      return result;
   };

The pattern-declaration instruction is a pattern like any other. Its syntax is "declare_pattern" pattern ";", and the pattern pattern is name "≔" syntax "⇒" type "➞" meaning; the paper says “it is not an exaggeration to say that the whole concept of π is based on two patterns”, these two.

π-EBNF: syntax as data

There is “no fixed syntax in π at all” - the language has no grammar, each pattern has one. A pattern’s syntax is written in π-EBNF, which is itself defined by syntax patterns in the core: constants in quotes, slots naming another pattern, sequences, [ ] optionals, | alternatives, { } zero-or-more and ⁅ ⁆ one-or-more repetitions and bracketed groups, each optionally labelled with :name so the meaning can refer to it. The lexer is folded into the parser and merely classifies characters (letters, digits, whitespace), so even integer and float literals are ordinary patterns and keywords cannot clash with identifiers. Whitespace is controlled with codes such as %W- (none) and %S_ (a medium space), and because π was meant to be edited in formatted text, the syntax language also has %I (italic), %U (underline) and %SUPER (superscript) - so that a pattern could really be written f(x) = x² + sin x rather than x^2 + sin(x).

Meanings, references and evaluation

Parameters are referenced by their label (following[k].i reaches into the k-th repetition of a multi-slot), by their type when unambiguous (“implicit referencing”: "twice" "(" integer ")" ➞ 2 * integer), or through the sub-symbols of a parameter (“pass-through referencing”, such as i.first_digit). The core present(...) and size_of(...) patterns test optional and repeated slots. Patterns may be recursive in two ways: semantic recursion (the meaning uses the pattern’s own symbol) and syntactic recursion (the syntax mentions the pattern itself, as in a nested array pattern).

Evaluation is not strict. A parameter referenced without evaluate(...) is evaluated implicitly on first use and its result cached (call-by-need); evaluate(reference) forces it explicitly (call-by-name). That is what allows control structures to be user-defined - the paper’s unless pattern is simply "unless" "(" expression ")" instruction ⇒ instruction ➞ if (!expression) evaluate(instruction). Every symbol is rewritten to a resulting symbol (patterns without a result yield the null symbol ␢), and results are inserted into the slots of enclosing symbols; the paper describes the whole language as “a pure symbol manipulation mechanism”.

Types and dispatch

Every pattern has an explicit type, which is also a pattern (integer_sum ≔ integer "+" integer ⇒ integer), and types are arranged in an ontology under symbol - instruction for things with side effects and control flow, expression for things that compute a result, with user-declared subtypes such as control_structure ⇒ instruction, loop ⇒ control_structure or sql_instruction ⇒ instruction. Typing is dynamic: the interpreter parses each result against the declared type and throws a type error on failure. When an input parses in several ways, partially homonymous patterns (same syntax, different slot types) are resolved by comparing slot types pairwise “as if in a lattice” - symmetric multi-dispatch - and the input is rejected as ambiguous if no reading is more specific in every slot; parse trees that differ in any other way are rejected outright as “an indication for poor pattern-design”. Higher-order patterns (patterns taking patterns) are allowed; the declaration instruction is one.

The core pattern set

The predefined “CPS” is explicitly “a proposal and an outline” rather than a fixed definition - “there is not the one core pattern set”, and Lisp- or Pascal-style cores could equally be built, the only indispensable pattern being some pattern-declaration pattern. The paper groups the core into declaration meta-patterns, mathematical operators (infix, accepting both * and ·), logical patterns (∧, and, &), symbol-manipulation patterns (string concatenation by + or by juxtaposition; a rewrite pattern that can change even a core pattern’s syntax, e.g. renaming print to write), control-flow patterns (if/else, while), data patterns (integer, float, boolean, character_string), ontological patterns (type is type), I/O (print), “world-knowledge” patterns (current_date), context patterns (references) and reflective interpreter patterns (parse(symbol) returning a parse tree, evaluate, and a user-definable interpret ≔ evaluate(parse(symbol))). The shipped 0.4 jar’s predefined-pattern packages match this list closely: control-flow, data-type, debug (check), environment (variable declaration), identifier, I/O, logical, mathematical (sum, difference, multiplication, division, modulo, comparisons, square root, digit-of-integer, is-natural-number) and structural (block, program, single instruction) patterns, plus “pre-predefined” literal, context, interpreter and pattern-declaration patterns.

Implementation

The interpreter bootstraps its core patterns in dependency order (integer needs digit; integer-sum needs integer), evaluates predefined meanings as Java code and user-defined meanings by interpreting their meaning symbol. The Earley parser is O(n³) in the length of the input in general. The paper lists two restrictions of the 2009 implementation: all references had to start with $, because using bare names made the parser generate “too many possible results” and consume too much memory, and nested pattern declarations were disabled for the same reason. The distributed jar runs as a console (java -classpath "pi.jar" de.tu_darmstadt.informatik.st.pegasus.pi.PiConsole) that reads one instruction per line and accepts status, debug on, debug off and exit; the site’s example session shows print (a^3) answering 27 and if ( (a ≠ 2) ∧ (|b^7| > 121) ) print ("yes!") answering yes!.

Evolution

π’s public history is short and its versions are confusing. The interpreter that can still be downloaded from pi-programming.org was compiled on 30 March 2009 with Ant 1.7.0 and Apple’s JDK 1.6.0_07, targets Java 5 class files, and prints “π-interpreter 0.4” when it starts; it was put on the web server on 30 October 2009, three days after the Onward! talk. The website’s news item of 22 January 2010 announces “π 0.8” and the download page describes 0.8’s limitations, yet the file it links to is the March 2009 build - either the 0.8 archive was never uploaded or it replaced the jar without changing the server’s timestamp, which is unlikely. The 0.8 notes themselves record a step backwards forced by a new interpreter core: the faster “extended” Earley parser had to be disabled.

The paper’s “future work” list reads like a roadmap that was never followed: parser performance and alternative grammar formalisms; integration with existing languages “as a super-language, as a domain specific language for the definition of patterns within these languages or by directly importing source-files of these languages into the (Java-)π-interpreter”; debugging support that could turn parse failures into useful hints; IDEs with formatted-text editing and a corresponding markup file format; and a community platform for sharing patterns, “maybe … organized in an ontological way”. The slides end with the same questions - “static (syntax) analysis? a π-calculus? IDE integration? pattern sharing community?” - and none was answered publicly. After the site’s last edit in July 2011 the group’s published work moved on to naturalistic types and to the Pegasus system, whose own news list runs to December 2018 (“Final project reorganization ongoing”) without mentioning π again.

Current Relevance

π is dormant. There is no repository, no package, no mailing list and no known user outside its authors; the only artefacts are the paper, the slides, the six-page website and an 837 KB jar that has been unchanged since 2009. The jar is self-documenting to an unusual degree - it bundles all 111 of its own .java sources, about 7,150 lines, together with Felix Wolff’s grammar and Earley-parser library and the Pegasus “mental_model” classes - so anyone curious can read exactly how the bootstrapping, dispatch and reflection patterns were built. Whether it still runs on a modern JVM is not documented; the class files are Java 5 format, the download page already reported start-up problems in 2010, and this site has not tested it.

Its ideas, on the other hand, are alive in a small but persistent research lineage. Christian Heinlein’s MOST-flexiPL (Onward! 2012) is the clearest heir: it acknowledges that “an approach whose basic ideas and objectives are almost identical to that of flexiPL is ‘π - a Pattern Language’”, that a flexiPL operator “directly corresponds” to a π pattern, and that both draw “the same virtually unlimited syntactic flexibility … from the lack of any predefined grammar” - while claiming static typing as the decisive advantage over “completely dynamically typed” π. More broadly, the questions π posed - can syntax be a first-class, user-definable, run-time value; can a general parser (Earley, GLL, GLR, PEG) make grammar extension cheap enough to be an ordinary programming operation - are the questions behind language workbenches and “syntax-extensible” languages of the 2010s, even where π itself is not cited.

Why It Matters

π is worth knowing for the purity of its experiment. Extensible-syntax languages before and since have almost always kept a host grammar and let users add to it: Lisp macros extend a fixed s-expression syntax, Katahdin and XMF extend object-oriented languages, the Java Syntactic Extender extends Java. π asked what a language looks like when there is no host grammar - when the parser’s rule set is simply the set of currently active patterns and “language” is just another name for “the core pattern set”. Its answer exposed the costs honestly: a cubic-time chart parser, ambiguity that must be dispatched or rejected, references that had to be prefixed with $ to keep the parser tractable, the loss of any static semantics once declarations can be conditional, and a whole new discipline of “good π” style to get some of it back. Those trade-offs are exactly what later designers such as Heinlein set out to improve on, and they are stated more clearly in π’s paper than almost anywhere else.

It also records a moment in the history of ideas. The 2009 paper sits at the crossing of three currents - Alexander’s patterns, Steele’s “growing a language”, and the DSL and language-workbench movement of the 2000s - and treats them, unusually, as one problem: abstraction, “recognizing a repeating pattern, naming it, declaring a symbol for it and making it context-dependent by parameterization”. Whether or not one believes a single mechanism can unify variables, loops, functions, macros and languages, π was the first serious attempt to build a language around that belief, and its authors said so: “π is the first implementation of a pattern language.”

Further Reading

• Website: pi-programming.org - the “what?”, “why?”, “demo!”, “get!”, “how?” and “who?” pages (last modified 2 July 2011); the download page links pi.jar and the CC BY-NC-SA 3.0 licence
• Roman Knöll and Mira Mezini, “π - a Pattern Language”, Proceedings of the 24th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA/Onward! 2009, Orlando), ACM SIGPLAN Notices 44(10), DOI 10.1145/1640089.1640128; author’s version at pi-programming.org/docs/π_a_pattern_language.pdf
• The Onward! 2009 slide deck, pi-programming.org/docs/π.pdf
• Roman Knöll and Mira Mezini, “Pegasus: first steps toward a naturalistic programming language”, OOPSLA 2006 Companion, DOI 10.1145/1176617.1176628; the Pegasus project site at pegasus-project.org
• Roman Knöll, Vaidas Gasiunas and Mira Mezini, “Naturalistic types”, Onward! 2011, DOI 10.1145/2048237.2048243
• Christian Heinlein, “MOST-flexiPL: modular, statically typed, flexibly extensible programming language”, Onward! 2012, DOI 10.1145/2384592.2384608; author’s PDF - the related-work section discusses π
• John Aycock and R. Nigel Horspool, “Practical Earley Parsing”, The Computer Journal 45(6), 2002 - the parsing algorithm behind the π interpreter
• Guy L. Steele Jr., “Growing a Language”, OOPSLA 1998 keynote - the source of the paper’s epigraphs
• Chris Seaton, “Katahdin” (2007) and Clark, Sammut and Willans, “XMF” - the languages the paper calls π’s closest relatives