Wednesday, October 22, 2014


In his blog entry entitled "Who Killed Prolog?", Maarten van Emden suggests that the Japanese Fifth Generation project killed Prolog by overhyping it. I agree that it did Prolog no huge favors by overhyping; as someone who has benefited from overhyping of AI, and usualy paid a price later, I wish people who get hysterical about AI would just get over their Frankenstein fantasies.
However, I think Prolog also has internal problems that have stymied its development. I base this on my recent experience teaching a course on computational linguistics. The textbook is Blackburn and Bos's book Representation and Inference in Natural Language, which uses Prolog throughout. I've had a blast doing some Prolog hacking, but I've also been sharply reminded about the language's limitations:
  1. Every Prolog program is basically organized as a global nondeterministic loop. When control gets to the end without a failure, the resulting variable bindings hold the answer. This behavior makes sense for some problems, but not all. Even when it does make sense, technically, the way success and failure propagate out of one piece of a system and into another is often counterintuitive. For example, I wrote an NLP parser that was returning the same parse multiple times, often exponentially many times. The problem turned out to be that the morphology module was succeeding exponentially many times. A better programmer would have seen trouble coming, or would have been a more thorough tester than I. But really, why should multiple success in the humble morphology module be allowed to propagate to the syntax module in the first place?
    What one wants to be able to do is put some braces around a piece of search code and declare what sorts of success and failure signals it makes sense for one box to send to another. If failure in the syntax box might be due to a bad morphological analysis, one should say so; otherwise, a failure in syntax will not result in trying to find another morphological analysis at all.insulation
  2. The Prolog search engine is underneath the hood, inaccessible to the application programmer. Adding enhanced facilities such as tabling and constraint logic programming makes the search engine more complex, requiring hints and nudges to work properly, but it is still somewhere offstage. What language is the engine written in? Is it as high-level as Prolog? If so, why can't it be made visible to the Programmer, in a notation integrated with the notation of the overall program? (Perhaps a language like Oz makes this possible.) Yes, I know that in Prolog it is easy to write your own "meta-interpreter," and vary it to your heart's content, but then you are writing your own language — on top of the built-in engine. Somehow there should be a place to stand outside of all the search processes, a place from which the search can be managed.
    Recent Prologs have exception-handling mechanisms, but they are independent of the failure-handing mechanisms. Perhaps the two could be unified. Imagine a language where one way exceptions can propagate is chronologically. The possible places an exception might land could be partly declared in advance, partly settled at run-time.scheme
  3. Prolog code, especially for manipulating recursive data, has a functional feel. A Haskell programmer will feel right at home, merely needing to add an argument or two to turn functions defined by pattrn matching into relations; and to adjust to the switch from booleans to success/failure. But this happy story takes an abrupt turn for the worse when it is necessary to use side effects and suddenly we are "asserting" data into a global "database." Although the DB raises issues of namespace control (suppose two modules written by different people use the same dynamic predicates), a far uglier issue is the poor level of integration of the assert/retract system with the search engine. There is no way to specify that the lifetime of a DB is specific to a module. It is entirely the programmer's responsibility to use low-level primitives to ensure that just the right assertions are retracted at the just the right time so that failure out of a program and success back into it will work properly.
  4. Prolog is completely untyped. Although untyped ("dynamic") languages are enjoying a vogue right now among young programmers (who love Ruby and (shudder) Python), I think this just shows how poorly educated most programmers are. I am very fond of Common Lisp, but I find it hard to use without my macros for civilizing CL's clumsy type-declaration notations. Restructuring Prolog to fix the other problems in this list would benefit a lot from having types to serve as support beams. For instance, exception-propagation control requires knowing the types of exceptions.
    There are a couple of possible comebacks here: (a) Prolog terms are typed, one might argue, typed by their "functors" (their predicates and/or functions). Yes, this might be adequate for data structures that consist entirely of a globally knowable list of slot fillers, but not for a large data structures with hidden or computed parts. (b) There are OO extensions to Prolog, such as F-logic and LogTalk. Perhaps this is where Prolog is going in the future. I don't know how the OO features sit with the basic Prolog worldview. Plus, objects by themselves do not give you types.
Even if Prolog and Lisp are essentially dead, living on as embers of formerly roaring fires, there are some consolations. These languages contributed many features to languages with warmer metabolisms, such as garbage collection, functional programming, and pattern matching. (Although many programmers don't know this history.amnesia) Perhaps we should think of these old, beautiful languages as the classical music of the programming world. The community of listeners is small, but their being outnumbered by pop fans doesn't mean pop is superior to serious music; quite the opposite: only the person with wisdom and insight can appreciate the intricate complexities of classical music, Lisp, and Prolog.


Note insulation
Of course, I am not advocating being able to insulate programmers from the consequences of buggy code; the problem in the morphology analyzer needs to be caught before it leads to an exponential search for one correct answer. But sometimes the failure propagating back into a module will cause an expensive, futile (but correct) search in that module ultimately leading to its correctly signaling failure; one should be able to skip that on the grounds that even success there wouldn't help the failing module. [Back]
Note scheme
I'm sure this could be done in Scheme, using call-with-current-continuation. This is a consequence of a folk theorem that anything can be done with call/cc. [Back]
Note amnesia
Recently trained programmers seem to think the world consist of the systems they were trained on. If they were taught Ruby, they defend it to the death against critics, because it seems natural to them. (I can't claim to be an exception, having been trained on Lisp as an undergraduate.) So, in the 1980s, everyone was a C programmer, and garbage collection was attacked as being for people too stupid to know when to free a malloc'ed block of storage. Now everyone takes garbage collection for granted, simply because Java, Python, and Ruby have it, although no one knows why. It drives me crazy that from generation to generation programmers hate Lisp syntax, just because a+b isn't the way you add two numbers. They don't always know how many of the forebears have shared their disdain; the other day someone criticized Lisp's "novel and unintuitive" syntax on some message board. "Unintuitive," okay, but "novel"? One of these days Clojure or something of that sort will become a big success story, and all of a sudden Lisp's syntax will be defended as the only one possible. [Back]

No comments: