NU-Prolog

NU-Prolog (pronounced “new Prolog”) is a Prolog system built at the University of Melbourne in the mid-1980s. It tried to make logic programs more declarative. Most Prologs of the time relied on cut, \+ and the -> conditional to control execution, and these constructs can give logically wrong answers if a programmer misuses them. NU-Prolog provided sound alternatives: negation, universal and existential quantifiers, implication, a logical if-then-else, inequality, and when declarations, which make a call wait until its arguments are bound enough. It compiled programs to an abstract machine based on Warren’s design. It also had an external database, a lint-style checker and a tool that added control information automatically. In the 1990s it was one of the two Prolog systems used to bootstrap the Mercury compiler.

History & Origins

From MU-Prolog to NU-Prolog

NU-Prolog’s predecessor was MU-Prolog (Melbourne University Prolog). John Lloyd wrote the short-lived version 1 in Pascal in 1981. Lee Naish then built an entirely new interpreter in C, completing version 2.0 in 1982. MU-Prolog was a structure-sharing interpreter, and its wait declarations were an early way of making calls proceed or delay depending on how instantiated their arguments were. It also delayed negated goals until they were ground, so negation was sound. Naish’s PhD thesis on these ideas was published by Springer in 1986 as Negation and Control in Prolog (LNCS 238).

Naish later wrote that after the invention of the Warren Abstract Machine (WAM) “the time was right to move on”: development of the MU-Prolog interpreter stopped in the mid-1980s, and the group designed a compiled system instead. The reference manual describes NU-Prolog as “the successor of MU-Prolog 3.2”, and a footnote adds that the name “is not an acronym for Naish’s Ultra Prolog”.

The Machine Intelligence Project

NU-Prolog came out of the Machine Intelligence Project in Melbourne’s Department of Computer Science. The manual says the project was set up in 1984 by Barry Jones, then federal Minister for Science, and Jean-Louis Lassez. The Australian Government’s Department of Science and the university funded it, and John Lloyd and Kotagiri Ramamohanarao supervised it.

The credits in the reference manual divide the work as follows:

Peter Van Roy’s 1994 survey of Prolog implementations describes NU-Prolog as “a WAM-based emulator written in C primarily by Jeff Schultz and completed in 1985”. The manual thanks Pyramid Australia for lending a Pyramid 90X during 1985. The source distribution’s copyright notice also gives 1985 as the starting year.

Design Philosophy

The manual’s introduction says what the project was trying to do:

NU-Prolog is intended to be a successor to the current generation of Prolog systems. Programs can be written more logically in NU-Prolog than is possible with other versions of Prolog; NU-Prolog is a step towards purely declarative logic programming.

It says the new constructs “make most uses of cut unnecessary”. The manual separates predicates with a declarative meaning, which it documents both declaratively and operationally, from constructs it labels “(Non-logical)”, such as cut. A programmer can declare a predicate pure, and the nit checker will then complain if that predicate uses any non-logical subgoal.

NU-Prolog also stayed compatible with existing Prolog code. Its syntax and built-ins were “essentially a superset” of DEC-10 Prolog, MU-Prolog and Quintus Prolog, so the manual says “most DEC-10 and Quintus Prolog programs should run with few alterations”. It also kept the ordinary ->, \+ and \=, but recommended its sound equivalents instead.

Key Features

When declarations (coroutining)

A when declaration says when a call to a predicate may run. If the call’s arguments are not bound enough, it is suspended and resumes automatically once other goals bind them. The manual’s own example:

1
2
3
4

?- append(A, B, C) when A or C.
append([], A, A).
append(A.B, C, A.D) :-
    append(B, C, D).

According to the manual, append([X, 2], [3], Y) and append(X, Y, [1, 2, 3]) run immediately, while append(X, [3], Y) “would delay immediately”. (NU-Prolog source of this period often wrote lists with the . constructor, so A.B means [A|B].) A condition can be ever, a variable that must be bound, ground(Var), or a combination of these with and and or.

Van Roy notes that the implementation compiled when declarations into decision trees with several entry points. As a result, a resumed call does not repeat tests it has already passed, and predicates in practice get indexing on more than one argument.

Sound negation, quantifiers and if-then-else

The manual describes not/1 as delaying “until all variables other than Locals are ground”, and only then calls the goal. If a negated call could otherwise give a wrong answer, it waits rather than answer incorrectly. Other declarative constructs include:

Two examples from the manual’s appendix:

1
2
3
4
5
6
7
8
9

% True when Person takes no computer science courses;
% delays until Person is ground.
no_cs(Person) :-
    all Unit not takes(Person, cs, Unit).

% Sets as lists: A is a subset of B.
?- pure subset/2.
subset(A, B) :-
    all E member(E, A) => member(E, B).

