A Squl module is made of many Squl statements. Each statement describes how a part of your application works.
A simple Squl statement looks like the following:
list:( head:H tail:_ ) head:H.
This statement defines the head of a list to be the first element of a list.
Each statement consists of a number of clauses. In the example statement, there are two clauses: * list:( head:H tail:_ ) * head:H
As you can see, each clause has a label, then a colon, then a value. The first clause has the label “list”, and a value which is a sub-statement. The second clause has the label “head” and the value “H”.
Finally, a statement is concluded with a period.
A query has exactly the same syntax as a statement but concludes with a question mark.
Labels can consist of any printable Unicode characters other than a period, question mark, parenthesis, colon or uppercase Latin characters. Each label in a statement must be unique within that statement, with the exception of the special label “if”. [Note: this restriction will be removed in version 0.3]
The clauses in a statement can appear in any order. For example, these two statements are identical:
father:alfred of:bob.
of:bob father:alfred.
[Note: in version 0.3, clauses will be ordered.]
Values can be atoms, variables, sub-statements or literals.
Atoms, such as “alfred”, consist of the same characters as labels, and exist as placeholders. For example, a list with a single element would be “head:singleElement tail:end.”, where “singleElement” and “end” are atoms.
Variables, such as “X”, are values that begin with an uppercase Latin character followed by any number of characters that would be valid in a label. Alternatively, they could be the character “_”, which creates a new unnamed variable every time it occurs.
A variable’s context is in a single statement: all instances of the same variable in a statement must have the same value, but if the same variable occurs in another statement, there is no relationship between the two statement’s variables (unless those two statements have been unified - variables in the two statements might then have the same name, but are considered different from each other).
Variables differ in usage from imperative programming. Variables are not assigned values. Instead, they are “matched” or “bound” to values to create a new statement. This is described in more detail later.
Sub-statements are just statements, enclosed in parenthesis to prevent them from falling apart. Any variables in sub-statements are considered to be part of the whole statement, so that instances of those variables, should they be deeply nested in substatements, are still bound to other instances elsewhere in the same statement.
Literals are integers, floats, characters, strings, and so forth. These are enclosed in square brackets. The very first character of a literal determines what type that literal is. Some examples of literals are:
A double-quote defines a string. A string can have any valid Unicode codepoints in it, including all whitespace and combining characters. A single closing square bracket (“]”) terminates a string, even if it is part of a combining pair of Unicode codepoints. To include a closing square bracket inside the string, include two square brackets: [“A single square bracket: ]] ] is the same as “A single square bracket: ] ”. To include special characters, you just type them in using whatever mechanisms are available (such as your operating system’s character map). Inserting special characters might be a feature of later versions of Faish. To include a newline character, you just type it in:
["Hello, world!
]
TODO: Floating point numbers are not yet implemented.
Another statement can be included as a statement literal rather than as a sub-statement. This will prevent any variables in that statement literal from being matched. The defining character for this is the backslash. For example, a statement literal appears like this: [head:a tail:end.].
One other type of literal is the module literal, but this is rarely used directly by a user but rather by utilities that the environment provides. These use the tab character as their defining character.
Literals can also be defined by the user.
TODO: user-defined literals not implemented yet.
An implementation of Squl would produce useful results from your program by combining statements to produce new ones, until a solution is found.
Take, for example, the list head example above:
list:( head:H tail:Tail ) head:H.
Say that we want an answer to this query (“what is the head of the list [,a, b]?”):
list:(head:a tail:(head:b tail:end)) head:X?
The following matches are made, by finding possible substitutions for all the variables in both statements:
H = a
Tail = ( head:b tail:end )
H = X
Here, we can see that H = a, and H = X, therefore X = a. The implementation then produces the following statement by substituting a for X:
list:(head:a tail:(head:b tail:end)) head:a.
This would be the result returned by the implementation. Note that no mention is made of the original X; you as a user are expected to be intelligent enough to see what happened to it.
If multiple substitutions, other than variables, are found for a variable then matching will fail and no result will be returned. For example:
list:( head:H tail:Tail ) head:H.
list:( head:a tail:end ) head:b?
This produces the following substitutions:
H = a
Tail = end
H = b
Here we have both H = a and H = b. Obviously a is not b, so this match would fail. If we had both H = a and H = a again, then it would succeed.
Substitutions also work with sub-statements. Say that we have these contrived statements:
a:( a:X ) b:B.
a:B b:( a:( b:c )).
Unifying (i.e. substituting variable) these together would produce the following substitutions:
a:X = B
B = a:( b:c )
Thus we can see that a:X = B = a:(b:c), thus a:X = a:(b:c), thus X = b:c, producing:
a:( a:( b:c )) b:( a:( b:c )).
There are some instances where unification can cause infinite loops of sub-statements in a statement. This is not implemented in the current version of Faish, but might be an interesting and useless esoteric feature to later include. Currently such statements cause the matching to fail.
To produce useful behaviour, we need some mechanism for being Turing-Complete. If-then rules achieve this by allowing for recursion.
An example if-then rule is:
if:(bounces:X) then:(ball:X).
However, it is more typically written in this format:
then:(
bounces:X )
if:(
ball:X ).
This is just another statement, spread over several lines. This is the conventional syntax for complex statements and is described in the language conventions section below.
Given, for example, the statement and query:
ball:myBlueBall.
bounces:myBlueBall?
Faish will then try to solve your query. First it searches for anything that matches “bounces:myBlueBall”, and finds the if-then rule above. It then unifies the if-then statement to produce “then:(bounces:myBlueBall) if:(ball:myBlueBall).”. Finally, it verifies the truth of the if-clause, by finding ball:myBlueBall, returning as result:
bounces:myBlueBall.
An if-then statement can have as many if-clauses as it wants. The then-clause is considered usable if all variables in the then-clause have values, and all if-clauses have been deduced or found in the modules.
When trying to find a solution to a query, multiple search paths are usually possible. For example:
Implementations are free to traverse the statements of a Squl application in whichever order they choose. There is, in fact, no guarantee your application will even run, but an implementation of Squl that does not actually produce useful results from your code will not be particularly popular.
It is entirely possible to have multiple processes or even multiple computers investigating the different options.
Some statements are intercepted by the implementation to provide primitive operations, such as adding two numbers together. These are described below:
TODO - list them all.
When the mathematics allows, these rules can also be used in reverse:
n:X plus:[+4] result:[+6]?
The built-in “query:Query numResults:N searchDepth:Depth timestamp:Time.” allows for negation-by-failure as follows:
then:(
noResults:Query )
if:(
query:Query numResults:[+0] searchDepth:10 timestamp:Time ).
Usually the programmer is responsible for including a similar rule in his module when desired. The programmer must use a searchDepth as appropriate; a large value may cause huge inefficiencies as infinitely recursive clauses are investigated, while a too-small value may cause valid solutions to not be found.
Using “not:X” for negation-by-failure is considered bad form. Negation-by-failure is not actual negation.
Note that version 0.3 of the Squl language will have added semantics for determining which built-in operations are available.