Call / CC в Луа - возможно?

https://stackoverflow.com/questions/2827620

26-09-2019
|

Вопрос

Статья в Википедии на Продолжение говорит:
«На любом языке, который поддерживает замыкание, можно написать программы в продолжение прохождения стиля и Вручную внедрить вызов / CC."

Либо это правда, и мне нужно знать, как это сделать, или это неправда, и это утверждение необходимо исправить.

Если это правда, пожалуйста, покажите мне, как реализовать вызов / CC в LUA, потому что я не вижу, как.

Я думаю, что смогу реализовать Call / CC вручную, если у Луа был функция COROTINE.CLONE, как объяснено здесь.

Если замыкание недостаточно для реализации вызова / CC, то что еще нужно?

Текст ниже является необязательным чтением.
PS: Lua имеет односторонние продолжения с его Coroutine Table. Функция COROTINE.CLONE позволит мне клонировать его, чтобы вызвать его несколько раз, тем самым эффективно создавать возможным Call / CC (если я не понимаю, вызов / CC). Однако эта функция клонирования не существует в LUA. Кто-то на канале Lua IRC предложил, чтобы я использовал библиотеку PluTo (она реализует сериализацию), чтобы маршал COROUTINE, скопируйте его, а затем MotherArshal его и использовать его снова. Хотя это, вероятно, будет работать, я более заинтересован в теоретической реализации Call / CC и нахождение того, какой является фактическим минимальным набором функций, которые необходимо иметь язык, чтобы обеспечить его ручную реализацию.

Редактировать 1: Хорошо, люди, помогите мне здесь, это понадобилось много времени, потому что я не знаю никакой схемы, но я придумал что-то, что должно помочь нам. Пожалуйста, посмотрите на коды ниже. Первый - это программа на схеме, вторая - одна и та же программа, но в LUA.
Надеюсь, это поможет нам. Я верю, что мы очень Закрыть.

PS: эти примеры взяты с первого примера на Статья Википедии на CALCCC. Схема версии

(define call/cc call-with-current-continuation)

