Abstractions, Encapsulation, Coupling, and Code Organization in Prolog

[jjtolton]

Abstractions, Encapsulation, Coupling, and Code Organization in Prolog

Overview

I'm curious what everyone's experience with modularization/organization is with Prolog. I strongly suspect the answer is "DCGs", but allow me to explain my case:

In OO languages, techniques such as inheritance or SOLID principles are used to organize code in such a way that (in theory, if not practice) it is easy and comprehensible to extend, modify, and maintain the code. Python allows for operator overloading and polymorphism, so you can do fun things like

>>> 1 + 2
3

>>> "c" + "at"
"cat"

>>> [1] + [2,3]
[1,2,3]

That's because integers, strings, and lists all define the __add__(self, other) method, which is what gets invoked when the + operator is called.

Haskell of course really takes this to the next level, and adds a layer of type safety on top of that.

There are a zillion approaches to this, way too many to list, I'm just trying to establish some common understanding of what I'm talking about.

Prolog approaches identified "in the wild"

In exploring Prolog code, I've identified two examples so far of these techniques.

The first is the A* implementation from Prolog Programming for Artificial Intelligence, and the other is from library(atts).

The more familiar one (to some) is probably the library(atts) version loading files, where (credit @bakaq for showing this to me) users are able to define goal_expansion/2 and term_expansion/2 in their modules and they will be invoked in some way (I don't fully understand the details) in conjunction with when atts:term_attributed_variables/2 is invoked while for attributed variables, attribute_goals//1 and/or verify_attributes/3 are defined (see #2591 (comment)).

Module loading

Module loading APIs defined for atts.pl and dgs.pl

%%% atts.pl

%% ...snip...
user:term_expansion(Term0, Terms) :-
    nonvar(Term0),
    Term0 = (:- attribute Atts),
    nonvar(Atts),
    prolog_load_context(module, Module),
    phrase(expand_terms(Atts, Module), Terms).
%% ...snip...
user:goal_expansion(Term, M:put_atts(Var, Attr)) :-
    nonvar(Term),
    Term = put_atts(Var, M, Attr).
user:goal_expansion(Term, M:get_atts(Var, Attr)) :-
    nonvar(Term),
    Term = get_atts(Var, M, Attr).
%% ...snip...

And here's how it's used in library(dcgs):

%% library(dcgs)
%

user:goal_expansion(phrase(GRBody, S, S0), GRBody2) :-
    loader:strip_module(GRBody, M, GRBody0),
    nonvar(GRBody0),
    catch(dcgs:dcg_body(GRBody0, S, S0, GRBody1),
          E,
          dcgs:error_goal(E, GRBody1)
         ),
    (  E = error(instantiation_error, _),
       GRBody0 = [T|Ts] ->
       GRBody2 = (error:must_be(list, [T|Ts]),
                  lists:append([T|Ts], S0, S))
    ;  GRBody = (_:_) ->
       GRBody2 = M:GRBody1
    ;  GRBody2 = GRBody1
    ).

user:goal_expansion(phrase(GRBody, S), phrase(GRBody, S, [])).

A* approach

This A* code takes a different approach.

Client domains are only required to implement s/3 and h/2, which are successor functions and the A* heuristic function respectively. Implicit in these definitions is a model of the state, as the successor function relationship is of s(State0, State, Cost), where Cost is the g(n) in the heuristic estimator function (f(n) = g(n) + h(n)).

Thus any client of the algorithm need only define those two predicates, then invoke bestfirst/2 with a valid starting starting state (that is the same as the argument used by s/3.

You can see the details of the configuration technique in the following details sections.

A* code organization examples

A* important "APIs"

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

% bestfirst( Start, Solution): Solution is a path from Start to a goal
bestfirst( Start, Solution) :-
        expand( [], leaf( Start, 0/0), _, yes, Solution).


%%% ... snip ... (other cases of expand/5 omitted)

% Case 2: leaf-node, f-value less than Bound
% Generate successors and expand them within Bound
expand( P, leaf(N, F/G), Tree1, Solved, Sol) :-
        (   bagof( M/C, ( s(N, M, C), maplist(dif(M), P)), Succ),
            succlist( G, Succ, Ts), % Make subtrees Ts
            bestf( Ts, F1),         % f-value of best successor
            expand( P, t(N, F1/G, Ts), Tree1, Solved, Sol)
        ;   Solved=never
        ).

%%% ... snip ... (other cases of expand/5 omitted)

%% succlist( G0, [Nodel/Cost1, ...], [leaf(BestNode, BestF/G),
%  make list of search leaves ordered by their f-values
succlist( _,[],[]).
succlist( G0, [N/C | NCs], Ts) :-
        G #= G0 + C,
        h( N, H), % h(Node, Hvalue): h(n) = f(n) + g(n)
        F #= G + H,
        succlist( G0, NCs, Ts1),
        insert(Ts1, leaf(N, F/G), Ts).  % <-- maintain insertion order by h-value

%%% ... snip ... 

% Heuristic term h(N)
% Insert T into list of trees Ts preserving order with respect to f-values

insert([], T, [T]).
insert(Ts0, T, Ts) :-
        f(T, F),    % f(Node, Fvalue): get fvalue of node
        bestf(Ts0, F1), % bestf(Nodes, BestFValue): Fvalue of head of nodes, since priority sorted
        if_(clpz_t(F #=< F1),
            Ts=[T|Ts0],
            ( Ts0=[Tx|Ts0_],
              Ts =[Tx|Ts_],
              insert(Ts0_, T, Ts_)
            )
           ).

Task Scheduling Domain API "implementations"

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   task scheduling problem
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

% s( Node, SuccessorNode, Cost):
% Node: WaitingTasks * ActiveTasks * Time
s( Tasks1 * [_/F | Active1] * Fin1, Tasks2 * Active2 * Fin2, Cost) :-
        select( Task/D, Tasks1, Tasks2),      
        cond([memberd_t(T/_, Tasks2),
              (   before(T, Task),
                  fail
              ),

              memberd_t(T1/F1, Active1),
              (   F #< F1,
                  before( T1, Task),
                  fail
              ),
              else_,
              true
             ]),
        Time #= F + D,          
        insert( Task/Time, Active1, Active2, Fin1, Fin2),
        Cost #= Fin2 - Fin1.
        
s( Tasks * [_/F | Active1] * Fin, Tasks * Active2 * Fin, 0) :-
        insertidle( F, Active1, Active2).


h( Tasks * Processors * Fin, H) :-
        totaltime( Tasks, Tottime),
        sumnum( Processors, Ftime, N),
        Finall #= ( Tottime + Ftime) // N,
        (   Finall #> Fin,
            H #= Finall - Fin
            ;
            H #= 0
        ).


start( [t1/4, t2/2, t3/2, t4/20, t5/20, t6/11, t7/11] * [idle/0, idle/0, idle/0] * 0).


% ?- time(_Sol+\(start( Problem), bestfirst( Problem, _Sol))).

Eight Puzzle Domain API "implementation"

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   eight puzzle domain problem
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

s( [Empty | Tiles], [Tile | Tiles1], 1) :-
        swap( Empty, Tile, Tiles, Tiles1).

% Heuristic estimate h is the sum of distances of each tile
% from its 'home' square plus 3 times 'sequence' score
h( [_Empty | Tiles], H) :-
        goal( [_Empty1 | GoalSquares]),
        totdist( Tiles, GoalSquares, D),
        seq_score( Tiles, S),
        H #= D + 3*S.


start1( [2/2,1/3,3/2,2/3,3/3,3/1,2/1,1/1,1/2]).

?- _+\(time((start1(Pos),
             bestfirst( Pos, Sol),
             showsol( Sol)))
     ).
%@ 
%@ ---
%@ 134
%@ 8 2
%@ 765
%@ ---
%@ 134
%@ 82 
%@ 765
%@ ---
%@ 13 
%@ 824
%@ 765
%@ ---
%@ 1 3
%@ 824
%@ 765
%@ ---
%@ 123
%@ 8 4
%@ 765   % CPU time: 0.005s, 7_635 inferences
%@    true
%@ ;  ... .

Using DCGs for Domain Specific Languages(?)

My initial attraction to Prolog was actually from DCGs, because (assuming you are good at Prolog and DCGs, which is turning out to be much harder than I thought!), it should be very possible to quickly write up a domain specific language (provided you understand the domain well) to accomplish good abstractions via syntax directed translation while staying close to the core Prolog abstractions, but that's still pretty hypothetical :)

Wrap-up

Like any other code organization techniques, these have pros and cons. I have a feeling that Prolog suffers from some of the same issues that lisp and Forth/PostScript do -- meaning, there are many (wonderful) ways to write abstractions, but the more you stray from core abstractions and the more "magic" that gets introduced (e.g., lisp macros), there can be some long term consequences for that approach. Likewise, not using enough abstractions results in a lot of highly coupled, repetitive code, codesprawl, and disorganization.

I don't yet know what the trade-offs of using DCGs for DSLs are at scale.

Curious what everyone's thoughts are, here! What did I miss? What did I overlook or get wrong?

[bakaq]

users are able to define goal_expansion/2 and term_expansion/2 in their modules and they will be invoked in some way

That is goal expansion, not attributed variables. They are often used together to create nice interfaces, like in library(clpz). For attributed variables you need to define attribute_goals//1 and/or verify_attributes/3. goal_expansion/2 and term_expansion/2 are run when consulting files. verify_attributes/3 is called on unification. If you want simple examples of attributed variables, I think library(freeze) and library(dif) are good starting points.

[jjtolton]

I knew I should've taken notes!! Thanks for pointing that out!

[haijinSk]

Inspired, I was thinking: in Prolog, can I conceptualize a computation in an object-oriented way? At least one aspect, the central aspect of OOP, computation by sending messages? Of course, as I'm a programming and Prolog beginner, I can use only a small subset of Prolog , without low-level predicates, so only very simple and immutable objects... And of course, the concept how to do OOP without an OOP language is not from my head.

Edit: It seems that I should not use the words like "low-level predicates" and "only" before "immutable objects"...
Edit 2: My example is bad/problematic in more then one aspect. I conflated two concepts into one structure: hand-made "List" (it should have two "(sub)classes", like: "ConsList" and "EmptyList") and data/value "objects", etc., etc.

:- use_module(library(clpz)).

class(
  obj(data(1, a),next(
  obj(data(2, b),next(
  obj(data(3, c),next(
  obj(data(4, d),next(
  obj(data(5, e),next(
  objnull))))))))))).

obj_sum(objnull, 0).
obj_sum(obj(Data, next(Next)), Sum) :-
  data(Integer, _) = Data,
  obj_sum(Next, SumNext),
  Sum #= Integer + SumNext.

obj_product(objnull, 1).
obj_product(obj(Data, next(Next)), Product) :-
  data(Integer, _) = Data,
  obj_product(Next, ProductNext),
  Product #= Integer * ProductNext.

obj_string(objnull, "").
obj_string(obj(Data, next(Next)), String) :-
  data(_, Char) = Data,
  obj_string(Next, StringNext),
  String = [Char | StringNext].

?- class(Obj), obj_sum(Obj,Sum).
   Obj = obj(data(1,a),next(obj(data(2,b),next(obj(data(3,c),next(obj(data(4,d),next(obj(data(5,e),next(objnull)))))))))), 
   Sum = 15.
?- class(Obj), obj_product(Obj,Product).
   Obj = obj(data(1,a),next(obj(data(2,b),next(obj(data(3,c),next(obj(data(4,d),next(obj(data(5,e),next(objnull)))))))))), 
   Product = 120.
?- class(Obj), obj_string(Obj,String).
   Obj = obj(data(1,a),next(obj(data(2,b),next(obj(data(3,c),next(obj(data(4,d),next(obj(data(5,e),next(objnull)))))))))), 
   String = "abcde".
      

[jjtolton]

There is the assoc module, which would allow you to create things like "objects" (or data containers, anyway). I assume at some point I will need it but it hasn't happened yet!

Actually, that gives me a pretty good idea for something I'm working on... 🤔

Had another discussion about them a few days ago where I was trying to figure how how to test for a key

[hurufu]

There is a logic OO language LogTalk, it is very mature and has a lot of libraries and it even runs on top of Scryer Prolog.

[jjtolton]

Whoa. Wait a minute. LogTalk came out in 1998. I'm no math expert but I think might predate Scryer by a few minutes at least. Does that mean that LogTalk can run on any isocompliant prolog? Do you have a link to how to do that? Maybe?? 😍

[jjtolton]

We need to update the "Prolog back-end compatability" section of the wikipedia article if this is true! I see our cousins Trealla in there!

IT IS IN THERE!

[bakaq]

Just a correction, LogTalk actually doesn't support Scryer Prolog as a backend anymore since version 3.71.0, because politics basically. Scryer Prolog uses the last supported LogTalk version in the test suite. From what I investigated from the LogTalk codebase, putting the support back is not that hard (although it won't have any new features that it didn't support before), and I've been thinking recently about making a fork that does that so that we can at least benefit from the LogTalk's latest version test suite until it supports Scryer Prolog officially again.

[UWN]

Is really objects what you are so much interested in? Recall that messages are a slightly more polite form of a command. (Just as the question "Did you get the message?" just means "Objey the command") And a command implies state. It is possible to simulate state somewhat in Prolog, but the dilemma you face is this: Either the state is explicit, then your OO-ish programs look rather awkward or you devise a formalism to hide it, but the you mostly lose the nice algebraic properties.

[haijinSk]

Personally, I don't use OOP (whatever that means), for my small things, even if a language supports OOP and I have a better imagination for a functional programming way, though not exactly for the Haskell way of FP.

Yet... My intuition (of course, after studying ideas of others) is that a proper use of the OOP idea, a la Alan Kay: computation by exchange of messages between objects and "then to try to eliminate [assignment] altogether" (so: recursion and value/immutable objects; not the mainstream OOP) is not very different from FP.

[jjtolton]

Is really objects what you are so much interested in? Recall that messages are a slightly more polite form of a command. (Just as the question "Did you get the message?" just means "Objey the command") And a command implies state. It is possible to simulate state somewhat in Prolog, but the dilemma you face is this: Either the state is explicit, then your OO-ish programs look rather awkward or you devise a formalism to hide it, but the you mostly lose the nice algebraic properties.

It's not the message passing, it's easing the maintenance burden that I'm looking for and lowering the cost for exploratory development. For instance, the OO technique of "Composition" allows for adding behavior to an object via template. It's a technique that works well for smaller medium sized projects, particularly when good compiler support is available. Monads are another option, but those are a extremely difficult idea to get right without compiler support.

In practice, I encounter the following situation most of the time -- Concept A, Concept B, and Concept C all share 90% of the same behavior. Concept A and B share 95% of the same behavior (or the same "relations", in a logical implementation). The remaining 5% and 10% is significantly different, even if it is semantically similar. Think for instance, writing to stdout vs writing to a database. It would be extremely unfortunate if you needed to copy/paste a 90% of the code for concepts A, B, and C and then write extreme hacks to compensate for the other 10%.

Sometimes it's ok if you only have to do it once, but if you have to do it multiple times, such as adding large chunks of new behavior, this becomes problematic quickly.

In the case of Scryer, this is going to be incredibly important, because behavior in the browser and behavior on the server can be completely different. You cannot have blocking behavior on the browser, you must use callbacks. That makes the difference between writing to the console or writing to a database (or making an API call) very, very different concerns, and even traditional OO composition AND monadic techniques fail here because they do not account for differences in the runtime environment.

Now, there are so many techniques in Prolog I do not yet know about that I am sure there are amazing answers for encapsulation and "programming in the large", i.e., 5th generation systems, but they are not covered in any of the resources I have access to.

It's also hard to think about programming in the large when, as I am, I am still learning the the techniques of programming in the small.

[jjtolton]

As an aside:

Actually, it is this very problem which attracted me to Prolog in the first place. I deal with this problem on a day-to-day basis, because I write runtime isomorphic Clojure and ClojureScript for server and browser. But the system I am developing is complex enough that I am reaching the limitations of what can be done with this lisp, it was not designed to handle the problem I described above. That's when I began researching DCG's and came across @triska 's videos.

With DCGs and DSLs I think I see an answer to the problem, because (on paper) DCGs should make it easy enough to write a language (and compiler) to handle this problem in a runtime agnostic away (provided you are a competent enough Prolog developer, which I am not yet). This is a very untested hypothesis, however. Actually, @UWN, part of the reason I think this may be a viable approach comes from your answer in another thread, and also from discussions I've had with @triska which indicate the only reason that DCGs are not more widely used for compilers is because up until Scryer, there have been no open-source, isocompliant versions of Prolog which efficient string processing. And now with the new rebis-dev and the closing of #1714, I am feeling even more confident about it!

[hurufu]

My 5 cents, I think that "programming in the large" in Prolog is such a large and highly debated topic that it isn't really possible to answer it in a single post. Prolog already offers the richest form of polymorphism invented. Do you really need object orientedness in Prolog? I personally don't think so.

[bakaq]

Julia handles multiple-dispatch quite nicely in my opinion. Julia has dynamic (optionally static) but quite strong types. I also tend to prefer very strong type systems (Haskell, Rust, Elm) precisely because they make refactoring not feel like a minefield. When I use dynamic languages I tend to use gradual typing if it's available (Python, Typescript, GDScript), but in my experience these gradual type systems are extremely complex and very brittle. By it's very nature I don't think Prolog could be meaningfully typed in a way I would like, which makes me a bit sad.

[jjtolton]

Thank you very much for the response. I thought (in my imagination about how I want to program in a FP way) that, if not Haskell, then, for example, OCaml; in a word, algebraic data types; in regard to the compiler-will-check-my-editing-and-every-change-everywhere, so to speak, and as a program design tool. And, of course, Ocaml has first-class modules.

ADTs work exceptionally well when you have strong compiler support, they are my second favorite style of composition. They have a few issues which are difficult to overcome:

1. They are typically tied to a single runtime (i.e., don't cross-compile to javascript). This may or may not be something you care about, but it matters a lot to me.
2. They don't usually solve business problems like "I want to add analytics to everything", "We are switching databases", "we are switching frameworks", "we are switching programming languages", etc.
3. Flow control is not usually reified in the type system, especially if across runtimes (i.e., synchronous on the server but asyncronous in the browser)

And yes I actually do think that Scryer Prolog is an answer to all of these problems :D

1. They are typically tied to a single runtime (i.e., don't cross-compile to javascript). This may or may not be something you care about, but it matters a lot to me.

This is the entire reason I am working on the embedded version of Scryer!

2. They don't usually solve business problems like "I want to add analytics to everything", "We are switch databases", "we are switching frameworks", "we are switching programming languages", etc.

I believe that Prolog has the facilities for this, though I'm still learning them. The heavy hammer that originally brought me to Prolog was using DCGs to make a DSL that allows the compiler to solve these problems, but I'm becoming spoiled by the nice facilities Prolog has too. Regarding "switching programming languages", the embedded version also allows you to switch to any programming language (that supports FFI, which is most major languages), but you get to keep Scryer!

3. Flow control is not usually reified in the type system, especially if across runtimes (i.e., synchronous on the server but asyncronous in the browser)

Prolog doesn't have flow control, so nothing to worry about! But also this is something that can be handled via compilation and interpreters, from points 1 and 2 above.

[jjtolton]

However, in regards to this discussion, I AM wondering "what is the ADT equivalent in Prolog"!

[haijinSk]

However, in regards to this discussion, I AM wondering "what is the ADT equivalent in Prolog"!

Edit: I read "ADT" as "algebraic data type" at that moment (vs. "abstract data type" possibility).

"[...] If these ideas seem new or confusing, you can’t go wrong with an analogy: the world of Prolog data is like one big algebraic data type.

• An atom is like a nullary value constructor, just like nil or NONE in ML.
• A functor is like a value constructor that takes one or more arguments, like SOME or cons in µML.
• A Prolog term is like a value of algebraic data type.

Prolog terms even participate in a form of pattern matching, just like ML values of algebraic data type. Only the concrete syntax is different. [...]"

Norman Ramsey: Programming Languages - Build, Prove, and Compare, 2022 - The Supplement, [PDF]

[jjtolton]

Julia handles multiple-dispatch quite nicely in my opinion. Julia has dynamic (optionally static) but quite strong types. I also tend to prefer very strong type systems (Haskell, Rust, Elm) precisely because they make refactoring not feel like a minefield. When I use dynamic languages I tend to use gradual typing if it's available (Python, Typescript, GDScript), but in my experience these gradual type systems are extremely complex and very brittle. By it's very nature I don't think Prolog could be meaningfully typed in a way I would like, which makes me a bit sad.

You can actually use multiple dispatch in Python, in conjunction with the type system. Inspired by Haskell and Clojure, I wrote up a multidispatch library to do it awhile ago. It uses Haskell style ADTs to implement polymorphic dispatch over the most important Clojure functions and it patches the default Python datastructures to use them.

It is really fun. But it's also how I learned the hard way it can also lead to really bad code, because when any function can do anything, without compiler support it can be really difficult to figure out what's going on or to change things. That's when I started staying closer to the core abstractions of the language I'm working in.

So, if you want to program like Haskell... use Haskell. If you want to program like Clojure... use Clojure. If you want to program like Prolog... well, I'll let you know when I figure out how to program in Prolog haha 😅