+.\" 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 5.1 (Berkeley) %G%
+.\"
+.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.
projects / unix-history / commitdiff