Logic Programming

Reasoning over incomplete information
Mechanical combination of independent rulesets (although you can also get this by modelling rules as an explicit DAG - see GETTSIM, comment from Merigoux)
Advanced querying capabilities

A Horn clause is a clause with at most one positive literal. These admit a useful rule-like representation:
¬p ∨ ¬q ∨ … ∨ ¬t ∨ u
is equivalent to
u ← p ∧ q ∧ … ∧ t
which is the basis for Prolog rules.

A logic program typically is, at its heart, a set of clauses, often Horn clauses, but there could be other stuff in it besides clauses. People do all kinds of crazy stuff. But basically, usually, a set of clauses is the main thing. Logic programs roughly correspond to first-order theories.

A "tight" logic program is one with an acyclic dependency graph between its positive atoms.

Negation (Tonhofer's notes):

• Negation as failure or weak negation: Anything the program can't prove true is assumed to be false
  
• Classical or strong negation: Must be able to derive an explicit negative value
  

Answer Set Programming
Constraint Logic
Description Logic
Non-Monotonic Logic
Fixed-Point Logic
Frame Logic
Temporal Logic

Free and open source
Isomorphism with source text -> defeasibility
Explanations (exhaustive, hypothetical)

Epilog
Prolog, particularly SWI-Prolog, Jan Wielemaker's implementation (online environment: SWISH)
Ciao
Flora-2: Object-oriented knowledge representation and reasoning system
Logtalk: Prolog + modern OO and module features
Logic Production Systems: Kowalski's latest, I think. "aims to close the gap between logical and imperative"
Picat: General-purpose, multi-paradigm, logic-based programming language
rOWLer: OWL-based legal reasoning engine. Not sure it got any real use
s(CASP)
Turnip: Defeasible deontic logic
VisiRule: Visual decision tree editor backed by Prolog and FLINT

There have been some efforts to combine functional and logic programming (Functional Logic Programming: From Theory to Curry), particularly:
Curry: Integrated functional logic language
Mercury: Pure functional, strongly typed logic programming
The Verse Calculus: a core calculus for functional logic programming (Simon Peyton Jones)

Index of /project/Breccia: Markup language for logically structured text (?)
A type system for logic programs - ScienceDirect
{2001.08133v1} Drawing Prolog Search Trees: A Manual for Teachers and Student…
Justifications for Logic Programming (as in explanations)

Imagine a table with some bowls of water on it. The water on the table is like data in a computer.

Imagine putting some spoons on the table. You can use the spoons to move water between the bowls.

The spoons are like statements in imperative programming. You can do whatever you want at any time. The attraction is obvious: if you want the water in one bowl to be in another bowl, you just pick it up and move it (even if it's a bit tedious). To put this another way, imperative code is very flexible. This is an important strength.

But there is a corresponding weakness. Imagine walking up to this table, which you know represents some program:

Now: What does this program do? Where is the water supposed to go, and why? How well do you understand the domain? These are very hard questions to answer, just from looking at the layout of the bowls and spoons. This is what I think about when I describe code like this as being not very expressive.

Now, we could add some documentation, maybe some labels on the bowls, maybe a little manual that we keep on the table next to them.

But this doesn't feel very good. Don't we wish the code would just say more by itself? Also, nobody actually writes documentation, much less reads it.

So, let's try something else. We'll get rid of the spoons, and replace them with pipes connecting the bowls.

You can pour water in at the top, and it flows to the bowls as directed by the pipes.

Great! This feels good. When I walk up to this table, I feel much more confident that I can understand where the water is going, and maybe I even have a glimmer of what this program is for. This is something like functional programming, where the pipes are like (pure) functions. It's more expressive, which we like, but we had to sacrifice some flexibility to achieve that. Let's say I want to flick some water across the room at my cat, who is being bad.

If I still had my spoons, this would be very easy.

With my pipes, I can still do it, but it's harder. I have to figure out a way to run a pipe up to that shelf, to get water up that high I need to start pouring from a different point, etc.

So, when we move from imperative to functional code, we gain expressiveness and lose flexibility. Many people consider this an acceptable trade-off. Some people consider it actually a win-win, flexibility being something programmers should not be trusted with in the first place.

OK. Let's do it again. Trade even more flexibility for even more expressiveness. Imagine our table is a half sphere, round side down, so it can tilt in any direction. We'll keep our pipes connecting the bowls, but instead of being inclined, they're parallel with the table. Now, to move the water around, we tilt the whole table.

This is kind of like logic programming, and our levelled pipes are like relations. They don't determine how to move water around, they just establish connections between the bowls. It's up to us to issue some kind of query (tilt the table) to get the program to actually "do" something. Note also that there isn't really a notion of input or output - there isn't an entry point at the top of the pipes and bowls at the bottom. The water is all in the system already, and we can slosh it around through the pipes in whatever direction we want. For example, I can tilt it so the "dirty water" bowl is at the bottom, asking, "Is there any dirty water?" Or I can tilt it so the drinking water bowl is at the bottom, asking "Do we have any drinking water?"

Think about the equation y = 2x. What is the procedural interpretation of this equation? That is, how do you "do" it, how do you "perform" it?

How about: y(x) => x * 2

Looks good. But that's only one way of looking at it. An equivalent formulation of the equation would be x = y/2. So we need another function, that we might think of as running "backwards": x(y) = y / 2.

OK. What if we add a variable? Think about y = 2x + 3z. We could also represent this as x = (y - 3z)/2, or as z = (y - 2x)/3, or (most neutrally) as 2x - y + 3z = 0.

Maybe you see where this is going. For an equation with n variables, we need n! functions to express all the different ways we might "run" it, that is, plug in n - 1 variables to find the missing value.

But wait! Even that isn't enough. Maybe we have incomplete information - we only know a value for one out of the three variables, and we want to know how that constrains the values of the other two. Now we're really in trouble, and it's time to revisit our premises.

The original question didn't really make sense. There is, in fact, no authoritative procedural interpretation of y = 2x. It's just a statement of fact, a relation between quantities. The equation doesn't define a specific procedural interpretation at all and, by the same token, it admits as many procedural interpretations as you can imagine. We could just as well plot it as solve it for some specific value. We would be better off to think of the relation as data, not code.