; callcc CPS-transformed (thanks to the people from the #scheme channel at freenode.net)
(define cpscallcc
  (lambda (consumer k)
    (let ((cc (lambda (result) (k result))))
      (consumer cc k))))

; this is the continuation we will use to display the "returned" values
(define main-continuation
  (lambda (result)
    (display "--> ")
    (display result)
    (newline)))

; define f function non-CPS
(define (f return)
  (return 2)
  3)

; these are my past attempts at defining a CPS f function
;(define (cps-f return k)
;  (k (return 2)) 3)
;(define (cps-f return k)
;  (k (lambda ()
;       (return 2)
;       3)))

; this is what I came up with - I'm not sure if this is correctly CPS-transformed but I     believe so
(define (cps-f return k)
  (return 2)
  (k 3))

; call the non-CPS f function
(display (f (lambda (x) x))) ; displays 3
(newline)

; call the non-CPS f function with call/cc (I don't understand what this does)
(display (call/cc f)) ; displays 2
(newline)

; now call the CPS version of the f function
(cps-f (lambda (x) x) main-continuation)  ; displays --> 3

; now call the CPS version of the f function with the CPS version of call/cc
(cpscallcc cps-f main-continuation)  ; displays --> 2 but then it also displays --> 3 afterwards -> I'm not sure why it displays the 3 afterwards, as it should only display the 2 just like the non-CPS versions above

Lua версия

-- callcc CPS-version
cpscallcc = function(consumer, k)
    local cc = function(result)
        return k(result)  -- ?or k(result)
    end
    return consumer(cc, k)  -- ?or return consumer(cc,k)
end

-- define f function non-CPS
f = function(ret)
    ret(2)
    return 3
end

-- define f function CPS-version (again, not sure this is correct)
cps_f = function(ret, k)
    ret(2)
    k(3)
end

-- call the non-CPS f function
print(f(function(x) return x end))

-- we cant call the non-CPS f function with callcc because
-- Lua doesnt have callcc, but the line below displays the correct expected output (maybe by accident)
--cpscallcc(f, print)

-- now call the CPS version of the f function
cps_f( function(x) return x end, print )  -- displays 3

; now call the CPS version of the f function with the CPS version of call/cc
cpscallcc( cps_f, print) -- displays 2 and then 3 just like the Scheme version!!
-- so apparently the translation from Scheme to Lua is correct...

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

Решение

Существует два предпосылки для вручную реализации Call / CC на Wikipedia Quote:

Язык должен поддерживать закрытие
Вы должны написать свою программу в продолжение прохождения стиля (CPS)

Я подозреваю, что вы не любите № 2.

Чтобы написать свою программу в продолжение прохождения стиля:

Каждая функция должна пройти аргумент продолжения
Функции должны вернуться, вызывая их продолжение

Итак, используя k Как название аргумента продолжения, функция будет выглядеть так:

function multiplyadd(k, x, y, z) return k(x * y + z) end

Toplevel может использовать print как его продолжение, так что вызывает multiplyadd На верхнем уровне будет выглядеть так:

multiplyadd(print, 2, 4, 1)

С этими лесами мы можем определить Call / CC как

function callcc(k,f) return f(k,k) end

Обратите внимание, что вышеперечисленное multiplyadd на самом деле читы с момента * и + не в CPS. Очень утомительно добавлять все операторы в форме CPS, замените все функции библиотеки LUA с эквивалентом CPS и переводятся / генерировать весь ваш код в CPS; видеть подробности здесь.

Другие советы

Я предполагаю, что вы забыли деталь о написании вашей программы в стиле прохождения продолжения. Как только вы это сделаете, Call / CC тривиально (в LUA или на любом другом языке), так как продолжение будет явный параметр для всех функций (Call / CC включен).

PS: Помимо закрытия, вам также нуждаются в правильных вызовах для программы в процессе прохождения прохождения.

Отвечая на вопрос о планах Call / CC в Луа: нет планов на Call / CC в Lua. Захват продолжения является слишком дорогим, либо требует некоторых кода анальсис, кроме того, что может сделать компилятор LUA. Существует также проблема, что продолжения Lua могут включать части в C.

Однако с CONOUTINES мы уже можем реализовать вызов / CC1 в LUA (продолжение одного выстрела). Это достаточно хорошо для многих применений продолжений.

Ключевая фраза

Можно реализовать программы в Продолжение прохождения

(Упор мой.) Вы делаете это, взяв регулярные программы «прямой стиль» и преобразование их к стилю продолжения прохождения (CPS) трансформацией программы, называемую CPS Transform. Отказ Ключ заключается в том, что преобразование CPS call/cc это простой функция.

Это не практично для программистов. Преобразование CPS имеет два использования:

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

Вы не хотите идти куда угодно рядом с CPS преобразовываться на LUA-код, особенно не вручную.

Возможно: Typescript-to-lua компилятор https://github.com/roblox-ts/roblox-ts. + Call-CC в JS https://github.com/zaoqi/callcc.js/blob/master/callcc.js.

Вот мой CPS-преобразованный схема, просто пропустите его каждую функцию, которую вы хотите преобразовать.

(define (cps-convert function . functions)
  # Since "help" is called at 2 different places...
  (define (help) (error "syntax: (cps-convert f1 f2 ...)"))
  # Single function converter
  (define (convert func)
    # "name" contains the function's name prefixed with "cps-"
    (let ([name (string->symbol
                          (string-append "cps-" (symbol->string func)))])
      # Dirty hack to define "cps-*" in the global environment
     `(eval '(begin
                   # Necessary to prevent the function from being evaluated
                   (define ,name #f)
                                # Magic
                   (set! ,name (lambda (k . args) (k (func args)))))
                 # Global environment
                 (interaction-environment))))
  # Prerequisite... Call help if condition not met
  (if (symbol? function)
      # function is a symbol
      (cond
        # If there is only one function to convert
        [(null? functions) (convert function)]
        # Else ensure every other "functions" are symbols and convert each
        [(every symbol? functions) (apply convert function functions)]
        # Oops! Condition not met!
        [else (help)])
      # Else clause from previous "if"
      (help)))

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow