Short lambdas, promises, and lazy lists

[Luis Carvalho <lexcarvalho@...>]

Hi,

I took the laziness from this end of year holiday season to play a little with
the token filter patch, especially with the short lambda syntax. Here's a
short write-up of my findings; I'm sharing it in the hope of being useful to
somebody. :) Merry Christmas and happy holidays!

[ Short lambdas, promises, and lazy lists ]

The recent suggestion for a short, light function syntax using token filters
[1] makes for a straightforward way of defining a /promise/ as a nullary
function,

  \(exp) --> function () return exp end

To force the delayed exp, we would simply need to call the (anonymous)
function.

A more efficient promise would, however, memoize the result. One way of using
token filters in this setup would be:

  &(exp) --> function ()
               local result, forced
               return function ()
                 if not forced then result, forced = exp, true end
                 return result
               end
             end

The first notation is simpler though, and should still be fine if we
explicitly cache the result. Here's a simple module for a promise object as a
table that stores the result at its first position and a *non*-forced status at
its second position:

  -- promise.lua
  local assert, type, setmetatable = assert, type, setmetatable
  
  local function force (p)
    if p[2] then -- force promise?
      p[1], p[2] = p[1](), nil
    end
    return p[1]
  end
  
  local _P = {__call = force}
  return function (f) -- delay
    assert(type(f) == "function", "function expected")
    return setmetatable({f, true}, _P)
  end

The token filter is still useful here to shorten the notation,
 
  > delay = require "promise"
  > p = delay(\(1))
  > print(p()) -- force
  1

and so, from now on, I will stick with the short lambda syntax.

Now, for an application of promises, let us implement lazy lists. Following a
long tradition, lists are built using cons cells, but we incorporate promises
by having a /delayable/ cons. Let us take a look at the list module:

  -- list.lua
  local assert, type, setmetatable = assert, type, setmetatable

  list = {}
  local _L = { __index = list }
  
  local cons = function (h, t, delayed) -- delayable cons cell
    assert(not delayed or (delayed and type(t) == "function"),
        "function expected for delayed cons")
    return setmetatable({h, t, delayed}, _L)
  end
  list.cons = cons

  local car = function (l) return l[1] end
  list.car = car

  local cdr = function (l)
    local v = l[2]
    if l[3] then -- delayed?
      v = v() -- force
      l[2], l[3] = v, nil -- forced (non-delayed)
    end
    return v
  end
  list.cdr = cdr

  return list

The first and second positions of a cons cell are, as usual, its car and cdr;
the cdr, however, is what makes the cell delayable. The second and third
positions of the cons cell are exactly like the first two positions in the
promise object: they store the function when not forced and the result after
forcing, and the non-forced status respectively.

We can already use our lists as /streams/. Here are a few examples adapted
from SICP:

  > list = require "list"
  > ones = list.cons(1, \(ones), true)
  > print(ones:cdr():cdr():cdr():car()) -- ad infinitum
  1
  > intsfrom = function (n) return list.cons(n, \(intsfrom(n+1)), true) end
  > integers = intsfrom(1)
  > print(integers:cdr():cdr():cdr():car())
  4
  > fibaux = function (a, b) return list.cons(a, \(fibaux(b, a+b)), true) end
  > fibs = fibaux(0, 1)
  > print(fibs:cdr():cdr():cdr():car())
  2

Let us continue with a more complete list implementation. We need a sentinel
element that represents an empty list,

  local null = cons(); null[2] = null -- sentinel
  list.null = null

  list.isempty = function (l) return l == null end

and a filter method that discriminates lazy lists from standard lists by using
delayed cons cells:

  local function filter (l, f, delayed)
    if l == null then return null end
    local v = car(l)
    if f(v) then
      if delayed then -- delayed cons?
        return cons(v, \(filter(cdr(l), f, true)), true)
      else
        return cons(v, filter(cdr(l), f))
      end
    else
      return filter(cdr(l), f, delayed)
    end
  end
  list.filter = filter

Another example from SICP:

  > notdivisibleby = function (n) return \x (x % n ~= 0) end
  > sieve = function (l)
  >> local c = l:car()
  >> local f = l:cdr():filter(notdivisibleby(c), true)
  >> return list.cons(c, \(sieve(f)), true)
  >> end
  > primes = sieve(intsfrom(2))
  > print(primes:cdr():cdr():cdr():car())
  7

For our next two examples we need another important routine that operates on
two lists and, like /filter/, is also delayable:

  local function map2 (l1, l2, f, delayed)
    if l1 == null and l2 == null then return null end
    if delayed then
      return cons(f(car(l1), car(l2)), \(map2(cdr(l1), cdr(l2), f, true)), true)
    else
      return cons(f(car(l1), car(l2)), map2(cdr(l1), cdr(l2), f))
    end
  end
  list.map2 = map2

The /integers/ and /fibs/ streams can now be coded as:

  > add2 = \x,y (x + y)
  > addstreams = function (s1, s2) return list.map2(s1, s2, add2, true) end
  > integers = list.cons(1, \(addstreams(ones, integers)), true)
  > fibs = list.cons(0, function()
  >> return list.cons(1, \(addstreams(list.cdr(fibs), fibs)), true)
  >> end, true)

Finally, here are a couple more utilitary routines that are not delayable:

  local function take (l, n)
    if n == 0 then return null end
    return cons(car(l), take(cdr(l), n - 1))
  end
  list.take = take

  local function foreach (l, f)
    if l == null then return l end
    f(car(l)); foreach(cdr(l), f)
    return l -- for chaining
  end
  list.foreach = foreach

Let us test our new versions:

  > primes:filter(\x (x > 1000), true):take(5):foreach(print)
  1009
  1013
  1019
  1021
  1031

[Note]
The short lambda token filter patch used here is due to lhf:

[1] http://lua-users.org/lists/lua-l/2010-11/msg00808.html 

Unfortunately, it fails when composed:

  > curriedadd2 = \x(\y(x+y))
  stdin:1: unexpected symbol near '\'


Cheers,
Luis

-- 
Computers are useless. They can only give you answers.
                -- Pablo Picasso

-- 
Luis Carvalho (Kozure)
lua -e 'print((("lexcarvalho@NO.gmail.SPAM.com"):gsub("(%u+%.)","")))'