SE Code Restructuring

ETH

Eidgenössische Technische Hochschule Zürich

Swiss Federal Institute of Technology Zürich
Reverse Engineering

Code Restructuring Mainframe
Guest Lecture
Session: Basic Techniques
October 2007 – 3rd Version
presented by
Dipl. Ing. Werner Hoffmann
A member of IEEE and ACM
EMAIL: pwhoffmann@tonline.de Please see the

notes pages for

See: © Copyright Note in Note Page. additional
Date: 27.10.2007 comments.
Page: 1
SE_CodeRestructuring.ppt
Audience
Reverse Engineering At least this session may be

Code Restructuring interested for:
© 2007
• Researcher for Education /

Training,
• IT Professionals,
• Professors, and Students.
"Learning is
experience.
Everything else is
information.“
Albert Einstein.
Date: 21.06.2007 Code Restructuring Page: 2

Agenda
• Introduction
• Review: Structured Programming
• Basic Code Restructuring Methods
• The Spaghetti Bowl Approach
• Indecomposable program figures
• Conclusion
Note: Some exercises are available!

Agenda
• Introduction
• Conclusion
"You do not really
understand something
unless you can explain it to
your grandmother."
Albert Einstein.

Introduction (1)
Learning to write computer programs is not easy:

• Students have difficulty learning programming as they are trying to
develop skills in three areas at the same time, these
being:
You need to improve
• using the program development environment; your unstructured
code –
• learning the programming language syntax; this session might
• and developing logic design. be right for you…
• With respect to the above, good pedagogy therefore

requires the instructor to keep initial facts, models, and
rules simple and only expand and refine them as students
gain experience.
This session is about “Code Restructuring”. As a

result students should get better understand what
“structured programming” means.
Introduction (2)
Defining the 'R' words for maintenance:

• Reverse Engineering,
• Restructuring,
• Reusability.
Definitions for the most common "buzz words" in the field

of reverse engineering:

This session is about
“Restructuring”.
• Forward Engineering,
• Reverse Engineering ,
• Re-documentation ,
“Insanity: doing the
• Design Recovery , same thing over and
• Restructuring , over and expecting
• Reengineering . different results.”
Albert Einstein.

Introduction (3)
This session is about “Restructuring”:

• Software Restructuring:
• transforms a program’s source code into a more
‘‘structured’’ form, thereby improving its
maintainability and prolonging its life.
• Motivation:
• Software Maintenance
• Structure of a program refers to:
• structure of the code,
• structure of the system.
We only look at the
structure of code.

Introduction (4)
This session is about “Code Restructuring”:

• Software Restructuring:
We only look at a method
• Restructuring Stages: for Code Level
Restructuring.
• Code Level Restructuring,

• Data Restructuring,
• Procedural Restructuring, and
• Re-modularization.
Note: Before you start a Code Restructuring task, take a short Analysis about program
understanding:
Program understanding is the process of developing mental models of a software system, at

various levels of abstraction (top-down, bottom-up, or opportunistic strategies).
If you find a very bad design, a bad solution (which may address one of the other points
mentioned above),
Date: 21.06.2007
Code Codeyour
Restructuring may not help to solve Restructuring
problem! Page: 8
Introduction (5)
Example:
(Convert Julian date into
Gregorian date)
Bad Design/Solution
Don’t try to
restructure this code.
The problem here is
missing data
structures to solve
the problem!
It’s a problem of
data restructuring,
not a problem of
code restructuring!
Introduction (6)
Example:
(Convert Julian date into Gregorian date)
A better solution:
Note: This coding may not be a perfect solution; but

