sieve.tlv

   1 # .tlv file generated by https://github.com/akkartik/teliva
   2 # You may edit it if you are careful; however, you may see cryptic errors if you
   3 # violate Teliva's assumptions.
   4 #
   5 # .tlv files are representations of Teliva programs. Teliva programs consist of
   6 # sequences of definitions. Each definition is a table of key/value pairs. Keys
   7 # and values are both strings.
   8 #
   9 # Lines in .tlv files always follow exactly one of the following forms:
  10 # - comment lines at the top of the file starting with '#' at column 0
  11 # - beginnings of definitions starting with '- ' at column 0, followed by a
  12 #   key/value pair
  13 # - key/value pairs consisting of '  ' at column 0, containing either a
  14 #   spaceless value on the same line, or a multi-line value
  15 # - multiline values indented by more than 2 spaces, starting with a '>'
  16 #
  17 # If these constraints are violated, Teliva may unceremoniously crash. Please
  18 # report bugs at http://akkartik.name/contact
  19 - __teliva_timestamp: original
  20   check:
  21     >function check(x, msg)
  22     >  if x then
  23     >    Window:addch('.')
  24     >  else
  25     >    print('F - '..msg)
  26     >    print('  '..str(x)..' is false/nil')
  27     >    teliva_num_test_failures = teliva_num_test_failures + 1
  28     >    -- overlay first test failure on editors
  29     >    if teliva_first_failure == nil then
  30     >      teliva_first_failure = msg
  31     >    end
  32     >  end
  33     >end
  34 - __teliva_timestamp: original
  35   check_eq:
  36     >function check_eq(x, expected, msg)
  37     >  if eq(x, expected) then
  38     >    Window:addch('.')
  39     >  else
  40     >    print('F - '..msg)
  41     >    print('  expected '..str(expected)..' but got '..str(x))
  42     >    teliva_num_test_failures = teliva_num_test_failures + 1
  43     >    -- overlay first test failure on editors
  44     >    if teliva_first_failure == nil then
  45     >      teliva_first_failure = msg
  46     >    end
  47     >  end
  48     >end
  49 - __teliva_timestamp: original
  50   eq:
  51     >function eq(a, b)
  52     >  if type(a) ~= type(b) then return false end
  53     >  if type(a) == 'table' then
  54     >    if #a ~= #b then return false end
  55     >    for k, v in pairs(a) do
  56     >      if b[k] ~= v then
  57     >        return false
  58     >      end
  59     >    end
  60     >    for k, v in pairs(b) do
  61     >      if a[k] ~= v then
  62     >        return false
  63     >      end
  64     >    end
  65     >    return true
  66     >  end
  67     >  return a == b
  68     >end
  69 - __teliva_timestamp: original
  70   str:
  71     >-- smarter tostring
  72     >-- slow; used only for debugging
  73     >function str(x)
  74     >  if type(x) == 'table' then
  75     >    local result = ''
  76     >    result = result..#x..'{'
  77     >    for k, v in pairs(x) do
  78     >      result = result..str(k)..'='..str(v)..', '
  79     >    end
  80     >    result = result..'}'
  81     >    return result
  82     >  elseif type(x) == 'string' then
  83     >    return '"'..x..'"'
  84     >  end
  85     >  return tostring(x)
  86     >end
  87 - __teliva_timestamp: original
  88   menu:
  89     >-- To show app-specific hotkeys in the menu bar, add hotkey/command
  90     >-- arrays of strings to the menu array.
  91     >menu = {}
  92 - __teliva_timestamp: original
  93   Window:
  94     >Window = curses.stdscr()
  95 - __teliva_timestamp: original
  96   main:
  97     >function main()
  98     >  task.spawn(main_task)
  99     >  task.scheduler()
 100     >  Window:refresh()
 101     >  Window:getch()
 102     >end
 103 - __teliva_timestamp: original
 104   main_task:
 105     >function main_task()
 106     >  Window:clear()
 107     >  local c = task.Channel:new()
 108     >  task.spawn(counter, c)
 109     >  for i=1,10 do
 110     >    print(c:recv())
 111     >  end
 112     >end
 113 - __teliva_timestamp:
 114     >Sat Feb 26 21:50:11 2022
 115   __teliva_note:
 116     >a simple counter
 117   counter:
 118     >function counter(c)
 119     >  local i = 2
 120     >  while true do
 121     >    c:send(i)
 122     >    i = i+1
 123     >  end
 124     >end
 125 - __teliva_timestamp:
 126     >Sat Feb 26 21:54:53 2022
 127   filter_task:
 128     >function filter_task(p, cin, cout)
 129     >  while true do
 130     >    local i = cin:recv()
 131     >    if i%p ~= 0 then
 132     >      cout:send(i)
 133     >    end
 134     >  end
 135     >end
 136 - __teliva_timestamp:
 137     >Sat Feb 26 21:55:46 2022
 138   main_task:
 139     >function main_task()
 140     >  local primes = task.Channel:new()
 141     >  task.spawn(sieve, primes)
 142     >  for i=1,10 do
 143     >    print(primes:recv())
 144     >  end
 145     >end
 146 - __teliva_timestamp:
 147     >Sat Feb 26 21:59:37 2022
 148   __teliva_note:
 149     >filter out multiples of a single number
 150   sieve:
 151     >function sieve(ch)
 152     >  local iota = task.Channel:new()
 153     >  task.spawn(counter, iota)
 154     >  task.spawn(filter_task, 2, iota, ch)
 155     >end
 156 - __teliva_timestamp:
 157     >Sat Feb 26 22:08:07 2022
 158   __teliva_note:
 159     >implement the complete sieve algorithm
 160   sieve:
 161     >-- Set up a Sieve of Eratosthenes (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
 162     >-- for computing prime numbers by chaining tasks, one per prime.
 163     >-- Each task is responsible for filtering out all multiples of its prime.
 164     >function sieve(primes_ch)
 165     >  local c = task.Channel:new()
 166     >  task.spawn(counter, c)
 167     >  while true do
 168     >    local p, newc = c:recv(), task.Channel:new()
 169     >    primes_ch:send(p)
 170     >    task.spawn(filter_task, p, c, newc)
 171     >    c = newc
 172     >  end
 173     >end
 174 - __teliva_timestamp:
 175     >Sat Feb 26 22:09:47 2022
 176   __teliva_note:
 177     >infinite primes
 178   main_task:
 179     >function main_task()
 180     >  local primes = task.Channel:new()
 181     >  task.spawn(sieve, primes)
 182     >  while true do
 183     >    Window:addstr(primes:recv())
 184     >    Window:addstr(' ')
 185     >    Window:refresh()
 186     >  end
 187     >end
 188 - __teliva_timestamp:
 189     >Sat Feb 26 22:09:47 2022
 190   __teliva_note:
 191     >clear screen when it fills up; pause on keypress
 192     >
 193     >In Teliva getch() implicitly refreshes the screen.
 194   main_task:
 195     >function main_task()
 196     >  Window:nodelay(true)
 197     >  Window:clear()
 198     >  local primes = task.Channel:new()
 199     >  task.spawn(sieve, primes)
 200     >  local h, w = Window:getmaxyx()
 201     >  while true do
 202     >    Window:addstr(primes:recv())
 203     >    Window:addstr(' ')
 204     >    local c = Window:getch()
 205     >    if c then break end  -- key pressed
 206     >    local y, x = Window:getyx()
 207     >    if y > h-1 then
 208     >      Window:clear()
 209     >    end
 210     >  end
 211     >  print('key pressed; done')
 212     >  Window:nodelay(false)
 213     >end
 214 - __teliva_timestamp:
 215     >Sat Feb 26 22:27:25 2022
 216   doc:blurb:
 217     >Sieve of Eratosthenes
 218     >https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 219     >
 220     >A demonstration of tasks and channels, the primitives for (cooperative) concurrency in Teliva.
 221     >
 222     >We string together a cascade of tasks connected by channels. Every prime number gets a new task that prints the first incoming number, and then filters out multiples of it from the incoming channel.
 223     >
 224     >This approach has the advantage that we don't need to create an array of n numbers to compute primes less than n.
 225     >
 226     >However, we still need to create p tasks and p channels if there are p primes less than n. Probably not worth it, given tasks and channels are much larger than numbers. This is just a demo.
 227     >
 228     >The noticeable periodic pauses are perhaps due to garbage collection.