#4 - Markus Triska on constraints and the power of Prolog

The Search Space

Visit the show's web page: thesearch.space

Show notes

The Power of Prolog, Markus' ongoing book project

"It says, 'Find your way from darkness to light,' which is one of the quotes that occurs in The Knight of Cups, which is a recent movie by Terrence Malick."

"I was introduced to Prolog by Ulrich Neumerkel at the Vienna University of Technology."

"the convener of the Prolog ISO standard group."

"He has developed his own teaching environment called GUPU, which means talk-assisted programming environment [Gesprächsunterstützende Programmierübungsumgebung]."

Declarative program development in Prolog with GUPU (paper)

"one fellow student came to me and asked for a solution to [what] you may now know as the SEND MORE MONEY task."

SEND + MORE = MONEY

"People have ... in different languages, explored multi-dispatch, multi-methods, and all kinds of stuff."

"... the notion that an algorithm can be decomposed into a logic aspect and a control aspect. So this is written as 'algorithm is logic plus control.'"

"...let's look at the HTTP framework of SWI-Prolog"

"...the first use case that Prolog should solve was translating weather reports between French and English. It was the METEO system..."

"For this purpose ... DCGs were invented. So this is a sub-formalism in Prolog that lets us describe lists in a very natural way."

"...you have kind of a special syntax with the keyword is, and many of the normal, nice properties of Prolog start breaking down."

(is)/2 is not actually a keyword or a special syntax. Markus describes the issues involved very well here:

https://github.com/triska/clpz#an-impure-alternative-low-level-integer-arithmetic

and here:

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

"It is abbreviated as CSP: Constraint Satisfaction Problem."

"You have variables, you have associated domains, which in plain Prolog are always Herbrand terms, named after Jaques Herbrand."

"In the literature, this has even been mentioned as the Holy Grail of computer science. This property [or] at least the idea that users or application programmers specify a task and the system solves it."

Eugene C Freuder. “In pursuit of the holy grail”. In:Constraints 2.1 (1997), pp. 57–61. (not freely available)

There is an ongoing series of workshops following up on the ideas in the original paper:

https://freuder.wordpress.com/pthg-20-the-fourth-workshop-on-progress-towards-the-holy-grail/

"For comparison, [...] the constraint solver for SICStus Prolog is hundreds of times faster than for example what I've implemented."

> "rusty-wam, implemented in Rust"
(hence renamed Scryer Prolog, with Markus being an active contributor)

> "There is O-Prolog, which is implemented by Kenichi Sasagawa from Japan."

> "..in the case of Tau Prolog, it's implemented in JavaScript and they can embed Prolog in a web browser"

The Power of Prolog YouTube channel

★ Support this podcast ★