20-CS-4003-001 Organization of Programming Languages Fall 2017
Lab Assignment 5

Lambda calculus, Type theory, Formal semantics, Program analysis

Scheme procedures

Due: 6 October, 2017 (submit instructions: here)

Rationale:
    Simple procedure calls in Scheme
 
Lab Problem:
Write a procedure stol in scheme that outputs a set of the M smallest prime numbers in increasing order. Use the algorithmic idea known as a sieve. Let S be the solution list, initially empty. Begin with the consecutive list of numbers
   L = 2,3,4, ... ,N
where N is sufficiently large, which means at least equal to the Mth smallest prime number (unfortunately one cannot assume that the Mth smallest prime number is known when the code is run). Move the smallest number in L (that is, 2) to S. Remove all multiples of 2 from L to get
   L = 3,5,7,9,11, ... ,N
Move the smallest number in L (now 3) to S (which is now the list [2,3]) and remove all multiples of 3 from L to get:
   L = 5,7,11,13,17,19,23, ... ,N
Repeat to get
   S = [2,3,5]
   L = 7,11,13,17,19,23,29, ... ,N
Repeat to get
   S = [2,3,5,7]
   L = 11,13,17,19,23,29,31,37,41,43,47, ... ,N
and so on. The first 100 primes are:
   2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
   97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 
   181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 
   277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 
   383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 
   487 491 499 503 509 521 523 541
Of course, the hard part is to figure out what N is. If you choose too big a number for N some computation will be wasted and if you choose too small a number for N you won't get the right answer.