mdiep / logician

Logic programming in Swift

Logician

Logic programming in Swift

Logic Programming

Logic programming is a declarative style of programming that uses constraints to describe problems. Instead of writing a solution to the problem, you describe the characteristics of the solution and let the computer solve it for you.

Here are some example problems that are a good fit for logic programming:

• Coloring a map/graph so adjacent regions don’t use the same color
• Resolving dependencies in a package manager
• Solving puzzles like sudoku, n-queens, etc.

Different logic programming implementations contain different types of constraints.

Installation

Logician is compatible with Swift Package Manager. Add the following line into your Package.swift dependencies: .package(url: "https://github.com/mdiep/Logician.git", .branch("master")

Using Logician

In order to use Logician, you need to be familiar with 3 concepts:

1. Variable

   A variable describes an unknown value in a logic problem, much like variables in algebra. Logician variables are generic over a value type.

2. Goal

   A goal represents some condition that should be true in the solved state. It’s currently implemented as a (State) -> Generator<State>. A goal can diverge and return multiple possible states or terminate, signaling that a constraint was violated.

   Logician provides a number of built-in goals—like ==, !=, distinct, &&, ||, all, and any—that should provide a good start in most cases.

3. solve

   This function is the interface to Logician’s solver. Its block takes Variables to solve as input and returns Goals to solve for.

Logician is still in its early stages. Its current implementation is based on the miniKanren approach of using functions that return generators. This is likely to change in the future in order to enable optimizations.

Examples

Logician includes playgrounds with a sudoku solver and an n-queens solver that demonstrate usage of the library.

License

Logician is available under the MIT License

Learn More

The following are good resources for learning more about logic programming:

• Logic Programming in Swift

  An explanation of how logic programming works in Swift.

• μKanren: A Minimal Functional Core for Relational Programming (pdf) by Jason Hemann and Daniel P. Friedman

  This paper explores what forms the minimal logic programming language in Scheme. It strips away the complexity of more capable solvers to expose the core idea.

• Kanren.swift

  Swift playgrounds with implementations of various Kanrens.

• Hello, declarative world by @tomstuart

  A brief explanation of logic programming and a minimal language in Ruby.

• The Reasoned Schemer by Daniel P. Friedman, William E. Byrd and Oleg Kiselyov

  An unorthodox book, in the style of The Little Schemer, that has pages of exercises that demonstrate how a kanren-style logic programming works.

• Constraint Processing by Rina Dechter

  An in-depth look at constraints, algorithms, and optimizations. This book explains all you need to know to write a complex solver.

logician's Issues

Add a bimap method to Variables

Followup from #4.

map lets you create a Property, which acts as a unidirectional goal.

Bidirectional goals require mapping in both directions; hence bimap.

Inspect two variables

How can I create a goal that depends on the value of two or more variables?

Fill out the README

Should contain a code snippet, some links, and some examples uses.

Store constraints as values that can be inspected and manipulated

In order to optimize based on constraints, we need to be able to inspect constraints to some extent—instead of immediately evaluating them.

Add a map method to Variables

As a way of adding constraints

// should find "mouse", "moose"
let fourLetterWords: AnyIterator<String> = solve { word in
    return word.map { $0.length } == 5
        && any(
            word == "dog",
            word == "cat",
            word == "mouse",
            word == "moose",
        )
}

SwiftPM compatibility

Add domain constraints

let x: Variable<Int>
let goal: Goal = (5..<10).contains(x)

Build up complex values

You should be able to solve for something more than just a primitive type by solving based on its properties.

Move your blog entry onto github

It's good stuff and helps understand why I would want to use Logician.

Use Result

try/catch will work well in some places yet, but it'd be nice to have the types and it will enable some source improvements.

Add support for deconstructing tuple variables

Given Variable<(A, B)>, you should be able to get Variable<A> and Variable<B>.

Not running with Xcode 9 and Swift 4

Using Xcode 9, the compile failed with

Command failed due to signal: Segmentation fault: 11

Add an Xcode playground with examples

• N Queens
• Sudoku

iOS framework

bimap should be able to throw if a value can't be converted

For instance, integer multiplication would require division with no remainder. Given a * b == 12 where a and b are integers, b == 7 shouldn't unify.

Add inequality constraints

let x = Variable<Int>()
let goal: Goal = x != 5

Add a Stream type

Using AnyIterator has worked well so far, but it's started to feel a bit cumbersome. I think this will simplify the code.

Implement an "all different" goal

Not sure what this should look like from an API standpoint. But the code to implement it already exists.