CS461: Programming Languages

CS461: Programming Languages

Week 2

Design of Pseudocode

(one similar to L1 and L2 developed by Bell Labs for the IBM 650 in 1955-56)

Computer has 2000 words of 10-digit memory

Facilities we want include:

-floating point arithmetic (+, - , *, /, sq root)

-floating point comparisons (=, >, <, >, <=, >=)

-indexing

-transfer of control

-I/O

No alphabetic I/O => use numeric codes

1 number (representing operation) on each card (10 digits)

addresses size? 2 digits => 100 locations NO!

4 digits => 10,000 locations NO!

3 digits => 1000 locations (other 1000 for interpreter and program)

(3 digits will not allow addressing outside of the 2000 words)

Security principle – no program that violates the definition of the language, or its own intended structure, should escape detection

Instruction format

Instructions could have 2-4 addresses:

- 2 x <- x+y

- 3 z <- x+y

- 4 w <- x+y+z

each address must be represented in the instruction

4 addresses require 12 digits for operand addresses (we only have 10 digits)

2 addresses require 6 digits, leaves 4 digits for operations (10,000 operations, only need 13)

3 addresses require 9 digits for operands, leaves 1 digit for operation (with sign gives us 20 operations)

format for arithmetic instructions

s op opn1 opn2 dest

+1 010 150 200 blanks just help us to read, actually +1010150200

add contents of 010 to contents of 150 store in 200

Orthogonal Design

Difficult to remember code, want pseudocode simpler and more regular than machine code

Put arithmetic operations in pairs (+, -) (*, /) (sq, sqrt)

Orthogonal language design

2 independent mechanisms

-digit (1, 2, 3) selects class (additive, multiplicative, quadratic)

-sign selects direct or inverse

Orthogonality Principle : independent functions should be controlled by independent mechanisms

Corollary to

Regularity Principle: regular rules, w/o exceptions, are easier to learn, use, describe, and implement

Why it simplifies? Arbitrary assignment of digit to operations is hard! Must remember 20 independent facts. We made distinction between direct, inverse => now 12 independent facts.

Orthogonal means right-angled

Too much orthogonality can hurt, if we include facilities simply for symmetry

Some mn possibilites useless or difficulty to implement, some illegal (then we have to remember exceptions, violating regularity principle)

Advantage if m+n+e < mn – e (where e are number of exceptions)

+4 200 201 035

= goto instruction

Adopt convention that 000 contains the number zero

Exercise: How to do an unconditional jump?

Moving

Moving can be done by adding 0 +1 150 000 280 inefficient with floating point arithmetic

Use +0 for move. Why not +6???

Exercise: What should –0 be? Should not be easily accomplished with other operations.

Indexing

Need address of array, address of index variable

Only one address left: so we can only move them to and from

+ 6 move from z <- x[i]

- 6 move to x[i] <- z

Use of arrays => want a loop

Initialize, increment and test index variables w/o floating point

Abstract out code common to all loops, eliminate other source of operation => Automation principle and

corollary, Abstraction principle

Abstraction Principle: Avoid requiring something to be stated more than once; factor out recurring pattern

+0 initialize indices

+7 increment and test -7? Decrement and test/or undefined

+7 iii nnn ddd

index upper addr of

bound loop start

I/O

+8 read one operand from card into a location

-8 print contents of a memory location

Program Structure

Now we know how to write instructions, but not program as whole

1)how to arrange program loading

2)initialization of locations in memory

3)provide for input data for program

Interpreter reads initialization cards and stores contents in consecutive memory.
Program starts with declarations, then executable statements followed by input data.

CS461: Programming Languages

Homework: Due: Thursday

Exercise: How to do an unconditional jump?

Exercise: What should –0 be? Should not be easily accomplished with other operations.

Exercise: Read in coefficients of quadratic equation (a, b, c), print both roots (if they exist).

ax2 – bx + c = 0

If b2 – 4ac = 0, 1 real root which is –b/2a

______

If b2-4ac > 0, then there are two roots -b + \/ b2 – 4ac

------

Implementation of interpreter for pseudocode

(iterative, not recursive)

-investigate how we’d execute by hand first

-need to record state of computation (contents of data memory, program and record of place in it)

2 major data structures – 2 “arrays”

