Hacker News Reader

falsissimeon The Simplicity of Prolog

Yes, this technique has been used by several implementations. And any application developer can use `asserta/1` for the very same purpose. Just one rule, that is certainly much more appealing.

falsissimeon The Simplicity of Prolog

> The user has no realistic way of implementing the `call/N` builtin themselves.

Not sure what you mean by realistic, but `call/1` can be implemented by having one simple rule for each existing predicate (now for the sake of the argument ignoring control constructs, which require somewhat more complex processing first) plus a rule for uninstantiated variables and one for an inexistant predicate. And `call/N, N > 1` can now be defined based on it.

falsissimeon Language models can explain neurons in language models

You lost this bet: Write append3/4 which appends three lists to a fourth, such that append3(Xs,Ys,[e],[]) terminates.

falsissimeon Why split lexing and parsing into two separate phases?

For many languages, the lexical part requires an "eager consumer rule"/"maximal munch" in addition to the actual grammar, whereas the remaining grammar does not.

falsissimeon Why did Prolog lose steam? (2010)

> ... all the activity of the early years of logic programming has died out, ...

Of course, now there is activity of the current years! What else could we have now? If you look back, there was not only progress but also quite a lot of regress. Like, dif/2 in Prolog 0, then to stay submerged for so long, resurfacing in Prolog II and Mu etc. Errors in Prolog I, then abolished in DEC10 at the expense of incorrectness, only to resurface later on, but still not entirely recovered...

falsissimeon Why did Prolog lose steam? (2010)

> Which system are you referring to?

SICStus. The best for catching resource errors (that is with catch/3) and continues thereafter happily. SWI does catch many situations, but as you observe it is much less reliable. SICStus is also best for timeouts. I have not tested SWI recently, only noted that the compatibility library(timeout) has been updated. The call_with_inference_limit/3 might be interesting. The others you mention have just bad interfaces. But what both systems lack is a reproducible notion of time on a lower level. Walltime is not useful, as it is load dependent, CPU-time depends on TLBs, caches and all that. Think of number of (completed) CPU-instructions. PAPI-wise. While there is some JIT-tering in both systems this is still the best. Anyway, I start daydreaming...

> they're most of the time a sign of programming error

Often yes, but then you need to explain such errors which incurs a lot of attempts to execute fragments of the looping program. Like with a failure-slice https://stackoverflow.com/tags/failure-slice

And then, there is another kind of programs that effectively do not terminate but are still useful. Those that try to find counterexamples (posh expression for bugs).

> Oh, is that lisp-y style?

Recursive functions a la (cons x (recursive ...)) are not tail recursive (or at least have been not in the 1970s), whereas the corresponding code in Prolog is. So they were often transformed with an auxiliary argument that collected all conses in the wrong direction and were nreverse-d thereafter since (ideally) noone else referred to that list. I believe this has been solved in the meantime.

And yes, with a step-by-step tracer, this style makes things easier to watch. OTOH, you could use purer methods for debugging (for the pure part of your programs). At least, when you are into constraints, the tracers are of no use any longer and you have to switch.

falsissimeon Why did Prolog lose steam? (2010)

> But there's no formal concept of "interface" in Prolog

Any predicate you write for someone else has an interface. Someone else includes you in a couple of weeks. All predicates that are not truly auxiliary ones which are more like basic blocks of command oriented programming languages - COPLs.

> instantiations errors are a possible issue at every level of a program

That is not the worst that can happen. Nor is non-termination the worst. The worst is if an unexpected failure or success happens that looks like a legitimate answer. However, for many, non-termination is seen as being worse than such real errors. The reason is that there are only very few Prolog systems that reliably catch resource errors or have reliable timeouts. Well, to be true, there is one system. And the others most often abort.

> (hence my practice of documenting the structure of inputs and outputs carefully).

> I really don't like the ad-hoc "type" checking in Prolog (as in integer/1 etc).

integer/1 is one of the orignal sins of DEC10 which remplaced the errors of Prolog I by silent failure. And everybody then followed suit. Mindlessly. There is library(si) that offers integer_si/1 to make things much cleaner.

As for your remarks on type systems for Prolog, one feature they do not provide is a dynamic conversion between regular Prolog and the typed part. There was an attempt some time ago but unfortunately the individual left for FP.

> Who needs type safety anyway?

It seems there are two different objectives: type safety and instantiation safety. Both are often confounded.

> SWI-Prolog's Picat-style matching with the "=>" operator that is an > alternative to ":-".

This approach does not distinguish between instantiation and type errors. Take the sum_list/2 from https://www.swi-prolog.org/pldoc/man?section=ssu

   ?- sum_list(1, N).
      existence_error(matching_rule, sum_list(1, 0, _A)).
   ?- sum_list(L, N).
      existence_error(matching_rule, sum_list(_A, 0, _B)).

And then when adding the suggested catchall rule, both fail. Both. This throws us back by almost half a century. So now DEC10-style errors get into the 21st century. Prolog 0 and Prolog I were better.

   ?- sum_list(1, N).
      false.
   ?- sum_list(L, N).
      false, unexpected.

