Web Prolog - a multi-paradigm language?

[torbjorn.lager]

@j4n_bur53

The only thing one should keep in mind, is that Prolog predicates are non-deterministic and not functions. So Erlang stripped non-determinism from its execution model. It might be that non-determinism has some new challenges in stock.

Yes, that might be a problem, but don’t think it is. So far, my investigations have shown, at least to my own satisfaction, that it’s remarkably easy and feels very natural to extend Prolog with features from Erlang, or, if you want, to combine the logic programming model of computation with the actor programming model.

Here’s an example from the manuscript which didn’t fit in the Erlang’19 paper. It shows how a tiny yet fairly generic encapsulated search predicate can be implemented on top of an actor in Web Prolog. It doesn’t have all the features a “real” pengine has, but it shows, quite nicely I think, how easy it is to build such a thing on top of an actor:

search(Query, Pid, Options) :-
    self(Self),
    spawn(query(Query, Self), Pid, [
        monitor(true),
        src_predicates([query/2])
        | Options
    ]).
    
query(Query, Parent) :-
    self(Self),
    call_cleanup(Query, Det=true),
    (   var(Det)
    ->  Parent ! success(Self, Query, true),
        receive({
            next -> fail;
            stop -> 
                Parent ! stopped(Self)
        })
    ;   Parent ! success(Self, Query, false)
    ).

We don’t have to assume that the implementation is available at the remote node. Instead, by passing the src_predicate option, we send the predicate query/2 along for injection into the workspace of the process. Here is an example of how search/3 can be used to query a remote node:

?- search(p(X), Pid, [
       node('http://remote.org')
   ]).
Pid = 1879876@'http://remote.org'.

?- flush.
Shell got success(1879876@'http://remote.org', p(a), true)
true.

?- $Pid ! next.
true.

?- flush.
Shell got success(1879876@'http://remote.org', p(b), true)
true.

?- $Pid ! stop.
true.

?- flush.
Shell got stopped(1879876@'http://remote.org')
Shell got down(1879876@'http://remote.org', true)
true.

?-

Note that the code for search/3 does not say anything about what should happen if an exception is thrown, which would for example be the case if the predicate called by the goal is not defined. But since the spawned process is monitored, the error message will eventually reach the mailbox of the spawning process anyway, in the form of a down message. The same is true for failure.

The key here is the receive/1-2 predicate and the decision to make it semidet, allowing it too fail if the body of one of its receive clauses fails. Here’s what I say about the much smaller examples in the paper:

The tiny examples in this section highlighted a vital feature of the Web Prolog design as they showed how Prolog-style search and Erlang-style concurrency can be integrated and how a non-deterministic query can be supplied with a deterministic interface. This is precisely the point where the logic programming model and the actor programming model – represented here by Prolog and Erlang – interface with each other. This suggests that Prolog’s backtracking mechanism is perfectly compatible with, and in fact complements, the proposed Erlang-like mechanisms for spawning actors and handling the communication between them.

Of course, since pengines are available, you don’t have write your own solver.

So, does Web Prolog deserve to be called a multi-paradigm programming language then? Yes, why not, because in the very nicely organised and very well argued taxonomy of programming paradigms by Peter van Roy, as seen below, it is indeed possible to pinpoint exactly where Web Prolog fits in. I have enclosed the relevant boxes in boxes with rounded corners. (The original diagram, with explanations, is available here, and a book chapter, with even more explanations here.)

With access to predicates for asserting and retracting facts in the dynamic database, traditional Prolog has always been able to support imperative programming (and later additions such as setarg/3 has of course amplified this). Thus Prolog has never really been a single-paradigm programming language, and this is reflected in van Roy’s taxonomy. With the addition of support for the actor programming model, Web Prolog becomes a much clearer as well as (in my view) a more interesting example of a multi-paradigm programming language.

[j4n_bur53]

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

[torbjorn.lager]

@j4n_bur53

One problem with the actor model, irrespective whether you add it to logic programming or something else, is the debugging of actors. Since the state is in the parameters, taking SWI-Prolog as an example, you need at least the following features in the debugger:

• Thread Attachment: It might be helpful if you can control debugging on the level of threads or whatever that drives the actors.
• Variable Display: You need to be able to see the variable bindings of actors. Otherwise you don’t see the state that an actor has.

I don’t know whether there is some research or practice that confirms this. The usual SWI-Prolog debugger might be fit or unfit for actor debugging. I am currently working on a thread monitor, which should simplify both requirements by easy graph drill down.

