Return to manCh5.rno CVS log

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

Annotation of 43BSDReno/share/doc/ps2/07.fp/manCh5.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: .\"    @(#)manCh5.rno  6.1 (Berkeley) 4/29/86
        !             6: .\"
        !             7: .NS 1 "Programming Examples"
        !             8: .pp
        !             9: We will start off by developing a larger FP program, \fImergeSort\fP.
        !            10: We measure \fImergeSort\fP using the trace package, and then we
        !            11: comment on the measurements.
        !            12: Following \fImergeSort\fP
        !            13: we show an actual session at the terminal.
        !            14: .NS 2 "MergeSort"
        !            15: .pp
        !            16: The source code for
        !            17: \fImergeSort\fP is:
        !            18: .(b
        !            19: .sp 4p
        !            20: .hl
        !            21: .sp 4p
        !            22: .(c
        !            23: # Use a divide and conquer strategy
        !            24: .sp 3p
        !            25: {mergeSort $^"\fB|\fP"^$ merge}
        !            26: .sp 6p
        !            27: {merge atEnd @ mergeHelp @ [[], fixLists]}
        !            28: .sp 6p
        !            29: # Must convert atomic arguments into sequences
        !            30: # Atomic arguments occur at the leaves of the execution tree
        !            31: .sp 3p
        !            32: {fixLists &(atom -> [id] ; id)}
        !            33: .sp 6p
        !            34: # Merge until one or both input lists are empty
        !            35: .sp 3p
        !            36: {mergeHelp (while \kxand @ &(not@null) @ 2
        !            37: \h'\nxu'(firstIsSmaller -> \kytakeFirst ;
        !            38: \h'\nyu'takeSecond))}
        !            39: .sp 6p
        !            40: # Find the list with the smaller first element
        !            41: .sp 3p
        !            42: {firstIsSmaller < @ [1@1@2, 1@2@2]}
        !            43: .sp 6p
        !            44: # Take the first element of the first list
        !            45: .sp 3p
        !            46: {takeFirst [apndr@[1,1@1@2], [tl@1@2, 2@2]]}
        !            47: .sp 6p
        !            48: # Take the first element of the second list
        !            49: .sp 3p
        !            50: {takeSecond [apndr@[1,1@2@2], [1@2, tl@2@2]]}
        !            51: .sp 6p
        !            52: # If one list isn't null, then append it to the
        !            53: # end of the merged list
        !            54: .sp 3p
        !            55: {atEnd (firstIsNull -> \kzconcat@[1,2@2] ;
        !            56: \h'\nzu'concat@[1,1@2])}
        !            57: .sp 6p
        !            58: {firstIsNull null@1@2}
        !            59: .)c
        !            60: .sp 4p
        !            61: .hl
        !            62: .sp 4p
        !            63: .)b
        !            64: .pp
        !            65: The merge sort algorithm uses a divide and conquer strategy;
        !            66: it splits the input in half, recursively sorts each half,
        !            67: and then merges the sorted lists.
        !            68: Of course, all these sub-sorts can execute
        !            69: in parallel, and the
        !            70: tree-insert ($"\fB|\fP" $) functional form expresses this
        !            71: concurrency.  \fIMerge\fP removes successively larger elements
        !            72: from the heads of the
        !            73: two lists (either \fItakeFirst\fP or \fItakeSecond\fP)
        !            74: and appends these elements to the end of the merged sequence.
        !            75: \fIMerge\fP terminates when
        !            76: one sequence is empty, and then
        !            77: \fIatEnd\fP appends
        !            78: any remaining non-empty sequence
        !            79: to the end of the merged one.
        !            80: .CH "Dynamic Statistics"
        !            81: .pp
        !            82: On the next page we
        !            83: give the trace of the function \fImerge\fP, which information
        !            84: we can use to determine the structure of
        !            85: \fImerge\fP's execution tree.
        !            86: Since the tree is well-balanced,
        !            87: many of the \fImerge\fP's
        !            88: could be executed in parallel.
        !            89: Using this trace we
        !            90: can also calculate
        !            91: the average length of the
        !            92: arguments passed to \fImerge\fP, or a distribution of argument lengths.
        !            93: This information is useful for
        !            94: determining communication costs.
        !            95: .(b
        !            96: .nf
        !            97: .sp 4p
        !            98: .nf
        !            99: .hl
        !           100: .sp 4p
        !           101: .(c
        !           102:        )trace on merge
        !           103: 
        !           104:        mergeSort\ :\ <0\ 3\ -2\ 1\ 11\ 8\ -22\ -33>
        !           105: |\ 3\ >Enter>\ merge\ [<0\ 3>]
        !           106: |\ 3\ <EXIT<\ \ merge\ \ <0\ 3>
        !           107: |\ 3\ >Enter>\ merge\ [<-2\ 1>]
        !           108: |\ 3\ <EXIT<\ \ merge\ \ <-2\ 1>
        !           109: |2\ >Enter>\ merge\ [<<0\ 3>\ <-2\ 1>>]
        !           110: |2\ <EXIT<\ \ merge\ \ <-2\ 0\ 1\ 3>
        !           111: |\ 3\ >Enter>\ merge\ [<11\ 8>]
        !           112: |\ 3\ <EXIT<\ \ merge\ \ <8\ 11>
        !           113: |\ 3\ >Enter>\ merge\ [<-22\ -33>]
        !           114: |\ 3\ <EXIT<\ \ merge\ \ <-33\ -22>
        !           115: |2\ >Enter>\ merge\ [<<8\ 11>\ <-33\ -22>>]
        !           116: |2\ <EXIT<\ \ merge\ \ <-33\ -22\ 8\ 11>
        !           117: 1\ >Enter>\ merge\ [<<-2\ 0\ 1\ 3>\ <-33\ -22\ 8\ 11>>]
        !           118: 1\ <EXIT<\ \ merge\ \ <-33\ -22\ -2\ 0\ 1\ 3\ 8\ 11>
        !           119: 
        !           120: <-33\ -22\ -2\ 0\ 1\ 3\ 8\ 11>
        !           121: .)c
        !           122: .sp 4p
        !           123: .hl
        !           124: .fi
        !           125: .)b
        !           126: .bp
        !           127: .NS 2 "FP Session"
        !           128: .pp
        !           129: User input is
        !           130: \fBemboldened\fP, terminal output in Roman script.
        !           131: .sp 0.5i
        !           132: .nf
        !           133: \fBfp\fP
        !           134: 
        !           135: FP, v. 4.1 11/31/82
        !           136: \fB    )load ex_man\fP
        !           137: {all_le}
        !           138: {sort}
        !           139: {abs_val}
        !           140: {find}
        !           141: {ip}
        !           142: {mm}
        !           143: {eq0}
        !           144: {fact}
        !           145: {sub1}
        !           146: {alt_fnd}
        !           147: {alt_fact}
        !           148: \fB    )fns\fP
        !           149: 
        !           150: .TS
        !           151: l l l l l l l.
        !           152: abs_val        all_le  alt_fact        alt_fnd eq0     fact    find
        !           153: ip     mm      sort    sub1    \&      \&      \&
        !           154: .TE
        !           155: 
        !           156: \fB    abs_val : 3\fP
        !           157: 
        !           158: 3
        !           159: 
        !           160: \fB    abs_val : -3\fP
        !           161: 
        !           162: 3
        !           163: 
        !           164: \fB    abs_val : 0\fP
        !           165: 
        !           166: 0
        !           167: 
        !           168: \fB    abs_val : <-5 0 66>\fP
        !           169: 
        !           170: ?
        !           171: 
        !           172: \fB    &abs_val : <-5 0 66>\fP
        !           173: 
        !           174: <5 0 66>
        !           175: 
        !           176: \fB    )pfn abs_val\fP
        !           177: 
        !           178: {abs_val ((> @ [id,%0]) -> id ; (- @ [%0,id]))}
        !           179: 
        !           180: \fB    [id,%0] : -3\fP
        !           181: 
        !           182: <-3 0>
        !           183: 
        !           184: \fB    [%0,id] : -3\fP
        !           185: 
        !           186: <0 -3>
        !           187: 
        !           188: \fB    - @ [%0,id] : -3\fP
        !           189: 
        !           190: 3
        !           191: 
        !           192: \fB    all_le : <1 3 5 7>\fP
        !           193: 
        !           194: T
        !           195: 
        !           196: \fB    all_le : <1 0 5 7>\fP
        !           197: 
        !           198: F
        !           199: 
        !           200: \fB    )pfn all_le\fP
        !           201: 
        !           202: {all_le ! and @ &<= @ distl @ [1,tl]}
        !           203: 
        !           204: \fB    distl @ [1,tl] : <1 2 3 4>\fP
        !           205: 
        !           206: <<1 2> <1 3> <1 4>>
        !           207: 
        !           208: \fB    &<= @ distl @ [1,tl] : <1 2 3 4>\fP
        !           209: 
        !           210: <T T T>
        !           211: 
        !           212: \fB    ! and : <F T T>\fP
        !           213: 
        !           214: F
        !           215: 
        !           216: \fB    ! and : <T T T>\fP
        !           217: 
        !           218: T
        !           219: 
        !           220: \fB    sort : <3 1 2 4>\fP
        !           221: 
        !           222: <1 2 3 4>
        !           223: 
        !           224: \fB    sort : <1>\fP
        !           225: 
        !           226: <1>
        !           227: 
        !           228: \fB    sort : <>\fP
        !           229: 
        !           230: ?
        !           231: 
        !           232: \fB    sort : 4\fP
        !           233: 
        !           234: ?
        !           235: 
        !           236: \fB    )pfn sort\fP
        !           237: 
        !           238: {sort (null @ tl -> [1] ; (all_le -> apndl @ [1,sort@tl]; sort@rotl))}
        !           239: 
        !           240: \fB    fact : 3\fP
        !           241: 
        !           242: 6
        !           243: 
        !           244: \fB    )pfn fact sub1 eq0\fP
        !           245: 
        !           246: {fact (eq0 -> %1 ; *@[id , fact@sub1])}
        !           247: 
        !           248: {sub1 -@[id,%1]}
        !           249: 
        !           250: {eq0 = @ [id,%0]}
        !           251: 
        !           252: \fB    &fact : <1 2 3 4 5>\fP
        !           253: 
        !           254: <1 2 6 24 120>
        !           255: 
        !           256: \fB    eq0 : 3\fP
        !           257: 
        !           258: F
        !           259: 
        !           260: \fB    eq0 : <>\fP
        !           261: 
        !           262: F
        !           263: 
        !           264: \fB    eq0 : 0\fP
        !           265: 
        !           266: T
        !           267: 
        !           268: \fB    sub1 : 3\fP
        !           269: 
        !           270: 2
        !           271: 
        !           272: \fB    %1 : 3\fP
        !           273: 
        !           274: 1
        !           275: 
        !           276: \fB    alt_fact : 3\fP
        !           277: 
        !           278: 6
        !           279: 
        !           280: \fB    )pfn alt_fact\fP
        !           281: 
        !           282: {alt_fact !* @ iota}
        !           283: 
        !           284: \fB    iota : 3\fP
        !           285: 
        !           286: <1 2 3>
        !           287: 
        !           288: \fB    !* @ iota : 3\fP
        !           289: 
        !           290: 6
        !           291: 
        !           292: \fB    !+ : <1 2 3>\fP
        !           293: 
        !           294: 6
        !           295: 
        !           296: \fB    find : <3 <3 4 5>>\fP
        !           297: 
        !           298: T
        !           299: 
        !           300: \fB    find : <<> <3 4 <>>>\fP
        !           301: 
        !           302: T
        !           303: 
        !           304: \fB    find : <3 <4 5>>\fP
        !           305: 
        !           306: F
        !           307: 
        !           308: \fB    )pfn find\fP
        !           309: 
        !           310: {find (null@2 -> %F ; (=@[1,1@2] -> %T ; find@[1,tl@2]))}
        !           311: 
        !           312: \fB    [1,tl@2] : <3 <3 4 5>>\fP
        !           313: 
        !           314: <3 <4 5>>
        !           315: 
        !           316: \fB    [1,1@2] : <3 <3 4 5>>\fP
        !           317: 
        !           318: <3 3>
        !           319: 
        !           320: \fB    alt_fnd : <3 <3 4 5>>\fP
        !           321: 
        !           322: T
        !           323: 
        !           324: \fB    )pfn alt_fnd\fP
        !           325: 
        !           326: {alt_fnd ! or @ &eq @ distl }
        !           327: 
        !           328: \fB    distl : <3 <3 4 5>>\fP
        !           329: 
        !           330: <<3 3> <3 4> <3 5>>
        !           331: 
        !           332: \fB    &eq @ distl : <3 <3 4 5>>\fP
        !           333: 
        !           334: <T F F>
        !           335: 
        !           336: \fB    !or : <T F T>\fP
        !           337: 
        !           338: T
        !           339: 
        !           340: \fB    !or : <F F F>\fP
        !           341: 
        !           342: F
        !           343: 
        !           344: \fB    )delete alt_fnd\fP
        !           345: 
        !           346: \fB    )fns\fP
        !           347: 
        !           348: .TS
        !           349: l l l l l l l.
        !           350: abs_val        all_le  alt_fact        eq0     fact    find    ip
        !           351: mm     sort    sub1    \&      \&      \&      \&
        !           352: .TE
        !           353: 
        !           354: \fB    alt_fnd : <3 <3 4 5>>\fP
        !           355: 
        !           356: alt_fnd not defined
        !           357: 
        !           358: ?
        !           359: \fB    {g g}\fP
        !           360: 
        !           361: {g}
        !           362: \fB    g : 3\fP
        !           363: 
        !           364: non-terminating
        !           365: 
        !           366: ?
        !           367: 
        !           368: [Return to top level]
        !           369: 
        !           370: FP, v. 4.0 10/8/82
        !           371: \fB    [+,*] : <3 4>\fP
        !           372: 
        !           373: <7 12>
        !           374: 
        !           375: .(b
        !           376: \fB    [+,* : <3 4>\fP
        !           377: 
        !           378: syntax error:
        !           379: 
        !           380: [+,* \kx: <3 4>
        !           381: \h'\nxu'^
        !           382: .)b
        !           383: \fB    ip : <<3 4 5> <5 6 7>>\fP
        !           384: 
        !           385: 74
        !           386: 
        !           387: \fB    )pfn ip\fP
        !           388: 
        !           389: {ip !+ @ &* @ trans}
        !           390: 
        !           391: \fB    trans : <<3 4 5> <5 6 7>>\fP
        !           392: 
        !           393: <<3 5> <4 6> <5 7>>
        !           394: 
        !           395: \fB    &* @ trans : <<3 4 5> <5 6 7>>\fP
        !           396: 
        !           397: <15 24 35>
        !           398: 
        !           399: \fB    mm : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
        !           400: 
        !           401: <<3 4> <5 6>>
        !           402: 
        !           403: \fB    )pfn mm\fP
        !           404: 
        !           405: {mm &&ip @ &distl @ distr @[1,trans@2]}
        !           406: 
        !           407: \fB    [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
        !           408: 
        !           409: <<<1 0> <0 1>> <<3 4> <5 6>>>
        !           410: 
        !           411: \fB    distr : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
        !           412: 
        !           413: <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>
        !           414: 
        !           415: \fB    &distl : <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>\fP
        !           416: 
        !           417: <<<<1 0> <3 4>> <<1 0> <5 6>>> <<<0 1> <3 4>> <<0 1> <5 6>>>>
        !           418: 
        !           419: .(b
        !           420: \fB    &ip @ &dist & distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
        !           421: 
        !           422: syntax error:
        !           423: 
        !           424: [+,* \kx: <3 4>
        !           425: \h'\nxu'^
        !           426: &ip @ &distl \kx& distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
        !           427: \h'\nxu'^
        !           428: .)b
        !           429: \fB    &ip @ &distl @ distr @ [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
        !           430: 
        !           431: ?
        !           432: .sp 2
        !           433: .fi
        !           434: .bp

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.