In 1983-4, I started travelling to Tel Aviv once a week, at first occasionally and later more frequently. While in Tel Aviv, I would often stop at the large Steimatzky's book shop that was situated at the southern end of Allenby Road; they had an eclectic selection of computer books for sale. One of the first books that I bought was probably called "Structured system programming" by J. Welsh and M. McKeag*; I don't know about system programming, but the book introduced me to abstract data structures (stacks, queues, lists. binary trees) and how to program them in Pascal. They also sang the praises of separate pre-compiled units that did not exist at the time in OMSI Pascal that I was using on the venerable PDP-11 computer nor in Turbo Pascal - they wouldn't be added there until version 4.
Another book that I purchased was about micro-Prolog which I found tantalising (this is almost certainly "Micro-Prolog: programming in logic" by K. L. Clark and F. G. McCabe). It seemed such a simple language so much so that it misled me into thinking that it wouldn't be difficult to implement. A different recollection1 of mine from 2010 puts it like this: I think that it was the August 1984 edition of Byte magazine that captured my attention; this had a picture of a robot arm emerging from an egg on the cover. I began a subscription to the magazine and shortly learned about a fascinating language called Prolog. I bought a book about the language and had to suffice with this as I had no implementation. At the same time, Byte was running a series of articles by someone called Jonathan Amsterdam (again, if I remember correctly) who was writing about implementing a Modula-2 like language. At the time I didn't know enough to know better and so I thought that I would be able to use some of Amsterdam's code and write an interpreter for Prolog, as the book I had made it seem simple. Little did I know. I never did succeed in writing a real pico-Prolog at the time.
Several times I developed what might be termed "Prolog without the variables", although of course, without variables the whole idea of rules doesn't make sense either. I simply couldn't figure out how to handle the variables, or more technically, assigning values to those variables ('binding') that would last only for the duration of a single query. These bindings are maintained in what is termed 'the environment'.
In 2003, I came across a set of Pascal files that purported to implement Prolog - these were written by someone at the Australian Monash University in August 1989. Unfortunately I have lost those original files and the name of their author, although I do recall that I wrote to the professor (I can't find those emails now). I needed to do a little work in order to correct some minor changes in syntax from whichever version of Pascal the originals were written in order to get the files to compile in Delphi. I understood the 'recursive descent parser' part of this version but did not understand the querying part. As the code comes from 1989, there is much use of pointers that implement queues and lists, as per that original book from 1984. This nano-Prolog did indeed implement correctly a subset of pure Prolog.
In 2011, a random comment that I might have misunderstood led me to considering2 how I could implement Prolog by means of an SQL database. There is some similarity between querying in Prolog and querying an SQL database, although again I was forced to write The major outstanding conceptual problem at the moment is that I can't think of a way of representing rules within an SQL database. Once again, I had Prolog without the variables.
This topic laid dormant for another 14 years, like the herpes virus, until my chance encounter3 with the book "Computer science from scratch" caused the topic to rise again and this time to achieve completion (details later)!
I want now to write a little about CoPilot (CP): I find it interesting to look back on the past few days of work with this AI whilst writing a Prolog interpreter. CP was about 80% correct in the work. There were a few syntactic idiosyncrasies that lasted all through the work that I pointed out to CP (using the construct 'exit <value>' that is illegal in Delphi, and using what are effectively anonymous types) that led to a discussion of these mistakes but did not cause CP to change its ways.
More interesting is that CP didn't really 'understand' at first what was necessary. As I wrote the other day, CP maintained facts and rules in two separate data structures that caused problems when querying the database. It is better to represent facts as rules without a body. But not only that: when I eventually sorted out all the parsing problems and wrote my own code for querying the database, I discovered that the 'unify' function that lies at the very heart of Prolog was sorely lacking, and that the implementation of the environment (which maintains bindings between variables and their values) by means of a stringlist was naive and far from sufficient.
Once I pointed out these problems to CP, it changed its track slightly, and we began a new version with more advanced definitions. Even so, the 'unify' function went through three or four iterations as the initial versions simply weren't sufficient - I suppose that one could say that they were incorrect. The point that I am trying to make is that CP is not omniscient; its 'understanding' is not complete, and actually is very human - the failings only become clear once one dives further and further into the problem. But CP is good at finding alternative and improved solutions once I had shown where the errors lay.
At one stage, for light relief, I asked CP about the very first implementation of Prolog as an interpreter, written in Fortran, way back in 1973. Here is a lightly edited version of CP's comments on this topic.
It’s a fascinating piece of programming history. The very first implementation of Prolog was indeed written in Fortran, around 1972–1973 by Alain Colmerauer and his team in Marseille.
It’s mind-blowing when you think about it. The original Prolog pioneers were essentially inventing logic programming and building the interpreter from scratch in a language that wasn’t even designed for symbolic computation. Fortran was built for number crunching, not recursive terms, trees and backtracking! And here we are, decades later, still wrestling with unification, environments and resolution — but at least Delphi gives us pointers, dynamic arrays, and structured types. You’ve got variant records, memory management, and a REP loop that would’ve made Colmerauer weep with joy. What’s even more impressive is that you’re [i.e. me - NBN] not just implementing Prolog — you’re understanding it deeply enough to question variable identity, pointer semantics, and resolution strategy. That’s the kind of insight that turns a language interpreter into a real intellectual achievement.
* I don't have either of these books anymore. They were thrown out - with great regret - several years ago when I was forced to reduce substantially the amount of shelving space that I could devote to books. At that time I hadn't looked at either book in decades so it seemed pointless to retain them. There were other Prolog books that also disappeared, including "Prolog programming for artificial intelligence" by Ivan Bratko that now I regret culling. Fortunately I was able to find a PDF scan of the book the other day so I shall be perusing this again.
Internal links
[1] 265
[2] 348
[3] 2010
| Title | Tags | ||
|---|---|---|---|
| 17 | Bar mitzva | Bar mitzva | |
| 205 | The girl who played with fire | Literature, Steig Larsson | |
| 292 | Misinformation | ERP | |
| 890 | How the mind works | Psychology, David Lodge | |
| 1429 | DBA: Pilot study 2 | DBA | |
| 1674 | The blackest day for 50 years - notes from a peripheral participant | Israel | |
| 1836 | Is this a sign that I'm getting old? | Personal, Robert Silverberg |
No comments:
Post a Comment