Logica, a novel open-source logic programming language
opensource.googleblog.com
opensource.googleblog.com
Myself, I would like to see data query/manipulation language as a total functional language, possibly based on the idea of categorical data transformations: https://www.categoricaldata.net/
Also - bit of a rant - if you're creating a new programming language, consider making syntax and semantics separate in the specification. Lots of people get hung up on arguing about language syntax but it's really semantics differences that are important for compatibility. Lot of new languages comes up only to fix syntactic problems with existing languages but create small semantic differences in the process, making automated translation from and to existing languages difficult. I wish we could move to a world where syntax and semantics in programming languages are discussed separately from each other.
I agree. Implementations should accept a stable, machine-friendly format (doesn't matter which; JSON, s-expressions, or even XML would do). If they also accept a human-friendly format, there should be a standard/built-in translation from human format -> machine format (optionally the other way too).
This way, we can always convert random real-world code (scraped from GitHub, or whatever) into a language-agnostic format (yes Python has an `ast` module; that doesn't help a Python linter written in something else, like Go); tools can manipulate this format without having to care about the surface syntax (e.g. linting/doc-gen/static-analysis/versioning/diffing/refactoring/macros/etc.); the output of such tools can always be fed back into the main implementation to compile/run/type-check/syntax-check/etc.
Note, I'm not advocating for a single solution, here. I'm advocating that language authors should always think in terms of a front, middle, and back-end: front is surface syntax (their preferred one?); middle is the semantics, with a prescribed API; and, the backend is the implementation side — nicely abstracted by a 2nd API.
That way it gives those of us stuck in not-your-language a fighting chance to integrate Your Cool Thing™.
IIRC, Ohm (successor to OMeta) separates syntax from semantics!
Erm, like PromQL?
Edit: also I find the title a bit grandiose since this isn't about Logic Programming in general, but only database querying
https://github.com/EvgSkv/logica/blob/main/compiler/dialects...
Consider also the practical side: using Datalog as merely "prettier SQL" still doesn't allow you to dynamically define data properties or go schema-less as in RDF or other logic/deductive graph databases. Whenever you want a new column, you must execute DDLs (ALTER TABLE ADD COLUMN) also leading to forced commits, overly broad permissions, chaotic backup procedures and/or code artefacts containing the dreaded SELECT * syntax. Also, parsing Datalog queries, reformulating into SQL, then re-parsing SQL in the DB engine isn't the most efficient thing.
Basically, the workflows and use cases for SQL RDBMSs and Datalog/graph databases are not the same, and if you're using one on top of the other, you're getting the intersection of possibilities but the union of problems, as is well known from O/R mappers );
I don't understand what you mean here. With datalog, if you have a predicate person(Name, Age, Height) and you want to add an argument (a "column") for income, you can simply create a new predicate person(Name, Age, Height, Income).
Or, if you want to avoid duplication, you can write a rule to combine the information in two (or more) predicates:
person(Name, Age, Height, Income):-
person(Name, Age, Height)
,person(Name, Income).
That's true for Datalog, based on what I know about Prolog (not a Datalog expert!). I don't know how it works in Logica, but from reading the article above I think the semantics would be similar.
>> Basically, the workflows and use cases for SQL RDBMSs and Datalog/graph databases are not the same, and if you're using one on top of the other, you're getting the intersection of possibilities but the union of problems, as is well known from O/R mappers );
That's funny. But I don't think it applies here. SQL and datalog are both relational. The difference is that Datalog lets you define relations over tables ("rules"), not just relations over data ("facts"/"rows"). Essentially, SQL is one half of datalog's relational semantics - only information without reasoning. Datalog adds reasoning on top, but the reasoning is still, well, relational (facts, rules and queries are all relations). There's no impedence mismatch here, as in trying to fit relational data into a non-relational program.
What is the difference between Datalog rules and SQL views?
Funny thing. It used to be my day to day work was 80% SQL. Nowadays it's 99% Prolog maybe with a little bit of bash and powershell scripting (gotta automate those experiments!). I kiiind of miss SQL? But not quite. Personally I don't 100% get the grumbling about SQL's syntax. It's unintuitive and it works very hard to hide the actual semantics behind it, but, eh, at least it has clean semantics.
I recently found this free book on databases that goes over both SQL and Datalog. It's a bit thick with obtuse terminology but it actually goes in depth over many useful topics:
I also recommend that to OP, if they're reading.
Obviously Prolog is well-suited for this task, but there's a reason why you don't often hear of "Inductive Python Programming" or "Inductive Java Programming", say. The reason is that imperative languages tend to have lots of specialised syntax, for example for class declarations, loops, variable assignment etc. Whereas Prolog syntax consists entirely of one kind of expression, the Horn clause. So for instance, to learn a program with a "loop" in Prolog you "only" need to add a recursive clause to the program, where a recursive clause is simply an ordinary Horn clause with the same predicate symbol in a head literal and one or more body literals. To learn a program with a loop in Python you have to add the loop to the program as a specialised structure with its own peculiar syntax.
Also, because in Prolog everything is a Horn clause, examples, background knowledge and language bias can be (and often are) represented as Prolog programs themselves, so it's possible to learn new background knowledge, new language bias and even new examples. That'd be tricky to do in Python where examples, say, would be not programs, but the inputs of and outputs to programs.
The sister field to ILP, of Inductive Functional Programming exploits the homoiconicity of functional languages in similar ways.
Finally, Prolog is a language with a deductive inference algorithm as an interpreter and it turns out deduction can be sort of inverted into induction. Which is to say, we can go from reasoning to learning, with but a tiny little hop. Well, ish.
If you're interested in more details about my work, there's links in my profile.
I loooooooooove the ideas being expressed in the post. I am firmly in the camp that SQL needs a deep rethink because of its many and manifold software engineering flaws, and this is exactly the sort of thing I'm thinking of, not just a slight gloss on SQL, but a complete rethink. I'm just not sure this is going to be practical sitting on top of SQL. Make this a native query language for Postgres or something and we'd be talking. One step at a time, though. I'm very positive on this step being taken.
At this point, extracting the industry from its path dependence history [1] of SQL is a Google-sized problem. The engineering itself isn't necessarily a Google-sized problem but the rest of it is.
[1]: https://en.wikipedia.org/wiki/Path_dependence - that is, if databases were all separately evolving over the years and only this year were they all going to get together and produce a standard to unify themselves, it would not look like SQL. It would quite likely look a lot more like this. SQL has too many glaring flaws, not least of which is its total composability fail.
I think it's a bit confusing that datalog is always discussed in the context of databases and as a "query language" etc. In fact it's a subset of Prolog, so it really belongs to the subject of logic programming. It doesn't help that Prolog programs themselves are implemented as databases and that Prolog programming uses terms such as "query" that blur the waters about exactly what one is doing.
I confess I don't have a background in databases and so I only understand the very basics about SQL's semantics, which is the Relational Calculus, but as far as I understand it, RC is a subset of predicate logic (a.k.a. first-order logic). Prolog is itself a different subset of predicate logic, Horn clause logic; and Datalog is a subset of Prolog and equivalent to SQL in expressive power.
Very briefly, every expression in Prolog is a Horn clause. A clause is a disjunction of literals. A literal is an atom, or the negation of an atom. An atom is an atomic formula, a predicate symbol followed by a number of terms in parentheses where the number is the "arity" of the predicate. Terms are variables, functions or constants.
For example, father(john, bob) is an atom of the predicate father/2, where "father" is the symbol and "2" is the arity.
An example of a clause is grandfather(x,y) ∨ ¬father(x,z) ∨ ¬parent(z,y). This is a disjunction of one positive literal, grandfather(x,y) and two negative literals, ¬father(x,z) and ¬parent(z,y). By the rules of logical connectives, the same disjunction can be written as an implication: father(x,z) ∧ parent(z,y) → grandfather(x,y). By Prolog convention also observed in Datalog, implications are written with the positive literal first: grandfather(x,y)← father(x,z), parent(z,y). The left-facing implication arrrow is rendered as ":-" in ASCII friendly manner, conjuctions are represented by the comma, ",", and variables are represented by upper-case letters, yielding the standard Prolog -and Datalog- notation:
grandfather(X,Y):- father(X,Z), parent(Z,Y).
s(0). % [1]
s(N):- s(s(N)). % [2]
Now, s(0) is a Prolog and Datalog fact and is just as fine a SQL table, called "s" and with a single row with one value, "0". Here's a fuller example:
father(bob,john).
father(john,alex).
grandfather(X,Y):- father(X,Z), parent(Z,Y).
?- father(X,Y).
X = bob, Y = john ;
X = john, Y = alex.
?- grandfather(X,Y).
X = bob, Y = alex ;
false.
Now, I leave it as an exercise to the reader (you) to figure out how the above works out with SQL. Keep in mind that father/2 has a clean translation to a SQL table named "father" with two columns, for example named "father" and "child". The "rule" for grandfather/2 is probably best represented as a join.
In any case, as you can probably see, we have here a very different language than SQL, but with semantics that can be seen as, in a sense, being equivalent to the semantics of SQL. Except, where SQL makes a distinction between "data" and "queries over data", Datalog only has facts, rules and queries, that are all Horn clauses and that are all part of the "program database".
So it's not a complicated machinery on top of SQL at all. The only thing I'm concerned is of the naturaleness of SQL queries generated by the "compiler" (some kind of transducer, probably). On the other hand, I reckon SQL is only meant to work as a kind of "relational assembly" and will not have to be seen by any human eyes except in rare cases. Or that's hopefully the plan.
Edit: note there are many, Many, MANY variants of Datalog with confusingly subtly different semantics. See the book I recommended in my comment to juki, below. Personally, I get lost in the variations pretty quickly...
It is a reflection of the way that SQL is so ensconced in the developer's gestalt as "The Way To Query Data", such that Querying Data means SQL and SQL means Querying Data, that most people are not capable of coming at something like a logic-based database layer as a first-order element on its own, but can only conceive of it as an SQL layer.
Further observe how there's a category of databases called "NoSQL"... when you have a category of something defined by its not being in some other category, that really shows just how large that category looms in the developer's mindset. NoSQL is slowly cracking the SQL consensus, but it's a long and slow process. You'll know it has really made it when we give a positive name to that category, or perhaps more likely, 3 or 4 names to the several types of databases within. "Document store" is getting close to being the name of one of the styles.
My particular reason for speaking this way though is that this specific technology manifests that way. You'll note I called for this to be made a native query layer, because I'm personally pretty much over SQL and ready for the next thing to come out. I'm tired of it being the 1970s again every time I speak to a database. Unfortunately, it's such a task that it has killed everyone who has tried it so far. AIUI FoundationDB got the closest from anyone I've seen. I'm not sure how they're doing; a cursory web search suggests perhaps they aren't as dead as I thought.
I agree with that, although since I don't write any SQL anymore, I don't really mind it, as such. But I think the reason Logica is compiled to SQL must be the pervasive association of "database" with "SQL" that you point out. Datalog in fact has its own execution model that doesn't really need SQL. Perhaps the people behind Logica felt that it would be easier for it to be adopted if it piggy-backed on SQL, the same way that so many languages target the JVM etc. I too think that's a little disappointing. But I'm heavily invested in logic programming so I'm glad to see _some kind_ of logic programming language at least created at Google (no idea how much it's used though).
I have been looking for examples of how to use a practical implementation of Datalog for years and the closest I've come to is actually miniKanren instead. Could you point me to codebases that productively use Datalog internally?
https://github.com/algernon/hydiomatic
I've heard informally there are many companies relying on clojure/core.logic to rewrite complicated business rules for the sake of filtering and constraint solving problems in applications, but I do not know of any open source examples to reference.
edit: i accidentally linked to a dependency of the project i meant to link to. originally linked to the mk implementation: https://github.com/algernon/adderall
I'm well aware of datomic family databases, but it's the part about solving interesting problems with them that interests me, not that someone has implemented another one ;)
Used by projects such as Doop: https://bitbucket.org/yanniss/doop and Ddisasm: https://github.com/grammatech/ddisasm
Would be pretty awesome if we could have logica (or something similar) for dataframes (including pandas), and so could build pipelines of transformations-via-queries on those.
(If there is anything like this already implemented, I'm all ears!).
> English words (...) often capitalized to keep the old-fashioned COBOL spirit of the 70s alive!
I like logic programming a lot but a convention not technologically enforced is a poor reason to argue for a language change. When arguing about SQL limited abstraction capabilities that space would have been better spent talking about CTE limitations, for example.
Also:
> To make things worse, SQL code is rarely tested, because “testing SQL queries” sounds rather esoteric to most engineers, at best
So nonexisting best practices require a language change, apparently. It was also not showcased how this can be done in Logica, beyond the table mocking that could be done with a "with xxx as (values a, b, c) select (query to be tested)" approach in sql.
Look for the section containing the text "As a final example, let us mock the comments table, in a unittest of a query." That demonstrates mocking and is explicitly pointing towards testing. The article is only a high-level intro document.
This really should have demonstration of some of the actual use cases where this shines vs SQL.
Also: SQL-92 has values clause which makes the example provided a little bit silly, you could just use
values (2),(3),(5)
select * from (values (1, 'hello'), (2, 'logic'), (3, 'programming')) as mocktable(user_id, comment);Note that I'm not claiming it can't do but I would be interested for the authors to point out what the actual benefits are.
All I see from their examples that clauses in Logica are much longer than SQL counterparts and that they are importing modules which (I assume) re-define already defined schemas which brings all kinds of different dependency problems that I'm not going to go in here..
Tangentially related, but does anybody know of a program or a library that takes standard SQL queries as input and outputs one or multiple equivalent queries using the SQL dialects of a set of DBMSs? That is, compiles a standard SQL query into a PostgreSQL one, an SQLite one, etc.
There are a number of tools that translate queries between SQL dialects. Google for “sql dialect translator”.
has_descendant(?ancestor, ?descendant) :-
has_child(?ancestor, ?child),
has_descendant(?child, ?descendant).
In SQL, given a table has_child(parent, child), it is not clear to me how you can get all descendants of a given person, or all ancestors.
Other people talk about recursive extensions to SQL, maybe that provides a way.
Sqlite official examples: https://sqlite.org/lang_with.html
MySql official examples: https://docs.oracle.com/cd/E17952_01/mysql-8.0-en/with.html
Logica instead seems to create tables and drop tables?
https://github.com/EvgSkv/logica/blob/main/examples/Logica_e...
It looks like Logica code isn't actually translated to a (large) SQL query, but Logica code is dynamically interpreted by some interpreter that calls into a SQL database as the virtual machine.
Not sure what Logica really provides here. Datalog usually comes with elaborate techniques to make sure only what's really needed is calculated instead of just generating all values every fact generation "iteration".
Actually, I might have jumped to a wrong conclusion. I really don't know if that's what happens here, but if not then it would imply that recursion isn't actually driven by the evaluation mechanism, but by Logica creating enough tables for a given program to ensure that iterative evaluation of rules ends up with a fixed point result set. Not quite sure. None of the other examples show recursion in the SQL output itself either.
Well, at any rate I'd like to learn more about the actual mechanism here but they are a bit light on documentation.
The end result is (you hope) a very complex database where the smaller blocks/relationships can be audited and verified quickly, and where parallelization more or less comes for free.
The reality is that Datalog systems end up being massive hairballs of declarations that are hard to unravel for mere humans (well, regular developers) and that query-based solutions are 10x faster to develop for 80% of the application use cases.
The closest parallel is functional-vs-procedural programming (don't flame me); it's a niche solution for niche problems.
Source: former Datalog developer for ERP systems.
So this is going to run into the same issues as any SQL code generator (compare Hibernate for example): you need to know what query it will output. And you need DBA skills to know what that query means in terms of performance. Neither of those steps can be skipped.
Nor is unit testing necessarily helpful when using small n. Issues of poor scaling don't show in tests unless the data is large.
What about optimizations? It seems like it should be possible to construct a SQL query that doesn't hit the pain points (e.g. avoids queries that do not use indexes). Although from my experiences with other ORM frameworks, that probably isn't an easy problem.
Even then though, since it looks like it somewhat aims to replace SQL even in the database-construction step, that might help in this regard, by constructing a more optimal representation of the data (which doesn't seem to be tabular)?
Unit testing I am similarly skeptical about though. The article does mention it being "rather esoteric [sounding] at best", I would actually agree with that expression, haha. I don't think I've ever written or even seen, in my 8 years as a developer, a 100-line SQL query that was not at least partly generated (and hence required testing as a unit, and not just the code around it). I suppose Google operates at a different scale, but still.
Edit: Never mind, the Scryer Prolog github page states it as follows:
Scryer Prolog aims to become to ISO Prolog what GHC is to Haskell: an open source industrial strength production environment that is also a testbed for bleeding edge research in logic and constraint programming, which is itself written in a high-level language.> It supports modules and imports, it can be used from an interactive Python notebook and it even makes testing your queries natural and easy.
I don't see any examples of how to do tests in the announcement. Consider adding some.
* My business clients and I speak SQL together. I don't see them learning a new language. I don't have the authority nor any will to force them to.
* I can spin up a container for testing business rules logic (and often share the results back to the client: here is what the impact of updating rule A is, rows of type W will be affected in this way).
Even though SQL has ceremony/verbosity, I'd rather see the standard be evolved. My clients and I could pick it up more easily.
----
That's great for BigQuery though. You can't spin up a BigQuery docker container anyway, and testing with another schema/project is risky while you have interns around.
I see that one can create predicates (functions) with parameters as a means for code re-use. I could also see that having implications for testability. That's interesting.
I could see how one could build a DSL with Logica to make fairly tricky queries easier. That's interesting.
Has anyone used this? If so could you explain how are SQL functions called? Do they have to specifically exist in Logica or are they just assumed to exist in SQL? (I'm thinking about geographic functions in particular for example. Are window functions also possible in Logica?
Only I wish we had such a language for a more generic streaming / data processing framework, such as materialize [1].
I was very optimistic about that for some time, as the guy behind the technology, Frank McSherry, wrote some datalog tooling as well [2].
It's almost as if people saw OWL 2 DL, didn't believe what it had accomplished, and didn't try to make anything better.
For Prolog me too wondering if there's a great source. But I have read 'the Reasoned Schemer', it used a simple Scheme-based logical programming language for teaching purposes and it's very educative and entertaining.
The best way to learn it, in my opinion, is to implement microkanren, which is micro by design for teaching purposes. It is small enough to fit in your head, understand what's unification, and play with it. Then you can jump into other implementations.
If you like clojure, you can use core.logic, although documentation is not abundant.
More prolog-related, The Power of Prolog https://www.metalevel.at/prolog has been praised here several times.
My recommendation would be to learn the real thing, not an almost, sort-of Prolog that's actually a LISP dialect in disguise.
Prolog Programming for Artificial Intelligence by Ivan Bratko.
Also it's got some small incompatibilities with SWIprolog and I don't know how well amzi works under Wine so it can be frustrating if you're on linux.
The relational model adds constraints, state, and a mechanism for first-class derived relations (updateable views).
And while you can stick anything with a well-defined equality in a relation, including other relations, the point of the relational algebra is to describe structure using relations, thus making it all accessible to relational operators. In a properly normalized database, all structure can be manipulated through a common set of operations.
So you could, e.g. create a relation with a single JSON attribute and call it a day. But now, in addition to the relational operators, you need a whole mess of JSON operators to query it.
Thus, while you could have a sum type, you don't need this because you can put the various summands into separate relations. For instance, the simple case of booleans:
Persons(key id: int, name: str, is_tall: bool)
... noramlizes to ...
Persons(key id: int, name: str)
TallPersons(key id: int)
Persons(key id: int, name: str, zing: either<int, str>)
... noramlizes to ...
Persons(key id: int, name: str)
LeftPersons(key id: int, zing: int)
RightPersons(key id: int, zing: str)
AssertEmpty: LeftPersons{key} & RightPersons{key}
Then, you'd get the simplicity of entering Persons.insert(key=5, name='bob', zing=Left(5)), but that's simply an updateable view. It will really update the base tables Persons / LeftPersons with simple atomic values.
The SQL vs NoSQL debate reminds me of the static types vs dynamic types debate. Static type systems offer a more robust mental model and verification, but at the cost of rigidity and forcing the programmer to think in the type system's mental model. Dynamic types are therefore appealing because they can adapt to the programmer's mental model, even if that model is seriously flawed. One change in philosophy that has helped static type system is the realization that you can design static type systems that while not conceptually pure, get closer to the dynamic mental models. These systems, such as TypeScript or Go, make static types easier to swallow.
I wonder if the same could be said for SQL/relational systems. If you could design a relational system that's a touch more ergonomic, that doesn't require learning a mental model that feels a little foreign, maybe the NoSQL options will be a lot less appealing.
I completely agree, and I may not have driven this point home, but because a relational system lets you have different views of the same data, you can have sum types in one view, while breaking them into relational structures in another view of the same data. We don't get that in SQL DBMSs because SQL isn't really relational.
> If you could design a relational system that's a touch more ergonomic, that doesn't require learning a mental model that feels a little foreign, maybe the NoSQL options will be a lot less appealing.
What's could be ergonomic about a strongly system is that it can guarantee that if I pull a record from the database, it has exactly what types it says it does, so my code knows what it's dealing with. Even if I'm writing something in Python, I don't actually want to do a mess of instanceof checks.
I think what we want is to properly wire a DBMS into build tools. The production system should have everything strictly typed, presenting a clean API to consumers.
Meanwhile, a development branch should let you put whatever you want in there while you're experimenting, and then you lock it down before you promote your code to prod.
> Informally, a relational database relation is often described as "normalized" if it meets third normal form.
> An approximation of Codd's definition of 3NF, paralleling the traditional pledge to give true evidence in a court of law, was given by Bill Kent: "[every] non-key [attribute] must provide a fact about the key, the whole key, and nothing but the key".[7] A common variation supplements this definition with the oath "so help me Codd".
Could anyone clarify?
I'm talking about a more basic idea of expressing structures that are accessible through relational operations, so joins, intersections, unions, etc. That's known as 1NF[1] and, as you might expect, it's a pre-requisite to 2NF and 3NF.
Just as you showed how a sum type could be represented with component relations, a similar example could be constructed showing how any needed attribute of a datetime could be normalized to various tables combining the features of dates and times.
I can't find any mention of recursion on the original blog post or the GitHub page. Without recursion it isn't Datalog.
There is a syntax debate I respect. While I prefer austere syntax, deeper thinkers like Bill Joy note that programmer productivity increases with more information on screen at once. Syntax that improves both code density and clarity is a good thing. I love Haskell and Ruby in actual use, even if I want to prefer Lisp without parentheses (an easy preprocessor if one thinks it through).
I cannot respect perpetuating C syntax just to attract users who would otherwise be challenged (that Apollo 13 astronaut who "never trained in the LEM"). Rob Pike once gave the only justification I can understand: Code used to need to survive communicating through channels that mangled whitespace.
That is no longer the case, and modern editors all support syntax highlighting. (We've reached the point where one should develop an editor language server in parallel with any new language.)
If your editor can figure out your language's grammar, and then you can with the editor's help, then one achieves greater code density and clarity at once. Some people do love terminals, but most people use graphical user interfaces. Why is language design stuck in terminal pre-history? There is no excuse in 2021 for lots of stray punctuation that's just ground glass in programmers' eyes.
I strongly prefer verbose type systems, in particular, some lightweight type inference is good as long as it's not full fledged HM type inference (like Haskell, Rust etc). The problem with HM type inference is although it's extremely powerful and makes the code look cleaner, it hides important data from programmer, which ultimately causes 2 bugs:
* variables being inferred to have types slightly different than ehat programmer expects. E.g. I expected foo to be A(B(C)) -> D(C) turns out it's actually A(B(X)) -> D(C) which also type checks.
* Errors can be harder to read.
A join of A and B looks like
C(x,z) :-
A(x,y),
B(y,z)This is objectively bullshit.
What SQL database engine doesn't provide views, stored procedures and/or user-defined function support?
Failure to construct higher-order abstractions in SQL is a failure of the engineer to understand the problem domain, not a failure of the tool.
SQL is capable of operating at any level of abstraction you wish for it to. It is all engineering from there.
In terms of lack of linguistic abstraction, try writing a query that abstracts over what table it's to be run against, allowing choice of source data to be parameterized, without either resorting to shenanigans like passing strings of SQL fragments around to be eval'd during query execution, or writing the query in some other system such that it can then be compiled into SQL for execution.
The problem is that "Compose" function is essentially impossible to write. I say essentially because it's probably something that could theoretically be written, but not with any reasonable amount of effort. It would literally be on par with the difficulty of implementing a DB from scratch that implements the Logica language as its base query language.