LUA Лямбда-исчисление

Krutoy · 5 марта, 2022

Я пишу свой интерпретатор на Lua для роботов. Мне потребовалось использовать лямбда-вычисления.

Задача - написать функцию L, где L(f, n) выдавало бы функцию Ln(a1)(a2)(...)(an) которая при выполнении выдает f(a1, a2, ..., an).

@ProgramCrafter подсказал написать так:

local function L(f,n)
  if n<=1 then return f
  else
    return function(a)
      return L(function(...)
        return f(a,...)
      end, n-1)
    end
  end
end

Такая функция работает при значениях n>=1, но не работает с n=0

f = L(print, 2)
f(1)(2) -- печатает: 1 2

f = L(print, 0)
f() -- выдает функцию print

Вопрос:

Нужна функция L, которая принимает в параметр функцию f и дополнительно n аргументов - стандартных значений, которые так же будут показывать количество аргументов.

local function L(f, ...)
  -- ???
end

-- Функция для примера - просто выводит три своих параметра
local function abc(a, b, c)
    return 
        '"a:'..tostring(a)..
        ' b:'..tostring(b)..
        ' c:'..tostring(c)..'"'
end

local f = L(abc, 'a', 'b', nil) -- Создаем λ-функцию с тремя значениями по умолчанию

-- Должно выводить:
print( f(1)(2)(3) ) -- "a:1 b:2 c:3"
print( f()()() ) -- "a:a b:b c:nil"
print( f(nil, 2)() ) -- "a:a b:2 c:nil"

ECS · 5 марта, 2022

1 час назад, Krutoy сказал:
Такая функция работает при значениях n>=1, но не работает с n=0
f = L(print, 2)
f(1)(2) -- печатает: 1 2

f = L(print, 0)
f() -- выдает функцию print

Если запустить этот пример, то f() не выдает ничего, хотя сказано обратное. Пруф:

image.png.263ecb04670665da57312fce0aeece49.png

image.png.ce69c01c526c01881e0985007d05efff.png

Поясни, пожалуйста, должна ли функция L по ТЗ выдавать функцию print, если n = 0, или же наоборот не должна

ECS · 5 марта, 2022

local function L(f, ...)
  local defaults = {...}

  if #defaults == 0 then
    return f
  end

  local defaultIndex = 1
  local fArgs = {}

  local function appendNextArg()
    if defaultIndex > #defaults then
      return f(table.unpack(fArgs))
    end

    return function(fArg)
      table.insert(fArgs, fArg or defaults[defaultIndex])
      defaultIndex = defaultIndex + 1

      return appendNextArg()
    end
  end

  return appendNextArg()
end

f = L(function(a, b, c) return a .. b .. c end, 'a', 'b', 'c')
print(f()('e')()) -- Нужно что бы вывело "aec"

f = L(function() print('succes!') end)
f() -- Должно выводить "succes!"

image.png.70769e92359f13ee1a8ee0bbe1b6fe96.png

В общем, не уверен, что я правильно понял задачу, но ТЗ из второго примера результат соответствует

Krutoy · 5 марта, 2022

1 час назад, ECS сказал:

В общем, не уверен, что я правильно понял задачу, но ТЗ из второго примера результат соответствует

Спасибо, это ближе к решению.

Но эта функция неправильно работает, если дефолтные значения nil

f = L(function(a, b, c) return
    'a:'..tostring(a)..' b:'..tostring(b)..' c:'..tostring(c)
end, 'a', nil, 'c')

print(f()()()) -- Выводит "a:a b:c c:nil", хотя должно "a:a b:nil c:c"

Если же список дефолтных значений кончается на nil, то вообще ошибка:

f = L(print, 'a', nil, nil)
print(f()()()) -- attempt to call a nil value

Хотя возможно, в Lua вообще нельзя посчитать количество значений из ..., если они кончаются на nil.

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

local function L(f, ...)
  -- ???
end

-- Функция для примера - просто выводит три своих параметра
local function abc(a, b, c)
    return 
        '"a:'..tostring(a)..
        ' b:'..tostring(b)..
        ' c:'..tostring(c)..'"'
end

local f = L(abc, 'a', 'b', nil) -- Создаем λ-функцию с тремя значениями по умолчанию

-- Должно выводить:
print( f(1)(2)(3) ) -- "a:1 b:2 c:3"
print( f()()() ) -- "a:a b:b c:nil"
print( f(nil, 2)() ) -- "a:a b:2 c:nil"

ECS · 5 марта, 2022

2 часа назад, Krutoy сказал:

Хотя возможно, в Lua вообще нельзя посчитать количество значений из ..., если они кончаются на nil

Хе-хе, вот поэтому без внятного ТЗ результат ХЗ: не было ж ни слова про nil'овые дефолты. Вообще вариант у нас лишь один - всегда указывать размер таблицы defaults вручную, если в ней присутствует nil в конце, т.к. lua попросту не воспринимает его ни в случае вараргов, ни при инициализации таблицы напрямую:

