Examples

The examples/ directory of the repository holds runnable examples. Each example has a README, a run script, and a file expected.out with the exact output of the run script. Most examples have a Python driver, go.py, and one Curry module.

To run an example, stage Sprite with make stage and run the script from the example directory:

cd examples/10-queens-set-functions
./run

A run script uses the installed Sprite with the flags of SPRITE_INTERPRETER_FLAGS. The script of example 03 adds interpret:off to them, so the module is compiled before it runs and the example prints the first line of the generated C++ (its README says why). Example 04 runs on the reference backend of the developer notes, which its run script selects: it saves a module in the saved form of that backend.

The first run of an example also runs the Curry front end on its module. That takes a fraction of a second per module: example 01 took 0.56 s on its first run and 0.15 s on the second, on the machine of this text. The test tests/unit_examples.py runs every example on the backends it declares and compares the output with expected.out; the backends named below are the ones of that test.

The sections below name each example, its backends, and its idea, and quote its README.

Run Curry programs with sprite-exec

Directory examples/00-run-curry-programs.

One program runs three ways: by file name, by module name, and with another goal. Its two goals show call-time choice: a shared choice gives two values, two independent choices give four.

cd examples/00-run-curry-programs
./run

Run Curry programs with sprite-exec
===================================

This example runs one Curry program in three ways with sprite-exec, the
command-line interpreter of Sprite.  The program is program.curry.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Call-time choice.  The program defines

    flip = True ? False

The operator ? is a non-deterministic choice.  The goal main binds x to flip
once and returns (x, x).  Both components share the one choice, so main has
two values: (True, True) and (False, False).

The goal mainalt returns (flip, flip).  The two calls of flip are independent
choices, so mainalt has four values.  The difference between the two goals
is the whole point of call-time choice.


2. What the example shows about running Curry
----------------------------------------------

sprite-exec runs a program by file name.  With the -m switch it runs a module
that it finds on CURRYPATH.  It evaluates the goal main by default.  The -g
switch names another goal.  sprite-exec prints every value of the goal, one
per line.  The example uses no Python code.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run


4. Expected output
------------------

The file expected.out holds the exact output of ./run:

    % sprite-exec program.curry
    (True, True)
    (False, False)
    % CURRYPATH=. sprite-exec -m program
    (True, True)
    (False, False)
    % sprite-exec program.curry -g mainalt
    (True, True)
    (True, False)
    (False, True)
    (False, False)


5. Limits
---------

The program is tiny.  A warm run of ./run took 0.4 s on the C++ backend.  The
first run also compiles the program with the Curry front end, which takes
about half a second more.

Run a Curry program from Python

Directory examples/01-run-with-python.

The first contact with the Python API. A script imports a Curry module from its own directory and prints every value of a goal.

cd examples/01-run-with-python
./run

Run a Curry program from Python
===============================

This example is the first contact with the Python API.  The script go.py
imports the Curry module rev.curry and prints the values of its goal.


1. What the example shows about functional logic programming
-------------------------------------------------------------

The module rev.curry defines list reversal with two functions:

    append :: [t] -> [t] -> [t]
    append []     x  = x
    append (x:xs) ys = x : append xs ys

    rev :: [t] -> [t]
    rev []     = []
    rev (x:xs) = append (rev xs) [x]

The goal main is rev [1,2,3,4].  The functions are deterministic, so the goal
has one value.  A Curry goal may have several values, and the Python side is
written for that case.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The script adds its own directory to curry.path, the search path for Curry
modules.  Then it imports the module from the virtual package curry.lib:

    from curry.lib import rev

The import compiles rev.curry and loads it.  The functions of the module are
attributes of the module object.  The call

    curry.eval(rev.main)

returns an iterator over the values of the goal.  The script prints each
value.  A Curry value prints in Curry syntax, so a list of Ints prints as
[4, 3, 2, 1].


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run


4. Expected output
------------------

The file expected.out holds the exact output of ./run:

    % python go.py
    [4, 3, 2, 1]


5. Limits
---------

A warm run of ./run took 0.2 s.  The first run also compiles the module
with the Curry front end,
which takes about half a second more.

Compile Curry code at run time

Directory examples/02-dynamic-code-generation.

A Python program compiles a Curry module from a string and builds two goals, one with curry.expr and one with curry.compile. Each compile runs the Curry front end.

cd examples/02-dynamic-code-generation
./run

Compile Curry code at run time
==============================

This example compiles Curry code from strings inside a Python program.  It
builds a module, builds two goals, and evaluates them.


1. What the example shows about functional logic programming
-------------------------------------------------------------

The module defines the natural numbers as data:

    data Nat = O | I Nat deriving Show

and two functions, natToInt and natFromInt, that convert between Nat and
Int.  The functions are deterministic.  The point of the example is the
Python side.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

Compiling a module.  The call

    Nat = curry.compile('''...''')

passes Curry source text to the front end and returns a module object.  The
constructors and functions of the module are attributes of that object.

Building a goal without the front end.  The call

    curry.expr(Nat.natToInt, [Nat.I, Nat.O])

builds the expression natToInt (I O) directly.  A Python list whose first
element is a Curry symbol is an application of that symbol.

Compiling an expression.  The call

    curry.compile('natFromInt 3', mode='expr', imports=Nat)

passes an expression to the front end, with the module Nat in scope.  The
front end checks the types.  curry.expr checks them too, from the type
schemes in the interface the front end wrote for Nat.  It reports an error
when the expression is built.

Both goals go to curry.eval, which returns an iterator over the values.  The
script takes the first value of each with next.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run


4. Expected output
------------------

The file expected.out holds the exact output of ./run:

    % python go.py
    goal1: natToInt (I O)
    1
    goal2: natFromInt 3
    I (I (I O))


5. Limits
---------

Each call of curry.compile runs the Curry front end, which costs about a
third of a second.  The script compiles twice on every run, so ./run took
0.8 s.  Code compiled from a string is not cached between runs.

Inspect Curry objects from Python

Directory examples/03-inspect. Runs on the C++ backend, with the module compiled before it runs (the interpreter flag interpret:off; see Interpreter flags).

The module curry.inspect lists the symbols and the types of a loaded module and finds its ICurry files. The example also prints the code that the backend generated for one function.

cd examples/03-inspect
./run

Inspect Curry objects from Python
=================================

This example looks inside a loaded Curry module with the module curry.inspect.
It lists the symbols and the types of the module Nat, finds the files that
hold its ICurry, and prints the code that the backend generated for one
function.


1. What the example shows about functional logic programming
-------------------------------------------------------------

The module Nat.curry defines the natural numbers as data and two conversion
functions.  The example shows what Sprite makes of such a module: ICurry,
the intermediate language of the Curry front end, and the code of the
backend.  The generated code for natToInt shows the shape of a Curry
function in Sprite.  It brings its argument to head normal form, selects on
the constructor, and rewrites the root of the expression.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The script adds its own directory to curry.path and imports the module Nat.
Then it calls these functions of curry.inspect:

    inspect.symbols(Nat)        the public constructors and functions
    inspect.types(Nat)          the types
    inspect.geticurryfile(Nat)  the ICurry file of the module
    inspect.getjsonfile(Nat)    the ICurry-JSON file of the module
    inspect.getimpl(Nat.natToInt)  the generated code of one function

Types are not attributes of the module object.  The script looks the type up
by its full name, curry.type('Nat.Nat'), and reads its constructors from the
type object.

The symbol list holds two names that are not in the source:
natFromInt_COMPLEXCASE0 and natFromInt_COMPLEXCASE1.  The front end lifts
the guarded rules of natFromInt into these helper functions.

The script prints the names of the ICurry files and the first line of the
generated code on the standard output.  The whole generated code goes to
the standard error stream.  It changes with the compiler, and expected.out
holds the standard output only.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The run script adds interpret:off to the interpreter flags, so the module
is compiled before it runs, and inspect.getimpl reads the generated C++
function from the .cpp file beside the shared library.  That is the code
on the standard error stream, which section 2 describes.  Under the
default of the flag interpret (tiered) a fresh module is interpreted from
its ICurry first, and getimpl shows its bytecode there instead.  The first
line is the banner "/****** Nat.natToInt ******/" under every mode, and
whatever the C++ compiler, so expected.out holds it.  The example runs on
the C++ backend.


4. Expected output
------------------

The file expected.out holds the exact output of ./run:

    % python go.py
    Symbols defined in Nat: I, O, natFromInt, natFromInt_COMPLEXCASE0, natFromInt_COMPLEXCASE1, natToInt
    Types defined in Nat: Nat
    Constructors of Nat.Nat: O (arity 0), I (arity 1)

    ICurry file: Nat.icy
    ICurry-JSON file: Nat.json.z
    Both live under .curry/ next to Nat.curry.

    The C++ implementation of Nat.natToInt starts with:
        /****** Nat.natToInt ******/
    The whole code is on the standard error stream.

The front end writes the ICurry files under .curry/ next to the source, in a
subdirectory named after the front end version.  The whole generated code
follows on the standard error stream.  It is a C++ function of about twenty
lines.  It brings the argument to head normal form, selects on its
constructor, and rewrites the root with 0 for O and with 1 plus the
converted predecessor for I.


5. Limits
---------

A warm run of ./run took 0.3 s.  The first run also compiles the module
with the Curry front end and the C++ compiler, which takes about 2 s
more.  Only the first line of the generated code is part of expected.out,
so a change of the generated code does not change the expected output.

Save a compiled Curry module

Directory examples/04-static-compile. Runs on the reference backend (Developer Notes).

curry.save writes the compiled module in the saved form of the reference backend, a script with a goal, and the script runs the goal. The C++ form of curry.save is an open decision; see the developer notes.

cd examples/04-static-compile
./run

Save a compiled Curry module
============================

This example writes the compiled form of a Curry module to a script with
curry.save, and then runs that script.  The script is the saved form of the
reference backend; the developer notes of the documentation describe it.


1. What the example shows about functional logic programming
-------------------------------------------------------------

The module wildcard_matching.curry matches a string against a pattern with
the wildcards ? and *.  The function tails is non-deterministic: it returns
every suffix of a string.  The matcher calls a set function, set2 aux, on
the string and the pattern, and tests whether the set of results is empty.
The goal main checks ten cases and is True when every case agrees.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The script go.py imports the module and saves it:

    curry.save(wildcard_matching, 'wildcard_matching.py', goal='main')

The saved file is a script that holds the generated code of the module.
The goal argument records the goal to evaluate.  When the script runs, it
imports the Sprite runtime, loads the module, and prints every value of
main.  The script reads -g as sprite-exec does: -g NAME evaluates another
goal of the module.  A program needs a goal: curry.save without one raises
an error.  To save a module as a library for curry.load, pass
module_main=False.

The saved form belongs to one backend.  On the reference backend of the
developer notes of the documentation it is Python.  On the C++ backend
curry.save writes C++ source, so the example runs on the reference backend
only.  The saved program of the reference backend, a script in Python,
retires at the removal gate of issue #82 (the developer notes).  This
example retires with it.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The run script selects the reference backend.  It runs go.py and
then the saved script, wildcard_matching.py.  The saved script is a build
product and is not checked in.


4. Expected output
------------------

The file expected.out holds the output that ./run is meant to produce:

    % python go.py
    Loading and compiling wildcard_matching.curry
    Saving the program to wildcard_matching.py with goal main
    % python wildcard_matching.py
    True

The last line is the value of main.


5. Limits
---------

A warm run of ./run took 0.8 s.  The first run also compiles the module
with the Curry front end, which takes about half a second more.

N queens with set functions

Directory examples/10-queens-set-functions.

A non-deterministic permutation, a functional pattern, and a set function solve the puzzle in four functions. Python counts the solutions of each board size and draws the smallest one.

cd examples/10-queens-set-functions
./run

N queens with set functions
===========================

This example places N queens on an N by N board so that no queen attacks
another.  The program is the QueensSet program from the 2009 paper "Set
Functions for Functional Logic Programming" by Antoy and Hanus.  It solves the
puzzle in four short functions.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Non-determinism as values.  The function perm builds one permutation of
[1..n] with ndinsert.  Both rules of ndinsert apply to a non-empty list, so
each call is a choice.  The program means every permutation at once.

Functional patterns.  The pattern in

    unsafe (_ ++ [x] ++ y ++ [z] ++ _)

names any two queens x and z, with the queens y between them.  The two queens
share a diagonal when abs (x - z) equals length y + 1.

Set functions.  A set function encapsulates the search inside one function.
The expression set1 unsafe p is the set of every value of unsafe p.  The guard
isEmpty (set1 unsafe p) holds when that set is empty.  This negates the
non-deterministic predicate unsafe.  A placement is a solution when it has no
unsafe pair.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds its own directory to curry.path and imports the module
Queens.  It calls the function queens with a Python int.  One call is a
generator of solutions.  The driver collects every value with

    curry.eval(Queens.queens, n, converter='topython')

The converter turns each Curry list of Ints into a Python list of ints.  The
scheduler does not promise an order of the values, so the driver sorts the
solutions.  It then counts them and draws the smallest board.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To try other board sizes, pass them to go.py.  Use the Python of the staged
install.  For example, on the C++ backend:

    SPRITE_INTERPRETER_FLAGS=backend:cxx ../../install/bin/python go.py 7 8


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The key lines are:

    n=4: 2 solutions, smallest [2, 4, 1, 3]
    n=5: 10 solutions, smallest [1, 3, 5, 2, 4]
    n=6: 4 solutions, smallest [2, 4, 6, 1, 3, 5]

The smallest board follows each line.  Each row holds one Q for the queen in
that row.  For n = 4 the board is:

    . Q . .
    . . . Q
    Q . . .
    . . Q .

A size with no solution, such as 3, prints "n=3: 0 solutions" and no board.


5. Limits
---------

The run script uses n = 4, 5, 6.  A warm run of ./run took 0.2 s.  The
first run also compiles the module.  It took about a second more.

Larger boards: n = 7 has 40 solutions and n = 8 has 92.  n = 8 took 1.3 s.

Cryptarithms: SEND + MORE = MONEY

Directory examples/12-cryptarithm.

A structural permutation of the digits and a guard that checks the columns from the units column upward solve any cryptarithm. Python validates the words and prints the completed sums.

cd examples/12-cryptarithm
./run

Cryptarithms: SEND + MORE = MONEY
=================================

