Ursala

Ursala is what a functional language looks like when one person designs it alone, for himself, for eleven years, with nobody to answer to. It is variable-free, essentially untyped, aggressively terse, hosted on a virtual machine whose entire universe consists of an element called nil and ordered pairs of things, and documented in a 486-page manual written by the same hand that wrote the compiler. Its author’s summary of it, in the README he wrote in 2012, is hard to improve on: the project is “essentially an investigation of some off-beat ideas about functional programming”, and the language is “probably best suited to individual projects because it enforces no particular coding standards or practices and makes unreadable code easier to write than most non-esoteric languages.”

That last clause is not false modesty. Here is the whole of an n-queens solver from the distribution’s contrib/ directory:

queens =

%np+~command.options.&h.keyword.&iNC; -+
   ~&iNC+ file$[contents: --<''>+ %nLP*=]+ ~&rSSs+ nleq-<&l*rFlhthPXPSPS,
   ~&i&& ~&lNrNCXX; ~&rr->rl ^/~&l ~&lrrhrSiF4E?/~&rrlPlCrtPX @r ^|/~& ^|T\~& -+
      -<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS,
      ^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-,
   ^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-

None of that is line noise. Every character does something specific and is documented somewhere in the manual. But it is a fair warning about what kind of language this is.

The catalogue entry needs two corrections

Most listings date Ursala to 2008. The release is 2007: the ChangeLog’s first entry reads “ursala 0.1.0: initial version” and is dated 23 September 2007. What happened in 2008 is that the language became visible - the home page appeared, version 0.2.0 shipped on 24 January, and in April Furey gave a talk about it at a hackers’ meeting in London.

The deeper correction is that neither date is when the language began. The author’s own home page opens: “It began in 1996 as a personal tool kit to assist its author at certain practical problems in CAD applications and mathematical finance, but it is now mature enough and adequately documented for general distribution.” By the time it had a name, the thing was eleven years old.

The name arrived only because releasing it required one. From the manual’s Nomenclature section:

Since its earliest prototypes, the name of the compiler has been fun, and this name is retained because of its brevity and the ease typing it on a command line. However, the transformation from personal tool kit to a community project necessitates a more recognizable and searchable name in the interest of visibility. The name of Ursala has been chosen for the language as of this release, which is meant as a quasi-abbreviation for “universal applicative language”.

So Ursala is the language, fun is the compiler, and fun is the older name of the two. To this day the file extension is .fun.

Origins: a thesis, then a machine, then a language

The chronology runs backwards from what you would expect. The virtual machine came first, and behind it a doctoral thesis.

Furey submitted “A functional approach to asynchronous circuit design and verification” to the University of London in 1994; it was published in 1995. In July 2001 he wrote a four-line HISTORY file for the virtual machine naming that thesis as the prior art behind it. The circuit-design provenance never quite washed out of the language - the very first worked example in the manual is minimising a finite state transducer, “a type of problem that occurs frequently in CAD applications”.

The machine itself, avram - a quasi-acronym for applicative virtual machine - has a ChangeLog entry dated 23 November 2000 reading simply “avram: initial version”, signed from his South Bank University address. It went onto SourceForge on 10 April 2001, where release 0.1.0 was uploaded that April and May. Nothing else was ever uploaded there; later releases came from his own site, and the SourceForge page has sat frozen at 0.1.0 for twenty-five years.

His explanation for building it, from the avram home page, is the most concise statement of the whole project’s motivation:

The reason for writing Avram was that I wanted to do some work using a functional programming language, didn’t like any functional programming languages that already existed, and felt that it would be less trouble to write a virtual machine emulator than the back end of a compiler.

What made the language releasable was the machine growing arms. Through 2006, avram 0.3.0 and 0.4.0 added interfaces to mpfr, UMFPACK, FFTW and minpack, and by 2010 the list ran to GSL, LAPACK, Rmath, GLPK, lpsolve, KINSOL and harminv. Once a dozen high-quality numerical libraries were callable behind a single convention, the terse little language sitting on top of them had a genuine selling point, and in September 2007 it got a name and a tarball.

The machine underneath

Ursala is unusual in that its manual expects you to understand its target. The abstract says the language “is based on a firm semantic foundation derived from a well documented virtual machine model visible to the programmer”, and argues that a concrete virtual machine “promotes segregation of procedural considerations within a primarily declarative formalism.”

The avram specification defines its semantic domain not by construction but by the properties it needs. There is a distinguished element; there is a binary operator that maps pairs of elements to a unique element and never yields the distinguished element; and the set has no proper subset with those properties. Call the distinguished element nil and the operator cons, and you have recovered the S-expression universe from first principles - as the document itself notes, “Lisp users and functional programmers may recognize familiar concepts of atoms and lists in this description”, while pointedly avoiding those words so that readers do not import assumptions.

Programs live in the same domain as data. From the avram FAQ:

