Hamming Numbers

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

FP
 PFL
  Examples
  Syntax

Below is a straightforward implementation of the Hamming numbers program in PFL; compare it to the [λ-calculus] list-based version. Note the use of an unbounded buffer (which could be more efficient) because of the uneven work rate of producers. Also note the "fan out" operator, fan4, duplicating values to pass to the producers.

let rec
   add = lambda x. lambda list. {add element x to end of list}
      if null list then x::nil else hd list :: add x  tl list,


   buffer = lambda inch. lambda opch. {buffer inch onto opch}
      let rec
         b = lambda buff. {NB. unbounded buffer}
            if null buff then
                 inch?x       -> b (x::nil)
            else opch!hd buff -> b tl buff     |
                 inch?x       -> b (add x buff)
      in b nil,


   merge = lambda in1. lambda in2. lambda op. {infinite steams}
      let rec
         m = lambda x1. lambda x2.
            if      x1 in1?y -> m y x2
            else if x2 in2?z -> m x1 z
            else   {x1=x2}     op!x1 -> merge in1 in2 op
      in
         in1 ? x1 -> in2 ? x2 -> m x1 x2  |
         in2 ? x2 -> in1 ? x1 -> m x1 x2,


   merge3 = lambda in1. lambda in2. lambda in3. lambda op.
      let in1in2 = chan
      in  merge in1 in2 in1in2  ||  merge in1in2 in3 op,


   fan4 = lambda inch. lambda op1. lambda op2. lambda op3. lambda op4.
      let rec fan = {4-way fan out}
         inch?x -> op1!x -> op2!x -> op3!x -> op4!x -> fan
      in fan,


   times = lambda n. lambda inch. lambda opch.
       inch ? x     ->
       opch ! n*x   ->
       times n inch opch,


   in2 =chan, in3 =chan, in5 =chan, {declare channels}
   out2=chan, out3=chan, out5=chan, {to join}
   b2  =chan, b3  =chan, b5  =chan, {system}
   mergeout=chan                    {together}


in  times 2 in2 out2               ||
    times 3 in3 out3               ||
    times 5 in5 out5               ||
    merge3 out2 out3 out5 mergeout ||
    fan4 mergeout output b2 b3 b5  ||
    buffer b2 in2                  ||
    buffer b3 in3                  ||
    buffer b5 in5                  ||
    mergeout!1 {seed the system} -> stop

{\fB Parallel Hamming Numbers Program. \fP}

e.g. c1993

Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

pfl...
|   choice
|| parallel
-> sequence
? input act
! output act
chan new channel

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 28-Mar-2024 21:44:55 AEDT.