Browse Prior Art Database

Symbolic Interpretation / a Methodology for Transforming Programs Into Equivalent Ones

IP.com Disclosure Number: IPCOM000082224D
Original Publication Date: 1974-Oct-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Urschler, G: AUTHOR

Abstract

A methodology is provided for transforming programs into equivalent ones, both by modifying and copying program text. Its use is particularly in the area of program optimization.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Symbolic Interpretation / a Methodology for Transforming Programs Into Equivalent Ones

A methodology is provided for transforming programs into equivalent ones, both by modifying and copying program text. Its use is particularly in the area of program optimization.

A flow diagram can be viewed as an infinite tree, the branches of which are labelled by "elementary blocks" (sequences of assignment statements, denoted by A, B, C, ...). A node in this tree is either unlabelled (if it is the source of a single branch only) or labelled by a Boolean expression.

Since the infinite tree is derived from a finite flow diagram, there is only a finite number of different subtrees (subprograms) in it, de denoted by Alpha , Beta , Gamma , ... . These subtrees can be described by equations of either the form Alpha = A Beta (in the case where Alpha is the root of a single branch only), or the form Gamma = [ B Nu Absolute Value of C Epsilon ] (in the case a decision p denotes the involved Boolean expression which, for convenience, is assumed to be a Boolean variable).

Such programs get a meaning (a semantics) by interpreting elementary blocks as functions (transformations) over a set of state descriptors (data spaces), and by providing them with a control mechanism. The latter is commonly given by both sequencing (if Alpha is the subprogram to be executed, Alpha = A Beta , and execution is to be performed with respect to the state descriptor Sigma ' - denoted by Sigma . Alpha - then Sigma . Alpha results in A Sigma '.

Beta, where Sigma ' is the result of applying A to Sigma ) and selection (if Gamma = { B Upsilon Absolute Value of C Epsilon }, then Sigma . Gamma results in either B Sigma '. Upsilon or in C Sigma ".

Epsilon in an analog...