.if !\n(xx .so tmac.p
.ND
.nr H1 0
.NH
Design Considerations
.NH 2
Goals
.PP
As more fully described in [1], the goals of this
Berkeley
Pascal system are:
.IP
.RS
.HP 1) 
To provide an easily usable teaching tool.
.IP 2)
To provide high-quality diagnostics to the user.
.IP 3)
To provide fast compilation at the expense, if necessary,
of execution speed.
.IP 4)
To faithfully implement Pascal 6000\-3.4 as described in [5], and
to be as compatible as possible with the
.SM CDC
implementation of the language.
.RE
.PP
The Pascal execution profiler, hereafter referred to simply as
.XP ,
results from the second design goal.
The system, however, would benefit
greatly from a more complete debugging facility.
A design for an
interactive and post-mortem debugger
.I pdb
for the system exists [6], but
has not been implemented as of this writing.
.NH 2
Placement of statement counters
.NH 3
Basic considerations
.PP
Execution profiling is quite simple in concept.
One merely places
counters at a sufficient number of points in the program to allow
the determination of the number of times each statement has been executed.
Knuth, in [7], gives an algorithm for determining the minimum number
of counters necessary to gather complete information.
.PP
Berkeley
Pascal code is interpreted.
Thus the addition of statement counters
does not tend to have a significant degrading effect on the speed of execution.
Even in heavily travelled loops, a statement counter is of low enough
execution cost that techniques for, e.g., moving counters out of
.B for
loops were determined to be unnecessary.
More complicated techniques
such as determining the number of calls on a 
.B procedure
or
.B function
by adding together the call counts for all calling sites would
not materially decrease the time in execution and would add significantly
to the complexity of the post-processing.
It was thus decided not to do
any counting optimization of this type.
.NH 3
Goto statements
.PP
A more subtle consideration involved non-local 
.B goto
statements.
Without global
analysis, which was not available in the one-pass compiler scheme being
used, there is always the possibility that an arbitrary 
.B procedure
or
.B function
call will not return to the calling site.
To maintain
accurate counts and a simple scheme when non-local
.B goto
statements are allowed
would likely involve the placement of a counter after each such
.B procedure
or
.B function
call.
The presence of these extra counters could easily multiply the number
of counters
required for typical programs by a factor of 5 or more.
.PP
As 
.B goto
statements which cut across levels of control tend to be used
only in infrequently occurring error situations, it was decided not to place
counters to allow for non-local 
.B goto
statements.
Counters are not placed after each
.B procedure
and
.B function
call so,
if a call fails to return, the counts will be inaccurate to
the next sampling point.
.PP
An option to allow for correct counts in the presence of non-local 
.B goto
statements
was considered, but rejected.
It was felt that 
such an option would rarely, or never, be used.
It is the author's belief that
summary data flow information indicating possible non-local
control transfers would be necessary if the placement of counters were
to be done appropriately.
.NH 3
Counter placement rules
.PP
Thus, it was decided to place counters at the following program points:
.IP
.RS
.HP 1)
At the entry point to each
.B function
and
.B procedure .
.IP 2)
In the
.B then
part of each
.B if
statement.
The
.B else
part
of each
.B if
statement is counted by subtracting the count for the
.B then
part from the pre-statement count.
.IP 3)
In the body of each
.B repeat ,
.B while ,
and
.B for
loop.
.IP 4) 
On each case of a
.B case
statement, with one counter
for each group of case labels.
.IP 5)
After each
.B goto
statement.
.IP 6) 
Before any statement which has a
.B label
preceding it.
.RE
.PP
The counts are made completely accurate in the presence of local 
.B goto
statements
by placing an extra counter after each
.B if ,
.B repeat ,
.B while
and
.B for
statement which contains a
.B goto .
If there is no
.B goto
statement in such a statement,
the count after the statement is taken to be the count before the statement.
.PP
It was later suggested to the author that one could count the frequency
of each individual label in a
.B case
statement, rather than keeping one count for each group.
This might provide useful information for some programs,
but has not been implemented
as an option.
.NH 3
Partial program counting
.PP
A final consideration related to the placement of counters over parts
of the program only.
This would surely be desirable if gathering profile data were expensive.
In this case a
user might be able to restrict his cost by specifying which
parts of his code were to be counted.
After it was decided
that the profile listing would be constructed by reparsing
the source text of the program and combining it with the profile data,
it seemed clear that the savings from such partial counting would not
materially affect the overall cost of producing a profile.
It was therefore decided to allow selectivity of profile output
in
.XP
rather than selectivity of count gathering at compile or
execute time.
.NH 2
Producing the profile
.PP
Given the collected data in the form of an array of statement counts,
one then wishes to produce a listing of all or part of the program
with the count information appended in an easily understandable form.
It seems clear that a system which presents the count information
to the user with associated source text from his program will be
superior to one which merely produces a table of counts for identified
points in the program.
.PP
Satterthwaite's
.SM "ALGOL W"
debugging system [8] produced such a listing by
.I unparsing
a saved internal form of the source program.
In his system
this internal form was also used to provide symbolic flow-trace
information at run time.
As we did not propose to do symbolic statement tracing in our
debugger design [6], there was no need for an internal form of the
source program to be available at run time.
Given the fact that our operating system is primarily disk-space
limited, it was decided that reparsing the source text of the program
to produce the execution profile was a reasonable approach.
This allows the profiler to use the existing source text of the
program without requiring a potentially large intermediate form.
This also allowed the profiler to use the existing parser and to
receive as its input a well defined parse tree as described in [1].
.PP
Thus the execution of a program normally produces a file named
.I pmon.out
which contains an array of counters.
The code generated need contain
only the instructions required to prepare these counts.
This solution
is very conservative of disk storage resources.
.NH 2
Abnormal termination
.PP
In cases where the execution of a Pascal program terminates abnormally,
or has to be terminated due to apparent infinite looping, it is often
desirable to obtain a profile to help discern the cause of the error.
The Pascal runtime system will create the
.I pmon.out
file in these cases, and profiling is still possible.\u\s-2\*(dg\s0\d
.FS
\*(dg If the Pascal runtime system terminates due to a fault,
either because of a bug in the runtime system,
a severe misuse of pointers,
or an untested out-of-range subscript,
a core-image file will be produced.
It is possible,
using a
.XP
option,
to extract the profile information from this core image,
allowing profiling in this case also.
.FE
It should be noted that, 
in general,
the information so gathered is not as usable as that which could be
garnered easily by using a debugger such as
.I pdb
[6],
since variable values are not available.
.PP
A final point to be noted is that the counts are inaccurate
near the suspended control points whenever the program terminates abnormally.
This is explained more fully in [3].
The complete
debugging system design included the marking in the profile of the
point of abnormal termination in a fashion similar to that used by
Satterthwaite [9], but this has not yet been implemented.
.NH 2
Formatting of the program
.PP
As already noted, easy comprehension by the user of the the profile
produced by
.I pxp
requires that the profile be in a readable form.
One possibility would be an annotated source listing, using the
form of the original source text.
This has the advantage that
the listing is in a form familiar to the user.
A major disadvantage
in this approach is the fact that the format of the source may not
leave room for easy placement of all of the profile information.
.NH 3
Pretty printers
.PP
There have been a number of systems designed or constructed which
provide automatically restructured listings of programs
[10] [11] [12] [13].
Such programs have often been called ``pretty printers.''
It is not hard to see that the production of a readable profile
from a well-structured listing would not be difficult given
the framework of a pretty printer.
It was therefore decided to produce such a restructured listing
and to annotate it with the profile information.
An option to use the execution profiler as a pretty printer was
also provided.
.NH 3
Comments and output compression
.PP
One problem with the evolving approach was the treatment of comments.
The interface from the parser to the semantic routines in the compiler,
which was the available and highly suitable framework, had no
provision for the placement of comment text anywhere in the parse tree.
For the purposes of profiling this could be easily tolerated.
An effort can be made when profiling to suppress output which is not absolutely
necessary in the profile.
In particular, comments, declarations, and the bodies of
unexecuted procedures and functions could be normally suppressed.
In fact, early versions of
.XP
suppressed all of these.
In the current implementation, however,
the default is that only the bodies of unexecuted
functions and procedures are suppressed.
All such suppression is controllable through options as described in
[3].
.PP
The design of the comment formatting facility for
.XP
is presented in section 3.
The author feels that significantly better approaches to program
maintenance and formatting are possible
in future systems.
Some possibilities are discussed in section 4.
.NH 3
Bushy if\-then\-elses
.PP
Many different formats for presenting Pascal structure are possible.
The author's personal programming style largely determined
the structure of programs produced by
\fIpxp\fR.
In particular, the author was bothered by one feature of other ``pretty
printers.''
Many other pretty printers
present a ``bushy''
.I "if\-then\-else"
construct in a fashion similar
to the following:
.LS
\*bif\fR condition1
        \*bthen\fR statement1
        \*belse\fR \*bif\fR condition2
                \*bthen\fR statement2
                \*belse\fR ...
.LE
This could be termed ``wandering across the page.''
.PP
In structured programs, especially in a language which contains
no
.B return
or other escape statement, it is easy to get ``buried''
in many levels of conditions.
While the merits of escape-less programming are debatable, it seems
important to present the structure of the above construct as
clearly as possible.
The author feels that a more appropriate way to present
this statement is often the following:
.LS
\*bif\fR condition1 \*bthen\fR
        statement1
\*belse\fR \*bif\fR condition2 \*bthen\fR
        statement2
\*belse\fR
        ...
.LE
.NH 3
Begin\-end pairs and well\-bracketing
.PP
Another aspect of modern programming languages which are not
.I "well-bracketed"
is the presence of
.I "begin\-end"
pairs, which, if mismatched, can cause problems,
especially
if they escape detection at compile time.
With an automatically reformatted listing, the user
no longer needs to worry that his listing may textually represent
the structure of the program in a way different from the true structure.
Given this situation, the author feels that the words
.B begin
and
.B end
convey no information to the user that is not already reflected in
a more convenient form by the textual indentation.
.PP
Thus in considering
how to represent the ``bushy''
.I "if\-then\-else"
when
.I statement1
and
.I statement2
are
.I "begin\-end"
blocks and choosing between:
.LS
\*bif\fR condition1 \*bthen\fR
\*bbegin\fR
        statement list 1
\*bend\fR
\*belse\fR \*bif\fR condition2 \*bthen\fR
\*bbegin\fR
        statement list 2
\*bend\fR
.LE
and
.LS
\*bif\fR condition1 \*bthen\fR \*bbegin\fR
        statement list 1
\*bend\fR \*belse\fR \*bif\fR condition2 \*bthen\fR \*bbegin\fR
        statement list 2
\*bend\fR
.LE
the author chose the latter, which he prefers.
.PP
It should be noted that this is essentially the syntax of
the language
.SM
ALGOL 68
.NL
[14],
and is similar to Wirth's
.SM
MODULA
.NL
[15], e.g.:
.LS
\*bif\fR condition \*bthen\fR
        statement list 1
\*belsif\fR condition2 \*bthen\fR
        statement list 2
\*bfi\fR
.LE
.NH 3
Indenting of structured levels
.PP
Another issue of style arises in choosing how many spaces to indent
each structured statement of the source text.
While 8 spaces per level is very
convenient since
one level then corresponds to one
.SM
ASCII
.NL
tab character,
4 spaces seemed to work best with the execution profile when using
an adaptation of the format of Satterthwaite [8].
Thus, options were provided to allow a level to be defined as
any small number of column positions, with 4 columns the default.
.NH 3
Expressions
.PP
The printing of expressions presented yet another problem.
It was felt that a format which reflected the true structure of an expression
was best.
For this reason, a fully parenthesized expression format was first tried.
This turned out to be a very poor choice as it made complicated
expressions very hard to read.
The author then implemented a minimal-parenthesis format as the default
with full parenthesization as an option.
.PP
It is probably true that many users would prefer to have their
parenthesization preserved even when the parentheses deleted are, in fact,
unnecessary.
This would be even more true in a language which had a large number
of precedence levels with a large number of operators.
It is not as necessary in Pascal since there are only a small number
of levels here, but such an option would have been useful in any case.
This option is not, however, included in the current
\fIpxp\fR.
.NH 3
Procedures and functions
.PP
It was decided that
.B procedure
and
.B function
definitions which are nested
within one another would be indented one structured statement
level by default to improve readability.
An option was included to omit this indenting if desired.
.PP
The
.B end
keyword of each
.B procedure
and
.B function
is labelled with the name of the
.B procedure
or
\*bfunction\fR.
This is done also for the opening
.B begin
if any nested
.B procedure
or
.B function 
definitions occur within the
.B procedure
or
\*bfunction\fR.
.NH 3
Case statements
.PP
When first designing the statement formats, the author felt that
the statements in a
.B case
statement should be formatted so that cases with one and cases with
more than one statement would line up for easy readability.
At the time, 8 spaces per level was the default format and the choice
was between:
.LS
\*bcase\fR ch \*bof\fR
    \(aa \(aa:
        col := col + 1;
    tab:
        col := (col + 8) \*bmod\fR 8;
    \(aa*\(aa:
        \*bbegin\fR
                tok := star;
                tokval := line
        \*bend\fR
\*bend\fR
.LE
and
.LS
\*bcase\fR ch \*bof\fR
  \(aa \(aa:
        col := col + 1;
  tab:
        col := (col + 8) \*bmod\fR 8;
  \(aa*\(aa:
      \*bbegin\fR
        tok := star;
        tokval := line
      \*bend\fR
\*bend\fR
.LE
.PP
With the eventual choice of 4 spaces per structured level as the
default indentation, the difference between the corresponding formats
is slight.
In retrospect, this was not
necessarily sufficiently valuable to justify the amount of time spent on the
.B case
statement format,
as different strategies were needed
for each indenting option, and the format was optimized
to be ``pretty'' in each case subject to the alignment constraint.
Thus the current
.XP
uses only the simpler first strategy.
.NH 3
Labels and miscellania
.PP
Labels are place on a separate line, aligned with the header
line of the
containing
.I program,
.I procedure
or 
.I function.
Placed this way, they are easy to locate.
.PP
In general,
the text editing facilities on the
.SM
UNIX
.NL
system are geared toward
line oriented editing.
Thus it is extremely convenient to have statements on single
lines.
For this reason the format of the programs produced by
the pretty printer gives section keywords like
.B var
and
.B type
alone on a line.
In this way deleting the first declaration
of such a section is made easier \- there is no need to split
the keyword away from the first declaration.
.PP
Other options, such as an option to underline all of the keywords
in the program, are provided by
.XP .
These are detailed more fully in [3].
.NH 3
Summary
.PP
In summary, the profiler format reflects the taste of
the author in Pascal formatting at the time this program was
written.
It largely succeeds in producing readable Pascal texts.
.PP
Treatment of long statements and placement of multiple statements per line
are desirable additions
and a design for some of these is described in section 2.
They were omitted from the original
design only because the author was not initially sure of a reasonable way
to proceed in these areas, and felt that these were more important
in the context of a pretty printer.
.Xp
was intended primarily as an execution profiler.
Even without the features of section 3, earlier versions of
.XP
were useful in showing students who had trouble formatting their programs
one acceptable way of writing Pascal.
.NH 2
Profile Data Presentation
.PP
The basic format for the profile is essentially that of Satterthwaite [8] [9].
Examples are given in [3].
The following pieces of information are included with the profile
in addition to the basic count information.
.IP
.RS
.HP 1) 
The version number and date of the instance of
.XP
which produced the profile.
.RE
.IP
.RS
.HP 2) 
The version of the program being profiled (taken to be the time at which
the file it is contained in was last modified.)
.IP 3) 
The time at which the profile data was gathered.
.RE
.LP
This information serves to identify uniquely the program involved.
.NH 3
Count interpretation
.PP
The algorithm for count interpretation is given in [3] and is essentially
the same as that given by Satterthwaite in [9].
.NH 3
Data compression
.PP
Two options for compressing profile data are available.
One gives a table of the procedures and functions with their activation
counts.
This requires only a very small amount of data even for large programs.
.PP
More easily readable than a simple table are profiles of parts of a
program.
These can be obtained without modifying the source text.
One can give a list of
.B procedure 
or
.B function 
names on the command
line, and profiles will be enabled for these and their contained
procedures and functions only.
.PP
This ability to extract selective information and to be able to do it
without modifying the source code is critical.
Editing the source code (at least twice!) for each profiling pass
would not only be tedious, but could easily be done incorrectly.
The command line syntax is simple and relatively foolproof.
This feature is fully described in [3].
.bp