> "steadfastness", that you also mentioned, and that is a new term for me

Since 1987-09-29 in common use, see the Prolog Digest of that date, posting by Richard O'Keefe. Here is my definition: an argument Ai is steadfast w.r.t. a goal g(A1,..Ai,..AN), when executing this goal is equivalent (complete operationally) to, g(A1,..CAi,..AN), CAi = Ai with CAi a fresh new variable. And more generally an argument Ai is steadfast, if this property holds for all goals.

A good example of a steadfast argument is the second argument of append/3. You can replace any goal append(Xs, Ys, Zs) by append(Xs, CYs, Zs), CYs = Ys without observable effect (except efficiency, resource consumption and the like). But even non-termination is preserved! Another one is the 3rd argument of phrase/3.

Or take your run_length_encoding/2/3, where the second argument is steadfast. You (presumably on purpose) accumulated in the second argument all the elements only to reverse them finally in a highly lispeling manner. At least no destructive nreverse.

falsissimeon Why did Prolog lose steam? (2010)

(It seems one needs to go into a post directly to be able to reply more rapidly. The delay seems to be reserved for the thread-mode.)

Before sending an e-mail, check https://www.softwarepreservation.org/projects/prolog/ there are so many original sources now online that help to reconsider some perceptions. In particular, the Prolog I manual is there, but in a very bad shape (bad scan from a used up chain printer, probably a 3203, all caps, no accents ...).

falsissimeon Why did Prolog lose steam? (2010)

Explicit checking of the appropriate instantiations is something for more or less official interfaces, not for every internal predicate. For those official checking via must_be/2, can_be/2 and the library(si) (all in Scryer) is often all you need. (The SWI-version conflates must_be/2 and can_be/2).

