C Plus Prolog | Hacker News Reader

C Plus Prolog

github.com

177 pointsmpweiher53 comments

If you like this stuff, consider how to "implement" JSON in Prolog:

    :- op(400, yfx, :).
    ?- JSON = {
      a: 1, b: "a string",
      c: { d: "a compound" }
    },
    JSON = { a: X, b: Y, c: { d: Z }}

Basically, you don't ;) all we did here is declaring ':' as an infix operator. The next lines bind/unify a term to the var JSON, and the last line is again unification in action (basically destructuring on steroids), binding the vars X, Y, and Z to the respective value 1, "a string", and "a compound" from the previously bound JSON var.

You can paste this snippet into [1] and execute it right in your browser to check that indeed X, Y, and Z are bound as described if you wish.

Not that it matters that much. Prolog is really for indeterministically searching a large/infinite space such as in planning (and yes it can be used for theorem proving and program verification as well). It's always fun to see newcomers trying to implement pointless low-level stuff such as list primitives when coming from a functional programming background or even getters/setters.

[1]: https://quantumprolog.sgml.net/browser-demo/browser-demo.htm...

> Prolog is for indeterministically…

One side note here. Yes you can do indeterministic search but it’s not a property in Prolog. In fact, Prolog execution is completely deterministic without use of randomization.

But I guess that in some domains (e.g. optimization) people would rather shuffle numbers than do a boring 1…1000000000 loops.

The search order is neither indeterministic, nor deterministic; it is undefined. Some implementations do depth-first search, others go random.

If your code is logically correct, it doesn't matter in the end - except if you use the cut-operator which essentially says 'don't look any further, just go with the first match', which will behave (in)deterministically based on the implementation.

>> Prolog is really for indeterministically searching a large/infinite space such as in planning (and yes it can be used for theorem proving and program verification as well).

I'd say theorem proving is what Prolog "is really for", in the sense that it's a language whose interpreter is an automated theorem prover.

It just so happens that a (first-order) theorem prover is the best tool to explore an infinite space, if it's worth its salt, because that's what it has to do in order to find a proof in the first place.

And of course you can cast all sorts of combinatorial problems like planning and verification as proofs (this sequence of actions reaches this goal state from this starting state).

Edit: incidentally, it's so dumb that the standard for pattern matching in the industry is regexes, with their insufferable, cryptic pandemonium of notations, rather than Prolog, which has got to be the language with the simplest possible syntax in all of computer science this side of Brainfuck. When I was doing my NLP homerwork during my MSc I kept writing small ad-hoc parsers that were all balls of mud around a bunch of regex scripts, and I longed for the simplicity of Prolog and its DCGs (I couldn't use Prolog because the homework was in Python and at the time there was no Janus). Why do programmers do that to themselves?

Long time ago I was obsessed with Prolog. I found that if you bend it enough you could implement imperative code (a-la JavaScript) evaluation, still being valid Prolog:

https://github.com/xonixx/prolog-experiments/blob/main/Prolo...

This was super funny, but obviously absolutely useless

Why do you say that? Imagine you wrote a language that looked procedural but was actually relational underneath? We could get rid of so much glue and use unification when it made sense and ignore it otherwise. That’s a great idea

Sounds similar to Haskell "do" notation where it can look procedural, but backed by FP principles and tools.

(Something something monads are sequentialness)

Does anyone know if Prolog is useful for creating a schedule for workers with many constraints? I have a comment somewhere where I included the constraints but I have forgotten most of it by now. Constraints like minimum of 2 workers for both morning and night shifts, all workers must have 2 days off at least in a week, so no consecutive 3 days work, etc. The number of workers would be defined with names as well, etc. The goal would be to create a monthly schedule. I tried to come up with one but I may have messed up the constraints because it took too long (it got stuck, actually), maybe the constraints were too tight, I don't remember. If not Prolog, then what would be the best way to do this? I am interested in FOSS.

I wish there was a way to search for my comments, it sucks that I would have to paginate. I left a lot of comments.

You could have a look at the potassco suite[0]. It is a grounder and solver for Answer Set Programming (ASP). ASP is a form of Logic Programming.

[0] https://potassco.org/

I will take a look at it. Are you familiar with it, an example or a snippet would come in handy, but I may just ask Claude (if it even knows about Potassco).

ASP is optimized for combinatorial problems. Basically, you list the parts that are variable, and the constraints, the answers are given by the solver. Have a look at the documentation[0]. Here is an example:

    % Each shift needs a nurse).
    1 { shift_nurse(Shift, Nurse): nurse(Nurse) } 1 :- shift(shift).

    % It cannot be that a nurse does two shifts in a row.
    :- nurse(Nurse), shift_nurse(Shift1,Nurse),shift_nurse(Shift2,Nurse), Shift1 + 1 = Shift2.

[0] https://potassco.org/doc/start/

Thanks.

Found the original comment: https://news.ycombinator.com/item?id=41756679

Would this still work with ASP?