I agree about the need for tools for debugging and monitoring of pengines and other actors. The developers of Erlang and Elixir have developed such tools, which we could perhaps at least get inspiration from. However, I tend to think that they might not be very relevant for a language such as Web Prolog and a platform such as the Prolog Web. My first idea would be to take SWI-Prolog’s debugger as a reasonable point of departure, but not the usual one – I think I would prefer to start from the one available in SWISH.

Because I believe such tools should be web-based. I’m pretty certain this will pay off in the end.

I’m not sure what you mean by “control debugging on the level of threads or whatever that drives the actors”. I think debugging should be done on the level of Web Prolog. A variable display seems useful, and something similar to a thread monitor, but for actors. Being able to inspect an actor’s mailbox might also be useful.

If authorised, or depending on the node’s setting, you should perhaps be able to enter into code that is stored in a node’s index.pl file, regardless of if you are the node´s owner or not. This file defines the predicates that the node makes available in addition to the built-in ones. These predicates might call other predicates that you are not allowed to enter into, since the owner of the node has decided that you shouldn’t be. (I’m just playing here with an half-baked idea for how a node can be structured. )

[torbjorn.lager]

@j4n_bur53

So while I was thinking about debugging actors, I could recall another programming model, which is also quite successful in programming concurrent systems. Its not so well known, since its not from the 3 Amigos, its from another OO professional Peter Coad.

The idea is there to do class design of so called “moments”:

https://en.wikipedia.org/wiki/Object_Modeling_in_Color

You can imagine that a “moment” is a working area, which will hold the receive parameters and references to the actor states. Since the working area is a class, it has class methods which then serve as the receive body. You can use all OO modelling on moments like subobject aggregates, and thus combine behaviour.

I would like to have this in Prolog, but I did not yet find a suitable way to do it. Neither Logtalk nor my own ISO module based objects satisfies me here. The nice thing when doing “moments” in Java is the Java garbage collection. So you just call the methods of the “moment”, fire and forget, and its like last call optimization.

“moments” would be easier to debug and more self descriptive. Since one would debug objects which belong to a class. I don’t know where this methodology is located in the diagram. I wrote my shop system http://www.jekejeke.ch/ with this modellig approach. All the server behaviour is programmed as higher level moments using Peter Coads methodology.

There are also lower level moments to access the database, which is usually known as DAO. Also IBMs SOA is often implemented this way using layers of moments. Further I have the feeling that somehow moments have a little revival. A lambda closure is typically a moment, and for example parallel Java streams under the hood basically use also moments.

But as I wrote, I couldn’t bring it yet to Prolog.

That might be a nice programming model to base a language on, but this language is, I suppose, not likely to look like Erlang. This is a quote from my paper, something Joe Armstrong wrote in a personal communication last summer after having read the manuscript:

Reading the code was fun – I had to do a double take – was I reading Erlang or Prolog – they often look pretty much the same.

In my opinon, the fact that Web Prolog looks, and in many, many cases behaves, just like Erlang, should be seen as a big plus for the language. It means that Prologers may be able to start learning the Erlang-ish aspects of Web Prolog programming already now, just by reading Erlang textbooks, and it means that Erlangers might become interested in using the language.

So why don’t you switch track and focus on something that probably can be brought to Prolog, namely Web Prolog? I bet you could implement a prototype in your Jekejeke Prolog using Java libraries for WebSocket communication and HTTP and such things in no time. Just an idea…

As regards methodology, Erlang DNA comes with a way of thinking and a software development methodology which I believe would work for Web Prolog, and which is nicely captured in the following quote from Armstrong’s Ph.D. thesis:

Our applications are structured using large numbers of communicating parallel processes. We take this approach because [… I]t provides an architectural infrastructure – we can organize our system as a set of communicating processes. By enumerating all the processes in our system, and defining the message passing channels between the processes we can conveniently partition the system into a number of well-defined sub-components which can be independently implemented, and tested.

It is also captured by the following description of a workflow (found in this book by van Roy and Haridi):

1. Informal specification. Write down a possibly informal, but precise specification of what the system should do.

2. Components. Enumerate all the different forms of concurrent activity in the specification. Each activity will become one component. Draw a block diagram of the system that shows all component instances.

3. Message protocols. Decide on what messages the components will send and design the message protocols between them. Draw the component diagram with all message protocols.

4. State diagrams. For each concurrent entity, write down its state diagram. For each state, verify that all the appropriate messages are received and sent with the right conditions and actions.

5. Implement and schedule. Code the system in your favorite programming language. Decide on the scheduling algorithm to be used for implementing the concurrency between the components.

6. Test and iterate. Test the system and reiterate until it satisfies the initial specification.

That’s probably another sign of a new paradigm; it brings with it a new software development methodology.

