Pytanie call / cc w Lua - Możliwe?


Artykuł Wikipedii o Kontynuacja mówi:
"W dowolnym języku, który obsługuje zamknięcia, możliwe jest pisanie programów w stylu kontynuacji przekazywania i ręcznie zaimplementuj połączenie / cc. "

Jest to prawdą i muszę wiedzieć, jak to zrobić, lub nie jest prawdą, i to stwierdzenie musi zostać poprawione.

Jeśli to prawda, pokaż mi, jak zaimplementować połączenie / cc w Lua, ponieważ nie widzę sposobu.

Myślę, że byłbym w stanie zaimplementować wywołanie / cc ręcznie, jeśli Lua ma funkcję coroutine.clone, jak wyjaśniono tutaj.

Jeśli zamknięcie nie wystarcza do wdrożenia połączenia / cc, to co jeszcze jest potrzebne?

Poniższy tekst jest opcjonalnym odczytem.
P.S .: Lua ma kontynuację jednego strzału ze swoim coroutine table. Funkcja coroutine.clone pozwoliłaby mi sklonować ją, aby zadzwonić do niej wiele razy, a tym samym efektywnie umożliwić wywołanie / cc (chyba że źle zrozumiałem połączenie / cc). Jednak funkcja klonowania nie istnieje w Lua. Ktoś na kanale IRC Lua zasugerował, że używam biblioteki Plutona (implementuje serializację), aby sterować korupcją, kopiować ją, a następnie odmagam i użyć ponownie. Chociaż to prawdopodobnie zadziałałoby, bardziej interesuje mnie teoretyczna implementacja połączenia / cc oraz znalezienie minimalnego zestawu funkcji, które język musi posiadać, aby umożliwić jego ręczne wdrażanie.

EDYCJA 1: Ok, ludzie, pomóżcie mi tutaj, zajęło mi to dużo czasu, ponieważ nie znam żadnego Planu, ale wymyśliłem coś, co powinno nam pomóc. Proszę spojrzeć na kody poniżej. Pierwszy to program w Scheme, drugi to ten sam program, ale w Lua.
Mam nadzieję, że to nam pomoże. Wierzę, że jesteśmy bardzo blisko.

P.S .: Te przykłady pochodzą z pierwszego przykładu na artykuł w Wikipedii na temat CallCC. Wersja schematu

(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



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



Używam DrScheme i Lua dla Windows - dla każdego, kto chce pomóc, są dwa łatwe do pobrania i zainstalowania narzędzia, które działają.


21
2018-05-13 14:33


pochodzenie




Odpowiedzi:


Istnieją dwa warunki wstępne do ręcznego wdrożenia połączenia / cc według cytatu z Wikipedii:

  1. język musi obsługiwać zamknięcia
  2. musisz napisać swój program w stylu przekazywania kontynuacji (CPS)

Podejrzewam, że nie spodoba ci się # 2.

Aby napisać swój program w stylu przekazywania kontynuacji:

  1. Każda funkcja musi przyjąć argument kontynuacji
  2. Funkcje muszą powrócić, wywołując ich kontynuację

Tak, używając k jako nazwę argumentu kontynuacji, funkcja wyglądałaby następująco:

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

Może wykorzystać ten poziom print jako jego kontynuację, tak powołując się multiplyadd na najwyższym poziomie wyglądałby tak:

multiplyadd(print, 2, 4, 1)

Przy takim rusztowaniu możemy zdefiniować call / cc jako

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

Zauważ, że powyższe multiplyadd w rzeczywistości oszukuje * i + nie są w CPS. Bardzo ciężko jest dodać wszystkich operatorów w postaci CPS, zastąpić wszystkie funkcje biblioteki Lua odpowiednikami CPS i przetłumaczyć / wygenerować cały kod na CPS; widzieć szczegóły tutaj.


18
2018-05-13 16:28



Wow, bardzo mnie to zrozumiałeś. Czy możesz rozwinąć definicję funkcji callcc? Zwłaszcza wyjaśniając część, która pozwala mu pamiętać, zapisz / zapamiętaj, że działa cały stan, taki jak Schemat wywołania / cc. - PeterM
Chyba mam problemy z używaniem tej funkcji callcc - w Scheme musisz ustawić miejsce dla połączenia / cc do skoku, ale w CPS nie masz ... to mnie wyrzuca. - PeterM
Ponieważ k jest zamknięciem, do którego wróci callcc, przekazanie go do jego argumentu f wykonuje zadanie call / cc [właśnie zredagowałem moją definicję powyżej, ponieważ zapomniałem wrócić poprawnie]. To proste, gdy program jest w CPS, ponieważ kontynuacja jest zawsze dostępna; w Scheme jest ukryty, a zadanie call / cc jest trudniejsze (na poziomie językowym implementacja może być tak samo trywialna w kompilatorze), ponieważ musi "reifikować" kontynuację. - Doug Currie
Ok, czy to jest twoja definicja callcc równoważna z Scheme? Czy oznacza to, że funkcja przechwytuje kontynuację, więc mogę ją później wywołać? Zawsze myślałem, że nazwa "callcc" wprowadzała w błąd (przynajmniej ze względu na sposób, w jaki jest używany w Scheme). - PeterM
Tak, callcc jest równoważny Scheme z tym wyjątkiem, że kontynuacja jest jawnym argumentem (ponieważ program jest w CPS), a nie ukrytym argumentem (ponieważ Scheme używa stylu bezpośredniego). - Doug Currie


Przypuszczam, że zapomniałeś o napisaniu programu w kontynuacji przejścia styl. Gdy to zrobisz, wywołanie / cc jest trywialne (w Lua lub w jakimkolwiek innym języku), ponieważ kontynuacja będzie jawnym parametrem dla wszystkich funkcji (call / cc w zestawie).

PS: oprócz zamknięć, potrzebujesz również prawidłowych wywołań do programu w kontynuacji przekazywanie stylu.


17
2018-05-13 16:04



Przede wszystkim, to zaszczyt, że możesz odpowiedzieć na moje pytanie. Jestem całkowicie zakochany w twoim języku, z wielu różnych powodów (mały rdzeń, integracja C, bardzo spójna gramatyka, rzeczywiste zamknięcia, funkcje pierwszej klasy, itd.). A teraz odpowiedź: PS bardzo dużo wyjaśnia. Czy byłoby to niegrzeczne, gdybym poprosił o przykładową implementację call / cc w Lua, że ​​Lua pozwala zarówno na zamknięcie, jak i optymalizację połączeń? :) - PeterM
Zgadzam się z odpowiedzią Normana Ramseya poniżej. Sądzę, że lepszym pytaniem byłoby, czy są jakieś plany wprowadzenia pierwszej klasy kontynuacji, a co za tym idzie callcc w Lua? ;) - PeterM
Łał! Panie Ierusalimschy, witamy w StackOverflow! - Alexander Gladysh
Zobacz EDYCJA 1 powyżej. - PeterM
Słuszna uwaga. Edytowałem Wikipedię, aby wyjaśnić prawidłowe wywołania ogona. Artykuł o "rekursji ogona" jest przerażający ... - Norman Ramsey