Yes, but honestly if you can use specialized software instead of writing your own, do so. Scheduling problems become very hairy quite quickly. For ASP, there is also sCASP that is the current flagship application of SWI Prolog.

Yes, you could do this and it's likely it'll turn out as rather nice and decently performant code. You would, however, most likely run into the problem of finding people to maintain it that are willing to learn. Most Prolog teaching material is quite abstract in the sense that it mainly teaches the language and its tricks, not so much applications, though there are of course a lot of FOSS and example applications to look at.

In practice you would have to write documentation that basically turns into a course on constraint solving in Prolog. There are footguns and somewhat advanced techniques involving control over the execution strategy that are going to trip up newcomers. You'll also have to figure out how to interface with a Prolog implementation.

A compromise might be to use bindings for Z3 or something like the Timefold solver, https://timefold.ai/open-source-solver. Either way it's a good idea to spend some time playing around with Scryer, https://www.scryer.pl/, and Markus Triska's crash course, https://www.metalevel.at/prolog. SWI-Prolog has more conveniences that might make it more suitable for practical applications, but being used to them might make it harder to adapt to e.g. Scryer, Tau or some other implementation.

There's also the Mercury language, it's weirder but also very interesting, https://mercurylang.org/.

Edit: Some people swear by Picat but I have very little experience with it, http://picat-lang.org/.

Prolog is definitely the tool for this. I created an entire year's schedule for teachers a decade ago without a sweat. Maybe remove some constraints and try to debug which one is causing the problem.

Is it open source? Is the code available anywhere?

Oh no, it is in an undergrad thesis probably rotting in some library.

Try Z3

yes[1][2]. You can write Prolog schedulers with arbitrary constraints.

[1]: https://www.metalevel.at/prolog/timetabling/

[2]: https://github.com/mthom/scryer-prolog/discussions/2519

So something like this: https://news.ycombinator.com/item?id=41756679 can be created using this?

I really need to learn Prolog. It looks interesting and powerful, but it's different enough form most languages that I'd need to actually sit down and learn it and how to write useful stuff with it.

At a superficial level, it looks a bit like Z3, which I do have some experience with, but I suspect that there's a lot of intricacies to Prolog that don't apply to Z3.

Prolog feels like magic, and it well worth learning. It is a general purpose programming language rather than a very specific purpose tool like Z3.

Sadly non-'pure' logical programming is required to get real-world performance (eg. cuts that prune the search tree) which kind of feel like, or is, a leaky abstraction that breaks the magic.

I have had good success in solving logical problems by asking o1 to produce prolog programs.

If you learn modern prolog techniques, cuts have become less and less necessary.

Can you point to some resources that show this? Are there new facilities that make cuts fewer? Are there more accepted idiomatic ways published for different kinds of problems?

I learnt Prolog a long time ago and would like to start from scratch.

There is a web site that shows how to use modern techniques to make Prolog less procedural:

https://www.metalevel.at/prolog

> Sadly non-'pure' logical programming is required to get real-world performance (eg. cuts that prune the search tree) which kind of feel like, or is, a leaky abstraction that breaks the magic.

They aren’t required but are convenient. Excuse brutalizing syntax and formatting but in Prolog you can do:

  A(X) :- between(1,3,X).
  B(X) :- between(1,1000,X).
  ?- A(X), B(X).
  ?- B(X), A(X).

And get either 9 visits or 3000. It’s possible to design a program without cuts but (in my opinion) it’s very hard and doesn’t bring any benefits outside of street cred.

Also cuts and pruning long time ago felt like bloated terms (when I didn’t get Prolog) whereas it’s a simple break equivalent in imperative languages loops.

I have solved some logic problems using Prolog, but Prolog is neat for text-based adventure games, too.

SWI Prolog has great libraries, BTW.

I wonder if it is still the case that the most widely-used Prolog app in the world was the solver for network stack configurations in Windows NT?

https://web.archive.org/web/20040603192757/research.microsof...

There's nothing wrong with the cut, or with getting more control over the execution of your program, which is what the cut gives you.

You only get in trouble with the cut when you're just starting out and don't know what you're doing, and write your code in a way that it keeps entering infinite recursion or backtracking until the cows come home. At that point, because you don't yet know how to control those behaviours, you start sowing your code with cuts all over the place, which maybe stops the backtracking and infinite recursion (but maybe not) but it makes it an incomprehensible mess that still doesn't do what you want it to do.

As you grow and learn, you figure out how to control backtracking and recursion by ordering your program clauses and your clause literals in a sensible manner. At that point the use of the cut becomes so regular and formulaic that it might as well be added in by a pre-procesor.

For instance, you want a program that walks over a list and modifies an element if a condition holds, otherwise it continues, until the list is empty. You write:

  % Program "skeleton" not meant to be executed but to expose a pattern

  modify_list([],Xs,Xs):- 
    ! % We're done, stop trying
  modify_list([X|Xs],[Y|Acc],Bind):-
    modify_element(X,Y)
   ,! Don't re-process X!
   ,modify_list(Xs,Acc,Bind).
  modify_list([_X|Xs],Acc,Bind):-
    modify_list(Xs,Acc,Bind).