may be a good starting point for further
investigations.
Introduction (7)
Previous Research:
• Basic works: Dijkstra – debate over the use of GOTO statement.
• Code and Procedural Restructuring: Böhm and Jacobi – transform
arbitrary flow diagrams into structured flow diagrams.
• Ashcroft and Manna extended this by introducing an algorithm for
transforming arbitrary “goto programs” into equivalent “while
programs”.
• Peterson showed how to transform any program into “well-formed”
program, that only use if, repeat, and multi-level exit statements.
• Yourdon introduced a boolean flag approach to eliminate multi-exit
loops.
• Linger introduced a technique for parsing arbitrary flowgraphs into
their prime components: sequence, if-then-else and while-do.
• There are published several work available for a fully automatic
FORTRAN “structure engine”. Additional several work where
published to restructure COBOL programs.

Introduction (8)
• As noted previous this session is about code level

restructuring:
• Code refactoring:
• A code refactoring is any change to a
computer program's code which improves its
readability or simplifies its structure without
changing its results.
• Note that I do not want to create the impression
that this is an easy job, though.
• I’m using flowcharts to show a manually driven method to
transfer unstructured code
Used symbols: 1 into A
structured
p code.
• The method don’t change data dependency!
To be independent , I will show

• This method is completely independent from
Code only as Pseudoany
Code.computer
language.
Introduction (9)
Refactoring dos and don'ts

Do:
• Refactor in stages. Thoroughly test at each stage of the refactoring
process.
• Apply refactorings that will make adding new function easier before
adding those new functions. This may seem obvious, but it's often
tempting to get new functionality working before cleaning up the code.
• Accept that some refactorings will look good on paper but may add
more
complexity to your code. Be prepared to back them out.
Don't:
• Try not to refactor based on what you think future requirements will
be.
Refactoring is based on the state of things today.

Introduction (10)
An Example:
“Spaghetti-Code”,
Unstructured Flowchart.
…copied from IBM Independent Study Program,

Structured Programming.

Introduction (11)
An Example:
Our goal:
Structured Flowchart,
Structured Pseudo-Code.
Levels of Indentation
1-4
…copied from IBM Independent Study Program,

Structured Programming.

Agenda
• Introduction
• Review: Structured
Programming
"Great thinkers have
• Conclusion always encountered
opposition from mediocre
minds."
Albert Einstein.

Review: Structured Programming (1)
I like to look at following main points:
1. Basic Control Logic Structures
3. Equivalent Control Logic Structures
5. Proper Programs
“Intellectuals solve
problems. Geniuses
prevent them.”
Albert Einstein.

1) Basic Control Logic Structures:

1. Single Block:
A
1. IF THEN ELSE Block:

T A
p 1
F B
1. DO WHILE Block:
A
T
F
1 p

2) Control Logic Structure Equivalences:

Example 1: REPEAT UNTIL Block:
Basic Control Logic Structure: Pseudo-Code:
A A
T DOWHILE (p)
F
A 1 p A
ENDWHILE
Equivalent Control Logic Structure:

Pseudo-Code:
F where q = ¬p
T REPEAT
1 A q A
UNTIL (q)
REPEAT_UNTIL (q)


Pseudo-Code:
Example 2: CASE Block:
IF p1
THEN F1
ELSE IF p2
THEN F2
Basic Control Logic Structure: ELSE …
… IF pn
THEN Fn
T F1 ELSE Fotherwise
ENDIF
p1 1 …
T F2
ENDIF
F p2 2 ENDIF
T Fn
F Pseudo-Code:
… pn n
CASE_ENTRY
F CASE (p1) F1
Fotherwise
CASE (p2) F2
…
CASE (pn) Fn
OTHERWISE Fotherwise
END_CASE

- You can use/define additional equivalent program structures:
Pseudo-Code:
- For example DO v = exp1 TO exp2 BY exp3
F1
- Iterative DO ENDDO
LOOP
- LOOP’s F1
EXITIF (p1)
…
- CASE block’s Fn
ENDLOOP
- SEARCH block’s SELECT (exp)

CASE (1) F1
CASE (2) F2
- etc. …
OTHERWISE Fotherwise
ENDSELECT
etc.
3) Proper Program (example) :