But you could save your beloved cut with minimal effort by using dif_si/2 (voir https://stackoverflow.com/a/20238931/772868) just before the cut. In this manner you would get instantiation errors for exactly the cases you cannot handle.

falsissimeon Why did Prolog lose steam? (2010)

(It takes some time here, before the reply link appears)

While I do not know what you were thinking either, I do know that you insisted on a mode +,- and thus refrained from using the most general query to test your program just in case. Prolog would have shown you the problem right in the first answer!

    ?- run_length_encoding(L,E).
       L = [], E = []-0, unexpected
    ;  ... .

While the most general query often leads to an unfair enumeration of answers/solutions, it is still a useful and effortless way to test a program, just in case.

falsissimeon Why did Prolog lose steam? (2010)

Support of as many modes as possible is an aim that is often too ambitious. Instead, unsupported modes should be indicated with an instantiation error or (much rarer) an uninstantiation_error. In this manner the logic remains intact as long as no error occurs and the program does not loop. And yes, this may come at the expense of its usefulness, think of (is)/2.

YeGoblynQueenne omitted what the mode +,- actually means. And the program does not check it. Does it mean that the first argument must be ground or is it OK, to leave some variables inside? Think of `[a,f(X),b]`. Also the - has sometimes the meaning of being descriptive (that is a completely steadfast argument) or prescriptive (meaning that the program may be incorrect if the argument is not an unaliased variable). Would errors be used for the unintended cases things would be much clearer.

falsissimeon Why did Prolog lose steam? (2010)

For one, the second argument should be (upon success at least) a list. But in your program it isn't a list for `[]`.

falsissimeon Why did Prolog lose steam? (2010)

There is a minor impurity in this code: `N = 1+1, rle([a,a],[[a,N]]).` succeeds, yet `rle([a,a],[[a,N]]), N = 1+1` fails. Add `:- op(150, fx, #).` and use it like `#CountPlus1 #= #Count+1` etc.

falsissimeon Introduction to Datalog

> but the burning problem that datalog does fix is Prolog's semi-decidability, or in other words, its tendency to enter infinite recursions.

Prolog's built-in search is not semidecidable. https://en.wikipedia.org/wiki/Decidability_(logic)#Semidecid...

As you observe, Prolog gets stuck in left-recursions. But iterative deepening for Prolog is semidecidable (among other fair methods). This indeed is restricted to the pure, monotonic subset of (full) Prolog together with all pure, monotonic extensions.

falsissimeon Scryer Prolog

Any progress for Quantum conformity wise? It's doc reads is a full ISO Prolog implementation https://quantumprolog.sgml.io/docs/langreference.html

falsissimeon A Prolog assisted search for new simple Lie algebras

op(150, fx, #) would make the SWI code more readable.

falsissimeon Tar.pl – A tar creator and extractor in ~130 lines of Prolog

The 1978 DEC10 Prolog user guide mentions PROG.PL as an example of a Prolog file with an extension. See 3.2 in https://userweb.fct.unl.pt/~lmp/publications/online-papers/U...

Maybe the 1975 Prolog I manual has more to say...

falsissimeon Prolog at Work

Consider to set the flag to "error" to see if there are any cases where infinite terms would be created.

falsissimeon Prolog at Work

> the occurs check is crucial for the performance of the algorithm (because without it unification can go on forever, whereas with the occurs check unification will terminate and find an mgu if one exists).

Many current systems perform rational tree unification. Like SICStus, SWI by default, Scryer by default etc. This claim that unification going on forever only holds for rather the minority of systems today.

falsissimeon Prolog at Work

Just to note one error in I.2.1:

> ... whereas unification without the occur check is linear on the size of the smallest of the terms being unified.

This claim is incorrect, it goes far beyond what is possible. To see its incorrectness consider the unification problem X = Y. And just for illustrative purposes, think of them both as being very big and evolved. Now, consider a related unification problem Z-Z = X-Y with Z just a variable. According to above claim, the cost would be now independent of X and Y which cannot be.

falsissimeon Prolog at Work

> [3] What does the DEC10 Prolog manual say about the occurs check?

See I.2.1. Occur Check of https://userweb.fct.unl.pt/~lmp/publications/online-papers/D...

A recent related discussion: https://stackoverflow.com/questions/65600226/what-occurs-che...

In general, we do agree on the observation that Prolog profits from both the theoretical and the practical side. But still even today I have the impression that the highly theoretically leaning side does not appreciate the fundamental contribution errors have on ensuring correctness properties. At least this was my impression of November 10th in Paris.

Just one personal recollection (from memory) which probably also influences my view on the Kowalski-Colmerauer relation. At a META 90 tutorial/talk about meta interpreters, Sterling attributed the origin of meta interpreters to Warren and the DEC10 manual. Kowalski responded (publicly during the talk) that this was well known to Colmerauer, well before Warren ever got into Prolog.

As to the lady you are referring to she is his widow, a linguist.

falsissimeon Prolog at Work

> If Colmerauer had his way, Prolog would be a quick and dirty programming language fit to replace javascript or C.

No. There are far too many such allusions in this post that it is difficult to dismantle them all. So I will stick to this one.

Note that Prolog was born exactly in the very moment when Colmerauer understood how to encode grammars. How much is this quick and dirty? Since Robinson there was some unease about how to encode grammars as this (so far) only lead to extremely inefficient proof procedures. (Roughly, any partition of a text had to be analyzed, most of which were finally discarded) Prior to this moment of understanding in the summer of 1972, as is best illustrated by Philippe Roussel's thesis of May 1972, it was not clear which strategy to use.

Quick and dirty features were rather introduced when Prolog was taken from Marseille to Edinburgh. In particular,

1mo, the quite clean error mechanism was replaced by just silent failure. `T =.. L` just failed. Thereby disregarding the observation of Battani and Meloni 1973 that built-in predicates have three possible outcomes: success, failure, and error.

2do, characters were replaced by character codes something any self respecting compiler writer would have never done.

But then, all in all, DEC10 Prolog had so many improvements that helped to spread Prolog.

Errors are absolutely essential to ensure the correctness of pure Prolog programs. It took some more decades to recover from these quick and dirty setbacks.

There is only one single such quick and dirty issue in Prolog I and that is the omission of the occurs check which was present with a flag in Prolog 0 (the first version written in Algol-W). In particular the lame excuse of this omission was started with the Prolog I manual of 1975. It was then mindlessly reiterated time and again to DEC10's and many other systems' manuals. At least, Colmerauer developed thereafter the notion of rational trees present since Prolog II.

It is only now that systems slowly recover from this offering an optional occurs check.

https://en.wikipedia.org/wiki/Occurs_check#Sound_Unification

falsissimeon Reasons why Fortran is still used (2021)

The first Prolog was written in Algol-W. The second one, which was called Prolog I was written in Fortran. See comments for more: https://stackoverflow.com/a/4478969

falsissimeon The Mercury functional programming language

And third, it produces redundant solutions for ground queries.

falsissimeon The Power of Prolog [video]

In fact, you can do this with Prolog already, however, you have restrict yourself to the pure monotonic subset. Many parts of Prolog the do not fit can be replaced by purer counterparts. See library(si), library(reif), library(clpz) for such attempts.

falsissimeon Books I recommend to my software engineering students

You probably meant The Craft of Prolog by Richard O'Keefe. The preface of the Art of Prolog is about David H. D. Warren's recollections of his first encounters with Prolog.

falsissimeon The Power of Prolog

https://www.metalevel.at/prolog/business

which is a chapter of the book

falsissimeon The Power of Prolog

    :- use_module(library(clpz)).

for its successor which runs with SICStus and Scryer.

falsissimeon The Power of Prolog

From the interface (mostly yes, that, is apart from the impure extensions added later, and that chars are used and not codes) it is the same. But from the implementation behind it´s different. In particular from the space requirements. A text of n characters requires 3 * 8 * n bytes in SWI, but n + 2 * 8 bytes in Scryer. So there is a factor 24 in space requirements (on 64bit).

Also, there is now ample room for input that SWI once almost offered.

falsissimeon The Power of Prolog

See https://github.com/mthom/scryer-prolog/issues/251