print(#{nil, "b", "c"}) -- 3
print(#{"a", nil, "c"}) -- 3
print(#{"a", "b", nil}) -- 2
print(#{[1] = "a", [2] = "b", [3] = nil}) -- 2

Поэтому только ручками, видимо:

local function L(f, fArgsCount, defaults)
  fArgsCount = fArgsCount or 1

  if fArgsCount <= 1 then
    return f
  end

  local fArgIndex = 1
  local fArgs = {}

  local function appendNextArg()
    if fArgIndex > fArgsCount then
      return f(table.unpack(fArgs, 1, fArgsCount))
    end

    return function(...)
      local fArgsParts = {...}

      if #fArgsParts == 0 then
        fArgs[fArgIndex] = defaults and defaults[fArgIndex] or nil
        fArgIndex = fArgIndex + 1
      else
        for i = 1, #fArgsParts do
          fArgs[fArgIndex] = fArgsParts[i] or (defaults and defaults[fArgIndex] or nil)
          fArgIndex = fArgIndex + 1
        end
      end
          
      return appendNextArg()
    end
  end

  return appendNextArg()
end

local function test(name, expectedResult, f)
  local result = f()

  print("[" .. (result == expectedResult and "Passed" or "Failed") .. "] " .. name .. ":")
  print("Expected: " .. tostring(expectedResult))
  print("Got: " .. tostring(result))
  print()
end

test(
  "test 1: no defaults, no result",
  nil,
  function()
    f = L(function() print('succes!') end)
    f()
  end
)

test(
  "test 2: no defaults, every argument is passed directly",
  "a:1 b:2 c:3",
  function()
    f = L(
      function(a, b, c) return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c) end,
      3
    )

    return f(1)(2)(3)
  end
)

test(
  "test 3: no nils in defaults",
  "a:a b:e c:c",
  function()
    f = L(
      function(a, b, c) return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c) end,
      3,
      {'a', 'b', 'c'}
    )

    return f()('e')()
  end
)

test(
  "test 4: nil at defaults middle",
  "a:a b:nil c:c",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      3,
      {'a', nil, 'c'}
    )

    return f()()()
  end
)

test(
  "test 5: nil at defaults end",
  "a:1 b:b c:3",
  function()
    f = L(
       function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      3,
      {'a', 'b', nil}
    )

    return f(1)()(3)
  end
)

test(
  "test 6: multiple returns, nil at defaults end",
  "a:a b:2 c:nil",
  function()
    f = L(
       function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      3,
      {'a', 'b', nil}
    )

    return f(nil, 2)()
  end
)

image.png.25fa99c7c9d700c41fd9cb55514a46e2.png

Фичу мульти-ретурна я сделал, фигня вопрос, однако если какая-то функция из цепочки вернет результат с nil в конце - система сдохнет. Тут уж либо опять вручную указывать кол-во аргументов, либо забить болт:

test(
  "test 7: multiple returns with nil at end",
  "a:a b:2 c:nil",
  function()
    f = L(
       function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      3,
      {'a', 'b', 'c'}
    )

    return f(2, nil)()
  end
)

image.png.f201dc29b62bdfe5b4942b25c7c18017.png

Krutoy · 5 марта, 2022

@ECS Огонь, большое спасибо!

Мне самому не хватало мозгов что бы это написать.

Сейчас имплементирую в код и скоро опубликую прогу для робота. Функция правда выглядит громоздко для EEPROM и робота с одной Т1 платой, но ченить придумаю.

Fingercomp · 5 марта, 2022

Всё в Lua сделать можно, я даже статью про это писал. Там про table.pack в основном, но хочу вдобавок напомнить здесь про функцию select, которая умеет как число переданных аргументов возвратить, так и вытащить нужный:

select('#', 2, 4, nil, 8, nil, nil, nil, nil) --> 8
select(2, 2, 4, nil, 8, nil, nil, nil, nil) --> 4       nil     8       nil     nil     nil

Никакие nil ему не помеха.

Krutoy · 5 марта, 2022

4 минуты назад, Fingercomp сказал:
Всё в Lua сделать можно, я даже статью про это писал. Там про table.pack в основном, но хочу вдобавок напомнить здесь про функцию select, которая умеет как число переданных аргументов возвратить, так и вытащить нужный:
select('#', 2, 4, nil, 8, nil, nil, nil, nil) --> 8
select(2, 2, 4, nil, 8, nil, nil, nil, nil) --> 4       nil     8       nil     nil     nil
Никакие nil ему не помеха.

Тогда получается количество аргументов в виде параметра не нужно 😮

ECS · 5 марта, 2022

1 час назад, Fingercomp сказал:

Всё в Lua сделать можно, я даже статью про это писал. Там про table.pack в основном, но хочу вдобавок напомнить здесь про функцию select, которая умеет как число переданных аргументов возвратить, так и вытащить нужный:

Да, я поначалу думал заюзать pack/select, но в нашем случае это ломает кейс без таблицы дефолтных значений:

f = L(function(a, b, c) return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c) end)
f(1)(2)(3)

