Реализация отложенного выполнения в Lua?

Question

Мне было интересно, возможно ли реализовать отложенное выполнение, в стиле.NET Linq, в Lua, просто для удовольствия.

В.NET мы можем создать последовательность элементов, известную как IEnumerable, Эти элементы могут быть отфильтрованы с помощью различных средств, таких как map/reduSelect(predicate), Where(predicate)), но вычисления для этих фильтров выполняются только при перечислении через IEnumerable - он откладывается.

Я пытался реализовать подобную функциональность в Lua, хотя с Lua я довольно ржавый и давно не трогал его. Я хотел бы избежать использования библиотек, которые уже делают это для меня, поскольку я хотел бы иметь возможность делать это на чистом Lua, где это возможно.

Моя идея заключалась в том, что, возможно, это будет возможно с использованием сопрограмм..

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 

Однако после написания этого я понял, что это на самом деле не отложенное выполнение... это просто прославленные итераторы, использующие зеленые потоки.

Я пытаюсь реализовать его, чтобы лучше понять, как работает функциональное программирование, на языке, который я уже знаю.

Мысли?

Answer 1

Способ получить отложенное выполнение в Lua - использовать функции. Вам нужно будет изменить свой API с

Where( x > 1 )

в

Where(function(x) return x > 1 end)

---

Полный рабочий пример будет примерно таким, как в следующем коде. Я упустил синтаксис цепочки для простоты.

-- 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

---

В случае, если вам интересно, как обрабатывать цепочки, способ сделать это состоит в том, чтобы тип "поток" был объектом с методами вместо простой функции.

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() )

---

Сопрограммы больше предназначены для того, чтобы позволить вам писать взаимодействующие функции простым способом без необходимости выворачивать одну из них "наизнанку". Например, вполне возможно реализовать итератор для списков без использования сопрограмм:

-- 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

Так как мы возвращаем функцию "getnext", мы можем выбирать только один элемент за раз. Однако нам пришлось "взорвать" цикл for, превратить его в ifs и вручную обновить счетчик цикла. Нам также нужно явно отслеживать все состояния итерации. В этом случае это просто счетчик циклов, но в сопрограммах с рекурсией вам потребуется сохранить стек, и если сопрограмма имеет более одного выхода в своем теле, то вам нужен некоторый флаг состояния, чтобы выполнить работу счетчика программы.