Using Prolog as the AST
marcellerusu.com
marcellerusu.com
I have a tiny prototype based on Go and soufflé.
The overall goal would be to figure out classical error conditions like nill pointers deference.
If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same.
However it is very hard work and the part I am currently stuck in is creating a reasonable abstraction level where I can reason (in soufflé) about code and not about an AST.
I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4"
Moreover we will be able to check the "real code" starting from main down to all execution paths. Which is much more powerful than current static analysis that usually analyse a single function without considering how the function itself is invoked.
Beside the actual implementation difficulties, the other big elephant in the room is the amount of resources needed to run this kind of analysis.
(I am less concerned about that as computation resources exploded due to AI and solving SAT is getting faster and faster)
> If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same.
Note, this is called flow-sensitive typing (also called type narrowing) and I think that typescript does it.
https://en.wikipedia.org/wiki/Flow-sensitive_typing
> I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4"
A model checker can do that!
See this
https://model-checking.github.io/kani/tutorial-kinds-of-fail...
Other techniques are also possible
https://github.com/viperproject/prusti-dev#quick-example
(Here I could link a lot of things, I just selected two Rust projects to illustrate)
This works better if you are able to provide contracts in your API that says which guarantees you provide. Alternatively, asserts are useful too.
> I am less concerned about that as computation resources exploded due to AI and solving SAT is getting faster and faster
Sadly we are usually very concerned about this. The complexity of these problems are usually NP-hard, so we usually have either heuristics (imprecise), exponential algorithms, or fixed-parameter tractable algorithms (practically speaking, O(2^c n) for a pretty large c), which are either imprecise or too slow. This is still an area with active research. The main problem is that, even if your computational power gets 2x faster, you cannot solve problems 2x larger within the same amount of time. It doesn't scale... (but of cause, usually we are dealing with sparse problems so the scaling is not in LOC for example)
> the part I am currently stuck in is creating a reasonable abstraction level where I can reason (in soufflé) about code and not about an AST
I recommend aiming for an abstraction level similar to the one in the paper (starts on page 9). Once you have that target, writing relations to convert an AST fact such as `binary_op("=", leftId, rightId)` to `Move(to, from)` is fairly straightforward!
There's a very easy way to do it, simply add a pointer from the child back up to the parent. It means you can't share AST nodes but it's damn fast and, once debugged, very easy to maintain.
I've done this on my personal project and so a question to everyone: when I originally heard of using datalog in compilers it seemed like a very good idea, like it was promising some real value somewhere, but I've seen examples that show you can do trivial type checking – but I do that myself and it's very, very easy. Perhaps I'm looking at this wrong? If I'd used data log then I could knock at a few hundred lines of code scattered around the AST objects, but surely I can do more than that with datalog? I feel I'm missing something, and the crowd here seems knowledgeable so any good pointers (good = simple, because I'm a n00b) would be incredibly helpful!
(I am aware of some really advanced stuff like BDDBDDB (https://suif.stanford.edu/bddbddb/), so advanced I can't even follow it, I'm looking for something between the triviality of type checking and the complexity of full dataflow – the problem here may be a personal one, in that I might need to have to write a dataflow implementation to get a really good 'feel' for it, and then I might 'get' the value of using e.g. datalog, I don't know, but any guidance welcome) this will feed into an actual working project).
Not quite out yet.
I am thinking about using this idea of Prolog as AST to build an ai-first, reactive IDE. DM me at @eating_entropy on Twitter or email me at joshcho@stanford.edu if you are interested.
1. Free de-duplication. No more debugging why a predicate is returning the same result more than once.
2. Commutativity. Order of predicates does not change the result. Finally, true logic programming!
3. Easy static analysis. There are many papers that describe how to do points-to analysis (and other similar techniques) with Datalog rules that fit on a single page :O
Souffle[0] is a mature Datalog that is highly performant and has many nice features. I highly recommend playing with it!
To those who have used Prolog, is the description sufficient to know what it does and if it will be useful? I've never use prolog and I don't know the lingo.
But I do agree that being familiar with Prolog is a big help in understanding what Souffle is. For a quick intro to Prolog, I recommend this video[2], which speaks from a "industry practical" point of view, and introduces concepts that almost all apply to Datalog :)
[0] https://souffle-lang.github.io/simple
[1] https://souffle-lang.github.io/tutorial
[2] https://twitter.com/ThePrologClause/status/15006425339400233...
That said, Souffle is touring complete due to its adding of constructors to the language.
Moreover, using various forms of coinduction you can encode infinite computation even in non-TC languages.
But, other visions of programming have coexisted with this main educational vortex, including logic programming like Prolog. Actually, if you have heard of any of these alternates, you have probably heard of functional programming, which can be ahistorically understood as saying “hey these locks and races and all that, it's actually very complicated, maybe we could have a simpler model of programming for 90% of our work and only break out the Java when we really need it.” And you’re like “what will you replace it with?” and they respond “Template substitutions! It's all the power of lexicographic scopes, all the power of looping (via recursion), but when you want to express the really complex stuff you need templates that have side effects when substituted, we can give those scary names.” So you give me a sunbeam and a raincloud and I give you back a rainbow.
If that's the functional programming idea then logic programming takes the same idea but adds unification and search. The idea is “ok but why do I have to fill in all the parameters to a template before I use it? I should just say “if light shines on a droplet-cloud it makes a rainbow, a sunbeam is a light, a raincloud is a droplet-cloud, hey language, what are all the things that make a rainbow?”
Functional programming was based on the function, the template, the “I take these args and produce a structure looking like such-and-so.” Logic programming is based on the Horn clause, “X verbs Y, for some entities X and Y that I maybe know about and some verb that I am being introduced to.”
Basic things that logic programming does very well, OOP kind of struggles with. You can kind of understand this if you have written a SQL query. The verbs can be thought of as tables that foreign-key to X and to Y, if you want to write OOP to solve a logic puzzle you have to choose explicit ways to search or brute force... SQL DBs come with B-trees and indexes to solve a lot of these problems. Whereas with Prolog you just write the pattern to match and the new pattern to emit.
It's a rather different take on what the building blocks should be.
Someone on Mercury's mailing list took pity on me, and told me to just straight up try some Prolog.
Prolog, at least the basics, isn't hard at all, and it takes maybe a day to get you to write something that works. Of course, every language has its inconsistencies, dark corners and unexpected turns, and, sometimes some very deep and general pieces of wisdom that aren't on the surface. But, really, if you want to understand any Prolog derivative, the best way I can think about, is to learn some Prolog. It's the most efficient way to the goal. It doesn't really take long.
I'm not sure this is a good selling point. The fact that predicate order matters in Prolog allows performance optimization and more transparent debugging.
That said, order of constraints can affect performance. But since reordering doesn't affect outcome, you are free resort them as you wish in effort to optimize for better performance :)
Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.
edge(1, 2).
edge(2, 3).
edge(3, 4).
+——-+——-+
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
+——-+——-+
However, in Prolog you can easily define something like reachability using recursion:
reachable(V, V).
reachable(V, W) :-
edge(V, U),
reachable(U, W).
But the graph in your example is still directed, simply by the virtue of predicate arguments being ordered.
So your example misses two rules to be correct.
reachable(V, W) :- edge(V, W).
reachable(V, W) :- edge(W, V).
reachable(V, W) :-
reachable(V, U),
reachable(U, W).
edge(V, W) :- edge(W, V).In fact fore recent SQL standards have added extensions for these kinds of recursive joins. (And some databases like Oracle, DB2 have had recurse or tclose operators for a long time.)
I don't think they're particularly elegant -- they're awkward like most things in SQL because SQL's syntax sucks -- but the ability is in fact there these days.
I wonder whether you're accurately portraying the structural foundations of either Prolog or SQL.
Now, some people argue you might want a less expressive logic programming language, especially datalog, so this isn’t a knock-down argument, but it’s a pretty big difference.
yes it is
> SQL gets Turing completeness by means of various additions/alterations.
Sigh. No. SQL was a subset of relational until recursive CTEs were included to round it off properly.
Can you double check and/or give references? Because I specifically doubted my memory here, and everything I found online before posting matches what I thought—-standard relational algebra is not Turing-complete (hence relational queries are guaranteed to terminate).
Prolog and Lisp were derived from first principles, SQL was designed to be a language that reads similar to English (i.e. easy to learn for non-programmers).
Prolog and Lisp also has the concept of "atom" which can represent many things, but in parsing it's used for terminal symbols.
Prolog has the advantage over Lisp that you can define custom operators and their precedence, so you can create easy to read domain specific languages without excessive amounts of parentheses.
The built-in backtracking can also be useful for parsing.
Definite Clause Grammer rules are also a standard feature, which is very similar to the Backus-Naur form.
BNF and DCGs get a bit closer to what I'm asking, but even then I'm not sure it really adds anything novel -- what, if any advantages do you get from that over the relational algebra whose set theoretic underpinnings serve as the foundation for SQL? How is backtracking functionally different or more powerful than joining?
Let me give an example by way of another formalism, which is the Church-Turing correspondence that establishes a correspondence between the lambda calculus and Turing machines. Is there any theoretically stronger expressive power one gets from Prolog over SQL, or is it an ergonomics question, similar to using say, Ruby over Java?
But ergonomics of the syntax certainly hinders you ...
I guess this is best illustrated by examples.
In prolog, you can define how people are related using "facts" or data:
person_parent(alfred, benny).
person_parent(benny, carl).
CREATE TABLE persons ( name TEXT NOT NULL, parent TEXT NOT NULL);
Let's say I want to know if "carl" is the grandparent of "alfred", in Prolog I would first write a rule to define what a grandparent is:
grandparent(X, Y):- person_parent(X, Z), person_parent(Z, Y).
grandparent(alfred, carl). --> true
grandparent(X, carl). --> X = alfred (and any other kid)
grandparent(alfred, Y). --> Y = carl (and any other grandparent)
grandparent(X, Y). --> X = alfred, Y = carl (and any other combination).
A more powerful example, is defining the rules of suduko and then asking prolog to finish solving a board for you. I will not even begin to suggest how that would be done in SQL (partly because you simply would not use SQL for that).
If it's just that you can define relations in the database scheme, then pretty any programming language would be considered relational.
They're not "true" relations though because SQL allowed duplicate tuples ("rows") and missing values (null) which the pure relational model does not permit.
It's also considered relational because it uses at least some of the terminology and functionality of relational algebraic operators (join, project, restrict(select), union, cross product, etc.). Though this sometimes leads to confusion (e.g. "select" in the rel-algebra means something different from what a lot of people writing SQL queries think it means -- 'select' in the relational algebra is a restricting/filter operator, but the way it appears in a SQL query implies that it's the thing choosing which attributes (columns) to retrieve... which is another operation entirely (project) in the relational algebra...)
As for the explicitness, that's orthogonal to the question. Relational algebraic expressions are in fact quite explicit. Datalog queries (and Prolog maybe too, to some degree, but not always) can be essentially compiled down to relational algebraic operations (tho they don't have to be.) And so can SQL.
SQL is sort of ... inbetween... the relational algebra and something like a "relational calculus" which figures more out for you and does things more automagically.
Sometimes the explicitness of SQL is in fact a feature. I've found Datalog queries a bit awkward to read at times, with the joins sort of automagically happening, it's sometimes tricky to fully grasp what's happening behind the scenes.
Regardless one of the features of the relational algebra is that various operations can be re-ordered for efficiency without losing the semantic meaning. So behind the scenes SQL query planners restructure things as they need and desire.
Two rather distinct solutions:
https://www.sqlite.org/lang_with.html#outlandish_recursive_q...
http://conway.rutgers.edu/~ccshan/wiki/blog/posts/Sudoku_in_...
Nope. Can be written as a non-predicated recursive CTE. Just add a 'where' at the end to specify what you want.
The practical difference is in the way the search takes place. In SQL you would get the right results but it might take a lot longer because it might (depending on what you're looking for) generate all possibilities and just pick the ones you want. In Prolog I think it's a bit more intelligent in searching.
That depends, of course because it's an implementation detail and predicate pushdown or whatever might regain that efficiency, but from experience I can say It Depends.
(I recently did something like this at work, so it is actually useful)
Edit: see https://www.andrewvillazon.com/recursive-cte-sql-server/ for something similar
Example: Adds nulls (weird trivalue logic, and breaks reordering of some relational algebraic expressions), has duplicate tuples (relations stop being sets of sets).
Unfortunately SQL has done more recently to put people off the relational model than it has to bring them around. Though the majority of people who use it don't actually understand the relational model, so.
Datalog is also built on the relational algebra. Or at least, Datalog works on relations and any Datalog programme can effectively "compiled down" to a relational algebraic expression.
Another, unrelated aspect: I/O, system calls, all that stuff that would require from you in SQL database to go outside and implement functions that are loaded into your database in some database-specific way.
Parsing. SQL doesn't offer much in terms of working with strings. Writing as much as a parser for arithmetic expressions with just integers would be a huge undertaking. No sane person would write such a parser unless for some bizarre code-golf challenge. It's trivial to do that in Prolog.
CLFD. This isn't part of standard Prolog, but it comes with most implementations. This allows you easily to write queries about numerical facts (eg. find all factors of a given integer).
To continue in the similar spirit as above: modern Prologs come with a bunch of libraries. You can have an HTTP server in Prolog, or an image processing tool etc. Something that in SQL you'd have to implement outside of it, and load as an external function.
Modules. Prolog code is more amenable to reuse and can be better organized because you can put it in boxes, hide things you want to keep private in those boxes etc. This is while SQL operates entirely in some sort of a global namespace.
The list isn't exhaustive, these are just the things I could think in a short time.
1. Nothing, theoretically (but see 2, 3, 4)
2. They are for different domains/problems
3. Both are based on the same formal background (1st order predicate calculus IIRC)
4. Learn both. It's not hard and they're both useful and it won't be a waste of your time.
Prolog, OTOH, excels at planning, optimization, constraint solving, etc. Given Prolog was originally designed for old-school grammar/logic-based NLP, it also has excellent built-in support for custom DSLs and recursive-descent parsing using definite clause grammars making use of Prolog's logical variables (with indeterminism / backtracking and retry) and unification (pattern matching on steroids).
Check out Prolog in-browser demos for robotic planning/container logistics and machine learning/bioinformatics (not based on LLMs) at [1]. These aren't problems you'd tackle with SQL ;) but beyond SQL's inappropriateness also require actual language support for debugging, packages, testing, integration, etc.
https://xmonader.github.io/prolog/2018/12/21/solving-murder-...
Part of the reason I wanted to ask this question because I had a suspicion that there may not necessarily be as large of a gap between SQL and Prolog as there may initially appear. Said another way, I wondered if there was a Prolog (or Datalog) to SQL compiler used in production.
I recently stumbled upon Logica [1], which appears to based on a predecessor (Yeladog) built at Google. I don't have experience using it, so I'm not sure how complete the implementation is nor how efficient it is. I'm curious if anyone has used it before and if so, what their experience was. At first blush, it appears to bring the best of both worlds: the expressive power of Prolog/Datalog, combined with the standard operational tooling of SQL which is a common core dependency in many if not most production software systems. Two questions:
1) How does Datalog compare to Prolog for common problems you might use Prolog for? Any things you can do in Prolog differentially that wouldn't be as easy in Datalog and vice versa? 2) What issues might come up in system that uses a Datalog to SQL transpiler? Given that some of the answers in this thread about the efficiency of using Prolog to do constraint solving, it seems like such an approach might lose some of the efficiency that makes it so powerful in the first place. On the other hand, if it doesn't, it seems like it'd bring a killer app to SQL, which is the ability to do constraint solving in a nearly native fashion inside SQL.