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)™ ?