# 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
 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}
 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 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 Wednesday, 08-Feb-2023 10:58:29 AEDT.