Learning Resources: Implementing Prolog

[jgarte]

Hi,

Would you recommend this book as a good starting point for understanding how to implement Prolog?

The Implementation of Prolog (Princeton Series in Computer Science) by Patrice Boizumault

[infradig]

Yes, it's a good book. The code examples it gives are in Lisp not C, but the discussions are good and illustrative. Not so relevant to Trealla which is more a traditional interpreter than a WAM-type compiler.

…

On Thu, Jan 2, 2025 at 4:04 AM Jorge Gomez ***@***.***> wrote: Hi, Would you recommend this book as a good starting point for understanding how to implement Prolog? The Implementation of Prolog (Princeton Series in Computer Science) by Patrice Boizumault — Reply to this email directly, view it on GitHub <#652>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFNKSETXFFXYBSXPUNHD5XL2IQU4NAVCNFSM6AAAAABUO3DM5OVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZXG43DQNRSGE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[jgarte]

Thanks for the information.

I'm fluent in Common Lisp so that won't be an issue for me. I've worked on various Common Lisp projects.

What resources or books would you recommend for understanding the implementation of Trealla besides just reading the source code and trying to understand it with a reading and debugging the source code approach?

I feel like I need to gain some more context before the Trealla source code starts to make sense to me.

I am interested though in approaching the understanding required to do so.

[infradig]

I doubt the source code would make sense to anyone 😆 as it's quite ad-hoc, though i've tried to revise, organize and simplify it over the last year or so.

…

On Thu, Jan 2, 2025 at 11:14 AM Jorge Gomez ***@***.***> wrote: Thanks for the information. I'm fluent in Common Lisp so that won't be an issue for me. I've worked on a number of Common Lisp projects. What resources or books would you recommend for understanding the implementation of Trealla besides just reading the source code and trying to understand it with that approach. I feel like I need to gain some more context before the Trealla source code starts to make sense to me. I am interested though in approaching the understanding required to do so. — Reply to this email directly, view it on GitHub <#652 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFNKSEXUI5T7J3IQPIYIBGT2ISHGXAVCNFSM6AAAAABUO3DM5OVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNZRGMYTIMI> . You are receiving this because you commented.Message ID: ***@***.***>

[jgarte]

I've been trying to read it when I have some free time but it is a slog to get through as an outsider to the project 🙃

[jgarte]

Not so relevant to Trealla which
is more a traditional interpreter than a WAM-type compiler.

Hi, which book would you recommend for learning how to implement a WAM-type compiler? @infradig

[infradig]

Haven't really looked at it as it's not relevant to Trealla. I haven't written a WAM compiler but have worked on one.

[jgarte]

@infradig If Trealla, does not implement a WAM compiler, then, what has been implemented instead? 🦆

[infradig]

@infradig If Trealla, does not implement a WAM compiler, then, what has been implemented instead? 🦆

It's an interpreter. It's more complicated than that of course.

[jgarte]

@infradig Where do you recommend I start my implementing Prolog journey?

I have a very long term goal of someday maybe implementing a modern ISO Prolog in Common Lisp.

I know. It is a far fetch.

I was thinking to start by porting over Trealla Prolog note for note 🎶 from the C code to Common Lisp.

What do you think? Where should I start?

I was thinking to maybe start by porting the following toy implementation over to Common Lisp as a first exercise and trying to understand how it works:

https://github.com/aarroyoc/esgueva

[jgarte]

@infradig

It's an interpreter. It's more complicated than that of course.

Hi, can you give me a brief hint or nod at how it's more complicated than an interpreter just so I can get a ballpark idea of that? It would be much appreciated.

I am currently familiar with the structs, enums, functions, etc. in the code base but of course I still need to do more reading to connect the dots/usages. That said, I've been doing a lot of reading and thinking lately on the Trealla Prolog code base in order to familiarize myself.

[infradig]

As per initial comment...

Yes, it's a good book. The code examples it gives are in Lisp not C, but the discussions are good and illustrative. Not so relevant to Trealla which is more a traditional interpreter than a WAM-type compiler.

If you're working in Lisp then maybe start here. I don't Lisp.

[jgarte]

Thanks for the suggestion again. 🦆 😸

[infradig]

I started with a very simple Prolog interpreter, much like Adrian above. Then iterated more complex versions, trying different things. I will probably never attempt a WAM compiler though, plenty of options there already. Good luck, it's a very long & deep rabbit hole.

[jgarte]

What made you not want to attempt a WAM compiler and instead go with your own interpreter approach?

The WAM approach is convoluted in some way or something else?

[infradig]

When I started out I wasn't aware of the WAM.

…

On Tue, 18 Mar 2025, 13:23 Jorge Gomez, ***@***.***> wrote: What made you not want to attempt a WAM compiler and instead go with your own interpreter approach? The WAM approach is convoluted in some way or something else? — Reply to this email directly, view it on GitHub <#652 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AFNKSERSSI4ZXTTMYQCEGPL2U6GULAVCNFSM6AAAAABUO3DM5OVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTENJTGI3TKNA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[infradig]

More recently the code has become more 'inspired by' the WAM. For example compiling/inlinining control structures to static instructions during load. Clauses can have an alt form made of bytecodes instead of just goals. Meta goals like call/N & friends are also compiled just-in-time to bytes on the heap (though they are discarded as soon as possible).

For example the first listing here shows the source-like form (in Prolog)...

$ tpl
?- [user]. f :- g1 -> g2; g3.
   true.
?- listing(f/0).
f :-
   g1->g2;g3.

whereas the second here shows the compiled/inlined form (as instructions)...

?- '$xlisting'(f/0).
f:-
  '$succeed_on_retry'(A,10)
  g1
  !
  '$drop_barrier'(A)
  g2
  '$jump'(3)
  g3
  true

Note: 10 & 3 are offsets to jump in the instruction stream. The first is a conditional, the second unconditional.