This HTML document is automatically generated from the Help file that accompanies Bracmat, using Bracmat to do the conversion.

# BRACMAT

starting with Bracmat
pattern matching
grammar
binary operators
flags/unary operators
strings or atoms
symbols
the four evaluation contexts
programming in Bracmat
functions
data structures
objects
hash tables
how Bracmat evolved
how to obtain Bracmat

# If you haven't seen Bracmat before ..

Bracmat is an interpreted programming language that will evaluate instructions that you type at the keyboard. For example, Bracmat can

- simplify an algebraic formula,
- read a text file with source code and execute this code in one go,
- save interactively created source code in a text file,
- handle big, irregular data structures with "life" and "dead" code,
- let you delve in any data structure by means of pattern matching and
- access any text or binary file like in a low level language.

In Bracmat, data and instructions have the same syntax: a mix of parentheses, binary operators, operands and flags preceding those operands or parentheses. In fact, in many cases you can't tell the difference between the two. Moreover, Bracmat offers only one, simple, environment for both input of data and code. After the {?} prompt you may start to write. Bracmat evaluates your input and writes the result to the screen following a {!} sequence (unless there was no visible result). Under the result follows a line that tells whether the evaluation was successful (S) or not (F) (in rare cases you may see a "I", which, for the time being, you may interpret as failure). In the same line the machine shows how much processor time it needed. Intermediary results may also appear on the screen.

Bracmat and calculators have an important common feature: as long as the input data are simple enough, the user need (and can) not specify how these data have to be processed. Calculators handle basic calculations in a predictable, unchangeable way, e.g. "4+7" will always result in "11", and not in, say, "10" or "23-12". That is because the manufacturer had good reasons to think that "11" is what the user expects and nothing else. In the same way, Bracmat handles basic "calculations" with a much wider variety of data: rational numbers, symbols, words and collections thereof. For example, "a+b+a" becomes "2*a+b" and not, say, "x.a" or b+2*a. Again, its creator has taken decisions that you can't easily circumvent. However, the more complex the data are, the better are the chances that not all results, although defendable, have an appearance that suits you. It is here that programming comes in: Bracmat leaves certain kinds of data unchanged, but opens the possibility to dissect data, to perform calculations on the parts, and to assemble an answer from the resulting sub-answers.

First and foremost Bracmat was developed with symbolic algebra in mind. You may add, multiply, take powers and logarithms and differentiate. Oddly enough, Bracmat has no operators for subtraction and division. This reduces the amount of arbitrariness in the presentation of formulae. "a-b" must be written as "a+-1*b" and "a/b" must be written as "a*b^-1". Calculations are always exact. Expressions for which no rational representation exists are not further evaluated. Bracmat knows how to handle the special symbols i, e and pi, but it offers no numerical representation for e and pi. Examples (you may enter them now, after the {?} prompt. If you only press
<enter> or <return> the next page is shown):

>     {?} a+b+-1*a                 { this is how you subtract in Bracmat }
>     {?} 1+(1+i)*(1+-1*i)+-1      { the leading and trailing terms force
>                                    Bracmat to expand the product }
>     {?} -12345/54321 ^ 1/2       { the square root of -12345/54321 }
>     {?} x^(a+x\L2*1000)
>     {?} 5/2 \L 987654
>     {?} y\D(x\D((x+y)^-2))

The only numbers that Bracmat can calculate with are integer and rational numbers. There is virtually no limit to their size, but the program is not optimised for number crunching. Bracmat handles a non-integer power of an integer if the absolute value of this integer is less than 2^32. Likewise, both the numerator and the denominator of a rational number should be less than 2^32. Bracmat happily adds and multiplies numbers of, say, a few hundred digits. There is a pre-defined function, flt$, that represents rational numbers in a "scientific" floating point notation, but Bracmat cannot do calculations with these "reals", unless you write a function to convert them back to rational numbers.

The binary operators have an ordering of precedence. Of the mathematical operators, + has the lowest precedence and \D the highest (+ * ^ \L \D). You may use parentheses to overrule this ordering:

>     {?} (a+b)*(a+c)+a^(-1*d^2+(d+1)*(d+-1))

When instructions are entered from the keyboard, the program waits until all of the conditions below are fulfilled:

- <return> (or <enter>) is the last key that has been pressed
- every opening parenthesis has a closing counterpart
- every opening brace (start of comment) has a closing counterpart
- every string has either two enclosing double quotes, or none.

You can write a multiple-line instruction by putting the instruction inside an extra pair of parentheses. After each non-terminating <return>, Bracmat shows in the next line how many closing parentheses are needed for the completion of the instruction. If you are in the middle of a string or a comment when pressing <return>, the next line starts with {str} or {com}, respectively. If you want to enter several instructions on the same line, you should write a semicolon ";" between the instructions. These instructions are executed in the same order. If you do not want to see the result of a calculation, you may write a semicolon after the last instruction. Instructions in a text file must be separated by semicolons. You may freely surround binary operators with white-space characters (e.g. space, tab, line feed). Take care not to put spaces between the characters that make up a rational or negative number, - 1234 / 5678 is not the same as -1234/5678.

Bracmat can open and read a text file and execute the instructions as they are read. After the last instruction has been executed, the file is closed. The program that currently produces this information, is read from the file named "help". The instruction for reading a file "myprog" and executing the instructions therein is "get$myprog". The "$" is a binary operator that has to do with function evaluation. "get" is the function name of one of the few built-in functions. The result of the last executed instruction in a file is written to the screen. For better control over screen output one may use the built-in function "put", which writes from the current cursor position to the right, or the pre-defined (but changeable) function "out", which writes an extra line feed after its argument has been written to the screen.

>     {?} put$(x*x);put$(y+y)

Often you will need the result of the last evaluated instruction in the next one. You can use the exclamation mark "!" instead of re-entering the result. (Because Bracmat is still evaluating the instruction "get$help", this trick is of no use in the context of this program.) Example (try later): 1+1 !^!^!^!

When you write programs in the Bracmat language you will normally use an external text editor. You can enter small programs directly at the Bracmat prompt {?}, but a small change in an instruction can only be done by re- entering the whole instruction. You may save instructions that are still held in memory (which is only possible if they are bound to variables), by the built-in "lst" function. This function takes a number of optional parameters that tell the system whether the instruction has to be written in a compact and barely readable form, or in a more pretty form, with lots of indentations. Comments are never written, as they are ignored at input time. As an example, you can write the definition of the pre-defined factorisation function "fct" to a file "factorise" by entering the following instruction:

>     {?} lst$(fct,factorise,NEW) {NEW:replace old file with same name}

At first sight, a Bracmat program doesn't look like programs written in other languages. This may even become a permanent impression. So here are some recommendations about programming habits:

- Experiment with the examples from this information program.
- Use a modular and incremental style of programming: test every function before going on to the next one.
- Keep functions small, to begin with. Error messages point to functions, not to line numbers.
- Use meaningful names. There is no limit to their length and you may use the minus-sign as separator in multiple-word-names.
- Write comments if variable names do not tell enough.
- Feel free to write parentheses if that clarifies the program structure.
- Write parentheses in a BEGIN-END-style, the closing parenthesis below the opening parenthesis.
- Check whether Bracmat interprets your code in the way you intended by listing your functions without the LIN option.
- Try to evade the "not" flag ~ and the use of arrays.

Overview: BRACMAT .

# Pattern matching

The single most outstanding feature of Bracmat is the way in which it can recognise patterns in data. The data can be an algebraic expression, a directory listing in table form, a thesaurus structured like a tree, a text or whatever data that can be expressed as a string of characters or as a tree of such strings. Bracmat's pattern matching functionality is more advanced than the functionality offered by regular expressions. Regular expressions are fixed patterns once the matching operation is started. In Bracmat, the pattern can change during the match operation, depending on what has been matched thus far. Thus, it is possible to use the result if another pattern match operation to decide how the still outstanding part of the pattern match operation should proceed. In this way it is very easy to implement a relational database. But it doesn't stop here. Not only pattern match operations, but any operation can be nested inside a pattern match operation.
pattern matching in character strings
pattern matching in tree structures
Overview: BRACMAT .

# Pattern matching in strings

>     @(<string> : <pattern>)   "match <string> with <pattern>"

Pattern matching in a string of characters (a single atom) is like pattern matching in a string of atoms. Use the '@' to instruct the program to look inside the atom and use space operators to combine subpatterns. The space operator does not itself match any characters. To match a space in an atom, use a space in an atom!

Overview: Pattern matching .
Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Previous about topic : match (left: subject, right: pattern) .
Previous about topic pattern matching .

# Binary operators in pattern matching

>     <subject> : <pattern>   "match <subject> with <pattern>"

