Return to manCh6.rno CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp

Annotation of 43BSDReno/share/doc/ps2/07.fp/manCh6.rno, revision 1.1

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.