A Logic Programming Appetizer

http://kilian.evang.name/

Functional Groningen, 2014-05-08

Logic programming: common preconceptions

  • purely academic
  • niche: expert systems
  • torturing CS undergraduates

Logic programming: reality (excerpt)

  • SWI-Prolog
    • general-purpose programming language
    • rich library, web application framework
    • numerous commercial uses
    • specialty: RDF, linked data
    • neither type-safe nor pure
  • Mercury
    • type-safe and pure
    • continuous development since 1995
    • still obscure

What do I like about logic programming?

  • programs are small
  • programs look very declarative

 

→ programs are very readable

Logic programs are small

What makes Prolog systems small? Complex question, but we can identify various factors. With backtracking instead of control structures, Prolog eliminates the 90% of loops that are actually iterators. Backtracking often eliminates error handling. Partial binding and incomplete structures eliminate much data reformatting. And in general, there's just a lot more case based reasoning, which means a lot less ceremony associated with handling of edge conditions.

— Anne Ogborn

Prolog Example 1: Family

  • predicates, clauses, terms, variables
  • backtracking
  • bidirectional predicates
  • wandering between worlds
    • the lazy world of backtracking
    • the eager world of (proper) lists (findall/3, member/2)
    • the procedural world of effects (forall/2)
  • higher-order predicates

Prolog Example 2: Celsius/Fahrenheit

  • bidirectional interface, monodirectional implementations
  • extra-logical predicates (var/1)

Prolog Example 3: Greetings

  • pattern matching and guards
  • structured documentation: input/output arguments, determinism

Prolog Example 4: Max

  • steadfastness
  • danger of predicates allowing more modes than the programmer thought about

Mercury

  • pure logical
  • predicates must declare argument types
  • predicates must declare allowed modes
  • each mode must declare its determinism
  • single-mode predicates can use functional syntax

Mercury example 1: Max

  • functional syntax
  • no cut, have to use if-then-else
  • state handled by world-passing, state variables

Mercury example 2: Family

  • allowed modes declared explicitly
  • aggregate/4 for processing all solutions
  • lambda syntax could be friendlier

Mercury example 3: Celsius/Fahrenheit

  • advanced: different clauses for different modes

Discussion time!

Two penguins shouting at each other

Photo courtesy of Adam Arroyo, CC BY-NC-ND 2.0