20-CS-4003-001 Organization of Programming Languages Fall 2017
Streams

Lambda calculus, Type theory, Formal semantics, Program analysis

All lectures

Hamming's Sequence

 Development and use of control & data abstractions to solve problems efficiently Problem: Given: Set P of distinct primes. Produce: Distinct set of integers whose prime factors are in P. Example: For P = {3,5,11} Solution: 3,5,9,11,15,25,27,33,45,55,75,81,99,121,125,135 ... Possible Program ``` For all numbers 1,2,3 ... do the following: If the number has only prime factors in P, print it. ``` This is unfortunately too slow to be of value. Better Program ``` _ 5, 11, 25, 55, 121, 125, ... / / 3 < \ \_ 9, 15, 27, 33, 45, 75, 81, 99, 135, ... 3 * {3, 5, 9, 11, 15, 25, 27, 33, 45, ...} ``` So, generalizing: ``` Hamming(P) = if P is empty then return nothing. return First(P) + Merge(First(P)*Hamming(P), Hamming(Rest(P))). ``` C Code: ``` (3) 1*{3,5,11} _______________/ \_______________ / \ (5) (9) 1*{5,11} 3*{3,5,11} _____/ \____ _______/ \_____ / \ / \ (11) (25) (15) (27) 1*{11} 5*{5,11} 3*{5,11} 9*{3,5,11} \ __/ \__ __/ \__ __/ \__ \ / \ / \ / \ (121) (55) (125) (33) (75) (45) (81) 11*{11} 5*{11} 25*{5,11} 3*{11} 15*{5,11} 9*{5,11} 27*{3,5,11} \ \ / \ \ / \ / \ / \ .. .. .. .. .. .. .. .. .. .. .. #define ADD 1 #define POP 2 unsigned long ham (unsigned long p[]) { long right[4], left[4], q[4], i, j; int fbreak(); right[1]=0; right[2]=0; right[3]=0; left[1]=0; left[2]=0; left[3]=0; q[1]=p[1]; q[2]=1; q[3]=1; queue(ADD,q); for (j=0 ; j < 480 ; j++) { queue(POP,q); printf("%d\n",q[1]); left[1]=q[3]*p[q[2]+1]; right[1]=q[3]*p[q[2]]*p[q[2]]; left[2]=q[2]+1; right[2]=q[2]; left[3]=q[3]; right[3]=q[3]*p[q[2]]; queue(ADD ,right); if (left[1]>0) queue(ADD ,left); } } main(int argc, char *argv[]) { unsigned long p[11],i; printf("\nprime list:"); p[argc]=0; for (i=1; i < argc; i++) { p[i] = atoi(argv[i]); printf(" %d",p[i]); } printf("\n\n"); ham(p); } unsigned long a[1000][4],head = 1,tail = 0; unsigned long queue(int func, unsigned long q[]) { unsigned long tptr, i, val_arg, ptr_arg, t_arg; val_arg = q[1]; ptr_arg = q[2]; t_arg = q[3]; if (func == ADD) { tptr = ++tail; while (a[tptr-1][1] > val_arg && tptr > head) { for (i=1; i<=3; i++) a[tptr][i] = a[tptr-1][i]; tptr -= 1; } a[tptr][3] = t_arg; a[tptr][2] = ptr_arg; a[tptr][1] = val_arg; } else if (func == POP) { q[1] = a[head][1]; q[2] = a[head][2]; q[3] = a[head][3]; head++; } } ```