Daki Language Specification

Daki is a small computer programming language inspired by Prolog and Datalog. It is a declarative, logic, typed language based on Horn clauses, aimed at solving problems via deduction.

To execute a Daki program you must use a Daki language interpreter. You can find on GitHub the reference interpreter (mirror).

Regardless of your familiarity with Prolog or Datalog, the Daki language has significant differences to both. For this reason the following short language definition has been compiled, with examples.

Contents

Introduction

The Daki language is meant to be read by a computer. The usual flow of a Daki language computer program is to read a collection of declarations, and then allow the user to interact with the knowledge base and make questions to be solved via inference.

One interesting quality about Daki is that it is meant to bridge the capabilities of Datalog with some of the more powerful features of Prolog. In Datalog queries return all solutions, while in Prolog by default only the first solution is returned. In Daki you can always easily select between the two query methods, and still have access to powerful features missing from Datalog, like a typed system and automatic memoization. There are many other differences from these languages to Daki; these are introduced where appropriate along this text.

There are only five types of instructions in Daki, and these cannot be mixed (except for comments that may be inlined):

  1. Comments
  2. New declarations
  3. Queries
  4. Declarations to be removed
  5. Built-in commands

Comments

Technically not an instruction, because they are not interpreted; comments start with the "#" character, and everything after this character is ignored by the interpreter.

    > # I am a comment
    >
    > fact('john', 'mary', 1). # I'm a comment too

Declarations

New declarations add what is called a clause to the global table of clauses (sometimes called database or knowledge base in other logic languages). A clause is composed of a head declaration and an optional tail, separated by the characters ":-".

    > parent('john', 'emily').
    > grandparent(A, B) :- parent(A, C), parent(C, B).

Clauses are always terminated by a dot, ".". If they are declared with a tail, the tail must be evaluated true for the head to match. Clauses with a tail are called rules, while clauses without it are called facts.

In Daki, the tail dependencies order is not important. In accordance with other logic languages, the "," character is used to denote logical AND, and the ";" character logical OR. Notice how these are equivalent in Daki:

    > rule(x) :- reason1(x); reason2(x).
    > # is for all purposes the same as
    > rule(x) :- reason1(x).
    > rule(x) :- reason2(x).

In Daki, all clauses have their tail dependencies resolved into clauses with only logical AND relationships, and it is in this format they are stored internally. For example:

    > d(X, Y, X) :- (e(X); e(Y); e(Z)), (f(X); f(Y); f(Z)).
    > listing
    0: d(X, Y, X) :- e(X), f(X).
    1: d(X, Y, X) :- e(X), f(Y).
    2: d(X, Y, X) :- e(X), f(Z).
    3: d(X, Y, X) :- e(Y), f(X).
    4: d(X, Y, X) :- e(Y), f(Y).
    5: d(X, Y, X) :- e(Y), f(Z).
    6: d(X, Y, X) :- e(Z), f(X).
    7: d(X, Y, X) :- e(Z), f(Y).
    8: d(X, Y, X) :- e(Z), f(Z).

Notice how you can use parenthesis to declare many logical AND relationships at once.

The elements of clauses always have open brackets and are declared with one or more strings. Those strings can be literals - with a specific data type - or variables.

Data types

Literals in Daki always have an implicit data type associated. Many operations are only possible between compatible data type literals: this will be expanded on later in this document.

The Daki data types are string, for Unicode strings (for example 'daki'), integer, for arbitrary size integers (42), float, for IEEE 754 floating point numbers (3.14) and list, for sequential lists of literal values of arbitrary length and depth (['john', 24, ['skiing', 'running']]). This document also uses the term numeric to mean both integer and floating point values.

Literal values are not automatically coerced or matched, for example:

    > value('1', 1).
    > value(1, 2).
    > value(1.0, 3).
    > value([1], 4).
    >
    > value('1', X)?
    X = 1

    > value(1, X)? # integer  value 1 did not unify with floating point 1.0
    X = 2

    > value(1.000, X)? # integer  value 1 did not unify with floating point 1.0
    X = 3

    > value([1], X)?
    X = 4

Integer literals can be specified in decimal, octal, hexadecimal or binary notation:

    > value(119).       # decimal
    > value(0170).      # octal
    > value(0x7a).      # hexadecimal
    > value(0b1111011). # binary
    > listing
    0: value(119).
    1: value(120).
    2: value(122).
    3: value(123).