1 Levels of Indentation
1-3
3
F
T Pseudo-Code:
p3
DOWHILE (p1)
B IF (p2)
THEN DOWHILE (p3)
B
A ENDWHILE
2 ELSE A
ENDIF
p2 ENDWHILE
F T C
p1
T
F
The goal is to construct
C a well defined hierarchy
for the solution.

Agenda
• Introduction
• Basic Code Restructuring
Methods
"I have no special talents. I
• Conclusion am only passionately
curious."
Albert Einstein.

Basic Code Restructuring Methods
“Imagination is more important

than knowledge. Knowledge is
limited, imagination circles the
world...”
Albert Einstein.
• For the code restructuring process I use a

flowchart of the unstructured program.
• In the following foils I explain basic
transformation methods.
• The goal of the transformation is to get
basic structured control logic figures (BLOCK,
IF_THEN_ELSE, and DO_WHILE).
“Example isn't
Interchange
another way to
(2)
teach; it's the only
way.”
Albert Einstein.
1) Interchange - Example:
T F
p
T F
p
A B
A B
1
1
Interchange
1/2
2
2
T T
q C q C
F F
Unstructured Code Structured Code:

IF_THEN_ELSE, DO_WHILE
Transposition (1)
2) Transposition:
A
1 A = 1
1 = 1 A

Transposition (2)
2) Transposition (continued) :
A
T T
A p = p
F F
A
A
T T
p = A p
F F
A

Transposition (3)
2) Transposition - Example:
T F
p
T F
p B
A
D
A B
1
1
Interchange Transposition
1/2 D
2
2
T D
q C T
q C
F
F

Combination (1)
3) Combination:
A B = A,B
F1 F2 F3 = F3,F2,F
1

Combination (2)
3) Combination - Example:
T F T F
Combinati
p p
T F
p B
on
A A B,D
D
A B
Transposition
1 1
1
Interchange
Combination
1/2 D
2 2
2
T D C,D
q C T T
q C q
F
F F
Step 1: Step 2:
Structured Code:
Unstructured Code
Resolution (1)
4) Resolution:
a c a 1 A 2
1 A 2 m =
b b 4 A 3 m

Resolution (2)
4) Resolution - Example:
T F
1 2 p
T F B
p A
2
A 1
B
D D
1,2
1 D 2 2 1
T T T
q C q C q C
F F F
3

(first step)
Resolution
Substitution (1)
5) Substitution:
A
T
F
1 p = DoW (p) A
Means: DO_WHILE
F
T
1 A q = Rep A U(q)
Means:
Entry REPEAT_UNTIL
A
“proper program” = PGM x
x
Exit

Combination (2)
5) Substitution - Example:
T F
p
A B,D
1 SPGM S1
Substitution
S1
2
C,D
T
q
Structured Code
Inverse Notation (1)
6) Inverse Notation:
F T
p = ¬p
T F
A A
F T
T F
1 p = 1 ¬p
Means: DO_WHILE
T F
F T
1 A q = 1 A ¬q
Means: REPEAT_UNTIL
Agenda
• Introduction
• Conclusion
"Today's problems
cannot be solved
with the level of
thinking that
created them.”
Albert Einstein.
The Spaghetti Bowl Approach (1)
Method:
Draw a flowchart of the unstructured program logic. B 2 C
DO WHILE Spaghetti Bowl 1)

T
I nput line
p D
FOR each Spaghetti Bowl DO F
A 1 q
T
F
output line
Find an input line and an output line. 2) SB
Pull at the initial line and observe what comes out.

Proceed with following rules: 3) T
Rule 1: You watch a condition: p
Assume a IF_THEN_ELSE construct; F

Use the “Resolution method” following both
paths.
Rule 2: You watch a node with 2 input lines:
Assume a DO_WHILE construct; 2
Use restructure methods as described earlier
to get a DO_WHILE construct. A
Rule 3: You watch an indecomposable program structure; 2
T T
Special action is needed (see next section) . 1 p B q
F
Check and Cleanup flowchart. 4) F
Use restructure methods as described earlier.

