The programming language TransLucid

Abstract

This thesis presents TransLucid, a low-level, purely declarative, intensional programming language. Built on a simple algebra and with just a small number of primitives, TransLucid programs define arbitrary dimensional infinite data structures, which are then queried to produce results. The formal foundations of TransLucid come from the work in intensional logic by Montague and Scott.

The background chapters give a history of intensional logic and its predecessors in the Western world, as well as a history of intensional programming and Lucid, the first intensional programming language.

The semantics of TransLucid are fully specified in the form of operational semantics. Three levels of semantics are given, in increasing order of efficiency, with the sequential warehouse semantics, the most efficient, being presented together with a proof that any expression will be evaluated by only examining relevant dimensions in the current context. The language is then extended in three important ways, by adding versioned identifiers, (declarative) side-effects and timestamped equations and demands.

Adding versioned identifiers to TransLucid enriches the expressiveness of the language and allows the encoding of a variety of programming paradigms, ranging from manipulating large data-cubes to pattern-matching.

Adding side-effects supports one of the main reasons for TransLucid: namely, to provide a target language, together with a methodology, for translating the main programming paradigms, thus creating a uniform end platform that can be the focus for optimisation and program verification. A translation of imperative programs into TransLucid is given.

Timestamped equations and demands enable TransLucid to become a language for synchronous programming in real-time systems, as well as allowing runtime updates to a program's equations.

The language TransLucid represents a decisive advance in declarative programming. It has applications in many fields of computer science and opens up exciting new avenues of research.