PROLOG has (almost) the same Expressive Power as Human Language

Kelsey demonstrates Nintendog for Ciera & Ivan from the ESC SchoolImage by NJ – Library Events via Flickr

Many thanks to readers who appreciated this article (more than a thousand, so far). However, please note as…

  • URGENT: My e-mail address is now omadeon AT hotmail.com; please DO NOT send any e-mail to my obsolete yahoo-account.

A few days ago, I wrote a short posting in this blog about the fact that The ultimate high productivity programming language is PROLOG. A few days later, I was quite astonished to see that this posting became extremely popular! It was listed as no. 35 in the «most popular postings worldwide» list of WordPress a few days ago. (You can click here to verify this claim, scrolling down to no. 35). Meanwhile, some people discussed the Prolog posting elsewhere on the Web. E.g. a discussion in the wiki-site «reddicious», as well as in another blog («The Hungry Brain» – here).

As a result, I will continue to write about Prolog, about why I use it, about the wonderful things you can do in it, and (last but not least) about the fallacy that it cannot be used as a «general purpose programming language«. Well, of course it can be used as a «general purpose language»! This is the philosophy of Visual Prolog -for example- created by an innovative bunch of nice people in Denmark (whom I met personally in a Prolog conference, in April 2006). They created this Prolog dialect and designed it for maximum speed, highest efficiency and ease of use, with a Visual development environment and an object-oriented structure (in the latest versions, 6 and 7). (more about this later, in another posting)

However, today I want to talk about one aspect of Prolog (and many similar Logic Programming languages, e.g. Mercury) that is rarely discussed and very rarely appreciated: The fact that…

  • PROLOG has (almost) the same Expressive Power as Human Language!

So, what does this mean?

  • Well, this idea is a verifiable fact in linguistics and NLP (Natural Language Programming).

  • It’s also an issue of practical importance, since you can convert almost any human sentence to a Prolog (logic) representation, which is not a mere (passive) data representation, but a real working program (corresponding to an expression in First Order Logic) which can sometimes produce practical results (e.g. questions or queries in a database or knowledge-base).

  • One of the most serious challenges for the future is precisely this aspect of Prolog, which makes it possible to convert human text from Web pages to machine-readable representations of it. In fact, today’s Semantic Web initiative is feasible precisely due to some aspects of this conversion, extracting meaningful rdf code from human-text in web-pages, using software such as «Cypher«.

  • I used the word «almost», because it would be a little silly to convert e.g. poetic or allegorical human sentences to programming code, although it is still possible (to some extent).

  • Finally, your human sentence(s) must be (in certain ways) complete and consistent, to generate meaningful working Prolog code.

Many years ago, I had written an extension of «PIE» (PDC/Visual Prolog’s open source interpreteter) that was able to convert human sentences (in Greek) to Prolog trees, and from these Prolog trees it generated Prolog code. This was not new, at the time. There were many other Prolog programs converting human text to Prolog code. Of course, such programs typically convert subsets of English to meaningful Prolog code, and human sentences can only be converted if they have a precise (logical) meaning. However, such examples can demonstrate the Expressive Power of Prolog.

  • Moreover, the old dictionary limitations of only small «subsets of English» being convertible to Prolog, have been overcome by today’s vast machine – readable dictionaries of human language (e.g. Wordnet -click here) and large (open source) knowledge bases of facts about… life and the universe (such as «OpenCyc» -click here).

Well… (you may ask)

– Why aren’t other (procedural) programming languages, as powerful as Prolog (to «understand» human language)?

  1. Firstly, because they lack the inherent expressive power of Logical Representation, i.e. inference and unification, which are default features of Prolog.
  2. Secondly, because procedural languages are inherently stupid: They were designed only to do things that are meaningful for a computer; not designed to represent logically… anything that anyone does.
  3. Thirdly, there is no limit to what can be represented in Logic (and Logic Programming, i.e. Prolog).