A cryptarithm replaces the digits of a sum with letters.  Every letter stands
for one digit.  Different letters stand for different digits.  No word starts
with 0.  The puzzle is to find the digits.  SEND + MORE = MONEY has one
solution, 9567 + 1085 = 10652.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Crypt.curry solves any cryptarithm with one non-deterministic function and
one guard.

  * Non-determinism as values.  "perm [0 .. 9]" is one permutation of the
    digits, and every permutation is one value of that expression.  The
    function is built structurally: "ndinsert" puts a digit at each position
    of a permutation of the remaining digits.  The program contains no loop
    and no backtracking code.

  * Laziness as pruning.  The solver lists the letters units column first and
    pairs them with the permutation.  The guard checks the columns from the
    units column upward.  A permutation whose first digits break the units
    column fails before the remaining letters receive a digit.  The search
    never builds most of the 10! permutations.

  * A general solver.  "solveCrypt" takes any list of addends and any result.
    Each solution of the puzzle is one value of the call.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

go.py reads the words from the command line and checks them in Python: upper
case letters only, at most ten distinct letters.  It passes each word to Curry
as a Python str.  curry.expr converts a str by the type the parameter
expects, a String, so a word of one letter is a String and not a Char.

The call "curry.eval(Crypt.solveCrypt, addends, result, converter='topython')"
returns an iterator.  Each item is one solution, converted to a list of
(letter, digit) tuples.  Curry does not fix the order of the solutions, so
go.py sorts them before it prints them.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run the script:

    ./run

To solve another puzzle, give the words on the command line.  The last word
is the result:

    ../../install/bin/python go.py TO GO OUT


4. Expected output
------------------

    % python go.py
    SEND + MORE = MONEY
      9567 + 1085 = 10652
    solutions: 1

    TWO + TWO = FOUR
      734 + 734 = 1468
      765 + 765 = 1530
      836 + 836 = 1672
      846 + 846 = 1692
      867 + 867 = 1734
      928 + 928 = 1856
      938 + 938 = 1876
    solutions: 7

The file expected.out holds this output.  The test tests/unit_examples.py runs
./run and compares its output with the file.


5. Limits
---------

On the C++ backend the run takes about 1 s after the first compile.  The first
run also compiles Crypt.curry and takes about 2 s.  SEND + MORE = MONEY needs
less than 1 GB of memory; the test runs the example under a 2 GB cap.

Puzzles with up to ten distinct letters and three addends ran in about 2 s,
for example CROSS + ROADS = DANGER and FORTY + TEN + TEN = SIXTY.  A puzzle
with more than ten distinct letters has no solution, and go.py rejects it.

Regular expressions by non-determinism

Directory examples/13-regex-nondeterminism.

A function returns one word of the language of a pattern, and every word is one value, so the function generates the words; matching is unification with the subject. Python parses the pattern syntax into Curry data, lists the words of a star-free pattern, and lists every hit of a search.

cd examples/13-regex-nondeterminism
./run

Regular expressions by non-determinism
======================================

A regular expression denotes a set of words.  This example writes that
meaning as a Curry function: sem returns one word of the set, and every word
of the set is one value.  So sem generates the words of a pattern.  Two more
functions, match and grep, use the words to test a subject and to search it.
A small Python parser turns the usual pattern syntax into Curry data.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Non-determinism as meaning.  The function sem maps a pattern to one of its
words:

    sem (Lit c)   = [c]
    sem Any       = [c] where c free
    sem (Alt a b) = sem a ? sem b
    sem (Seq a b) = sem a ++ sem b
    sem (Star a)  = [] ? (nonEmpty (sem a) ++ sem (Star a))
    sem (Plus a)  = sem a ++ sem (Star a)
    sem (Opt a)   = [] ? sem a

The choice operator ? stands for alternation and for the two cases of a
star.  The list concatenation ++ stands for sequence.  A free Char stands
for the wildcard.  It unifies with any character of the subject.

Generation.  The values of sem r are the words of r.  The pattern (cat|dog)s?
has four words, cat, cats, dog and dogs, and the call sem on it has those
four values.  A word of a pattern with Any holds a free character: a word of
a. is ['a', _a], where _a stands for any character.  A star makes the stream
of words infinite: the words of ab* are a, ab, abb, and so on without end.
The driver prints the first few of them and stops.

Matching by unification.  The function match asks a word of the pattern to
be the subject:

    match r s | sem r =:= s = True

The non-deterministic evaluation of sem r picks the word.  Each unfolding
of a star is a choice.  Unification with the subject prunes a branch at the
first wrong character, so the search is finite.  When no word is the
subject, the guard fails and the call has no value.

Search with free variables.  The function grep splits the subject into three
free parts and asks the middle part to be a word:

    grep r s | pre ++ hit ++ post =:= s & hit =:= sem r = (pre, hit, post)
      where pre, hit, post free

Narrowing binds the free variables: the call pre ++ hit ++ post =:= s
instantiates them to each split of the subject into three parts.  The
bindings of pre, hit and post say where the hit is.  Each hit is one value
of the call.  The module has no matching automaton and no code for
backtracking.

A star repeats only non-empty words of its body.  The helper nonEmpty fails
on the empty word.  Without it a body that matches the empty word, as in
(a?)*, would unfold forever and consume no character.  The language stays
the same.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds its own directory to curry.path and imports the module
Regex.  It parses a pattern with a recursive-descent parser of about forty
lines.  The syntax: a character stands for itself, . is any character, | is
alternation, * + ? repeat the item before them, parentheses group, and a
backslash makes the next character literal.  The parser returns nested
tuples.  The first item of each tuple is the name of a constructor of
Regex.RE.  The function build turns each tuple into Curry data:

    curry.expr(getattr(Regex, tag), *args)

The argument of Lit is a Python str of length one, which curry.expr turns
into a Char, the type the constructor expects.  A subject is a str of any
length, which curry.eval turns into a String under the parameter type.

The Python function words collects every value of sem for a star-free
pattern with converter='topython', which turns each Curry String into a
str, and sorts them, because Curry does not promise an order of the values.
The function first_words takes the first few values of sem for any pattern
with itertools.islice and prints each one with str(), in Curry syntax, so a
word with a free character shows the variable.  The converter rejects such a
word: a free character is not a str.

The Python function match takes the first value of the goal and stops the
search.  A goal with no value means False.  A failed guard is not an error.
The Python function grep iterates over every value of the goal with
converter='topython', which turns the tuple of three Strings into Python
strings.  Curry does not promise an order of the values, so go.py sorts the
hits by position and length.  A pattern such as a*a* derives one hit in
several ways.  Each derivation is one value, so go.py keeps one copy of each
hit.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To try your own pattern and subject, pass both to go.py.  It runs match and
grep on the pair.  Quote the pattern for the shell:

    ../../install/bin/python go.py 'a.*c' xabcacx

To list the words of a pattern, pass --words and the pattern, and the number
of words to print after it (10 by default).  A pattern with a star has no
last word, so the number is the only end:

    ../../install/bin/python go.py --words '(cat|dog)s?'
    ../../install/bin/python go.py --words 'a.b*' 4


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The key lines are:

    words (cat|dog)s?: cat cats dog dogs
    match ab*c abbbc: True
    match a.c axc: True
    match a.c abbc: False
    grep ab*c in xxxxxxxabbbcyyyyyyyy: 1 hit
      xxxxxxx[abbbc]yyyyyyyy
    grep a+b? in zzaaabzz: 9 hits
      zz[a]aabzz
      zz[aa]abzz
      ...
      zzaa[ab]zz
    grep (cat|dog)s? in cats, dogs and a dog: 5 hits
      [cat]s, dogs and a dog
      [cats], dogs and a dog
      ...

The first line is the generation: the four words of a star-free pattern.
grep lists every substring that is a word of the pattern, not only the
longest one at each position.  So a+b? has nine hits in zzaaabzz, and
(cat|dog)s? finds both cat and cats.  The subjects of grep have twenty
characters; section 5 says why.


5. Limits
---------

A warm run of ./run took 0.2 s on the C++ backend.  The first run also
compiles the module, which adds about half a second.

Matching backtracks.  Each unfolding of a star is a choice, and the search
tries every way to spend the subject on the pattern.  So the time of match
grows with the number of those ways, and no bound that is linear in the
subject holds, as it does for an automaton.  grep adds the split
pre ++ hit ++ post, which has a number of cases that is quadratic in the
length of the subject, and asks the pattern at every split.  The subjects of
the run script have twenty characters: a grep of ab*c or of (cat|dog)s? in
one of them took 0.01 s.  A grep of ab*c took 0.04 s in a 41-character
subject, and 0.6 s in an 80-character subject.  A pattern with many hits
costs more.
In the 40-character subject of 25 x's, a b, 9 x's, a b and 4 x's, .*b.*
has 440 hits, every substring with a b, and the grep took 0.4 s.

A grep of ab*c in a subject of 100 x's took 2.0 s with a
peak of 139 MB, and one of 130 x's took 3.5 s with a peak of 176 MB.

curry.expr builds a String in one call (the list of its characters) and a
list in a loop, so the length of a subject is bounded by memory and time,
not by the Python recursion limit.

An expression parser from functional patterns

Directory examples/14-parser-functional-patterns.

Functional patterns split the input around an operator, and a split whose parts do not parse fails. Python prints the parse tree and the value of each expression.

cd examples/14-parser-functional-patterns
./run

An expression parser from functional patterns
=============================================

This example parses arithmetic expressions such as 1+2*3 with three Curry
functions and no parser library.  Each function has a rule with a functional
pattern that splits the input around an operator.  Python prints the parse
tree and the value of each expression.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Functional patterns.  The rule

    expr (l ++ "+" ++ r) = Add (expr l) (term r)

matches every way to split the input around a '+'.  The pattern contains the
function ++ and the variables l and r.  The system matches the input against
every string the pattern can denote.  Each match is one split.

Failure as control.  A split whose parts do not parse fails.  Failure is not
an error in Curry.  It yields no value.  For 1+2+3 the split with l = "1" and
r = "2+3" fails, because "2+3" is not a term.  Only the split with l = "1+2"
survives.  The parse of 1+2+3 is therefore Add (Add (Num 1) (Num 2)) (Num 3),
and the operators associate to the left.

Precedence from the grammar levels.  The right operand of '+' and '-' is a
term.  The right operand of '*' is a factor.  A term never contains a sum
unless parentheses enclose it.  So '*' binds tighter than '+' and '-' without
a precedence table.

The grammar is:

    expr   ::= expr '+' term | expr '-' term | term
    term   ::= term '*' factor | factor
    factor ::= '(' expr ')' | digits

The three Curry functions expr, term and factor follow it line by line.
There is no lexer.  The function eval computes the value of a tree.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds its own directory to curry.path and imports the module
Parser.  For each input it calls

    curry.eval(Parser.expr, s)

curry.eval converts the Python str s by the type of the parameter, a
String, also when s has one character.  The call is a generator of parse
trees.  The driver collects the trees in a list and counts them.  One tree
per input is evidence that the grammar is unambiguous.  An input with no
parse yields an empty list, and the driver prints "no parse".

A parse tree comes back as a Curry value.  Its str form prints the
constructors, such as Add (Num 1) (Num 2).  The driver passes the tree back
to Curry:

    next(curry.eval(Parser.eval, tree, converter='topython'))