[j4n_bur53]

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

[torbjorn.lager]

Looks like a nice tool!

[torbjorn.lager]

Noticed the tag? Because now I think you’ve drifted from the topic of this thread…

[j4n_bur53]

(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)

[torbjorn.lager]

Ok, fair enough. Thanks.

[pmoura]

@j4n_bur53

If you do this in Logtalk you need to manually dispose objects, it does not have a garbage collection like Java.

P.S. Garbage-collecting of Logtalk objects makes as much sense as garbage-collecting of Prolog modules.

[pmoura]

In Logtalk, instance is just a role that an object can play. But as this is clearly off-topic and there’s plenty of documentation explaining Logtalk fundamentals, I will not pursue a discussion about this here.

[torbjorn.lager]

@j4n_bur53

@torbjorn.lager I suggest moving the “debugger” posts to the other “debugger” thread. Somehow it got me thinking that you want to discuss paradigmas. But a debugger is not a paradigma, only a tool.

I would have been ok with you leaving that post here. I’m not against dealing with debugging tools under the paradigm “umbrella”. They are related to methodology, which in turn is related (I would say) to paradigms. It’s been many years since I read Thomas Kuhn’s The Structure of Scientific Revolution, from which the term spread to computer science I believe… Sure enough, I googled and found this, so here’s a clue:

Science historian Thomas Kuhn used this term in his influential book The Structure of Scientific Revolutions to describe a set of theories, standards, and methods that together represent a way of organizing knowledge, that is, a way of viewing the world.

Robert Floyd used the term in his 1979 ACM Turing Award lecture, “The Paradigms of Programming”. A programming paradigm is a way of conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer.

---

@j4n_bur53

How would you define paradigma? There is no English wiki for it?

I’m fine with the above definition, and I don’t think there is a precise definition with which everyone agrees. But if you follow the links I gave above to van Roy’s work, you’ll see that there’s a lot more to say about them than what’s reflected in the above definition.

And yes, there is a Wikipedia article about it: Programming paradigm - Wikipedia

Personally, I’m just going to keep on claiming that if we add actor-based programming to Prolog, then what you get is a dialect of Prolog which supports an additional way of “conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer”. And by doing so, Prolog doesn’t become less of a logic programming language. It doesn’t become more of a logic programming language either – the logic stays the same. What does happen, I think, is that Prolog becomes more of a multi-paradigm programming language than it was before.

But I would also say that for a good result, the kind of actor we should be adding to Prolog should be the same kind of actor that Erlang has – the kind of actor that has a mailbox, and the kind of actor that has a selective receive operation. (If I remember well, the original idea of an actor introduced by Carl Hewitt didn’t have those things).

Quite frankly, if we want to develop a new dialect of Prolog which is suitable for both concurrent and distributive programming, it would be crazy not to exploit the close affinity between Erlang and Prolog, an affinity due to mainly historical reasons. And for a web programming language, distribution is of course of utmost importance. The Web is the biggest distributed programming system ever constructed, and although I may be naive, I happen to believe that Prolog, through something like Web Prolog, can improve upon it.

[torbjorn.lager]

@j4n_bur53

I also don’t understand your search example. One thing I am reading off, is that src_predicate/1 would ship a predicate. Right? Like all clauses that belong to the given predicate indicator?

search(Query, Pid, Options) :-
    self(Self),
    spawn(query(Query, Self), Pid, [
        monitor(true),
        src_predicates([query/2])
        | Options
    ]).

But with this here, you can easily generate a stale pengine, if the client aka parent forgets
$Pid ! stop.

query(Query, Parent) :-
    self(Self),
    call_cleanup(Query, Det=true),
    (   var(Det)
    ->  Parent ! success(Self, Query, true),
        receive({
            next -> fail;
            stop -> 
                Parent ! stopped(Self)
        })
    ;   Parent ! success(Self, Query, false)
    ).

Yes, although instead of “shipping” I use the term “code injection”. (Someone might be able to come up with a better term.)

And yes, I agree that if the parent forgets to send stop to the “pengine”, it will become “stale” – unless of course the parent: 1) sends next, or 2) later remembers to send stop, or 3) the remote node kills it because it’s been around to long, or 4) a programmer decides to add a new features to the “pengine”, like so for example (not tested!):

search(Query, Pid, Options) :-
    self(Self),
    spawn(query(Query, Self, Options), Pid, [
        monitor(true),
        src_predicates([query/3])
        | Options
    ]).

