El blog de Adrián Arroyo

Scryer Prolog Meetup 2023 Notes

- Adrián Arroyo Calle

The 9th and 10th of November was the Scryer Prolog Meetup 2023 in Düsseldorf. As a Scryer Prolog user and contributor, I was very excited to go to this meeting. Now, I'm back at home and I can write here a report of what happened in this event with the notes I've taken.

But before starting with the talks, let's understand why this event took place. Officially, it is considered that Prolog, as a programming language, was born in 1972. That marked 2022 as a special year since it was its 50 anniversary! Several things were organized, a book was released and several papers were published on the matter. But the big celebration was the Prolog Day Symposium, which took place on November 10th in Paris. For some people like me, it was a special event in which we were surrounded by lots of the names behind what Prolog is. Several Scryer Prolog developers met there and after the good experience, we agreed it was a good idea to hold a meetup for Scryer Prolog on similar dates the next year.

And it happened! Thanks to Christian Jendreiko, a professor in Hochschule Düsseldorf; Markus Triska and the association Prolog Heritage, the event took place. Many thanks to them!

And now, let's start with the first day:

Current developments in Scryer Prolog - Mark Thom

Link to presentation

Mark is the main developer of Scryer Prolog. In this talk, he talks about the past and future of Scryer Prolog. First, Mark wants to thank all contributors for their work in the past year. He also wants to mention that Scryer has now a proper webpage. Also, now there's a playground that, although limited, allows people to try Scryer Prolog without the need to install anything. This playground is based on the WASM work by @rujialiu. This WASM port also required several changes to support 32 bit targets.

Since last year, two releases of Scryer happened (v0.9.2 and v0.9.3). They include lots of changes compared to v0.9.1. The main ones are:

  • Atom table concurrency (thanks to @Skgland). This will allow multithreading in the future.
  • clpz improvements (@notoria, @triska, etc)
  • CI improvements by @infogulch
  • HTTP improvements and foreign function interface basic support by @aarroyoc
  • Djot and documentation for most libraries by @aarroyoc and @triska
  • Moved from GMP to dashu thanks to @fayeed and @lucksus
  • The ability to use Scryer as a library by @fayeed and @lucksus
  • dif/2 improvements by @bakaq
  • #scryer IRC channel on Libera Chat by @rikardlang
  • Minor fixes and test cases (@gruhn, @UWN, @pmoura, @infradig, @flexoron, @haijinSk, @josd, @rujialiu, @triska, ...)

He has been working on the following items:

  • Improved ISO standard conformance
  • call/N goal expension caching
  • Much better compilation of disjunctions
  • Lookahead indexing
  • Introduction of stackless iterators
  • Many bug fixes
  • Golden Roll #1 (a technical doc showing how Scryer Prolog internals work)

He has also been working on several items that require a little bit more explanation:

Garbage Collection

He wanted to add it for 3 years already, but he was held back a little by Rust's youngness. The algorithm is based on two-finger mark+compactation from the paper Garbage Collection for Prolog Based on WAM. Some changes are required since, for example, Scryer Prolog features "partial strings". Partial strings are a response to some Prolog's inefficient use of strings. Partial strings were inspired by Lisp and provide a similar interface to lists while being stored more compactly.

Arena allocation will follow a BiBoP scheme, collected in tandem with the heap.

All these things will make it easier to track resources at the cost of being more verbose.

Some obstacles that he found with Rust are the imposed RAII. It would be nice to slot a custom allocator abstraction into common Rust data structures, like Vec. That would leave us with more flexible options, which are required for a garbage collector.

However, the allocator_api for Rust is not stable and only available on nightly releases.

Also some data types will require finalization when freed.

At this point, he is implementing some data structures from scratch to be able to continue working on the GC.

Last but not least, Prolog allows dynamic modification of the program, so a GC should be added to the code space too.

Partial String Heap Section

