What is meant by "meta-level" in logic programming?

General
1

A reviewer of one of my papers recently commented the following:

In logic it can be important to distinguish meta-level inference from inference involving second-order formulae. In logic programming and Prolog in particular the differences are much less apparent.

I have encountered this “meta-level” term a few times already and I’m scratching my head about what it means. My best guess is that it refers to Prolog’s lack of distinction between function and predicate symbols.

To clarify, in First Order Logic (FOL) a language includes disjoint sets of function and predicate symbols. So in FOL S(t_1, ..., t_n) where S is a symbol, can either be an atomic formula, if S is a predicate symbol, or a term, if S is a function symbol but not both!

In Prolog on the other hand there is no distinction between function and predicate symbols, and in fact there is no such thing as “functions”. So in S(t_1, ..., t_n) the symbol S/n is a “functor”, S(t_1, ..., t_n) is always called a “term” (or, confusingly, “literal”) and there may or may not be a “predicate” S/n (where a predicate is a set of clauses with S/n in the head).

In general, Prolog syntax is much more permissive than FOL and the result, as far as I understand it is that Prolog is not a first-order language despite it always been described as one. It’s really more like a “1.5-order language”.

In any case, it seems to me that “meta-level” really refers to this permissiveness of Prolog, compared to FOL, that makes it possible to write logic programs (i.e. “predicates”) that take other logic programs as arguments. For example, this permissiveness is the reason we can write meta-interpreters in Prolog, or other “meta-predicates”.

What does everyone think?

1 Like
2

Hard to say, Stassa. Possibly the best thing could be asking the reviewer himself/herself what he/she meant with “meta-level” :slight_smile: (I wouldn’t a priori exclude that he/she had nothing precise in mind…). My recollections of Logic are somewhat foggy and unclear, but for example I would say that Second Order Logic itself (as the name seems to suggest) can be considered a “meta-level” when compared to the language of First Order Logic…but maybe the reviewer had something else in mind.
The second thing you say (about Prolog’s permissive syntax) applies to functional languages as well, I think. This kind of approach (using functions as arguments of other functions) is considered a historical “trademark” of functional programming, as far as I know (the use of so-called “higher-order functions”)

3

I can’t easily ask the reviewer, because I was blinded to their name. If they see this post they might want to approach me though. I don’t bite and the review was very useful :slight_smile:

I think what the reviewer was alluding to with regards to the difference between “meta-level” and second-order logic is that in second order logic quantifiers range over predicate and function symbols. The effect is similar in practice with Prolog’s permissive syntax (you get variables that can take arbitrary values) but the formalisation is different.

Yeah, I remember seeing some conversations between Richard O’ Keefe and others in the old SWI-Prolog mailing list about higher-order programming in Prolog. I think Richard O’ Keefe’s argument was that higher-order programming was the way to go in logic programming.

1 Like
4

Ah ok. Sure…it was a serious academic peer-to-peer procedure or something along those lines

5

Well, there’s λProlog.

But if you treat call/1, call/2, etc. as if additional facts are defined in your program:

call(foo) :- foo.
call(foo, X) :- foo(X).
call(foo, X, Y) :- foo(X, Y).
call(bar) :-
  ...

then these facts can in principle be derived from analyzing your program, so we’re back to a first-order language.

Yes, but the trick of defining call/1 by adding extra statements provides a conversion between function and predicate symbols.
(The identical appearance of terms and predicates seems to confuse most beginners, so there might be a better way of doing things than the standard Prolog way – for example, adding a “thunk” to Prolog and a term_to_thunk/2 predicate.)

1 Like
6

Now, see, that’s exactly what I mean: in your example foo is both an argument to a literal and the symbol of another literal, in the same clause. FOL syntax does not allow you to do that. Under FOL syntax rules, only terms (i.e variables, constants or terms with function symbols, inductively defined) can be arguments to literals and only predicate symbols can be used as symbols of literals.

call/n is the quintessential “meta-predicate” and that makes sense since it’s basically a kind of … meta interpreter?

I don’t know about the “thunk” thing but it’s true that the way Prolog terminology is taught to beginners is confusing. In my case, I remember distinctly being extremely confused about “facts and rules” on the one hand and “definite clauses” on the other, since I was taught both terminologies at the same time. I remember thinking “so rules are definite clauses, then what are facts?”. I only finally cottoned on when I read Pereira and Shieber’s “Prolog for Natural Language Analysis” which takes some time to formally define the terminology around definite clauses (because it has to explain Definite Clause Grammars):

