![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to manCh6.rno CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp|
Return to manCh6.rno CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp |
1.1 root 1: .\" Copyright (c) 1980 Regents of the University of California.
2: .\" All rights reserved. The Berkeley software License Agreement
3: .\" specifies the terms and conditions for redistribution.
4: .\"
5: .\" @(#)manCh6.rno 6.1 (Berkeley) 4/29/86
6: .\"
7: .NS 1 "Implementation Notes"
8: .pp
9: FP was written in 3000 lines of \s-2FRANZ LISP\s+2 [Fod 80].
10: Table 1 breaks down the distribution of the code by functionality.
11: .(b
12: .sp
13: .TS
14: center box;
15: c|c
16: l|n.
17: Functionality % (bytes)
18: =
19: compiler 34
20: user interface 32
21: dynamic stats 16
22: primitives 14
23: miscellaneous 3
24: .TE
25: .sp 4p
26: .ce
27: .b "Table 1"
28: .sp 4p
29: .)b
30: .NS 2 "The Top Level"
31: .pp
32: The top-level function $runFp$ starts up the subsystem by calling
33: the routine \fIfpMain\fP,
34: that takes three arguments:
35: .BB
36: .np
37: A boolean argument that says whether debugging output
38: will be enabled.
39: .np
40: A Font identifier. Currently the only one is supported \fB'asc\fP (ASCII).
41: .np
42: A boolean argument that identifies whether the interpreter
43: was invoked from the shell. If so then all exits from FP return the
44: user back to the shell.
45: .EB
46: .pp
47: The compiler converts the FP functions into LISP equivalents in two
48: stages: first it forms the parse tree, and then it does the
49: code generation.
50: .sp
51: .NS 2 "The Scanner"
52: .sp
53: .pp
54: The scanner consists of a main routine, \fIget_tkn\fP, and a set of
55: action functions. There exists one set of action functions
56: for each character font
57: (currently only ASCII is supported). All the action functions are named
58: $scan dl "<font>"$, where $"<font>"$ is the specified font,
59: and each is keyed
60: on a particular character (or sometimes a particular character-type \-
61: \*(EG a letter or a number). \fIget_tkn\fP returns
62: the token type, and any ancillary
63: information, \*(EG for the token "name" the name itself will also be provided.
64: (See Appendix C for the font-token name correspondences).
65: When a character has been
66: read the scanner finds the action function by doing a
67: .sp
68: .ce 1
69: $(get ~ 'scan dl~ "<font> <char>")$
70: .sp
71: A syntax error message will be generated if
72: no action exists for the particular character read.
73: .sp
74: .NS 2 "The Parser"
75: .sp
76: The main parsing function, \fIparse\fP, accepts a single argument, that
77: identifies the parsing context, or
78: type of construct being handled.
79: Table 2
80: shows
81: the valid parsing contexts.
82: .(b
83: .sp 2
84: .TS
85: center box;
86: c|c
87: l|l.
88: \fBid\fP \fBconstruct\fP
89: =
90: top_lev initial call
91: constr$dd$ construction
92: compos$dd$ composition
93: alpha$dd$ apply-to-all
94: insert$dd$ insert
95: ti$dd$ tree insert
96: arrow$dd$ T{
97: .nf
98: affirmative clause
99: of conditional
100: .fi
101: T}
102: semi$dd$ T{
103: .nf
104: negative clause
105: of conditional
106: .fi
107: T}
108: lparen$dd$ parenthetic expr.
109: while$dd$ while
110: .TE
111: .sp
112: .ce 1
113: .b "Table 2, Valid Parsing Contexts"
114: .)b
115: .sp
116: .EQ
117: delim off
118: .EN
119: .pp
120: For each type of token there exists a set of parse action functions,
121: of the name \fIp$<tkn-name>\fP. Each parse-action function is keyed
122: on a valid context, and it is looked up in the same manner as
123: scan action functions are looked up. If an action function cannot
124: be found, then there is a syntax error in the source code.
125: .EQ
126: delim $$
127: .EN
128: Parsing proceeds as follows: initially $parse$ is called from the top-level,
129: with the context argument set to \fI\*(lqtop_lev\*(rq\fP.
130: Certain tokens cause parse to
131: be recursively invoked using that token as a context. The result
132: is the parse tree.
133: .sp
134: .NS 2 "The Code Generator"
135: .pp
136: The system
137: compiles FP source into LISP source. Normally, this code is interpreted by
138: the \s-2FRANZ LISP\s+2 system.
139: To speed up the implementation, there is an option to
140: compile into machine code using the \fIliszt\fP compiler [Joy 79].
141: This feature
142: improves performance tenfold,
143: for some programs.
144: .pp
145: The compiler expands all functional forms into their LISP equivalents
146: instead of
147: inserting calls to functions that generate the code
148: at run-time. Otherwise, \fIliszt\fP
149: would be ineffective in speeding up execution since
150: all the functional forms would
151: be executed interpretively.
152: Although the amount of code
153: generated by an expanding compiler
154: is 3 or 4 times greater than
155: would be generated by a non-expanding compiler, even in interpreted mode
156: the code runs twice as quickly as unexpanded code.
157: With \fIliszt\fP compilation this performance advantage increases to more
158: than tenfold.
159: .pp
160: A parse tree is either an atom or a hunk of parse trees. An atomic parse-tree
161: identifies either an fp built-in function or
162: a user defined function.
163: The hunk-type parse tree represents functional forms, \*(EG compose or
164: construct. The first element identifies the functional form and the other
165: elements are its functional parameters (they may in turn be
166: functional forms). Table 3 shows the parse-tree formats.
167: .(b
168: .sp 2
169: .TS
170: center box;
171: c|c
172: l|l.
173: Form Format
174: =
175: user-defined <atom>
176: fp builtin <atom>
177: apply-to-all $"{" "alpha" dd~~PHI"}"$
178: insert $"{"insert dd ~~PHI"}"$
179: tree insert $"{"ti dd ~~PHI"}"$
180: select $"{"select dd ~mu"}"$
181: constant $"{"constant dd ~mu"}"$
182: conditional $"{"condit dd ~~PHI sub 1 ~~PHI sub 2 ~~PHI sub 3"}"$
183: while $"{"while dd ~~PHI sub 1 ~~PHI sub 2"}"$
184: compose $"{"compos dd ~~PHI sub 1 ~~PHI sub 2"}"$
185: construct $"{"constr dd ~~PHI sub 1~~PHI sub 2~~,...,~~PHI sub n ~nil"}"$
186: .TE
187: .sp
188: Note: $PHI$ and the $PHI sub k$ are parse-trees and $mu$ is an optionally
189: signed integer constant.
190: .sp
191: .ce 1
192: .b "Table 3, Parse-Tree Formats"
193: .sp
194: .)b
195: .NS 2 "Function Definition and Application"
196: .sp
197: .pp
198: Once the code has been generated, then
199: the system defines the function via \fIputd\fP.
200: The source code is placed onto
201: a property list, $'sources$, to permit later access by the system
202: commands.
203: .pp
204: For an application,
205: the indicated function is compiled and then defined, only temporarily, as
206: $tmp dd$. The single argument is read and
207: $tmp dd$ is applied to it.
208: .NS 2 "Function Naming Conventions"
209: .pp
210: When the parser detects a named primitive function, it returns the name
211: $"<"name">" df$,
212: where \fI<name>\fP is the name that was parsed (all primitive
213: function-names
214: end in $df$). See Appendix D for the symbolic (\*(EG
215: compose, $+$) function names.
216: .pp
217: Any name that isn't found in the list of builtin functions
218: is assumed to represent a user-defined function; hence,
219: it isn't possible to redefine FP primitive functions.
220: FP protects itself
221: from accidental or malicious internal destruction
222: by appending the suffix \*(lq$_fp$\*(rq
223: to all user-defined function names, before
224: they are defined.
225: .NS 2 "Measurement Impelementation"
226: .pp
227: This work was done by Dorab Patel at UCLA.
228: Most of the measurement code is in the file 'fpMeasures.l'.
229: Many of the remaining changes were effected in
230: \&'primFp.l', to add calls on
231: the measurement package at run-time; to 'codeGen.l', to add
232: tracing of user defined functions; to 'utils.l', to add the new system
233: commands; and to 'fpMain.l',
234: to protect the user from forgetting to output statistics when he leaves
235: FP.
236: .NS 3 "Data Structures"
237: .pp
238: All the statistics are in the property list of the global symbol
239: \fIMeasures\fP.
240: Associated with each
241: each function (primitive or user-defined, or functional form)
242: is an
243: indicator;
244: the statistics gathered for each function are the corresponding values.
245: The names corresponding to primitive functions and functional forms end
246: in '$dl$fp' and the names corresponding to
247: user-defined functions end in '_fp'.
248: Each of the property values is an
249: association list:
250: .sp
251: .(l I
252: (get 'Measures 'rotl$dl$fp) ==> ((times . 0) (size . 0))
253: .)l
254: .sp
255: .pp
256: The car of the pair is the name of the statistic (\*(IE times, size)
257: and the cdr is the value.
258: There is one exception.
259: Functional forms have a statistic called funargtyp.
260: Instead of being a dotted pair, it is a list of two elements:
261: .sp
262: .(l I
263: (get 'Measures 'compose$dl$fp) ==>
264: ((times . 2) (size . 4) (funargtyp ((select$dl$fp . 2) (sub$dl$fp . 2))))
265: .)l
266: .sp
267: .pp
268: The car is the atom 'funargtyp' and the cdr is an alist.
269: Each element of the alist consists of a functional
270: argument-frequency dotted pair.
271: .pp
272: The statistic packages uses two other global symbols.
273: The symbol DynTraceFlg is non-nil if dynamic statistics are being
274: collected and is nil otherwise.
275: The symbol TracedFns is a list (initially nil) of the names of the
276: user functions being traced.
277: .NS 3 "Interpretation of Data Structures"
278: .NS 4 "Times"
279: .pp
280: The number of times this function has been called.
281: All functions and functional forms have this statistic.
282: .NS 4 "Size"
283: .pp
284: The sum of the sizes of the arguments passed to this
285: function.
286: This could be divided by the times statistic to give the average
287: size of argument this function was passed.
288: With few exceptions, the size of an object is its top-level length
289: (note: version 4.0 defined the size as the total number of \fIatoms\fP
290: in the object);
291: the empty sequence, \*(lq<>\*(rq,
292: has a size of 0 and all other atoms have size of one.
293: The exceptions are: \fIapndl, distl\fP (top-level length
294: of the second element), \fIapndr, distr\fP (top-level length of the first
295: element), and \fItranspose\fP (top level length of each top level
296: element).
297: .pp
298: This statistic is not collected for some primitive functions
299: (mainly binary operators like +,-,\(**).
300: .NS 4 "Funargno"
301: .pp
302: The number of functional arguments supplied to a functional
303: form.
304: .pp
305: Currently this statistic is gatherered only for the construction
306: functional form.
307: .NS 4 "Funargtyp"
308: .pp
309: How many times the named function was used as a
310: functional parameter to the particular functional form.
311: .NS 2 "Trace Information"
312: .pp
313: The level number of a call shows the number
314: of steps required to execute the function on an ideal machine
315: (\*(IE one with unbounded resources).
316: The level number is calculated under an assumption of infinite
317: resources, and
318: the system evaluates the
319: condition of a conditional before evaluating
320: either of its clauses.
321: The number of functions executed at each level can give an idea of the
322: distribution of parallelism in the given FP program.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.