<< . .

. 8
( : 45)



. . >>

variable ’’ external tag su¬x | internal quantity false
tag ’’ external tag | internal quantity string
path
pen
picture
EXERCISE 7.4
transform
True or false: Every variable is a legal su¬x . pair
numeric
The ˜[™ and ˜]™ that appear in the syntax for subscript stand for any sym-
bolic tokens whose current meanings are the same as ™s primitive
meanings of left and right bracket, respectively; those tokens don™t necessarily have to
be brackets. Conversely, if the meanings of the tokens ˜[™ and ˜]™ have been changed,
brackets cannot be used to delimit subscripts. Similar remarks apply to all of the sym-
bolic tokens in all of the syntax rules from now on. doesn™t look at the
form of a token; it considers only a token™s current meaning.

The examples of programs in this book have used two di¬er-
ent typographic conventions. Sometimes we refer to variables by using italic type
and/or genuine subscripts, e.g., ˜em ™ and ˜x2r ™; but sometimes we refer to those
same variables by using a typewriter-like style of type, e.g., ˜em™ and ˜x2r™. In
general, the typewriter style is used when we are mainly concerned with the way
a programmer is supposed to type something that will appear on the terminal
or in a ¬le; but fancier typography is used when we are focusing on the meaning
of a program rather than its ASCII representation. It should be clear how to
convert the fancier form into tokens that can actually understand.
In general, we shall use italic type only for tags (e.g., em , x , r ), while boldface
and roman type will be used for sparks (e.g., draw, ¬ll, cycle, rotated, sqrt).
Tags that consist of special characters instead of letters will sometimes get special
treatment; for example, em# and z2™ might be rendered em # and z2 , respectively.

The variables we™ve discussed so far have almost always had numbers as
their values, but in fact ™s variables are allowed to assume values of
eight di¬erent types. A variable can be of type
boolean, representing the values ˜true™ or ˜false™;
string, representing sequences of ASCII characters;
path, representing a (possibly curved) line;
pen, representing the shape of a pen nib;
picture, representing an entire pattern of pixels;
transform, representing the operations of scaling, rotating, shifting, re-
¬‚ecting, and/or slanting;
pair, representing two numbers (e.g., a point or a vector);
numeric, representing a single number.
56 Chapter 7: Variables


If you want a variable to represent something besides a number, you must ¬rst type declaration
declarations
give a type declaration that states what the type will be. But if you refer to a []
variable whose type has not been declared, won™t complain, unless collective subscripts
value, disappearance of
you try to use it in a way that demands a value that isn™t numeric. declaration
Type declarations are easy. You simply name one of the eight types, type
boolean
then you list the variables that you wish to declare for that type. For example, string
the declaration path
pen
picture
pair right , left , a.p
transform
pair
says that right and left and a.p will be variables of type pair, so that equations numeric
like
right = ’left = 2a.p = (1, 0)
can be given later. These equations, incidentally, de¬ne the values right = (1, 0),
left = (’1, 0), and a.p = (.5, 0). (Plain has the stated values of
right and left already built in.)
The rules for declarations are slightly trickier when subscripts are in-
volved, because insists that all variables whose names are identical
except for subscript values must have the same type. It™s possible to set things
up so that, for example, a is numeric, a.p is a pair, a.q is a pen, a.r is a path,
and a1 is a string; but if a1 is a string, then all other variables a2 , a3 , etc.,
must also be strings. In order to enforce this restriction, allows only
“collective” subscripts, represented by empty brackets ˜[]™, to appear in type
declarations. For example,
path r, r[], x[]arc, f[][]
declares r and all variables of the forms r[i], x[i]arc , and f [i][j] to be path
variables. This declaration doesn™t a¬ect the types or values of other variables
like r[ ]arc ; it a¬ects only the variables that are speci¬cally mentioned.
Declarations destroy all previous values of the variables being de¬ned.
For example, the path declaration above makes r and r[i] and x[i]arc and f [i][j]
unde¬ned, even if those variables previously had paths as their values. The idea
is that all such variables will start out with a clean slate so that they can receive
appropriate new values based on subsequent equations.
EXERCISE 7.5
Numeric variables don™t need to be declared. Therefore is there ever any reason
for saying ˜numeric x™ ?
The formal syntax rules for type declarations explain these grammatical con-
ventions precisely. If the symbolic token that begins a declared variable was
previously a spark, it loses its former meaning and immediately becomes a tag.
declaration ’’ type declaration list
type ’’ boolean | string | path | pen
| picture | transform | pair | numeric
Chapter 7: Variables 57


