CoPilot writes a Prolog interpreter!

The other day I was idly leafing through a book entitled "Computer Science from Scratch" by David Kopec; amongst other things it promises to show one how to build interpreters. All code examples are written in Python, which is how code is shown these days, but for an old codger like me, so much seems to be hidden away, making comprehension difficult. 

The second chapter describes writing an interpreter for Tiny Basic, a language that was often implemented on the 8-bit home computers of the late 1970s/early 1980s. This subset of the language is very simple: for example, there can be at most 26 variables that each have a one letter name (i.e. A, B, C); this translates into a simple 26 member array of integers (the only data type allowed).

When walking the dog afterwards, I contemplated writing a similar interpreter in Pascal. This shouldn't be too hard, I thought, although I missed in the discussion how GOTO and GOSUB were implemented (this turned out to be not particularly difficult). One problem with BASIC is that arithmetic is written using what is called 'infix notation' - the operator is inbetween the operands. For example 2 + 3 is a simple expression with infix notation: 2 and 3 are the operands and + is the operator. Some languages use prefix notation, e.g. Lisp, where the expression would be written as + 2 3, and some languages use postfix notation, e.g. Forth, where the expression would be written as 2 3 +. It's relatively easy to evaluate postfix notation by means of a stack.

Then I thought that maybe I could ask CoPilot to write a simple infix expression parser in Pascal. No problem, I was told; almost immediately code was shown that first turned the infix notation into postfix notation then showed how to evaluate this expression. Impressed, I then asked CoPilot to write a Tiny Basic interpreter in Pascal - this went through several iterations as I asked for more and more functionality. The code seemed to have correct Pascal syntax, although when I tested the most simple version, I discovered several minor mistakes that will have to be corrected throughout the versions.

Later on in bed, I thought about these capabilities and wondered whether CoPilot could write a simple Lisp interpreter or even (gasp) a Prolog interpreter. As a result of these thoughts, I found it very difficult to fall asleep.

This morning, in a free moment, I asked CoPilot to write a simple Lisp interpreter that too went through a few iterations (for example, car, cdr and cons were missing at the beginning). No lists were used at all in the implementation, only dynamic arrays. I have yet to test the final version, although to be honest, I'm not too interested in it.

If CoPilot can write a simple Lisp interpreter, then can it write a simple Prolog interpreter? Indeed it can! This too went through a few iterations as more functionality, especially backtracking which is the raison d'etre of Prolog, was added. Again, no lists or stacks using pointers: everything is implemented by means of dynamic arrays. This is a totally different way of implementing the language; no doubt I will spend no small amount of time single stepping though the code in order to understand how it works.

---

This day in blog history:

Blog #	Date	Title	Tags
16	05/10/2005	Sudoko	Programming
203	05/10/2009	Old computer in new case	Computer
411	05/10/2011	Firebird DB management tool (3) - Bells and whistles	Programming, SQL, dbExpress
979	05/10/2016	DBA: Entering the final third of the doctorate	DBA
1079	05/10/2017	A kibbutz day	Jewish holidays, Obituary, Kibbutz
1178	05/10/2018	Geoff Emerick, 1945-2018	Obituary, Beatles
1342	05/10/2020	Continuing the development of the Priority Cross Referencer (PrioXRef)	Programming
1428	05/10/2021	Continuing the BP saga	Health, CPAP, Blood pressure, Aldosterone
1672	05/10/2023	The neuroendocrine system and my blood tests	Health, Nutrition
1834	05/10/2024	The swimming season finished rather abruptly	Swimming