Fetch-Execute cycle

1) Fetch next instruction (and advance IP) why here? Step 3 must change IP for jumps…

2)decode it

3)execute it

4)go to step 1…so can’t do normal IP increment here

step 1: instruction := program [ip] NOTE: this would be written in machine language

ip ++;

step 2: decode instruction

a) extract sign, op code, 3 address fields +d ddd ddd ddd

dest addr ,_ abs(instruction) mod 1000

b)determine kind of operation – specified by op and sign fields

if sign is ‘+’ then

case op of

0: move;

1: add;

9: stop

end case

else {sign is ‘-‘}

case op of

0: exercise;

1: subtract;

end case

computational instructions

multiply: data[dest] := floating product (data[opnd1], data[opnd1]) NOTE: product is a subroutine

control flow instructions

IP must be altered, if test satisfied

Test EQUALITY:

If floating equality (data[opnd1], data[opnd2]) then

ip := dest;

NOW all we need is a loader to initialize and load program cards.

Statement labels

Aid coding

Eliminate absolute locations (modify programs easier)

Need a label definition operator

-7 0LL 000 000

00-99 so use 100-element label table

NOT EXECUTABLE, marks place in program

Jump instructions now refer to symbolic labels

Test equality: +4 xxx yyy 0LL

To interpret it, look up 0LL in table, get equivalent address

Build label table as program read into program memory

INTERPRETERS CAN AID DEBUGGING

LOADING

All labels defined before execution begins, increase security to ensure all labels defined! Security principle.

So put a –1s to initialize label table

When we encounter -7 instruction defining label, ensure label not already defined

When we reference a label in instruction, ensure it is defined

Use –2 for referenced, but not defined

When it is later defined, replace -2 with absolute location

At the end of loading, check for –2’s

Variables can be processed just like labels!!!

Construct a label table - symbolic labels still in form of 3 digit numbers.

Symbolic pseudocode

Hard to remember -2 or –3 is divide? Whether 111 is an index or temporary variable? Must keep track manually!

Use mnemonics (automation principle) and then translate with assembler.

3-4 char alphanumeric name

ADD

MOV look up in symbol table to replace with codes

READ

ADD TMP SUM SUM which means sum <-tmp + sum

FIXED format col1-4: op col6-8: opnd1 col10-12: opnd2 col14-16: dest

UPPER CASE

Declarations

END ------ 9999999999

Statements

END ------ 9999999999

Declarations

VAR var-name type # locations variable occupies

Intial value

FIG. 1.6

Loader-translates source -> intermediate numeric pseudocode

Interpreter

Summary

Pseudocode interpreters simplify programming

-virtual computer more regular and higher level than physical

-automation

-security (undec. Ids, out-of-bounds)

-simplified debugging by providing tracing

Floating point HW made interpreters unattractive

Decoding causes overhead to be added by about factor of 10

Pascal -> pcode -> machine code or interpreted

Libraries -> compiling routines

Translation and decoding done once

Compiled programs are faster

Interface overhead with libraries less efficient than 50’s assembly language

OPERATIONOP1OP2DSTCOMMENTS

VARZRO1CONSTANT ZERO

+0000000000

VARI1INDEX

+0000000000

VARSUM1SUM OF ARRAY

+0000000000

VARAVG1AVERAGE OF ARRAY

+0000000000

VARN1NUMBER OF ELEMENTS IN ARRAY

+0000000000

VARTMP1TEMPORARY LOCATION

+0000000000

VARDTA990THE DATA ARRAY

+0000000000

END

READNREAD NO. OF ELEMENTS

LABL20

READTMPREAD INTO TEMP

GETMPZRO40IF POSITIVE, SKIP TO 40

SUBZROTMPTMPNEGATE TEMP

LABL40

PUTATMPDTAIMOVE TEMP INTO I-TH ELEMENT

LOOPIN20LOOP FOR ALL ARRAY ELEMENTS

MOVEZROIREINIT INDEX TO ZERO

LABL50

GETADTAITMPADD I-TH ELEMENT

ADDTMPSUMSUM TO SUM

LOOPIN50LOOP FOR ALL ARRAY ELEMENTS

DIVSUMNAVGCOMPUTE AVERAGE

PRNTAVGAND PRINT IT

STOP

END