Dataspace 3: It Came from the S-Expressions

It is an interesting article! However, regarding the Prolog-related statements in the article, I think a few clarifications, qualifications and corrections would improve it considerably.

For example, the article states:

"The Prolog data model – based on logical terms , which are very similar to SQL relations, [...]"

Prolog predicates can be compared to SQL relations. Prolog terms, though, are data structures that can be arbitrarily deeply nested and correspond more closely to Lisp's S-expressions, with the addition that Prolog also supports logical variables in terms. Due to this feature, Prolog terms can be more flexibly constructed than data structures in languages that lack logical variables. As one consequence, more Prolog predicates are naturally tail recursive than corresponding Lisp functions. For example, the predicate append/3 is naturally tail recursive in Prolog, but the corresponding function is not naturally tail recursive in Lisp.

Here is another quote from the article:

"For one thing, a Prolog term looks like a C function call [...] but that syntax is rather irregular."

A Prolog term is completely regular, defined inductively from three basic cases: variables, atomic terms, and compound terms. Maybe the article means predicate calls? Yet, these are also completely regular, because each goal is, syntactically, also a valid Prolog term.

Regarding Prolog implementations, the article states:

"Traditionally, Prolog systems tend to be compilers (for speed) and internally don’t use linked lists to store data. The architecture generally derives from a 1983 specification, the Warren Abstract Machine, which was intended for raw speed. Unfortunately, the WAM has hardcoded in some annoying limitations."

The WAM is definitely a popular option for implementing Prolog, yet there are several other architectures that are also used with considerable success. For example, SWI-Prolog - which is also mentioned in the article - is not based on the WAM, but on the ZIP.

Further, the article states:

"Note that – just as we can’t express (a b c . d) in an array, we also can’t express ‘likes (John . @X’) in standard Prolog term form. There is no syntax for it, because there’s no semantic model for it – because the Prolog term data model comes from formal logic, not from S-expressions. And because the formal logic community existed centuries to decades before Lisp, nobody in that community quite got around to thinking that ‘capturing the remainder of an expression in a logical variable might be useful’."

Yet, "capturing the remainder of an expression in a logical variable" is possible in Prolog. In fact, the ability to write down and reason about so-called partially instantiated data structures is one of the defining characteristics of logic programming languages such as Prolog, and an immediate consequence of their using logical variables as in formal logic.

For example, we can write:

    [a,b,c|Ls]

In canonical form, this is the Prolog term:

    '.'(a,'.'(b,'.'(c,Ls)))

This is a compound term of the form '.'(A,B), i.e., a term with functor '.' and two arguments, whose second argument has the same shape as the primary term, and whose innermost compound term is '.'(c, Ls), where Ls is a Prolog variable. This is completely analogous to Lisp's S-expressions, with the exception of the logical variable Ls that denotes the remainder, if any, which cannot be expressed in Lisp in this generality.

It is unclear what is meant with 'likes(John . @X)' in the article; however, I consider it reasonable to assume that it means the perfectly admissible Prolog term likes(john, X), where X is a variable.

Regarding the statement:

"But the formal logic community made a bit of a huge oversight when it assumed that ‘higher order logic’ meant higher order semantics rather than higher order syntax."

Personally, I find that having a higher-order syntax without associated semantics would leave something to be desired. Is there an advantage to being able to write down a higher-order term without defining what that means?

Plain Prolog does provide several higher-order mechanisms, such as the meta-predicates functor/3 and (=..)/2, all-solution predicates like setof/3 and findall/3, and also the call/N family predicates for calling arbitrary goals dynamically. Using these mechanisms, you can dynamically inspect and construct terms:

    ?- functor(f(a,b), Functor, Arity).
    Functor = f,
    Arity = 2.
    
    ?- functor(Term, f, 2).
    Term = f(_3934, _3936).

In this way, you can implement additional higher-order constructs within Prolog.

I feel like Cyc was left out of his list of lisp representations of universal quantification (prologgy lisps).

They did several interesting things, going way back to the 90s. I'm probably going to grossly misrepresent the idea, but they have a way to structure and represent knowledge (an ontology) as an atomic frame, a way to represent relations between frames, a way to reason about it (eg check that assertions and relations are consistent), and then--brute force by hand--wrote thousands of common sense meatspace frames. The idea was a lispy prolog that came with a database of things a five year old human might know about.

http://opencyc.org

https://en.wikipedia.org/wiki/Cyc

This belongs to a series of blog posts [0] by Nate Cull. He subtitled it: "An attempt at rethinking computation. Periodically updated." A refreshing read.

[0] http://natecull.org/wordpress/dataspace/

If the ideas of this series of posts interests you, I think you may also find tuple spaces interesting.

https://en.wikipedia.org/wiki/Tuple_space