Regarding partial strings, as mentioned, there must be some changes in how they work. This started a discussion about the trade-offs of different designs. Right now, partial strings are not freed on backtracking (most other data types do), so GC is the only option here. Adding support for free-on-backtracking will make choicepoints bigger in memory, though. Also, the current code needs to know in lots of places if we're dealing with a partial string or not.

WAM Heap Cells Optimization

Atoms that use 6 bytes or less are going to be stored in heap cells directly, without being written to the atom table. This is an optimization found in several programming languages and it'll make more sense now that the atom table is thread-safe and there's some synchronization overhead.

Also, the tag space has been revised and now they use fewer bits. Most data types in the WAM go from 6 bits to 4 bits.


Current plan is to compile WAM using Cranelift. However, GC must be done first. Maybe Prolog in the future could be used to analyze Prolog programs and produce optimizations (Prolog compiler in Prolog?)

Compilation speed-ups

There's a bottleneck translating between heap terms and Term (eliminate Term). Making Instruction data type smaller.

Compilation of Scryer itself is becoming a concern with Rust compiler taking more time and using more memory.

Other improvements

There's an effort to push for multithreaded Prolog. But still a lot of questions are unanswered. How to coordinate threads? Which concurrency model should we support?

An even better disjunction compilation was also proposed for several cases.

Inlining common predicates was also being worked on since a lot of WAM inefficiencies come from shuffling HeapCellValues around in registers. Some ISO predicates already have this inlining implemented like var/1.

Writing more Golden Rolls as they serve both as reference documents and incite people to contribute. Open to subjects!

Scryer Prolog is not cache friendly. Clobbering the most common sequences of instructions into a single instruction could help.

Arithmethic performance can be improved even without native compilation

Some questions were asked to Mark. To the question of how he keeps doing the project, he just replied he feels he's doing more meaningful work here than in other places. About benchmarks, he replied that Scryer still doesn't have any automatic benchmark suite. Also, it was remembered in the room that we should not trade off correctness for performance. About coroutines, it was said that Scryer supports freeze/2 and dif/2 (one of the few systems with a correct dif). But when/2 and block declarations are still missing.

Foreign Function Interface - Adrián Arroyo Calle

Since this talk was given by me I didn't take any notes :). You can still download the presentation

How we use Prolog in ADAM and the Synergy Engine - Nicolas Luck

Nicolas is the co-founder of the DAO Coasys. Coasys current products are three: Flux, ADAM and the Synergy Engine.

ADAM is actually the most important thing. It's a layer upon new applications can be built. When you build your application on top of ADAM, all the communications are abstracted and you just focus on creating data and querying data, in the form of knowledge graphs.

Flux is an app built using ADAM, a chat platform similar to Discord and Slack. It serves as a proof-of-concept for ADAM.

Unlike other approaches with knowledge graphs like semantic web, ADAM takes an agent-centric perspective, since it's the only way data can scale to civilization levels. In today's society, companies need to host the information, and that makes them not objective by definition. Blockchains can solve some issues here but they're slow. With the agent-centric approach, each agent is responsible of their own knowledge.

Each agent has its own data. Each agent can choose to define its data with their own ontologies. The data units for an agent are expressions, which can be expressed in different "languages" (different technical backends, like IPFS, blockchain, Twitter, ...) and are cryptographically signed.

"Perspectives" are how we associate expressions between them.

When we move this from just one agent to several ones, we have neighborhoods, which are perspectives shared by more than one agent. Those perspectives have a social DNA which we can use to interact and understand the data. This social DNA is Prolog code, although there are DSLs in other languages to generate these queries.

Apps in ADAM take a perspective or a neighborhood and their respective social DNA and then they represent the data

Apart from the ORM, there's also an editor to define classes in Prolog. There's also an LLM system to help people create the Prolog code from natural language.

