Prolog Schemes

This library provides a polymorphic implementation of commonly abstracted operations such as map, fold, member etc. along with a rich DSL for specifying complex data structures they can be applied to. It is inspired by type-classes, optics and recursion schemes found in functional languages, but thanks to Prolog’s flexibility and lack of type constraints can blend them into one.

General structure

Every predicate exported by the library expects its first argument to be a scheme - a sufficiently grounded term describing the structure of the following arguments. Eg.:

:- combined(int(+), 1, 2, Sum),
   assertion(Sum = 3).

will add its arguments as integers.

The scheme has to be grounded only as much as needed, and can be backtracked over:

:- empty(int(Op), E),
   assertion((Op = +, E = 0 ; Op = *, E = 1)).

Composing Types

Content Types

Operator : is used to indicate the type of contents of a complex type:

:- reduced(list:int(+), [1,2,3], Sum),
   assertion(Sum = 6).

Nesting

Operator / composes two container types together, for example:

:- mapped(list/list, plus(1), [[1,2],[3]], List),
   assertion(List = [[2,3], [4]]).
% Sum all nested elements.
:- reduced(list/list:int(+), [[1,2],[3]], Result),
   assertion(Result = 6).

Sometimes we want to use different operation at different levels and this can be reflected in the schema:

% multiply the elements of inner lists and sum the results.
% parentheses are necessary here
:- reduced((list:int(+)) / (list:int(*)), [[1,2],[3]], Result),
   assertion(Result = 5).

A nice feature that comes with this syntax is that where eg. a Scala type List[List[Int]] can be ambiguously interpreted as a functor, in Prolog we can differentate between

• list / list : int(+) for a functor List[List[*]]
• list : list : int(+) for a functor List[*].

Alternative

Multiple possible patterns a value can take can be listed using ; operator:

:- reduced(list / (list ; id) : int(+), [1, [2,3], 4], Sum),
   assertion(Sum = 10).

Warning: This feature can cause excessive backtracking, incorrect results or domain errors, due to lack of reliable type information. A general rule is that types that can be checked at runtime like lists and functors should go first.

Supported Types

Integers

Various ways to interpret integers are supported using the int(Op) scheme. For now supported operations are +, *, max and min.

Atoms

Atom literals can be specified as atom(Atom) and are treated as an empty container if necessary.

:- reduced(list / (atom(fizz) ; atom(buzz) ; id) : int(+), [1, 2, fizz, 4, buzz], Sum),
   assertion(Sum = 7).

Tuples

Tuple schemes are represented as tuples of schemes.

:- empty((int(+), int(*), list), Empty),
   assertion(Empty = (0, 1, [])).

Id

Sometimes we want to treat a value as a container of itself. We can achieve this using the id scheme:

:- mapped(id, plus(1), 5, V),
   assertion(V = 6).

Functors

Functor schemes are denoted by functor(Symbol, Arity, Arguments). Functor Arguments are specified by their number (starting 1) and nested types are supported using / operator:

:- mapped(functor(f, 2, [1, 2/list]), plus(3), f(1, [2]), V),
   assertion(V = f(4, [5])).

Both Symbol and Arity can be unbound.

Dicts

SWI-Prolog’s dicts are supported in a similar fashion:

:- mapped(dict(f, [a, b/ list]), plus(3), f{ a: 1, b: [2] }, V),
   assertion(V = f{ a: 4, b: [5] }).

List indexing

A subset of list indexes can be specified using CLP(FD) domain syntax:

:- use_module(library(clpfd)).
:- contains(elems([1, 3..5, 7..sup]), [1,2,3,4,5,6,7,8,9], V),
   assertion(member(V, [1, 3, 4, 5, 7])). % etc

Recursion

Recursion is explicitly indicated using rec(Rec, Type) scheme:

% recursively defined comma-list
:- CommaListType = rec(Rec, functor(',', 2, [1, 2/(Rec ; id)])),
   List = (1, 2, 3),
   mapped(CommaListType, plus(1), List, NewList),
   
   assertion(NewList = (2, 3, 4)).

Notice how the Rec variable is used at the recursion point.

More Examples

Easy data aggregation

We can make use of various combine operations for integers to compute simple statistics for a given list of values:

sum_max_min(List, Sum, Max, Min) :-
    Type = list:(int(+), int(max), int(min)),
    mapped(Type, [X, (X,X,X)]>>true, List, InterList),
    reduced(Type, InterList, (Sum, Max, Min)).

:- List = [3,6,8,3,7], sum_max_min(List, Sum, Max, Min),
   assertion(Sum = 27, Max = 8, Min = 3).

Notice that since schemes are purely declarative, we can interpret the same value in terms of different algebraic structures: monoids with sum, max and min operation.

Disclaimer: Code above doesn’t work due to CLPFD not allowing sup and inf as values, but is left as example for the time being.

Optics

Assume we have a list of employee salary data and want to give everone a $10 raise. We can use a more concise syntax to point exactly at employee salaries:

:- Employees = [
       employee{name: keanu, surname: reeves, salary: 100},
       employee{name: dwayne, surname: johnson, salary: 90},
       employee{name: justin, surname: bieber, salary: 1}
   ],
   EmployeeSalaries = list / {salary},
   GiveRaise = [Salary, NewSalary]>>(NewSalary is Salary + 10),
   mapped(EmployeeSalaries, GiveRaise, Employees, NewSalaries),
   assertion(NewSalaries = [employee{name: keanu, surname: reeves, salary: 110} | _] ).

:- BinaryTreeType = rec(Rec, (atom(nil) ; functor(node, 3, [1/Rec, 2, 3/Rec]) )),
   Tree = node(node(nil, 1, nil), 2, node(nil, 3, nil)),
   mapped(BinaryTreeType, plus(1), Tree, NewTree),
   reduced(BinaryTreeType:int(+), NewTree, Sum),
   assertion(Sum = 9).

Types and operations table

	empty	combined	mapped	folded	reduced	contains
composable	no	no	yes	yes	yes	yes
id	x	x	x		x	x
int(_)	x	x
atom(_)	x		x			x
list	x	x	x	x	x	x
tuple	x	x
functor	x		x	x	x	x
dict	x		x	x	x	x
elems		x	x			x

DSL Overview

Type	Long syntax	Shorthand
Id	id
Int	int(-Operation)
Tuple	(+Types)
Atom	atom(+Atom)
List	list	[]
Elems	elems(+Domain), elems([+Domains])	[+Domains]
Dict	dict(Symbol, [+Fields])	{+Fields}
Functor	functor(-Symbol, -Arity, +Fields)	at(+Field)
Nesting	T1 / T2
Content	T1 : T2

Known bugs and issues

• empty elements for int(max) and int(min) are useless (not acepted by is and CLPFD)
• sum-type schemes (alternatives with ;) cannot be handled safely in general

Instalation

The library is not yet packaged and the only way to install it is to clone this repo onto your library path.

Mentions

This project takes a lot of inspiration from Scala projects: [Cats](https://github.com/typelevel/cats), [Quicklens](https://github.com/softwaremill/quicklens), [Monocle](https://github.com/julien-truffaut/Monocle) and [Algebird](https://github.com/twitter/algebird).