Y Combinator in Lua

yc.lua

local tests = {
  function ()
    local function fib(n)
      if n < 2 then return n end
      return fib (n - 1) + fib (n - 2)
    end
    return fib (10)
  end

  ;

  function ()
    local function fib (f)
      return function (n)
               if n < 2 then return n end
               return f (f) (n - 1) + f (f) (n - 2)
             end
    end

    return fib (fib) (10)
  end

  ;

  function ()
    local function fib (f)
      local function g (x)
        return f (f) (x)
      end

      return function (n)
               if n < 2 then return n end
               return g (n - 1) + g (n - 2)
             end
    end

    return fib (fib) (10)
  end

  ;

  function ()
    local function fib (f)
      return (function (g)
                return function (n)
                         if n < 2 then return n end
                         return g (n - 1) + g (n - 2)
                       end
              end) (function (x)
                      return f (f) (x)
                    end)
    end

    return fib (fib) (10)
  end

  ;

  function ()
    local function fib_inner (g)
      return function (n)
               if n < 2 then return n end
               return g (n - 1) + g (n - 2)
             end
    end

    local function fib (f)
      return fib_inner (function (x)
                          return f (f) (x)
                        end)
    end

    return fib (fib) (10)
  end

  ;

  function ()
    local function fib_inner (g)
      return function (n)
               if n < 2 then return n end
               return g (n - 1) + g (n - 2)
             end
    end

    local fib = (function (f)
                   return fib_inner (function (x)
                                       return f (f) (x)
                                     end)
                 end) (function (f)
                         return fib_inner (function (x)
                                             return f (f) (x)
                                           end)
                       end)


    return fib (10)
  end

  ;

  function ()
    local function fib_inner (g)
      return function (n)
               if n < 2 then return n end
               return g (n - 1) + g (n - 2)
             end
    end

    function y (g)
      return (function (f)
                return g (function (x)
                            return f (f) (x)
                          end)
              end) (function (f)
                      return g (function (x)
                                  return f (f) (x)
                                end)
                    end)
    end

    return y (fib_inner) (10)
  end

  ;

  function ()
    function y (g)
      return (function (f)
                return g (function (x)
                            return f (f) (x)
                          end)
              end) (function (f)
                      return g (function (x)
                                  return f (f) (x)
                                end)
                    end)
    end

    return y (function (g)
                return function (n)
                         if n < 2 then return n end
                         return g (n - 1) + g (n - 2)
                       end
              end) (10)
  end
}


for i, f in ipairs (tests) do
  local val = f ()
  print (i .. ": " .. tostring (val))
end

yc.md

Published