So, what is Synergy Engine? It's a search engine built on top of ADAM. User writes a query, the query gets translated via LLM to Prolog code, and it's executed on the local graph or a remote one trying to find an answer. When a node finds an answer that generates the correct information (this is cryptographically checked, so it's the right answer), it gets an optional reward, if the user set it at the beginning

50 years of Prolog - A few things to keep in mind - Guy Narboni

Guy worked in Prologia, in the team that developed Prolog IV. Now, he has a consultancy called Implexe and it's also the president of Prolog Heritage.

At the beginning there were no numbers in Prolog. One could only symbolically express numbers, using Peano's arithmetic. Nowadays we can express integers using #= from clpz while preserving all logic features.

However, it only works for integers. We need all numbers covered cleanly. That's where Relational Interval Arithmetic enters.

It makes possible calculations with guaranteed precision, safe pruning deductions in logic and interval constraints generalize clpz.

Computation that has Interval Arithmetic is compatible with logic and it's safe. That was the idea pushed by Prolog IV.

Also, it was pushed that both =/2 and dif/2 should work for every data type, even if they're numbers. Using dif/2 is very useful since it often removes the need for cuts.

Rationals, decimals, integers,... were numbers but also they were treated as trees

Now we can get some of the benefits of Prolog IV with #= but in Prolog IV, that was normal unification. Guy presents the Perfect Rectangle Case Study from Prolog III

It shows that a simple syntactic change like replacing H0 with 0 in the head would make different results, because unification in Prolog III, unlike in IV, doesn't support all datatypes.

Prolog IV worked with several types. All of them can be thought as a tree, but they're handled differently. There's a preunification table for types.

In Prolog IV reals are approximated by intervals. Every numerical value is represented by a rational with infinite precision where integers are as big as necessary.

Since dif/2 is a generic constraint, you have to deal with open and closed intervals

Prolog IV was a beautiful PoC. Industrializing Prolog IV would be a rich idea! Even more powerful than clpz

Marseille Prolog benefitted from WAM-Prolog line, but WAM-Prolog line ignored Marseille Prolog line!

Eclipse has some parts of Interval Arithmetic

Guy's wishlist

  • Interval solver
  • Linear solver
  • Research issues: enhanced LP / IA communications

Art, Design and DCGs: The generative power of Prolog - Prof. Christian Jendreiko

I came from a different perspective. I'm not an engineer, or a mathematician. I studied Media Theory. I liked logic to understand medieval thinkers.

In Systems Design. We try to work on interdisciplinary teams. I'm happy we can bring together artists and engineers. I think is important that also artists understand a little bit of how computers work.

I teach Prolog to young artists and designers.

Two reasons: helpful tool to understand your own ways of reasoning and it's a great tool to step into logical things. So they can use it in the creative process Get students to get in touch with the fundamental concepts of CS (graphs, search, permutations, ...) from a solid logic ground.

From a didactic point of view: with Prolog you can deep dive into the big topics of CS without any distraction.

I also use it for electronic art. The computer changes the status quo of the artist in society and changes how communication happens. (Max Bense Programmierung Des Schönen)

Paul Klee: "making art of any kind means to think in sequences in order to create patterns". Context of the time: shaky grounds in physics, maths "Prolog was made to describe sequences"

Together with the students we learn how to teach Prolog. What are the good ways to communicate Prolog to people?

The course is not about using tools created by other people like Midjourney but about creating their own programs. And to really understand what programming really means.

Prolog also helps thinking in backward reasoning in the arts: Michel Angelo (you have a goal). And differentiate it from forward reasoning: Miró. He went to the beach and out of the pieces he found he constructed his art

When you're taking a photo, in what mode are you thinking? Backward or forward?

Let artists work systematically, without resorting to drugs

Now that there's a browser version, it's going to be very helpful for students since they have trouble setting up.

I want to migrate to Scryer. We're using SWI.

We also want to use the predicate format_/2 which is a big improvement.

Example of poems generated by DCG. A DCG is like a casting mold.

He wants with the help of the students create a database from the Pattern Poetry book. With all patterns in the database, we could start experiments, mixing, recombination,... We would use the great power of generation of Scryer Prolog. Also, we want to abstract the shape of the output.

There were some questions:

LLMs get boring because they all. They all recombine the same. You need to get into the basics, the structure to avoid boringness.

You only use format_? Have you tried going 2D canvas or a 3D space? Yes we are trying with Tau because it can access JS and acccess to MIDI, graphics, ... I hope with Scryer web version we could also use that in a future. We also really want a MIDI interface to play with music format.

ISO Prolog, a basis for Prolog extensions - Prof. Dr. Ulrich Neumerkel

He's the convener of ISO standardization.

Prolog systems often are interested in ISO but later they get creative and they break. One of the systems that has kept ISO Prolog conformance is Scryer Prolog. Even with "weird" examples.

Then Ulrich starts to go over the history of Prolog:

  • 05/1972 Before Prolog existed: système OEdipe, not yet Prolog, first dif/2 (almost no documentation)
  • 1972 Prolog 0 with dif/2, boum/2 (similar to atom_chars/2), occurs-check option, many cut-like constructs (very obscure feature).
  • 1975 (date of manual, probably 1973) Prolog I, no constraints, but errors, cut
  • 1977 DEC 10, better syntax, no errors, mostly silent failure instead very influential, basis for ISO, started (deadly) speed race where systems tried to be faster and faster.
  • 1981 FGCS. They used Hungarian MProlog at the beginning, but later they went to committed choice languages. The decision to use MProlog was controversial (Iron Wall) so ESPRIT project started, and many Prolog systems were developed. Take into account Prolog systems were very expensive systems. For example, IF/Prolog cost 20.000 Deutsche Marks at their time. Need for standardization
  • 1984 BSI with Roger Scowen started standardization with BS6154
  • 1987 Proposal accepted to ISO, begin of WG17
  • 1995 ISO/IEC 13211-1 published

Some of the highlights of the standard:

  • disambiguated DEC10 syntax (first systems worked fine but their docs were bad so other systems later did it wrong)
  • unification defined for the first time NSTO. But STO is not defined. Because there were problems with rational trees that should also be there.
  • multi octet character set handling (MOCSH). Bytes and characters are not the same
  • clean error system, separates between instantiation errors and type/domain errors (this was very controversial at the time, as lots of people liked silent failure approaches)
  • no modules, later another standard was developed (13211-2:2000) but it's weak and accepts lots of interpretations
  • no constraints, but... allows extension mechanism (5.5.11)

Extensions are only allowed if there's a strictly conforming mode without it. Most things can be done with modules (constraints, builtins, ...) but some are more difficult (syntax extensions, ...). Constraints are allowed then!

What was the state of the art of constraints at that time?

First, freeze/2 and frozen/2. consistency only via labeling. Then in 1988, meta-structures but very unusable. Attr vars were created in 1990 as "better meta-structures" but it was module based! So couldn't join ISO because there was no place in the standard for modules.

AttrVars are present in SICStus and Scryer and to a lesser degree Ciao, SWI. They have different models. Markus Triska says for library developers it's easier the SICStus/Scryer interface while probably it's more costly for the Prolog system too.

What's the current WG17 work?

  • DCG (yes, still)
  • No work on attr var as it's too hard to specify them mechanically. So we prefer to work on a higher level with things like dif/2
  • dif/2 only works without bugs on three systems: Prolog IV, SICStus, and Scryer.
  • Unicode support
  • Prolog prologue - things like length/2. Still very surprising how very different behaviors are observed with these simple predicates.
  • clpfd/clpz. Far from finishing it
  • STO unification but rational trees originate problems again
  • Queries using answer descriptions (quad). First for documents, and later for tests.
  • Conformity testing. Continuous work

Suggestions are welcome!

That was the end of day 1. See the following post for day 2 where we'll see how Prolog helps in oncology, automated train systems, and the Austrian government.


Añadir comentario

Todos los comentarios están sujetos a moderación