3 ms·
The Boolean circuit example on page 148 is interesting: In modern Prolog systems that provide this functionality, we can model such circuits very elegantly with
by triska 4y ago
The Boolean circuit example on page 148 is interesting: In modern Prolog systems that provide this functionality, we can model such circuits very elegantly with CLP(B), Constraint Logic Programming over Boolean variables.
For example, with Scryer Prolog and its clpb library, we can define:
:- use_module(library(clpb)).
nand_gate(X, Y, Z) :- sat(Z =:= ~(X*Y)).
xor(X, Y, Z) :-
nand_gate(X, Y, A),
nand_gate(X, A, B),
nand_gate(Y, A, C),
nand_gate(B, C, Z).
We can enumerate all solutions with labeling/1:
?- xor(X, Y, Z), labeling([X,Y]).
X = 0, Y = 0, Z = 0
; X = 0, Y = 1, Z = 1
; X = 1, Y = 0, Z = 1
; X = 1, Y = 1, Z = 0.
The solver also includes a feature that lets us algebracially show the defined relation as a function of X and Y by posting the query:
?- xor(x, y, Z).
Yielding:
clpb:sat(Z=:=x#y), ... .
This makes it immediately obvious that the circuit models XOR, as intended!
The section on Constraint Logic Programming starting at page 171 contains more information about this paradigm. You can make constraint solvers available as libraries also in other programming languages. However, they blend in especially seamlessly in logic programming languages like Prolog, because constraints already play such a prominent role in these languages, and generalizations and specializations of programs and queries come naturally: In fact, the built-in predicates (=)/2 (unification) and dif/2 (disequality of terms) can also be regarded as constraints (over Herbrand terms, H). Prolog itself can therefore be regarded as a particular instance of constraint logic programming, CLP(H).
I also highly recommend the chapter on Logic Grammars starting at page 185 in the magazine: Convenient and efficient text processing was the original goal of Prolog and the reason for its development. Prolog originates from Q-systems, which were introduced by Alain Colmerauer for the translation of weather reports between French and English. Nowadays, virtually all Prolog systems ship with Definite Clause Grammars (DCGs), one of the most attractive mechanisms to describe and reason about sequences in Prolog, which can be used for describing and analyzing lists of characters and hence text as a special case.
- Tomte 4y ago> Convenient and efficient text processing was the original goal of Prolog That was actually where I first saw "real" Prolog program: in University in the introduction to computational linguistics lecture. Parsing syntax trees, annotating trees with semantic meaning, and calculating all kinds of cool stuff I don't remember anymore was eye-opening. Unfortunately, our lecturer used IBM Prolog, we students had only access to SWI, and none of his programs worked on SWI. That made the lecture very frustrating, and doubly so, because the lecturer all those years before our cohort was excellent, with great study material and exercises.
- triska 4y agoThese use cases become especially interesting now with several recent Prolog systems such as Scryer, Tau, Trealla and ichiban/prolog: All these systems set the Prolog flag double_quotes to chars already by default, and this means that we can write lists of characters especially conveniently as double-quoted strings in programs in queries! For example, the list of characters [a,b,c] can be conveniently written as "abc" in all these systems, and of course also if we manually set the flag to chars in any conforming Prolog system. Scryer and Trealla combine this default for the flag with an extremely efficient internal representation of strings, using packed UTF-8 encoding internally, so that also very large amounts of text can be efficiently and conveniently processed with DCGs. In Trealla Prolog, using phrase_from_file/2 even transparently maps the file contents to memory with the system call mmap(2) for extreme performance.