declaration list ’’ declared variable declaration list
| declaration list , declared variable ,
declared variable
declared variable ’’ symbolic token declared su¬x declared su¬x
declared su¬x ’’ empty | declared su¬x tag DARWIN
Algol
| declared su¬x [ ] LOCKYER

EXERCISE 7.6
Find three errors in the supposed declaration ˜transform t42,24t,,t,path™.




Beings low in the scale of nature are
more variable than those which are higher.
” CHARLES DARWIN, On the Origin of Species (1859)

Among the variables, Beta (¬) Persei, or Algol,
is perhaps the most interesting, as its period is short.
” J. NORMAN LOCKYER, Elements of Astronomy (1870)
(page 58)




8
Algebraic
Expressions
Chapter 8: Algebraic Expressions 59


programmers express themselves algebraically by writing algebraic expressions
variable
formulas called expressions. The formulas are algebraic in the sense that they constant
involve variables as well as constants. By combining variables and constants with operator
operands
appropriate mathematical operations, a programmer can specify an amazing parentheses
variety of things with comparative ease. sqrt
product
We have already seen many examples of expressions; our goal now is to
make a more systematic study of what is possible. The general idea is that an
expression is either a variable (e.g., ˜x1 ™ ) or a constant (e.g., ˜20™ ), or it consists
of an operator (e.g., ˜+™ ) together with its operands (e.g., ˜x1 + 20™ ). The
operands are, in turn, expressions built up in the same way, perhaps enclosed in
parentheses. For example, ˜(x1 +20)/(x2 ’20)™ is an expression that stands for the
quotient of two subexpressions. It is possible to concoct extremely complicated
algebraic expressions, but even the most intricate constructions are built from
simple parts in simple ways.
Mathematicians spent hundreds of years developing good ways to write
formulas; then computer scientists came along and upset all the time-honored
traditions. The main reason for making a change was the fact that computers
¬nd it di¬cult to deal with two-dimensional constructions like
2√
x1 + 20
a2 ’
+ b.
x2 ’ 20 3
One-dimensional sequences of tokens are much easier to input and to decode;
hence programming languages generally put such formulas all on one line, by
inserting parentheses, brackets, and asterisks as follows:
(x[1]+20)/(x[2]-20)+sqrt(a**2-(2/3)*sqrt(b)).
will understand this formula, but it also accepts a notation that is
shorter and closer to the standard conventions of mathematics:
(x1+20)/(x2-20)+sqrt(a**2-2/3sqrt b).
We observed in the previous chapter that allows you to write ˜x2™
instead of ˜x[2]™; similarly, you can write ˜2x™ instead of ˜2*x™ and ˜2/3x™ instead
of ˜(2/3)*x™. Such operations are extremely common in programs,
hence the language has been set up to facilitate them. On the other hand, -
doesn™t free you from all the inconveniences of computer languages; you
must still write ˜x*k™ for the product of x times k, and ˜x[k]™ for the variable
x subscripted by k, in order to avoid confusion with the su¬xed variable ˜x.k™.
We learned in the previous chapter that there are eight types of variables:
numeric, boolean, string, and so on. The same types apply to expressions; -
deals not only with numeric expressions but also with boolean expressions,
string expressions, and the others. For example, ˜(0, 0) . . (x1 , y1 )™ is a path-
valued expression, formed by applying the operator ˜. .™ to the subexpressions
˜(0, 0)™ and ˜(x1 , y1 )™; these subexpressions, in turn, have values of type “pair,”
and they have been built up from values of type “numeric.” Each operation
60 Chapter 8: Algebraic Expressions


