Transcript 10 Nov - Petrozavodsk State University

10 Nov
1. HW 3
Remember to submit a .jsp file:
•
•
•
for a valid int
for an int with errors
that produces the java program
2. Structure clashes
3. HW 4: Backtracking Exercise
Data structure for a
well-formed Integer
Possible errors
We want the error messages to be useful.
What are the different possible errors?
1. Start with non-sign, non-digit
2. Signed integer
i. Non-digit immediately after sign
ii. Non-digit in digit body
3. Unsigned integer
i.
Non-digit in digit body
Data structure for identifier with
possible errors
Simple Programs
The design method described above applies only to a class of "simple programs'.
A 'simple program' has the following attributes:
1.
The program has a fixed initial state; nothing is remembered from one execution to the next.
2.
Program inputs and outputs are serial files. There may be more than one input and
more than one output file.
•
•
•
3.
Each input and output file associated with the program is a tree structure and can be described with a
grammar for regular expressions
The input data structures define the domain of the program, the output data structures its range.
Nothing is introduced into the program text which is not associated with the defined data structures.
The data structures are compatible, in the sense that they can be combined into a program
structure as we done previously
–
–
The program structure derived from the data structures is sufficient for a workable program.
Elementary operations of the program language (possibly supplemented by more powerful or suitable
operations resulting from bottom-up designing) are allocated to components of the program structure
without introducing any further 'program logic'.
More complex programs:
Structure Clashes
Three types of structural clash:
1. Boundary clash (physical blocks on input
don’t coincide with logical groups on
output)
2. Ordering clash (wish report sorted by
named, input is unsorted)
3. Interleaving clash (wish to produce report
of user job times, inputs are interleaved)
Boundary clash example:
An accounting program may have a boundary clash between an input
file structured by months and an output file structured by weeks.
from Jackson JSP In Perspective (2001)
Examples: Boundary Clashes
Boundary clashes:
• The calendar consists of years, each year consisting of a number of
days. In one structure the days may be grouped by months, but by
weeks in another structure. There is a boundary clash here: the
weeks and months can not be synchronised.
• A chapter of a printed book consists of text lines. In one structure the
lines may be grouped by paragraphs, but in another structure by
pages. There is a boundary clash because pages and paragraphs
can not be synchronised.
• A file in a low-level file handling system consists of variable-length
records, each consisting of between 2 and 2000 bytes. The records
must be stored sequentially in fixed blocks of 512 bytes. There is a
boundary clash here: the boundaries of the records can not be
synchronised with the boundaries of the blocks.
Solution to Structural Clashes
• General view of problem
Structure diagram
• Solution: program decomposition
Program decomposition
There is no structure clash between A and I, so the
structure of PA can be constructed without difficulty;
the same is true of I and X and PB
Processing - general view:
1. Batch processing (пакетная обработка данных)
2. Parallel processing
3. Quasi-parallel processing (program
inversion)
program inversion
Program Inversion
инверсия программов
• We wish to design PA and PB independently of
each other so that the structure of each is based on
the data structure representation of its own
problem environment.
• Program inversion is a purely mechanical
transformation of the independent programs, PA
and PB, into a main program and subroutine
• The subroutine has a single ENTRY point and
stores its return address within its state vector so
that it is resumable.
HW 4: Backtracking Exercise
Warehouse (товарный склад)
A warehouse records a transaction for every
item received into or issued out of the
warehouse:
Transaction:
0-3 Item code
4 ‘+’ (in), ‘-’ (out)
9-10 initialization (контроль)
Backtracking Exercise:
Warehouse (товарный склад)
• At the end of the day, the transaction file is sorted by
item number, and a "Daily Net Movement Summary"
showing the net movement of each item into or out of the
warehouse is produced as shown below:
Daily Summary
A12345
40
A23456
-30
..........
Z13579
25
End Summary
Backtracking Exercise:
Warehouse (товарный склад)
1.
However, parts are to be included on the
report only if every shipment and order
transaction has been properly verified, as
indicated by a code in the initials field on each
transaction record.
2. Parts with one or more unverified shipment or
order transactions, indicated by a blank in the
initials field, should be written on an error
listing; they are not to be included in the report
(no total line should be generated).
Backtracking exercise
We don't know how many shipment and order transactions
exist for any part number.
– Thus, we don't know how many records we have to read in order
to recognize whether we have a part all of whose shipments and
orders have been verified.
– Need to use backtracking
Develop solution in 3 stages, creating a .jsp file for:
–
–
–
–
Stage 1 (ignoring the recognition difficulty
Stage 2 (using posit and admit)
Stage 3 (taking care of side effects)
Elaborated program structure