"Democratizing Software" Talk at Handmade Seattle, starting at 1:24. Starts out with a statement of goals and values, as the title suggests, and then explains why rewriting techniques are a good way to reach those goals. Ends with a presentation of Nova, a rewriting system for nearly-plain-language. This is so incredibly similar to my own work over the last years that I am probably going to rewatch this at least once. The only difference is the target audience: Wryl (the speaker) uses everyday language as a building material, addressing games and other use cases that everyone can relate to, whereas I use mathematics as a building block, addressing scientists. I could probably set up a rewriting system for translating their talk to my own scenario.

I think that this is just a parallel-universe implementation of Chris Marten's Ceptre. Am I mistaken?

Ceptre is described as a logic programming language (I didn't look into the details). Nova is a multiset rewriting system. So the two have very different foundations, even if the target application areas overlap. Wryl argues that rewriting is easier to get into for newcomers (no programming experience at all) than the more popular PL paradigms, and that's the main argument for Nova in the talk. This affirmation sounds credible to me but not obviously true.

@Konrad Hinsen I got interested in Ceptre for other reasons. If I strip away the haughty words, I see no technical difference between Ceptre and the technology that Wryl describes. Basically: Factbase that allows the existence of duplicate facts. A way to pattern match against the factbase. Rules that rewrite the factbase based on the results of the matches (including removal of matched facts and insertion of new facts). Looks trivial to implement in Lisp, or Prolog, or ???. Actually, the big win is the use of a declarative syntax. Don't code actions, relegate all action-oriented details into the engine. Prolog does this. Ceptre does this. Nova does this. Martens' github contains numerous examples of games implemented this way. If interested, I can dig out some references from my notes...

When I see "logic programming", I expect an inference engine as in Prolog. A rewriting system doesn't have that, it simply evolves the factbase over time until it reaches a stable state. And yes, rewriting is easy to implement and has a nice declarative syntax. Good reasons to adopt it.

I think that Nova and Ceptre work in 2 stages. (1) search, (2) do something with the matched stuff (i.e. mutate the factbase). In my mind, the basic function of Prolog is to do "exhaustive search". In function-based languages, exhaustive search would be written as nested loops. Both, Nova and Ceptre need to do exhaustive search in step (1), hence, they both need the basic exhaustive-search-function of Prolog (or bug-inviting nested loops). In step (2) they, both, need to do only very simple things - retract facts from the factbase, insert facts into the factbase. At 20526, Wryl shows syntax with dark-background text and grey-background text. I see the dark text as "constants" and the grey stuff as "holes". Prolog syntax uses lower-case for constants and Upper case for holes. Ceptre uses the same syntax and adds the "lolli" operator ("o-" in ASCII) to separate step (1) from step (2). And, Ceptre uses a circle-X ("*" in ASCII) to separate pattern matching clauses (in Prolog that would be ","). Off the cuff, I think Wryl's example is:

image(Name,X,Y,R,G,B)
palette(Color,R,G,B) 
--->
image(Name, X, Y, Color)

and, would be written in Prolog as:

image(Name,X,Y,R,G,B) ,
palette(Color,R,G,B) ,
retract(image(Name,X,Y,R,G,B)),
retract(image(Name,X,Y,Color)),
assert(image(Name, X, Y, Color)).

And, in Ceptre it might be written as

image(Name,X,Y,R,G,B) * palette(Color,R,G,B) o- image(Name, X, Y, Color).

[My knee-jerk reaction would be to use t2t or OhmJS to rewrite the Ceptre syntax into Prolog syntax, then to run SWIPL on the result. Then, I would write yet another t2t program that would allow extending the Prolog-ish syntax by adding JS externals, then, spit that out as a /bin/bash pipeline (example syntax from an unrelated experiment

<https://github.com/guitarvydas/das/blob/main/das2f/layerboundingbox.md>

)]. [Some months ago, I dissected the Ceptre dungeon crawler example and hand-mapped it to DPL syntax:

<https://guitarvydas.github.io/2024/01/19/Ceptre-Dungeon-Crawler-Example-Walk-Through.html>

]

Thanks for those examples! According to my understanding of Nova (all I have seen so far is the video), it doesn't have search in the Prolog sense. It doesn't have real holes. But the mechanism shown for automatically creating variables is perhaps equivalent.

As far as I can tell, Nova and Ceptre have to do some sort of unification. Thinking in terms of the mechanics, in the general case, this means doing something like the /first/ match produced by a Prolog engine (without hitting ';' for more matches). Concretely, using Wryl's example, this means finding any "image(Name,X,Y,R,G,B)" then trying every variant of "palette(Color,R,G,B)" until you find one where all holes "R,G,B" unify with the "image(...)" fact (of course, backtracking to another "image(...)" rule if nothing matches up). miniKanren demonstrates another mechanism for generating potential matches, but, the end result is the same - find the first match that unifies the conjunction of all holes in all patterns being considered. PEG parsers do the same thing - backtrack until you find a successful match all the way to the end. [If I think back, I conclude that SNOBOL and Icon needed to do the same sort of unification]. [From my perspective, "find the first successful match that unifies all holes" is the sweet spot of Prolog, the rest is gravy. Nils Holm's "Prolog Control in 6 Slides" gives the algorithm in Scheme. I transpiled his Scheme code to JS using OhmJS, so it can't be a very hard algorithm :-]. Am I missing some other way to do this?

I can't think of any other way to do this than unification, which as you say isn't that complicated. But I have always seen Prolog as more than unification plus backtracking. But then, I have never seriously used Prolog.

Thanks! Do you have any suggestions on where to ask a question about comparing Ceptre and Nova? (@Kartik Agaram ?)

FWIW: further to my earlier comments, I wrote a quickie article about how I tied Prolog and Javascript together into a nano-DSL ... https://programmingsimplicity.substack.com/p/combining-prolog-and-javascript-into?r=1egdky. [Aside: for me, the essential feature of Prolog is the ability to easily specify exhaustive search and unification, something I'm not too eager to write in Javascript, OTOH, I wouldn't want to write string interpolation code in Prolog, so, my answer was to simply bolt both together into something that solved my problem at the time. My attitude of "syntax is cheap" helped me imagine this kind of solution.].