Odpowiadając na pytanie dotyczące planów połączenia / DW w Lua: Nie ma planów połączenia / cc w Lua. Przechwytywanie kontynuacji jest albo zbyt kosztowne, albo wymaga analizy kodu znacznie wykraczającej poza możliwości kompilatora Lua. Istnieje również problem, że kontynuacje Lua mogą obejmować części w C.

Z Coroutinami możemy już jednak implementować call / cc1 w Lua (kontynuacje one shot). Jest to wystarczająco dobre dla wielu zastosowań kontynuacji.


7
2018-05-14 16:56



Mogę to zrozumieć. Jakieś plany dotyczące coroutine.clone, podobnie jak te wprowadzone przez Mike'a Pall'a na link w moim oryginalnym wpisie? - PeterM
Aby zobaczyć działający przykład callcc w Lua, używając zmodyfikowanego Lua, który implementuje coroutine.clone, zobacz: github.com/torus/lua-call-cc/blob/master/callcc.lua . Niedługo to wypróbuję. :) - PeterM


Kluczową frazą jest

Możliwe jest wdrażanie programów w styl kontynuacji przejścia

(Podkreśl moje.) Robisz to, biorąc regularne programy "w stylu bezpośrednim" i konwertując je do stylu kontynuacji przejścia (CPS) przez transformację programu zwaną Transformacja CPS. Kluczem jest to, że transformacja CPS call/cc jest prostą funkcją.

To nie jest praktyczne dla programistów.  Transformacja CPS ma dwa zastosowania:

  • Jako teoretyczny pomysł studiowania cech językowych, szczególnie operatorów kontrolnych
  • Jako przejście w kompilatorze używającym CPS jako języka pośredniego

Nie chcesz nigdzie w pobliżu robić transformacji CPS na kod Lua, zwłaszcza nie ręcznie.


2
2018-05-13 21:27



Możesz nie chcieć pisać całych aplikacji za pomocą CPS, ale całkowicie praktyczne jest zaimplementowanie indywidualnych algorytmów do rozwiązywania podproblemów w ten sposób. - sigfpe
transformacja CPS wywołania / cc jest prostą funkcją - Ostrożnie! call / cc może być zdefiniowane w celu transformacji CPS za pomocą prostej funkcji, ale nie jest to transformacja CPS niczego, ponieważ nie powraca przez wywołanie jej kontynuacji. - Charles Stewart
Pytanie brzmiało "jak", a nie "powinno". - Lloyd Moore


Oto mój przelicznik cps w schemacie, po prostu podaj go każdej funkcji, którą chcesz przekonwertować.

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

-2
2017-11-21 16:29



-1 Pytanie dotyczy Lua. - BMitch
Nie ma to znaczenia w odniesieniu do pytania. - Lloyd Moore