lua y combinator

y.lua

#!/usr/bin/env lua

-- recursive
local multiply0; multiply0 = function (x, y, z)
  if x == 0 then return z end
  return multiply0(x - 1, y, z + y)
end

-- explicit function argument, normal
local multiply1 = function (f, x, y, z)
  if x == 0 then return z end
  return f(f, x - 1, y, z + y)
end

-- explicit function argument, curried
local multiply2 = function (f)
  return function (x, y, z)
    if x == 0 then return z end
    return f(f)(x - 1, y, z + y)
  end
end

-- direct call, normal
local multiply3 = function (f, x, y, z)
  if x == 0 then return z end
  return f(x - 1, y, z + y)
end

-- direct call, curried
local multiply4 = function (f)
  return function (x, y, z)
    if x == 0 then return z end
    return f(x - 1, y, z + y)
  end
end

-- binding function to self, normal
local Y1 = function (f)
  return function (...)
    return f(f, ...)
  end
end

-- binding function to self, curried
local Y2 = function (f)
  return f(f)
end

-- recursive Y combinator, normal
local Y3; Y3 = function (f)
  return function (...)
    return f(Y3(f), ...)
  end
end

-- recursive Y combinator, curried
local Y4; Y4 = function (f)
  return function (...)
    return f(Y4(f))(...)
  end
end

-- real Y combinator, normal
local Y5 = function (f)
  return function (...)
    return (function (x)
      return x(x)
    end)(function (x)
      return function (...)
        return f(function (...)
          return x(x)(...)
        end, ...)
      end
    end)(...)
  end
end

-- real Y combinator, curried
local Y6 = function (f)
  return function (...)
    return (function (x)
      return x(x)
    end)(function (x)
      return f(function (...)
        return x(x)(...)
      end)
    end)(...)
  end
end

local profile = function (f)
  --collectgarbage 'stop'
  local M = 1e7
  local N = 4
  local T = os.clock()
  assert(M * N == f(M, N, 0))
  print(os.clock() - T)
  --collectgarbage 'restart'
  --collectgarbage 'collect'
end

profile(  (multiply0))
profile(Y1(multiply1))
profile(Y2(multiply2))
profile(Y3(multiply3))
profile(Y4(multiply4))
profile(Y5(multiply3))
profile(Y6(multiply4))

-- lua     luajit
-- 0.477   0.016
-- 0.508   0.016
-- 1.928   1.216
-- 2.395   1.444
-- 3.816   2.480
-- 3.429   2.249
-- 3.982   2.552