Lambda the Ultimate

> Loves is Exists ***

> I find this non-reflexive use of `is` a bit awkward. Why not "loves is a verb"?

Yes I agree it is awkward. "loves is a verb" is actually valid. For consistency it should be "a loves is a exists", but I found that awkward too, I think I was mistaken. In any case, defining verbs by subtyping other verbs gives more structure than defining all verbs by typing "verb".

> Regarding expressiveness, do you think you could demonstrate a few more challenging programs: shortest routes in a graph, traveling salesman, sorting a list?

My understanding is that those problems are not hard to express, they are hard to solve; and that that hardness is in the work the machine has to do to solve it, rather that in the work the programmer has to do to instruct the machine. There shouldn't be much difficulty in producing an ontology where we can speak of points in a 2D plane, distances, sequences of points,
lengths of those sequences, and comparisons of those lengths. Solving the problem should not be difficult either, but probably not very efficient. I would use one of the known algorithms for it, implemented as a set of rules, in much the same way as I would in prolog.

In any case the problems that complexity theory is interested in are not the problems Terms is devised to solve. Terms is directly concerned with expressivity. A way of measuring what I mean with expressivity would be the how much of the natural language description of a problem or situation can be directly and simply expressed in the language.
E.g., if you are taking the requirements for a software project, how much of those requirements can be directly and simply translated to code: how similar are the expressions of the requirements in natural language and in code.

In general, the logic languages I see have a common limit in their expressivity, given by the way they tend to represent natural verbs. They cannot quantify over them, or they need special variables, etc. This is the limit first established by Bertrand Russell with his paradox over Frege's work.

What I find is that if we limit the natural verbs that are represented as logical predicates to just the copular verbs, and represent all the rest as individuals, we gain a lot of expressivity. One manifestation of this would be how we can use verb or fact variables in Terms. I don't see how to do that in other systems.

> Can you express that john likes a particular traveling salesman problem?

We could, if we take into account the above; if we understand that the expression of "a particular traveling salesman problem" would not carry any solution to it.

You speak generally of expressiveness. I am curious what definition you are using for the word; I happen to favor Matthias Felleisen's definition of the word from On the Expressive Power of Programming Languages. This describes expressiveness on a lattice, as a partial order between languages, with regards to locality of expression.

I have worked with many logic languages, even implemented a few. They are not difficult - at least if you aren't too concerned with consistency (via termination guarantees), performance, or scalability. Of those I've studied, my recent favorites are probably Dyna (weighted logic), Dedalus (temporal logic), and Coq (constructive logic).

You mentioned of Terms language that "it can reason efficiently (polynomial time)". I am curious what you mean by this, e.g. in context of the traveling salesman problem.

About expressiveness, I think we mean the same. I have been reading the wikipedia article on "expressive power" and I concurr, and Matthias Felleisen's work is mentioned there as support.

About polynomial time, I mean that, given a knowledge base and a new sentence, the cost of integrating the new sentence depends very little on the size of the knowledge base, and directly on the amount of consecuences. Simply put, that I am using a RETE network for the ruleset and also an eficient structrure for querying the factset. I was not talking about solving any possible problem with any given efficiency. I only wanted to convey that Terms is based on a very simple logic, that can be solved efficiently, where "solved efficiently" means "we have a set of rules and a set of facts, and we want to add a new one and all the derived consecuences, and take the same time (given generous spatial resources) independently of the number of rules or facts".

In general, the logic languages I see have a common limit in their expressivity, given by the way they tend to represent natural verbs. They cannot quantify over them, or they need special variables, etc. This is the limit first established by Bertrand Russell with his paradox over Frege's work.

Do you mean the quantification of predicates or Russel's paradox?

With regards to quantification, can we not just use call or apply in Prolog. This comment comes from the Edinburgh Prolog parser circa 1984:

I have added the rule X(...) -> apply(X,[...]) for Alan Mycroft.

and here we we see this gives us quantification of predicates.

Now Russel's paradox is "Let w be the predicate: to be a predicate that cannot be predicated of itself. Can w be predicated of itself? From each answer the opposite follows." How can Terms manage to deal with this?

[edit: changed "How can any language manage" to "How can Terms manage"]

I mean quantification of predicates ;)

> With regards to quantification, can we not just use call or apply in Prolog.

That is, if I am not mistaken, second order, and what I propose is first order.

Concerning Russell's paradox, Terms does not deal with it, it is not possible to quantify over predicates in Terms. But only the copular verbs ("is of type", "is subtype of") are predicates in Terms. The facts provided in Terms, actually have the implicit form:

(subject verbx object) is a exists.

With this, we just have an operator "()" that allows us to provide a tuple as an individual, in an otherwise simple first order set theoretic sentence. And "subject", "verbx", and "object" are common individuals... The point is that the pattern in parenthesis matches very conveniently the natural sentences. With this scheme we loose the ability of quantifying over the copular verbs, but they are just 2 -or 3- so it doesn't feel so necessary.

> Can you define what you mean with expressive power in a bit more detail?

Naïvely: I would start with collecting a number of natural language patterns, such as "a _ is a _". I would try to provide a set with which to be able to specify clearly and without ambiguity the requirements of any software project. And then I would classify the expressivity of mechanical languages according to the subsets of those patterns that they adecuately cover.

> What things can you express in Terms that cannot be done in Prolog, where is Term's advantage?

Nothing; Terms might very easily be expressed in Prolog. The previous incarntion of Terms was implemented in CLIPS. Where Prolog would be first order logic, Terms would be a first order theory.

What I believe is the advantage of Terms is the way it relates to the natural language. It is a very simple structure, but it can be taken as a model for a sizeable part of the natural language.

> How would we write this in Terms?

That's a trycky one. There is in Terms the foundation for the implementation of this. This would involve operations over the database, such as getting -in a rule- the number of sentences matching a given pattern, or the person who has been the most times to the pole. I'm not sure about the complexity of this.