https://www.semanticscholar.org/paper/Prolog-and-Natural-Language-Analysis-Pereira-Shieber/547d483ed1e80066693af561f63daa30ffa8e9fa

It’s possible the same information was in the many other Prolog textbooks I read but I still didn’t get it. Maybe it’s just me being particularly thick but after having seen (as a TA) my share of university students really struggle with Prolog and give up I’m convinced that it’s really hard to teach Prolog and nobody quite gets it right.

7

Yes, but call/n can be defined as a first-order thing (just add a corresponding call/n clause for every predicate in the program), so I don’t think of it as something special. Others might disagree.

“Thunk” is, I suppose an old-fashioned word for what is now called “closure” (although the definition of “closure” is somewhat variable, it seems) – basically, a pointer to code plus some environment. See also delimited continuations, which I don’t fully understand.

So, it might be useful to have something like term_closure/2 or term_callable/2 that maps between a term and something that can be called. Whether this would be more or less confusing than call/1, call/2, etc., I don’t know.

If you have the following code:

number_word(0, zero).
number_word(1, one).
number_word(2, two).
number_word(I, big) :- I > 2.

then there’s a predicate number_word/2 that has 4 clauses, and all of the clauses happen to have the syntax of a term (see: homoiconicity). There’s no intrinsic reason why this to be true – Picat, for example, does not represent its predicates in a form that is directly representable as terms. (Lisp is the canonical example of homoiconicity; but it has the opposite default from Prolog: everything is called unless specifically quoted (e.g., by the QUOTE special form)).

It’s convenient to have the same syntax for predicates and terms, for things like macro-expansion or program analysis (see clause/2) or for dynamically adding facts/rules (see assertz/1); but it also confuses beginners. (Does the similar thing in Lisp also confuse beginners?)

8

This is possible, but you’d have to do it in a rather clunky and non-general way, that reminds me of translating first-order relations to propositions. It goes like this:

call_foo:- foo.
call_foo(X):- foo(X).
call_foo(X,Y):- foo(X,Y).
% ... etc

A pre-processor could be used to automate the process, so you’d only need to define the names and arities of call_<symbol> predicates. Like I say, it’s clunky.

The way I understand homoiconicity in Prolog is that everything is a “term”, plus some punctuation. Formally, Prolog terms should be either Horn clauses or first order terms, but since there’s no distinction between function and predicate symbols, well, then, everything is a term. So everything can be an argument of everything else and that gives a certain freedom of expression you don’t find in FOL.

Prolog tosses FOL strictness out the window. The reason, I think, is the pragmatism and practicality that shines through the fundamental decisions in the language. E.g. having disjoint sets of function and predicate symbols would require some way to define those sets and that would just be a hassle and would get in the way of just writing programs to get things done. Mrs Colmerauer and Kowalski knew what they were doing!

I agree. I think I best understand Prolog syntax in the context of SLD-Resolution, which, in turn, I best understand in the context of a Prolog meta-intepreter, the vanilla kind. A vanilla Prolog meta-interpreter basically picks clauses apart literal-by-literal, but it can only do that if there is a matching clause head literal in the program database. When a clause is, er, beheaded, its body literals are placed on the meta-interpreter’s stack and the process continues recursively. So everything has to be the same data structure (a term) or things get very complicated.

Prolog’s syntax is what really makes it tick. If I ever find myself teaching Prolog to beginners I’ll start by teaching FOL syntax, then tear it down to replace it with Prolog syntax, then show them how to use that to define a vanilla meta-interpreter to understand SLD-Resolution. I wish someone had done that for me, it would have saved me years of confusion.

I don’t either. I also don’t think I understand closures in functional languages (only transitive closures). Neither do I know any LISP :slight_smile:

9

It’s hard for me to say much without reading the submission or knowing the context of the paper, but in my undergrad studying logic “meta” simply meant formalisms about logic itself, rather than statements “in” logic. Godel’s study of the principia was meta, as is some of Quine’s work.

So in this sense, a second-order predicate calculus (or formulae) have clear delineations between predication involving objects or relations between objects, and the formulation of statements of statements in logic (not a typo).

Prolog has predicates, which I wouldn’t really say is meta-logic, but meta-predicates reason about predicates, so I would say they are a form of meta-logic.

It’s been a decade since my undergrad though, so I may be mistaken.

10

