triska / the-power-of-prolog Goto Github PK

It would be great if you had a WFS/Tabling section.
It is a great book, thanks!

Hi Markus, I really liked the simple but effective mi_list3 from the acomip chapter. It's already in difference list form, so it can of course be rewritten using DCGs (and called with phrase/2 to force reduction to [] i.e. true):

mi_dcg_clause, [] --> [natnum(0)].
mi_dcg_clause, [natnum(X)] --> [natnum(s(X))].
mi_dcg_clause, [always_infinite] --> [always_infinite].

mi_dcg --> [].
mi_dcg --> mi_dcg_clause, mi_dcg.

Here's the original for reference:

mi_ldclause(natnum(0), Rest, Rest).
mi_ldclause(natnum(s(X)), [natnum(X)|Rest], Rest).
mi_ldclause(always_infinite, [always_infinite|Rest], Rest).

mi_list3([]).
mi_list3([G0|Gs0]) :- mi_ldclause(G0, Remaining, Gs0), mi_list3(Remaining).

I think this DCG form has several really nice features:

1. Pedagogically, I think it's a beautiful example of semicontext notation, which I'd found confusing.
2. The optional empty list semicontext (, []) in the first mi_dcg_clause conveniently corresponds to the optional :- true., and the --> corresponds to implication in the usual direction. And it makes it clear that the interpreter itself is just the reflexive transitive closure of some rewriting rules.
3. It's a nice basis for experimenting with meta-interpreters which make non-trivial use of DCG capabilities. For example, using seq and ... we can write some basic rules in a very readable way:

mi_dcg_clause, A, [X], B, C --> seq(A), [X], seq(B), [Y], seq(C), {X == Y}. % idempotence
mi_dcg_clause, [false] --> ..., [X], ..., [\+ Y], {X == Y}, ... . % contradiction
mi_dcg_clause, [false] --> ..., [\+ X], ..., [Y], {X == Y}, ... .
mi_dcg_clause, L, R --> seq(L), [true], seq(R). % everything absorbs true
mi_dcg_clause, [false] --> ..., [false, _], ... . % false absorbs everything
mi_dcg_clause, [false] --> ..., [_, false], ... .

I thought this might be a fun addition to the DCG or meta-interpreter chapters, or at least worth sharing!

Would be nice to have a chapter about that, with some examples maybe.
Maybe something similar to https://www.cs.ubc.ca/~poole/aibook/code/ailog/ailog2.html or so.

Take for example the second chapter "Facets of Prolog". In this chapter, there is the following code example:

list_length([], 0).
list_length([_|Ls], N) :-
        N #> 0,
        N #= N0 + 1,
        list_length(Ls, N0).

If the reader does not bother reading the "Integer Arithmetic" chapter first (which is linked in the previous sentence, but I assume newcomers would not follow those links right away), then the reader has no idea that they have to add :- use_module(library(clpfd)). with most distributions.

This lead people in the Prolog learning chatroom to not understand why a simple first Prolog example did not work, or even to conclude that the code exposed in The Power of Prolog is a not a standard dialect of Prolog.

There is a good example of blog engine using Prolog Markdown parser: https://github.com/oblivia-simplex/plog.

It will ease the reading/writing the book contents in the popular editors and GitHub itself. Also will allow to kill a lot of unrequired JavaScript - e.g. no need for jQuery, imho.

There's no link to the page about attributed variables (https://www.metalevel.at/prolog/attributedvariables) in the table of contents. I don't know whether that's an intentional omission, but the page is quite informative and it would be nice to have it listed.

You mention only Emacs-based development environment, but it makes sense to add also:

• SWISH
• The Prolog Development Tool
• Visual Studio Code Prolog

IMHO the VSC Prolog offers the best experience of all.

In logical purity section:

call(Goal) is pure iff Goal is pure

I think a useful chapter would be a getting started tutorial.

Start with a working program that does something, using have a dozen predicates with two clauses each.
p1 :- ....
p2 :- ...
p3 :- ...
...
p6 :-...

Exercises, get used to the syntax errors in your toplevel:

• On line p2, put a % to comment it out, consult, what happens.
  -- On line p2, put a # python comment in error, what happens.
  -- repeat the above after the first clause of a predicate, before the second clause.
  -- replace a :- with a :.

