Why is understanding goto transformations useful?

• Understand operational semantics
• Observation that resulting code is hard to understand
• Useful to hand convert code to assembly language

Computers have memory that can be used for storage.

Originally, code and date were separate.

The Hungarian genius John Von Neumann (who started many important fields of mathematics, computer science, economics, etc.) first recognized that code and data were interchangeable.

The traditional model of computers (almost all computers) are named von Neumann machines.

Computers have memory that can be used to store code and data.

The computer processor reads code in sequence and, when necessary, changes the location of where the code is read using jump or goto statements. Some jumps or goto statements are conditional.

Note: Variables are named memory locations.

The goto statements covered are part of the language C (and C++).

FORTRAN made extensive use of the goto statement.

The BASIC (Beginners All-Purpose Symbolic Instruction Code) programming language started with goto statements.

Java has goto as a reserved word in the language specification but has not implemented nor specified that feature.

The Go programming language has a goto statement. Why might this be?

The target of a goto statement (on memory or in a program) is represented by a label. A label starts with a letter and is followed by letters and/or digits followed by a colon character. (Note: Some other characters are also permissible). Here are some labels.

An unconditional goto statement has the form

and, when executed, will transfer control to the first statement that follows label.

The conditional goto statement has the form

and, when executed, if expression is true, then control is transferred to the first statement that follows label.

The "if-then-else" statement has the following form.

The above "if-then-else" code does the same thing as the following code using the goto statement.

The above "if-then-else" code has the following axiomatic semantics.

Loops allow repetitive actions to be done. There are three primary forms of the loop.

• "while-do" loop
• "do-while" loop
• "for-next" loop

The "while-do" loop has the following form.

That is, while the expression is true, do the statements.

The above "while-do" loop does the same thing as the following code using the goto statement.

In a "while-do" loop, the expression is tested before the statements are executed, so it is possible that the statements may never be executed.

The "while-do" code

is the same as the following.

The above "while-do" code has the following axiomatic semantics.

The expression invariant is the loop invariant. Note that the invariant may be non-trivial and not easily expressed as an expression unless the expression calls a function to compute some non-trivial value.

The "do-while" loop has the following form.

The above "do-while" code does the same thing as the following code using the goto statement.

In a do loop, the statements are executed before the first test of expression, so the statements will always be executed at least once.

The "do-while" loop form can be expressed as the following "while-do" loop.

To see this, convert the "while-do" loop to goto form using the transformation rule for the "while-do" loop and compare the resulting goto form to the goto form for the "do-while" loop.

The "for-next" loop has the following form.

The above "for-next" code does the same thing as the following code using the goto statement.

The above "for-next" loop can be expressed as the following "while-do" loop.

To see this, convert the "while-do" loop to goto form using the transformation rule for the "while-do" loop and compare the resulting goto form to the goto form for the "for-next" loop.

The "For-next" code

is the same as the following code.

On for loops: In formal program verification, for loops are converted to their equivalent while loops.

While loops (and do while) always work and have a clear and consistent semantics which does not change. For loops are more complicated in that they have subtle semantics that can change between languages. For example:

• Is the for loop control ending condition evaluated once or every time?
• What happens if the for loop variable is changed within the for loop?
• Does the for loop control variable have a value or a valid value after the for loop ends?
• And so on.

This behavior can change between languages. Such issues do not arise in while loops.

I recommend (to students and others) that one should only use a for loop for 0 to n-1 or 1 to n, unless you are an expert and know what you are doing. Iterators follow this form, that is, iterate over everything in the collection.

In all of the above loops,

• expression is the loop condition, a logical expression, and
• statements is the loop body that consists of one or more statements.

Since both the "do-while" and "for-next" loops can be converted to "while-do" loop form, we will discuss some features of the "while-do" loop.

Joke: If you understand the body of a loop, you will understand how a loop works after a while.

An expression is a formula that evaluates to and can be expressed as a literal value. A statement is a command that is executed for effect.

Reasoning about the correctness of programs for which expressions have side-effects is very difficult. Therefore, the assumption is made that expressions are not allowed to have side-effects.

A further assumption is made that control cannot transfer out of the middle of a "begin-end" block.

• The loop condition expression must change, otherwise it is always either true or false.

If the loop condition expression is always true, the code

will never terminate.

If the loop condition expression is always false, the statements in the code

will never be executed and the entire "while-do" loop can be removed.

Since the loop condition expression should never be always true or always false, something in the loop condition expression must change such that the loop condition expression changes at some point from true to false.

If there are no side-effects in expressions, then there must be a variable in the loop body statements that is changed, or in code that the loop body statements calls.

If there is something in statements that changes, then there is something that stays the same. The part that stays the same is called the invariant, or loop invariant.

Every well-formed loop has a loop invariant.

It is beyond the scope of this course for you to identify your own loop invariant. However, you are expected to study and understand loop invariants that are provided in order to understand code containing loops.

The informal semantics is as follows.

• The loop condition is evaluated.
• If the loop condition is true, then the statements in the loop body are executed.
• This two-step process is continued until b evaluates to false.
• Execution is continued with the statements after the end of the loop.

For example, identify b and s in the following pseudo code example.

WHILE you do not understand this handout DO
study this handout
ENDDO

One way to approach programming in assembly language is as follows.

• Write a pseudo code algorithm
• Implement in a high level program code.
• Transform to assembly language
• For expressions, transform to postfix stack machine.
• For control flow, transform to goto statements
• For procedures and functions, handle the run-time stack.

1 questions omitted (login required)