END
Note: This technique can be
END
used for every problem; no
Rebuild complete source code using the structured Flow-
matter how complex this
Chart or Pseudo-Code.
problem may be.
Optionally redesign additional equivalent program structures. 5)
Step 1: Draw a flowchart of the unstructured code.
B 2 C
T
Input line
p D
F T output line
A 1 q
F

Step 2.1: Conceal the complete program logic except for

an initial line and an exit line.
B 2 C
T
Input line
p D
F T output line
A 1 q
F
SB

Step 2.2: Conceal the complete program logic except for

an initial line and an exit line.
B 2 C
T
Input line
p D
F T output line
A 1 q
F
SB
Rule 1 : There is a condition, we assume a IF_THEN_ELSE construct.

Step 2.3: Result
B 2 C
D
T
T 1 q
Input line F
p
output line
F 2 C
3
D
T
A 1 q
F

Step 3: Cleanup each SB.
B 2 C
D
T
T 1 q
SB1 F
Input line
p
output line
F 2 C
SB2 3
D
T
A 1 q
F
IF_THEN_ELSE
Step 3.1: Cleanup SB1 - Result.

SB1 C
T
B 2 D q
T F
Input line
p
output line
F 2 C
SB2 3
D
T
A 1 q
F

Step 3.2: Cleanup SB2 - Result.

SB1 C
T
B 2 D q
T F
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F

Step 3.3: Result after cleanup SB1 and SB2.

C
SB1
T
B 2 D q
T F
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F

Step 4: Repeat SB Approach for SB1 and SB2.

C
SB1
T
B 2 D q
T F
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F

Step 4.1: Repeat SB Approach for SB1.

C
SB1
T
B 2 D q
T F
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F

Step 4.1.1: Repeat SB Approach for SB1.

C
SB1
T
B 2 D q
T F
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F


Rule 2 : There is a node with 2 input
C
lines, we assume a DO_WHILE
construct. T
B 2 D q
T F
SB1
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F


A DO_WHILE construct does not have a C
code block on the input line; we need
to transport block D using the
Transposition method. T
B 2 D q
T F
SB1
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F


1) A DO_WHILE construct does not C,D
have a code block on the input line; we
need to transport block D using the
Transposition method. T
B,D 2 q
T F
2) Additional we use the Combination
method to cleanup the flowchart.
SB1
Input line 3)
p
output line
F
SB2 3
C,D
T
A 1 q
F


C,D
T
B,D 2 q
T F
SB1
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F

Step 4.1.5: Result for SB1.

C,D
T
B,D 2 q
T F
block DO_WHILE
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F


C,D
T
B,D 2 q
T F
block DO_WHILE
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F


C,D
T
B,D 2 q
T F
block DO_WHILE
Input line
p
output line
F
SB2 3
Rule 2 : There is a node with
2 input lines, we assume a
C,D
DO_WHILE construct.
T
A 1 q
F

Step 4.2.3: Result for SB2.

C,D
T
B,D 2 q
T F
block DO_WHILE
Input line
p
output line
F
SB2 3
C,D
T
A 1 q
F
block DO_WHILE
Step 5, 5.1: Check flowchart.

C,D
T
B,D 2 q
T F
block DO_WHILE
Input line
p
Same Code, we can use the
transportation method to
F simplify the control structure.
3
output line
C,D
T
A 1 q
F
block DO_WHILE
Step 5.2: Result.

B,D C,D
T T
Input line
p 1 2 q
F output line
F
A
IF_THEN_ELSE DO_WHILE
Pseudo-Code: IF p
THEN {B,D}
ELSE A
ENDIF
DOWHILE q
{C,D}
ENDWHILE

Step 6: Rebuild source code
. using the final structured flowchart, or

. the structured Pseudo Code.
Step 7: Optionally check whether additional equivalent

program
figures like iterative loops, search-blocks etc.
may
improve the reading/maintenance of the
program.
• If this is the case, analyze the code and
rewrite the logic using predefined equivalent
Note: Doprogram elements.
not forget to test the new code !!!
Agenda
• Introduction
• Indecomposable program
figures
• Conclusion "The secret to creativity
is to know how to hide
your sources.”
Albert Einstein.

