Well-formed expressions consist of symbols A, B, I, N and are either
This defines a certain set of well-formed expressions (statements of the ABIN language); for example, NBII is a statement of the language but AB is not. The truth/falsehood interpretation of the ABIN language is the following. All well-formed expressions starting with NB are interpreted as true statements (they are "axioms" of the system). In addition, there is one deduction rule allowing one to prove "theorems":
Thus, NABIBI can be proved starting from the axiom NBI, but NANBB cannot be proved. The task at hand is to decide whether a given sequence of symbols is a provable statement of the ABIN language.
(The idea behind this interpretation is to assume that all B, BI etc. are some false statements that one could denote "B0", "B1" according to the number of "I" symbols; "N" is the logical Not and "A" is the logical And. Then the statement NABIB would mean "it is false that both B0 and B1 are true" and NANBB would mean "it is false that both B0 and negation of B0 are true". The NANBB statement is true in this interpretation but the deductive system of ABIN is too weak to obtain its proof.)
IsExpr(x_IsList) <-- IsBExpr(x) Or IsNExpr(x) Or IsAExpr(x); IsProvable(x_IsList) <-- IsAxiom(x) Or IsTheorem(x); IsAxiom(x_IsList) <-- IsNExpr(x) And IsBExpr(Tail(x)); |
The definitions of IsBExpr(x) and IsNExpr(x) are simple recursion to express the rules 1 and 2 of the ABIN grammar. Note the use of Take to create a copy of a list (we'd better not modify the value of x in the body of the rule).
10 # IsBExpr({}) <-- False; 10 # IsBExpr({"B"}) <-- True; 20 # IsBExpr(x_IsList) <-- x[Length(x)]="I" And IsBExpr(Take(x, {1, Length(x)-1})); 10 # IsNExpr({}) <-- False; 20 # IsNExpr(x_IsList) <-- x[1] = "N" And IsExpr(Tail(x)); |
The predicate IsAExpr(x) is a little bit more complicated because our rule 3 requires to find two well-formed expressions that follow A. Also, for proving theorems we need to be able to extract the first of these expressions. With this in mind, we define another auxiliary function, FindTwoExprs(x), that returns the results of search for two well-formed expressions in the list x. The return value of this function will be a pair such as {True, 3} to indicate that two well-formed expressions were found, the first expression being of length 3. We shall use a For loop for this function:
FindTwoExprs(x_IsList) <-- [ Local(iter, result); For( [ iter:=1; result:=False; ], iter < Length(x) And Not result, iter:=iter+1 ) [ result := IsExpr(Take(x, iter)) And IsExpr(Take(x, {iter+1, Length(x)})); ]; {result, iter-1}; ]; |
Now we can define the remaining predicates:
10 # IsAExpr(x_IsList)_(Length(x) <= 1) <-- False; 20 # IsAExpr(x_IsList) <-- x[1] = "A" And FindTwoExprs(Tail(x))[1]; IsTheorem(x_IsList) <-- If(IsNExpr(x) And IsAExpr(Tail(x)) And IsProvable( Concat({"N"}, Take(Tail(Tail(x)), FindTwoExprs(Tail(Tail(x)))[2]) )); |
The ABIN language is now complete. Let us try some simple examples:
In> IsExpr({"A","B"}); Out> False; In> IsExpr({"N","B","I"}); Out> True; In> IsAxiom({"N","B","I"}); Out> True; In> IsTheorem({"N","B","I"}); Out> False; In> IsProvable({"N","B","I"}); Out> True; In> IsProvable({"N","A","B","I","B"}); Out> True; |
It is somewhat inconvenient to type long lists of characters. So we can create an interface function to convert atomic arguments to lists of characters, e.g. AtomToCharList(BII) will return {"B","I","I"} (provided that the symbol BII has not been given a definition). Then we define a function ABIN(x) to replace IsProvable.
AtomToCharList(x_IsAtom) <-- [ Local(index, result); For( [ index:=Length(String(x)); result:={}; ], index > 0, index:=index-1 ) Push(result, StringMid(index, 1, String(x))); result; ]; Holdarg(AtomToCharList, 1); ABIN(x) := IsProvable(AtomToCharList(x)); |
In> AtomToCharList(NBII); Out> {"N", "B","I","I"}; In> ABIN(NANBB); Out> False; |
It is easy to modify the predicates IsTheorem() and IsAxiom() so that they print the sequence of intermediate theorems and axioms used for deriving a particular theorem. The final version of the code is in the file examples/ABIN.ys. Now we can try to check a "complicated" theorem and see an outline of its proof:
In> ABIN(NAAABIIBIBNB); Axiom {"NBII"} Theorem NABIIBI derived Theorem NAABIIBIB derived Theorem NAAABIIBIBNB derived Out> True; |
Suppose we want to build a system that understands a simple set of English sentences and will be able to answer questions. For example, we would like to say "Tom had an apple and Jane gave 3 apples to Tom"; the system should understand that Tom has 4 apples now. In the usual LISP-based treatments of artificial intelligence, this problem would be illustrated with a cumbersome list syntax such as (had (Tom apple 1)) but we would like to use the power of the Yacas syntax and use plain English.
We shall create a set of rules that will "simplify" sentences to atoms such as True or False. As a side-effect, these "simplifications" will maintain a "knowledgebase" of information about all existing persons and objects.
Unix> yacas [editvi.ys] [gnuplot.ys] [unix.ys] True; Numeric mode: "Internal" To exit Yacas, enter Exit(); or quit or Ctrl-c. Type ?? for help. Or type ?function for help on a function. Type 'restart' to restart Yacas. To see example commands, keep typing Example(); In> Load("wordproblems.ys") Out> True; In> Jitse and Ayal are persons; OK, Jitse is a person. OK, Ayal is a person. Out> {True,True}; In> apple is an object; OK, apple is an object. Out> True; In> there are many apples and pears; Note: we already know that apple is an object OK, we assume that the plural of " apple " is " apples ". OK, pear is an object. OK, we assume that the plural of " pear " is " pears ". Out> {True,True}; In> Serge had an apple; OK, Serge is a person. OK, Serge has 1 apples now. Out> True; In> Jitse had (10!) pears; OK, Jitse has 3628800 pears now. Out> True; In> Ayal had (2+3) apples and Serge had \ 2 pears; OK, Ayal has 5 apples now. OK, Serge has 2 pears now. Out> {True,True}; In> Serge ate the apple; OK, Serge has no apples now. Out> True; In> Ayal ate a pear;// this should fail Error: Ayal does not have enough pears at this time. Out> False; In> Ayal gave an apple to Serge and \ Serge gave a pear to Ayal; OK, Ayal has 4 apples now. OK, Serge has 1 apples now. OK, Serge has 1 pears now. OK, Ayal has 1 pears now. Out> {True,True}; In> Ayal ate a pear; OK, Ayal has no pears now. Out> True; In> soup is an object and Ayal had \ some soup; OK, soup is an object. OK, Ayal has some soup now. Out> {True,True}; In> Ayal gave soup to Serge and Serge \ ate the soup; OK, Ayal has no soup now. OK, Serge has some soup now. OK, Serge has no soup now. Out> {True,True}; In> Serge has soup Out> no; In> Serge has apples Out> 1; In> Ayal has apples Out> 4; In> Serge has some soup Out> False; In> Serge has some apples Out> True; In> Ayal has some pears Out> False; In> Knowledge(); OK, this is what we know: Persons: Jitse, Ayal, Serge Object names: soup, pear, apple Countable objects: pears, apples Jitse has: 3628800 pears |
Ayal has: 4 apples no pears no soup |
Serge has: 1 apples 1 pears no soup |
Out> True; In> software is an object OK, software is an object. Out> True; In> Ayal made some software OK, Ayal has some software now. Out> True; In> Ayal gave some software to everyone OK, everyone is a person. OK, Ayal still has some software OK, everyone has some software now. Out> True; In> Ayal gave some software to Serge OK, Ayal still has some software OK, Serge has some software now. Out> True; In> Serge ate the software OK, Serge has no software now. Out> True; |
The string "OK" is printed when there is no error, "Note" when there is a warning, and "Error" on any inconsistencies in the described events. The special function Knowledge() prints everything the system currently knows.
Now we shall see how this system can be implemented in Yacas with very little difficulty.
It is logical to declare "had" as an infix operator and "a" as a prefix operator quantifying lamb. In other words, "Mary had a lamb" should be parsed into had(Mary, a(lamb)). This is how we can do it:
In> [ Infix("had", 20); Prefix("a", 10); ] Out> True; In> FullForm(Mary had a lamb) (had Mary (a lamb )) Out> Mary had a lamb; |
Note that we declared the precedence of the prefix operator "a" to be 10. We have in mind declaring another infix operator "and" and we would like quantifiers such as "a", "an", "the" to bind more tightly than other words.
Clearly, we need to plan the structure of all admissible sentences and declare all necessary auxiliary words as prefix, infix, or postfix operators. Here are the patterns for our admissible sentences:
"X is a person" -- this declares a person. Parsed: is(X, a(person))
"X and Y are persons" -- shorthand for the above. Parsed: are(and(X, Y), persons). "person" and "persons" are unevaluated atoms.
"A is an object" -- this tells the system that "A" can be manipulated. Parsed: is(A, an(object))
"there are many As" -- this tells the system that "A" can be counted (by default, objects are not considered countable entities, e.g. "milk" or "soup"). Parsed: are(there, many(As)). Here "As" is a single atom which will have to be stripped of the ending "s" to obtain its singular form.
"X ate N1 As", for example, Tom ate 3 apples -- parsed as ate(Tom, apples(3)). Since we cannot make the number 3 into an infix operator, we have to make apples into a postfix operator that will act on 3.
"X gave N As to Y" -- Here "N" is a number and "A" is the name of an object. Parsed as: gave(X, to(As(N), Y)). So to and gave are infix operators and to binds tighter than gave.
Sentences can be joined by "and", for example: "Tom gave Jane an apple and Jane ate 3 pears". This will be parsed as the infix operator "and" acting on both sentences which are parsed as above. So we need to make "and" of higher precedence than other operators, or else it would bind (apple and Jane) together.
"X made some A" -- note that if "A" is not countable, we cannot put a number so we need to write some which is again a prefix operator. made is an infix operator.
"X ate some A" -- the interpretation is that some A is still left after this, as opposed to "X ate the A" or "X ate A".
"X gave some A to Y" -- similarly, X still has some A left after this.
After each sentence, the system should know who has what at that time. Each sentence is parsed separately and should be completely interpreted, or "simplified".
All knowledge is maintained in the variable Knowledge which is an associative list with three entries:
Knowledge := { {"objects", {} }, {"countable objects", {} }, {"persons", {} } }; |
Infix("is", 20); Prefix("a", 10); _x is a person <-- DeclarePerson(x); |
The operator "and" will group its operands into a list:
Infix("and", 30); 10 # x_IsList and _y <-- Concat(x, {y}); 15 # _x and _y <-- Concat({x}, {y}); |
10 # there are many xs_IsList <-- MapSingle("DeclareCountable", xs); 20 # there are many _xs <-- DeclareCountable(xs); |
However, in the present system we cannot simultaneously parse "there are many apples and ideas" and "Isaac had an apple and an idea" because we have chosen had to bind tighter than and. We could in principle choose another set of precedences for these operators; this would allow some new sentences but at the same time disallow some sentences that are admissible with the current choice. Our purpose, however, is not to build a comprehensive system for parsing English sentences, but to illustrate the usage of syntax in Yacas.
Declaring objects is a little more tricky (the function DeclareCountable). For each countable object (introduced by the phrase "there are many ...s") we need to introduce a new postfix operator with a given name. This postfix operator will have to operate on a preceding number, so that a sentence such as "Mary had 3 lambs" will parse correctly.
If x were an unevaluated atom such as "lambs" which is passed to a function, how can we declare lambs to be a postfix operator within that function? The string representation of the new operator is String(x). But we cannot call Postfix(String(x)) because Postfix() does not evaluate its arguments (as of Yacas 1.0.49). Instead, we use the function UnList to build the expression Postfix(String(x)) with String(x) evaluated from a list {Postfix, String(x)}, and we use the function Eval() to evaluate the resulting expression (which would actually call Postfix()):
Eval(UnList({Postfix, String(x)} )); |
MacroRuleBase(String(x), {n}); |
Finally, we would need to define a rule for "had" which can match expressions such as
_Person had n_IsNumber _Objects |
Incidentally, the parser of Yacas does not allow to keep unevaluated atoms that are at the same time declared as prefix operators but it is okay to have infix or postfix operators.
A rule that we need for an operator named String(x) can be defined using MacroRule:
MacroRule(String(x), 1, 1, True) {x, n}; |
In> 5 lambs; Out> {lambs, 5}; In> grilled lambs Out> {lambs, grilled}; |
But what about the expression "many lambs"? In it, many is a prefix operator and lambs is a postfix operator. It turns out that for Yacas it is the prefix operator that is parsed first (and remember, we cannot have unevaluated atoms with the same name as a prefix operator!) so "many lambs" will be transformed into many(lambs) and not into an illegal expression {lambs, many}.
Ayal gave soup to Serge and Serge ate the soup |
{gave(Ayal, to(soup, Serge)), ate(Serge, {soup, 1}} |
Here is the simplest rule: "giving" is implemented as a sequence of "eating" and "making".
10 # _x gave _obj to _y <-- [ x ate obj; y made obj; ]; |
One more subtlety connected with the notion of "countable" vs. "uncountable" objects is that there are two different actions one can perform on an "uncountable" object such as "soup": one can eat (or give away) all of it or only some of it. This is implemented using the keyword "some" which is a prefix operator that turns its argument into a list,
some _obj <-- {obj, True}; |
the _x <-- {x, 1}; |
To implement this, we have made a special rule for the pattern
_x had {obj, True} <-- ... |
_x had {obj, n_IsNumber} <-- ... |
(_x had _obj )_(Not IsList(obj)) <-- x had {obj, 1}; |
Admittedly, the module wordproblems.ys has not very much practical use but it is fun to play with and it illustrates the power of syntactic constructions from an unexpected angle.
The libltdl library, part of the libtool package and distributed together with Yacas, is used to load the plugins. This means that plugins will only function on platforms supported by libltdl. This includes Linux, Mac OS X, Solaris, and HP-UX.
Plugins currently have to be written in C++ and require certain include files from the Yacas source tree. A plugin may be compiled as a shared object after Yacas itself has been compiled and installed successfully.
// FILE: func1.h double func1 (double x, double y); |
// FILE: func1.cc #include "stubs.h" // required #include "func1.h" // our exported API #include <math.h> // we need math.h for sin() double func1 (double x, double y) { return sin(x/y); } |
For our simple plugin, we shall only need a few lines of code in the Yacas stub:
/* FILE: func1_api.stub */ Use("cstubgen.rep/code.ys"); /* Start generating a C++ stub file */ StubApiCStart("Func1"); /* Write some documentation */ StubApiCRemark("This function computes beautiful waves."); /* define a plugin-specific include file */ StubApiCInclude("\"func1.h\""); /* Declare a plugin-specific function */ StubApiCFunction("double","func1","Func1", { {"double","x"},{"double","y"}}); /* generate a C++ stub file "func1_api.cc" */ StubApiCFile("libfunc1","func1_api"); |
Another example of a Yacas stub is found in the file plugins/example/barepluginapi.stub of the source tree.
yacas -pc func1_api.stub |
libtool c++ -I/usr/local/include/yacas/ -I/usr/local/include/yacas/plat/linux32/ -c func1.cc |
libtool c++ -I/usr/local/include/yacas/ -I/usr/local/include/yacas/plat/linux32/ -c func1_api.cc |
libtool c++ -module -avoid-version -no-undefined -rpath `pwd` -o libfunc1.la func1.lo func1_api.lo |
If compilation succeeds, the dynamic library file libfunc1.la is created. This is our plugin; now it could be installed into the Yacas plugin path (usually /usr/local/lib/yacas/) with
libtool cp example.la /usr/local/lib/yacas/example.la |
But we can also keep it in the working directory.
In> DllLoad("libfunc1"); Out> True; |
If the plugin is not installed in the Yacas plugin path, we have to specify the path to the plugin, eg. DllLoad("./libfunc1").
In> Func1(2,3); Out> 0.61837; |
In> DllUnload("libfunc1"); Out> True; |
Suppose we had a numerical function on real numbers, e.g.
In> f(x,y):=Sin(2*x*Pi)+Sqrt(2)*Cos(y*Pi); Out> True; |
We can generate some C++ code that calculates this function for given floating-point arguments (not for multiple-precision numbers):
In> CForm(f(x,y)); Out> "sin(2 * x * Pi) + sqrt(2) * cos(y * Pi)"; |
Now it is clear that all the steps needed to compile, link, and load a plugin that implements f(x,y) can be performed automatically by a Yacas script. (You would need a C++ compiler on your system, of course.)
This is implemented in the function MakeFunctionPlugin() (see file unix.ys in the addons/ subdirectory). To use it, we might first define a function such as f(x,y) above and then call
In> MakeFunctionPlugin("fFast", f(x,y)); Function fFast(x,y) loaded from ./plugins.tmp/libfFast_plugin_cc.so Out> True; In> fFast(2,3); Out> -1.41421; |
Now we can use the function fFast(x,y) which is implemented using an external plugin library. The function MakeFunctionPlugin() assumes that all arguments and return values of functions are real floating-point numbers. The plugin libraries it creates are always in the plugins.tmp/ subdirectory of current working directory and are named like libNNN_plugin_cc.so.
If MakeFunctionPlugin() is called again to create a plugin function with the same name (but different body), the DLL will be unloaded and loaded as necessary.
The Yacas header files are installed in /usr/local/share/yacas/include, and the libraries in /usr/local/share/yacas/lib. The main entry library is the cyacas library, which offers an interface which can be reached through a normal c or c++ program. The API it offers is the following:
void yacas_init(); |
void yacas_eval(char* expression); |
char* yacas_error(); |
char* yacas_result(); |
char* yacas_output(); |
void yacas_exit(); |
void yacas_interrupt(); |
The directory embed/ contains some examples demonstrating calling Yacas from your own programs. Use the makefile.examples makefile to compile the examples (it is in a separate makefile because it is not yet guaranteed to work on all platforms, so it might otherwise break builds on some platforms).
The simplest "hello world"-type example is example2, which reads:
#include <stdio.h> #include "cyacas.h" int main(int argc, char** argv) { yacas_init(); yacas_eval("D(x)Sin(x)"); if (!yacas_error()) printf("%s\n",yacas_result()); yacas_exit(); return 0; } |
And yields on the command line:
$ ./example2 Cos(x); |
The example example1 allows you to pass expressions on the command line:
$ ./example1 "D(x)Sin(x)" "Taylor(x,0,5)Sin(x)" Input> D(x)Sin(x) Output> Cos(x); Input> Taylor(x,0,5)Sin(x) Output> x-x^3/6+x^5/120; |
The file example3 shows a piece of code accepting an expression in Lisp syntax, the result being printed to the console using PrettyForm.
The interface described above will probably not change very much in the future, but the way to compile and link might. In an ideal world, there would be one library libcyacas.a and one header file cyacas.h, which get installed in a place where all programs can find it. Perhaps a dynamic link library is even better.