String literals are UTF-8 encoded Unicode strings that can be enclosed both by the characters "'" and """, and both of these can be escaped with "\". The character "\" itself is escaped with "\\". You can write ""'"" and "'"'", but need to escape it if the character is used for delimiting the string: ""\""" and "'\''". The characters for line feed ("\n"), carriage return ("\r") and horizontal tab ("\t") also need to be escaped.

The character "\" is also used to denote line continuation: when placed at the end of a line, it is discarded and the line is joint with the line bellow. Line continuation works inside long strings as well. Commented text is only filtered to the end of the text line (the continuation character). See for example the following valid piece of code:

    > mammal(A) :- # a simplified definition \
    >   blood(A, 'warm'), \
    >   (hasHair(A); hashFur(A)), \
    >   # laysEggs(A), Not all of us lay legs! \
    >   producesMilk(A).

You can also specify ASCII characters in hexadecimal in "\xFF" notation and Unicode in "\uFFFF" notation. For Unicode code unit escaping, you can use "\u{FFFFF}" with an arbitrary number of hexadecimal algarisms. The "\x" and "\u" parts are case-sensitive.

Variable names and clause names must start with a letter and be composed of letters, algarisms and underscores.

All whitespace outside of string literals is ignored. This is perfectly legal:

    >        hello  (  World   ,   [ [ [ ' '] ] ])          .   #
    > listing
    0: hello(World, [[[' ']]]).

Queries

A query has a similar format to a tailless clause, but ends with a "?" character instead of ".". Upon being input, it starts a search for all its solutions using the global table of clauses.

The search will try to find all solutions for which the original query has no outstanding variables, showing the literals that have filled in those variables. When all variables of a clause head are replaced, we say it has unified.

If the original query has no outstanding variables, the query is instead about verifying if that combination of literal values as arguments for the clause unify.

The interpreter will print the values of the variable arguments of every solution found, or return "Yes" if a solution exists but the query had no variable arguments, or return "No" if no solution was found.

    > parent("john", "anna").
    > parent("john", "mary").
    > parent("victor", "john").
    > parent("sophia", "john").
    > parent("victor", "victor jr").
    > parent("sophia", "victor jr").
    > grandparent(X, Y) :- parent(X, Z), parent(Z, Y).
    >
    > grandparent(A, B)?
    A = 'victor'
    B = 'anna'

    A = 'sophia'
    B = 'anna'

    A = 'victor'
    B = 'mary'

    A = 'sophia'
    B = 'mary'

    > grandparent('sophia', 'mary')?
    Yes

    > grandparent(A, A)?
    No

The interpreter will print a warning when a query is impossible to unify when no clauses with the same name and arity were declared.

Short queries

The previous queries that return all the solutions are called full queries. If the clause ends with a "!" instead of "?", a short query is performed instead. A short query terminates as soon as the first solution is found. They only return one answer, or "Yes" and "No":

    > month('January').
    > month('February').
    > month('March').
    > month(name)!
    month = 'January'

Queries have a time limit to be completed. If a query times out the interpreter prints the message "Search timeout". A full query can timeout even after finding at least part of the solution. The default time limit is interpreter or system specific.

Previously we said the order of tail clauses is not important, which is true for full queries. With short queries, the first solution found may be different depending on the order of the tail clauses. The interpreter algorithm, however, is stable: given the same definitions the result will be constant (if not introduced by built-in clauses with side effects).

Anonymous arguments

Sometimes we only want to know if a solution exists, or are only interested in part of the solution. Daki allows the use of anonymous arguments in queries, that unify with any value, for this purpose. They are particularly useful when a query would result in an enormous amount of output solutions.

Without anonymous arguments, boilerplate clauses would have to be used instead, that just transform a short query into a long query with discarded arguments. Remember that Daki does not require all arguments in the tail dependencies to unify, contrary to Datalog.

    > food('fruit', 'apple', 120).
    > food('fruit', 'banana', 90).
    >
    > # With boilerplate clauses
    > food(A, B) :- food(A, B, C).
    > food(A) :- food(A, B).
    >
    > food('fruit', 'apple')?
    Yes

    > food('fruit', Name)?
    Name = 'apple'

    Name = 'banana'

    >
    > # With anonymous arguments
    > food('fruit', 'apple', _)?
    Yes

    > food('fruit', Name, _)?
    Name = 'apple'

    Name = 'banana'

    >
    > # Impossible without anonymous arguments
    > food(_, _, _)?
    Yes

Retractions

You can remove a declaraction from the global table of clauses by declaring it again, with a final "~" instead of ".". The clause must be equivalent, that is, have all the same facts in the same argument order, except for the variables that may use different names.

If you declare the same rule twice, executing "listing" will show the number of declarations next to the rule, in parenthesis:

    > dinner(X) :- meal(X), time_of_day(18, 23).
    > dinner(X) :- meal(X), time_of_day(18, 23).
    > listing
    0: dinner(X) :- meal(X), time_of_day(18, 23). (2)

Conversely, to completely retract a rule you must retract it as many times as it is declared.

If you declare a rule that includes logical OR relationships, and is expanded into several rules in memory, you do not need to retract each rule. Since the original statement itself is expanded into many rules, you can retract the whole statement which retracts all generated rules at once:

    > star("Sun").
    > a(X, Y) :- ((c(Z))); ((b(X); c(X)), (b(Y); c(Y))).
    > listing
    0: star('Sun').
    1: a(X, Y) :- c(Z).
    2: a(X, Y) :- b(X), b(Y).
    3: a(X, Y) :- b(X), c(Y).
    4: a(X, Y) :- c(X), b(Y).
    5: a(X, Y) :- c(X), c(Y).

    >
    > a(X, Y) :- b(X), b(Y).
    > a(X, Y) :- c(X), c(Y)~
    > listing
    0: star('Sun').
    1: a(X, Y) :- c(Z).
    2: a(X, Y) :- b(X), b(Y). (2)
    3: a(X, Y) :- b(X), c(Y).
    4: a(X, Y) :- c(X), b(Y).

    >
    > a(X, Y) :- ((c(Z))); ((b(X); c(X)), (b(Y); c(Y)))~
    > listing
    0: star('Sun').
    1: a(X, Y) :- b(X), b(Y).

To reduce the amount of typying required, you can also retract in-memory rules by their index (the left-most number that appears when executing "listing". This is done using the built-in command "retract <Index>".

    > a(X, Y) :- ((c(Z))); ((b(X); c(X)), (b(Y); c(Y))).
    > listing
    0: a(X, Y) :- c(Z).
    1: a(X, Y) :- b(X), b(Y).
    2: a(X, Y) :- b(X), c(Y).
    3: a(X, Y) :- c(X), b(Y).
    4: a(X, Y) :- c(X), c(Y).

    >
    > retract 2
    > retract 2
    > listing
    0: a(X, Y) :- c(Z).
    1: a(X, Y) :- b(X), b(Y).
    2: a(X, Y) :- c(X), c(Y).

Environment commands

Aside from the language itself, some commands are required to perform operations related to the interpreter and global table themselves. These are:

quit
Stop execution and exit the interpreter if in interactive mode; only stop processing the current file if in consult mode
select_table <Name>
Changes the global table of clauses currently in use; by default, table "0" is active; passing no argument prints the current table number
listing
Prints all clauses kept in the current global table
retract <Index>
Retracts a clause from the current global table specified by index
consult <File path>
Read and interpret a Daki language file; receives file path as an argument
add_memo <Name>
Add a clause name to the list of clauses to memoize (ex: "func/3")
rem_memo <Name>
Remove a clause name to the list of clauses to memoize; clears the memory pertaining to that clause
list_memo
List all clause names of the memoization list
clear_memo
Clear all memory spent on clause memoization (does not clear the list of clauses to memoize)

These commands are executed without any trailing ".", "?" or "!", and are case-insensitive. The memo commands are made clear in the memoization section.

The language features up to here are the minimum required for a pure, logic-based, query-only language. For many real problems, however, this is not enough.

Operator clauses

The Daki language also has built-in clauses, that unify with user-specified clauses and perform some form of calculation. To see why these are important, let's look at a practical example. In a language like Prolog, for instance, calculating a number in the Fibonacci sequence may look like:

    fib(1, 1).
    fib(2, 1).
    fib(N, X) :- f1 = fib(N - 1, X1), f2 = fib(N - 2, X2), X is X1 + X2.

In Prolog we find arithmetic and conditional logic mixed with the clause itself. In the Daki language, however, we prefer to keep the clause format consistent even for these operations. We use instead what we call operator clauses.

Operator clauses are always unifiable only when the input variables are present, if any, and for performance they are always unified before user-defined clauses where possible. The result of the operation is output in the last argument.

Some operator clauses have variants with the same name but higher arity. This is represented by "...", bellow and it means that it accepts an infinite number of input arguments.

Arithmetic operator clauses

The inputs must be numeric to unify.

add(Numeric1, Numeric2, ...., Output).
Unifies with the result of the addition of the inputs
sub(Numeric1, Numeric2, Output).
Unifies with the result of the subtraction of Input1 with Input2
mul(Numeric1, Numeric2, ..., Output).
Unifies with the result of the multiplication of the two inputs
div(Numeric1, Numeric2, Output).
Unifies with the result of the division of the two inputs; integer division is used if both inputs are integer
mod(Numeric1, Numeric2, Output).
Unifies with the rest of the integer division of the two inputs
pow(Numeric1, Numeric2, Output).
Unifies with the result ofInput1 to the power of Input2
sqrt(Numeric, Output).
Unifies with the result of the square root of Input
log(Numeric1, Numeric2, Output).
Unifies with the logarithmic base Input2 of Input1
round(Numeric1, Numeric2, Output).
Unifies with the rounded value of Input1 to Input2 decimal cases
trunc(Numeric, Output).
Unifies with the value of Input without decimal part
floor(Numeric, Output).
Unifies with the largest integer value that is less or equal to the input
ceil(Numeric, Output).
Unifies with the smallest integer value that is greater or equal to the input
abs(Numeric, Output).
Unifies with the absolute value of the input
eval(Numeric1, ..., StringN, Output).
Replaces the instances of a placeholder for each variable "$N" in StringN with each numeric value with the same index, and resolves the resulting equation; ignores whitespace; instead of using this clause directly, see inline operations

Bitwise operator clauses

The inputs must be of type Integer to unify.

bit_and(Integer1, Integer2, Output).
Unifies with the bitwise AND of the two inputs
bit_or(Integer1, Integer2, Output).
Unifies with the bitwise OR of the two inputs
bit_xor(Integer1, Integer2, Output).
Unifies with the bitwise XOR of the two inputs
bit_neg(Integer, Output).
Unifies with the bitwise inversion of the bits of the input
bit_shift_left(Integer1, Integer2, Output).
Unifies with the left shifted value of Integer1 by Integer2
bit_shift_right(Integer1, Integer2, Output).
Unifies with the right shifted value of Integer1 by Integer2

Comparison operator clauses

The inputs must be both numeric or both strings to unify.

eql(Input1, Input2, Output).
Unifies if the values are equal; with the string literal 'Yes'
neq(Input1, Input2, Output).
Unifies if the values are not equal; with the string literal 'Yes'
max(Input1, Input2, ..., Output).
Unifies with the maximum value between the inputs; if the inputs are strings, string comparison is used instead of numeric
min(Input1, Input2, ..., Output).
Unifies with the minimum value between the inputs; if the inputs are strings, string comparison is used instead of numeric
gt(Input1, Input2, Output).
Unifies if Input1 is greater than Input2; if any of the inputs is a string, string comparison is used instead of numeric; unifies with the string literal 'Yes'
lt(Input1, Input2, Output).
Unifies if Input1 is lower than Input2; if any of the inputs is a string, string comparison is used instead of numeric; unifies with the string literal 'Yes'
gte(Input1, Input2, Output).
Unifies if Input1 is greater or equal to Input2; if any of the inputs is a string, string comparison is used instead of numeric; unifies with the string literal 'Yes'
lte(Input1, Input2, Output).
Unifies if Input1 is lower or equal to Input2; if any of the inputs is a string, string comparison is used instead of numeric; unifies with the string literal 'Yes'

Type casting operator clauses

The inputs must be of the correct data type to unify.

as_string(Input, Output).
Unifies with the text representation of the input (of any type)
as_string(Integer1, Integer2, Output).
Unifies with the text representation of Integer1, with the base specified by Integer2
as_integer(Input, Output).
Unifies with the integer value of the input (of any type); will truncate floating point values
as_integer(String1, Integer2, Output).
Unifies with the integer value of String1, with the base specified by Integer2
as_float(Input, Output).
Unifies with the floating point value of the input (of any type)

String operator clauses

The inputs must be of the correct data type to unify.

len(String, Output).
Unifies with the number of characters of a string input
concat(String1, String2, ..., Output).
Unifies with the concatenation of the string inputs
slice(String1, Integer2, Integer3, Output).
Unifies with the remainder of a string String1 starting at index Integer2 and ending at index Integer3, or the end of the string
index(String1, String2, Integer3, Output).
Unifies with the integer position of String2 if found in String1, or integer literal -1; searching starting from Integer3
ord(String, Output).
Unifies with the numeric Unicode value of the first character in the string input
char(Integer, Output).
Unifies with a string with the Unicode character found for the integer input
split(String1, String2, Output).
Unifies with a list of the separate string characters of String1, separated by String2; if String2 is the empty string (''), every character is separated

List operator clauses

The inputs must be of the correct data type to unify.

head(List, Output).
Unifies with the first element of the list; list must not be empty
tail(List, Output).
Unifies with the remaining elements of the lest after the first one; will unify with empty list ([]) for inputs with a single element, and will not unify with empty lists
push(List1, Input2, Output).
Unifies with a list with Input2 added at the beginning of List1
append(List1, Input2, Output).
Unifies with a list with Input2 added at the end of List1
put(List1, Input2, Integer3, Output).
Unifies with a list with Input2 added at position Integer3 of List1; position Integer3 must be valid
len(List, Output).
Unifies with the number of elements in the list
concat(List1, List2, ..., Output).
Unifies with the concatenation of the list inputs into one
slice(List1, Integer2, Integer3, Output).
Unifies with the remainder of list List1 starting at index Integer2 and ending at index Integer3, or the end of the list
index(List1, Input2, Integer3, Output).
Unifies with the integer position of Input2 if found in List1, or integer literal -1; the search starts from index Integer3
unique(List, Output).
Unifies with the the list of unique elements
reverse(List, Output).
Unifies with the the list with all elements in the inverse positions
sort(List, Output).
Sorts all the elements of the list; all must be of a similar type: numeric, strings or lists
sum(List, Output).
Sum all the elements of the list; all must be of a similar type: numeric, strings or lists; the sum of strings will have a similar output to join/3, and the sum of lists a similar output to concat/3
max(List, Output).
Find the maximum value of all the elements of the list; all must be of a similar type: numeric, strings or lists
min(List, Output).
Find the minimum value of all the elements of the list; all must be of a similar type: numeric, strings or lists
join(List1, String2, Output).
Converts each element of the list to string and joins the strings with the String2 separator
init(Integer1, Input2, Output).
Unifies with a list of size Integer1 with each element set to Input2

Other operator clauses

These always unify.

set(Input, Output).
Just transposes the input to the ouput variable
rand(Output).
Unifies with a random floating point value between 0 and 1
type(Input, Output).
Unifies with the string literal of the name of the data type of Input: 'string', 'integer' or 'float'
print(Input, Output).
Print Input to the console; unifies with the string literal 'Yes'
print(Input1, Input2, Output).
Print Inpu1 to the console; Input2 is used to enforce order of execution; unifies with the string literal 'Yes'
time(Output).
Unifies with the integer number of milliseconds since the UNIX epoch
time(Input, Output).
Unifies with the integer number of milliseconds since the UNIX epoch; the input is used to enforce order of execution

Operator clauses cannot be overwritten or retracted with clauses with the same name and arity. They also only unify with some data types - for instance an arithmetic clause will not unify with string arguments. Illegal argument combinations, like trying to divide by 0, also do not unify.

Let's now go back to how to implement a program that returns the value of the Fibonacci sequence at position N. At first glance, the solution in Daki would be:

    > fib(1, 1).
    > fib(2, 1).
    > fib(N, Res) :- gt(N, 2, Y), sub(N, 1, N1), sub(N, 2, N2), fib(N1, F1), fib(N2, F2), \
                     add(F1, F2, Res).

Since this solution is recursive: a dependency on fib will try all solutions by expanding all clauses named fib, including itself; does this result in an infinite cycle? Not quite. A Daki interpreter is smart enough to stop the whole tail calculation when one of it's parts is proven impossible to unify, and most cases we don't have to think hard about this: operator clauses are guaranteed to have higher priority to being processed, and thus the expansion of the clause tail can be aborted sooner.

Clause conditions

The Daki interpreter, however, is not all-knowing. A more complex example may require many clause expansions to reach a falsifiable part. The best solution would be to avoid expanding clauses dependencies as early as possible.

This is best achieved by using what we call clause conditions. Clause conditions are boolean tests on variables of the head of candidate clauses to be evaluated. The condition is tested at the clause selection phase, which is more efficient. With clause conditions our Fibonacci program becomes:

    > fib(1, 1).
    > fib(2, 1).
    > fib(N > 2, Res) :- sub(N, 1, N1), sub(N, 2, N2), fib(N1, X1), fib(N2, X2), \
                         add(X1, X2, Res).

The clause condition fib(N > 2, Res) restricts matching N to values greater than the numeric value 2. The full list of operators is as follows.

Condition Operators

<
Tests if the variable is lower than the literal; not available for list types
<=
Tests if the variable is lower or equal to the literal; not available for list types
>
Tests if the variable is greater than the literal; not available for list types
>=
Tests if the variable is greater or equal to the literal; not available for list types
<>
Tests if the variable is not equal to the literal
:
Tests if the data type of the variable is the literal value (from 'integer', 'float', 'string' or 'list')

Clause conditions are exclusively between a variable and a literal value, and different data types never unify, except if they are both numeric. This contrasts with the usual clause matching rules that do not unify integer with floating point literals. The comparison operators use alphabetical order for strings.

Also note that you can mix multiple conditions. A variable must match all conditions for the clause to be expanded:

    > positive_except_five1(0 < N, N <> 5.0).
    > positive_except_five(N) :- positive_except_five1(N, N).
    >
    > positive_except_five(3)?
    Yes

    > positive_except_five(4.50)?
    Yes

    > positive_except_five(5)?
    No

    > positive_except_five(-3)?
    No

    > positive_except_five('1')?
    No

    > is_string(X: 'string').
    > is_string(1)?
    No

    > is_string(1.0)?
    No

    > is_string("1")?
    Yes

    > is_float(X: 'float').
    > is_float(1)?
    No

    > is_float(1.0)?
    Yes

    > is_float("1")?
    No

    > is_integer(X: 'integer').
    > is_integer(1)?
    Yes

    > is_integer(1.0)?
    No

    > is_integer("1")?
    No

    > is_numeric(X) :- is_float(X); is_integer(X).
    > is_numeric(1)?
    Yes

    > is_numeric(1.0)?
    Yes

    > is_numeric("1")?
    No

As a last example, we can also benchmark how fast our two Fibonacci functions are, by making use of the time/2 and time/3 operator clauses:

    > # Using only operator clauses
    > fib1(1, 1).
    > fib1(2, 1).
    > fib1(N, Res) :- gt(N, 2, gt), sub(N, 1, N1), sub(N, 2, N2), fib1(N1, X1), \
                      fib1(N2, X2), add(X1, X2, Res).
    > time_fib1(N, Val, Elapsed) :- time(StartTime), fib1(N, Val), time(Val, EndTime), \
                                    sub(EndTime, StartTime, Elapsed).
    >
    > time_fib1(10, Val, Elapsed)?
    Val = 144
    Elapsed = 161

    > # Using a clause condition
    > fib2(1, 1).
    > fib2(2, 1).
    > fib2(N > 2, Res) :- sub(N, 1, N1), sub(N, 2, N2), fib2(N1, X1), fib2(N2, X2), \
                          add(X1, X2, Res).
    > time_fib2(N, Val, Elapsed) :- time(StartTime), fib2(N, Val), time(Val, EndTime), \
                                    sub(EndTime, StartTime, Elapsed).
    >
    > time_fib2(10, Val, Elapsed)?
    Val = 144
    Elapsed = 99

As you can see, using only operator clauses where a clause condition could've been used can result in a large performance penalty. Operator clauses are obviously still useful for intermediate calculations, but should be avoided for logic control.

Inline Operations

Even though operator clauses are very powerful, it can still be somewhat cumbersome to write mathematical formulas using them. For this reasion, some of the more common numeric operations can still be used inline, as such: 
    > is_power(N, N2) :- eql(N * N, N2, Res).
    > is_power(3, 9)?
    Yes

    > print_more(N, L) :- print(N + (L * 2), Out1), \
                          print(N * 2, Out2), \
                          print(N * N, Out3), \
                          print((N + 1) * N + 1, Out4).
    > print_more(5, 2)?
    9
    10
    25
    31
    Yes

Inline operations are limited to the following numeric operations and the use of parenthesis. Invalid operations like dividing by zero do not unify.

Inline Operators

+
Numeric addition
-
Numeric subtraction
*
Numeric multiplication
/
Numeric division; integer division if both operands are integer
%
Remainder of the numeric division
&
Bitwise AND
|
Bitwise OR
^
Bitwise XOR
~
Bitwise complement

Notice the bitwise complement operator is the only one with a single operand. It is used as, for example, "~123", so you will need to surround it with parenthesis if in the middle of a longer expression.

In practice, inline operations are expanded into using the eval operator clause with an intermediate variable for the output. You can see this seamless expansion by using the command listing.

    > sum_of_powers(X, Y, Res) :- set((X * X) + (Y * Y), Res).
    > sum_of_powers(3, 2, Sum)?
    Sum = 13

    > listing
    0: sum_of_powers(X, Y, Res) :- eval(X, Y, '($0*$0)+($1*$1)', $1), set($1, Res).

Inline operations, the eval operator clause and in fact the entire parsing algorithm uses deterministic finite-state machines for the evaluation. Because of this the operators do not have an intrinsic operator priority, they are evaluated sequentially. You must use parenthesis to enforce an evaluation order.

Memoization

In the last example where we calculated the value of position N of the Fibonacci sequence, we were recalculating many intermediate values. In some contexts, this is required, because a clause can be expanded in many ways; other types this can be avoided, and we can apply memoization to the known unifiable forms of the clause.

In the Daki language this is done by telling the interpreter what functions can be memoized:

    > # Having fib1, fib2, time_fib1 and time_fib2 defined before
    >
    > add_memo fib1/2
    OK

    > add_memo fib2/2
    OK

    >
    > time_fib1(12, Val, Elapsed)?
    Val = 144
    Elapsed = 11

    > time_fib2(12, Val, Elapsed)?
    Val = 144
    Elapsed = 8

    >
    > # Values have already been completely memoized:
    >
    > time_fib1(12, Val, Elapsed)?
    Val = 144
    Elapsed = 0

    > time_fib2(12, Val, Elapsed)?
    Val = 144
    Elapsed = 0

In this example, we have instructed the interpreter to remember the argument configurations for which our functions unify, and, where possible, to reuse those configurations instead of starting new searches. We must be very careful to be consistent in how we expand our requirements on a memoized clause. If we later tried to find out all positions in the Fibonacci sequence for which the value is 1, it would fail to give all the solutions, because it has already cached one configuration that unifies:

    > fib2(X, 1)?
    X = 1

Memoization is always relative to a global clauses table. Changing to another table will use another memoization tree. Adding or retracting individual clauses does not affect what clauses are memoized, nor is the process memory cleared, use the built-in commands rem_memo and clear_memo for that.

As a last example, let's create a small program that prints the first twenty elements of the Fibonnaci sequence, using memoization, lists and inline operations:

    > add_memo fib/2
    OK

    >
    > fib(1, 1).
    > fib(2, 1).
    > fib(N > 2, Res) :- fib(N - 1, X1), fib(N - 2, X2), add(X1, X2, Res).
    >
    > fib_seq(0, []).
    > fib_seq(N > 0, Out) :- fib(N, Val), init(1, Val, Out2), fib_seq(N - 1, Out1), \
                             concat(Out1, Out2, Out).
    >
    > time_fib2(N, Out, Elapsed) :- time(StartTime), \
                                    fib_seq(N, Out), \
                                    time(Out, EndTime), \
                                    sub(EndTime, StartTime, Elapsed).
    >
    > print_fib(N) :- time_fib2(N, Out, Elapsed), \
                      join(Out, ", ", Seq), \
                      concat("Sequence: ", Seq, Line1), \
                      print(Line1, ok), \
                      as_string(Elapsed, ElapsedStr), \
                      concat("Elapsed (ms): ", ElapsedStr, Line2), \
                      print(Line2, ok).
    >
    > print_fib(20)?
    Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 41
    81, 6765
    Elapsed (ms): 95
    Yes

Copyright (c) 2021 Gonçalo Mendes Ferreira

Permission to use, copy, modify, and/or distribute this document for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.