I've been wondering whether it was possible to implement deferred execution, .NET Linq-style, in Lua, just for funsies.
In .NET, we can create a sequence of elements known as an IEnumerable. These elements can then be filtered through various means, such as map/reduce (Select(predicate), Where(predicate)), but the computation for these filters are only executed when you enumerate over the IEnumerable - it is deferred.
I've been trying to implement a similar functionality in Lua, although I'm pretty rusty with Lua and haven't touched it for a while. I'd like to avoid using libraries that already do this for me as I'd like to be able to do it in pure Lua where possible.
My idea was that perhaps it would be possible using coroutines..
Enumerable = {
-- Create an iterator and utilize it to iterate
-- over the Enumerable. This should be called from
-- a "for" loop.
each = function(self)
local itr = Enumerable.iterator(self)
while coroutine.status(itr) ~= 'dead' do
return function()
success, yield = coroutine.resume(itr)
if success then
return yield
else
error(1, "error while enumerating")
end
end
end
end,
-- Return an iterator that can be used to iterate
-- over the elements in this collection.
iterator = function(self)
return coroutine.create(function()
for i = 1, #self do
coroutine.yield(self[i])
end
end)
end
}
tbl = {1, 2, 3}
for element in Enumerable.each(tbl) do
print(element)
end
table.insert(tbl, 4)
for element in Enumerable.each(tbl) do
print(element)
end
However, after writing this I realized this isn't really deferred execution.. this is just glorified iterators using green threads.
I'm trying to implement it to get a better understanding on how functional programming works, in a language that I am already aware of.
Thoughts?
The way to get deferred execution in Lua is using functions. You would need to change your API from
Where( x > 1 )
to
Where(function(x) return x > 1 end)
A full working example would be something along the lines of the following code. I left out the chaining syntax to keep it simple.
-- A stream is a function that returns a different value each time you call it
-- and returns nil after the last value is generated. Its a bit like what ipairs returns.
-- Receives a list, returns a stream that yields its values
function Each(xs)
return coroutine.wrap(function()
for _, x in ipairs(xs) do
coroutine.yield(x)
end
end)
end
-- Receives a stream and returns a new stream, filtered by a predicate
function Where(input, pred)
return coroutine.wrap(function()
for x in input do
if pred(x) then
coroutine.yield(x)
end
end
end)
end
local ys = {1,2,3,4,5}
for y in Where(Each(ys), function(x) return x <= 2 end) do
print(y)
end
In case you are wondering how to handle the chaining, the way to do it is to have the "stream" type be an object with methods instead of a plain function.
local Stream = {}
-- The low level stream constructor receives a generator function
-- similar to the one coroutine.wrap would return. You could change the API
-- to something returning multiple values, like ipairs does.
function Stream:new(gen)
local stream = { _next = gen}
setmetatable(stream, self)
self.__index = self
return stream
end
-- Receives a predicate and returns a filtered Stream
function Stream:Where(pred)
return Stream:new(coroutine.wrap(function()
for x in self._next do
if pred(x) then
coroutine.yield(x)
end
end
end))
end
function Stream:Length()
local n = 0
for _ in self._next do
n = n + 1
end
return n
end
function Each(list)
return Stream:new(coroutine.wrap(function()
for _, x in ipairs(list) do
coroutine.yield(x)
end
end))
end
local ys = {10, 20, 30, 40}
print( Each(ys):Where(function(x) return x <= 20 end):Length() )
Coroutines are more about letting you write cooperating functions in a straightforward way without needing to turn one of them "inside out". For example, its perfectly possible to implement an iterator for lists without using coroutines:
-- if you try to code ipairs on your own, without coroutines
-- it might look a bit like this
function Each(xs)
local i=1
return function()
if i <= # xs then
local x = xs[i]
i = i + 1
return x
else
return nil
end
end
end
Since we return a "getnext" function, we are able to only fetch one element at a time. However, we had to "blow up" the for-loop, turning it into ifs and manually updating the loop counter. We also need to keep track of all the iteration state explicitly. In this case its just the loop counter but in coroutines with recursion you would need to keep a stack and if the coroutine has more than one yield in its body then you need some state flag to do the job of the program counter.