Indecomposable program figures (1)
Indecomposable program figures can be restructured by

adding a special flag construct to the program figure:
Terms:
TRUE - allocate flag and set value to TRUE.

FALSE - allocate flag and set value to
FALSE.
POP - deallocate flag.
TOP - Test Flag.

Example: Unstructured control flow.

A
T T
1 p B q
F
F
Structured control A TRUE

flow: T
TRUE 3 TOP POP
T T
TRUE 1 POP p B q 2 F
F
F
FALS
E

Example: Structured control flow.

A TRUE
T
TRUE 3 TOP POP
T T
TRUE 1 POP p B q 2 F
F
F
FALS
E
Pseudo-Code: TRUE
REPEAT
POP
IF p
THEN {A,TRUE}
ELSE {B, IF q
THEN TRUE
ELSE FALSE
ENDIF}
ENDIF
UNTIL TOP
Agenda
• Introduction
• Conclusion
"Everybody is a genius. But
if you judge a fish by its
ability to climb a tree, it will
spend its whole life thinking
its stupid."
Albert Einstein.
Conclusion (1)
Exercise: Describe methods/rules to restructure this code

!

Conclusion (2)
Benefits:
• What benefit’s do we expect?
• We can identify:
• deleting ‘dead’ code,

• deleting unnecessary branches,
What we cannot • recognizing loop structures,
expect: • improving loop bodies.
“A simple design is an outline for a small

software component. It has the smallest
number of features that meet the requirements
of the current phase. As simple as possible, but
not simpler.” Albert Einstein.

Conclusion (3)
PROGRAMMING AS A PROCESS:
“Of course! Why
didn't I ever think of
• A Revolution in Programming? that?”
D.E. Knuth.
• Programming starts with a problem and ends

with an efficient solution..
• … what is more difficult: finding a solution or
refining it.
• Programming is program development,
• Development goes in small steps,
• Programming goes stepwise,
• thus, programming means structuring,
• it may also mean: sub-structuring the
objects,
• introducing “data structures”.
Conclusion (4)
Closing remarks:
• After this session you should know how to
restructure a unstructured flowchart into a structured
form by using a manually procedure which includes 6
basic transformation methods and 3 additional rules
to deal with more complex programs.
• The resulting flowchart /pseudo-code can be used to
rebuild the source code into a structured format.
• The final result may be a starting point for further

work,
• like “bug” fixing,
• performance optimization,
• maintenance tasks,
• other reverse engineering tasks.
Conclusion (5)
…! ? GOTO…
“Not everything that can be

counted counts, and not
everything that counts can be
counted.”
Albert Einstein.

Source
See:
Web page
http://www.refactoring.com/
http://istpub.berkeley.edu:4201/bcc/Fall2004/refactoring.html
Discussion site on code smells: http://c2.com/cgi/wiki?CodeSmell
Books:
• Software Productivity, Harlan D. Mills, 1988
• General Principles of System Design, Gerald M. Weinberg & Daniela
Weinberg
• Rethinking System Analysis & Design, Gerald M. Weinberg
• Program Development by stepwise transformation, F.L. Bauer, Springer
Berlin
• Refactoring: Improving the Design of Existing Code, by Martin Fowler (et
al.),1999, Addison-Wesley
• Additional publications:
• Using Hammock Graphs to Structure Programs, Fubo Zhang and Erik H.
D’Hollander, Member, IEEE
• An Algorithm for Structuring Flow graphs, Brenda S. Baker
• Restructuring Control Flow of IBM/370 Assembler Programs, Michael
Ricking
• A Non-Deterministic Approach to Restructuring Flow Graphs, Toni A.
Bünter, TR CUCS-019-93 Columbia University
• Code Cleanup Idioms, Ninad
Date: 21.06.2007 Jog
Code Restructuring Page: 70
• Aggressive Function Inlining with Global Code Reordering, IBM, H-0247,
Discussion (1)
Now let’s start discussion…

