Aggregation

Help!
21

LOL, I had decided against sending that message as I thought it might come off as unnecessarily caustic and then saw your response this morning. Apparently my 3 year old had other ideas.

That’s an interesting point about picat.I didn’t know about them adopting a context sensitive reader. I’ll have to read up. From bad experiences with lisp reader black-magic, I’d tend to agree with you.

Also I think they idea of adding warnings is a good one and relatively easy. And indeed, the Logtalk linter has caught a number of mistakes in my code already.

I wouldn’t necessarily throw the baby out with the bathwater though. For almost all uses of variables in FOL, HOL or elsewhere, what is required is merely lexical scoping. This is true of all the forms discussed here, and existential and universal quantification in logic. This doesn’t mean having a context sensitive reader, just one that can deal with binding forms. I find the argument given by Qi persuasive:

A careful examination of the examples discussed above shows that even though the application domains are quite different, there is a common part to what needs to be treated with regard to binding in both cases. The important aspects of binding can in fact be uniformly captured by using the terms of the λ-calculus as a representational mechanism. For example, the concept of the scope of a binding is explicitly reflected in the structure of a λ-abstraction. Similarly, the recognition of the irrelevance of names for bound variables and the preservation of their scopes during substitution are manifest though the usual λ-conversion rules. Thus, the representation of formal objects relevant to different contexts can be accomplished by using λ-abstractions to capture the underlying binding structures and using constructors like in firstorder abstract syntax representations to encode whatever context specific semantics is relevant to the analysis. – Xiaochu Qi, “An Implementation of the Language Lambda Prolog Organized around Higher-Order Pattern Unification”

Of course this, as you’re well aware, is a can of worms, and you’re undoubtably correct that without a clear demonstration of the lack of negative consequences on existing libraries and performance as well as implementation complexity, it makes sense to stick to warnings.

The first version of Teyjus had an enormously complex extension to the WAM in order to make things work out. However, with Qi’s thesis, they restructured Teyjus and limited to the pattern fragment of higher order unification and this simplified things tremendously. The pattern fragment is deterministic and not too difficult to implement.

It seems now in Teyjus 2, the extensions to the WAM are limited to representation of binding in terms (using de Bruijn indexing to keep comparison/unification fast and structural), and a co-routining approach to deferral of unification when things fall outside of the pattern framgment, and a routine for beta-reduction. Types are no longer relevant at runtime in Teyjus 2 except at constants, which is not important for a normal prolog.

Since many prologs implement some extension to unification (for CLP for instance) and already have co-routining, the differences don’t appear that major anymore. I intend to make a bit of an experiment of it and report back.

1 Like
22

Thanks for the pointers. I think I see it a bit different. It is interesting to see that it seems you can get proper semantics for higher order expressions with sharing variables (if I understand you correctly).

IMO though, while higher order programming fits well in Prolog, notably the maplist and aggregation family, lambda expressions stress the syntax too much. Despite all the effort some years ago that resulted in Ulrich’s library(lambda) and Paulo’s library(yall), I find most usage confusing. Only really simple swapping of arguments seems justified to me. In slightly more complicated cases a helper predicate is a cleaner solution and allows for naming the thing you are doing so you don’t need to comment it :slight_smile:

Part of the problem is that there doesn’t seem to be a good syntactical and semantical fit. I guess one ideally writes something like below, but that doesn’t really work out :frowning:

maplist({(X,Y) :- ...}, In, Out)

This typically also holds for setof/3 and existential qualification: a helper that simply omits the variables often leads to an easier to understand program.

Given that context I think warning on probably wrong variable sharing is the way to go. The effectivity of the inverse (singletons) makes such warnings promising.

Note that even when correct, I typically avoid relying on variable scoping using {…} in our familiar languages. It is just too easy to get it wrong (for example renaming the inner variable and forgetting one instance, misinterpreting the code later by not spotting the scope, etc.)

2 Likes
23

I cannot comment on the underlying theory, only on the practical implications that a certain programming style has, and the features of the languages I have used so far, in comparison to each other. I will try to keep it short so if something is not clear I can elaborate. If I mention a particular language, this means I have actually had to write non-trivial code using that language.