Other virtual machines are (to my knowledge) based on the traditional von Neumann model of a central processor with registers, an instruction set, and a writable memory… By contrast, avram has none of these characteristics. A program is described by a tree-like structure specifying a transformation from inputs to outputs, which is the computation itself.

The specification writes its semantics in an auxiliary notation it calls silly, “a simple Lisp like language”, and then confronts the fact that silly has no variables. Its answer is an algorithm called isolate that takes an expression containing an identifier and mechanically returns an equivalent expression that does not - the bracket abstraction familiar from combinatory logic, applied here as an engineering convenience so that the rest of the document can use variables in its explanations while the machine never does. Variable freedom is not a slogan bolted onto Ursala; it is the level at which the machine actually operates.

Design philosophy

Furey set out four themes on the old site, hedging the first line: “Philosophy may be too strong of a word. The language was developed from a clean slate with no time constraints and no ideological axe to grind, very much in the tradition of an exploratory spare time project or hack.”

Brevity

Most of the language’s density comes from pointer expressions - case sensitive strings of letters and digits attached as suffixes to operators, each denoting a projection, a fan, a distribution, a fold or a reduction over the structure of the argument. The manual introduces them by saying flatly that the mechanism “has no counterpart in other modern languages”, and devotes an entire chapter to them before the reader has met a single operator.

Two prefixes carry a disproportionate share of the work: & evaluates to a pointer (the identity pointer with no suffix, and whatever the suffix describes otherwise), and ~ turns a pointer into the function it induces. Hence the ~& that studs every Ursala program. The distinction between a pointer and the function it induces is deliberate and is reflected in the virtual code, because pointers can be transformed in ways functions cannot.

The productivity claim attached to all this is the author’s own and is offered as an estimate, not a measurement: “By a conservative estimate, you’ll write about one tenth the number of lines of code in this language as in C or Java to get the same job done.” He follows it with a footnote: “I’m a big fan of C, as all real programmers are, but I still wouldn’t want to use it for anything too complicated.”

Interoperability

Two layers of it. Through the virtual machine, the numerical libraries listed above are callable with no source-level memory management, so the result of a LAPACK call can go straight into a GSL call. Through the expect library, any program with a command line interface - locally or over ssh - can be launched and driven from a function call, with the character-by-character transcript returned as data. Interfaces shipped for Octave, R, Scilab, Axiom, Maxima, PARI/GP, GAP, bash and the Perl shell psh, and users could define new ones without rebuilding the compiler. The site makes a sharp point about what this implies: because only the user-level documentation of the target tool is needed - not its source, API or library - the technique works on proprietary applications too.

Extensibility

Any user-defined function can be invoked at compile time to transform data or source code, which the site describes as “a computationally universal generalization of the concept of a macro preprocessor”. Separately compiled libraries let new functions effectively become part of the language, and any standard library function may be redefined or renamed. Below even that, the compiler’s semantics, grammar rules and algebraic optimising transformations live in declarative tables that a user can override with dynamically loaded replacements. The last resort is to edit the compiler, which is itself written in Ursala under GPLv3.

Testability

Furey took seriously the awkwardness of debugging a language with no print statements and no variables to inspect, and the answers he arrived at are among the language’s more transferable ideas. Type expressions can be inserted at strategic points as annotations, and their semantics tuned: halt immediately and display the argument the first time control reaches this point; display the last argument before a crash, but only if it crashes; produce a “stack dump” of arguments for a recursive function; display the first successful result; display only the values that fail to match the type. Because type expressions are compact, all of this can be done without disturbing the shape of the code.

The complement is test data. Given any type expression, Ursala will generate random instances of it, at any size, on demand - which turns the difficulty of hand-constructing test cases for complicated data structures from a blocker into a non-issue.

What the code looks like

Output as a side effect of compilation, and output from a compiled executable:

#show+

main = -[Hello world!]-

#import std

#executable ('parameterized','')

main = <file[contents: -[Hello world!]-]>!

Directives beginning with # control the compiler: what to import, whether to emit an executable shell script or a binary, what to display. The -[ ]- brackets delimit literal text, and can interpolate expressions - which is how the 99-bottles program in contrib/ builds its verses:

quantity = # forms the plural as needed

~&iNC+ --' of beer'+ ~&?(
   1?=/'1 bottle'! --' bottles'+ ~&h+ %nP,
   'no more bottles'!)

verse =

^(successor,~&); ("s","n"). -[
   -[quantity "s"]- on the wall, -[quantity "s"]-,
   Take one down and pass it around, -[quantity "n"]- on the wall.]-

The FAQ’s answer to “What does it look like?” is: “Like nothing you’ve ever seen.” It is not wrong.

Types and numbers

The type system is optional but elaborate. Primitive types include unlimited precision naturals, unlimited precision rationals, IEEE double precision floating point, IEEE complex, and - when mpfr is present - arbitrary precision floating point; signed integers arrived in 0.5.0 and binary coded decimals in 0.7.0. Exact naturals and rationals are implemented by libraries written in Ursala itself; doubles and complexes go through the host C library.