A match succeeds if <subject> succeeds and <pattern> is successfully matched with <subject>. The returned value is the left operand, <subject>. Patterns may be built up from sub-patterns and may also include actions that are triggered if a sub-pattern successfully matches (part of) the subject. As with the evaluation of other binary operators, the left operand of the ":" operator is evaluated first. The other operand, <pattern>, is not evaluated, but in the process of pattern matching (parts of) <pattern> may be evaluated several times. This is the case with function calls, atoms with a "!" flag and all right hand sides of the "&" operator. The use of the involved binary operators ($ ' &) and flags (! !!) as "meta operators" does not restrict the range of matchable expressions in a serious way, as these operators and flags normally do not occur in evaluated subject expressions. The same is true for some other operators (: | _ and =). These operators, too, have a special meaning within patterns. All other binary operators occurring in a pattern are searched for in the subject expression as part of the pattern matching.

Especially the & | and : operators are helpful in formulating complex patterns with alternatives, conjunctions and side effects in the form of actions. In the following examples, !s stands for the subject expression, the expressions in parentheses are patterns and !p, !pa, !pb, etc. are sub-patterns therein. !a, !aa, etc. stands for an action (a part of the pattern that is conditionally evaluated).

>         !s:(!p&!a)

If !p matches successfully with !s, then !a is evaluated. If !a fails, the whole match fails. In more complex patterns, only part of the match might fail, resulting in backtracking and retry.

>         !s:(!pa|!pb)

If pattern !pa does not match with subject !s, then !pb is tried.

>         !s:(!pa:!pb)

If pattern !pa matches with !s, then pattern !pb is also tried. The next example combines these operators in a grammar-like expression:

>         !s:( !pa         & !aa       If either !pa, or !pb or both of !pc1 and !pc2
>            | !pb         & !ab       "fire", actions !aa, !ab and !ac, respectively
>            | (!pc1:!pc2) & !ac       are triggered.
>            )

Take care for the grouping of the : & and | operators : (!s:!pa):!pb and !s:(!pa:!pb) have, accidentally, the same effect, but the following expressions are very different :

>         (!s:!p)&!e
>      or  !s:!p&!e

If !s matches with !p, !e is returned.

>         !s:(!p&!a)

If !s matches with !p, !a is evaluated, but the expression as a whole returns !s.

>         (!s:!p)|!e
>      or !s:!p|!e

If !s matches with !p, !s is returned. Otherwise, !e is returned.

>         !s:(!pa|!pb)
>     If !s matches with either !pa or !pb (in that order), !s is returned.

The possibility that !s might fail further complicates the above examples.

Overview: Pattern matching .
Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Overview: Programming advice .
Previous about topic | "or else" .
Previous about topic & "and then" .
Previous about topic : match (left: subject, right: pattern) .
Next about topic : match (left: subject, right: pattern) .
Next about topic pattern matching .
Next about topic pattern matching .

# The grammar of Bracmat

Note: in long lists the "|" is left out.

>     <input>           ::= [<expression>] [;<input>]
>     <expression>      ::=   <white space> <expression> <white space>
>                           | [<flags>] ( <expression> )
>                           | <leaf>
>                           | <expression> <binop> <expression>
>     <leaf>            ::= [<flags>] <atom or nil>
>     <atom or nil>     ::= <atom> | <nil>
>     <atom>            ::= "<string>" | <string>
>     <string>          ::= <character> [<string>]
>     <character>       ::= any printable character except \ and " | <spec>
>     <spec>            ::= \a \b \t \n \v \f \r \" \\
>     <nil>             ::= ""   (or nothing at all, such as in "()")
>     <binop>           ::= = . , | & : <white space> + * ^ \L \D ' $ _
>     <flags>           ::= <flag> [<flags>]
>     <flag>            ::= ~ / # < > % @ ` ? ! !!
>     <white space>     ::= spaces, tabs, new line and form feed characters

White space (operator/cosmetic measure) almost never leads to confusion. It does in (some) cases where a <nil> leaf without flags is adjacent to the white space operator. For example : "get' out$now". Bracmat interprets this as : "get'(out$now)". "" or () fixes the problem : "get'() out$now". Quotation marks are not part of the string they surround. They should be used if necessary, e.g. "in this case" or "he{this is not a comment}re". Comments can be written everywhere, except in the middle of a string in Quotation marks. Comments are enclosed in {} and may be nested.

Overview: BRACMAT .

# Binary operators

overview over the 15 binary operators
algebraic operations
program flow
pattern matching
data structures
assignment
functions and macros
the dummy operator
Overview: BRACMAT .

# =.,|&: +*^LD'$_

These are, in order of growing priority, the 15 binary Bracmat operators.
= binds unevaluated expression (right) to name (left)
. "dotted pair" operator
, like ".", but with automatic alignment of elements into linear list
| "or else"
& "and then"
: match (left: subject, right: pattern)
[blank] (space, new line, tab) as ",", with associative access (backtracking)
+ addition
* multiplication
^ exponentiation
L logarithm
D differentiation
' function, macro
$ function, forced evaluation (e.g. in pattern)
_ (underscore) dummy operator (matches any operator)
Overview: Binary operators .

# The = operator

This operator assures that the right hand operator stays unevaluated. It is mainly used in the definition of pieces of code (e.g. functions). The code on the right is bound to the name on the left.
<atom>=<expression>
Each time when the value of <atom> is asked for, a fresh copy of <expression> is made available. <expression> itself is unchangeable and can only be wiped out by removing the binding between <expression> and its name, <atom>. This has, in turn, no influence on the copies made earlier.

>     {?} a=2    { create binding }
>     {?} !a:?b  { bind copy to b }
>     {?} !b     { show b's value }
>     {?} a=3    { remove a's binding to 2}
>     {?} !b     { show b's value }

There is a second way of using the = operator, with a slightly different syntax :
<nil>=<expression>
The = operator serves as a shock proof container for <expression>. The effect of evaluating this type of expression is almost the same as that of the macro instruction ()'<expression>. Indeed, after evaluating a macro instruction we have an expression with the <nil>=<expression> syntax.

>     {?} out$(b+a)
>     {?} out$(=b+a)
>     {?} out$('(b+a))
>     {?} c=3
>     {?} out$(=b+a+$c)
>     {?} out$('(b+a+$c))

Overview: =.,|&: +*^LD'$_ .
Next about topic = binds unevaluated expression (right) to name (left) .

# Objects

With the = and . operators you can construct and dereference conventional data structures and even objects with methods. In an expression, each subexpression with a = operator in the top node and an atom in the lhs of the top node indicates a field or object method that can be accessed and changed independently of other fields and methods, i.e. without the need to dissect and reassemble the whole expression. Such expressions are objects. An object member (a field or method) is addressed by using the lhs of the = operator as the member's name, preceded by the objects name. The name of the object and the name of the member must be separated by a dot operator. In the example below an object named "John" is created with the members "length", "age" and "name". The "name" member has two sub-members "first" and "family":

>     {?} John = (length = 180),(age = 30),(name = (first=John) (family=Bull))

There is no prescribed way in which the members should be glued together to form an object. Here, the comma operator and blank operator are used, but any operator but the = operator can be used to separate field names. John's length can be changed to 185 in the following ways:

>     {?} John.length = 185

or

>     {?} 185 : ?(John.length)

The same object can be assigned to another variable, creating an alias, but we have to take care not to evaluate John, because that would create or overwrite the variables "length", "age" and "name"):

>     {?} !John:?alias {Wrong}

>     {?} '$John : (=?alias) {Right}

Bracmat replaces the expression '$John by the value of John, protected against evaluation by a = operator. For that reason, the pattern on the rhs of the match operator : contains a = operator as well. Now we can change John's age by operating on the variable "alias":

>     {?} alias.age = 31

To see that the above expression indeed has the wanted (side-)effect, we can inspect John:

>     {?} lst$John
>      (John=
>        (length=180)
>      , (age=30)
>      , (name=(first=John) (family=Bull)));

Alternatively, we can also just show the field "age" in John:

>     {?} !(John.age)
>     {!} 31

It is also possible to create an alias for a sub-object. Taking the previous example, we could create an alias for the name member:

>     {?} '$(John.name):(=?nm)

Now assign a new family name:

>     {?} Flinter:?(nm.family)
>     {?} lst$John
>      (John=
>        (length=180)
>      , (age=30)
>      , (name=(first=John) (family=Flinter)));

Using an alias for a sub-object can save some code and processing time if the sub-object is accessed many times. Without the alias for John's name, we can change his family name in this way:

>     {?} Flinter:?(John.name.family)

It is valid to have an empty name for a member:

>     {?} x=(header=blabla) (=(a=1) (b=2))

Here, a and b are fields in a "nameless" sub-object of x. We can ask for the value of b:

>     {?} !(x..b)
>     {!} 2

To retrieve the whole sub-object:

>     {?} '$(x.):(=?sub-object)
>     {?} lst$sub-object
>      (sub-object=
>      (a=1) (b=2));

An alias can also be created for part of an object:

>     {?} x=(a=) (b=) (c=) (d=)
>     {?} '$x:(=(a=) ?alias (d=))

Now 'alias' only shares the members x.b and x.c with x. The same result follows from

>     {?} '$x:(=? ((b=) (c=):?alias) ?)

Objects can be composed to form new objects containing the union of the members of the contributing objects:

>     {?} x=(a=) (b=)
>     {?} '((p=) ($x) (q=)):(=?r)

Sometimes it is almost inevitable not to evaluate an expression that contains '=' operators that are meant to enable side effects, for example in a list of 'records' in a 'database'. One has to take care of the following: First suppose that the database x (containing one record with one field) is unevaluated (A):

>     {?} x=(=)
>     {?} !x:?y
>     {?} !x:?z

Now x, y and z are different objects.

>     {?} !x:?y:?z

Now y and z are the same object, but still different from x. It follows that changes made to y or z do not affect the database at all.

Now suppose that x IS evaluated (B):

>     {?} (=):?x
>     {?} !x:?y
>     {?} !x:?z

Now x, y and z are the same object.
Explanation: in (A) the value of x is not evaluated, especially the lhs of the '=' operator. Therefore, a new '=' node is created each time x is evaluated. In (B), the value of x IS evaluated, so no new copies of the '=' node are made.

Overview: =.,|&: +*^LD'$_ .
Overview: Programming advice .
Overview: BRACMAT .
Previous about topic = binds unevaluated expression (right) to name (left) .
Previous about topic . "dotted pair" operator .
Previous about topic data structures .
Next about topic = binds unevaluated expression (right) to name (left) .

# Assignment to variables

There are two forms of assignment to a variable:
<variable> = <expression>
<variable> must evaluate to an atom. <expression> is not evaluated.
<expression> : ?<variable>
<expression> is evaluated before assignment takes place.
<variable> must be an atom.
The = operator is mainly used to bind (still) unevaluated expressions to variables (patterns, but above all functions and routines). Assignment with the ":" makes use of pattern matching with a universally unifying pattern. This way of assignment is very powerful and can even be used to assign unevaluated expressions, by preceding the subject with an = or an ' operator.

>     {?} car=.!arg:(?%arg ?)&!arg   { one may freely reuse arg ! }
>     {?} (=(.!arg:(?%arg ?)&!arg)):?car { another way to define car }
>     {?} car$(one two three)
>     {?} (four five six):(?`%first ?rem) {"`": 0 of 1, "%": 1 or more, together 1}
>     {?} The first element is !first and the remainder is !rem.

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Previous about topic = binds unevaluated expression (right) to name (left) .
Next about topic : match (left: subject, right: pattern) .

# Construction of data structures

In Bracmat linear lists can be made by separating the elements with any binary operator, but most usual are the comma, plus sign, asterisk and space. These four operators do not lend themselves to forming other structures than linear lists. In addition, the plus sign and the asterisk don't preserve the order of the elements under addition of new elements. With the dot any tree structure can be built. Which operator one should use depends on the following considerations :

- Space and comma offer automatic concatenation of lists, but are slower than the dot.
- Space is more apt in searching algorithms, as this operator allows back- tracking, but it is slower than the comma.
- The comma is used in linear lists that are accessed recursively and in record-like structures, where the elements must have absolute positions.
- The dot should be used to separate function parameters if the actual parameters may contain any kind of operators. (You can't pass two comma separated lists to a function if these parameters are themselves separated by a comma, as the two parameters are concatenated to one single comma separated list.)
- The plus and the asterisk should only be used in formulae.

Examples :

>     {?} x=a.b.c
>     {?} y=p.q
>     {?} !x.!y
>     {?} x=a b c
>     {?} y=p q
>     {?} !x !y

{?} rotate=car,cdr.!arg:(?car,?cdr) & (!cdr,!car)

>     {?} rotate$(one,two,three,four)
>     {?} rotate$((one,two),(three,four))   { stop! }

By combining dots, commas and spaces, one may build any tree-like data structure that, thanks to the backtracking mechanism on space-separated lists, make the formulation of queries (goals) almost as easy as in Prolog. This is an example of a simple database, in which each row starts with a descriptor field, followed by a varying number of similar fields.

>     {?} M=((odd      ,1 3 5 7 9)
>            (even     ,0 2 4 6 8)
>            (prime    ,2 3 5 7)
>           )

We choose the space operator to form the backbone of the lists of numbers, because we want to access these numbers associatively, by using the back- tracking mechanism.

Let us formulate a query that searches for all numbers that occur in two or more categories (odd, even, prime). The findings are to be printed to the screen.

>     {?} (!M:(?                            { skip 0 or more rows ---               }
>              (?c1,?row)                   { ---fetch (number type, number row)---  }
>              ?                            { ---skip 0 or more rows ---            }
>              (?c2,                        { ---fetch another number type,...      }
>                ?                          { ...skip 0 or more numbers...          }
>                (?`%el                     { ...fetch a number...                  }
>                  & !row : ? !el ?         { does number occur in earlier row ?    }
>                  & out$(!el is both !c1 and !c2){ yes?  show                      }
>                  & ~                      { not satisfied yet: fail and backtrack }
>                )
>                ?                          { ...skip rest of numbers---            }
>              )
>              ?                            { ---skip rest of rows                  }
>             )
>         )

Experimentation with the implementation of matrices in Bracmat has learned that lists (of lists (of lists..)) lead to smaller and faster programs than arrays, artificially made multidimensional by playing with the index. A drawback of the list approach is its unconventionality. Much time has to be spend in reformulating existing algorithms based on indices. On the other hand, the list approach is essentially insensitive to the dimensionality of the matrix at hand, and may even be indifferent to the number of indices.

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Overview: Programming advice .
Overview: BRACMAT .
Next about topic . "dotted pair" operator .
Next about topic data structures .

# Binary operators in program flow

>     <exprA> & <exprB>  ("<exprA> and then <exprB>")
>     <exprB> is only evaluated if <exprA> succeeds,

>     <exprA> | <exprB>  ("<exprA> or else <exprB>")

<exprB> is only evaluated if <exprA> does not succeed.
In both cases <exprA> is always evaluated and <exprB> conditionally. If <exprB> is to be evaluated, <exprA> and the & or | operator have served their purpose. Therefore, they are eliminated before <exprB> is evaluated. In this way, the program stack doesn't grow indefinitely when recursive calls are made from the right hand side of any & or | operator occurring in an expression . Even a conventional sequence of instructions (where the success or failure of the evaluations of each instruction do not matter) can make use of this tail recursion optimisation. In that case one uses the pacifier (short cut flag) ` .

>     (`!a & !b)     !b is always evaluated. (sequence)
>     (`!a | !b)     !b is not evaluated. (useless in this form)

The pacifier or shortcut flag is inherited by higher levels, it percolates towards operators that are closer to the root of the tree, until it is subsumed in situations like the above ones.

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Next about topic | "or else" .
Next about topic & "and then" .
Next about topic program flow .

# Program flow

Most binary operators are used in expressions that "flow on their own" or "flow not at all". In the first group are the arithmetic operators, in the second is the dot-operator. In between are the two other structuring operators, comma and white space. Branching to a function is done with the $ and ' operators :

>     a $ b (or a'b)       "evaluate function a with argument b"

Branching without argument passing and local variables is done with the unary operator (flag) ! :

>     !X                   "do subroutine X"

but often this flag and its cousin !! are used for the purpose of variable expansion, it just depends on whether a variable is bound to an unevaluated or to an evaluated expression :

>     !X                   "expand X"
>     !!Y                  "expand expansion of Y" (two !'s is the maximum)

Conditional evaluation is decided by the success or failure of subexpressions. Every (sub)expression has two kinds of value: a visible value and a success(S)/failure(F)/ignore(I) value. Success and failure are primarily decided by the low level functions in the interpreter. The ignore value is generated if a failing expression is back-quoted. The & and | operators are sensitive to the S/F/I value of the left operand (where I counts as S). Often this left operand is a matching expression.

>     !a & !b              "if !a succeeds do !b"
>     !a | !b              "if !a fails do !b"
>     !subject : !pattern  "try to prove that !pattern describes !subject"

The back quote ` can be used to overrule the failure of a subexpression. The tilde ~ negates failure and success.

>     `!p & !q             "do !p and then do !q"
>     !a:!p & `!b | !c     "if !a matches !p do !b else do !c"
>     ~!a                  "succeed if !a fails and fail if !a succeeds"

Overview: =.,|&: +*^LD'$_ .
Overview: Programming advice .
Previous about topic | "or else" .
Previous about topic & "and then" .
Next about topic | "or else" .
Next about topic & "and then" .
Next about topic program flow .

# Algebraic operations

>     <term> + <term>        addition
>     <factor> * <factor>     multiplication
>     <base> ^ <exponent>     exponentiation
>     <base> \L <expr>        logarithm
>     <variable> \D <expr>    differentiation

Subtraction and division are treated as special forms of addition and multiplication. Therefore there are no binary operators for subtraction and division. (The minus sign - and the slash / can be used in numbers, however.) If one operand of an algebraic operator is evaluated then the other one is normally evaluated as well, even if this may seem unnecessary (multiplication by 0). This is done to ensure that all side effects take place as intended. However, if an operand fails to evaluate then the algebraic expression fails too and if the failing operand is the left hand side of the expression, then the right hand side is not evaluated. In this sense algebraic operators behave like the logical & operator.

Bracmat gives the user practically NO control over the format of evaluated algebraic expressions, such as the order of terms or factors. Bracmat tries to present algebraic objects in a unique (canonical) form. This is in many cases an unattainable goal : the forms (a+b)*(c+d) and a*c+a*d+b*c+b*d are both stable expressions. On the other hand, (a+b)*(c+d)+e becomes e+a*c+a*d+b*c+b*d. Bracmat keeps "expensive" completely factorised expressions, but does not automatically factorise factorisable expressions. Another domain of duality are expressions with logarithms. Sums and products start with rational numbers, followed by pi, i and e (if present, that is). Then follow other terms and factors. It is recommended not to assume anything about the ordering of these terms and factors, as this may change in later versions of the program.

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .

# function evaluation

The binary operators $ and ' are similar in most respects. In general, the left operand evaluates to the name of a built-in or defined function, whereas the right operand is an expression that is passed as an argument to the function. The $ evaluates the right operand before it is passed over, the ' doesn't. Parameter passing is by value, although the implementation postpones and limits copying of data as much as possible. In the code of the called function, the passed argument is bound to a local variable that is always called arg. Most often, the left operand of the $ and the ' operator evaluates to an alfa- numeric name. There are a few special function names:

- No name at all. Here, the $ and the ' operator have decidedly different and complementary roles. (Forced evaluation of subexpressions in otherwise unevaluated expressions, such as patterns)
- An integral number. (Array indexing.)
- Only flags. (Flag pasting or influencing success and failure of non-atomic expressions.)

Function calls are even effective in patterns, as it is fair to assume that the $ and ' operators seldom occur in subjects and so need not to be matched (the same is, a fortiori, true for the & and | operators). In patterns, the return value of a function is part of the pattern. A function may be called several times during one evaluation of a matching expression, due to backtracking and retrying.

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Overview: functions .
Next about topic functions and macros .
Next about topic function evaluation .

# The dummy operator "_"

Bracmat has only 1 "variable" that binds to a binary operator, the "_" operator. Worse even, this variable is global. Nevertheless this variable is most useful in definitions of certain types of recursive functions ("tree walkers"). The assignment of a new value to the "_" variable can only take place in a match. A "_" in a pattern is always "receiving", whereas a "_" outside a pattern is either "giving" or left unchanged. Try this :

>     {?} a_b             { This has unpredictable results. }
>     {?} x^y:?_? & a_b   { _ gets bound to ^. Thus a_b evaluates to a^b }

A "_" is evaluated by the expression evaluator, but also by the macro evaluator. The latter is useful if the "_" has matched an operator that is very volatile, such as "&" and "|".

>     {?} (=!a:!b&!c):(=?left_?right) {match the "&"}
>     {?} '_
>     {!} =&              { It worked, the "_" is replaced by a "&". }
>     {?} get$(str$('_),MEM,VAP):"=" ?op & !op { "freeze" and slice }
>     {!} &               { The operator is immobilised in a string. }

The "_" variable is always expanded BEFORE the left and right hand side operands are evaluated. That explains why new assignments in the operands do not result in unwanted side effects in the upper node with the "_".

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Next about topic _ (underscore) dummy operator (matches any operator) .
Next about topic the dummy operator .

# Recursion and the "_"-operator

In Bracmat functions are allowed to call themselves. Often this happens if a the function's argument is split into a left subtree and a right subtree and the function is called with each subtree in turn as its argument. If the operator in between the subtrees is unknown, it is time consuming to try all patterns ?+? ?*? ?$? ?'? etc. The _ operator circumvents this problem. It is a dummy operator that matches any other operator and expands to the operator with which it matched last time. Thereby preceding matches are "forgotten" : the _ operator is a global variable.

>     {?} reverse=l,r
>       .
>             (!arg:?l_?r)              { If arg is a compound expression ...}
>           & (reverse$!r)_(reverse$!l) { ... swap the reversed operands. }
>         | !arg                        { Let atoms as they are. }
>     {?} reverse$(Bill loves sweet Nancy. This is true)

Overview: =.,|&: +*^LD'$_ .
Overview: Binary operators .
Overview: functions .
Previous about topic _ (underscore) dummy operator (matches any operator) .
Previous about topic the dummy operator .
Previous about topic defining functions .

# Some often used control structures

Sequence :
-----------

>        (pseudo code)                             (Bracmat)

>     a; b;                                  `!a & !b { !b must be evaluated,
>                                                       even if !a fails }

Repetition :
-----------

>     WHILE a DO b;                           while = !a & `!b & !while;
>                                             ~!while;{ if !a fails, then !while
>                                                       fails, but ~!while succeeds }

>     DO b WHILE a;                           do = `!b & !a & !do;
>                                             ~!do; { see remark above }

>     DO b UNTIL a;                           do = `!b & ~!a & !do;
>                                             ~!do;

>     FOR i := m TO n DO b;                   for = !i:>!n | `!b & 1+!i:?i & !for;
>                                             !m:?i & !for;

Selection :
-----------

>        (pseudo code)                             (Bracmat)

>      IF a THEN b ELSE c;                    !a & `!b | !c;

>      v := IF a THEN b ELSE c;               (!a & `!b | `!c) : ?v
>                                            { works even if !c fails }

>      SELECT  a                              !a : (!c1 & `!b1 | !c2 & `!b2 |? & !bx);
>      WHEN  c1 : b1
>      WHEN  c2 : b2
>      OTHERWISE  bx;                        { the ? matches anything }

branching :
------------------------------

>        (pseudo code)                             (Bracmat)

>     CALL a;                                !a;
>     CALL b(x,y,z);                         b$(x,y,z);
>     v := b(x,y,z);                         b$(x,y,z) : ?v;

Overview: Binary operators .
Overview: Programming advice .
Previous about topic program flow .
Previous about topic program flow .

# The "nameless" functions $<expression> and '<expression>

These functions play complementary roles.
Depending on the context, $<expression> can have two effects : In the context of a pattern, which is a largely unevaluated expression, $<expression> forces an evaluation of <expression> before the match goes on. The evaluated <expression> thereby becomes part of the pattern (without the $ operator). This is repeated on every retry after backtracking. In the following example, a list of numbers is searched for two numbers that are followed by a third number that is the sum of the first two:

>     {?} 41 2 5 8 1 23 12 11 19 : ? `%?A ? `%?B ? ()$(!A+!B) ?

Notice that !A+!B is re-evaluated after each mismatch of the sub-pattern ()$(!A+!B). This can be used to count the number of trials (do the same without the ` flags !!):

>     {?} 0:?count
>     {?} 41 2 5 8 1 23 12 11 19 : ? `%?A ? `%?B ? ()$(!count+1:?count & !A+!B) ?
>     {?} found !A and !B after !count trials

The other context is in a macro. Macro's are mainly used to selectively replace late binding by early binding and may thereby improve performance. In Bracmat, a macro has the general form '<expression>. When '<expression> is evaluated, <expression> is searched for sub-expressions of the form $<atom> or $(<object>). Such a sub-expression is replaced by the binding of <atom> or
<object> (if it has any).
Replacements and sub-expressions of the form '<sub-expression> are not scanned. After macro substitution has taken place, what remains is an expression of the form =<expression>. The = operator is a safeguard against evaluation of
<expression>. The = operator is not seen in pattern-matching.
Macro substitution makes it possible to dynamically create unevaluated code and bind it to a variable.

>     {?} '($cat):?my-cat-var
>     {?} !my-cat-var$(Hello world)
>     {?} '($cat):(=?my-cat-alias)
>     {?} my-cat-alias$(Hello world)

Pattern matching can sometimes be made more efficient by using macro substitution, but the resulting code is harder to understand:

>     {?} 0:?count

>     {?} 41 3 5 7 6 23 12 11 19 : ? `%?A ? (`%?B  {Each number pair [A,B] ... }
>     {is added only once, giving C.   }    & !A+!B:?C
>     {C's value is hard-coded into rem}    & '(? ()$(!count+1:?count & $C) ?) : ?rem
>     {which is the remaining pattern. }    ) !rem

>     {?} found !A and !B after !count trials

In the same way, function code can be pieced together before it is ever executed.

>     {?} ((!power : two & (=!arg^2)) | (=!arg^3)) : ?abc       {If power="two",
>         abc is bound to !arg^2 (unevaluated). Otherwise, abc is bound to !arg^3.}
>     {?} '(.!arg + -1*$abc + 2) : ?poly {"poly" is the name of a new function
>         that will return a value that depends on the current value of arg
>         and on the value of power at the time when abc got its binding.}
>     {?} lst$poly { show poly's definition }

The macro construct '<expr> is useful if an expression has to be executed many times while parts of it remain constant, for example in nested loops: Without macro construct (5 X 5 multiplication table) :

>     {?} 0 : ?m                    { initialise counter of outer loop }
>     {?} (outer = 1+!m : <6 : ?m   { code for outer loop : }
>                 & put$\n          { start output on new line }
>                 & 0 : ?n          { initialise counter of inner loop }
>                 & `!inner         { execute inner loop }
>                 & !outer)         { loop }
>     {?} (inner = 1+!n : <6 : ?n   { code for inner loop : }
>                & put$(!m X !n "=" !m*!n ", ")
>                                   { the same !m is expanded 10 times }
>                & !inner)          { loop }
>     {?} !outer

With macro construct :

>     {?} 0:?m
>     {?} (outer = 1+!m : <6 : ?m
>                 & '( 1+!n : <6 : ?n
>                    & put$($m X !n "=" ()$m*!n ",")
>                                   { !m is expanded only 2 times }
>                    & !inner
>                    ) : ?inner     { at each pass through the outer loop
>                                     the inner loop "inner" is defined anew }
>                 & put$\n
>                 & 0 : ?n
>                 & `!inner
>                 & !outer)
>     {?} !outer

Overview: Binary operators .
Overview: functions .
Previous about topic functions and macros .
Previous about topic function evaluation .

# Flags

program flow
pattern matching
flags combined with expressions
unary operators
Overview: BRACMAT .

# Flags and program flow

Unlike other programming languages, Bracmat does not return the value of a variable or object member if we type its name. In Bracmat, variables and object members have to be told explicitly that we want their value, not their name. This is achieved with the ! and the !! flags in front of the variable name or object member name. !<atom> is replaced by the binding of <atom> !!<atom> is replaced by the binding of the binding (after evaluation) of <atom> Likewise !(<object name>.<member name>) is replaced by the binding of <object name>.<member name> Bindings can be evaluated or unevaluated. In the last case, the next step after expansion is the evaluation of the binding, unless expansion took place within a pattern.

>     {?} 2+3:?four     { bind 5 to "four" }
>     {?} !four         { evaluation has already taken place when four is expanded }

>     {?} 5=2+!four     { numbers are legal names ! 5 is bound to 2 + !four}
>     {?} !5            { evaluation takes place immediately after expansion }

>     {?} sum=%+%       { define pattern "sum" }
>     {?} a+b+c:!sum    { is a+b+c a sum? After expansion, %+% is not evaluated }

The !! flag is not used as often as the single !, but comes in handy if you want to pass a variable by name instead of by value.

>     {?} (check=one,two,criterion
>           .     !arg:(?one,?criterion,?two)
>               & !!criterion
>               & TRUE
>             | FALSE
>         )
>     {?} is-greater-than = !one:>!two
>     {?} is-divisor-of = (div$(!two,!one)*!one):!two
>     {?} check$(3,is-greater-than,15)  { pass by name }
>     {?} check$(3,is-divisor-of,15)

Passing by name is used here to postpone the evaluation of the second argument until it has arrived in the function check and the local variables "one" and "two" have been bound to the first and the third arguments, respectively.

Postponement of evaluation can also be achieved with the = and the ' operators.

>     {?} (chack=one,two,criterion
>           .    !arg:(?one,?criterion,?two)
>              & !criterion
>              & TRUE
>            | FALSE
>         )
>     {?} is-greater-than == !one:>!two                  { an extra = }
>     {?} is-divisor-of ='((div$(!two,!one)*!one):!two)  { an extra ' }
>     {?} chack$(3,!is-greater-than,15)  { pass by value }
>     {?} chack$(3,!is-divisor-of,15)

Overview: Flags .

# Flags and pattern matching

In patterns, atoms and expressions within parentheses may be preceded by flags that

>                control the matching process.

>     ?          unifies with anything. If ? is followed by a non-nil atom denoting
>                a variable or an expression denoting a member of an object, then the
>                matched part of the subject is captured by this variable or member.
>                In other words, pattern matching can have assignment as a
>                side-effect.
>     ! and !!   in front of an non-nil atom or an expression denoting a member of an
>                object causes expansion of the atom or the member to its direct or
>                indirect binding. This binding is matched with the subject.
>     #          unifies only with rational numbers.
>     /          unifies only with non-integer rational numbers.
>     < and >    unifies only with atoms that are "less" or "greater" than the
>                atom following the < or > flag.
>     @          unifies only with atoms.
>     `          causes backtracking if the pattern did not successfully unify with
>                a non-trivial element of the subject-list. A list is an expression
>                consisting of terms (+ operator), factors (* operator) or words
>                (white-space operator). Trivial elements are 0 in a sum, 1 in a
>                product and a word without characters in a list of words. In non-
>                sophisticated patterns, ` means simply : unify with at most one non-
>                trivial element. Zero non-trivial elements are allowed, in which
>                case unification takes place with an implicit trivial element :
>                Bracmat sees 0's everywhere in a sum, 1's in a product and zerolength
>                words in a sentence.
>     %          causes the match to succeed only with 1 or more non-trivial elements
>                of the subject-list.
>     ~          constrains the match to subjects that are not equal to the atom
>                following the ~ flag.

The above flags may be combined. The ordering in which they are input by the user is irrelevant; Bracmat keeps flags in this order : ~ / # < > % @ ` ? ! !! Repeating flags in front of the same atom does not convey a new meaning to the pattern, except for the ! and the ~ flags. More than one ! is interpreted as the !! flag. An odd number of ~ is treated as a single ~, an even number thereof is treated as none. A ~ in front of other flags negates the first of them. The most useful combinations are :

>     ?!         in front of an atom causes the atom to be expanded to its binding.
>                This binding is treated as a variable name.
>     ?!!        is like ?!, but expands two levels deep (with an evaluation of the
>                first level expansion), instead of one.
>     <>         is like a solitary ~.
>     /<>5/6     unifies only with non-integer rational numbers unequal to 5/6.
>     ~<         means "greater or equal" ("not less").
>     ~>         means "less or equal".
>     ~#         does not unify with rational numbers.
>     ~/         does not unify with non-integer rational numbers.
>     ~/#        unifies only with integer numbers.
>     ~/#<9      unifies only with integer numbers less than 9.
>     ~/#<>0     unifies only with non-zero integer numbers.
>     ~@         unifies only with non-atomic expressions.
>     ~`         backtrack immediately.

Many of these combinations can be combined further, e.g. ~/#?!! accepts only an integer number and binds it to the indirect binding of the atom following the flags.

If you want to match pattern !pat one or more times (in the literature, this is often written as {pat}+ ), use the complex pattern (? !pat|`). Likewise, if you want to match !pat zero or more times ( {pat}* ), use (|? !pat|`). These patterns should not be the last sub-pattern, because their correct working depends on repeated backtracking from following sub-patterns. In the last resort, you can add a pattern like () or (&) or (|) or (:), which match with an empty list only (assuming that the connecting nodes are spaces, otherwise use 0 in the case of a sum and 1 in the case of a product). Example:

>     {?} a a a c c:(? a|`) (|? b|`) (? c|`) (&) { {a}+ {b}* {c}+ }

Overview: Flags .
Overview: Programming advice .
Previous about topic flags combined with expressions .
Previous about topic pattern matching .

# <flags>$<expression> and <flags>'<expression>

Functions that have only flags as their function name can have two effects : Most flags (/ # @ % < > ?) are added to the flags of the function argument. The enriched argument is passed back as the function's return value. The function named ~ negates success and failure of its argument, which is passed back. In the same way, the function named ` (back-quote) changes failure into "failure that is to be ignored and leaves program flow undisturbed, as if there was success" (outside patterns) or into "failure that cuts off further attempts at matching the failing subpattern and forces immediate backtracking to previous matches." (inside patterns). The ! and !! flags cannot occur as function names. A single ! evaluates to the answer to the last typed-in expression. A !! tries to expand this answer one step further.

>     {?} (!arg:(smaller,?number) & <'!number | >'!number):?pat
>         { Either "<!number" or ">!number" is bound to pat, postponing the
>           evaluation of !number until !pat is evaluated. }

>     {?} apple banana tomato grape orange : ?fruits { make a list of fruit names }
>     {?} ~$(!fruits : ? raspberry ?) & raspberry !fruits : ?fruits
>         { if "raspberry" is NOT in "fruits" then put it in front of the list.}
>         { this has the same effect as : }
>     {?} condition = !fruits : ? raspberry ?         { bind code to atom }
>     {?} ~!condition & raspberry !fruits : ?fruits   { test atom's failure }

As in every computer language, it's bad practice to use negation if there exists a readable and short alternative formulation. The above membership checking example has a shorter alternative without negation:

>     {?} !fruits : ? raspberry ?  |  raspberry !fruits : ?fruits
>         { "raspberry" is in "fruits" or else it is put in front of the list.}

Overview: Flags .
Overview: functions .
Next about topic flags combined with expressions .

# minus sign

The minus sign "-" has only its normal arithmetic meaning when used as an unary operator in front of a rational number or the imaginary number "i". If a product contains both a rational number and the number "i", the "i" takes precedence in accepting a minus sign:

>                        -7*i*a

>     is evaluated to    7*-i*a.

The advantage of having both "i" and "-i" becomes clear by considering the following:

>                        (-1*i)^1/3

>     evaluates to       (-i)^1/3,

which is written as -i^1/3. As expected, this is the complex conjugate of

>                         i^1/3.

If Bracmat did not have a separate representation for -i, then

>                        (-1*i)^1/3
>     would evaluate to  i,

(because i^3 is equal to -i),which means that Bracmat would not consider (-1*i)^1/3 and i^1/3 as complex conjugates. The transcendental numbers e and pi do not accept arithmetic minus signs.

Overview: Flags .

# strings or atoms

A string in Bracmat is the same as an "atom". If you envisage a Bracmat expression as a tree like structure, atoms or strings are to be found in the leafs. In Bracmat terminology, an empty leaf is syntactically represented by <nil>. <nil> is not an <atom> proper, but an <atom or nil>. So not every leaf contains an atom. On the other hand, leafs may contain other things besides <atoms>, such as flags. In Bracmat, atoms are less accessible than trees. Therefore there are some ways to convert atoms to trees and back.

1. Conversion between an atom and its constituent characters: - get$(<atom>,MEM,VAP) puts every character in the literal <atom> in its own leaf in a tree, which has space-operators in every node. - str$<tree> does more or less the inverse.
2. Conversion between an atom and executable Bracmat code: - get$(<atom>,MEM) literally "reads" an atom as though it is a file with Bracmat expressions. - lst$(<variable>,MEM) "writes" the expression that is bound to <variable> to an atom.

Atoms can be used as names for variables, functions, files, etc.. Often they are used as literals, such as mathematical symbols or text.

Most characters which the computer knows of can be members of an atom. Only the first seven characters in the ASCII character set are forbidden. These characters are used by the system. In most cases you don't need quotation marks in order to get a string of characters into an atom. You do need them if you want parentheses, operators or flags to be part of an atom. Some special characters have to be preceded by a back slash:

>     \a  attention (bell)
>     \b  backspace
>     \t  tab
>     \n  new line
>     \v  vertical tab
>     \f  form feed
>     \r  carriage return
>     \\  back slash
>     \"  double quote

If you precede a string with the flag @, then back slashes are treated as normal characters. E.g. sys$@"C:\dos\edit". In stead of the tab and new line characters above, you may enter tabs and new lines by pressing the tab and the return key, respectively.

Examples:

>     {?} this is a "tree" with\nsix leafs
>     {?} (this is a "tree" with
>           seven leafs)
>     {?} "this" has 4 characters and "" (nil) none
>     {?} "this is an \"atom\" with 36 characters"
>     {?} "this string\nno verb"
>     {?} "this string

no verb either"

>     {?} "if zero equals one, I hang up" = "1:0&get$(\")y\",MEM)"
>     {?} get$(!"if zero equals one, I hang up",MEM)

Overview: BRACMAT .

# Symbols

literals
variables
Overview: BRACMAT .

# Literals

In Bracmat, symbols have only literal meaning, unless we explicitly state that we want a symbol to behave like a programming variable. Contrary to most computer languages, Bracmat evaluates an expression with literals not by expanding these literals to their associated values (if they have any) and computing with these values until a result is obtained, but by rearranging and transforming the expression until a stable form is reached.

>     {?} a + a
>     {?} i*i
>     {?} e^(19/2*pi*i)

In Bracmat, the context of a symbol decides whether it is treated as a variable or as a literal. So it is not necessary to "kill" a variable in order to use its symbol as a literal, the two uses live peacefully together.

>     {?} i=2   { variable i is bound to the literal "2" }
>     {?} !i^2  { the associated value of i is squared }
>     {?} i^2   { the literal "i" (a special one, like "pi" and "e") is squared }
>     {?} 7 = prime { the variable 7 is bound to the literal "prime"}
>     {?} 7 is !7 { the symbol 7 is used as both a literal and a variable}

Overview: Symbols .

# Variables

Variables are represented by <atom>'s, but not all <atom>'s are variables. The context of a symbol determines whether it is a variable or not :

1. the left operand of the = operator, unless this operand has zero length.
2. the atom following the ! and !! flags
3. within a pattern, a non-zero length atom following the ? flag
4. the left operand of the $ and ' operators
5. the right operand of the $ operator in macro constructs (e.g. '(1+$a) ).

Overview: Symbols .

# The four evaluators

In Bracmat, a binary operator may have four different effects, depending on the context of the operator. For each of these contexts there is one evaluator. Of these four evaluators, the macro evaluator is relatively unimportant. The four evaluators are :

1. the expression evaluator, which takes care for the transformations of expressions.
2. the match evaluator, which handles the unification of pattern expressions with subject expressions.
3. the macro evaluator, which merely substitutes certain parts of an expression.
4. the archivist, which doesn't do anything but keeping expressions alive.

The expression evaluator is the first evaluator that a newly input expression is confronted with. If necessary, it delegates tasks to one of the other three evaluators. The match evaluator can only delegate tasks to the expression evaluator and to the archivist. The macro evaluator can only delegate tasks to the expression evaluator. The archivist doesn't delegate any tasks to other evaluators. The cross link is in most cases a binary operator. The exceptions to this rule are in the context of the match evaluator: some (combinations of) flags involve the expansion of a chain of variable bindings and all but the last subexpansion demand the expression evaluator. In the scheme below, you'll find the "current" evaluator in the left column and the successor evaluators in the top row. A cross link is represented by the relevant operator or flags. If the change of evaluator only applies to the left (right) operand of the cross link operator, the symbol "l" ("r") is used. If the transition depends on the left operand being <nil>, the symbol "n" is used.

>                 expression       match            macro            archivist
>     expression                   :r               n'r              =r 'r
>     match       &r $ 'l ?! !!                     n'r              =r 'r
>     macro       $r

archivist

Overview: BRACMAT .

# Programming advice

program flow
pattern matching
data structures
debugging
Overview: BRACMAT .

# Debugging

If a program written in the Bracmat language doesn't work properly, the same debugging protocol applies as with other programming languages :

- Test extensively, above all with absurd and trivial input, in order to locate the pain in the many limbs of your program code.
- Create watch points by inserting out$ instructions at sensible places (entry and exit points of functions, branches, before and after assignments).
- If you are in doubt whether Bracmat has interpreted your program in the way you intended, use lst$(<function-name>,<file-name>) and inspect the code that is output into <file-name>.
- Errors that are easily made are : - Forget that Bracmat may see trivial elements (0 terms, 1 factors, zero length words) at places where this is not what you intend. Are all % ` and @ flags in place? - Forget the grouping of operators. a b c : ?%x ?%y is grouped as (a b c):(?%x ?%y) , but a,b,c : ?%x,?%y is grouped as a,b,(c:?%x),?%y Remember that = and . have very low priorities, often making a pair of parentheses necessary. - A misconceived idea about the Bracmat's backtracking mechanism. Unlike other languages with backtracking capabilities, Bracmat does not offer suspend/resume cycles. An expression embodying alternatives does not successively produce each alternative on every evaluation.

Overview: Programming advice .
Next about topic debugging .

# using out$ as debugging aid

The best aid in finding out what a program does, is using the out$ function. The following code is part of a function that computes n! .

>       loop = !k+1 : ?k          { increment k }
>                   : <!n         { compare (old) k+1 with n; if not less, stop }
>            & !fac*!k : ?fac     { multiply fac with k }
>            & !loop              { repeat until k = n }

Outside patterns out$ is most easily used. Inside patterns, if you want to inspect a variable that has just been assigned a new value, you use the & operator to temporarily escape into the non-pattern world. If you want to add extra text to the output, remember that all of out$'s argument is returned.

>       loop = out$!k+1 : (?k & out$(k is !k)) {show k before and after increment}
>                       : <!n                  {but before comparison with n}
>            & out$("new fac is:" (!fac*!k:?fac)) {show fac after computation}
>            & out$(still need !n+-1*!k loops) {you don't always need quotation marks}
>            & !loop

Now an example that is faulty. The purpose is to find two equal words in a sentence. This expression succeeds, but finds nothing:

>       (He loves her and she loves him : (? ?a ? !a ?) & out$(!a is occurring twice))

Check what is unified with "? ?a". To do so, put a variable after the first "?" and insert an output action after each sub-pattern.

>       (He loves her and she loves him
>           : ((?x & out$(x is !x))   {output x after unification}
>             (?a & out$(a is !a))    {output a after unification}
>             ? !a ?)                 {the remainder of the pattern}
>           & out$(!a is occurring twice)
>       )

The program would have to backtrack several times until ?a was unified with "loves", but the match succeeds with ?a unified with the omnipresent zero length word. A % sign avoids this. A back quote ` helps speeding up, since it avoids multi-word assignments and forces immediate backtracking.

>       (He loves her and she loves him
>           : ((?x & out$(x is !x))  { Watch the number of words in ?x grow ... }
>             (%`?a & out$(a is !a)) { while ?a moves towards "loves". }
>             ? !a ?)                { There backtracking stops }
>           & out$(!a is occurring twice) { and the message is output. }
>       )

Overview: Programming advice .
Overview: Predefined functions .
Previous about topic debugging .
Previous about topic out output to screen .
Next about topic debugging .
Next about topic out output to screen .

# using dbg' as debugging aid

Some programming errors may be found with the built-in dbg function. The argument of the dbg function is evaluated with an internal debugging flag set. With this flag set, suspicious code is warned against. It is important that the argument is not evaluated before being passed to the dbg function.

Overview: Programming advice .
Overview: Predefined functions .
Previous about topic debugging .
Previous about topic out output to screen .

# functions

function evaluation
defining functions
nameless functions
flag functions
built-in functions
predefined, changeable functions
Overview: BRACMAT .

# <function name>=.<function body>

Definition of a function without explicit local variables. The function is called by
<function name>$<argument expression> or
<function name>'<argument expression> ,
depending on whether <argument expression> must be evaluated ($) or not (') before it is passed to the function in the always present local variable "arg". The returned value of a function is simply the function body after it has been evaluated.

>     {?} square=.!arg^2 {definition}
>     {?} square$5            {call}

Overview: functions .
Next about topic defining functions .

# <function name>=<var1> [,<var2>, ...].<function body>

Definition of a function with local variables <var1>,<var2>, etc. .

>     {?} swap = a,b            {declare local variables a and b}
>            .   (!arg:(?a,?b)) {dissect arg to find the "real" arguments}
>              & (!b,!a)        {swap and return}
>     {?} swap$(I think,I guess)

Local variables are dynamically scoped, which means that they are visible to functions called from within the function in which the variables are declared. It is possible to declare a function inside another function. Always declare the name of an embedded function as a local variable.

Overview: functions .
Previous about topic defining functions .
Next about topic defining functions .

# Built-in functions

access array element
alc allocate memory (low level)
asc convert character to internal representation
chr convert internal representation to character
dbg debugging aid
den denominator
div quotient
fil file I/O (low-level)
fre return allocated memory (low level)
get get input (from file,keyboard or memory)
lst list un-evaluated value of variable(s)
mem list existing variable names
mod remainder
new create new object as a copy of another object
pee get value from address (peek) (low level)
pok put value at address (poke) (low level)
put write output
ren rename file or directory or move file
sim similarity between two atoms
str stringize expression into atom
swi software interrupt (low level)
sys command line shell
tbl establish array size
Overview: functions .

# <index>$<array name>

<array name> and <index> should both evaluate to atoms. <array name> may be
preceded by flags, such as ? or !. Indexing starts at 0 and is done modulo(size-of-array). Negative values count from the upper end of the array. The chosen index remains in force until a new indexing function is evaluated.

>     {?} tbl$(array,4)              { declare array[0..3] }
>     {?} a-value : 2 $ ?array       { array[2] := a-value }
>     {?} array = another-value      { array[2] := another-value }
>     {?} !array : -1 $ ?array       { array[3] := another-value }
>     {?} 45 : 1$?array              { array[1] := 45 }
>     {?} 2'!array : 3'!array        { are array[2] and array[3] equal?
>                                      Notice use of ' instead of $. }

Overview: Built-in functions .

# alc$<number of bytes>

This function allocates memory and returns the starting address of the allocated memory, but crashes the program if not enough memory can be allocated. Access to memory that has been allocated in this way is by means of pee$ and pok$. Any allocated memory should at some time be returned to the memory heap with the function fre$.

>     {?} alc$1000:?p {allocate 1000 bytes and assign starting address to p}

Overview: Built-in functions .

# asc$<character>

asc$ returns the integer value that corresponds to the character according to the current table used by the operating system (e.g. an extended ASCII table).

>     {?} asc$"+" {return "ASCII" value of character +}

Overview: Built-in functions .

# chr$<value>

chr$ returns the character at location <value> in the current table of characters used by the operating system. (e.g. an extended ASCII table). chr$ fails if <value> equals 0.

>     {?} chr$255 {return the last character from the current table of characters
>                  (assuming a machine with 8-bit characters)}
>     {?} tolower=.
>         !arg:~<A:~>Z                  {If arg is in the range A-Z,}
>       & chr$(asc$!arg+-1*asc$A+asc$a) {then return its lower case equivalent,}

| !arg {else return arg unchanged.}
{(Works only correctly if the "distance" between lower and upper case
versions is the same for all characters in the range A-Z.)}

>     {?} tolower$G

Overview: Built-in functions .

# dbg'<expression>

Create warnings in situations that probably are programming errors. Currently, a warning is generated when a function definition can not be found.

>     {?} dbg'(foo$a)
>     {?} dbg'((myclass.yourfunc)$X)

Overview: Built-in functions .

# den$<rational number>

The denominator of <rational number> is returned. There is no built-in numerator extractor function.

>     {?} den$22/7
>     {?} num = .!arg*den$!arg { home-made numerator function }
>     {?} num$22/7
>     {?} den$sim$(,monkey)   { return length of word "monkey"}

Overview: Built-in functions .

# div$(<rational number>,<rational number>)

div$ returns the (integral) quotient of its arguments.

>     {?} div$(123/45,67/890)

Overview: Built-in functions .

# fil$([[<file name>][,<option>[,<number>[,<value to output>]]]])

fil$ is a multi-purpose low level I/O function.

>       (1) opening a file
>       fil$([<file name>],<mode>)

>     Option <mode> is one of the following :
>      r              open text file for reading
>      w              create text file for writing, or truncate to zero length
>      a              append; open text file or create for writing at eof
>      rb             open binary file for reading
>      wb             create binary file for writing, or truncate to zero length
>      ab             append; open binary file or create for writing at eof
>      "r+"           open text file for update (reading and writing)
>      "w+"           create text file for update, or truncate to zero length
>      "a+"           append; open text file or create for update, writing at eof

"r+b" or "rb+" open binary file for update (reading and writing)

>      "w+b" or "wb+" create binary file for update, or truncate to zero length
>      "a+b" or "ab+" append; open binary file or create for update, writing at eof

>       (2) Prepare for reading or writing fixed sized records
>       fil$([<file name>],<type>,<number>)

>     Option <type> is one of the following :
>      CHR  character or string I/O
>      DEC  number I/O

Option <number> must be a non-negative integer and determines the number of bytes that are read or written as one chunk during a future call to fil$. If <type> is "DEC", only values 1,2 and 4 are valid, corresponding to 1, 2 and 4 byte sized integers, respectively. Notice that 2 and 4 byte integers are not portable between implementations with different byte order.

>       (3) Prepare for reading variable sized record
>       fil$([<file name>],STR[,<stop>])

Option <stop> is a string of end-of-record characters. The default is "\n".

>       (4) Telling the position inside the file
>       fil$(<file name>,TEL)

returns the current value of the file position indicator.

>       (5) Go to file position
>       fil$(<file name>,<whence>,<offset>)

sets the current value of the file position indicator to an <offset> based on the value of <whence>. Option <whence> is one of the following :

>      SET  start of file
>      CUR  current file position
>      END  end of file. (In some implementations, binary files may not handle END).

For a text file, <offset> must be 0, or the value returned from a call to fil$(<file name>,TEL), in which case <whence> must be SET.

(6) Reading
fil$([<file name>][,,<number>])
reads (if <mode> permitting) <number> chunks of <size> bytes. When reading variable sized records (STR), fil$ returns a dot-separated list of two elements: the found end-of-line character and the read string (which does not contain the end-of-line character).

>     {?} fil$("mytext.txt","rb") { Open for reading in binary mode. }
>     {?} fil$(,STR)                  { Reading until end-of-line "\n".}
>     {?} fil$:(?stop.?line)          { Read the first line. }
>     {?} fil$(,SET,-1)               { Close the file. }

>       (7) Writing
>       fil$([<file name>],,<number>,<value>)

writes (if <mode> permitting) <number> chunks of <size> bytes from <value>. If <type> is "DEC", <number>*<size> must be 1,2 or 4. <value> must be an integer value and is cast to a binary number with at most <number>*<size>*8 digits. This number is stored in <number>*<size> bytes, which in turn are output. If <number> is greater than 1, the byte(s) with the least significant digits are output first. In machines with little-endian byte-order, only the product <number>*<size> matters. If <type> is "CHR" and the length of <value> is shorter than <number>*<size>,
<value> is padded with spaces (to the right).

>       (8) Closing the file
>       fil$([<file name>],SET,-1)

An open file is closed by specifying an impossible file position.

Overview: Built-in functions .

# fre$<memory address>

fre$ returns a chunk of memory to the memory pool (heap). The only valid parameter is a return value of alc$. Applying fre$ to a chunk of memory that was never allocated or that has been returned already results in undefined behaviour of the program.

>     {?} alc$1000:?p {allocate chunk of 1000 bytes from the memory pool}
>     {?} fre$!p      {return this chunk to the memory pool}

Overview: Built-in functions .

# get$(<atom or nil>[,MEM][,ECH][,VAP][,STR])

get$ reads and interprets characters in a string (internal memory) or file (external memory or keyboard). options :

>       MEM present  :The name of the first parameter is the source of the characters.
>                     (MEMory)
>           otherwise:A file with the name of the first parameter is the source.
>       ECH present  :The characters are echoed to the screen as they are read.
>           otherwise:No echo.
>       VAP present  :The characters are read "as is". Between the characters extra
>                     spaces are inserted.
>                     (VAPorised)
>           otherwise:No extra spaces are added.
>       STR present  :The characters are read into one string.
>           otherwise:The characters are interpreted as parts of a Bracmat expression
>                     and evaluated after the whole expression has been read.

The VAP option is evaluated before the STR option.

Applications :

>       get'(matrix,ECH)

Read file "matrix" and evaluate the expressions (delimited by semicolons) therein. If the system finds a syntax error in a multiple expression file, the ECH option makes it easier to locate the error.

>       get'(matrix,STR):?intern

Read file "matrix" into a string called "intern". If this file contains Bracmat instructions, they hereafter exist in a "sleeping" state in memory.

>       get$(!intern,MEM)

!intern is, in this example, expanded to an atom with a very long name, namely all of the text of file "matrix". The sleeping expressions are evaluated one after the other, just as if "get'matrix" was evaluated.

>       get'(,VAP):?space-list

Read characters from standard input (normally keyboard) until next line feed character. Put each character into an atom. Put all atoms into a linear list with space operators. Bind this list to the name "space-list".

>       get'(")y",MEM)

Read the sleeping "expression" ")y" from memory. The lexical scanner will find an unbalanced right parenthesis, which could mean that this Bracmat session should stop. The "y" confirms this assumption and the program will come to an end immediately. If the "y" hadn't been present, Bracmat would ask "end Bracmat session ? (y/n)" after which the user has to choose. This trick is useful in batch processing.

If the first parameter is <nil> or "stdin" and the MEM option is not used, input is coming from standard input. Take care for putting filenames in double quotes if they contain any characters that can be misunderstood, such as dots, (back) slashes or dollars.

Overview: Built-in functions .

# lst$(<variable>[,LIN])

Outputs all present bindings of one or more variables to standard output. If the first parameter is the zero-length string, then all variables with names starting with a character below ASCII 128 are shown. If a variable has more than one binding (arrays/stacks) then the current value is preceded by a ">"-sign. The second parameter is optional.

>     {?} lst$help      { shows this programme on screen,
>                         unless stdout has been redirected }
>     {?} lst$(tay,LIN) { listing without indentations of function tay$ }

Overview: Built-in functions .
Next about topic lst list un-evaluated value of variable(s) .

# option LIN

If LIN is not present, output is very much indented, sometimes making it more readable for humans. If LIN is present, output is as compact as possible.

Overview: Built-in functions .
Previous about topic lst list un-evaluated value of variable(s) .
Previous about topic put write output .
Next about topic lst list un-evaluated value of variable(s) .
Next about topic put write output .

# lst$(<variable>,MEM [,LIN])

The difference with the preceding form is, that "output" takes place to memory. What is normally visible on screen is put in one atom, which is the return value of the call to lst. It has the opposite effect of get$(<atom>,MEM). Use : compression of an expression to save space. If the compressed expression is needed, it is decompressed with get$. Compression is typically by a factor of about 5, but may be as large as 16. Expressions with very large atoms (such as this help function) do less well. Example:

>     {?} lst$(fct,MEM):?sleeping-fct
>     {?} tbl$(fct,0)   { remove function fct$ from memory }
>     {?} { .. celebrate space-saving, until fct$ is needed .. }
>     {?} get$(!sleeping-fct,MEM)

Overview: Built-in functions .
Previous about topic lst list un-evaluated value of variable(s) .
Next about topic lst list un-evaluated value of variable(s) .

# lst$(<variable>,<file name>,NEW | APP [,LIN])

This time, output is sent to the named file instead of standard output. The third argument is explained below. Code that has been saved with lst$ can be reloaded with get$.

>     {?} lst$(,"all",NEW,LIN)
>         { write all current code without indentations to file "all" }
>     {?} lst$(tay,taylor,NEW)
>         { save function tay$ to file "taylor" in indented format }

Overview: Built-in functions .
Previous about topic lst list un-evaluated value of variable(s) .
Next about topic lst list un-evaluated value of variable(s) .

# options NEW and APP

one of the options NEW and APP must be present : NEW tells the computer to open a new file or overwrite an old one. APP directs output to an existing file. If the file does not exist, it is
created first.

Overview: Built-in functions .
Previous about topic lst list un-evaluated value of variable(s) .
Previous about topic put write output .

# mem$[EXT]

mem$ produces a list of all currently existing variables, except those beginning with a character above ASCII 126. The EXT option adds information about the number of occurrences (array or stack size - 1) of those variables which have more than one occurrence and shows which of them is currently in focus (index into array: 0 .. size-1). The predefined function cat$ makes use of mem$.

>     {?} mem$
>     {?} mem$EXT

Overview: Built-in functions .

# mod$(<number>,<divisor>)

mod$ divides <number> by <divisor>. The rest is returned.

>     {?} mod$(22,7)

Overview: Built-in functions .

# new$<object> or new$(<object>,<args>)

new$ creates a shallow copy of an object and calls the method "new" of the new object, if there is one. With the second form, <args> is passed to the method "new". Example:

>     {?} (patient=
>       (name=(first=John),(last=Bull)) {name is a copy, first and last are not}
>       , (age=20)
>       , ( new
>         =
>           .   out$"hello world"
>             & new$(its.name):(=?(its.name)) {create fresh copies of first and last}
>             &   !arg
>               : (?(its.name.first).?(its.name.last).?(its.age))
>       ))
>     {?} new$(patient,(Albert.Keinstein.42)):?x
>     {?} new$(patient.name):(?Name)
>     {?} Alice:?(Name..first)
>     {?} new$(('$patient),(Albert.Keinstein.42)):?y {x and y are identical !}
>     {?} new$(=(a=1),(b=2)):?ab {"die" is called when ab is reassigned}
>     {?} 3:?(ab..a)
>     {?} new$(=(a=1),(b=2),(new=.),(die=.)):(=?cd) {"die" is called at once!}
>     {?} 3:?(cd.a)

When an object was created with the new$ function, an internal flag is set in the object telling the system that the "die" method must be called just before deletion of the object. The "die" method, like the "new" method, is optional and should be used to do clean-up.

Overview: Built-in functions .

# pee$(<address> [,<size>])

Depending on <size>, a 1, 2 or 4 byte sized integer allocated at <address> is returned.

2 and 4 byte integers may only start at addresses that are multiples of 2 and 4, respectively. <address> is lowered to the nearest allowable value, if needed. Notice that multi byte integers are stored differently in Little Endian (iAPx86, VAX, ARM) and Big Endian (MC680x0) machines. Many operating systems abort programs that try to access non-existent or protected memory areas.

{?} chr$pee$34567 {return value at address 34567 (1 byte) as a character}

>     {?} pee$(34567,2) {return value at address 34566 (2 bytes)}
>     {?} pee$(34567,4) {return value at address 34564 (4 bytes)}

Overview: Built-in functions .

# pok$(<address>,<value> [,<size>])

Depending on <size>, a 1, 2 or 4 byte sized integer is stored at <address>.

2 and 4 byte integers may only start at addresses that are multiples of 2 and 4, respectively. <address> is lowered to the nearest allowable value, if needed. Notice that multi byte integers are stored differently in Little Endian (iAPx86, VAX, ARM) and Big Endian (MC680x0) machines. Many operating systems abort programs that try to access non-existent or protected memory areas.

{?} pok$(34567,asc$K) {store the internal value of the character K at memory
location 34567 (as 1 byte)}

>     {?} pok$(34567,-1,4) {store 2^32-1 at memory location 34564
>                           (assuming 1-complement arithmetic)}

Overview: Built-in functions .

# put$(<expression>[,LIN])

Sends <expression> to standard output. The cursor is positioned after the last output character. The predefined function out$ does the same as put$, with the exception that it positions the cursor on the beginning of the next line.

>     {?} put$("b+a" is after evaluation b+a)

Overview: Built-in functions .
Next about topic put write output .

# put$(<expression>,MEM [,LIN])

<expression> is stringized and placed into an atom, which is the return
value of the call. This use of put$ is similar to the str$ function, but whereas str$ suppresses the space-operator, put$ transfers every character, including space-operators, to the atom.

>     {?} put$(this is not Lotus 1 1+1 1+1+1,MEM):?proposition &
>     {?} put$!proposition

Overview: Built-in functions .
Previous about topic put write output .
Next about topic put write output .

# put$(<expression>,<file name>,NEW | APP [,LIN])

Sent <expression> to the named file.

>     {?} put$(tay$(e^x,x,10),"e.out",APP)

Overview: Built-in functions .
Previous about topic put write output .
Next about topic put write output .

# ren$(<oldname>.<newname>)

Renames a file or directory or moves a file.
The ren$ function succeeds, unless a syntactic error was made. If there is an error at the operating system level, one of the following codes is returned:

>         EACCES
>             File or directory specified by newname already exists or could not be
>             created (invalid path); or oldname is a directory and newname specifies
>             a different path.

>         ENOENT
>             File or path specified by oldname not found.

>         EINVAL
>             Name contains invalid characters.

If the command succeeds at the operating system level, the value 0 is returned.

Overview: Built-in functions .

# sim$(<atom or nil>,<atom or nil>)

sim$ uses the Ratcliff/Obershelp pattern matching algorithm in establishing a measure of the similarity between its two (atomic) arguments. The returned value is an unsimplified fraction. The denominator is the sum of the numbers of characters in both arguments. The numerator is the total number of characters that have been matched successfully. Matching is case-insensitive.

>     {?} sim$(colour,Color)
>     {?} den$sim$(,"this is an easy way to find this string's length")
>     {?} div$(sim$("similarity rounded","and in procents")+1/200,1/100)

Overview: Built-in functions .

# str$<expression>

str$ "writes" <expression> into one single atom. All atoms, flags and operators, with the exception of the space-operator, are copied to the output string. Main use : pasting of two or more atoms.

>     {?} n=3
>     {?} str$(var !n) = seventeen
>     {?} out$(var3 is !var3)
>     {?} editfile = mytxts/story
>     {?} sys$str$("vi " !editfile)   { execute UNIX command "vi mytxts/story" }
>     {?} a=x+2*y;b=2*x+y
>     {?} put$str$(!a "+" !b " = " !a+!b)

Overview: Built-in functions .

# swi$(<interrupt number>.<input value>,[<input value>,...])

This function is the most operating-system-dependent function in Bracmat. Currently, it is implemented for RISC-OS (Archimedes) and 16-bit MS-DOS versions of Bracmat. All arguments must be integer values. The list of input values (registers r0 and upwards) need not be complete. Missing values are assumed to be zero. Blocks of memory should be passed by allocating memory with alc$ and passing the returned value. The returned value has the form (<error code>.<output value>,<output value>,...) An error code of 0 means that no error is reported. In the MS-DOS version, the input registers are AX,BX,CX,DX,BP,SI,DI,DS,ES and FLAGS, respectively.

{?} {RISC-OS only}

>     {?} putstr=(loop,c,buf,ret.        { goal:copy argument to memoryblock }
>           alc$(den$sim$(!arg,)+1):?buf:?ret { allocate block for string to fit }
>         & get$(!arg,MEM,VAP):?arg      { argument -> single characters }
>         & (loop = !arg:%?c ?arg & pok$(!buf.asc$!c.1) & !buf+1:?buf & !loop)
>         & ~!loop                       { poke each character into memory block }
>         & pok$(!buf.0.1)               { poke string-delimiting zero }
>         & !ret)                         { return pointer to block }
>     {?} putstr$"OS_EvaluateExpression":?inbuf { create pointer to string }
>     {?} 57:?"OS_SWINumberFromString"   { From manual }
>     {?} swi$(!"OS_SWINumberFromString".0,!inbuf):(?error.?nummer,?) { find
>          interrupt number corresponding with the string "OS_EvaluateExpression"}
>     {?} fre$!inbuf { deallocate block containing copy of input string }

{?} {MS-DOS only}

>     {?} gotoxy = (VIDEO,setCursorPosition,videoPage0.
>     {?}   16:?VIDEO                 { interrupt number 10H }
>     {?} & 2*256:?setCursorPosition  { AH }
>     {?} & 0*256:?videoPage0         { BH }
>     {?} & !arg:(?x,?y)              { DL and DH }
>     {?} & swi$(!VIDEO.!setCursorPosition,!videoPage0,0,!x+256*!y)
>     {?} )
>     {?} gotoxy$(0,0) & put$(top left corner)

Overview: Built-in functions .

# sys$<command line commando>

In most environments, sys$ passes its argument to the command line interpreter. Therefore, sys$ has a functionality that very much depends on the operating system in which Bracmat runs. One has to take care for memory limitations and the possibility that sys$ may never return. Possible uses are for example :

- instructions to the video display unit for cursor movement or graphics
- running another program, such as an editor
- manipulation of files (directory listing, copying, etc.)

The functions put$(<expression>,MEM) or str$<expression> may be used for constructing an argument for sys$ :

>     {?} file = bracmat.c
>     {?} !file:((?stem.?)|?stem) {remove file extension and put result in "stem"}
>     {?} sys$str$("copy " !file " " !stem.bak)

The sys$ function succeeds, unless a syntactic error was made. If there is an error at the operating system level, one of the following codes is returned:

>         E2BIG
>             Argument list (which is system-dependent) is too big.

>         ENOENT
>             Command interpreter cannot be found.

>         ENOEXEC
>             Command-interpreter file has invalid format and is not executable.

>         ENOMEM
>             Not enough memory is available to execute command; or available memory
>             has been corrupted; or invalid block exists, indicating that process
>             making call was not allocated properly.

If the command succeeds at the operating system level, the value 0 is returned.

Overview: Built-in functions .

# tbl$(<variable>,<array size>)

The named variable is (re-)sized to an array with <array size> elements. Resizing always affects the elements with the highest indexes first : shrinking means that the last elements are lost, expanding creates new zero-valued elements at the end. If <array-size> equals zero, the named variable ceases to exist in memory. This is the only way in Bracmat to get rid of global variables. Stacks and arrays are exactly the same thing in Bracmat. Therefore, it is not possible to declare arrays locally. Bracmat never accesses arrays as a whole; there is always just one element that is in focus. By issuing an instruction of the form <index>$<array name> or
<index>'<array name> you can explicitly tell Bracmat to put focus on some
element. Bracmat does this automatically in the case of pushing and popping local variables onto and from a stack.

>     {?} tbl$(bigarray,16000)
>     {?} lst$bigarray          { this may take a long time to execute }
>     {?} tbl$(bigarray,0)      { remove bigarray }
>     {?} lst$bigarray

Overview: Built-in functions .

# Predefined functions

Besides hard-coded built-in functions, Bracmat offers a number of soft-coded functions which behave as user defined functions in all respects. They are redefinable and removable, for example. Some functions are called by the interpreter itself and should never be changed by the user. Such functions have names that start with an 8-bit character with the high-bit set. Bracmat has been drilled to leave these names out when the user asks for a list of variable names (lst$ or mem$), so you will not notice their existence. The following visible functions are predefined:
abs (and sgn) absolute value and sign
cat list existing variable names selectively
cos (and sin) cosine and sine
ego (and goe) goniometric functions -> exponentials (and vice versa).
fct factorising
flt floating point notation of numbers
out output to screen
sub substitution
tay Taylor series
Overview: functions .

# abs$<expression> and sgn$<expression>

sgn$ determines the sign of the numerical factor of <expression>. If the sign is "-", then sgn returns -1. In all other cases the returned value is 1. abs$<expression> is defined as sgn$<expression>*<expression>.

>     {?} sgn$(-1*i)
>     {?} abs$(-7*a)

Overview: Predefined functions .

# cat$([<include list>][,[<exclude list>][,EXT]])

cat$ is like the built-in function mem$, but offers the possibility to exclude names that are not in the first parameter and/or to exclude names that are in the second parameter. The optional third parameter adds information about array size and current index value, e.g. (arg,5,5). If the first parameter is missing, this is taken to mean that NO names are excluded (unless by virtue of the second parameter). You can use cat$ to save the state of the variable space for later use, e.g. removing all variables that have been created since.

>     {?} cat$(,,EXT):?save-state  { mem$EXT is also OK. }
>     {?} newvar1=12345            { create new variables }
>     {?} tbl$(newvar2,100)
>     {?} cat$(,!save-state,EXT)   { show the newcomers }

Overview: Predefined functions .

# cos$<expression> and sin$<expression>

These functions produce cos(expression) and sin(expression), expressed in powers of e. In this way, expressions with goniometric functions can be differentiated and, sometimes, simplified.

Overview: Predefined functions .
Next about topic cos (and sin) cosine and sine .

# ego$<expression> and goe$<expression>

ego$ translates all occurrences of subexpressions of the form (sin.<expr>) by (sin$<expr>). In the same way, (cos.<expr>) is translated by (cos$<expr>). goe$<expression> translates powers of e into goniometric expressions, where sin(a) and cos(b) are represented by (sin.a) and (cos.b), respectively. goe$ and ego$ swap representations in opposite directions.

>     {?} goe$ego$((sin.x)^4+(cos.x)^4)
>     {?} goe$(x\Dego$(sin.x))
>     {?} goe$(x\D(ego$((sin.x)^4+(cos.x)^4)))

Overview: Predefined functions .
Previous about topic cos (and sin) cosine and sine .

# fct$<expression>

fct$ uses some heuristics in trying to factorise <expression>.

>     {?} 1+(2*a^3+6/7*t)*(3*x+4*y+z^-1)+-1:?sum
>     {?} fct$!sum

Overview: Predefined functions .

# flt$(<rational number>,<number of decimals>)

flt$ converts a rational number to a floating point presentation. The result is stored in an atom. This function is meant for output, Bracmat does not use floating point numbers itself.

>     {?} flt$(123/456,78)
>     {?} flt$(sub$(tay$(sin$x,x,40).x.11/7),12)

Overview: Predefined functions .

# out$<expression>

Uses the built-in function put$ to output <expression> to the output stream (usually the screen). Output is ended with a new line. Normally, out$ returns its argument. out$ is a good debugging tool, but put$ is slightly safer, as it handles failing arguments in the correct way, contrary to out$.

>     {?} put$a & put$b
>     {?} out$a & out$b

Overview: Predefined functions .
Next about topic out output to screen .

# sub$(<expression>.<pattern>.<replacement>)

substitution function
argument 1 : subject
argument 2 : pattern
argument 3 : replacement for subexpressions matched by pattern. Often, patterns and replacements have to be passed in unevaluated form. Therefore, it is wise to use the = or - less rigorously - the ' operator. The ego$ function uses sub$ in this way :

>     {?} (ego
>         = r
>           . sub$( sub$(!arg.(sin.?r).(=sin$!r)) { protection with = }
>                 . (cos.?r)
>                 . 'cos$!r            { alternative protection with ' }
>                 )
>         )

Overview: Predefined functions .

# tay$(<expression>,<variable>,<number of terms>)

A Taylor expansion is applied to <expression>.
The second argument is the independent variable.
The third argument denotes the number of terms, including vanishing terms.

>     {?} tay$((cos$x)^-1,x,20)

Overview: Predefined functions .

# Hash tables

If you need to manage a large data set it may be a good idea to use a hash- table instead of a list. Storing, retrieving and deleting are costly processes in lists, but cheap in hash tables. Handling hash tables in Bracmat is very simple. You create a hash table as follows

>     {?} new$hash:?myhash

Hereafter, 'myhash' refers to a hash table and is treated in the same way as a user defined object. The following methods are defined for hash tables:
find
insert
remove
New
Die
DOS
ISO
casesensitive
forall
Overview: BRACMAT .

# (myhash..find)$key:(?Key.?Value) ?OtherKeyValuePairs

Returns a blank-separated list of key-value pairs, all with the same key.

Overview: Hash tables .

# (myhash..insert)$(key.value)

Inserts the key Key with the value Value. Multiple values for the same key are possible and the same value can be inserted more than once for the same key.

Overview: Hash tables .

# (myhash..remove)$key:?KeyValuePairs

Removes the key with all its values and returns a blank-separated list of key-value pairs.

Overview: Hash tables .

# New

This is a method of the hash class that is called by the system when it evaluates 'new$hash'. It cannot be called from user code.

Overview: Hash tables .

# Die

This method is called when a hash object is deleted. It is not directly called from user code. (Compare with a C++ destructor). You can add your own clean up code by writing a 'die' method and adding it to a hash object once it is created. Example:

>     {?} new$hash:?myhash; { create a hash table myhash }
>     {?} ((
>         =   ( Insert                       { Add a method 'Insert' to myhash that
>                                              only allows one value per key. }
>             =   K,V
>               .     !arg:(?K.?V)
>                   & (Its..find)$!K:(?.?v)
>                   &   out
>                     $ ( str
>                       $ ( "Key "
>                           !K
>                           " already present"
>                           ( !V:!v&" with same"
>                           | ", but with different"
>                           )
>                           " value "
>                           !v
>                         )
>                       )
>                 | (Its..insert)$!arg
>             )
>             (die=.out$"Oh my dear")        { This method is called just before
>                                              the object is deleted. }
>         )
>       : (=?(myhash.)))

>     {?} (myhash..Insert)$(X.12);                { Insert the value 12 for key X. }
>     {?} (myhash..Insert)$(X.12);                { Try to do it one more time. }
>     {?} (myhash..Insert)$(X.10);                { Try to insert another value
>                                                   for the same key.}
>     {?} (myhash..insert)$(Z.1);                 { Use the built-in insert method.}
>     {?} (myhash..insert)$(Z.1);                 { Insert same value again. }
>     {?} (myhash..insert)$(Z.2);                 { Also insert a different value. }
>     {?} (myhash..find)$X;                       { Show all key-value pairs of X.
>                                                                  (only 1) }
>     {?} (myhash..find)$Z;                     { Show all key-value pairs of Z.(3)}
>     {?} (myhash..remove)$Z:?values;
>     {?} :?myhash;                               { Get rid of the hash table. }

Overview: Hash tables .

# (myhash..DOS)$

Make all key access case-insensitive and use DOS codepage 850.

Overview: Hash tables .

# (myhash..ISO)$

Make all key access case-insensitive and use the ISO table ISO8859.

Overview: Hash tables .

# (myhash..casesensitive)$

Make all key access case sensitive. This the default.

Overview: Hash tables .

# (myhash..forall)$<FunctionBody>

Apply the functionbody to all key-value pairs. Example:

>     {?} new$hash:?myhash; { create a hash table myhash }
>     {?} (myhash..insert)$(X.12);                { Insert the value 12 for key X. }
>     {?} (myhash..insert)$(Z.1);                 { Use the built-in insert method.}
>     {?} ( (myhash..forall)                      { Output all key-value pairs. }
>         $ (
>           =   Key,Value,loop
>             .   ( loop
>                 =   !arg:(?Key.?Value) ?arg
>                   & out$(str$("Key=" !Key  "Value=" !Value))
>                   & !loop
>                 )
>               & ~!loop
>           )
>         )

Overview: Hash tables .

# How Bracmat evolved

Bracmat originated from a Basic program that was meant (and able) to do some algebraic calculations in General Relativity. This program could do the mathematical operations that Bracmat can: add, multiply, take powers and logarithms and differentiate. This calculator was not programmable, all program flow had to be done in Basic. It became clear that the program could only solve the simplest algebraic problems. The reason for this was its inability to recognise complex patterns in the subject expressions. All pattern recognition had to be done in Basic and this was a very fault prone business. It would be nice to have an interpreter at hand that could interpret human readable production rules. That is exactly what Bracmat embodies. This program is written in ANSI-C and developed on the fastest home computer that existed at that time (Acorn Archimedes). Although Bracmat is much faster than its predecessor, its main virtue lies in its programmability. The speed at which it processes formulae is not impressive, Bracmat needs a fast machine. Unlike many other algebra systems, its grammar has no relationship to the Algol grammar. Instead, the language component extends the syntax of simple algebraic formulae.

Compared with other algebra systems, Bracmat has few built-in functions and even its set of mathematical operators is small. There are no operators for subtraction and division, for example. Nevertheless, Bracmat is general and flexible enough to be able to solve even problems outside the field of computer algebra in an elegant way. This flexibility on the programming level is traded off against the inability to change the behaviour of the interpreter itself. There are no switches (toggles) that could influence, for example, the order of terms within a polynomial, or whether or not complex products are expanded, or the way backtracking is done. This choice was, of course, easier to implement, but it also has benefits for the user: the working of Bracmat programs is not obscured by deep side effects of switch settings. The only side effects that Bracmat allows are expression binding and change of focus in a multiple valued variable (array indexing, stacking). A later addition is support of objects, i.e. data structures that allow for partial updates. This introduced another kind of side effect.

One peculiar thing about the original, object-less Bracmat is the way in which it manages data:

1. Processes are not periodically interrupted for garbage collection.
2. Each piece of data has a reference counter. If the reference counter equals zero, the occupied memory is returned to the memory pool at once. If the reference counter is about to overflow, a fresh copy of this piece of data is made with a reference counter set to one. For objects, the reference counter counts to approximately 4000000000, making overflow practically impossible.
3. Data is only created and destroyed. It is never changed.
4. To the user, there is no difference between two expressions being equal, but stored in different parts of memory, and two expressions being two representations of the same parts of memory.
5. There is no facility for named fields within a data structure.

Leaving one of these features out would have severe consequences for the other features. (2) explains why (1) is true. (3) ensures that (2) is workable: if two pieces of data are created equal they will remain so. This, in turn, explains why (4) is true. (5) almost follows from (3) : in any full fledged programming language, named fields allow all types of actions on the named parts of a data structure that are allowed on whole data structures, that is: creation and destruction. But the possibility to destroy only part of a data structure means that the data structure as a whole is changeable, which violates (3).

In the current version of Bracmat, with objects, the last restriction (5) no longer exists. As a consequence, restrictions (3) and (4) are not true for objects. (2) needs the additional remark that the reference counter for objects is made so big (counts to more than 4000000000), that overflow is practically impossible. Restriction (1) is still true, which means that the Bracmat programmer must take care of the deletion of some pathological structures (to be precise: circular structures, which were non-existent in the object-less Bracmat).

How can a programming language that is created for handling data structures do without named fields ? If I only can create and destroy data, how can I let data evolve gradually, piecemeal ? The answer lies in the well-developed pattern matching mechanism. Change of data is a two step process. In the first step you retrieve, by means of pattern matching, all those parts of the data that you want to keep. The second step is building the new data from the retrieved parts, together with new pieces. Creation of complex data structures from parts is straightforward in Bracmat. For example, the variable Row is a list of three words. We want to change the second word into the word "cat":

>     {?} the dog runs:?Row     {initial creation}
>     {?} !Row:%?one % %?three  {step 1: retrieval of 1st and 3rd word}
>     {?} !one cat !three:?Row  {step 2: reconstruction}

This may seem complicated and cumbersome, but look at this:

>     {?} 123:?a                  {create three variables a,b and c}
>     {?} a sentence:?b
>     {?} (a.silly,data*structure):?c
>     {?} (!a.!b.!c):(?b.?c.?a)   {permutation of 3 values in just 1 "statement"}

Bracmat has no clear genealogy, but it has borrowed features from a number of programming languages. It is not declarative, like Prolog, nor deeply object oriented, like Smalltalk, but it is more or less procedural, like the majority of languages. Below, I have tried to make the origin of some details more explicit:
C:

1. conditional execution of right operands of "and" and "or"
2. parameter passing (only "by value")

Pascal:
locally defined functions and routines Lisp:

1. implementation of expressions in binary trees
2. weak type checking
3. late binding Logo: different notations for the same variable, depending on whether it produces or receives a value Snobol,Icon : 1) a well developed pattern matching apparatus including backtracking 2) dual results of evaluations : both value and success/failure

Every similarity to other computer algebra systems is a matter of evolutionary convergence.

Overview: BRACMAT .

# How to obtain Bracmat

You can obtain a copy of Bracmat by sending an e-mail to me (Bart Jongejan) at bart[AT]cst.dk. Please state your hardware/OS.

Overview: BRACMAT .