E.g. there is no point to convert into ‘C’ or C# or Pascal (etc.) something like «The grandparent of a human is a parent of the human’s parent«. It simply makes no sense, and it can’t correspond to a meaningful (i.e. executable) program. However, in Prolog, you can certainly convert (automatically) the previous sentence to a meaningful, executable piece of Prolog code, e.g.

grandparent(A,X):- human(A), parent_of(A,Parent), parent_of(Parent,X).

If you also tell Prolog that «john, jack and jill are human», as well as «john is a parent of jack» and «jack is a parent of jill», the following Prolog code can be automatically generated (by a simple NLP parser and Prolog code generator):

human(john).

human(jack).

human(jill).

parent_of(jack,john).

parent_of(jill,jack).

Now the above lines of code are ready to execute, to get immediately meaningful results, e.g.

?- grandparent(X,Y).

Answers: X=jill, Y=john.

Of course, it is because the human sentences had meaning (in real life) that Prolog was able to successfully convert them into meaningful code, able to deliver meaningful results.

However, if you write nonsense, Prolog cannot understand it (but neither can a… human reader)!🙂

Exercises (for the reader):

  1. Use your… mouse, to access the knowledge accumulated inside the hyperlinks of this posting!🙂
  2. Use Google (or my bookmarks, or other search methods) to find Prolog programs that can convert subsets of English to Prolog code, and are also able to use this code, to answer human questions (in the same subset of English).
  3. Read my… next posting!🙂
Related articles

.