produces a result whose type can be determined from the types of the operands; order of operations
precedence
furthermore, the simplest expressions (variables and constants) always have a magnets
de¬nite type. Therefore the machine always knows what type of quantity it is braces
brackets
dealing with, after it has evaluated an expression.
If an expression contains several operators, has to decide
which operation should be done ¬rst. For example, in the expression ˜a ’ b + c™
it is important to compute ˜a ’ b™ ¬rst, then to add c; if ˜b + c™ were computed
¬rst, the result ˜a ’ (b + c)™ would be quite di¬erent from the usual conventions
of mathematics. On the other hand, mathematicians usually expect ˜b/c™ to
be computed ¬rst in an expression like ˜a ’ b/c™; multiplications and divisions
are usually performed before additions and subtractions, unless the contrary is
speci¬cally indicated by parentheses as in ˜(a ’ b)/c™. The general rule is to
evaluate subexpressions in parentheses ¬rst, then to do operations in order of
their “precedence”; if two operations have the same precedence, the left one is
done ¬rst. For example, ˜a ’ b/c™ is equivalent to ˜a ’ (b/c)™ because division
takes precedence over subtraction; but ˜a ’ b + c™ is equivalent to ˜(a ’ b) + c™
because left-to-right order is used on operators of equal precedence.
It™s convenient to think of operators as if they are tiny magnets that
attract their operands; the magnets for ˜—™ and ˜/™ are stronger than the magnets
for ˜+™ and ˜’™, so they stick to their operands more tightly and we want to
perform them ¬rst.
distinguishes four (and only four) levels of precedence. The
strongest magnets are those that join ˜2™ to ˜x™ and ˜sqrt™ to ˜b™ in expressions like
˜2x™ and ˜sqrt b™. The next strongest are multiplicative operators like ˜—™ and ˜/™;
then come the additive operators like ˜+™ and ˜’™. The weakest magnets are
operators like ˜. .™ or ˜<™. For example, the expression
a + sqrt b/2x < c
is equivalent to the fully parenthesized formula
a + (sqrt b)/(2x) < c.

EXERCISE 8.1
Insert parentheses into the formula ˜z1+z2..z3/4*5..z6-7*8z9™, to show ex-
plicitly in what order will do the operations.
High-school algebra texts often avoid parentheses inside of parentheses by
using braces and brackets. Therefore many people have been trained to write

{a + [(sqrt b)/(2x)]} < c

instead of the fully parenthesized formula above. However, professional mathematicians
usually stick to only one kind of parentheses, because braces and brackets have other
meanings that are more important. In this respect is like the professionals:
It reserves curly braces ˜{}™ and square brackets ˜[]™ for special purposes, so you should
not try to substitute them for parentheses.
Chapter 8: Algebraic Expressions 61


