Leda

Leda is a multiparadigm programming language designed by Timothy A. Budd at Oregon State University. It aims to let a programmer move between imperative, object-oriented, functional and logic programming inside one program, and even inside one statement, without leaving a single, consistent language. Most languages that mix paradigms start from one style and add pieces of another, as C++ added objects to C. Budd started from scratch and tried to find the smallest set of features from which all four styles could be built. The result reads much like Pascal, with begin/end blocks, := assignment and typed declarations, but it also has classes, generic types, first-class anonymous functions and a built-in relation type that gives Prolog-style backtracking. Leda never left research and teaching, but it is one of the clearest attempts at a “general-purpose” multiparadigm language, and its textbook remains a useful tour of all four paradigms.

History & Origins

Oregon State, 1989

Budd had already written about Smalltalk (A Little Smalltalk, 1987) when he began work on Leda at Oregon State. The earliest dated documents are Oregon State technical reports from 1989: “LEDA: A Blending of Imperative and Relational Programming” (TR 89-60-7), “Low Cost First Class Functions” (TR 89-60-12, June 1989), “Functional Programming in an Object-Oriented Language” and “Data Structures in LEDA”, and a working document titled “The Multi-Paradigm Programming Language LEDA” in September 1989. A May 1995 Oregon State report described Leda as “the product of six years of research in paradigm blending and language implementation”, which also points to about 1989. The encyclopedia catalogue gives 1988, but no source found for this page supports that year, so this page uses 1989.

The name was spelled in capitals, LEDA, at first. According to Rajeev Pandey’s 1998 thesis, it came from early example programs that built a family-tree database of figures from Greek mythology. Leda was the wife of King Tyndareus and the mother of Helen of Troy. Later projects in the group kept the mythological theme. The name was not unique: Pandey notes, among others, LEDA, the Library of Efficient Data types and Algorithms, a well-known C++ library that has nothing to do with Budd’s language.

First public description

On 25 September 1990 Budd joined a comp.compilers discussion about whether one language could cover the imperative, functional, logic and object-oriented paradigms. He argued that the trick was “to avoid using a large pot into which you throw everything anybody would ever like” and instead to “define a SMALL (syntactically and semantically) language in which the pieces of the various paradigms can be fit together naturally”. He wrote that he and his students had developed such a language, LEDA, whose grammar was “approximately the size of the PASCAL grammar”. He also wrote that a paper would soon appear in IEEE Software and that “the compiler is not ready for public display yet”.

The paper, “Blending Imperative and Relational Programming”, appeared in IEEE Software in January 1991. It described how logic programming could be expressed inside an imperative framework. A master’s thesis by Vinoo Cherian (May 1991), “Implementation of First Class Functions and Type Checking for a Multiparadigm Language”, is among the early Leda work cited by Pandey. In April 1992 Budd presented “Multiparadigm Data Structures in Leda” at the International Conference on Computer Languages in Oakland, California.

Implementations and the book

Budd’s distribution directory offered a “first leda compiler”, which it says “has subsequently been replaced by a more recent version”, the interpreter ledainterp. The interpreter’s release notes trace versions 0.1 to 0.7. Along the way they added integer and string operations, arrays, real numbers, the built-in unify function for logic programming (0.3), pattern-matching expressions (0.6) and finally garbage collection (0.7). Release 0.7 is dated 22 February 1994 and is described as “Still very Beta”.

In 1995 Addison-Wesley published Budd’s book Multiparadigm Programming in Leda (ISBN 0-201-82080-3), the complete description of the language. It went out of print, but Budd kept sample chapters online, including the introduction and the formal grammar. On his own book list he wrote: “Of all my books, this one is my favorite, and also the one that has sold the smallest number of copies.”

Design Philosophy

Budd’s group distinguished three kinds of multiparadigm language:

• Augmented languages add a new paradigm to an existing language, as C++ did for C.
• Hybrid languages embed other paradigms in a functional or logic language, usually for AI work.
• General-purpose multiparadigm languages look for an “ideal” blend of the major paradigms to solve general problems.

Leda was meant to be the third kind. Its central goal was to stay concise while combining four paradigms. Pandey’s thesis claims that, although Leda supports two more paradigms than C++, it has “54% fewer keywords and 67% fewer operators” than C++. Budd’s group argued that blending can happen at any scale, “from individual statements to complete modules”, so that a large program can use whichever style suits each subproblem. Their standard example was a compiler: the parser written as logic rules, the symbol table as objects, and transformations on the intermediate form as functions.

Pandey’s thesis quotes Budd’s goal as “to provide a vehicle for experiments in multi-paradigm programming” and to “explore the advantages of using various programming paradigms on assorted problems”. Leda was always presented as a research language that would keep changing.

Key Features

Imperative core