In the example above, the two cuts have a very clear reason to be where they are (they stop unnecessary backtracking) which is immediately obvious by eyballing the program with sufficient experience. The vast majority of the use of cuts in the code you write once you have a bit of experience and understanding of how Prolog works is like that.

Z3 is entirely different IMHO, once you get into solvers the question becomes not just 'is this satisfied' but 'what is the minimum sequence of steps necessary to arrive at the result'.

I have relied heavily on both Z3 and Alloy for ad-hoc jobs, and Prolog doesn't even come close to the inference power, and that's along-side Macsyma and Sage.

Have you tried sCASP?

What problem domain are you working in? I find usage of solvers and Prolog to be very domain specific.

At the moment I'm verifying a Rust floating point implementation, which has lead to many small snippets for not just generating test & edge cases (e.g. find inputs which falls outside of these conditions), but trying to prove completeness on all valid inputs.

The big advantage of prolog vs solvers is the logic programming aspect. If you can express parts of your program in a logically pure way, Prolog code will be much more concise than the Z3 equivalent, although probably slower. Another advantage is that Prolog outputs and reads Prolog terms, which makes it very good for metaprogramming. It's like lisp: incredible if you're solo prototyping, not so much if you're part of a team of corporate cogs.

Most better prologs now include solvers already.

Interesting timing...

I've just made something similar but with JS: C modules in JS.

    import * as CModule from "./module.c";

C module gets compiled to native code on load. I think that clear separation of execution models is a good thing.

https://sciter.com/c-modules-in-sciter/

https://sciter.com/here-we-go/

> I call it, “C Plus Prolog”, or “C+P” for short.

Missed the chance to call it CPP.

Would confuse it with the Canadian pension plan :^)

That was likely intentional because CPP is one of the many terms used for C++.

[GIF] That's the joke. [/GIF]

My first thought was 'why invent templates when you can use prolog' and turns out the author has similar observations.

I've been thinking over the years how to make prolog more useful. The primary constraint I have is not syntax or expertise, it's how to embed a useful prolog in a 'modern saas microservice' if you will. From what I can gather, this is not being done in the open; perhaps some closed products do it. It's telling that it's much easier to embed Z3 than prolog...

> it's how to embed a useful prolog in a 'modern saas microservice' if you will.

Incidentally this is something I've looked at long time ago and things pointed at SWI Prolog https://www.swi-prolog.org/pldoc/man?section=embedded

The target language for my case was embedding within PHP, that would have meant enough expertise to embed the interpreter, hook it into the PHP runtime, and expose it in the language through some interface. Way over my skill level. Should be certainly doable with any language that can interface at the C language level.

Is that not what Picat is all about? Imperative + Declarative Constraint Programming

[0] http://picat-lang.org/

Funny how we can stumble on the same idea from a different perspective. In my case, I wanted to generate efficient C code for an array library written in prolog. The logical solution was to manipulate a C ast from prolog, but since a lot of the ast needed to be written by me, I chose to make it very similar to the original C syntax. Here is the grammar generating tokens from the ast and then c code from tokens: https://github.com/kwon-young/array/blob/master/c99.pl

And some example uses: https://github.com/kwon-young/array/blob/master/kernel.pl#L5...

The main advantage of Prolog is that it forces you to think in different ways to solve problems. The main weakness of Prolog is that it forces you to think in different ways to solve problems. Especially because most existing libraries are written in procedural style, so they don't work well with prolog. In the end you'll have some difficulty to integrate with existing code.

I always felt that Prolog is a super valuable dsl that I would wish to be embedded like a reflex for certain problems, but is I'll suited for most programming tasks. I.e. have the GUI, Io etc. in language better suited to that.

You can do precisely that with ascent: https://s-arash.github.io/ascent/

This is the most creative idea I've seen in a long time.

It is also the smoothest way of "declaring an imperative" I've ever seen.

It is also the most amazing use of the parser which is built-in to prolog (no, not the DCG's, the other parser, the railroad/operator precedence parser).

I wish it had been discovered around 1981. The world might be very different.

This looks like it's using Prolog to be a rewriting engine into C? It reminds me a bit of M4 but seems like something better suited to something like Maude [1]?

[1]: https://maude.cs.illinois.edu/wiki/Maude_Overview

> Unfortunately, C is the only useful programming language.

Not really, plety of software has been written decades before it came to be, and plenty more has not been written in it, after it came to be.

Plus better reach out to something like SICStus if Prolog and performance is something one cares about in the same sentence.

I took that as hyperbole. Hard to tell how intentional it was, whether it was a joke or not... But yeah, obviously it is not true at all.

If this is meant to capture a would-be user's attention it ought to start with why it's good/useful/interesting, not with syntactic niggles.

Mercury is not mentioned.

Reply on news.ycombinator.com