5.1
Imperative Languages
Imperative languages
were designed based on a computer architecture called the von Neumann
architecture, named after John von Neumann.
This class of computer language has been popular through the last
several decades.
Imperative languages
use variables, assignment statements, selection statements and the iterative
form of repetition. Although imperative
(or procedural) languages usually allow for recursion, iteration is often the
fastest method of repetition.
One of the basic
ideas of imperative languages is that variable names are bound to values, which
may be altered later in a program.
5.2
SPoc
SPoc illustrates the
imperative (procedural) programming style.
The current implementation is deliberately simple as it is intended to
be used and modified as a student project.
In this implementation SPoc has a single data type, integer. This simplified imperative language, SPoc,
is block-structured, allowing the definition of named blocks as well as
procedures that define the scope of variable name bindings. Each block consists of a name, a declaration
section, which define bindings and a list of statements in which the bindings hold. Each procedure (declared before the main
program) consists of a name, a parameter list, a declaration section, which
define bindings and a list of statements in which the bindings hold. The only statements are print statements and
assignments with simple expressions on the right hand side of the
assignment. Global variables are
declared before any and all procedures as well as the main program.
5.3
Using SPoc with MuLE
A
SPoc window is created by executing the file "launcher.s" in
DrScheme. In the MuLE interface window
that appears, click on the "SPoc - functional" button or select from
the pull-down menu. This opens a SPoc
window by binding a variable to the result of a call to the procedure make-SPoc. Once in the SPoc environment, existing SPoc program files can be
opened and loaded into the simple editing window of the SPoc interpreter by
selecting the “open” button. The opened
file will appear in the upper window and may be modified before executing with
the SPoc interpreter. Everything typed
in the lower window will be interpreted as an expression by SPoc.
5.4
The SPoc interpreter
The
SPoc interface is a double paned window.
Both the upper definitions window and the lower interface window can be
used to enter in programs, though it is recommended that the definitions window
be used for this purpose. The interface
window accepts one argument/statement at a time and executes it when the enter
key is hit, whereas the definitions window allows for several arguments/statements
on different lines to be entered at once.
They will only be executed when the "execute" button is
clicked. All of the output will appear
in the interface window. Besides this
benefit, the definitions window allows for the saving and retrieving of files,
opposed to the interface window which does not. If the user wishes to alternate between the two, bear in mind the
environment, or list, that has been created is used by, and thus is changed by,
either window.
At
the command level, SPoc understands three meta-commands: list, help
and clear. Each command is
executed in SPoc by entering the command, without parentheses, at the SPoc prompt.
list A
debugging instruction that will list all of the environment (current variable) bindings.
clear Clears the environment (current variable) bindings. This is especially useful between program
executions.
help Displays
the SPoc grammar.
Simplistic comments
are allowed in SPoc programs. If the
first two characters on a line of a SPoic program are // then the line is ignored by the SPoc interpreter. There can be no white space or other
characters before the //, i.e. the // must be in columns one and two of the line.
5.5
Reserved Words in SPoc
There
are certain reserved words in addition to the three control commands listed
above that the interpreter looks for in a SPoc program. These words cannot be used as program,
block, procedure or variable names.
SPoc interpreter
reserved words:
begin
block call declare end exit globals
help
print procedure program return
5.6
Explanation of a Simple SPoc Program
program one program named one
declare a / b / c $ the integer variables a, b, c are initialized to zero
begin
a
= 1 $ the variable a is assigned the value 1
b
= 2 $ the
variable b is assigned the value 2
c
= ( a + b ) $ addition is performed and returns 3
the variable c is
bound to 3
print
c $ the value of the variable c is printed
end
This program is very basic and does not include any global
variables or
procedures. Spacing
is important, as spaces between each symbol and variable
are essential for the program to run.
5.7
Parsing of a Simple SPoc Program
A sample SPoc program appears below:
program
one
declare
a / b / c $
begin
a = 1 $
b = 2 $
c = ( 2 * a + b ) $
print a $
end
If the word program is found, then the function parse-SPoc( ) is immediately
called. If the word procedure is found, the function parse-proc( ) is then called
to parse the procedure. This function
looks for more procedures, and continues parsing until the word program is found. Once program
is found, the function parse-SPoc(
) is
called.
In
the function parse-SPoc( ), the program
name is sent to parse-id( ), where the
interpreter makes sure that the program name is not a reserved word. The program name is returned as an ID called name.
Next, parse-SPoc( ) looks for the
reserved word declare. Parse-decl(
) is
called to parse the variables which were declared. Here, the variables are a, b, c.
The function parse-id(
) is
called for each variable, and then each variable is initialized to zero and
placed in the variable list. Parse-decl( ) also looks for
the symbol /, indicating that there
is another variable to parse. Once the
symbol $ is found, we have come to
the end of the variable declarations, and we return the list of variables to parse-SPoc( ). Parse-SPoc( ) adds the list
of variables to the environment.
Parse-SPoc( ) next finds the
reserved word begin. Since begin
is followed by a statement list (as we see in the grammar) parse-stmt-list( ) is
called. This function looks for
reserved words block, call, print, end. If block
is found, then parse-block(
) is
called. If call is found, then parse-call(
) is
called. If print is found, then parse-print(
) is
called. If end is found, then the flag token is set to be end, which will be checked in parse-SPoc(). If none of these
reserved words are found, then the statement must be an arithmetic expression
and parse-assignment( ) is called. If the
symbol $ is found, then the next statement is parsed by parse-stmt-list(). Looking at the
sample program, we find that the first statement is a = 1 $, therefore parse-assignment(
) is
called.
In parse-assignment(), the variable a
is sent to parse-id(). Then the symbol = is found, and parse-expression( ) is
called. In parse-expression(), the 1 is found
and is returned to parse-assignment(). Here, the value 1 is bound to the variable a.
This value will be shown when the environment is printed. Now we return to parse-stmt-list( ) and the rest
of the statements are parsed, until the reserved word end is found.
5.8
A Complete BNF Grammar for SPoc
|
<SPoc> |
::= |
SPoc command> |
|
<SPoc
command> |
::= |
help |
|
<SPoc
command> |
::= |
clear |
|
<SPoc
command> |
::= |
list |
|
<SPoc> |
::= |
<SPoc_program> |
|
<SPoc> |
::= |
outer_scope> |
|
<outer_scope> |
::= |
globals
<decl> <subpgm_list> <main> |
|
<subpgm_list> |
::= |
<subpgm> |
|
<subpgm_list> |
::= |
<subpgm>
<subpgm_list> |
|
<subpgm> |
::= |
<proc> |
<fnc> |
|
<fnc> |
::= |
|
|
<proc> |
::= |
|
|
<proc> |
::= |
pocedure <id>
( <id_list> ) <decl> beginproc <stmt_list> return |
|
<main> |
::= |
SPoc_program> |
|
<SPoc_program> |
::= |
program <id>
<decl> begin <stmt_list> end |
|
<decl> |
::= |
declare
<id_list> $ |
|
<id_list> |
::= |
<id> |
|
<id_list> |
::= |
<id> /
<id_list> |
|
<stmt_list> |
::= |
<stmt> $ |
|
<stmt_list> |
::= |
<stmt> $
<stmt_list> |
|
<stmt> |
::= |
<id> = (
<expr> ) |
|
<stmt> |
:= |
<id> =
<id> |
|
<stmt> |
::= |
<id> =
<no> |
|
<stmt> |
::= |
print <id> |
|
<stmt> |
::= |
<block> |
|
<stmt> |
::= |
call <id> (
<id_list> ) |
|
<block> |
::= |
block <id>
<decl> begin <stmt_list> end |
|
<expr> |
::= |
<factor> +
<expr> | <factor> - <expr> | <factor> * <expr> |
<factor> / <expr>
| <factor> @ <expr>
| <factor> &
<expr> | <factor> > <factor> |
<factor <
<factor> | <factor> |
|
<factor> |
::= |
<id> |
<no> | (<expr>) |
5.9
Relational Expressions
The value of a
relational expression is Boolean. The
relational expressions allowed in SPoc are greater
than or less than. When a variable is set equal to a relational
expression, that variable will be bound to the “Boolean” 0 for false or 1 for
true. For example:
a
= ( 1 > 2 ) $
In this example, the
variable a is bound to either Boolean
true or false. Since
( 1 > 2 ) is a false statement, a
will be bound to the value 0.
These relational
expressions can be used with Boolean and
and or. For example:
x
= ( ( 1 > 2 ) or ( 4 > 3 ) ) $
In this example, the
variable x is bound to the value of
an or expression. (
1 > 2 ) is false, while ( 4 > 3 ) is true. Therefore,
the or produces true which is
represented as 1, and x is bound to 1. SPoc uses atypical
symbols to represent and / or. See the next
section for use of the logical operators in SPoc.
5.10
Boolean Expressions
The Boolean operators
and and or are included in the possible expressions to be used in SPoc
programs. These operators will return a
1 if true and a 0 if false. The symbol @
corresponds to or, and the symbol
& corresponds to and. For example:
a
= ( 1 & b) $
c
= ( 0 @ d ) $
x
= ( ( 1 > 2 ) @ ( 4 > 3 ) ) $
In the first
assignment of this example, a will be
bound to either 0 or 1 depending on b. If b is anything other than 0,
then b is considered true. False is always 0, while true is anything other than 0. Therefore, if b is equal to 7, then a will be bound
to 1.
The expression
assigned to c uses the Boolean
expression or. The value of c depends on d, as the
first operand in the expression is 0.
Therefore, if b = 0, then the
expression is false or 0. If b is equal to anything other than 0,
then the expression is true and c
will be bound to 1.
5.11
Left to Right and Right to Left evaluation of expressions
There
is separate code for each method, either left-to-right in the file “left.spoc”
or right-to-left in the file “right.spoc” for evaluating expressions. The method used in the default version of
SPoc is left-to-right evaluation. To
use one method, the other code must be commented out using at least one
semi-colon before each line of code.
Or, alternatively, the excess code may be placed temporarily in another
file. Be sure to save the working SPoc
program before running the launcher program again as the new code must be
evaluated. A sample program to test
which method is being used would be a program including the lines:
program test
declare a $
begin
a = ( 5 + 2 * 7 ) $
print a $
end
If left-to-right
evaluation of expressions was being used, the function evaluating the
assignment for a would be sent to parse-expression(). First, 5 + 2 would be evaluated producing a 7.
Next, 7 * 7 would be
evaluated, and a would be bound to 49.
If right-to-left
evaluation of expressions was being used, the function evaluating the
assignment for a would be sent to parse-expression(). First, 2 * 7 would be evaluated yielding a 14.
Next, 5 + 14 would be
evaluated, and a would be bound to 19.
By printing the value
of a in the program, we could see
which type of expression evaluation is being used.
5.12
Precedence (Order of Operations)
To use precedence in
evaluating expressions,
the code in the file
“precedence.spoc”,
“Rprecedence.spoc”,
“LprecParen.spoc”, or
“RprecParen.spoc”
must replace the
current function parse-expression() in SPoc. Expressions may be evaluated so that
multiplication and division have higher precedence over addition and subtraction
using left-to-right evaluation. For
example, the expression (3 + 4
* 2 - 1), using left-to-right
evaluation (without precedence), would be (7
* 2 - 1) or (14 - 1)
or (13).
If multiplication and
division have precedence over addition and subtraction, then the 4*2 would be evaluated first. This would produce (3 + 8 - 1) or (10).
In order to use
precedence, the specific parse-expression() labeled as
using the idea of precedence should be uncommented, while the other form of parse-expression() should either be commented out or not be included.
The default version
of SPoc uses short-circuit evaluation and
and or. There is code for both full and short evaluation of expressions
using & (for and) and @ (for or).
Simply comment out the code by placing at least one semi-colon before
each line of code, and remove the comments in front of the code to use. (One hunk of code must be uncommented for
each and and or) Alternatively, cut out
the unnecessary code and store it temporarily in another file.
Using full evaluation
of expressions, the second expression of the & or @ is always evaluated
regardless of the value of the first expression. For example, consider the program:
program
one
declare a / b $
begin
a = ( 1 @ ( 2 + 4 ) ) $
b = ( 0 & ( 2 + 4 ) ) $
end
Assuming
left-to-right evaluation of expressions, in determining the expression assigned
to a, SPoc would have to evaluate the
expression ( 2 + 4 ) in order to
perform the or evaluation. This evaluation is actually unnecessary, as
the first term is 1, the final answer
will always be 1, regardless of the
second expression. In the expression
set equal to b, a similar situation
occurs. The first term of the expression
is 0, therefore the and will produce a 0 as long as the second expression can be evaluated.
Using short circuit
evaluation, in special cases, as in the cases described above, SPoc will only
evaluate one of the expressions used in an and
or or. This would allow the following program to be evaluated.
program
one
declare a / b $
begin
a = ( 1 @ ( 1 / 0 ) ) $
b = ( 0 & ( 1 / 0 ) ) $
end
If
full evaluation was used and this program was run, an error of division by zero
would occur. However, short circuit
evaluation will set a to be 1, and b to be 0.
A
short circuit evaluation or can be
used with a full circuit evaluation and,
and vice-versa. Expressions will still
be evaluated correctly if this is the case.
However, it is less confusing and more practical to use both short
circuit evaluation and and or, or both full circuit evaluation and and or.
The SPoc grammar
allows for the use of blocks within the main SPoc program. Blocks are of the same form as main
programs. For example:
declare a / b $
begin
a = 1 $
b = 2 $
block one
declare a / b $ The variables a and b are set to zero
begin
a = 3 $
b = 4 $
print a $ The value 3 will be
printed
print b $ The value 4 will be printed
end
print a $ The value 1 will be
printed
print b $ The value 2 will be
printed
end
This program has a
block called one within the main
program, which declares two integer variables and assigns them values. These variables have the same name as those
defined in the main program add. These variables are not the same as the
variables defined at the top of the main program. The declarations within the block are set to zero at declaration,
but this does not affect the values of the variables with the same name in the
main program because they are different variables. When the variables are printed within one, the values assigned to them within the block are printed. When the block ends those variables go
away. When the variables with the same
name are printed in the main program body, they will show the values that they
were assigned before the block executed.
Another example:
declare a / b / c $
begin
a = 5 $
b = 7 $
c = 1 $
block add
declare a / x / y $
begin
a = 2 $
x = c $
y = ( a + x ) $
print y $
end
print a$
end
In this example, the
variable a is assigned the value
5. Within the block, the variable a is declared and is initialized to
zero. In the next statement, a is assigned the value 2. Therefore, in the expression defining y, (
a + x ) is equal to (2 + 1). Obviously, when y is printed, the value 3
will be printed to the screen. After
the block ends and a is printed, the value 5 will be shown.
5.15 Procedures in
SPoc
SPoc procedures are
defined at the beginning of a SPoc program, after the global variable
declarations. Procedures may be called
from the main program. For example:
globals
declare a / b $
procedure add ( c / d )
declare e $
begin
c = ( d + e ) $
print c $
return
program one
declare x / y $
begin
x = 4 $
call add ( 1 / 2 ) $
print x $
end
The procedure
definition begins immediately after the global variables are declared. The procedure has two formal
parameters. If more than one procedure
were to be declared, then the next procedure would begin immediately after the
return of the first procedure.
Another example:
declare
a / b / c $
begin
a = 1 $
b = 7 $
call add ( a / b ) $
print a $ 1
is printed
end
This example has two
procedures defined, one adds two numbers and prints the result, and the other
subtracts two numbers and prints the result.
The procedure add calls the
procedure sub, whereas the main
program calls the procedure add.
5.16 The Parsing of
a Procedure
When SPoc is parsing
a program, it looks for the reserved word procedure
after the global variables declaration section. If a procedure is found, then the function parse-procedure() is
called. This function gets the name of
the procedure, then calls parse-proc-list(). This function
creates a list called proc_list in which the
first element is the name of the procedure and the second is a list of the
contents of that procedure. In the
example below, proc_list shows a
procedure named add. This procedure has
two formal parameters, c and d.
One local variable e is
declared. There are two statements in
the procedure body, an assignment and a print statement. The procedure ends with the key word return.
(add ((c /
d)(declare)(e)($)(begin)(c)(=)((d + e))($) (print)(c)($)(return))
The recursive
function, parse-proc-list(), places each element of a procedure into proc_list
and recurses until the reserved
word return is found. Then it returns to parse-procedure() and this list
is appended to the environment (static-scope). The function then
looks for either of the reserved words program
or procedure. If procedure is found, then there is another
procedure declared, and parse-proc() is called
again. If program is found, then there
are no more procedures and we can begin parsing the main program. Parse-spoc() is then
called.
5.17
The Parsing and Interpreting of a Procedure Call
The function parse-stmt-list() is called
while parsing the main program. This
function looks for the reserved words: print,
block, call, return, and end.
If the word call is found, then the main program is
referring to a previously defined procedure.
The function parse-proc-call() is then
called.
This function gets
the name of the procedure (which follows the word call) and then sends the next expression (i.e. the parameters being
passed) to
parse-param-list(). This function finds the values of these variables
using search-scope() and puts the values into a list. This list is returned as a param_list.
Next, the procedure
list is found in the environment and copied to global-procedure-body. The flag is set to zero at this point,
indicating to get-next-expression that a procedure is being parsed. The first expression in the list of arguments is a list of the
names of the actual parameters, and is parsed in parse-passing-param(). This list, ((1)(2)), is renamed as
tempA. This statement is
sent to parse-param-list(). In this case, the
expression ( c / d ) would be sent, and ((c
0)(d 0)) would be returned as
param_list.
Param_list and tempA
are then sent to the function bind-variables(), and the list ((c
1)(d 2)) is returned. The function then parses the reserved word declare, and sends the decl_list
that follows to parse-decl(). The decl_list
and the param_list are combined
using the function append_list(), and this list is appended to static_scope.
The reserved word begin is parsed next, and the $ symbol
is tokenized. This is so that parse-stmt-list() can continue
as expected.
Parse-stmt-list() continues to
parse statements (flag is still zero) until the word return is found. When this
word is found, we are no longer parsing a procedure and the flag is reset to
1. The parameter list that was appended
to the environment (static_scope) is removed, and then $
is made into a token so that parse-stmt-list() can continue
correctly.
5.18
Also See References Attached
Robert W. Sebesta, Concepts of Programming Languages,
4th Edition, Addison-Wesley Publishing, Inc., Menlo Park, CA., 1999.