At its base Leda is a statically and strongly typed language. The 2015 README describes its syntax as influenced by ALGOL 60 and similar to Pascal, Simula, Modula, Oberon and Ada. This insertion sort comes from the interpreter’s test suite (chap2a.led):

function sort(byRef aList : intList);
var
	current, p : intList;
	x, temp : integer;
begin
	current := aList;
	while defined(current) do begin
		x := current.value;
		p := aList;
		while p ~= current do begin
			if x < p.value then begin
				temp := p.value;
				p.value := x;
				x := temp;
			end;
			p := p.next;
		end;
		current.value := x;
		current := current.next;
	end;
end;

Comments are written in braces, ~= means “not equal”, ~ is logical negation, and byRef marks a parameter passed by reference. defined(x) tests whether a value is something other than NIL.

Classes and generic types

Leda has classes, subclasses and parameterized types. A type parameter can be constrained to types that support a given set of operations, such as equality or ordered. This set class (from chap7a.led) is generic in its element type T:

class Set [T : equality];
var
	values : List[T];

	function add (newValue : T);
	begin
		if ~ defined(values) then
			values := List[T]();
		if ~ values.includes(newValue) then
			values.add(newValue);
	end;

	function items(byRef val : T)->relation;
	begin
		return defined(values) & values.items(val);
	end;
	...
end;

First-class functions

Functions are values. They can be passed as arguments, stored, and created anonymously with a function expression that captures its surroundings. The book’s chapter on functional programming defines composition and currying like this (chap16.led):

function compose [X, Y, Z : object]
	(f : function(Y)->Z, g : function(X)->Y)->function(X)->Z;
begin
	return function (value : X)->Z;
		begin
			return f(g(value));
		end;
end;

const
	half := curry2 [real, real, real] (real.divide, 2.0);

Relations: logic programming without Prolog

The most unusual part of Leda is the built-in type relation. A function that returns a relation behaves like a Prolog predicate. Its byRef arguments act as logic variables, & and | combine goals as conjunction and disjunction, and unify binds or compares values. The test suite still contains the Greek family database that gave the language its name (child.led):

const
  eq := unify[string];

function child(byRef name, mother, father:string)->relation;
begin
  return eq(name, "helen") & eq(mother, "leda") & eq(father, "zeus")
 | eq(name, "clytemnestra") & eq(mother, "leda") & eq(father, "tyndareus")
 | eq(name, "hermione") & eq(mother, "helen") & eq(father, "menelaus")
 ...
end;

function motherOf(byRef mom, kid:string)->relation;
var
	dad : string;
begin
	return child(kid, mom, dad);
end;

A relation can be tested once with if, which finds the first solution and binds any unbound variables, or enumerated with for, which backtracks through every solution:

x := NIL;
for child(x, "clytemnestra", "agamemnon") do begin
	print(x);
	print(" is the child of clytemnestra and agamemnon\n");
end;

Because the solutions arrive as an ordinary loop, logic queries mix freely with imperative code. The same for form iterates over collections in object-oriented code. For example, for aTree.items(v) do ... walks a tree, because methods such as items are themselves written as relations, as in the Set class above.

Evolution

Leda grew through several implementations at Oregon State, and much of its later history is graduate research built on top of it:

The environment’s name is a play on the language’s. It was first called Sparta, the kingdom of Leda and Tyndareus, until the group noticed that it suggested a “spartan” environment. It was renamed Lacedaemon, another name for Sparta, written LacEDAemon to show the letters of “Leda”.

Budd also used Leda in teaching. In “Never Mind the Paradigm, What About Multiparadigm Languages?” (SIGCSE Bulletin, June 1995), Budd and Pandey argued that instead of choosing the correct paradigm for students, courses should expose them to all the major paradigms through a multiparadigm language. They then discussed where in the curriculum such a language could be introduced.

Current Relevance

Leda is no longer developed, and its last interpreter release notes date from 1994. In 2015 the interpreter sources were imported to GitHub under the MIT License, credited “Copyright (c) 2015 Timothy A. Budd”. The import modernised the lexer to use flex, and according to its README it builds with gcc or clang. The repository includes the language reference manual and test programs keyed to the chapters of the book, so the examples in Multiparadigm Programming in Leda can still be studied today. Budd’s Oregon State pages still describe the language and link to sample chapters of the book.

Why It Matters

Leda is one of the clearest experiments in general-purpose multiparadigm design. It did not build a large language by piling features together. It tried to find a small core from which imperative, object-oriented, functional and logic programming would all fall out. Its relation type showed that Prolog-style backtracking can be offered as an ordinary typed value inside a Pascal-like language, and that the same mechanism can serve as an iterator for collections. Since Leda, mainstream languages have adopted closures, generics and generator-style iteration side by side, which is close to the mixture Budd argued for in 1990. Leda’s lasting contribution is less the language itself than the argument, made in its book and papers, that programmers and students are better served by learning to choose among paradigms than by committing to one.