solutions/3 behaves like setof/3 with declarative semantics. If no answer exists, it can return an empty set together with a delayed inequality, where setof/3 would simply fail:

1
2
3
4
5

% (assuming P is not implicitly local to the goal)
?- solutions(D, drinks(P, D), S).
S = [beer, milk, tea], P = tim ;
S = [tea, wine], P = joe ;
S = [], P ~= tim, P ~= joe.

A toolchain, not just an interpreter

The reference manual describes five tools:

• nc, the compiler. It translates .nl source to .ns abstract-machine assembler and then to .no object files, and can link these into a standalone executable whose entry predicate is main/1.
• np, the interactive interpreter, used for testing, debugging and database queries.
• nit, a checker the manual describes as “analogous to lint”. It reports arity clashes, undefined or unused predicates, variables used outside their scope, singleton variables, negations whose variables can never be ground, and programs that are not stratified.
• nac, a preprocessor that adds control automatically. It analyses possible infinite recursion in pure predicates and inserts when declarations for them.
• revise, an incremental-recompilation tool that recompiles only the changed blocks of a source file.

Databases

NU-Prolog was designed with database work in mind. Its external database could store predicates on disk under several indexing schemes: static superimposed coding (simc), dynamic superimposed coding (dsimc, the default, which lets a ground-term database keep growing), and compiled rules. An sql scheme gave access to UNIFY relational databases by translating Prolog goals into SQL queries.

Evolution

NU-Prolog developed as a research system over about ten years:

• Version 1.1 (1987). The reference manual, Technical Report 86/10, carries a “Preface to Version 1.1” dated January 1987. FOLDOC cites a Version 1.3 edition of the same report from 1988.
• Version 1.5.x (by 1990). The November 1990 revision of the manual documents 1.5.24. It says releases after 1.5 support 32-bit integers, and that the foreign-function interface “is known to run on Sun-3s, Sun-4s, Encores and VAXes”.
• Version 1.6.x (about 1994-1995). Naish’s web page for the system offered source for 1.6.5 and 1.6.9; the Software Preservation Group dates both to 1994, while the 1.6.9 copyright notice runs to 1995. The 1.6.9 Makefile lists build targets for Sun-3, Sun-4 (SunOS and Solaris 2), Macintosh II, Encore, VAX, i386, Elxsi, MIPS, DECstation, SGI and Alpha. Jeff Schultz’s note in the release says it builds on DEC Alphas running DEC Unix, but warns that “in porting it I may have broken it for some other machines” and suggests users “may have more luck with 1.6.5”. The Makefile list therefore shows the machines the code base had targeted over the years, not ones confirmed to work with 1.6.9.

The project also produced several research systems: a parallel NU-Prolog (Naish, 1988), the NU-Prolog Deductive Database System (1987), the NUDE debugging environment (1989), and an interface to the Aditi deductive database.

NU-Prolog was never free software. The distribution’s copyright notice says it is “made available for teaching and academic research” and “may not be redistributed or used for any other purpose without written permission”. FOLDOC describes it as “available (but not free)”.

Current Relevance

NU-Prolog is no longer developed, and no new release has appeared since the 1.6.9 era. It is mostly remembered for its influence. In September 2021 Lee Yingtong Li, who wanted to run some existing software written in NU-Prolog, ported 1.6.9 to modern Linux as a 32-bit (-m32) build. The port needed a custom linker script to move the program’s load address, and a fixed 128 MiB mmap region at a low address in place of the original brk-based heap, because NU-Prolog needs its data at low memory addresses and its bundled malloc expects a contiguous heap. It also had to replace C library symbols that glibc has since removed. The port is on GitLab as RunasSudo/nu-prolog-linux. No official build exists for current systems, and no Docker image either.

Why It Matters

• Sound negation and quantifiers in a compiled Prolog. MU-Prolog showed that negation could be implemented soundly. NU-Prolog did this in a compiled WAM-based system, and Van Roy cites it for its “pioneering implementation of logical negation, quantifiers, if-then-else, and inequality, through extensions to the WAM”.
• Practical coroutining. When declarations, and the nac tool that generated them, made delayed execution an everyday tool for NU-Prolog programmers rather than a specialist feature.
• Logic programming and databases. NU-Prolog’s external database, SQL interface and deductive-database work led to Melbourne’s later Aditi project.
• A stepping stone to Mercury. Mercury was also designed at Melbourne, and Zoltan Somogyi, one of its designers, is credited in the NU-Prolog manual for the design of its revision system. Its compiler was first run on NU-Prolog and SICStus Prolog, and Mercury developers say Mercury’s if ... then ... else keywords come from NU-Prolog, which used them to tell its logical conditional apart from Prolog’s ->.

NU-Prolog never became a mainstream Prolog, but it explored the question that drove Mercury: how far a practical logic programming language can go without falling back on non-logical control.