Anonymous lambdas, as implemented in mainstream procedural languages of today (Python, Java, C++) are there to solve particular problems of the language. In Prolog, swapping the position of arguments is a real thing. For example, if you need to use arg/3 to get the arguments of a term at positions coming from a list:

?- T = t(a, b, c, d, e),
   maplist([Pos, Val]>>arg(Pos, T, Val), [1, 3, 5], Vals).
T = t(a, b, c, d, e),
Vals = [a, c, e].

You couldn’t do this without a lambda or a helper predicate, and the usefulness of a helper predicate in this particular case is relatively low. Especially because many built-in predicates are true relations, it is relatively common that in one case you’d like to bind one particular argument, and in another case another argument.

I toyed with the concept of “literate programming” (as first described by Donald Knuth). My personal verdict on the topic is: for writing code, literate programming is only good as a weapon against deficiencies of the language and the tooling around it. (This, btw, is in strong contrast to using code to obtain results: there, literate programming really shines; the concept of a “notebook” is by now somewhat mainstream).

SWI-Prolog allows a programming style that supports and encourages the programmer in truly writing self-documenting code. Many people have tried it with many languages; there is a lot of text written on the subject; still, for all kinds of practical reasons, self-documenting code is too difficult with mainstream languages.

Helper predicates are one example of self-documenting code encouraged by the language Prolog and the SWI-Prolog implementation.

I hope I am not just saying things that everyone already knows.

24

In the case of Python in particular, I still prefer to define a function for any non-trivial expression used inside a list comprehension. But Python is by now very widely used and I have already noticed that “best practices” have started diverging. In other words, depending on who you write code with, people have different opinions on what is “good” and what is “not so good”. From what I have seen, C++ has been there for decades. Even differences between compilers have strong influence on “coding style”.

25

The rational for the syntax of Logtalk lambda expressions, also implemented by library(yall), is explained at e.g. Lambda expressions in Logtalk - Logtalk The blog post also explains why the syntax diverged from library(lambda) syntax.

1 Like
26

I know all that, but it still doesn’t read naturally. Same typically holds for good old
existential variable notation of setof/3 and notably the aggregate family. That is a pity. I think most of Prolog’s syntax reads pretty naturally. Of course that could be that I’m exposed to it for too long :slight_smile: Still, I think there seems to be things that never feel natural. They are things that fit as good as possible in the language (at least, what the language designers thought was the best fit at the time), but keep being hard to read and/or write. Take

    void (*)(int) signal(int signum, void (*handler)(int));

After over 30 years of C programming I can write this without looking up an example (hope I got it right). but natural … no :frowning:

27

Yes, but helper predicates make it much easier to grasp, for me personally.

Last week I had a really simple question that I thought is a one-liner with bagof/3; and, as usual, I started negotiating with bagof/3 to give me what I want :slight_smile:

The simplified version of my question: give me groups of substrings, by length. In other words, if I had the string “foo”, I would have liked to see:

1 - "f", "o", "o"
2 - "fo", "oo"
3 - "foo"

So, I thought, I would use sub_atom/5 and bagof/3. Skipping the part where I negotiated with bagof/3, the one-liner turned out to be:

?- bagof(X, Before^After^( sub_atom(foo, Before, Length, After, X), Length > 0 ), R).

The trial-and-error along the way is the interesting part but the journey is personal. This means, if someone didn’t know this is the exact way to do it from the start, then seeing my mistakes won’t help them avoid similar mistakes in the future. The useful number is: it took me close to 30 minutes :’-(

What if I had done “the right thing” ™ from the start?

atom_proper_subatom_length(Atom, Subatom, Length) :-
    sub_atom(Atom, _Before, Length, _After, Subatom),
    Length > 0.

?- bagof(X, atom_proper_subatom_length(foo, X, Length), R).

The correct way to do this with library(yall) turned out to be:

?- bagof(Subatom, {Subatom,Length}/( sub_atom(foo, _, Length, _, Subatom), Length > 0 ), R).

… which is actually pretty neat. The only thing that is missing is the presense of the string “atom_proper_subatom_length” in the code.

2 Likes
28

Syntax error. :wink:

BTW: https://cdecl.org/ … except it can’t handle int *signal(int signum, void (*handler)(int));