Types of Programming

Logic Programming

Expressing programs as a set of logical facts and rules, letting the engine find solutions.

Overview

Logic Programming expresses programs as a set of logical facts and rules. The runtime (inference engine) derives conclusions through backward chaining or forward chaining. The programmer declares what is true; the engine determines how to prove it. Prolog is the canonical language. Datalog (a Prolog subset) powers production systems like Datomic queries and Souffl for static analysis.

Origin

Alain Colmerauer and Philippe Roussel created Prolog at the University of Aix-Marseille in 1972. It gained commercial interest during Japan's Fifth Generation Computer Systems project (1982-1992). Datalog emerged as a safer, more tractable subset in the 1980s. Modern applications include Datomic (Rich Hickey, 2012) and clj-datalog, tlaplus, and Answer Set Programming.

Examples

Prolog-style family relationships

# Simulating Prolog-style inference in Ruby with a rule engine
class KnowledgeBase
  def initialize
    @facts = []
    @rules = []
  end

  def assert(fact) = @facts << fact

  def rule(name, &block) = @rules << { name: name, proc: block }

  def query(goal)
    @facts.include?(goal) || @rules.any? { |r| r[:proc].call(goal, self) }
  end
end

kb = KnowledgeBase.new
kb.assert([:parent, :tom, :bob])
kb.assert([:parent, :bob, :ann])
kb.assert([:parent, :bob, :pat])

kb.rule(:grandparent) do |goal, base|
  next false unless goal[0] == :grandparent
  _, gp, gc = goal
  base.query([:parent, gp, :_any]).any? do |mid|
    base.query([:parent, mid, gc])
  end
end

This illustrates the declarative rule-assertion model. Production systems use SWI-Prolog or Datalog engines rather than hand-rolling inference. The key insight is that adding a fact or rule changes what the engine can derive without touching existing code.

Datalog-style queries with Datomic in Clojure

# Equivalent Datalog query (shown as commented pseudocode) for context
# [:find ?name ?email
#  :where
#  [?u :user/role :admin]
#  [?u :user/name ?name]
#  [?u :user/email ?email]
#  [?u :user/active? true]]

# Ruby equivalent using a simple triple store
triples = [
  [1, :name, 'Alice'],   [1, :role, :admin],   [1, :active, true],
  [2, :name, 'Bob'],     [2, :role, :editor],  [2, :active, true],
  [3, :name, 'Carol'],   [3, :role, :admin],   [3, :active, false],
]

def query_triples(triples, conditions)
  entities = triples.map { |e, _, _| e }.uniq
  entities.select do |e|
    conditions.all? do |attr, val|
      triples.any? { |eid, a, v| eid == e && a == attr && v == val }
    end
  end
end

admin_ids = query_triples(triples, { role: :admin, active: true })
admin_ids.map { |id| triples.find { |e, a, _| e == id && a == :name }&.last }
# => ["Alice"]

Datalog queries compose conditions without specifying join order. The query engine optimises execution. Datomic's immutable database enables time-travel queries by parameterising the database value at a given transaction.

Use Cases

01Static analysis and type checking tools (Souffl, CodeQL) where relationships between program entities are expressed as Datalog rules
02Configuration and policy languages (OPA/Rego for Kubernetes admission control) where access rules are logical clauses
03Natural language processing and knowledge graphs where facts and inference over relationships are the primary operation
04Scheduling and constraint satisfaction problems (timetabling, resource allocation) where Prolog's built-in backtracking search is effective

When Not to Use

//General-purpose application development where Prolog's performance and tooling ecosystem are inferior to mainstream languages
//When developers are not familiar with unification and backtracking; debugging unexpected backtracking is significantly harder than debugging imperative code
//I/O-heavy programs where Prolog's I/O model and concurrency support are weak compared to modern runtimes

Technical Notes

Prolog's execution uses SLD resolution (Selective Linear Definite clause resolution) with depth-first search and backtracking. Cut (!) prunes the search tree and can dramatically affect correctness if misused
Datalog is a Prolog subset that disallows function symbols and requires range-restriction (every variable in the head appears in the body). These restrictions guarantee termination and polynomial-time evaluation
Answer Set Programming (ASP, Potassco/Clingo) extends Datalog with negation-as-failure and disjunctive rules; it can solve NP-complete problems declaratively and is used in bioinformatics and planning
Datomic uses a Datalog variant called Datomic Query that runs against an in-process database value passed as an argument; the database is immutable, so queries are pure functions with no side effects