query(Query, Parent, Options) :-
    self(Self),
    call_cleanup(Query, Det=true),
    (   var(Det)
    ->  Parent ! success(Self, Query, true),
        receive({
            next -> fail;
            stop -> 
                Parent ! stopped(Self)
        }, Options)
    ;   Parent ! success(Self, Query, false)
    ).

Given this change, the soon-to-become-parent may pass the timeout option to search/3 like so:

?- search(p(X), Pid, [
       node('http://remote.org'),
       timeout(10)
   ]).

If the parent now forgets to send stop, the “pengine” will terminate anyway after ten seconds.

Of course, as I wrote above, you should never have to write your own “pengine”. In Web Prolog, real pengines are already available.

[torbjorn.lager]

I’m sorry, but I don’t follow. I simply don’t see the problem with pengines you seem to have in mind, and for which you appear to be looking for a solution. Can I ask you to state the problem again, as clearly as possible?

[torbjorn.lager]

@j4n_bur53

I don’t think its a pengines problem. Pengines is low-level with its own state machine. I was refering to your web Prolog high-level solution, which has spawn and that equals to a go-routine call.

What do you mean by my “Web Prolog high-level solution”? Are you referring to the rpc/2-3 predicate? If so, please note that while it’s true that this predicate can be implemented on top of pengine_spawn/1-2 and friends (which may have problems unless we control all the machines remote pengines are running on), there’s also an alternative (albeit less elegant) implementation using the stateless/RESTful HTTP API as transport. (I’ve already shown it to you.) I’ll say more about this latter implementation in a post later tonight or tomorrow, and why I think it might, due in part to the multi-core hardware revolution, be scalable to the extent that we might, at least in principle, be able to wrap the whole Web in a layer of Prolog.

@j4n_bur53

Structured programming itself is a programming paradigma. Maybe it is asked too much, to bring structured programming also to distributed programming. But this is kind of the vision I would like to folllow.

So, your response to my request for comments on Web Prolog is a description of your own vision? For how long have you been working on your vision, and what do you have to show for it? I’ve been working on my vision for almost 5 years, I’ve written hundreds of pages of text describing it, I’ve published a paper in an Erlang workshop that describes it, I have (with Jan Wielemaker’s kind help) written a proof-of-concept implementation and a tutorial that comes with it. With SWISH, backed by library(pengines), some aspects of my vision has been realised in a system which sometimes have more than 1000 concurrent users, but I still think more can and should be done in order to fulfill the promise that it shows.

I’ve appreciated your comments so far as they have kept the conversation going and has allowed me to sharpen my arguments and correct some of the misunderstandings that can arise. But can you please, please try to be a bit more focused in your comments in the future and refrain from peddling your own vision in my thread? Ok?

[torbjorn.lager]

@j4n_bur53

About the term “function shipping”. You can pick up the term “function shipping” at different places. It can mean marshalling a function and then injecting it.

Ok, so in the context of Prolog that would be “predicate shipping” then. Yes, thank you, that might be an alternative.

[torbjorn.lager]

From what you wrote, I got the impression that your vision is about the use of structured programming as a paradigm for distributed programming. To be on topic, your comments has to be about Web Prolog, and about Erlang-style distributed programming in Prolog. This cannot, as far as I can see, be classified as structured programming. As I said, I appreciate your comments, I really do, but please try to stick to the topic.

Comments of the form “your approach can never work, because …”, or “this might work, but why don’t you … instead?” or “what you write in section X.Y seems wrong because …” are most welcome. Despite having worked so long on this, I don’t pretend to have come up with something which is completey free of mistakes or crucial omissions.

What I’m proposing, and what I’m trying to demonstrate throughout my posts, is that Erlang-style message-passing concurrency and distribution mixes very well with Prolog. And on a more abstract level, I’m trying to convince you (as well as myself) that the addition of the actor programming model to the other programming models Prolog supports (such as logic programming and constraint programming) doesn’t leave us with an ugly kludge, but with something quite beautiful (in my admittedly subjective opinion). In the context of the current topic I just wanted to point out that if I’m right, it means that Prolog could become even more of a multi-paradigm programming language than it’s usually considered to be.

[torbjorn.lager]

This will be my last post in this topic. But since you bring up the distinction between asynchronous and synchronous communication, I just want to point out that in the actor model, messaging is asynchronous by definition, and both Erlang and Web Prolog adhere to this mode of communication. For Web Prolog, it’s easy to see this in the shell, since when you call !/2 or predicates built on top of it, you are returned to the ?- prompter immediately and can do other things while you wait for any results to arrive to the mailbox of the top-level process.

Synchronous messaging can be built on top of the asynchronous send and the blocking receive. The rpc/2-3 predicate, for example, is a synchronous construct.