The converter turns the Curry Int into a Python int.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To parse other expressions, pass them to go.py.  Use the Python of the staged
install.  The driver removes spaces from each expression.  For example, on
the C++ backend:

    SPRITE_INTERPRETER_FLAGS=backend:cxx ../../install/bin/python go.py '2 * (3 + 4)' '8-1-1'


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The key lines are:

    1+2*3  ->  Add (Num 1) (Mul (Num 2) (Num 3))  =  7  (1 parse)
    2*(3+4)-5  ->  Sub (Mul (Num 2) (Add (Num 3) (Num 4))) (Num 5)  =  9  (1 parse)
    10-2-3  ->  Sub (Sub (Num 10) (Num 2)) (Num 3)  =  5  (1 parse)
    2*(3+4  ->  no parse

The tree for 1+2*3 shows that '*' binds tighter than '+'.  The tree for
10-2-3 shows that '-' associates to the left.  The last input lacks its right
parenthesis.  No split parses, so Python reports no parse.


5. Limits
---------

The number of splits grows with the length of the input.  A warm run of
./run took 0.2 s.  The first run also compiles the module.  It took about
a second.

Longer inputs: an expression of 29 characters took 0.3 s, and one of 44
characters took 2 s.  An input with no parse costs about as
much as a well-formed one of the same length, because the search tries every
split.

A package dependency solver

Directory examples/15-dependency-solver.

A plan picks a version for every package that the roots reach, and a search over the candidates, newest first, finds the consistent plans. A set function pins the preferred plan, and a failure is explained. The index is nested Python data, and the output is a lockfile.

cd examples/15-dependency-solver
./run

A package dependency solver
===========================

This example resolves the dependencies of a package.  An index lists the
versions of every package with their requirements, and a requirement names a
package and a range of its versions.  A plan picks one version for every
package that the roots reach.  The program states the relation: a plan is
consistent when the version it picks for a package meets every requirement
of that package which the plan reaches.  The policy, newest first with the
versions of a lockfile preferred, is a second function over the same search.
The output is a lockfile.  When no plan exists, the program says which
requirement breaks the plan and where the search fails.


1. What the example shows about functional logic programming
-------------------------------------------------------------

The relation is a search.  The function solveFrom keeps the demands still to
meet, in order, and the versions chosen so far:

    solveFrom _   _      _    []                 plan = plan
    solveFrom idx yanked lock ((p, r) : pending) plan =
      case lookup p plan of
        Just v  -> if inRange r v then solveFrom idx yanked lock pending plan
                                  else failed
        Nothing -> solveFrom idx yanked lock (requires idx (p, v) ++ pending)
                                             (plan ++ [(p, v)])
      where
        v = anyOf (candidates idx yanked lock (p, r))

A demand on a package that is in the plan is a test: the chosen version
meets it, or the branch fails.  A demand on a new package is a choice: anyOf
picks one of its candidates, and the requirements of that version come next.
The call anyOf [] fails, so a package without a candidate ends the branch
too.  Every value of solve is a consistent plan of the roots, and the
function has no loop, no backtracking code and no search state.  The runtime
does the search.

The plan holds the closure of the roots and nothing else.  The index has a
package cli, whose one version needs web 1.  The root app does not reach
cli, so no plan of app mentions it, and the requirement of cli does not
constrain web.  A plan over the whole index would pick a version of cli as
well, and app and cli would then have no plan together.  The step with the
roots app 1 and cli 1 shows that case.

The preference is the order of the candidates:

    candidates idx yanked lock (p, (lo, hi)) = locked ++ fresh
      where
        versions = [ v | (q, v, _) <- idx, q == p, lo <= v, v <= hi ]
        locked   = [ v | v <- versions, (p, v) `elem` lock ]
        fresh    = [ v | v <- sortBy (>=) versions, v `notElem` locked
                       , (p, v) `notElem` yanked || lo == hi ]

The version of the lockfile comes first, then the others newest first.  A
yanked version is a candidate only when the lockfile names it or the range
pins it, which is the rule of pip for a yanked release.

A depth-first search over the candidates in that order finds the preferred
plan first.  Sprite does not search depth first.  Its scheduler is fair: a
choice at the root of a configuration replaces it by two configurations at
the back of the queue, and the front of the queue runs on.  The branches of
solve advance in turns, and the first value of solve is the branch that
finishes first, not the first branch in the order of the candidates.  The
order of the values is not promised.  The example pins the plan with a
second function:

    preferredFrom idx yanked lock ((p, r) : pending) plan =
      case lookup p plan of
        Just v  -> if inRange r v
                     then preferredFrom idx yanked lock pending plan
                     else failed
        Nothing -> preferredFrom idx yanked lock
                     (requires idx (p, chosen) ++ pending)
                     (plan ++ [(p, chosen)])
      where
        chosen = head [ c | c <- candidates idx yanked lock (p, r)
                          , leavesAPlan c ]
        leavesAPlan c = notEmpty (set5 solveFrom idx yanked lock
                                       (requires idx (p, c) ++ pending)
                                       (plan ++ [(p, c)]))

Every choice takes the first candidate that still leaves a plan.  The
lookahead is a set function: set5 solveFrom encapsulates the search from the
state after the candidate, and notEmpty asks whether that search has a
value.  The function preferred has no choice of its own, so it has one value
or none, in whatever order the scheduler runs the branches inside the set
function.  Its value is, by definition, the plan that a depth-first search
over the candidates in order finds first.  Section 5 gives the cost.

A failure is the absence of a value.  The roots app 2 have no plan: app 2
needs web 3 and db 2, web 3 needs http 2, and db 2 needs http 1.  Nothing in
the program says so; the branch that picks http 2 for web 3 fails at the
demand of db 2.  Two more functions explain a failure.  The function
conflict runs the search of solve with the requirer beside every demand and
every choice, and returns the first violation of a branch instead of
failing there:

    conflictFrom idx yanked lock (((p, r), by) : pending) plan =
      case lookup p plan of
        Just (v, by') -> if inRange r v
                           then conflictFrom idx yanked lock pending plan
                           else (((p, r), by), [(v, by')], trace)
        ...

A branch that reaches a plan has no violation and fails in conflict.  So
when the roots have no plan, the values of conflict are the ends of every
branch of the search, and the driver prints each one as a sentence.  The
function solvable is the set function of solve under notEmpty.  The driver
deletes one requirement of the index at a time and asks it whether a plan
exists without that requirement.  The requirements whose deletion restores a
plan are the ones that break it.

A root that the index does not know is a mistake in the question, not a
plan that does not exist.  The function unknown lists such roots, and the
driver asks it before the search, so that "no such package" and "no plan"
differ.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The index is Python data: a list of (name, version, requirements) tuples,
and a requirement is a (name, (low, high)) tuple.  The roots have the same
shape as the requirements.  The yanked versions and the lockfile are lists
of (name, version) pairs.  One call,

    curry.eval(Deps.preferred, INDEX, yanked, lock, roots,
               converter='topython')

passes all of it to Curry.  curry.expr converts each argument by the type of
its parameter: tuples become Curry tuples, lists become Curry lists, ints
become Ints, and a str becomes a String, also when the name has one
character.  An empty Python list becomes an empty list of the parameter
type.  The converter turns the plan into a Python list of (str, int) pairs.
preferred is deterministic, so the generator has one value or none, and
next(..., None) reads it.

The values of conflict are nested tuples of strings, ints and lists, and the
converter turns each one into Python data.  The driver iterates over the
values, which is the collection of the set, turns each one into a sentence,
and prints the sentences sorted and once each, because several branches end
in the same violation.

Python owns the question and the files.  The driver parses the roots, the
yank list and the lockfile from the command line, prints the plan as a
lockfile in TOML, and reads a lockfile back with tomllib from the standard
library.  The deletion loop of the explanation is Python too: it builds each
variant of the index and asks Curry one question per variant, solvable.
Curry decides, Python asks.  The exit status is 0 with a plan, 1 without
one, and 2 for a root that the index does not know.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To ask other questions, pass them to go.py.  Use the Python of the staged
install.  A root is NAME=V or NAME=LO..HI, --yank NAME=V marks a version of
the index as yanked, --lock FILE prefers the versions of a lockfile that an
earlier run printed, and --index prints the index first.  For example:

    ../../install/bin/python go.py --index
    ../../install/bin/python go.py app=2
    ../../install/bin/python go.py --yank web=3 app=1
    ../../install/bin/python go.py --lock plan.lock > new.lock

To change the index, edit INDEX at the top of go.py.


4. Expected output
------------------

The file expected.out holds the exact output of ./run, which runs go.py
seven times.  The first run prints the index, the roots and the preferred
plan of app 1..2, as one line and as a lockfile:

    roots: app 1..2
    plan: app 1, web 3, http 2, db 1
    [[package]]
    name = "app"
    version = 1
    dependencies = ["web 3", "db 1"]
    ...

app 2 is the newest version of app, and it has no plan, so the plan takes
app 1.  web 3 is the newest version that app 1 accepts, and it needs http 2.
db 2 needs http 1, so the plan takes db 1.  The second run asks for app 2:

    roots: app 2
    no plan
    a plan exists without any one of these requirements:
      app 2 needs web 3
      app 2 needs db 2
      web 3 needs http 2
      db 2 needs http 1
    every branch of the search ends in a conflict:
      app 2 > db 2 needs http 1, but app 2 > web 3 picked http 2
    exit status 1

The four requirements form the conflict: without any one of them a plan
exists.  The search has one branch, because every choice has one candidate,
and the branch fails at the demand of db 2.  The third run marks web 3 as
yanked, and the plan takes web 2.  The fourth run reads plan.lock, an older
lockfile with web 2, http 1 and db 2.  Those versions still satisfy the
roots, so the plan keeps them all:

    locked: app 1, db 2, http 1, web 2
    plan: app 1, web 2, http 1, db 2

The fifth run asks for app 1 and cli 1 together.  cli 1 needs web 1 and
app 1 needs web 2 or 3, so the six branches of the search all end in a
conflict, four distinct ones.  The sixth run asks for a version that the
index does not have.  No deletion of a requirement restores a plan, and
the one branch of the search fails at the demand of the roots:

    roots: app 5
    no plan
    every branch of the search ends in a conflict:
      the roots need app 5, and the index has no such version
    exit status 1

The seventh run asks for a package that the index does not know:

    roots: tls 1
    no such package: tls
    exit status 2


5. Limits
---------

A warm run of ./run, seven processes, took 1.7 s.  The first run also
compiles the module, which
adds about a second.

The cost is the fair search.  The scheduler advances the branches of solve
in turns, so the first plan arrives when every branch has advanced that
far: on a chain of seven packages with four versions each and no conflict,
16384 plans, the first value of solve took 0.9 s on the C++ backend, where a
depth-first resolver takes seven steps.  The set function is evaluated
lazily, and notEmpty stops at the first value, so the lookahead of preferred
costs one such search per candidate it tries, over the branches below that
candidate alone.  preferred took 0.3 s on that chain, and 5 s with 255 MB on
a chain of eight packages with five versions, 390625 plans, where the first
value of solve took 13 s.  A measurement of this cost against another
resolver belongs
in the benchmark harness, not here: an example runs in seconds and is
pinned by its expected.out.  The applications suite of the harness
(tests/README, section 9) asks this solver and resolvelib, the resolver
of pip, for a plan of generated indexes of growing size.  The benchmark
record of this example is
tests/data/curry/benchmarks/results/apps-2026-10-06-applications.jsonl.

What other resolvers do that this example does not:

  * resolvelib, the resolver of pip, lets its provider order the open
    requirements as well as the candidates, so that the package with the
    fewest candidates is resolved first, and it backjumps to the cause of a
    conflict instead of trying the alternatives in between.  This example
    resolves the demands in the order it meets them and lets the scheduler
    try every branch.
  * PubGrub, the resolver of Dart, Cargo and uv, learns an incompatibility
    from every conflict and never meets the same conflict twice.  It
    explains a failure as a derivation of incompatibilities.  Here a
    conflict that recurs in many branches is met again in every branch, and
    the explanation names the first violation of each branch and the
    requirements whose deletion restores a plan.
  * Both work with version sets, pre-releases and semantic versions.  A
    version here is an Int, and a range is one closed interval.

Out of scope: features and extras, platform conditions, optional
dependencies, several versions of one package in one plan, and the sources
and hashes of a lockfile.

Scheduling tasks fed from Python data

Directory examples/16-scheduling.

Each task gets a start slot by a choice, and guards forbid overlap and enforce precedences. Python grows the horizon until a schedule exists and draws a Gantt chart.

cd examples/16-scheduling
./run

Scheduling tasks fed from Python data
=====================================

This example schedules five kitchen tasks.  Each task has a duration and
needs one resource.  Some tasks must follow others.  Python holds the data
and asks Curry for a schedule that fits a horizon of a given length.  It
grows the horizon until a schedule exists and draws that schedule as a
Gantt chart.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Constraint solving by search.  The schedule in

    starts = [ (n, anyOf [0 .. horizon - d]) | (n, d, _) <- tasks ]

gives each task anyOf the start slots that keep it inside the horizon.  The
call anyOf xs is a choice among the elements of xs.  So the one expression
starts means every assignment at once.

Lazy generate and test.  The guard

    all ordered prec && all noOverlap pairs

keeps the assignments where every precedence holds and no two tasks on one
resource overlap.  A failed guard is not an error.  It produces no value.
The Curry side only states the constraints.  It has no loop, no search
state, and no backtracking code.  The runtime does the search.

The order of the guards matters.  The runtime makes a choice only when the
guard needs its value.  The precedence check comes first.  It forces the
starts along the chain of tasks, and a task that starts too soon fails
before any later task gets a start.  The resource check comes second and
sees only the assignments that survived.

Optimization by failure.  A horizon that is too short has no schedule, so
the call yields zero values.  Python counts upward from the longest task.
The first horizon with a schedule is the shortest one.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The tasks and the precedences are Python data: a list of (name, duration,
resource) tuples and a list of (before, after) pairs.  The driver go.py
passes them to the Curry function schedule with the horizon.  curry.eval
converts them with curry.expr: tuples become Curry tuples, lists become
Curry lists, and ints become Curry Ints.

A name is a Python str.  curry.expr converts it by the type the parameter
expects, a String, also when the name has one character.

One call,

    curry.eval(Sched.schedule, tasks, precedences, horizon, converter='topython')

is a generator of schedules.  The driver takes the first one with next() and
discards the generator.  This stops the search.  A horizon with no schedule
yields zero values, so next() returns the default None, and the driver tries
the next horizon.  The converter turns the schedule into a Python list of
(str, int) pairs.  The driver sorts it by start slot and draws the chart.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To try other tasks, edit TASKS and PRECEDENCES at the top of go.py.  If
several schedules of the same length exist, the first one found may differ
from one run to the next.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The driver prints
the tasks and the precedences first.  Then it prints one line per horizon:

    horizon 8: none
    horizon 9: mix@0 bake@2 cool@5 frost@7 pack@8

The chain mix, bake, cool, frost, pack has a total duration of 9.  So no
schedule fits 8 slots, and exactly one fits 9.  The chart follows, with one
row per task in order of start:

    slot   012345678
    mix    ##.......  bowl
    bake   ..###....  oven
    cool   .....##..  rack
    frost  .......#.  bowl
    pack   ........#  table


5. Limits
---------

The work depends on how early the guards prune.  The precedences prune
early, so a chain of tasks is cheap.  A chain of eight tasks on four
resources took 0.04 s.
Without precedences only the resource check prunes.  It forces the start of
every task that shares a resource, so the work grows with the slot count to
the power of the task count.  Five tasks on one resource and no precedences
took 0.4 s.  Six such tasks ran out of memory under a 2 GB cap.

A warm run of ./run took 0.2 s.  The first run also compiles the module.
It took about a second.

Type inference by unification

Directory examples/17-type-inference.

Free variables are unknown types and =:= is unification. Python builds lambda terms, and an ill-typed term has no value.

cd examples/17-type-inference
./run

Type inference by unification
=============================

This example infers the types of small lambda terms.  The Curry function
infer has one rule for each kind of term.  A free variable stands for a
type that is not yet known, and the constraint =:= unifies types.  Python
builds the terms, calls infer, and prints each term with its type.  A term
with no type prints "ill-typed".


1. What the example shows about functional logic programming
-------------------------------------------------------------

Free variables are unknown types.  The rule for a lambda is

    infer env (Lam x b) = Fun a (infer ((x, a) : env) b)
      where a free

The bound variable x gets the fresh type a.  Nothing is known about a yet.
The body is inferred under that assumption.  Each use of x in the body adds
a constraint on a.

Unification is =:=.  The rule for an application is

    infer env (App f x) | infer env f =:= Fun (infer env x) r = r
      where r free

The type of f must be a function type.  Its argument type must equal the
type of x.  The constraint binds r to the result type.  It can also bind
variables inside the type of f or the type of x.  In \f -> \x -> f (f x)
the inner application binds the type of f to Fun a r.  The outer one binds
r to a.  The result is Fun (Fun _a _a) (Fun _a _a).

A variable that no constraint binds stays free.  The identity \x -> x has
the type Fun _a _a.  The printer names the unbound variables _a, _b, _c in
the order of their first appearance.  Such a type is polymorphic.  The
term works for every choice of _a.

A term with no type has no value.  In 1 2 the type of 1 is TInt, and the
constraint TInt =:= Fun TInt r fails.  Failure is not an error in Curry.
The computation yields zero values, and Python reports ill-typed.  The term
\b -> if b then b + 1 else 0 fails for a subtler reason.  The condition
binds the type of b to TBool.  The addition then needs TInt, and
TBool =:= TInt fails.  The variable y is not in scope.  The lookup finds
nothing, so y has no type either.

The rule for a conditional shares one free variable between the two
branches, so both branches get the same type.  The rule for an addition
requires TInt on both sides.  There is no let, so a variable bound by a
lambda has one type.  In \f -> f 1 + f True the two uses of f need
different types, and the term is ill-typed.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

Python is the front end and Curry is the core.  The driver go.py writes
each term as nested tuples, for example ('lam', 'x', ('var', 'x')).  The
function build maps a tuple to a Curry term with curry.expr:

    curry.expr(Infer.Lam, x, build(b))

The inner call returns a Curry expression, and the outer call nests it in a
new one.  The name x is a Python str.  curry.expr converts it by the type
the constructor expects, a String, also when the name has one character.

The driver calls

    curry.eval(Infer.infer, [], build(term))

The empty Python list is the empty environment.  The call returns a
generator of types.  A well-typed term yields one type.  An ill-typed term
yields none, and the driver prints ill-typed.

A type comes back as a Curry value.  Its str form prints the constructors,
such as Fun TBool (Fun TInt TInt).  An unbound free variable in the value
prints as _a, _b, and so on.  The driver prints the term itself in lambda
syntax with its own function show.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To infer other terms, pass them to go.py as Python literals.  Use the
Python of the staged install.  For example, on the C++ backend:

    SPRITE_INTERPRETER_FLAGS=backend:cxx ../../install/bin/python go.py "('app', ('lam', 'x', ('var', 'x')), ('lit', 7))"

The constructors are var, lam, app, lit, bool, if and add.  They follow the
data type Term in Infer.curry.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The key lines are:

    \x -> x : Fun _a _a
    \f -> \x -> f (f x) : Fun (Fun _a _a) (Fun _a _a)
    \b -> \x -> if b then x + 1 else x : Fun TBool (Fun TInt TInt)
    1 2 : ill-typed

The first line shows an unbound type variable.  The second shows a variable
that unification links across three positions.  The third shows how the
constants fix every variable.  The last term applies a number as a
function, so it has no type.


5. Limits
---------

Inference does not search.  Each term has at most one type, and the cost
grows with the size of the term.  A warm run of ./run took 0.15 s.  The
first run also compiles the module.  It took about a second.

Larger terms: a chain of applications f (f (... x)) of length 150 took
0.03 s, a chain of 500 took 0.3 s, and a chain of 700 took 0.5 s.  A chain
of 1000 hit the recursion limit inside curry.expr.  A term on the command
line has
a lower limit.  A literal of 200 nested applications overflowed the parser
of Python.

There is no occurs check.  The term \x -> x x needs a type a equal to
Fun a r, and no finite type satisfies that.  The run exhausted a 2 GB
address space cap after 7 s.  Do not pass this term.

Text extraction with functional patterns, compiled at run time

Directory examples/18-text-extraction.

Extraction rules are Curry text inside the Python program, compiled once with curry.compile. Curry extracts the fields and tags of each line, and Python aggregates them.

cd examples/18-text-extraction
./run

Text extraction with functional patterns, compiled at run time
==============================================================

This example reads a small log file with two Curry rules and no regular
expressions.  The rule field reads the value of a key from a line of
key=value fields.  The rule tag lists the tag names in a line of markup.
The rules are Curry text inside go.py.  Python compiles them at run time,
applies them to every line of sample.log, and counts the matches.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Functional patterns as an extraction language.  The rule

    field :: String -> String -> String
    field k (_ ++ k ++ "=" ++ v ++ " " ++ _) | ' ' `notElem` v = v

matches a line that contains the key k, then "=", then a value v, then a
space, at any position.  The pattern contains the function ++ and the
variables k and v.  The system matches the line against every string the
pattern can denote.  Each match binds v to one candidate value.

Non-determinism returns every match.  The rule

    tag :: String -> String
    tag (_ ++ "<" ++ t ++ ">" ++ _) | '<' `notElem` t && '>' `notElem` t = t

yields one value per tag.  On the line <p>Hello, <em>world</em>!</p> it
yields p, em, /em and /p.  A tag that occurs twice yields two values.

The guard removes the longer matches.  Without its guard, field "host" on
the line host=alpha status=200 path=/index.html yields three values: alpha,
"alpha status=200" and "alpha status=200 path=/index.html".  Each one is a
valid split of the line.  The guard ' ' `notElem` v keeps only the value
without a space.  The guard of tag rejects a match that spans from one tag
into the next in the same way.

Failure is not an error.  A line without the key yields no value.  The
driver prints "-" for such a cell.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

Compiling Curry text at run time.  The rules are a string in go.py.  The
driver passes the string to

    curry.compile(source, modulename='Rules')

which runs the Curry front end and returns a module object.  The functions
of the module are attributes of that object: Rules.field and Rules.tag.  An
extra rule from the command line (section 3) is appended to the string
before the call, so the module is compiled once.  There is no .curry file,
so the driver does not touch curry.path.

Curry extracts, Python aggregates.  For each line the driver calls

    curry.eval(Rules.field, 'status', line + ' ', converter='topython')

curry.eval converts each Python str by the type of its parameter, a String,
also when the str has one character.  The driver appends one space to the
line, so the last field matches too.  The call is a generator of values.
The converter turns each Curry String into a Python str, the empty String
into ''.  The driver sorts the values, because the scheduler does not
promise an order, and counts them with collections.Counter.

A compile error is not a Python Exception.  curry.CompileError derives from
BaseException.  The driver catches it by name, reports a bad rule on stderr
and exits with status 1.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To add a rule, pass --rule with a name and the body of a Curry equation of
type String -> String.  The driver applies the rule to every line, with one
space appended, and adds a column and a total for it.  For example:

    ./run --rule path '(_ ++ "path=" ++ p ++ " " ++ _) = p'

To see the matches that the guard of field removes, add a rule without a
guard:

    ./run --rule hostAny '(_ ++ "host=" ++ v ++ " " ++ _) = v'

The hostAny cell of the first line then reads

    alpha,alpha status=200,alpha status=200 path=/index.html

To read another file, pass its name after the options.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The table has one
row per line of sample.log.  The key rows are:

    line                                    status  host   tags
    host=alpha status=200 path=/index.html  200     alpha  -
    status=200 host=beta path=/index.html   200     beta   -
    host=beta path=/robots.txt              -       beta   -
    <p>Hello, <em>world</em>!</p>           -       -      /em,/p,em,p
    <ul><li>one</li><li>two</li></ul>       -       -      /li,/li,/ul,li,li,ul

The totals follow the table:

    status: 200 (6), 301 (1), 404 (1), 500 (1)
    host: alpha (4), beta (3), gamma (3)
    tags: /li (2), li (2), /em (1), /p (1), /ul (1), em (1), p (1), ul (1)

The second row shows that the position of a field does not matter.  The
third row has no status, so its status cell is "-".  The tags li and /li
count twice, because each occurrence of a tag is one match.


5. Limits
---------

The compile of the rules costs about half a second on every run.  The
module is built in a temporary directory, so there is no cache.  A run of
./run took 0.8 s, compile included.  One call of field on a 70-character
line took less than 0.1 s.

The cost of field grows with the square of the line length.  The variable k
occurs as a parameter and inside the pattern.  The front end turns the rule
into a lazy unification of the pair (pattern, k') with (line, k), where k'
is a fresh variable.  The pattern therefore tries every substring of the
line as the key before k' meets k.  A rule with a literal key, such as
(_ ++ "status=" ++ v ++ " " ++ _), tries no substring as the key.

The pattern of field also matches a key that ends with k, such as vhost=
for k = "host".  To require a whole key, put " " before k in the pattern
and prepend a space to the line as well.

Blocks World as a command-line application

Directory examples/19-blocks-world-app.

A non-deterministic move and a bounded search give a shortest plan by iterative deepening. An argparse front end parses the worlds and draws the plan, and an optional form uses http.server.

cd examples/19-blocks-world-app
./run

Blocks World as a command-line application
==========================================

This example plans moves in the Blocks World.  A world is three stacks of
blocks.  One move takes the top block of a stack and puts it on another
stack.  The program finds a shortest plan from a start world to a goal
world.  Curry states what a legal move is.  Python parses the worlds,
drives the search, and draws the plan.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Non-determinism as search.  The function move has one rule per source
stack:

    move (x:xs, ys, zs) = (xs, x:ys, zs) ? (xs, ys, x:zs)
    move (xs, y:ys, zs) = (y:xs, ys, zs) ? (xs, ys, y:zs)
    move (xs, ys, z:zs) = (z:xs, ys, zs) ? (xs, z:ys, zs)

The rules overlap, so every rule that matches applies.  Each rule offers a
choice of two target stacks with ?.  So move w means every legal move from
w at once.  The Curry side has no loop, no list of moves, and no search
state.

Failure prunes the search.  The call plan n start goal extends a trace one
move at a time.  A trace that repeats an earlier world fails.  A trace that
uses up its n moves before it reaches the goal fails too.  A failed branch
is not an error.  It produces no value.  The values of plan n are exactly
the traces of at most n moves that reach the goal.

Iterative deepening.  A bound of n moves may have no plan.  Python asks for
bound 0, then 1, then 2, and so on.  The first bound with a plan gives a
shortest plan.  Python takes one plan per bound and stops the search.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py is a small application built with argparse:

    python go.py ABC// //ABC

A world is three stacks separated by slashes.  Write each stack from its
top block to its bottom block.  The driver checks the notation and builds
the Curry data itself.  Each block is the expression of a constructor,
curry.expr(Blocks.A).  A Python list whose first element is a Curry symbol
is an application, not a list, so a stack is a list of such expressions.
A Python tuple of three lists becomes the Curry tuple World.

One call,

    curry.eval(Blocks.plan, bound, start, goal, converter='topython')

is a generator of plans.  The driver takes the first one with next() and
discards the generator.  This stops the search.  A bound with no plan
yields zero values, so next() returns the default None, and the driver
tries the next bound.  The converter turns the trace into a Python list of
tuples of lists.  The blocks come back as Curry constructors.  str() of one
gives its name, and the driver uses that to draw the stacks.

The option --serve PORT starts a web form with http.server from the Python
standard library.  The form calls the same function solve() as the command
line does.  A Flask front end would call the same function.  The run
script does not start the server.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

To plan other problems, pass a start world and a goal world to go.py.  Use
the Python of the staged install.  For example, on the C++ backend:

    SPRITE_INTERPRETER_FLAGS=backend:cxx ../../install/bin/python go.py ABCD// //ABCD

The blocks are A, B, C, D, and E.  The start and the goal must hold the
same blocks.  The option --max-moves N sets the bound at which the search
gives up.  The default is 12.

To use the web form, run

    ../../install/bin/python go.py --serve 8000

and open http://127.0.0.1:8000/ in a browser.  Press Ctrl-C to stop it.

The module has a goal main for sprite-exec.  It prints every plan of at
most five moves for the first problem of the run script.  There is one
plan, so the command prints one line:

    ../../install/bin/sprite-exec Blocks.curry
    [([A, B, C], [], []), ([B, C], [A], []), ([C], [B, ...], []), ([], ..., [C]), ([], ..., [B, C]), ([], [], [A, B, C])]

The worlds of a trace share their stacks, and the printer prints ... in
place of a list that it has printed before.  For example, [B, ...] stands
for [B, A], and a bare ... stands for a whole list printed before.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The script plans
two problems.  The first carries A, B, C from the first stack to the third
stack in the same order.  The key lines are:

    start ABC//  goal //ABC
    bound 0: no plan
    bound 1: no plan
    bound 2: no plan
    bound 3: no plan
    bound 4: no plan
    shortest plan: 5 moves
      1. A to stack 2  BC/A/
      2. B to stack 2  C/BA/
      3. C to stack 3  /BA/C
      4. B to stack 3  /A/BC
      5. A to stack 3  //ABC

Each move names the block and the stack it moves to.  Then it shows the
world after the move in the input notation.  A picture of the trace
follows.  Each world is drawn as three stacks with the top block on top:

    step 0   step 1   step 2   step 3   step 4   step 5
    A . .    . . .    . . .    . . .    . . .    . . A
    B . .    B . .    . B .    . B .    . . B    . . B
    C . .    C A .    C A .    . A C    . A C    . . C
    1 2 3    1 2 3    1 2 3    1 2 3    1 2 3    1 2 3

The second problem reverses the stack onto the third stack.  It takes
3 moves:

    shortest plan: 3 moves
      1. A to stack 3  BC//A
      2. B to stack 3  C//BA
      3. C to stack 3  //CBA

Each of the two problems has exactly one shortest plan.  For a problem with
several shortest plans, the first one found may differ from one run to the
next.


5. Limits
---------

The work grows with the bound.  Each world has up to six moves, and the
runtime keeps the open alternatives in memory.  Three blocks are cheap: a
warm run of ./run took 0.4 s.  Four blocks, ABCD// to //ABCD, need 7
moves.  That took 1.9 s.  Five blocks, ABCDE// to //ABCDE, ran out of
memory under a 2 GB cap after 16 s.  So keep to four blocks.

The first run also compiles the module, which took about half a second
more.

C++ compile time

The examples 20 to 23 form a series. They model the compile-time algorithms of a C++ compiler over one algebraic model of C++ types, the shared Curry modules under examples/cxx: template argument deduction and the partial ordering of specializations, overload resolution, trait checking, and member layout. A template parameter is a Curry free variable, search is non-determinism, and set functions collect the results. The motivation is a future integration with the Circle C++ compiler, whose compile-time metaprogramming can run Python; Sprite would supply the search and the unification, and Circle the types. The model is a simplification of the C++ type system, and each README says what it leaves out. The README of example 20 introduces the series.

Template argument deduction over a model of C++ types

Directory examples/20-cxx-types-deduction.

A template parameter is a free variable, and deduction is unification of the parameter pattern with the argument type. A set function turns a failed deduction into an empty set, and the partial ordering of specializations is deduction again. Python builds the C++ types and prints the answers.

cd examples/20-cxx-types-deduction
./run

Template argument deduction over a model of C++ types
=====================================================

This example opens a series of four.  The series models the compile-time
algorithms of a C++ compiler in Curry: template argument deduction and the
partial ordering of specializations (this example), overload resolution (21),
trait checking (22), and member layout (23).  All four work on one algebraic
model of C++ types, the shared modules under ../cxx.

The algebra is the data type Type of CxxType.curry.  Its constructors are the
type constructors of C++: Fund for a fundamental type, Const, Volatile, Ptr,
LRef, RRef, Arr, Fun, MemPtr, and Class for a class or a class template
applied to arguments.  CxxLimits.curry holds the fundamental types and the
tables of the LP64 data model of the x86-64 ABI: sizes, alignments, digits,
signedness, ranges and conversion ranks.  CxxType adds a normal form, the
traits of <type_traits> as functions, a printer that writes C++ syntax, and
the deduction and ordering algorithms.

A template parameter is a Curry free variable.  Deduction is unification of
the parameter pattern with the argument type.  Search is non-determinism, and
set functions turn a failed search into an empty set.

The motivation is a future integration with the Circle C++ compiler.  Circle
can run Python during compilation, inside its metaprogramming features.  A
Python program there sees the types of the program under compilation.  With
Sprite in that Python, a metaprogram could ask the questions of this series:
which specialization is chosen, which overload wins, which types satisfy a
constraint, and the inverse questions that a compiler never answers, such as
which types decay to a given pointer.  Sprite would supply the search and the
unification; Circle would supply the types.  No such integration exists yet.
The value today is as an analysis, testing and metaprogramming tool.

The model is a simplification of the C++ type system: it has no enumerations,
unions, wide character types, qualified or noexcept functions, no non-type
template parameters, and no derived-to-base conversions.  The model has types
only, so the value category of an argument is encoded in its type: an
argument of type int& is an lvalue of type int, int&& an xvalue, and int a
prvalue.  Section 5 lists what deduction leaves out.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Deduction is unification.  The function template f(T const&) has one
template parameter, T, and one function parameter, the pattern T const by
lvalue reference.  For an argument type a, Python asks the goal

    call ["T"] [ByLRef (Const (Class "T" []))] [a]

The class named T stands for the template parameter.  The library function
deduceCall makes one fresh free variable per name, puts it in place of the
name, and unifies the pattern with the argument type.  The constraint =:=
binds the variable.  The binding is the deduced template argument.  The rule
for a reference parameter strips the reference from the argument and takes
the const off the pattern, and off the argument when the argument has it,
because the referee of a by-reference parameter may be more cv-qualified
than the argument ([temp.deduct.call]/4).  So int deduces T = int, and so
does an lvalue of type int const.  An array argument int[3] is not decayed
by a reference parameter, and T = int[3].  The const of int const[3] is the
const of its elements, so that argument gives T = int[3] as well.  A
function type argument gives T = void (int).

Names, not free variables, in the pattern.  A rule of deduction looks into
the pattern: a forwarding reference is an rvalue reference to a bare
template parameter, and the const of the pattern T const* comes off the
argument.  A function that looks at a free variable narrows it: Curry binds
the variable to every constructor in turn, and each binding is a solution.
A pattern over free variables would then also yield bindings that no
compiler picks, such as T = int const for f(T*) from int*.  So the pattern
names its parameters, deduceCall inspects it with the names in place, and
the names become free variables when the unification starts.  The library
also has deduce, the same deduction over a pattern with free variables; its
comment in CxxType.curry describes where that pattern is exact.

A shared variable is a shared constraint.  Scenario (b) deduces the call
g(pair<T, U*>, T).  Both parameters are patterns over the name T, and the
name maps to one variable:

    call ["T", "U"] [ByValue (Class "pair" [t, Ptr u]), ByValue t] [a1, a2]

with t = Class "T" [] and u = Class "U" [].  A by-value parameter unifies
with the decayed argument.  The first argument binds T to int and U to char.
The second argument must then unify int with its own type.  For the call
with a long second argument the unification fails, and the whole deduction
fails.  There is no code that compares the two deductions of T.  The
variable is the comparison.

Failure is a value of a set function.  A failed deduction has no value, and
a goal with no value prints nothing.  So the goal wraps its deduction in a
set function:

    call names params args =
      report (sortValues (set3 bindCall names params args))

The set holds every binding.  An empty set prints "no deduction".  The
bindings are sorted, because the scheduler does not promise an order of the
values.

Partial ordering by deduction.  A partial specialization S<T*> is more
specialized than S<T> when S<T> can be deduced from S<T*> and not the other
way round ([temp.class.order]).  The library tests the direction with a
synthesized class: it instantiates the pattern T* with the class __synth1
and deduces the other pattern from __synth1*.  Each test needs a fresh copy
of a pattern, and a pattern with free variables cannot be copied.  So a
Template names its parameters:

    Template ["T"] (Ptr (Const (Class "T" [])))

The library replaces the name by a fresh free variable before it deduces
and by a synthesized class before it instantiates.  The match test
matches tmpl target is a set function over the deduction, so a pattern that
does not unify gives False, not failure.  mostSpecialized collects the
matching specializations and keeps those that no other match beats.

The inverse question.  Scenario (d) asks two questions that a compiler never
answers: which types decay to int*, and from which types does f(T const&)
deduce T = int.  The trait decay is a function from types to types, and
deduction is a function from a call to bindings.  A function does not run
backwards.  A free variable and a bounded generator turn it round:

    decaysTo n target | t =:= anyType n && decay t =:= target = t
      where t free

anyType n is every well-formed type of depth at most n, one per value.  It
is the generator of CxxType, which the README of example 22 describes.  The
first equation binds the unknown t to one of them.  The second equation is
the question.  Each solution is one value, and a set function collects
them.  The second question has the same shape with deduceCall in place of
decay: the bindings for the bound type must unify with [("T", int)].


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds two directories to curry.path: its own, for
Deduction.curry, and ../cxx, for the shared modules.  It imports CxxLimits,
CxxType and Deduction from curry.lib.

Python builds the types and the patterns.  Each constructor of CxxType.Type
is applied with curry.expr, for example

    curry.expr(CxxType.Ptr, curry.expr(CxxType.Const, INT))

for int const*, where INT is curry.expr(CxxType.Fund, CxxLimits.Int).  A
template parameter is the class of its name, cls('T'), and a function
parameter is a pattern under ByValue, ByLRef or ByRRef: by_lref(const(T))
is the parameter T const&.  A partial specialization is a Template with the
names of its parameters: template(['T'], ptr(T)) is S<T*>.  A name is a
Python str, which curry.expr converts by the type the constructor expects,
a String, also for a name of one character such as "T"; a list of names is
a list of such strings.  Python can make a free variable: curry.free() in a
goal is one variable (Y1), and the typed builder gives it its type (#56).
This driver keeps its free variables in Curry by choice: deduceCall makes
one per template parameter, and the inverse questions of Deduction.curry
declare one.  Python passes concrete types and patterns.

Every goal returns a String, and the driver reads it with

    next(curry.eval(goal, *args, converter='topython'))

The converter turns the Curry String into a str.  The driver prints the
parameters of a template through Deduction.signature and the argument types
through the Curry printer, curry.eval(CxxType.showCxx, t), so that Python
holds no knowledge of C++ syntax.  The whole driver builds the data, calls
the goals and aligns the columns.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The first run also compiles the two shared modules and Deduction.curry.
The build products go to .curry/ next to each source.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  Scenario (a) has
one template parameter.  Each row gives the parameters of f, the argument
types of the call, and the deduction.  An argument type int& is an lvalue
of type int, int&& an xvalue, and int a prvalue.

    (a) deduce T from the parameters of f and the argument types of a call
      f(T const&)  int              T = int
      f(T const&)  int const&       T = int
      f(T const&)  int[3]           T = int[3]
      f(T const&)  int const[3]     T = int[3]
      f(T const&)  void (int)       T = void (int)
      f(T&&)       int&             T = int&
      f(T&&)       int&&            T = int
      f(T&&)       int              T = int
      f(T)         int const        T = int
      f(T)         int const&       T = int
      f(T)         int[3]           T = int*
      f(T)         void (int)       T = void (*)(int)
      f(T const*)  char*            T = char
      f(T*)        int[3]           T = int
      f(T, T)      int, double      no deduction
      f(T, T)      int, int const&  T = int

The rows show the rules of [temp.deduct.call]:

  * f(T const&): a reference parameter deduces from the type of the
    argument without its reference, and the deduced type may be more
    cv-qualified than the argument ([temp.deduct.call]/3 and /4).  No
    array or function decays: T = int[3] and T = void (int).  The const of
    an array is the const of its elements ([basic.type.qualifier]), so
    int const[3] gives T = int[3] too.
  * f(T&&): a forwarding reference.  With an lvalue argument of type int,
    the type int& is used in place of int, and T = int&; the parameter
    type T&& is then int& &&, which collapses to int& ([temp.deduct.call]/3,
    [dcl.ref]).  With an xvalue or a prvalue of type int, T = int.
  * f(T): a by-value parameter deduces from the decayed argument.  The
    top-level const of int const goes, from the prvalue and from the
    lvalue; an array becomes a pointer to its element, int*; a function
    becomes a pointer to the function, void (*)(int) ([temp.deduct.call]/2).
  * f(T const*): the deduced type char const* differs from the argument
    char* by a qualification conversion, which [temp.deduct.call]/4 allows
    for a pointer, so T = char.
  * f(T*): the array decays before deduction, and T* matches int*
    ([temp.deduct.call]/2).
  * f(T, T): both parameters deduce T, and the deductions must agree
    ([temp.deduct.type]/2).  int and double disagree, and deduction has no
    promotion or conversion to reconcile them.  int and int const& agree,
    because the by-value rule drops the reference and the const first.

Scenario (b) has two template parameters, or a parameter inside a class
template argument:

    (b) deduce the template parameters from the parameters of g and the argument types of a call
      g(pair<T, U*>, T)  pair<int, char*>, int   T = int, U = char
      g(pair<T, U*>, T)  pair<int, char*>, long  no deduction
      g(vector<T>)       vector<int const*>      T = int const*

Section 1 explains the first two rows.  In the third, T occurs only inside
the template argument list of vector, where the match is exact
([temp.deduct.type], the form TT<T>): T = int const*, and no conversion
applies inside the list.

Scenario (c) orders the specializations S<T>, S<T*> and S<T const*>:

    (c) the most specialized of S<T>, S<T*>, S<T const*> for S<...> with
      int                unique: S<T>
      int*               unique: S<T*>
      int const*         unique: S<T const*>
      char const* const  unique: S<T>

The last line is the surprise of the scenario.  The pattern T* does not
match char const* const, because the match of a partial specialization is
exact and the target is a const pointer ([temp.class.spec.match]).  The
primary template is chosen.  This is why the standard library spells out
four specializations for is_pointer: T*, T* const, T* volatile and
T* const volatile.

The second set, S<pair<T, int>> and S<pair<int, T>>, shows the other two
outcomes.  pair<int, int> matches both and neither is more specialized:
ambiguous.  pair<char, int> matches the first only: unique.  pair<char, char>
matches neither: no match.

Three more sets order one pair of specializations at a time:

    (c) the most specialized of S<T>, S<T*> for S<...> with
      int*  unique: S<T*>
    (c) the most specialized of S<T&>, S<T const&> for S<...> with
      int&        unique: S<T&>
      int const&  unique: S<T const&>
    (c) the most specialized of S<vector<T>>, S<vector<T*>> for S<...> with
      vector<int*>  unique: S<vector<T*>>
      vector<int>   unique: S<vector<T>>

S<T*> is more specialized than S<T>: T can be deduced from a synthesized
type U*, and T* cannot be deduced from a synthesized U ([temp.class.order],
[temp.func.order]).  S<T const&> matches int const& with T = int, and S<T&>
matches it with T = int const; the first is more specialized and wins.  For
int& only S<T&> matches, because the match is exact and T const& does not
match a reference to a non-const int.  The same holds one level down,
inside vector<...>.

Scenario (d) prints two lines:

    (d) the types of depth at most 2 that decay to int*: int (&&)[3], int (&)[3], int*, int* const, int* volatile, int*&, int*&&, int[3]
    (d) the types of depth at most 1 from which f(T const&) deduces T = int: int, int const, int&, int&&

Arrays are generated with the bound 3.  The depth excludes int* const& and
int* const volatile, which have depth 3.  The second line is small enough
to check by hand.  The types of depth at most 1 are the fundamental types,
the class Foo of the generator, and one constructor over one of them.
f(T const&) deduces T = int from int itself, from int const, whose const
comes off by the rule of the first rows of (a), and from int& and int&&, an
lvalue and an xvalue of type int.  Every other type gives another T:
int volatile gives T = int volatile, and int* gives T = int*.  The lvalue
of type int const, int const&, has depth 2 and is outside the bound; at
depth 2 the question also finds int const& and int const&&, and nothing
else.  The bare type int const is not the type of a C++ expression: a
prvalue of a cv-qualified scalar type is adjusted to the unqualified type
([expr.type]).  The model deduces from the written type, so that row stands
for an expression of type int const of any value category.


5. Limits
---------

A warm run of ./run took 0.6 s.  The first run also compiles the three
modules; it took about 3 s more.

The generator grows by a factor of six per level of depth.  Depth 0 holds
the 17 fundamental types and one class; depth 1 has 194 types, depth 2 has
1245, and depth 3 has 7330.  The inverse question at depth 3 took 1.2 s,
and it finds 13 types: the cv-qualified and reference forms of int* and of
int[3] up to that depth.

Deduction follows [temp.deduct.call] for a call and [temp.deduct.type] for
the match of a partial specialization.  What the model leaves out:

  * Value categories beyond the encoding of the argument types: a
    reference type is an lvalue or an xvalue, a bare type a prvalue.  A
    bare cv-qualified scalar type, such as int const in scenario (a), is
    not the type of a C++ expression; the model deduces from the written
    type.  Deduction does not check that the reference can bind: f(T&)
    deduces T = int from a prvalue int, and overload resolution would then
    reject the call.
  * Non-deduced contexts.  Every occurrence of a template parameter in a
    pattern is deduced; a nested-name-specifier or an expression cannot be
    written in a pattern.
  * The derived-to-base conversion: a class argument Derived does not
    match the pattern Base<T>, and Derived* does not match Base<T>*
    ([temp.deduct.call]/4).  The model knows no class hierarchy in
    deduction.
  * The function pointer conversion: the model has no noexcept, so there
    is nothing to convert.
  * The qualification conversion covers pointers and pointers to members
    at every level, with the rule of [conv.qual] that an extra qualifier
    below the first level needs const at every level above it:
    f(T const* const*) deduces T = int from int**, and f(T const**)
    deduces nothing.  Inside a class template argument, an array or a
    function type the match is exact.
  * Non-type template parameters: the bound of an array is a number, not
    a parameter, so f(T (&)[N]) cannot be written.  No default template
    arguments, explicit template arguments or parameter packs.
  * The partial ordering compares the patterns of class template
    specializations, as [temp.class.order] rewrites them.  Function
    templates are not ordered, and overload resolution (example 21) does
    not consult deduction.

Overload resolution over a model of C++ types

Directory examples/21-cxx-types-overloads.

The conversions of the standard are non-deterministic rules, a candidate with an argument that no rule converts is not viable, and a set function collects the viable set with its ranks. The inverse question finds every argument type up to a depth that makes a call ambiguous. Python builds the overload sets, the class hierarchy and the calls.

cd examples/21-cxx-types-overloads
./run

Overload resolution over a model of C++ types
=============================================

This example is the second of a series of four.  The series models the
compile-time algorithms of a C++ compiler in Curry: template argument
deduction (20), overload resolution (this example), trait checking (22), and
member layout (23).  All four work on one algebraic model of C++ types, the
shared modules under ../cxx.  CxxType.curry holds the type algebra, the
traits, a printer and a bounded generator; CxxLimits.curry holds the
fundamental types and the tables of the LP64 data model.  This example
adds CxxOverload.curry: the standard conversion sequences, the viable
candidates of a call, and the best viable function.

Overload resolution is a search.  A candidate function is viable when every
argument converts to its parameter.  Each conversion has a rank: exact
match, promotion or conversion.  The best viable function is the candidate
that is not worse than any other in any argument and better in at least one.
In Curry the conversions are non-deterministic rules, the choice of a
candidate is a choice, and a set function collects the viable set.

The motivation is a future integration with the Circle C++ compiler.  Circle
can run Python during compilation, inside its metaprogramming features.  A
Python program there sees the types of the program under compilation.  With
Sprite in that Python, a metaprogram could ask the questions of this series:
which specialization is chosen, which overload wins, which types satisfy a
constraint, and the inverse questions that a compiler never answers, such as
which argument types make a call ambiguous.  Sprite would supply the search
and the unification; Circle would supply the types.  No such integration
exists yet.  The value today is as an analysis, testing and metaprogramming
tool.

The model is a simplification of overload resolution in C++: it has no
user-defined conversions, no templates, no argument-dependent lookup, and
references and value categories only in the simple cases.  Section 5 lists
what it leaves out.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Conversions are rules, and the rules are alternatives.  The function
standard of CxxOverload has one rule per conversion of the standard:

    standard _ a p | a == p = Exact
    standard _ a p | a /= p && qualifies a p = Exact
    standard _ a p | promotes a p = Promotion
    ...

In Curry, two rules with the same left-hand side are alternatives, not a
fall-through chain.  Each rule has a guard that names its case: the
identity, a qualification conversion, a promotion, an arithmetic conversion,
a pointer conversion, a derived-to-base conversion, a null pointer
conversion, a boolean conversion.  The guards do not overlap, so a pair of
types has at most one sequence.  A pair that no guard accepts has no value
at all.  There is no Maybe, no error code and no "else" branch.

Failure makes a candidate not viable.  The function viable picks a
candidate with anyOf and converts every argument:

    viable h cands args
      | length params == length args = (cand, zipWith (convert h) args params)
      where cand = anyOf cands
            params = snd cand

When one argument has no conversion, the value of viable for that candidate
fails.  Nothing else happens: the candidate is gone from the search.  The
set function set3 viable collects the values that remain.  That set is the
viable set of the call, each candidate with the rank of each argument.  An
empty set is the case "no viable function".

Ranks are compared, and sequences of the same rank are ordered by the rules
of the standard.  The function better compares two sequences for the same
argument.  A better rank wins.  For two sequences of the same rank the
tie-breakers of [over.ics.rank] apply: a conversion of a pointer that does
not go to bool beats one that does, Derived* to Base* beats Derived* to
void*, and a sequence without a qualification conversion beats the same
sequence with one.  The second overload set of scenario (c) shows the three
rules.  The call k(Derived*) has three viable candidates of rank conversion,
and k(Base*) wins.  The call k(int*) has two exact matches, and k(int*)
beats k(int const*).

The inverse question.  Scenario (d) asks which argument types make a call
ambiguous.  Overload resolution is a function from a call to a result, and
a function does not run backwards.  A free variable and a bounded generator
turn it round:

    ambiguousArg n cands
      | t =:= anyType n && (ambiguousCall cands $## t) = t
      where t free

anyType n is every type of depth at most n, one per value.  The first
equation binds the unknown t to one of them.  The second equation is the
question.  Each solution is one value, and a set function collects them.
The operator $## evaluates the type to normal form before the question sees
it.  The question runs a set function, and the set function would give the
right answer for the variable t as well; the normal form saves the work
that the variable costs.  Section 5 says how much.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds two directories to curry.path: its own, for
Overloads.curry, and ../cxx, for the shared modules.  It imports CxxLimits,
CxxType and Overloads from curry.lib.

Python builds the data.  A type is built with the constructors of
CxxType.Type, for example curry.expr(CxxType.Ptr, INT) for int*, where INT
is curry.expr(CxxType.Fund, CxxLimits.Int).  An overload set is a Python
list of tuples (name, [parameter types]), and a class hierarchy is a list
of tuples (derived, base).  curry.eval turns a Python tuple into a Curry
tuple and a Python list into a Curry list, so the Curry goals receive
values of the types [Candidate] and Hierarchy with no conversion code.  A
name is a Python str, which curry.expr converts by the type the goal
expects, a String, also for a name of one character such as "f".  Python
can make a free variable: curry.free() in a goal is one variable (Y1), and
the typed builder (#56) will give it its type.  This driver keeps its free
variables in Overloads.curry by choice, and Python passes concrete types.

Every goal returns a String, and the driver reads it with

    next(curry.eval(goal, *args, converter='topython'))

The converter turns the Curry String into a str.  The driver prints the
calls and the overload sets through the Curry printer,
curry.eval(CxxType.showCxx, t), so that Python holds no knowledge of C++
syntax.  The whole driver builds the data, calls the goals and prints.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The first run also compiles the three shared modules and Overloads.curry.
The build products go to .curry/ next to each source.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  For each call the
driver prints the viable candidates with the rank of each argument, then
the result of overload resolution.  Scenario (a) shows the three ranks:

    (a) overloads f(int), f(long), f(double)
      f(int)    viable: f(int) [exact], f(long) [conversion], f(double) [conversion]
                result: f(int) [exact]
      f(char)   viable: f(int) [promotion], f(long) [conversion], f(double) [conversion]
                result: f(int) [promotion]
      f(float)  viable: f(int) [conversion], f(long) [conversion], f(double) [promotion]
                result: f(double) [promotion]

char and bool promote to int, and float promotes to double.  The call
f(int*) has no viable function: a pointer converts to bool, but no
candidate takes bool.

Scenario (b) is the classic ambiguity.  With f(long) and f(double), the
call f(int) has two conversions of the same rank:

      f(int)    viable: f(long) [conversion], f(double) [conversion]
                result: ambiguous: f(long), f(double)

Scenario (c) works with pointers and the class Derived derived from Base.
The call g(Derived*) picks the exact match g(Derived*).  The call
g(std::nullptr_t) is ambiguous: a null pointer converts to every pointer
type with the same rank.  The call g(Derived const*) has no viable
function: a qualification conversion adds const, and never removes it.  The
second set shows the tie-breakers among sequences of the same rank:

      k(Derived*)        viable: k(void*) [conversion], k(Base*) [conversion], k(bool) [conversion]
                         result: k(Base*) [conversion]
      k(int*)            viable: k(int*) [exact], k(int const*) [exact], k(void*) [conversion], k(bool) [conversion]
                         result: k(int*) [exact]
      k(std::nullptr_t)  viable: k(int*) [conversion], k(int const*) [conversion], k(void*) [conversion], k(Base*) [conversion]
                         result: ambiguous: k(int*), k(int const*), k(void*), k(Base*)

The null pointer converts to every pointer with the same rank, and not to
bool: std::nullptr_t converts to bool in a direct-initialization only, and
the initialization of a parameter is not one.  The third set binds a
reference to const of array type:

      h(int[3])        viable: h(int const (&)[3]) [exact], h(int*) [exact]
                       result: ambiguous: h(int const (&)[3]), h(int*)
      h(int const[3])  viable: h(int const (&)[3]) [exact]
                       result: h(int const (&)[3]) [exact]
      h(int[4])        viable: h(int*) [exact]
                       result: h(int*) [exact]

The reference binds the array lvalue directly, with no array-to-pointer
conversion.  So the call with int[3] has two exact matches and is
ambiguous, as in C++.  A const array binds, and int const* does not convert
to int*.  An array of another bound does not bind at all.

Scenario (d) prints one line:

      120 types; after the lvalue transformations, 12: bool, char, signed char, unsigned char, short, unsigned short, int, unsigned int, unsigned long, long long, unsigned long long, long double

Of the 1245 types of depth at most 2, 120 make the call ambiguous for
f(long), f(double), f(int const*).  Every one of them is a cv-qualified or
reference form of one of 12 arithmetic prvalue types: the integer types
that promote to int or that are neither long nor double, and long double.
No pointer, array, function or class type is in the list: a pointer
converts to int const* at most, and that candidate is then the only viable
one.


5. Limits
---------

A warm run of ./run took 1.0 s.  The first run also compiles the modules:
about a second more for CxxOverload.curry and Overloads.curry, and about
2 s more for the two shared modules of example 20 when they are not
compiled yet.  Scenario (d) once stopped with "Evaluation Suspended" on the
reference backend of the developer notes: the step of $## checked its
residuals before the normalization and walked the generators of the
narrowed type, where the fresh variables of the branches the alternative
had not taken never get a value.  The step checks the normal form now, as
the C++ runtime does.

Scenario (d) evaluates the type to normal form with $## before the question
sees it, for speed.  The set function gives the same answer for the
variable t: the choices that bound t escape the set function, one per
alternative.  But a narrowed variable costs.  Every choice of the generator
of t, and of the generators of its parts, escapes the capsule when the
question needs it, and each escape splits the capsule and restarts the
computation around it, in every candidate.  Measured: the question for
one type, int*, takes 1472 rewrite steps and 81 forks through the normal
form and 91618 steps and 14825 forks through the variable; scenario (d) at
depth 1 takes 0.08 s (425 thousand steps) through the normal form and 22 s
(118 million steps) through the variable, and at depth 2 0.24 s against
94 s.

The generator grows by a factor of six per level of depth.  Depth 2 has
1245 types, and scenario (d) over them took 0.3 s; depth 3 has 7330 types.

A measurement of this example against other implementations belongs in
the benchmark harness, not here.  The applications suite of the harness
(tests/README, section 9) resolves a thousand distinct calls with
Overloads.resultLine against a plain-Python implementation of the same
ranking.  The benchmark record of this example is
tests/data/curry/benchmarks/results/apps-2026-10-06-applications.jsonl.

The model leaves out:

  * User-defined conversions: constructors and conversion functions, and
    so the second standard conversion sequence and the ranking of
    user-defined conversion sequences.
  * References and value categories beyond the simple cases.  An argument
    type written as a reference is an lvalue or an xvalue, and the
    lvalue-to-rvalue conversion turns it into a prvalue.  A parameter
    T const& binds the converted argument with the rank of the conversion,
    unless T is an array or a function type: then the reference binds an
    argument of that type directly, and nothing else.  A reference to a
    function type binds the same way.  A parameter T& or T&& has no rule,
    so a candidate with one is never viable.  The reference binding rules
    of [over.ics.ref] and their tie-breakers are not modelled.
  * Templates: deduction of a candidate's parameters, the preference for a
    non-template, and partial ordering.  Example 20 has the deduction.
  * Argument-dependent lookup, member functions and the implied object
    parameter, default arguments and ellipses.
  * Pointer-to-member conversions, except the null pointer conversion to a
    pointer to member, and the conversions of enumerations.
  * Null pointer constants other than std::nullptr_t: the literal 0 is not
    a type.  std::nullptr_t converts to every pointer and pointer to
    member, and not to bool, as in a call.

Two sequences of the same rank from an arithmetic argument are never
ordered, as in C++: f(long) and f(bool) are ambiguous for an int argument.

Trait checking by narrowing over a model of C++ types

Directory examples/22-cxx-types-trait-check.

A bounded generator enumerates every well-formed type of the model up to a depth, one per value, and narrowing with =:= binds an unknown type to each. A set function collects the types for which a property of a trait is False, so an empty set is the verdict that the property holds. One trait is wrong on purpose, and the search finds every counterexample.

cd examples/22-cxx-types-trait-check
./run

Trait checking by narrowing over a model of C++ types
=====================================================

This example is the third of the series that opens with
20-cxx-types-deduction.  It checks the type traits of the shared library
CxxType, under ../cxx, against definitions of the C++ standard.  A Curry
generator enumerates every type of the model up to a depth.  A property is a
Curry function from a type to Bool.  For each property, a search collects
the types for which the property is False.  One trait is wrong on purpose,
so that the output shows what a found counterexample looks like.

The check is a bounded model check.  It covers the types up to the depth
and the shapes that the generator builds, and nothing beyond them.  Section
5 lists what it does not cover.

The motivation of the series, an integration with the Circle C++ compiler,
is explained in the README of example 20.  The model is a simplification of
the C++ type system: it has no enumerations, unions, wide character types,
qualified or noexcept functions, and no non-type template parameters.


1. What the example shows about functional logic programming
-------------------------------------------------------------

A generator is a non-deterministic function.  The shared module
CxxType.curry defines

    anyType n = cvType True n ? refType n ? funType n

The value of anyType n is any one type of depth at most n.  The depth of a
type is the number of constructors on its longest path: int has depth 0,
int const has depth 1, and int const* has depth 2.  Depth 0 holds the 17
fundamental types and one class, Foo.  Each further level adds one type
constructor to a type of the level before.  There are 18 types of depth at
most 0, 194 of depth at most 1, and 1245 of depth at most 2.

Categories exclude the ill-formed types.  The generator has one function
per category of types, and each compound takes its operand from the
categories that C++ allows there.  A pointer points to anything but a
reference; a reference refers to anything but a reference or cv void; an
array holds object types other than cv void; a function returns anything
but an array or a function.  For example

    refType n = if n < 1 then failed else LRef r ? RRef r
      where r = memberType (n - 1)

So a reference to a reference, a cv-qualified reference, an array of
functions, or a function that returns an array is never a value of the
generator.  The categories also keep the terms in normal form: const stays
outside volatile, no qualifier repeats, and the qualifiers of an array go
on its elements.  Every C++ type of the model appears exactly once, which
makes the counts above exact.  The generator calls no trait, and the traits
are what the check examines.

The search is narrowing.  A counterexample of a property is

    counterexample n name | t =:= anyType n && not (p t) = (depth t, showCxx t)
      where (_, p) = property name
            t free

The free variable t is the unknown type.  The constraint t =:= anyType n
binds it to one value of the generator in each branch of the search.  The
property p then runs on a bound type.  A branch where the property holds
fails, and a branch where it is False yields the type with its depth and
its text in C++ syntax.

A set function turns the search into data.  The expression

    sortValues (set2 counterexample n name)

is the sorted list of every counterexample, by depth and then by name, so
the report prints the simplest ones.  An empty list is the verdict that
the property holds.  The number of types is the number of values of the
generator, counted by a set function as well:

    countTypes n = foldValues (+) 0 (mapValues (\_ -> 1) (set1 anyType n))

The properties put a definition of the standard beside a trait of the
library.  For example, [basic.types.general] defines a scalar type as an
arithmetic type, an enumeration, a pointer, a pointer to member, or
std::nullptr_t, with or without cv-qualifiers.  The property is

    propScalar t = is_scalar t == scalarByDefinition t

where scalarByDefinition spells the list out in the primary traits.  The
other properties are the definitions of the fundamental and the object
types, the rule that exactly one primary type category holds for a type
and the same one for its cv-qualified forms ([meta.unary.cat]), the
idempotence of decay, and the identity remove_cvref (add_lvalue_reference t)
== remove_cv t for object types.  The last property checks is_scalar_wrong,
a copy of is_scalar that forgets the pointers to members.  It lives in
CxxCheck, not in the library.  The search finds every pointer to member of
the model as a counterexample.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The example has no Curry module of its own.  The driver go.py adds ../cxx
to curry.path and imports CxxCheck from curry.lib.  CxxCheck imports
CxxType and CxxLimits, which the first run compiles as well.

Python passes a depth and the names of the properties, and prints what
comes back:

    print(text(CxxCheck.header, depth))
    for name in names:
      print(text(CxxCheck.check, depth, name))

A name is a Python str, which curry.expr converts by the type of the
parameter, a String, also for a name of one character.  The helper text
reads the one value of a goal with converter='topython', which turns a
Curry String into a str.  The whole report, the names, the statements and
the counts, is composed in Curry.  Python holds the list of names and the
loop.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The first run also compiles the shared modules and CxxCheck.curry.  The
build products go to .curry/ next to the sources, under ../cxx.

To check another depth or a subset of the properties, pass them to go.py.
Use the Python of the staged install.  For example, on the C++ backend:

    SPRITE_INTERPRETER_FLAGS=backend:cxx ../../install/bin/python go.py 1 scalar wrong_scalar

The names are those of the table properties in CxxCheck.curry: scalar,
fundamental, object, category, decay_twice, cvref and wrong_scalar.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  The first line
gives the size of the check:

    Every type of depth at most 2: 1245 types.

Each property then takes two lines: its name and statement, and the
verdict.  Six properties hold:

    scalar: is_scalar t == is_arithmetic t || is_pointer t || is_member_pointer t || is_null_pointer t
      no counterexample among 1245 types

The last property fails:

    wrong_scalar: is_scalar_wrong t == ..., where is_scalar_wrong forgets the pointers to members
      191 counterexamples, the 5 simplest: Foo Foo::*, bool Foo::*, char Foo::*, double Foo::*, float Foo::*

The counterexamples are the pointers to members of depth at most 2.  The
five shown are pointers to data members of depth 1, in the order of their
names.  The type Foo Foo::* is a pointer to a member of type Foo in the
class Foo.  No class can have such a member, but the type exists, and the
generator does not know classes from the inside.


5. Limits
---------

A warm run of ./run took 2.3 s on the C++ backend.  A cold run, which
also compiles CxxCheck.curry, took 4.3 s.  The first run compiles the two
shared modules as well, when they are not compiled yet.  The time goes to
the traits: each one normalizes its argument, and a property calls up to 33
of them for each of the 1245 types.  The generator itself is cheap.  It
took 0.01 s to count the types of depth at most 2.

Depth 3 has 7330 types.  On the C++ backend the count took 0.06 s, and the
properties scalar and wrong_scalar together took 3.9 s at that depth, with
1258 counterexamples for the wrong trait.  The cost of a search grows
faster than the number of its values, so keep depth 3 for one property at
a time.

Bind the generator to a free variable before a property reads it.  An
earlier version shared the expression anyType n between the guard and the
result instead.  On the C++ backend, with a generator of 2230 types, the
property scalar took three times longer that way, and the property
decay_twice ran out of a 2 GB address space.  With the constraint
t =:= anyType n the choice is made once, when t is bound.

What the check does not cover:

  * Types of depth 3 or more.  int const* const&, for example, has depth 4.
  * The shapes outside the generator: the arrays have the bound 3 only, the
    functions take one of three parameter lists, there is one class, and
    there are no class templates, enumerations, unions, or wide character
    types.  Member pointers point into the one class.
  * The traits that no property uses: make_signed, make_unsigned, the
    promotions, common_type, sizeof_ and alignof_, and the tables of
    CxxLimits.
  * A property that has no value for a type.  When a trait in a property
    fails, the type is neither a pass nor a counterexample, and the report
    does not notice.  The traits that the seven properties call are total:
    at depth 2, every property has a value for every type, which a version
    of the driver that collected every outcome confirmed.  That version
    cost 0.5 s more per property on the C++ backend, so the example does
    without it.  A property over a partial trait, such as make_signed,
    needs it.
  * A mistake that both sides of a property share.  Every trait normalizes
    its argument with the same function norm, so a wrong normal form could
    satisfy every property.  The generator is independent of norm, which is
    why the count of types is a check of its own.
  * The meaning of the traits in a real compiler.  The properties compare
    the model with the text of the standard, not with the output of a C++
    compiler.

Member layout by search over a model of C++ types

Directory examples/23-cxx-types-layout.

A non-deterministic permutation yields every order of the members of a struct, a set function collects the size of each order, and a constraint on the order is one more guard. Python describes the struct through the annotations of a class, as a reflection would, and prints the layout tables.

cd examples/23-cxx-types-layout
./run

Member layout by search over a model of C++ types
=================================================

This example lays out a struct and searches for the member order of the
smallest size.  It closes the series of four that opens with
20-cxx-types-deduction.  The README of that example describes the shared
model under ../cxx and the motivation, a future integration with the Circle
C++ compiler.  Python describes the struct, as a reflection would, and Curry
lays it out and searches.

The layout follows the Itanium C++ ABI for a standard-layout struct without
bit-fields, base classes or virtual members.  Each member goes to the next
offset that is a multiple of its alignment.  The alignment of the struct is
the largest alignment of a member.  The size is the end of the last member
rounded up to that alignment.  The sizes and alignments come from the LP64
data model of CxxLimits.  The model is a simplification of the C++ type
system: it has no bit-fields, no bases, no virtual members, no nested class
members, no alignas and no packing pragmas.

The module CxxLayout.curry under ../cxx holds the layout and the search.
This directory holds the driver only.


1. What the example shows about functional logic programming
-------------------------------------------------------------

Non-determinism as values.  The function perm builds one order of the
members with insert.  Both rules of insert apply to a non-empty list, so each
call is a choice.  An expression over perm means every order at once:

    sizeOfOrder ss = (structSize (layoutSized order), order)
      where order = perm ss

One value of sizeOfOrder is the size of one order, paired with that order.
The function has 720 values for six members.

Set functions.  The set function set1 sizeOfOrder is the set of every such
pair.  The search sorts the set by size, counts the run of the smallest size,
and takes the first order of that run in the order of the member names:

    bySize = sortValuesBy (\p q -> fst p <= fst q) pairs
    best   = [order | (size, order) <- bySize, size == fst (head bySize)]
    result = (length bySize, length best, layoutSized (minimum best))

The sort compares sizes only.  The scheduler does not promise an order of the
values, so minimum picks the order to print.  The names are unique, and
minimum compares them first.

Constraints as rules.  Scenario (c) keeps the member tag first.  The search
is the same with one more rule, a guard on the generated order:

    sizeOfOrderFirst first ss | nameOf (head order) == first = (size, order)
      where (size, order) = sizeOfOrder ss

An order with another member in front fails.  A failure is not a value, so
the set function does not see it, and the set shrinks from 720 values to
120.  The guard needs only the head of the order.  Laziness builds the head
first, so an order that breaks the rule fails before the rest of it is built.

In this struct the pin costs no bytes.  The members urgent, port and length
fill the eight bytes behind tag, and both searches reach 24 bytes.  The pin
costs orders: 2 of 120 reach 24 bytes, against 48 of 720.


2. What the example shows about calling Curry from Python
----------------------------------------------------------

The driver go.py adds ../cxx to curry.path and imports CxxLimits, CxxType and
CxxLayout from curry.lib.  The struct is a Python class whose annotations are
its members:

    class Packet:
      tag: CHAR
      stamp: DOUBLE
      ...

The dictionary Packet.__annotations__ keeps the declaration order.  That is
the reflection of Python, and it stands in for the reflection of a compiler:
Circle would hand over the members of the struct under compilation in the
same shape.  Each type is a Curry expression built with curry.expr from the
constructors of CxxType, for example

    curry.expr(CxxType.Ptr, curry.expr(CxxType.Const, CHAR))

for char const*.  The function members turns the annotations into a Python
list of (name, type) pairs, and curry.eval converts it to a Curry list of
tuples.  A name is a Python str, which curry.expr converts by the type the
tuple expects, a String, also for a name of one character.

A layout comes back as nested tuples and lists.  The call

    curry.eval(CxxLayout.layout, members, converter='topython')

yields a Python tuple of the placed members, each a tuple of name, offset,
size and padding, then the size, the alignment and the padding at the end.
Python prints the table.  The type of each member goes through the Curry
printer, curry.eval(CxxType.showCxx, t), so Python holds no knowledge of C++
syntax.  The layout also goes back to Curry, to CxxLayout.padding, so the
tuple converts both ways.  The converter turns a Curry String into a str
inside a tuple or a list alike, and the empty String into ''.


3. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The first run also compiles CxxLayout.curry, and the two shared modules when
no earlier example of the series has run.  The build products go to .curry/
next to each source.

To lay out another struct, edit the class Packet in go.py.  The member types
may be fundamental types, pointers, references, arrays and pointers to
members.  A member of a class type has no size in the model, so a struct with
one has no layout, and the driver stops with StopIteration.


4. Expected output
------------------

The file expected.out holds the exact output of ./run.  Scenario (a) prints
the struct in declaration order, one row per member and one per hole:

    (a) struct Packet in declaration order
      offset  size  member
           0     1  char         tag
           1     7  (padding)
           8     8  double       stamp
          16     1  bool         urgent
          17     3  (padding)
          20     4  int          length
          24     2  short        port
          26     6  (padding)
          32     8  char const*  payload
      sizeof 40, alignof 8, padding 16

Scenario (b) searches every order:

    (b) the order of the smallest size
      smallest sizeof 24, reached by 48 of 720 orders
      the first of those orders: length, port, tag, urgent, payload, stamp

Scenario (c) searches the orders with tag first:

    (c) the order of the smallest size with tag first
      smallest sizeof 24, reached by 2 of 120 orders
      the first of those orders: tag, urgent, port, length, payload, stamp

The table of the chosen order follows each summary.


5. Limits
---------

A warm run of ./run took 0.6 s.  The first run also compiles
CxxLayout.curry.  It took 2.6 s, with the shared modules compiled by an
earlier example.

The number of orders is the factorial of the number of members.  A seventh
member makes 5040 orders.  The two searches then took 4.4 s and 0.6 s.

The layout is the layout of a standard-layout struct.  A struct with a base
class, a virtual function or a bit-field has another layout, and the model
does not describe it.

A makefile in Curry

Directory examples/24-build-system.

The makefile of a toy C project is a Curry module beside its sources: the variables are definitions with the uppercase names of make, a rule is an equation of the relation rule target inputs = recipe, the pattern rule %.o: %.c is a functional pattern, a condition is an if or a guard, and the header dependencies are the relation depends. The library Make.curry asks the relation with the inputs free and answers the questions of make: what a target reads, what is stale over a table of stamps, the plan in waves, the targets that can run now, the targets a change touches, and three lints, a target with two rules, a source that is missing, and a recipe with two values or none. The driver make.py, generic, substitutes the assignments of its command line into the makefile, reads the variables by introspection, runs the recipes with them in the environment, and asks Curry for the ready set after each completion. Nothing in Python names a file of the project.

cd examples/24-build-system
./run

A makefile in Curry
===================

A Curry script is to make as bash is to the file system.  Make reads a
makefile, decides what to build, and runs the commands.  Here the makefile
is a Curry module beside the sources of a toy C project,
project/Makefile.curry.  It is written over a small library, Make.curry,
and run by a generic driver, make.py, which knows nothing of the project.
The makefile reads as a makefile.  The variables are definitions with the
names of make.  A rule is an equation of a relation, in make's order:
target, inputs, recipe.  The pattern rule %.o: %.c is a functional pattern.
A condition is an if or a guard, and the command line reaches it.  The
header dependencies are a relation too.  The library asks the relation
with the inputs free, and Curry's narrowing fills them in.  Sprite itself
builds with configure and GNU make.  This example does not replace them.


1. The project
--------------

Five C sources and two headers: main.c, vec.c, shape.c, report.c, and the
optional plot.c, with vec.h and shape.h.  shape.h includes vec.h.  The
static library libgeom.a holds vec.o and shape.o, and plot.o when
WITH_PLOT is set.  The program demo links main.o, report.o and libgeom.a
with $(CC).  Two knobs: DEBUG=1 switches CFLAGS from -O2 -Wall to -O0 -g
-Wall.  WITH_PLOT=1 adds plot.o to the library and -DWITH_PLOT to
CPPFLAGS, and main.c calls plot under #ifdef WITH_PLOT, so the program
prints one line more.  The run script builds the program with cc and runs
it, and its output is part of expected.out.


2. Reading the makefile
-----------------------

This is project/Makefile.curry in full:

    module Makefile where

    CC = "cc"
    AR = "ar"
    DEBUG = "0"
    WITH_PLOT = ""
    CFLAGS = if DEBUG == "1" then "-O0 -g -Wall" else "-O2 -Wall"
    CPPFLAGS = if WITH_PLOT /= "" then "-DWITH_PLOT" else ""

    goal = "demo"

    -- %.o: %.c
    rule (stem ++ ".o") [stem ++ ".c"] = "$(CC) $(CPPFLAGS) $(CFLAGS) -c $< -o $@"
    -- libgeom.a: vec.o shape.o
    rule "libgeom.a" ["vec.o", "shape.o"] = "$(AR) rcs $@ $^"
    -- ifdef WITH_PLOT
    -- libgeom.a: plot.o
    -- endif
    rule "libgeom.a" ["plot.o"] | WITH_PLOT /= "" = ""
    -- demo: main.o report.o libgeom.a
    rule "demo" ["main.o", "report.o", "libgeom.a"] = "$(CC) -o $@ $^"

    depends "main.c"   = "shape.h"
    depends "main.c"   = "vec.h"
    depends "shape.c"  = "shape.h"
    depends "shape.h"  = "vec.h"
    depends "vec.c"    = "vec.h"
    depends "report.c" = "vec.h"
    depends "plot.c"   = "shape.h"

The comment on each rule is the make line it stands for.  The makefile has
no type signatures.  The front end infers them.

The variables.  CC = "cc" is make's CC = cc: a definition with the name of
make.  Curry proper reserves an uppercase name for a constructor, and the
front end of the pinned PAKCS accepts these as definitions.  CFLAGS is
make's ifeq ($(DEBUG),1) block, written as an if.  CPPFLAGS is make's ifdef
WITH_PLOT block.  A variable is a string, and a recipe reads it as
$(NAME), as in make.  The definition goal names the default goal.

The rules.  A rule is an equation of the relation rule.  The target and the
inputs stand in the head and the recipe on the right, in make's order:

    rule "libgeom.a" ["vec.o", "shape.o"] = "$(AR) rcs $@ $^"

The library never calls rule with the inputs in hand.  It asks the relation
with the inputs free,

    candidate rule t = (ins, rule t ins) where ins free

and collects the answers with a set function.  Narrowing fills the inputs
in: the answer for "libgeom.a" is (["vec.o", "shape.o"], "$(AR) rcs $@
$^").  Every equation that matches the target is one answer.  The first
takeaway: a rule is an equation of a relation, so the same text answers
"what does demo need" and "who needs shape.h".  The second question is
the inverse query of the library.  It draws a target from the targets of
the build and keeps it when it reads the file, directly or through another
target.  No second table and no index from files to targets.

The pattern rule.  The first equation is make's %.o: %.c:

    rule (stem ++ ".o") [stem ++ ".c"] = "$(CC) $(CPPFLAGS) $(CFLAGS) -c $< -o $@"

Its head is a functional pattern, and the pattern is non-linear: stem
occurs twice.  For the target "vec.o", the first occurrence binds stem to
"vec", and the second binds the free inputs to ["vec.c"].  The second
takeaway: a functional pattern is solved, not formatted.  Make substitutes
the stem into a template.  Curry solves stem ++ ".o" against "vec.o", and
then [stem ++ ".c"] against the free inputs.  A bare identifier in a
pattern is a variable, so the explicit rules name their targets as string
literals.

The conditional rule.  The equation

    rule "libgeom.a" ["plot.o"] | WITH_PLOT /= "" = ""

is make's ifdef WITH_PLOT block around the line libgeom.a: plot.o.  The guard
reads the variable.  /= is not-equal, so the guard holds when WITH_PLOT is
set.  An empty recipe is a prerequisite line.  When WITH_PLOT is set, both
equations for libgeom.a answer.  The library merges their
inputs, as make merges the prerequisite lines of a target: libgeom.a reads
vec.o shape.o plot.o.  The third takeaway: a condition is an if or a guard,
and the command line reaches it because the driver substitutes the
assignment.  make.py WITH_PLOT=1 replaces the line WITH_PLOT = "" with
WITH_PLOT = "1" and compiles the text.  That is what make does when the
command line overrides a variable.  The file's assignment is replaced, then
the file is read.

The header dependencies.  The relation depends has one equation per edge.
A file with two headers has two equations, main.c here, and the set of
answers is its dependency list.  The transitive closure follows the
headers' own edges: shape.h includes vec.h, so shape.o reads shape.c
shape.h vec.h.  The sources include exactly the headers the edges declare.
Make reads these lines from the .d files of the compiler.

Two traps.  First, every matching equation answers.  A second equation is not
an else.  The two equations for libgeom.a both answer when WITH_PLOT is set,
and that is the merge you want.  Two equations for CFLAGS both answer as well
(step 7 of the output).  A variable with two equations has two values, and
every recipe that reads it has two.  So the else of a condition belongs in
the if, as CFLAGS writes it.  Second, a variable or a target defined twice is
two answers, and the lints say so.  A second rule with a recipe for main.o
(step 6), CFLAGS twice (step 7), and CC = "gcc" ? "clang" (step 8) all stop
the build before the plan.


3. The interpolator
-------------------

The library expands a recipe once per target.  $@ is the target.  $< is
the first input of the rule that has the recipe, or nothing when the rule
has no input, as in make.  $^ is everything the target reads: the merged
inputs of its rules with the headers behind them, as make's $^ with .d
files.  $(NAME) is the value of NAME from the table the driver passes.  Any
other $x stays as written.  $(NAME) is strict: an undefined variable is no
recipe, and the lint names it.  An empty variable leaves its space,
cc  -O2 -Wall, as make leaves it.  The catch-all of the interpolator is a
guard in the same equation.  A second equation that also matched $ would be
a second answer per token.


4. The lints, and what make does instead
----------------------------------------

Three lints run before the plan, and any answer refuses the build.  ambiguous
lists a target with two rules with a recipe.  missing lists a name with no
rule that does not exist.  The recipe lint lists a target whose recipe has
two values, from a variable defined twice, or none, from an undefined
$(NAME).  The driver prints one sentence each and the exit status 2 of make.
GNU make 4.3 does otherwise.  It takes the last explicit recipe with a
warning, "overriding recipe for target", and lets an explicit rule beat a
pattern rule in silence.  It takes the last assignment of a variable in
silence and expands an undefined variable to nothing in silence.  On a
missing source it stops with "No rule to make target 'vec.o', needed by
'libgeom.a'" when the makefile has no prerequisite line for vec.o.  It names
the object, because its pattern rule does not apply without the source.  With
the .d-style line vec.o: vec.h it counts vec.o as made, plans the ar line,
and fails when ar runs.  It drops a circular dependency with a warning and
builds on.


5. What make has that this does not
-----------------------------------

Make's += is ++ in the expression.  Make's ?= and the process environment
have no form here: only the NAME=value arguments of the command line enter
the makefile.  A target-specific variable has no form: a rule writes its
flags in its recipe.  .PHONY, order-only prerequisites, $(wildcard) and VPATH
are facts about the file system, which the driver owns.  The makefile has no
form for them.  A recipe runs as one process without a shell, so a pipe or a
redirection has no form.  One pattern rule serves the objects.  The choice
among several pattern rules by which source exists, make's rule search, is
not modelled.


6. The driver: calling Curry from Python
----------------------------------------

make.py reads

    python make.py [-f FILE] [-C DIR] [-j N] [-n] [--touch FILE]
                   [--affected FILE] [--trace] [GOAL] [NAME=value ...]

as make does:

  * -C DIR names the project directory.
  * -f FILE names the makefile in it, Makefile.curry by default.
  * -n prints the plan and stops.
  * -j N sets how many recipes run at once.
  * GOAL names the target.  The default is the definition goal of the
    makefile.
  * NAME=value replaces the assignment of NAME in the makefile.
  * --touch FILE gives a file a stamp newer than every other file of the
    build before anything else.
  * --affected FILE prints the targets that read the file.
  * --trace prints each ready set to stderr.

A command-line assignment replaces the file's, then the file is compiled.
For every NAME=value, the driver reads the text of the makefile and
replaces the line that starts with NAME and = by NAME = "value".  It drops
any other assignment of NAME, as make's command line overrides every
assignment of the file.  A file without such a line gets it at the end.
Without assignments the driver imports the module from its directory, with
the cached products of the last run.  With assignments it writes the
substituted text under .curry/overrides/HASH beside the makefile, where
HASH names the text, and imports the module from there.  A second run with
the same assignments finds the compiled products of the first and does not
pay the front end again.

The variables are read by introspection.  Every definition of the module
whose name starts with an uppercase letter and whose type is String is a
variable.  dir(module) lists the names, curry.typeof gives the type, and
curry.eval(symbol, converter='topython') gives the values.  Each value is one
row of the table, so a definition with two values gives two rows.  The table
goes to Curry for $(NAME) and into the environment of every recipe the driver
runs.

One build, many questions.  The driver builds the Curry value of the build
once,

    curry.expr(Make.build, module.rule, module.depends, table, goal)

and passes the same node to every question.  A symbol with fewer arguments
than it takes is a partial application in curry.expr: rule and depends go
to Curry as relations.  A makefile without depends gets Make.noDepends.  A
deterministic question has one value, read with

    next(curry.eval(goal, *args, converter='topython'), None)

The plan has no value on a cycle, and the driver reads None then.  The
inverse query has one value per target, and the driver sorts them, because
Curry promises no order.

The build loop asks Curry for the ready set: the stale targets whose inputs
are all up to date.  It submits each new one to a thread pool, waits for the
first completion, and asks again with the new stamps.  The table it hands to
Curry omits the targets whose recipes run or failed, so a half-written object
does not read as up to date.  Each recipe is printed when it starts, as make
prints it.  It runs as one process in the project directory, without a shell,
split into words as a shell would split them.  When a recipe completes, the
loop prints its output, stdout to stdout and stderr to stderr, so the recipes
of one wave do not interleave.  A program that cannot start is a failed
recipe with the status 127.  The exit status is that of make.  It is 2 when
the build does not start, when a recipe fails, or when a target of the plan
never ran, and 0 otherwise.


7. How to run
-------------

Run "make stage" from the root of the repository first.  Then run

    ./run

The script copies the sources of project/ into four temporary directories,
one of them without vec.c, and links the makefiles into each copy.  So Sprite
compiles each makefile once, into project/.curry, and the build leaves
nothing in the repository.  It runs make.py eleven times there and the
program twice.  The example needs cc and ar on the PATH.

To build in project/ itself, run make.py from this directory:

    ../../install/bin/python make.py -C project
    ../../install/bin/python make.py -C project -n
    ../../install/bin/python make.py -C project DEBUG=1 WITH_PLOT=1
    ../../install/bin/python make.py -C project --touch shape.h --affected shape.h

and remove the objects, the library and the program afterwards.


8. Expected output
------------------

The file expected.out holds the exact output of ./run.  Every step prints
its command line first.  Step 1 is the build from scratch: the plan, the
recipes as they run, and the program's output:

    1. the build from scratch
    % python make.py -C project
    plan: 6 targets
      main.o    <- main.c shape.h vec.h       cc  -O2 -Wall -c main.c -o main.o
      report.o  <- report.c vec.h             cc  -O2 -Wall -c report.c -o report.o
      vec.o     <- vec.c vec.h                cc  -O2 -Wall -c vec.c -o vec.o
      shape.o   <- shape.c shape.h vec.h      cc  -O2 -Wall -c shape.c -o shape.o
      libgeom.a <- vec.o shape.o              ar rcs libgeom.a vec.o shape.o
      demo      <- main.o report.o libgeom.a  cc -o demo main.o report.o libgeom.a
    waves: [main.o report.o vec.o shape.o] [libgeom.a] [demo]
    cc  -O2 -Wall -c main.c -o main.o
    ...
    % project/demo
    c = (0, 3)
    area = 6

Each object reads its source and the headers behind it.  The six recipes
are the six lines that GNU make 4.3 prints for the same project with
make -rn.  Step 2 builds again, and the plan is "nothing to do".  Step 3
touches shape.h, asks the inverse query, and rebuilds the four targets it
names:

    3. touch shape.h: the inverse query, then the rebuild
    % python make.py -C project --touch shape.h --affected shape.h
    affected: demo libgeom.a main.o shape.o
    plan: 4 targets
    ...

Step 4 plans a fresh copy with DEBUG=1, and every object's recipe reads
-O0 -g -Wall.  Step 5 builds a fresh copy with WITH_PLOT=1: seven
targets, -DWITH_PLOT in every compile, plot.o in the library, and the
program prints a third line:

    5. WITH_PLOT=1: plot.o joins the library, the define, one line more
    % python make.py -C plot WITH_PLOT=1
    plan: 7 targets
      main.o    <- main.c shape.h vec.h       cc -DWITH_PLOT -O2 -Wall -c main.c -o main.o
    ...
      plot.o    <- plot.c shape.h vec.h       cc -DWITH_PLOT -O2 -Wall -c plot.c -o plot.o
      libgeom.a <- vec.o shape.o plot.o       ar rcs libgeom.a vec.o shape.o plot.o
    ...
    % plot/demo
    c = (0, 3)
    area = 6
    plot: (0,0) (4,0) (0,3)

Steps 6 to 8 are the lints.  Each variant makefile is a copy of the
makefile with one change.  Makefile_ambiguous.curry adds a second rule
with a recipe for main.o:

    6. a second rule with a recipe for main.o: the ambiguity lint
    % python make.py -C project -f Makefile_ambiguous.curry
    ambiguous: main.o has 2 rules
      main.o <- main.c  $(CC) $(CPPFLAGS) $(CFLAGS) -c $< -o $@
      main.o <- main.c  $(CC) -O3 -c $< -o $@
    refused: the build does not start
    exit status 2

Makefile_twice.curry defines CFLAGS twice, and every recipe that reads it
has two values:

    7. CFLAGS defined twice: two values, two recipes, the recipe lint
    % python make.py -C project -f Makefile_twice.curry
    main.o has 2 recipes
    report.o has 2 recipes
    vec.o has 2 recipes
    shape.o has 2 recipes
    refused: the build does not start
    exit status 2

The lint prints one line per target: the recipes themselves when they fit
in 79 columns, else their count, as here.

Makefile_toolchain.curry writes CC = "gcc" ? "clang".  The choice is two
answers, so the same lint refuses, and the command line decides:

    8. the compiler as a choice, CC = "gcc" ? "clang": two answers, and the command line decides
    % python make.py -C project -f Makefile_toolchain.curry -n
    main.o has 2 recipes
    ...
    demo has 2 recipes
    refused: the build does not start
    exit status 2
    % python make.py -C fresh -f Makefile_toolchain.curry CC=clang -n
    plan: 6 targets
      main.o    <- main.c shape.h vec.h       clang  -O2 -Wall -c main.c -o main.o
    ...

Step 9 plans Makefile_cycle.curry in a fresh copy, where every target of the
cycle is stale.  Its extra rule has the program write the header its own
objects read.  The plan has no value, and the driver says so.  Step 10 builds
the copy without vec.c, and the build stops before the plan:

    10. a source that is missing: no rule to make it
    % python make.py -C incomplete
    no rule to make vec.c, needed by vec.o
    refused: the build does not start
    exit status 2


9. Limits
---------

Warm runs of ./run took 4.8 s and 6.9 s.  A first run took 10.3 s.  It
also converts the library, the five
makefiles and the three substituted copies to ICurry.  The run starts eleven
make.py processes.

The library reads the rules of a target through a set function, whose values
are plain data, and every later question compares plain strings.  That is the
idiom for a functional pattern's result in Sprite today.  A name that a
functional pattern produced carries its narrowing into every later comparison
(#86).  A set function applied to such a name exhausted memory on the C++
backend before the fix of #97.  The pattern rule binds the free inputs of the
relation (#98).

A stamp is an integer that Python computes, here the modification time in
nanoseconds.  A target with the same stamp as an input is up to date, as
in make.  --touch waits until the file is newer than every other file of
the build.  The plan sees a cycle when a target of the cycle is stale.  A
cycle among targets that are up to date is nothing to do.  The project is
a toy by design.  A real project would read its header edges from the
dependency output of the compiler and would need the features that
section 5 lists.  The relations do not change.  Only the equations grow.