Next exercise: repeat with a DCG example.

Show how to use some debugging features of scryer.

Show how to put a testcase in the file, so when you consult, you can easily run the example.

Next exercise:

A few examples of predicates, like integer, -> , dif, etc, that the reader might want to use later.

We can do this by introducing two additional arguments that let us limit the number of rule applications to the given list's length: (https://www.metalevel.at/prolog/dcg)

As a reader, it’s not clear to me why there are two arguments, or what’s up with the sharing between LS1 in the left/right descents.

I suspect there is one or two intermediate steps to arrive at that solution, that you are able to leap straight past thanks to running across the problem many times before. For a newcomer, though, it leaves a mystery.

If you could elaborate on how this works within the chapter, that would be very helpful!

When I try to follow the reversal example from the DCG chapter, the example query loops on my system. More generally, the query phrase(reversal([a], Ls) loops under either scryer or swipl using the following file.

%% reversal.pl
%% :- use_module(library(dcg/basics)). %% For swipl
%% :- use_module(library(dcgs)). %% For scryer

reversal([]) --> [].
reversal([L|Ls]) --> reversal([Ls]), [L].

Can you verify that your system actually produces the below answer from the book's sample query? If so, can you imagine what I might be doing wrong?

?- phrase(reversal("abcd"), Ls).
   Ls = "dcba".

I am currently using the following versions:

$ swipl --version
SWI-Prolog version 8.4.2 for x86_64-darwin
$  scryer-prolog --version
"v0.9.0-63-gc490d818"

https://github.com/triska/the-power-of-prolog/blob/master/prolog/concepts.html

hailstone(N0, N) :-
    N0 mod 2 #= 0,
    N1 #= N0 // 2,
    hailstone(N1, N).

Should be N1 #= N0 / 2,

The section on integer arithmetic and constraint programming at https://www.metalevel.at/prolog/clpz explains that the list_length/2 predicate does not terminate when asked to find a list that has a specified length.

?- list_length(Ls, 3), false.
nontermination

"It takes only a single additional goal to make this query terminate. This is left as an exercise."

I have struggled to find what this single additional goal is. I have tried days of reading popular texts on prolog, googling and even asking on stackexchange.

I would love an answer or a link to an answer.

The server appears to start, but when I navigate to localhost:6012/prolog on my browser it can't seem to find seq/3.

$ scryer-prolog -g "server(6012)" server.pl 
waiting for connections...
handling client '127.0.0.1:52410'...
"server(6012)" causes: error(existence_error(procedure,seq/3),seq/3)

My Scryer version is cargo:0.8.127, and I'm at commit c0d48dd2023987432eda6dac0b77be45c2e03bd8 of the-power-of-prolog. I'm happy to provide more info if needed.

In your website, your rule list_length gives me error Syntax error: Operator expected

I'm a big noob at prolog, please bare with me

Thanks for the amazing resource! It's greatly apreciated, and I'm learning a lot. One thing that is lacking is a concrete set of exercises that follow the content. Any recommendations would be highly regarded. There are occasional suggestions to improve some predicate as an exercise, but I was usually blocked immediately by lack of knowledge.

I've started on 99 prolog problems, which are very useful, but the problems do show their age somewhat and I recognise that these are not in the same spirit as the Power of Prolog site. Although, maybe improving those exercises could also be seen as an exercise. :)

[EDIT]: PS, this is from the perspective of an absolute beginner. Also, I'm only half way through the book so these comments largely apply to the early material where beginner-friendly exercises would be a great asset.

Many thanks for posting the very interesting video on the "Social Golfer" problem! A similar problem is organising table positions for people over a multi-day conference / business meetings where you also want to maximise socialisation, but the days + table numbers (groups) are fixed.

How would you change your approach to the "social golfer problem" if the number of groups / people / weeks is fixed and even if the optimal solution is not possible, how can you minimise duplicate player pairings over the entire schedule to maximise socialisation?

I see that you explained this concept in the procedural sense but not the logical one (or did I miss it?). A logical explanation would explain the concept better.

Here, you write:

Head, [T1,...,Tn] --> Body.

can be read operationally as: parse the list using Body, then prepend the terms T1, ..., Tn to the remaining list...

Would it be accurate to say that:

Head describes the list difference Body minus [T1, ..., Tn] ?

I was expecting you to write something like that.

Continuing the above:

nt1, [b] --> [a].

The body of nt1//0 describes a list whose single element is the atom a. Operationally, after nt1//0 has consumed the atom a in a list that is being parsed, it inserts the atom b in front of the remaining list.

If my statement above is correct, then I suppose that a more concise version of the previous sentence could be:

nt1 describes the list difference [a] - [b]

which is proven by the output:

?- phrase(nt1, A, B), list_diff(A, B) = list_diff([a], [b]).
A = [a],
B = [b].

Side note: We could add that using phrases like "X is the list difference Y - Z" would make it obvious to the newbie why phrase/3 is needed instead of phrase/2.

If I think of nt1 in this way, it helped me to understand the section about passing implicit states. E.g you write:

state(S0, S), [S] --> [S0].

The nonterminal state(S0, S) can be read as: "The current state is S0, and henceforth it is S".

That left me scratch my head! Instead, I was expecting something like:

state(S0, S) describes the list difference [S0] - [S] where the current state is S0 followed by the state S

I practised and learnt that we can make the list track all state changes by making a simple change:

% keep the S to maintain a history
state(S0, S), [S] --> [S0, S].

I understood that this works because it describes the list difference [S0, S] - [S] equalling [S0], describing only the expected current state S0.

What do you think of my logical description of pushback lists?

Hello Markus,
Some links for your research papers are missing from the home page and I'm adding here because I don't know of any better place to send you:

• Better Termination for Prolog with Constraints (pdf via Arxiv)
• Tor: extensible search with hookable disjunction (link was broken) (pdf via Semantic Scholar)
• Constraint solving for high-level WCET analysis (pdf via Arxiv)
• A generalised finite domain constraint solver for SWI-Prolog (pdf via Semantic Scholar)
• Declarative Language Extensions for Prolog Courses (pdf)
• Compiler Technology for Blue Gene Systems (pdf via Semantic Scholar)

Big fan,
Jeshan

Hi! I liked your video about term rewriting with prolog. This made me curious if it's possible to do term rewriting on prolog code. You mentioned "narrowing" in passing which lead me to some interesting results after some light googling 1 2, but I'm not sure in which direction to go in to learn more.

My intuition tells me that to do this on a prolog query you'd first need to fold the query and all transitively referenced rules down into one very long query first, and then you could apply rewrite rules to it from there. But I'm not sure if this "folding" procedure could be valid for all possible rules.

Thoughts?

I am currently writing a chapter explaining some cryptographic applications of Prolog, such as:

• verification of SSL certificates
• establishing shared secrets
• how to securely store passwords
• encrypting important information
• generation of Bitcoin addresses
• etc.

If there is anything you would like to see covered in this chapter, please let me know. Thank you!

I know you touched on this in a video, I think it would be helpful to have a chapter on legacy vs modern predicates, which legacy predicates we should take the time to understand, and when is the correct time to use them vs the newer ones. Since most prolog books are old, what to watch out for when reading them.

Is there ever a place for \+ or once? Or predicates which gather all solutions into a list?

It seems that the target website (Universitat Politècnica de València) changed (structure of some) URLs; so in Testing Prolog Programs ("Further reading"), the link to the paper "Concolic Testing in Logic Programming" needs a new/edited URL.

Staying on the university website, this URL now works:

https://personales.upv.es/gvidal/german/iclp15/paper_CORR.pdf

Hello. I think this resource is great, but it is a bit inconvenient that to read it offline it is necessary to run a server. Could it be possible for you to offer it in some e-book format such as PDF or EPUB? It is not necessary, but some people, like myself, find it very convenient. Thank you for your time & effort.

Would be amazing to support Prolog syntax highlight in the code snippets.

Following the "Attributed Variables" chapter https://www.metalevel.at/prolog/attributedvariables, in a fresh REPL using scryer-prolog version "v0.9.0-63-gc490d818", I constructed a file attrmod.pl, and then attempted to use it at toplevel.

%% File attrmod.pl
:- module(attrmod, []).
:- use_module(library(atts)).
:- attribute a/1.

?- consult('/path/to/attrmod.pl').
   true.
?- attrmod:put_atts(X, a(test)).
caught: error(existence_error(procedure,attribute_goals/3),attribute_goals/3)

I did not expect this behavior. Perhaps a default implementation of attribute_goals in the suggested attrmod.pl file?

It would be interesting to have a chapter on commenting prolog. There seems to be some sort of syntax for comments I have seen in some of the scryer library code, and a way to express whether a predicate argument can be handled as input and/or output.

There must be some way to ask about a predicate's comments and/or its arguments comments so prolog code can reason about itself, and for predicate and argument comments to be modified when a predicate is wrapped somehow (macros? higher order predicates). Similar to Python's comment strings for functions and type hints for argument, and function decorators which can wrap functions, change comment strings, etc.

The chapter on web applications [1] says, among other things

In Scryer Prolog, library(xpath) allows us to access HTML elements by XPath specifications in a straight-forward way.

[1] https://www.metalevel.at/prolog/web

But the example shown (//li(text)) is not an XPath expression. It would be more accurate to describe the library as is done in the SWI Prolog documentation [2], as using "descriptions inspired by the XPath language". Saying the expressions are XPath, when it is obvious at a glance that they are not, gives a bad impression, at least to some readers.

[2] https://www.swi-prolog.org/pldoc/man?section=xpath

Hi,
in the memoization chapter, the fibonacci rule runs 'backwars' just fine if you do not use tabling:

2 ?- fibonacci(X, 34).
X = 8 .

If tabling is enabled, it stops working:

4 ?- fibonacci(X, 34).
ERROR: Type error: `user:fibonacci(_2628{clpfd = ...},_2624)' contains attributed variables
ERROR: In:
ERROR:   [10] throw(error(type_error(free_of_attvar,...),context(...,_2870)))
ERROR:    [7] <user>
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

Additionally, I think it would make sense to mention that one has to load the tabling module before using it:

:- use_module(library(tabling)).
:- table fibonacci/2.

Cheers and thanks for writing the book,
Julian

In the Reading This Book section it is mentioned to direct the browser to http://localhost:6012/prolog. However, the server just redirects to the online version of the page. It would make sense to have it available, or use a different example i.e. prolog/introduction works fine.

I'd like to run your book from docker for a reason. and I need to access it from external browser, like 192.168.0.183:6022/prolog., not localhost:6022/prolog.
while running the command scryer-prolog -g "server(6012)" server.pl , it looks it is running on localhost, as below lsof output. so I'd like to know is there some way to run scryer-prolog -g "server(6012)" server.pl with specified 0.0.0.0 IP address. Thanks.

root@324e3f0b47c4:/the-power-of-prolog# lsof -n | grep TCP | grep LISTEN
scryer-pr 8864 root    3u  IPv4 1120003      0t0     TCP 127.0.0.1:6022 (LISTEN)

Something like Rust book, see https://doc.rust-lang.org/book/ch08-03-hash-maps.html for example.
Should be feasible with just changing CSS files, without adding more javascript.

See these CSS-only frameworks for example:

• Pure CSS
• Mini CSS
• And more...

I want to use "ediprolog" package on Emacs as the book mentioned in https://www.metalevel.at/ediprolog/

He says:

The two most important configuration options are:
ediprolog-system, either scryer (default) or swi
ediprolog-program, the path of the Prolog executable.

So I tried C-X , customize-group , ediprolog and checked the configuration file. The files looks like this:

To be honest I have no idea how, where can I edit to add the prolog executable path ~/.cargo/bin/scryer-prolog. In addition, Emacs says You can't edit this part of the Custom buffer when I tried to type something on the file.

And as I can expected, when I run ediprolog-dwim, "view-echo" says ediprolog-run-prolog: No prompt from: scryer-prolog, probably because I don't set the path on a configuration file.

I'm noob to Emacs and the package also, sorry about that, but I'm really struggling to achieve this step. Your comments must be really helpful for me. Thanks.

As of this post, there are only links to the next chapter at the top of the page. I'm not there when I want to go to the next chapter, because I've scrolled all the way to the bottom. Links at the bottom would make it easier to continue reading.