If you really want alternatives to parentheses, there is actually a way to get delimiters
division of numeric tokens
them. You can say, for example,
fractions
tracingonline
delimiters [[ ]]; delimiters {{ }} scrollmode
forever
after which double brackets and braces can be used in formulas like scantokens
readstring
{{a+[[(sqrt b)/(2x)]]}}<c. message
expr.mf
The symbolic token ˜{{™ has no relation to ˜{™, and it has no primitive meaning, hence
you are free to de¬ne it in any way you like; the delimiters command de¬nes a new
pair of delimiters. In formulas with mixed delimiters as de¬ned here, will
check that ˜[[™ matches only with ˜]]™, ˜{{™ only with ˜}}™, and ˜(™ only with ˜)™; thus
you can more easily detect errors in large expressions. However, it™s usually unnecessary
to have any delimiters other than parentheses, because large expressions are rare, and
because the rules of operator precedence make most parentheses super¬‚uous.

If you™re reading this chapter carefully, you may be thinking, “Hey wait!
Isn™t there a contradiction? A minute ago I was told that ˜2/3x™ stands for
˜(2/3)*x™, but now the rules of precedence appear to state that ˜2/3x™ really
stands for ˜2/(3x)™. What gives?” Indeed, you have an excellent point; but
there is no contradiction, because of another rule that hasn™t been mentioned
yet. When two numeric tokens are divided, the magnetism of ˜/™ is stronger
than usual; in this case ˜/™ has the same precedence as the implied multiplication
operator in ˜3x™. Hence the operations in ˜2/3x™ are carried out from left to right,
as stated previously. (This is a good rule because it is almost always what a
programmer wants. However, one should bear in mind that ˜a/3x™
means ˜a/(3x)™ when a is not a numeric token.)
Because of the rule in the previous paragraph, the programs
2
in this book often say ˜ 3 x™ for what would be typed ˜2/3x™ in a ¬le. Such built-up
fractions are never used except when the numerator and denominator are both
a
numbers; a construction like ˜a/3x™ will always be rendered as ˜a/3x™, not ˜ 3x ™.
knows how to do dozens of operations that haven™t been
mentioned yet in this book. Let™s take a look at some of them, so that we will
know they are available in case of need. It will be most instructive and most
fun to learn about expressions by interacting with the computer; therefore you
should prepare the following short ¬le, called expr.mf:
string s[]; s1="abra";
path p[]; p1=(0,0)..(3,3); p2=(0,0)..(3,3)..cycle;
tracingonline:=1; scrollmode;
forever: message "gimme an expr: "; s0:=readstring;
show scantokens s0; endfor
You don™t need to understand what™s in expr.mf when you read this chapter for
the ¬rst time, because the ¬le uses in ways that will be explained
carefully later. But here is a translation, in case you™re curious: Line 1 declares all
variables of the form sk to be strings, and sets s1 to the value "abra". Line 2 declares
all variables of the form pk to be paths, and sets p1 and p2 to simple example paths.
62 Chapter 8: Algebraic Expressions


Line 3 tells to print diagnostic information online, i.e., on the terminal as online
log ¬le
well as in the log ¬le; it also establishes ˜scrollmode™, which means that the computer
gimme
won™t stop after error messages. Lines 4 and 5 set up an in¬nite loop in which - arithmetic
reads an expression from the terminal and shows the corresponding value. epsilon

If you start and type ˜expr™ when it asks for an input ¬le
name, it will read the ¬le expr.mf and then it will say ˜gimme an expr™. Here™s
where the fun starts: You can type any expression, and will compute
and display its value. Try it; type ˜2+2™ and return , obtaining the value ˜>> 4™.
Isn™t that amazing? Here are some more things to try:
You type And the result is
1.2-2.3 -1.1
1.3-2.4 -1.09999
1.3*1000 1300.00305
2.4*1000 2399.9939
3/8 0.375
.375*1000 375
1/3 0.33333
1/3*3 0.99998
0.99999 0.99998
1-epsilon 0.99998
1/(1/3) 3.00005
1/3.00005 0.33333
.1*10 1.00006
1+4epsilon 1.00006
These examples illustrate the small errors that occur because does
“¬xed binary” arithmetic using integer multiples of 65536 . The result of 1.3 ’ 2.4
1

is not quite the same as ’1.1, because 1.3 is a little bit larger than 13 and 2.4
10
is a little smaller than 24 . Small errors get magni¬ed when they are multiplied
10
by 1000, but even after magni¬cation the discrepancies are negligible because
they are just tiny fractions of a pixel. You may be surprised that 1/3 times 3
comes out to be .99998 instead of .99999; the truth is that both 0.99999 and
0.99998 represent the same value, namely 65535 ; displays this value
65536
as 0.99998 because it is closer to .99998 than to .99999. Plain
1
de¬nes epsilon to be 65536 , the smallest representable number that is greater
than zero; therefore 1-epsilon is 65535 , and 1+4epsilon is 65540 .
65536 65536

You type And the result is
4095.99998 (with error message)
4096
infinity 4095.99998
32767.99998 (with error message)
1000*1000
Chapter 8: Algebraic Expressions 63


infinity+epsilon 4096 enormous number
in¬nity
100*100 10000 mediation
multiply
.1(100*100) 1000.06104 divide
(100*100)/3 3333.33333
will complain that an ˜Enormous number has been reduced™ when
you try to introduce constants that are 4096 or more. Plain de¬nes
in¬nity to be 4096 ’ epsilon , which is the largest legal numeric token. On
the other hand, it turns out that larger numbers can actually arise when an
expression is being evaluated; doesn™t worry about this unless the
resulting magnitude is at least 32768.
EXERCISE 8.2
If you try ˜100*100/3™ instead of ˜(100*100)/3™, you get ˜3333.33282™. Why?
Sometimes will compute things more accurately than you would
expect from the examples above, because many of its internal calculations are
done with multiples of 2’28 instead of 2’16 . For example, if t = 3 the result of ˜1/3t™
will be exactly 1 (not 0.99998); the same thing happens if you write ˜1/3(3)™.
Now let™s try some more complicated expressions, using unde¬ned vari-
ables as well as constants. (Are you actually trying these examples, or are you
just reading the book? It™s far better to type them yourself and to watch what
happens; in fact, you™re also allowed to type things that aren™t in the book!)
You type And the result is
b+a a+b
a+b a+b
b+a-2b a-b
2(a-b+.5) 2a-2b+1
.5(b-a) -0.5a+0.5b
.5[a,b] 0.5a+0.5b
1/3[a,b] 0.66667a+0.33333b
0[a,b] a
a[2,3] a+2
t[a,a+1] t+a
b (with error message)
a*b
b (with error message)
1/b
has a preferred way to arrange variables in order when they are
added together; therefore ˜a + b™ and ˜b + a™ give the same result. Notice that
the mediation construction ˜.5[a, b]™ speci¬es a number that™s halfway between a
and b, as explained in Chapter 2. does not allow you to multiply
two unknown numeric quantities together, nor can you divide by an unknown
numeric; all of the unknown expressions that works with must be
64 Chapter 8: Algebraic Expressions


“linear forms,” i.e., they must be sums of variables with constant coe¬cients, linear forms
sqrt
plus an optional constant. (You might want to try typing ˜t[a,b]™ now, in order square roots
to see what error message is given.) **
true
You type And the result is false

sqrt 2 1.41422
sqrt 100 10
sqrt 100*100 1000
sqrt(100*100) 100
sqrt 100(100) 100
sqrt sqrt 100(100) 10
sqrt .01 0.09998
0.09998**2 0.01
2**1/2 1.41422
sqrt 2**2 2
0 (with error message)
sqrt -1
a (with error message)
sqrt a
Since sqrt has more “magnetism” than *, the formula sqrt 100*100 is evaluated
as (sqrt 100)*100; but in ˜sqrt 100(100)™ the 100(100) is computed ¬rst. The
reason is that ˜(sqrt 100)(100)™ isn™t a legal expression, so the operations in
˜sqrt 100(100)™ must be carried out from right to left. If you are unsure about
the order of evaluation, you can always insert parentheses; but you™ll ¬nd that
™s rules of precedence are fairly natural as you gain experience.
EXERCISE 8.3
Is ˜sqrt 2**2™ computed as ˜(sqrt 2)**2™ or as ˜sqrt(2**2)™ ?

<< . .

. 8
( : 45)



. . >>