call/1 is one of those things I never really got…maybe because I’ve never had the chance to see it “at work” in a single miniprogram in which it is meaningfully employed or in which it makes a difference to have a predicate like that. If anyone shares a fragment of code in which the use of call/1 or call/2 and related things “shines” it would be much appreciated :grinning:

11

I think that’s probably were “meta” comes from. You can certainly use Prolog’s higher-order facilities to reason about other predicate but “reasoning” is not the only thing that meta-predicates do, for example call/1 executes a program without analysing it.

13

You can certainly use Prolog’s higher-order facilities to reason about other predicate but “reasoning” is not the only thing that meta-predicates do, for example call/1 executes a program without analysing it.

That’s probably why they said the difference is less apparent in Prolog.

1 Like
16

call/1 is what makes Prolog homoiconic:

IMG_0028

This property is often summarized by saying that the language treats code as data. But leaning towards logic it means the language can treat formulas as terms. On first sight one might think this refers to clause/2 which doesn’t exist per se in FOL, but if we view “as” as going both ways, it also covers call/1, which also doesn’t exist per se in FOL.

Example use case for call/1:

:- dynamic memoized/2.
memo(X) :- memoized(X, Y), !, call(Y).
memo(X) :- call(X), !, assertz(memoized(X, true)).
memo(X) :- assertz(memoized(X, fail)), fail.

A very simplified tabling utility.

3 Likes
17

Thanx. Sure to get advice on logic from Johnny Rotten seems something of a paradox… :sweat_smile: but that is logic as well

18

I did not give any advice, nothing prescriptive like a logic driving license in my post. I just stated some material truth descriptively about Prolog, truth that is based on the correspondence between statements or beliefs and the actual state of affairs in the material world.

But of course we can never be sure, whether what we think and communicate via our rotten brain does really have such a correspondence. But the memo/1 predicate, although a toy example, seems to work quite well:

?- time(fib(32, X)).
% Zeit 3679 ms, GC 116 ms, Lips 5748167, Uhr 24.08.2024 11:44
X = 3524578.

?- time(fibm(32, X)).
% Zeit 1 ms, GC 0 ms, Lips 2948000, Uhr 24.08.2024 11:44
X = 3524578.

Mostlikely everybody and on most Prolog systems can veryify that the time complexity for fibonacci goes down from exponential to linear in terms of LIPS. Giving us the feeling of shared material world, even if the material is information processing. Thats the further source code:

fib(0, 1) :- !.
fib(1, 1) :- !.
fib(X, C) :- Y is X-1, fib(Y, A), 
   Z is Y-1, fib(Z, B), C is A+B.

fibm(0, 1) :- !.
fibm(1, 1) :- !.
fibm(X, C) :- Y is X-1, memo(fibm(Y, A)), 
   Z is Y-1, memo(fibm(Z, B)), C is A+B.

Still its up to everybody individually to draw some life changing lessons from it. I do not try to verbalize this part, otherwise I would end up writing business management summaries which do not have a single truth.

2 Likes
19

Thanks for the infos then

PS: Nevertheless I would find it a suitable and possibly attractive title for a playlist on Logic on YouTube “Logic Lessons from Johnny Rotten” :rofl: :rofl:

1 Like
20

You are getting those right here

1 Like
21

This is really nice code - except that X and Y are pointlessly abstracted, making everyone’s attempt at understanding, more difficult.

Example: G (meaning Goal) and B (meaning Boolean) would be far more meaningful, to aid understanding to everyone, than X and Y. G and B can of course be explained in code comments.

1 Like
22

There is also problem with that, since I used call/1 non-declarative. The realization of memo/1 makes heavy use of cut !/0 and the dynamic database, both things not available in FOL per se,

If you want a more declarative example of call/1 maybe try this,
using rotten™ cryptic variables X, Y, …:

or(X, _) :- X.
or(_, Y) :- Y.

Now there are the usual quizzes about this solution:

  • Quizz 1: Where is the call/1?
  • Quizz 2: Does it do the same as (;)/2 ?
2 Likes
23

Not only @Johnny_Rotten teaches Prolog, but now he even makes quizzes… :rofl: :rofl:
I didn’t know your career had had such a sharp twist in the last years, Johnny

BTW: I read in the documentation that writing a plain variable in the body of a clause is like using call/1

Not everything is yet completely clear to me though, but now I’m refreshing a little bit of FOL. Yesterday I bought me a seemingly nice book on the subject (by John Heil, First Order Logic, A Concise Introduction) to revise some things…working with pen and paper at the moment, not with calculators…