Point-Free Logic Programming
8 points by veqq
8 points by veqq
we could sidestep all the complex semantics around logic variables by just talking about entire relations at once, could we open a whole new door to user-sculptable programming?
if you have relations, I think you can express both functions and types in them. That would mean you can get a whole new level of higher-order programming.
This leverages "binates", a terser relation syntax:
write relations in terms of more primitive relations using conjunction or intersection ,, union ;, converse or inverse ~, composition (concatenation), transitive closure *, either negation ! or set subtraction -, and a form of N-ary Cartesian product: {x: a, y: b, ...} produces a relation from the intersection of the domains of a and b etc. to a set of tuples which are the domain of the new relations x and y etc., whose codomains are the codomains of a and b etc. respectively - https://dercuano.github.io/notes/binate-kanren.html
ancestor = parent parent*.
father = parent, "male" ~sex.
sibling = parent ~parent.
cousin = parent sibling ~parent.
sufficient to express anything you can express in Codd’s N-ary relational algebra or relational calculus
In relational programming, a relation is also its inverse, so:
a function of multiple arguments may have many inverses, and you only have to write it once
by composing your program out of binary relations, you can describe the computation you want in a somewhat terser fashion than any previous language. You can beat APL for terseness.
This is exactly what my dataframes and query syntax needs.
Fwiw, my experience with tacit binary relations (many graph query languages are) is that they look great for demos, and much less great when subjected to more complex work. At least, you end up building a lot of aliases (as the binate post does) for each of the different permutations of the higher-arity relation, just to fit the binary requirement.
It feels like there's an inherent tension between tacit programming where each step consumes the output of the next, and (non-acyclic) logic programming where you do plan to re-use bindings in later constraints (e.g. to find a triangle, which the binary approaches are often bad at). Perhaps it's as simple as putting dup into the language, but you probably trade stack manipulation for names.
It's worth flagging that bi-directionality, going beyond functions that go exclusively from inputs to outputs, doesn't require binary relations (self-promotion, but certainly not my idea). The ~ approach only gets one more of the four modes for binary relations (missing semijoin and crossjoin equivalents).