Здесь невозможно определить, сколько всего аргументов принимает функция f(a, b, c), а затем выполнить её на этапе (3). Хотя, конечно, мы могли бы ограничиться условием, что таблица дефолтных значений требуется всегда, что позволило бы на основании ее размера судить о кол-ве аргументов функции f. Но это уже вопрос к @Krutoy

Зато через pack можно решить проблему с nil в кач-ве последнего аргумента любого из замыканий в цепочке:

Скрытый текст


local function L(f, ...)
  local defaults = table.pack(...)

  if defaults.n == 0 then
    return f
  end

  local fArgIndex = 1
  local fArgs = {}

  local function appendNextArg()
    if fArgIndex > defaults.n then
      return f(table.unpack(fArgs, 1, defaults.n))
    end

    return function(...)
      local fArgsParts = table.pack(...)

      if fArgsParts.n == 0 then
        fArgs[fArgIndex] = defaults and defaults[fArgIndex] or nil
        fArgIndex = fArgIndex + 1
      else
        for i = 1, fArgsParts.n do
          fArgs[fArgIndex] = fArgsParts[i] or (defaults and defaults[fArgIndex] or nil)
          fArgIndex = fArgIndex + 1
        end
      end
          
      return appendNextArg()
    end
  end

  return appendNextArg()
end

local function test(name, expectedResult, f)
  local result = f()

  print("[" .. (result == expectedResult and "Passed" or "Failed") .. "] " .. name)
  print("Expected: " .. tostring(expectedResult))
  print("Got: " .. tostring(result))
  print()
end

test(
  "test 1: no defaults, no result",
  nil,
  function()
    f = L(function() print('success!') end)
    f()
  end
)

test(
  "test 2: no nils in defaults",
  "a:a b:e c:c",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', 'b', 'c'
    )

    return f()('e')()
  end
)

test(
  "test 3: nil at defaults middle",
  "a:a b:nil c:c",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', nil, 'c'
    )

    return f()()()
  end
)

test(
  "test 4: nil at defaults end",
  "a:1 b:b c:3",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', 'b', nil
    )

    return f(1)()(3)
  end
)

test(
  "test 5: multiple returns, nil at defaults end",
  "a:a b:2 c:nil",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', 'b', nil
    )

    return f(nil, 2)()
  end
)

test(
  "test 6: multiple returns with nil at end",
  "a:2 b:b c:nil",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', 'b', nil
    )

    return f(2, nil)()
  end
)

image.png.4aff784f31eb3f2aabc088d2b063aa3e.png

Krutoy · 5 марта, 2022

Я полностью удовлетворен! Спасибо за помощь!

P.S. Уже третий час пишу документацию по своему новому языку....

Krutoy · 5 марта, 2022

Нашел баг.

test(
  "true/false arguments",
  "a:true b:false c:c",
  function()
    f = L(
      function(a, b, c)
        return 'a:' .. tostring(a) .. ' b:' .. tostring(b) .. ' c:' .. tostring(c)
      end,
      'a', 'b', 'c'
    )

    return f(true)(false)()
  end
)

-- [Failed] true/false arguments
-- Expected: a:true b:false c:c
-- Got: a:true b:b c:c

Тот самый случай, когда ты подумал "a and b or c" это настоящий условный оператор, а он подвел.

Но я знаю как исправить, нужно просто заменить на "==nil"

prop · 6 марта, 2022

>lambda calculus

Весь лк или только каррирование?

http://lua-users.org/wiki/CurriedLua

Krutoy · 6 марта, 2022

1 минуту назад, prop сказал:

>lambda calculus

Весь лк или только каррирование?

http://lua-users.org/wiki/CurriedLua

Статью не читал. Лямбда-исчесления знаю ужасно. Знаю только что f(1)(2)(3) - это лямбда.

Войти

LUA Лямбда-исчисление

Вопрос

Krutoy 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

12 ответов на этот вопрос

Рекомендуемые сообщения

ECS 1 903

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

ECS 1 903

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

ECS 1 903

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Fingercomp 4 409

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

ECS 1 903

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

prop 19

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Krutoy Автор вопроса 1 169

Поделиться сообщением

Ссылка на сообщение

Поделиться на других сайтах

Присоединяйтесь к обсуждению

Сообщество

Активность

Игровые серверы

Сервисы

Lua

Krutoy
Автор вопроса
1 169

Krutoy
Автор вопроса
1 169

Krutoy
Автор вопроса
1 169

Krutoy
Автор вопроса
1 169

Krutoy
Автор вопроса
1 169

Krutoy
Автор вопроса
1 169