11 comments

  1. One problem of programming languages is they fail to become sufficiently knowledgeable about the medium they exist in. This is a bigger problem in Prolog than, say, in C#, because C# has lots of self-referent features, like being about to compile code at runtime and execute it at once. Consequently, what Prolog must be taught is how to interact better with its surrounding medium, i.e. the computer.

  2. Yes Dmitri, you are right.
    As you probably know, Prolog can also become self-referent, but mostly with regard to its own (meta-)programming structures; not necessarily «with the computer» (as C# does in a much lower level). Combining low-level access with self-referent capacity is the best, even better if self-reference is done at a very low level, close to machine code.
    I write a lot of Assembly language code for Prolog (this is one of my specialties) but I sometimes… envy C# programmers for some of the things they do. (Still, there is also a lot they can’t do as easily as Prolog).

  3. Any decent Prolog implementation compiles clauses that are asserted at run-time (which is of course possible in Prolog, via asserta/1 and assertz/1) just like static clauses – either to abstract machine code or native code. A Prolog program can also refer to its own clause database at run-time and is at least as introspective as any other language.

  4. Quite right, mt!

    There is of course a «catch», which is that asserting and retracting clauses is not without cost, in memory and in time (today minimised thanks to our extremely fast machines). This is why Visual Prolog in particular is based on an extremely rigid separation between clauses as code, and clauses as «facts» in a Prolog database. This used to be good in the past, since it resulted in extremely fast operation of the PDC/ Visual prolog compilers, enabling them to be useful for general purpose programming projects, since the speed of the resulting code was quite fast, comparable to Pascal (at the time -early nineties).

    In recent years, Visual Prolog has grown to become a fully-developed Object Oriented, Visual-Environment modular prolog system, which is quite robust (especially version 7) for any kind of programming. However, my complaint about Visual Prolog is that it continues (due to design decisions) the lack of generalised «assert» and «retract». Talking to Leo Jensen (leader of PDC) last year, and to Thomas Puls (at the conference in Portugal) made me appreciative of all the other qualities of their compiler, but NOT this one; if they changed their old design decision, they might also make their compiler compatible with ISO-standard Prolog (something that they are unwilling to do at the moment). In the end, for particular projects I do these days, I was forced to use SWI-Prolog instead.

  5. So, the real challenge I think is to re-design the low-level details of implementing meta-predicates, so that self-referent operation of Prolog becomes as efficient as code written before compilation. I haven’t done any benchmark tests, yet, but it seems reasonable that the current «small» inefficiency of Prolog compilers becomes a big inefficiency, ing things like massive Data Mining. This is why I use many Assembly Language extensions of Prolog, hand-written over a number of years, as explained in
    http://www.omadeon.com/alc

    If Leo Jensen approved of re-designing Visual Prolog so that assert and retract (and other features of standard Prolog) are implemented, I’d recommend Assembly langage (still trying to persuade him, in fact).

    As regards other compilers, we need to see the latest benchmark tests.

  6. It’s probably better to implement Hot-Spot compilation where it counts. An interesting shortcut is to compile Prolog to Java (byte-) code, and let other tools do the compilation to machine code on-the-fly.

  7. That’s a very interesting idea, mt!

    As an aside, there are (as you probably know) quite a few very decent Java-implementations of Prolog. E.g.

    http://del.icio.us/omadeon/java-prolog

    (my public bookmarks on java-prolog implementations; you can also try the search facility of «del.icio.us» with the string «java prolog» (the spacew being interpreted as «AND») to find… more than 240 references.

  8. Although more a fan of functional languages (Haskell) I can appreciate what you’re saying, although I would extend it to declarative languages in general. Sure, prolog expresses logical concepts and inferences very «naturally» so if you model human language as a system of logical concepts and inferences it’s trivially true that prolog becomes a very good way to represent human language in the computer. But:
    a) there is more than nonsense to what a logical model of human language would leave out,
    b) the logical model is not necessarily the best prediction of the forms of human language and
    c) the logical model is not necessarily an accurate explanation of the existence of human language.

    The above criticism is not of course a defense of procedural languages, only a caution of not to draw too much conclusion from the success of one declarative model. As an example of an alternative view, which suits my choice of programming language better, is the combinatorial style theories like for example the theories of Sebastian Shaumyan which are very «naturally» represented in Haskell.

  9. @kouk
    Thanks for your thoughtful comment.

    What you are saying is very true. A very trivial example of natural language sentences where all your reasonable objections are undoubtedly quite valid, is… poetry!🙂

    For example, I’ve been struggling to translate the poems of Odysseus Elytis from Greek to English, and… eating humble pie ever since I tried it: Most of them are extremely difficult to translate, some are simply untranslatable, and human translators draw resources from things like metaphor, inexact interpretations (in a language where the deep semantics are not the same), and so on. Certainly, logical models play only a very small part in the translation process, the logical model is CERTAINLY not the best prediction for the poetic forms, and as regards explanation (of a poem’s existence) logical models often fail catastrophically!

    I am now delighted to read the Wikipedia link you gave, about the theories of Sebastian Shaumyan, refreshing my knowledge about these issues.

    Well, although what you said is very true, it is also true that in a very large number of cases, especially e.g. in understanding human texts like scientific papers, reports, news articles, etc., Prolog and Haskell, as well as other declarative or functional languages can have an expressive power which is «ALMOST the same as human», as you already know. But the word «almost» is (even then) _not_ to be taken lightly!🙂

    P.S. An extract of the reference article you gave, has succeeded to make my day:

    «Recently, AUG has been used in computational linguistics in the development of a natural language parsing program, using the programming language Haskell. Natural language parsing has important applications in machine translation of sentences from one language into another.

    In the paper entitled Using Types to Parse Natural Language (In Proceedings of Glasgow Functional Programming Workshop, IFIP, Springer Verlag, 1995), Mark P. Jones, Paul Hudak and Shaumyan give a brief introduction to AUG:…»

    It seems that this approach is very promising, and I will certainly try it out!
    My first impression is that it is similar to the Categorial Functional Grammar approach I was taught many years ago, using a «slash notation» N/S also based on very simple elementary forms.

Σχολιάστε

Εισάγετε τα παρακάτω στοιχεία ή επιλέξτε ένα εικονίδιο για να συνδεθείτε:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s