4.3BSD/usr/doc/ps2/07.fp/manCh6.rno

.\" Copyright (c) 1980 Regents of the University of California.
.\" All rights reserved.  The Berkeley software License Agreement
.\" specifies the terms and conditions for redistribution.
.\"
.\"	@(#)manCh6.rno	6.1 (Berkeley) 4/29/86
.\"
.NS 1 "Implementation Notes"
.pp
FP was written in 3000 lines of \s-2FRANZ LISP\s+2 [Fod 80].
Table 1 breaks down the distribution of the code by functionality.
.(b
.sp
.TS
center box;
c|c
l|n.
Functionality	% (bytes)
=
compiler	34
user interface	32
dynamic stats	16
primitives	14
miscellaneous	3
.TE
.sp 4p
.ce
.b "Table 1"
.sp 4p
.)b
.NS 2 "The Top Level"
.pp
The top-level function $runFp$ starts up the subsystem by calling
the routine \fIfpMain\fP,
that takes three arguments:
.BB
.np
A boolean argument that says whether debugging output
will be enabled.
.np
A Font identifier.  Currently the only one is supported \fB'asc\fP (ASCII).
.np
A boolean argument that identifies whether the interpreter
was invoked from the shell.  If so then all exits from FP return the
user back to the shell.
.EB
.pp
The compiler converts the FP functions into LISP equivalents in two
stages: first it forms the parse tree, and then it does the
code generation.
.sp
.NS 2 "The Scanner"
.sp
.pp
The scanner consists of a main routine, \fIget_tkn\fP, and a set of
action functions.  There exists one set of action functions
for each character font
(currently only ASCII is supported).  All the action functions are named
$scan dl "<font>"$, where $"<font>"$ is the specified font,
and each is keyed
on a particular character (or sometimes a particular character-type \-
\*(EG a letter or a number).  \fIget_tkn\fP returns
the token type, and any ancillary
information, \*(EG for the token "name" the name itself will also be provided.
(See Appendix C for the font-token name correspondences).
When a character has been
read the scanner finds the action function by doing a 
.sp
.ce 1
$(get ~  'scan dl~ "<font> <char>")$
.sp
A syntax error message will be generated if
no action exists for the particular character read.
.sp
.NS 2 "The Parser"
.sp
The main parsing function, \fIparse\fP, accepts a single argument, that
identifies the parsing context, or
type of construct being handled.
Table 2
shows
the valid parsing contexts.
.(b
.sp 2
.TS
center box;
c|c
l|l.
\fBid\fP	\fBconstruct\fP
=
top_lev	initial call
constr$dd$	construction
compos$dd$	composition
alpha$dd$	apply-to-all
insert$dd$	insert
ti$dd$	tree insert
arrow$dd$	T{
.nf
affirmative clause
of conditional
.fi
T}
semi$dd$	T{
.nf
negative clause
of conditional
.fi
T}
lparen$dd$	parenthetic expr.
while$dd$	while
.TE
.sp
.ce 1
.b "Table 2, Valid Parsing Contexts"
.)b
.sp
.EQ
delim off
.EN
.pp
For each type of token there exists a set of parse action functions,
of the name \fIp$<tkn-name>\fP.  Each parse-action function is keyed
on a valid context, and it is looked up in the same manner as
scan action functions are looked up.  If an action function cannot
be found, then there is a syntax error in the source code.
.EQ
delim $$
.EN
Parsing proceeds as follows: initially $parse$ is called from the top-level,
with the context argument set to \fI\*(lqtop_lev\*(rq\fP.
Certain tokens cause parse to
be recursively invoked using that token as a context.  The result
is the parse tree.
.sp
.NS 2 "The Code Generator"
.pp
The system
compiles FP source into LISP source.  Normally, this code is interpreted by
the \s-2FRANZ LISP\s+2 system.
To speed up the implementation, there is an option to
compile into machine code using the \fIliszt\fP  compiler [Joy 79].
This feature
improves performance tenfold,
for some programs.
.pp
The compiler expands all functional forms into their LISP equivalents
instead of
inserting calls to functions that generate the code
at run-time.  Otherwise, \fIliszt\fP
would be ineffective in speeding up execution since
all the functional forms would
be executed interpretively.
Although the amount of code
generated by an expanding compiler
is 3 or 4 times greater than
would be generated by a non-expanding compiler, even in interpreted mode 
the code runs twice as quickly as unexpanded code.
With \fIliszt\fP compilation this performance advantage increases to more
than tenfold.
.pp
A parse tree is either an atom or a hunk of parse trees.  An atomic parse-tree
identifies either an fp built-in function or
a user defined function.
The hunk-type parse tree represents functional forms, \*(EG compose or
construct. The first element identifies the functional form and the other
elements are its functional parameters (they may in turn be
functional forms).  Table 3 shows the parse-tree formats.
.(b
.sp 2
.TS
center box;
c|c
l|l.
Form	Format
=
user-defined	<atom>
fp builtin	<atom>
apply-to-all	$"{" "alpha" dd~~PHI"}"$
insert	$"{"insert dd ~~PHI"}"$
tree insert	$"{"ti dd ~~PHI"}"$
select	$"{"select dd ~mu"}"$
constant	$"{"constant dd ~mu"}"$
conditional	$"{"condit dd ~~PHI sub 1 ~~PHI sub 2 ~~PHI sub 3"}"$
while	$"{"while dd ~~PHI sub 1 ~~PHI sub 2"}"$
compose	$"{"compos dd ~~PHI sub 1 ~~PHI sub 2"}"$
construct	$"{"constr dd ~~PHI sub 1~~PHI sub 2~~,...,~~PHI sub n ~nil"}"$
.TE
.sp
Note: $PHI$ and the $PHI sub k$ are parse-trees and $mu$ is an optionally
signed integer constant.
.sp
.ce 1
.b "Table 3, Parse-Tree Formats"
.sp
.)b
.NS 2 "Function Definition and Application"
.sp
.pp
Once the code has been generated, then 
the system defines the function via \fIputd\fP.
The source code is placed onto
a property list, $'sources$, to permit later access by the system
commands.
.pp
For an application,
the indicated function is compiled and then defined, only temporarily, as
$tmp dd$. The single argument is read and
$tmp dd$ is applied to it.
.NS 2 "Function Naming Conventions"
.pp
When the parser detects a named primitive function, it returns the name
$"<"name">" df$,
where \fI<name>\fP is the name that was parsed (all primitive
function-names
end in $df$).  See Appendix D for the symbolic (\*(EG
compose, $+$) function names.
.pp
Any name that isn't found  in the list of builtin functions
is assumed to represent a user-defined function; hence,
it isn't possible to redefine FP primitive functions.
FP protects itself
from accidental or malicious internal destruction
by appending the suffix \*(lq$_fp$\*(rq
to all user-defined function names, before
they are defined.
.NS 2 "Measurement Impelementation"
.pp
This work was done by Dorab Patel at UCLA.
Most of the  measurement code is in the file 'fpMeasures.l'.
Many of the remaining changes were effected in
\&'primFp.l', to add calls on
the measurement package at run-time; to  'codeGen.l', to add
tracing of user defined functions; to  'utils.l', to add the new system
commands; and to 'fpMain.l',
to protect the user from forgetting to output statistics when he leaves
FP.
.NS 3 "Data Structures"
.pp
All the statistics are in the property list of the global symbol
\fIMeasures\fP.
Associated with each
each function  (primitive or user-defined, or functional form)
is an
indicator;
the statistics gathered for each function  are the corresponding values.
The names corresponding to primitive functions and functional forms end
in '$dl$fp' and the names corresponding to
user-defined functions end in '_fp'.
Each of the property values  is an
association list:
.sp
.(l I
    (get 'Measures 'rotl$dl$fp) ==> ((times . 0) (size . 0))
.)l
.sp
.pp
The car of the pair is the name of the statistic (\*(IE times, size)
and the cdr is the value.
There is one exception.
Functional forms have a statistic called funargtyp.
Instead of being a dotted pair, it is a list of two elements:
.sp
.(l I
(get 'Measures 'compose$dl$fp) ==>
((times . 2) (size . 4) (funargtyp ((select$dl$fp . 2) (sub$dl$fp . 2))))
.)l
.sp
.pp
The car is the atom 'funargtyp' and the cdr is an alist.
Each element of the alist consists of a functional
argument-frequency dotted pair.
.pp
The statistic packages uses two other global symbols.
The symbol DynTraceFlg is non-nil if dynamic statistics are being
collected and is nil otherwise.
The symbol TracedFns is a list (initially nil) of the names of the
user functions being traced.
.NS 3 "Interpretation of Data Structures"
.NS 4 "Times"
.pp
The number of times this function has been called.
All functions and functional forms have this statistic.
.NS 4 "Size"
.pp
The sum of the sizes of the arguments passed to this
function.
This could be divided by the times statistic to give the average
size of argument this function was passed.
With few exceptions, the size of an object is its top-level length
(note: version 4.0 defined the size as the total number of \fIatoms\fP
in the object);
the empty sequence, \*(lq<>\*(rq,
has a size of 0 and all other atoms have size of one.
The exceptions are: \fIapndl, distl\fP (top-level length
of the second element), \fIapndr, distr\fP (top-level length of the first
element), and \fItranspose\fP (top level length of each top level
element).
.pp
This statistic is not collected for some primitive functions
(mainly binary operators like +,-,\(**).
.NS 4 "Funargno"
.pp
The number of functional arguments supplied to a functional
form.
.pp
Currently this statistic is gatherered  only for the construction
functional form.
.NS 4 "Funargtyp"
.pp
How many times the named function was used as a
functional parameter to the particular functional form.
.NS 2 "Trace Information"
.pp
The level number of a call shows the number
of steps required to execute the function on an ideal machine
(\*(IE one with unbounded resources).
The level number is calculated under an assumption of infinite
resources, and
the system evaluates the
condition of a conditional before evaluating
either of its clauses.
The number of functions executed at each level can give an idea of the
distribution of parallelism in the given FP program.