Porting NU-Prolog (c. 1995) from BSD Unix to modern Linux
NU-Prolog is a Prolog variant designed by the members of the Machine Intelligence Project at the University of Melbourne, released circa 1986, with a version 1.6.9 released circa 1995.
Recently, I sought to port some software written in NU-Prolog (written by one of its creators, Lee Naish). Due to NU-Prolog's unique features, not found in contemporary free Prolog implementations such as GNU Prolog or SWI-Prolog, this pointed to porting NU-Prolog to modern systems as the easiest approach.
The source code for NU-Prolog is available at https://people.eng.unimelb.edu.au/lee/src/nuprolog/, and it makes use of standard GNU/POSIX build tools – make, gcc, sed, awk, etc. However, it is written for BSD-like systems, and will not compile on Linux, even when appropriate configuration flags are set, producing errors such as:
machdep.h:128:26: error: conflicting types for ‘memcpy’; have ‘void(void *, const void *, size_t)’ {aka ‘void(void *, const void *, long unsigned int)’}
128 | #define bcopy(s1, s2, n) memcpy(s2, s1, n)
| ^~~~~~
[...]
/usr/include/string.h:43:14: note: previous declaration of ‘memcpy’ with type ‘void *(void *, const void *, size_t)’ {aka ‘void *(void *, const void *, long unsigned int)’}
43 | extern void *memcpy (void *__restrict __dest, const void *__restrict __src,
| ^~~~~~
Finding a supported target to build on; or, a tour of the greats
Before proceeding any further, I wanted to be able to build NU-Prolog on a supported system, to verify its operation and ensure that the software I was interested in would work. By default, the provided source code for NU-Prolog builds for MACHINE_SGI, i.e. a Silicon Graphics (SGI) machine, presumably running IRIX, its proprietary Unix operating system.
The MAME emulator is able to emulate IRIX 6.5.22 running on an SGI Indy, and a helpful tutorial is at https://sgi.neocities.org/. I was able to get IRIX to start booting on MAME, but it was very slow, and after 10 minutes waiting for IRIX to boot, I gave up and moved on.
The other machine targets listed in the NU-Prolog source are:
- MACHINE_SUN3 (Sun Microsystems Motorola 68020-based Sun-3), MACHINE_SUN4 (SPARC-based Sun-4) and MACHINE_SUN4_SOLARIS
- MACHINE_MACII (presumably the Apple Macintosh II running Apple's Unix implementation A/UX)
- MACHINE_ENCORE and MACHINE_ENCORE_BSD_EMUL
- MACHINE_386 (the Intel 80386 processor, forming the basis of today's personal computers)
- MACHINE_ELXSI
- MACHINE_DEC (MIPS-based DECstation) and MACHINE_MIPS
- MACHINE_VAX (the popular VAX ISA by DEC)
- MACHINE_ALPHA (DEC Alpha, which succeeded VAX, running DEC OSF/1 Unix)
Having set aside SGI IRIX, my attention was next drawn to MACHINE_VAX. VAX machines were highly influential, and the VAX has been described as ‘the single most influential computer of all time’. I recall my own first exposure to the term many years ago on a computer jargon glossary page for ‘grok’ hosted on some GeoCities equivalent.
SimH can emulate a VAX-11/780 or MicroVAX II, and can run 4.3BSD, the (almost) last version of the original Berkeley Unix, and which has been described as ‘greatest software ever written’. The greatest software on the most influential computer – what a combination!
Following instructions from the Gunkies Computer History wiki, I was able to install 4.3BSD on SimH, but faced difficulties with the setup being quite temperamental – networking is fiddly, so installing GCC and transferring the NU-Prolog code would be nontrivial, not to mention that BSD would sometimes refuse to boot.1 Faced with these obstacles, I again turned elsewhere.
The next option to catch my eye was MACHINE_MACII, the Apple Macintosh II. I have previously emulated a Macintosh II running Mac OS using Mini vMac (here's an old post of mine about Mini vMac from 2016).
However, Mini vMac does not emulate the hardware required for A/UX. Instead, Shoebill is a now-discontinued Macintosh II emulator with A/UX support. I was able to boot A/UX under Shoebill, but as with SGI IRIX the performance was poor.
The natural answer to poor emulation performance is to stop trying to emulate a different instruction set architecture, and use something x86-based, which would enable use of hardware-assisted virtualisation. One machine target listed by NU-Prolog is MACHINE_386, so I turned my attention to setting up AT&T System V Unix. I was able to install SysV in qemu-kvm, but found little in the way of resources on getting gcc and the other build tools installed. Instead, I turned to FreeBSD.
FreeBSD 4.11 comes bundled with gcc and all the other tools required to build NU-Prolog, and also supports networking, SSH and FTP out of the box, avoiding the issues faced with the other systems.
Building NU-Prolog on FreeBSD
Unfortunately, NU-Prolog does not build correctly on FreeBSD out of the box either, even when MACHINE_386 is set:
main.c: In function `code_gen':
main.c:147: conflicting types for `sys_errlist'
/usr/include/stdio.h:225: previous declaration of `sys_errlist'
Luckily, though, this error is easily addressed:
--- a/na/main.c 2021-09-07 21:13:27.613411522 +1000
+++ b/na/main.c 2021-09-07 21:12:22.084220723 +1000
@@ -146,3 +146,3 @@
extern int errno, sys_nerr;
- extern char *sys_errlist[];
+ //extern char *sys_errlist[];
The next error to squash comes from awk, reporting:
sh lex.make "-DMACHINE_386 -DBSD4"
awk: lex.c.awk:17: tolower["_"] = "_";
awk: lex.c.awk:17: ^ syntax error
awk: lex.c.awk:18: tolower["0"] = "0";
awk: lex.c.awk:18: ^ syntax error
awk: lex.c.awk:19: tolower["1"] = "1";
awk: lex.c.awk:19: ^ syntax error
[...]
This syntax error appears to be because tolower is a predefined function in this version of awk, so it cannot be used as an array name. This is a simple fix, too – we run:
$ sed -ibak 's/tolower/to_lower/g' na/lex.c.awk
$ sed -ibak 's/tolower/to_lower/g' sys/bytec.ns.awk
Next we have:
lex.c: At top level:
lex.c:895: syntax error before `!'
This also appears to be some sort of reserved word conflict, so we fix that too: (the function is not actually called anywhere)
--- a/na/lex.c 2021-09-07 21:21:23.920866609 +1000
+++ b/na/lex.c 2021-09-07 21:20:58.421181329 +1000
@@ -892,7 +892,7 @@
* Test whether a string is full of nothing but space(s)
*/
Bool
-isblank(line)
+is_blank(line)
char *line;
{
char *c;
This squashes all the compiler errors! We can now make na (the NU-Prolog assembler, used to bootstrap NU-Prolog) and nep (the NU-Prolog interpreter).
The next tool to be built is nc (the NU-Prolog compiler), which is written in NU-Prolog assembly and built using na and nep. Unfortunately, this results in a segmentation fault:
../nep/nep -C -u 64 -v 16 -w 8 -x 4 -s -i ../nep/wake.no -S nuc ../sys/parser.no ../sys/sort.no ../sys/atoms.no [...]
*** Signal 11
Helpfully, FreeBSD 4.11 also bundles the GDB debugger, so we can pass -g to GCC in the Makefile to build debugging symbols, and investigate this segfault in GDB:
$ cd co; gdb ../nep/nep
GNU gdb 4.18 (FreeBSD)
[...]
(gdb) run -C -u 64 -v 16 -w 8 -x 4 -s -i ../nep/wake.no -S nuc ../sys/parser.no ../sys/sort.no ../sys/atoms.no [...]
[...]
Program received signal SIGSEGV, Segmentation fault.
0x804faf6 in enterFunctor (arity=6, atom=0x7f778) at symTab.c:242
242 f = lookupFunctor(arity, atom->a_functors);
(gdb) bt
#0 0x804faf6 in enterFunctor (arity=6, atom=0x7f778) at symTab.c:242
#1 0x804bf79 in initStrHeaders () at nep.c:703
#2 0x804c7a6 in main (argc=58, argv=0xbfbff7b8, env=0xbfbff8a4) at nep.c:1016
We note from the code that we are dereferencing the pointer atom, which points to address 0x7f778, which is not a valid memory address. What's going on?
The relevant code in nep.c is:
StrHeader6_BMT = StarToStrHeader(6, &Sym_BMT);
Following the trail:
#define StarToStrHeader(arity, x) MakeStrHeader(arity, x)
#define MakeStrHeader(arity, x) \
((Structure) enterFunctor(arity, (Atom *) eRef(x)))
And one more step:
#define eRef(x) ((Object *)(((UWord)(x)) & 0x3ffffff))
So the pointer to Sym_BMT is first being bitwise AND-ed with 0x3ffffff. On 32-bit x86-based Unix-like systems, binaries are loaded into memory starting at address 0x08048000. We can see this using objdump:
$ objdump nep/nep
../nep/nep: file format elf32-i386
Sections:
Idx Name Size VMA LMA File off Algn
0 .interp 00000019 080480f4 080480f4 000000f4 2**0
CONTENTS, ALLOC, LOAD, READONLY, DATA
1 .note.ABI-tag 00000018 08048110 08048110 00000110 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
[...]
The bit twiddling, then, will clearly corrupt the pointer!2 This must not have been an applicable convention on NU-Prolog's original supported systems.
Thankfully, a workaround for this issue, though slightly obscure, is not too difficult. We need to create a custom linker script that will load the binary at some lower memory address (say, 0x01000000) where pointers will not be mangled.
We first extract the default linker script:
$ ld --verbose
GNU ld version 2.12.1 [FreeBSD] 2002-07-20
Supported emulations:
elf_i386
using internal linker script:
==================================================
/* Default linker script, for normal executables */
OUTPUT_FORMAT("elf32-i386", "elf32-i386",
"elf32-i386")
OUTPUT_ARCH(i386)
ENTRY(_start)
SEARCH_DIR("/usr/lib");
/* Do we need any of these for elf?
__DYNAMIC = 0; */
SECTIONS
{
/* Read-only sections, merged into text segment: */
. = 0x08048000 + SIZEOF_HEADERS;
.interp : { *(.interp) }
.hash : { *(.hash) }
[...]
}
We copy this to a file linker.lds and replace 0x08048000 with 0x01000000, and in the Makefile set:
CDEFS = $(MACHINE) -DBSD4 -g -Wl,-T,/home/runassudo/nuprolog/release1.6.9/linker.lds
We recompile NU-Prolog, yet find that, while compiling nc, nep segfaults again. GDB, however, shows that the segfault is at a different location:
Program received signal SIGSEGV, Segmentation fault.
0x106c722 in interpret (Self=0x1085ba4) at inter.c:2522
2522 v = Y[Arg1]; DeRef(v);
(gdb) bt
#0 0x106c722 in interpret (Self=0x1085ba4) at inter.c:2522
#1 0x104cf41 in execute (entryPoint=0x1077779 "$init", argflg=0, args=-1526202440) at nep.c:1258
#2 0x104cc5f in main (argc=58, argv=0xbfbff7b8, env=0xbfbff8a4) at nep.c:1128
After some investigation, I noted that nep was reading the bytes 00 00 00 12 from memory into a dword, yielding the unreasonable looking 0x12000000 (as x86 is little-endian). These bytes, however, would be the representation of the very reasonable value 0x00000012 in big-endian! Further investigation reveals that machdep.h contains some code to automatically detect the endianness of the host system; however, this does not account for MACHINE_386:
#ifndef LITTLEENDIAN
#if sequent && i386
#define LITTLEENDIAN
#endif
#if vax || ns32000 || ns32032 || ns32332 || ns32532
#define LITTLEENDIAN
#endif
#ifdef MACHINE_DEC
#define LITTLEENDIAN
#endif
#ifdef MACHINE_ALPHA
# define LITTLEENDIAN
#endif
#endif /* LITTLEENDIAN */
After manually adding -DLITTLEENDIAN to the compile flags, nc now compiles correctly! And, nc correctly compiles the software written in NU-Prolog that I was interested in.
Porting to modern Linux
Now that we know what is required to build NU-Prolog on BSD, porting to Linux is mostly straightforward. We must additionally pass -m32 in several places to force a 32-bit binary to built, some #includes need to be added, references to sys_errlist and sys_nerr need to be replaced (as they have been deprecated and removed in glibc), etc. as the compiler instructs.
However, there is one area where some more work is required: NU-Prolog ships is own malloc implementation. You may think we could simply strip this and replace it with glibc malloc, but NU-Prolog also interfaces with the internals of its malloc implementation to dump memory in bulk to a file and later restore – this is how compiling and executing compiled code works in NU-Prolog.
The best approach would probably be to refactor NU-Prolog to remove this dependence on malloc internals, but this would be a lot of work. Instead, I prefaced all nep's bundled malloc functions with nep_, allowing it to coexist with glibc malloc.
However, this causes glibc's own malloc to segfault (for example, when printf is called), presumably because both malloc implementations are stepping on each other's toes by trying to directly manage the nep data segment using brk. brk is used to grow/shrink the process's ‘data segment’, representing a contiguous area of virtual memory from which malloc makes allocations.
The nep_malloc internals NU-Prolog depends on for dumping and restoring memory require this segment to be contiguous, so I could not simply pass nep_malloc through to glibc malloc. To address this, I modified nep_malloc to instead initially request a 128 MiB allocation from glibc malloc, and then subsequently make its own allocations from this buffer:3
#define DYN_MEM_SIZE 1024 * 1024 * 128
// ...
void
initMalloc()
{
// ...
// initCURBRK;
lowWater = malloc(DYN_MEM_SIZE);
highWater = lowWater;
// ...
}
However, this ran into the issue from earlier, where NU-Prolog discards the high bits of pointers. malloc cannot be forced to make allocations at low memory addresses only, so I instead turned to mmap to reserve 128 MiB of memory at address 0x02000000, which fits within the range of NU-Prolog's supported pointers:4
#define DYN_MEM_BASE 0x2000000
#define DYN_MEM_SIZE 1024 * 1024 * 128
// ...
void
initMalloc()
{
// ...
// initCURBRK;
lowWater = mmap((void*)DYN_MEM_BASE, DYN_MEM_SIZE, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED_NOREPLACE, -1, 0);
if (lowWater != DYN_MEM_BASE) {
printf("mmap failed\n");
}
highWater = lowWater;
// ...
}
And with that, and a helluva lot of warning: implicit declaration of functions (FIXME!) we have enough of NU-Prolog compiled on Linux to run the software I was looking into!
$ ../nuprolog/bin/nc -e main_stdin count.nl
Reading and compiling count.nl.
% Time was 0.033s
Warning: main/1 redefined
./a.out < demo.txt
List of candidates:
a
b
c
d
e
f
Number of candidates: 6
Number of vacancies: 3
Number of ballots: 11
Quota: floor(11*1000/(3+1) + 1) = 2751
Distribution of first preferences:
ELECTING b
ELECTING a
Successful candidates with surpluses pending:
a 3000
b 3000
Continuing candidates:
c 2000
d 2000
e 1000
f 0
Exhausted ballots: 0
----------------------------------------------
Distribution of surplus for b:
Successful candidates with surpluses pending:
a 3000
Continuing candidates:
c 2000
d 2000
e 1000
f 249
Exhausted ballots: 0
----------------------------------------------
Distribution of surplus for a:
Continuing candidates:
c 2166
d 2000
e 1000
f 249
Exhausted ballots: 83
----------------------------------------------
EXCLUDING f
Distribution of parcel(s) of excluded candidate:
Continuing candidates:
c 2166
d 2083
e 1166
Exhausted ballots: 83
----------------------------------------------
EXCLUDING e
Distribution of parcel(s) of excluded candidate:
ELECTING d
Successful candidates with surpluses pending:
d 3083
Continuing candidates:
c 2166
Exhausted ballots: 83
Excluded ballots not yet distributed: 166
----------------------------------------------
Distribution of parcel(s) of excluded candidate:
Successful candidates with surpluses pending:
d 3083
Continuing candidates:
c 2166
Exhausted ballots: 249
----------------------------------------------
Distribution of surplus for d:
Continuing candidates:
c 2166
Exhausted ballots: 581
----------------------------------------------
EXCLUDING c
Distribution of parcel(s) of excluded candidate:
Exhausted ballots: 2747
----------------------------------------------
Electing remaining candidates.
Final result: the following candidates are elected:
b
a
d
(It turns out that this software has a significant logic error that makes it unsuitable for use…5 Que sera!)
My ported code for NU-Prolog is available at https://gitlab.com/RunasSudo/nu-prolog-linux.
Footnotes
-
I also tried 4.3BSD-Quasijarus and NetBSD to similarly mixed success. ↩
-
This bit twiddling appears to be necessary because NU-Prolog uses the high bits to store metadata. Fixing the code to handle larger pointers would be a better solution, but would likely be significantly more involved than just relocating the binary. ↩
-
This would cause issues if NU-Prolog ever wants to nep_malloc more than 128 MiB of heap data, but it seems to work for now. ↩
-
Similar to the 128 MiB issue, this would cause issues if the nep code were to exceed more than 0x01000000 bytes (and therefore overlap with this buffer). ↩
-
Next project, learn Prolog! ↩