Reverse Engineering
Code Restructuring
© 2007
“Computers are incredibly

fast, accurate, and stupid;
humans are incredibly slow,
inaccurate and brilliant;
together they are powerful
beyond imagination.”
Albert Einstein.

Discussion (2)
Q/A:
Not just prepared…
-You’ll get a final paper until next
session.
Requests:
1) Exercises – ok. I prepare some examples
…

Questions / Comments…
???
Questions, comments, further
information?
Please feel free to e-mail me!
Dipl.Ing. Werner Hoffmann
EMAIL: pwhoffmann@tonline.de or
[email protected]
Date: 27.10.2007 SE_CodeRestructuring.ppt Page: 73
The End…
Code Restructuring

I tha
n
for y k you
o
atte ur
ntio
n!
“The most beautiful thing we can

experience is the mysterious.”
Albert Einstein.

SE Code Restructuring

Uploaded by

Copyright:

Available Formats

SE Code Restructuring

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

SE Code Restructuring

Uploaded by

Copyright:

Available Formats

ETH

Eidgenössische Technische Hochschule Zürich

EMAIL: pwhoffmann@t­online.de Please see the

Reverse Engineering At least this session may be

• Researcher for Education /

Date: 21.06.2007 Code Restructuring Page: 2

Note: Some exercises are available!

Date: 21.06.2007 Code Restructuring Page: 3

Date: 21.06.2007 Code Restructuring Page: 4

Learning to write computer programs is not easy:

• With respect to the above, good pedagogy therefore

This session is about “Code Restructuring”. As a

Defining the 'R' words for maintenance:

Definitions for the most common "buzz words" in the field

Date: 21.06.2007 Code Restructuring Page: 6

This session is about “Restructuring”:

Date: 21.06.2007 Code Restructuring Page: 7

This session is about “Code Restructuring”:

• Code Level Restructuring,

Program understanding is the process of developing mental models of a software system, at

Note: This coding may not be a perfect solution; but

Date: 21.06.2007 Code Restructuring Page: 11

• As noted previous this session is about code level

To be independent , I will show

Refactoring dos and don'ts

Date: 21.06.2007 Code Restructuring Page: 13

…copied from IBM Independent Study Program,

Date: 21.06.2007 Code Restructuring Page: 14

…copied from IBM Independent Study Program,

Date: 21.06.2007 Code Restructuring Page: 15

Date: 21.06.2007 Code Restructuring Page: 16

I like to look at following main points:

1. Basic Control Logic Structures

3. Equivalent Control Logic Structures

Date: 21.06.2007 Code Restructuring Page: 17

1) Basic Control Logic Structures:

1. IF THEN ELSE Block:

Date: 21.06.2007 Code Restructuring Page: 18

2) Control Logic Structure Equivalences:

Basic Control Logic Structure: Pseudo-Code:

Equivalent Control Logic Structure:

Date: 21.06.2007 Code Restructuring Page: 19

2) Control Logic Structure Equivalences:

2) Control Logic Structure Equivalences:

- SEARCH block’s SELECT (exp)

3) Proper Program (example) :

Date: 21.06.2007 Code Restructuring Page: 22

Date: 21.06.2007 Code Restructuring Page: 23

“Imagination is more important

• For the code restructuring process I use a

Unstructured Code Structured Code:

Date: 21.06.2007 Code Restructuring Page: 26

Date: 21.06.2007 Code Restructuring Page: 27

Unstructured Code Structured Code:

Date: 21.06.2007 Code Restructuring Page: 29

Date: 21.06.2007 Code Restructuring Page: 31

Unstructured Code Structured Code:

Date: 21.06.2007 Code Restructuring Page: 33

DO WHILE Spaghetti Bowl 1)

FOR each Spaghetti Bowl DO F

EMAIL: pwhoffmann@tonline.de Please see the