Don't Sweat the Syntax

Supplementary References

For more on steam engines and engineering drawings see web pages on the history of steam and the Newcomen steam engine in particular.

Here are some slides contrasting syntactic conventions both engineering drawings and programming languages.

Despite my somewhat cavalier attitude in the text, coping with programming language syntax and wrapping your brain around recursion can be hard if you actually have to write code. Taking With Computers doesn't pretend to teach you programming, but, in the online supplements for Chapters 4 and 5, I'm providing a little more background and guidance for anyone wanting to take a stab at programming in Scheme.

Ubiquitous Syntax

We'll start by considering the role of syntax in programming languages. Consider the following simple SPAM filtering program specified in roughly formatted prose:

if the email is from a dot com address and
it has the word "sale" in the subject line or
it has the word "buy" in the subject line 
then if you're not in the mood to read a stupid advertisement
then call it spam otherwise if it's from a dot edu 
then read it else if it's from a dot gov 
then if you're expecting a tax refund 
then read it otherwise call it spam

Can you understand what's going on in the code? Now I'll format the code to make it a little easier to read:

if the email is from a dot com address and
   it has the word "sale" in the subject line or
   it has the word "buy" in the subject line 
   then if you're not in the mood to read a stupid advertisement
        then call it spam 
   otherwise if it's from a dot edu 
                then go ahead and read it
                else if it's from a dot gov 
                     then if you're expecting a tax refund 
                             then read it
                             otherwise call it spam

How about now? Is it any easier to understand? Here are some questions to consider:

What's the logical difference between ``If A then (if B then C) else D'' and ``If A then (if B then C else D)''?
Is there a logical difference between ``A and (B or C)'' and ``(A and B) or C''?
Is there a logical difference between ``(A and B) and C'' and ``A and (B and C)''? How about between ``(not A) and (not B)'' and ``(not A) or B''?
What's the difference between ``Yell `help and call 911''' and ``Yell `help' and call 911''?

What can we do to make the meaning of programs clearer?

Follow every ``then'' clause with an ``else'' clause even if the ``else'' clause doesn't do anything except act as a place holder.
Use the token ``endif'' to end every ``if'' statement whether or not it has an an "else" clause.
Use parentheses or other punctuation to group conditions in complex conditional statements.
Use precedence conventions to group conditions logically and then parentheses where needed to override those conventions when they imply unwanted groupings, for example, typically ``and'' takes precedence over ``or''.

Syntactic Drawings

Consider a mechanical drawing or an engineering diagram. Diagrams involving mechanisms (gears, chains, linkages) such as the Newcomen steam engine shown in the text are particularly interesting to analyze for this exercise. List similarities between syntactic conventions in text and related conventions in graphical representations. Here's the diagram from Chapter 4 (the slides provide a somewhat clearer rendering of the graphics):

Try to parse the iconography of the diagram. How do you know, for example, that one part of the diagram represents a chain or rope, another a container of liquid, and still another a rigid linkage? How do recognize the various degrees of freedom implied in a diagram, for example, rotational and sliding joints? Try to imagine the consequences of various interventions. What would happen if you pulled on a chain or rotated an axle?

Computer programmers didn't invent bugs. Think about how bugs might be introduced in copying or modifying graphical representations. Try to find the bug in the following diagram:

How do you think this bug was introduced? Think about simple errors in engineering diagrams that result from mistakenly ``flipping a bit''. For example, you might write code to perform a particular action if a test returns true when actually you meant to perform the action if the test returns false. This could happen, say, if you name the test in a potentially confusing way. For example, what do you think the programmer intends by setting the boolean variable light_is_off to true? How about the condition (switch_is_on && !light_is_off) where && indicates conjunction and ! indicates negation?

Programming language syntax needn't be textual. Find some examples of graphical languages. Here's one of the simplest examples: a program or mathematical expression depicted as a tree as in:

(+ (* (- x 1) (- x 1)) (* (- y 1) (- y 1)))

Can you see this expression as a tree? Here's what it looks like when represented a little more explicitly as a tree:

Think about executing such a program from the leaves up.

Consider the following ``map'' and imagine a robot that can sense what sort of junction it's in (one of ELL, TEE or HOME) and can move in four directions (one of N, E, W, or S). If the robot moves in a direction from a junction that's impossible (for example, it tries to move in the direction N from HOME), then nothing happens and the robot remains in the same location, none the wiser.

          ELL --- HOME -- ELL            N           
           |       |       |           E + W
          ELL --- TEE --- ELL            S

Write a program to guide the robot from any initial location in the map to the HOME junction.

set FLAG false
while not HOME
  if TEE 
     then go N
     else if FLAG 
             then go E
             else go W and set FLAG true

Now create a graphical version of the above program. You can invent your own graphical notation if you like or you can adopt the conventions used in simple flow charts or state diagrams.

Recursive Definitions

Now let's look at recursion. I'm throwing around the idea of recursion like it's the most natural thing in the world, but let's take a little closer look.

Here's a self-referential (or recursive) definition of number:

Zero is a number.
If x is a number, then the successor of x is a number.
Zero is not the successor of any number.
Two numbers of which the successors are equal are themselves equal.
If a set S of numbers contains zero and also the successor of every number in S, then every number is in S.

These five axioms are known as Peano's axioms and they form the basis for the version of number theory known as Peano arithmetic . Note that the above axioms don't attempt to enumerate the set of positive integers, or provide names such as the familiar one, two, three, etc., but they nonetheless capture the essence of such numbers in the abstract notion of successor. What is the successor of zero? Just think of it as successor(zero) and its successor as successor(successor(zero)).

Recursion is an important concept in mathematics but it crops up in all sorts of everyday circumstances. We encountered one such instance in Chapter 1 when we provided a recursive definition of the ancestor relation in our brief introduction to the logic programming language Prolog:

Your parents are among your ancestors.
If someone is among your ancestors then their parents are among your ancestors.

Here's another self-referential definition:

The empty list is a list of numbers.
The list that you create by taking a number and appending it onto the front of a list of numbers is itself a list of numbers.

Note that in the case of lists of numbers we allow the empty list to be a list of numbers. What if a person was defined to be their own ancestor?

Recursion really shines when it comes to numbers and computation:

1 factorial is 1.
n factorial is n times n - 1 factorial.

But recursion applies to all sorts of practical computations as we saw in the case of our Scheme function that computes the simulated debt on a credit card. Think of recursion in computation as a means of unrolling a recursive definition to compute a particular instance of what's being defined. How would you write a recursive procedure to list all of your ancestors back n generations? We define a recursive procedure to print out p's ancestors for n generations back for some arbitrary person p and integer n:

If n is zero, then quit. If n is greater than zero, then print out p's parents and then (recursively) print out the each of p's mother's ancestors for (n - 1) generations back and then print out p's father's ancestors for (n - 1) generations back.

We translate the above prose description into Scheme and then display the code as you might see it in a syntax-savvy text editor (download this example as file in zip format):

(define (ancestors person n)
  (if (> n 0) 
      (and (print-ancestor (mother person))
           (print-ancestor (father person))
           (ancestors (mother person) (- n 1))
           (ancestors (father person) (- n 1)))))
(define (mother person)
  (cond ((equal? person "lucy") "anne")
        ((equal? person "bill") "lucy")
        (else "unknown")))
(define (father person)
  (cond ((equal? person "anne") "fred")
        (else "unknown")))
(define (print-ancestor person)
  (if (not (equal? person "unknown"))
      (printf "~A~\%" person)))

Despite the fact that you probably don't know the primitive Scheme functions, you can probably understand what's going on from the prose description. Here we load the file containing the program and demonstrate it working:

> (load "ancestor.scm")
> (ancestors "bill" 4)
lucy
anne
fred

The ancestor code is not particularly well written given the way it makes use of if and and. Think about how to rewrite the above functions to make them clearer in the way they handle truth functional operators like and and expressions that are meant to be interpreted as true or false. Also, this version of ancestor keeps looking for unknown's parents. Alter the prose description to avoid searching unnecessarily.

Now let's take a look at a variant of the debt program in the text but without most of the syntactic cues:

define debt balance rate payment charges months
if months = 0
balance
debt charges + balance + balance * rate / 12 - payment 
     rate payment charges months - 1

Explore various ways of resolving the ambiguities that arise in trying to interpret this program and then comment on the conventions used in the Scheme version:

(define (debt balance rate payment charges months)
  (if (= months 0)
      balance
    (debt (+ charges
             balance 
             (* balance (/ rate 12))
             (- payment))
          rate
          payment
          charges
          (- months 1))))

Now look at the factorial function in Scheme, C, Mathematica and Java.

Example Exercises

Rube Goldberg Machines

Search the web for Rube Goldberg and find some of his strange and often wacky drawings of machines. See if the drawings actually make sense from a mechanical point of view. Take one of the machines and describe it in prose as a program.

Building on the example in the lectures, write a program for the following, somewhat more complicated map:

          ELL --- HOME -- ELL           
           |       |       |             N
          TEE --- TEE      |           E + W
           |       |       |             S
          ELL --- ELL --- ELL

Think about the advantages (and disadvantages) of the following random walk method for finding your way home:
```
while not HOME
  randomly choose one of N, E, W and go
```

Errata

The factorial function, notated n! and spoken ``n factorial,'' takes a non-negative integer as its only argument and returns 1 for n = 0 or the product of 1, 2, 3, ..., up to n, for n > 0; thus, 4! = 1 * 2 * 3 * 4 = 24. There is a typo in the first edition where it is incorrectly stated that the factorial function returns 0 for n = 0. The quantity n! can be interpreted as the number of ways of ordering n items. The special case of 0! is defined to have value 1 consistent with this interpretation -- there being exactly one way to arrange zero items.

Code Fragments

Download all the code fragments in this chapter as a file in zip format.