The precision rule for arbitrary precision arithmetic is characteristic of the language’s willingness to trust the user. The product of two mpfr numbers is allocated the greater precision of the two operands, so that library functions with hard-coded constants interoperate with numbers of any precision without run-time checks. The FAQ states the consequence without apology: “It is incumbent on the user to know how many digits are physically reliable.”

Above the primitives sit lists, sets, trees, balance-invariant trees, and the lattice containers written for derivatives valuation. Record types support named fields, generic and opaque fields, self-describing fields, parameterised “higher order” declarations, and self-initialising smart records; type expressions themselves are first-class values.

Approximately thirteen libraries shipped with the compiler, containing on the order of 250 functions - statistics, numerical calculus, combinatorics, LaTeX-compatible 2D and 3D plotting, date and time, linear programming, lattice traversal, tabular output, interpolation and curve fitting, and linear algebra.

Release history

The 2012 revival that didn’t happen

The clearest window into the end of the project is the ursala-users archive, whose month index runs from May 2010 to August 2012 and then stops. The last thread is titled “Dennis, are you there?”, started by Terrence Brannon. Furey replied.

Days later, on 29 August 2012, he rewrote the README:

Ursala is mainly an individual effort that has been around for some years but neglected lately due to my day job. I’m now looking to revive it and address some issues, such as improving the web presence and on-line documentation.

For three months something happened. He updated URLs, fixed stray commas, corrected the grid type example, rebuilt the manual PDF, moved the download pointers from basis.uklinux.net to GitHub - and, on 8 October, commented out “Institute for Computing Research, London South Bank University” from the manual’s title page, leaving only a mailing list address. On 1 September he had shipped avram 0.13.0 with the beginnings of distributed evaluation, marked “currently client side only”. On 6 January 2013 he committed “simplified the readme file” to avram, and that was the last commit either project received from its author.

The infrastructure has since gone, not merely gone quiet. basis.uklinux.net does not resolve. Furey’s GitHub account holds neither project any more, its public repositories now being C libraries for non-preemptive thread hierarchies and co-recursion. Both trees survive because Terrence Brannon kept copies.

Running Ursala today

There is no Docker image and no package in the major distributions - the Debian packaging the download page appealed for was never finished, and the commented-out dpkg -i lines are still sitting in the manual’s installation section.

Reconstructing a working system means building avram from its C sources with autotools (about 24,000 lines across 49 files) and then dropping the compiler’s precompiled .avm modules where the machine can find them, either under /usr/local/lib/avm or on the AVMINPUTS path. Bootstrapping the compiler from its own source is possible but is a project rather than a step: the script warns to “allow about 11 hours for it to run on a 3 GHz machine”.

Be careful about claiming portability. The manual is explicit that “there is no provision for installation on other operating systems (for example Microsoft Windows)”, though it notes that volunteer efforts and emulation are options. The avram home page as of 2010 said that “previous versions of the package have compiled successfully on Alpha, MIPS, Mac-OS, and OSF systems”, but immediately added that “the current version has been tested only on x86 platforms”. Compiled virtual code, on the other hand, is genuinely portable to any host where the machine is installed and the optional modules the application uses are present.

Why it matters

Ursala is a specimen of a road not much travelled. Furey’s own diagnosis of the functional programming field, in the manual’s section addressed to hackers and hobbyists, is that it “has changed considerably since the lisp era, not necessarily for the better unless one accepts the premise of the compiler writer as policy maker. We are now hard pressed to find current research activity in the field that is not concerned directly or indirectly with type checking and enforcement.” What he offers instead is “a glimpse of how functional programming might have progressed in the absence of this constraint”, and the answer he arrives at is: with far more imaginative and ubiquitous higher-order functions than a static type discipline would permit.

He was also unusually clear-eyed about why nobody would adopt it. The manual opens by conceding the economics: the expensive part of software is maintenance and staffing, “these costs escalate in the case of esoteric software technologies, of which unconventional languages are the prime example, and they ordinarily will take precedence over other considerations.” His answer was not to deny it but to name the four constituencies for whom it does not apply - academics under deadline, hackers, numerical analysts, and consultants maintaining their own code - and to say plainly that there is “no compelling argument for general commercial deployment”, only “a good reason for them to exist.”

That combination - a genuinely original design, a fully documented machine model, a self-hosting compiler, a 486-page manual, and a clear statement of why you probably should not use it - is rare enough that the project is worth knowing about even now that it has stopped. The most useful things to steal from it are not the pointer expressions but the debugging and testing ideas: type-expression annotations whose semantics you can dial between assertion, tracer and post-mortem, and automatic generation of arbitrarily large random test data from a type expression. Those were good answers to real problems, and they were arrived at by someone who had no committee to convince.