Milda Enkonduko al Nedeterminismo en Skimo

Esperanto • English

Laste ĝisdatigita: la 20-an de oktobro 2021

Kelke da plej kernaj paŝoj en mensa kresko baziĝas ne simple pri novajn kapablojn akiri, sed pri novajn administrajn manierojn akiri por tion uzi, kion oni jam scias.
—Marvin MINSKY

wallhaven-333472

Nedeterminisma programado estas tekniko en kiu la fluo de algoritmo ne linearas; kaj ekzistas pluraj eblaj daŭrigoj. La konduto de komputo ankaŭ povas ŝanĝiĝi per la samaj enigoj. Ekzistas multaj metodoj por nedeterminismon atingi. En ĉi tiu artikolo la metodo kiun mi uzos estas retroiĝado.

Kaj cetere, la programlingvon skimo mi uzos por tion atingi. En skimo, oni permesatas por facile iri al antaŭa tempo de komputo kaj reen facile.

Mi ankaŭ diskutos pri la postulaj temoj por ke nedeterminismo en skimo oni pli facile komprenu.

La aktuala daŭrigo

En skimo, la aktuala daŭrigo aŭ la restanta komputo estas la restanta laboro por la ceteron de la komputo taksi.

En la esprimo

la aktuala daŭrigo—la restanta komputo—estas

(lambda (v) v)

kaj la restanta operacio estas

((lambda (v) v) 0)

kiu liveras na

Tio estas la rezulto tial, ke la restanta komputo en tiu nivelo—la plej supra nivelo—estas la identa funkcio.

Memoru, ke la nomo de la argumento de la lambdo ne gravas. Ĝi povas esti v, x, aŭ hundo-kato-muso:

((lambda (hundo-kato-muso) hundo-kato-muso) 0)

Ekzemploj

En la esprimo

(* 1 2)

la restanta komputo por 2—la dua argumento de *—estas

(lambda (v) (* 1 v))

kaj la restanta operacio estas

((lambda (v) (* 1 v)) 2)

kiu, en tiu nivelo de komputo liveras

Konsekvece, la restanta komputo estas

(lambda (v) v)

kaj la restanta operacio estas

((lambda (v) v) 2)

kiu fine liveras, ĉe la plej supra nivelo:

En la esprimo

(+ (* 1 2) 3)

la fluo de la komputo estas

   (* 1 2)
(+         3)

Unue (* 1 2) taksiĝos tiam la rezulto fariĝas la unua argumento por (+ 3). En tiu malplena spaco, la restanta komputoestas

(lambda (v) (+ v 3))

kaj la restanta operacio estas

((lambda (v) (+ v 3)) (* 1 2))

La call/cc-operatoro

En skimo, la aktualan daŭrigon—la restantan komputon—oni povas kapti kiel variablo. Tion oni povas fari per call/cc. Ĝi estas operatoro, kiu nur unu argumenton ekskluzive akceptas—lambdon—sennoman funcion, kun unu argumento:

(call/cc (lambda (k) k))

Se je call/cc oni ne havas, ĝin difinu per:

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

En la angla, ĝi signifas voku funkcion kun la aktuala daŭrigo. Tiun nomon oni ankaŭ povas trakti kiel __voku funkcion kun la restanta komputo_. La funkcio, kiun ĝi vokas estas la lambdo. Kaj cetere, la aktualan daŭrigon—la restantan komputon—call/cc pasas al tiu sennoma funkcio.

En ĉi tiu lambdo:

(lambda (k) k)

k estas funkcio mem kiu unu argumenton akceptas. Do, en

(call/cc (lambda (k) k))

la aktualan daŭrigon—simple la funkcion—call/cc liveras. Tamen, en

(call/cc (lambda (k) (k 0)))

call/cc simple liveras je 0 tial, ke en tiu nivelo—la plej supra nivelo—k estas:

(lambda (v) v)

—la identa funkcio. Pro tio, la voko:

(call/cc (lambda (k) (k 0)))

funkcie ekvivalentas al:

((lambda (v) v) 0)

Kaptado

Reirante al la antaŭa ekzemplo:

(+ (* 1 2) 3)

la aktualan daŭrigon de (* 1 2) oni povas kapti per call/cc:

(+ (call/cc (lambda (k) (* 1 2))) 3)

Tamen, oni povas rimarki ke la funckion k oni ne aplikis al io ajn. La esprimo (* 1 2) taksiĝos, kaj la rezulto iras al (+ _ 3). Alidire, tiu esprimo funkcie ekvivalentas al:

(+ (* 1 2) 3)

Aplikado

La saman ekzemplon uzante, ĉi tie la funkcion k oni apliku:

(+ (call/cc (lambda (k) (k (* 1 2)))) 3)

Ene la voko de call/cc:

            (lambda (k) (k (* 1 2)))

la variablo k estas la aktuala daŭrigo—la restanta komputo. Kio estas la restanta komputo? Jen:

(+                                    3)

—la adicio al 3. Por ke tiun komputon reprezentu kiel funkcio, ĝi fariĝos:

(lambda (v) (+ v 3))

En kie (+ _ 3) estos reprezentata per ĉi tiu lambdo.

Do, la rolo de call/cc estas por lambdon voki, kiun la restanta komputo akceptas. Ĉi tie, la restanta komputo nomiĝas k. Pro tio, la konsekveco de:

(+ (call/cc (lambda (k) (k (* 1 2)))) 3)

funkcie ekvivalentas al

((lambda (v) (+ v 3)) (* 1 2))

Eskapado

(define z #f)
(+ (call/cc (lambda (k) (set! z k) (* 1 2))) 3)

normale la rezulto estos

tamen pro tio, ke la aktualan daŭrigon—k—ni konservis en z, al tiu konservita loko oni povas reiri per:

(z 1)

kiu liveras na

—alian valoron. Tiu meĥanismo donas al oni la kapablon por la komputon eskapi, ĉu kun nova valoro, aŭ malnova valaro, aŭ nenio.

Pro tio, ke la aktuala daŭrigo estas:

(lambda (v) (+ v 3))

la voko

(z 1)

funkcie ekvivalentas al

((lambda (v) (+ v 3)) 1)

anstataŭ

((lambda (v) (+ v 3)) (* 1 2))

Ekzemploj

(let ((x (call/cc (lambda (k) k)))) (x (lambda (o) "saluton")))

la voko

(x (lambda (o) "saluton"))

fariĝas

((call/cc (lambda (k) k)) (lambda (o) "saluton"))

tie, la restanta komputo estas

(lambda (o) "saluton")

kiu iras al la variablo k en la korpo de call/cc. Kiel antaŭe, je k oni apliku al (lambda (o) "saluton") ene alia lambdo:

((lambda (v) (v (lambda (o) "saluton"))) (lambda (o) "saluton"))

kiu liveras na

"saluton"

(((call/cc (lambda (k) k)) (lambda (x) x)) "saluton")

la kerno estas

((call/cc (lambda (k) k)) (lambda (x) x))

Ene la korpo de call/cc, la restanta komputo estas

(lambda (x) x)

kiu iras al la variablo k en la korpo de call/cc. Kiel antaŭe denove, ĝin oni apliku al la lambdo:

((lambda (v) (v (lambda (x) x))) (lambda (x) x))

kiu liveras na

#<procedure x>

Tio signifas, ke ĉi tiun funkcion oni nun povas apliki al la cetera argumento:

(((lambda (v) (v (lambda (x) x))) (lambda (x) x)) "saluton")

kiu liveras na

"saluton"

La amb-operatoro

Unu el la uzoj de la fama amb-operatoro en skimo estas por nedeterminisman programadon realigi per retroiĝado. Pere de tiu meĥanismo, la komputo povas iri al antaŭa stato; valorojn porti; ŝtatojn ŝanĝi; komputon eskapi; kaj pli.

En ĉi tiu artikolo la amb-operatoron oni uzos por la retroiĝadan meĥanismon ebligi.

Difino

La difino kiun oni uzos estas el shido.info/lisp. Ĝi estas makroo por certigi, ke la argumentoj ne taksiĝos. Krome, listojn ĝi interne uzas.

(define call/cc call-with-current-continuation) ;  1
                                                ;  2
(define f #f)                                   ;  3
                                                ;  4
(define-syntax amb                              ;  5
  (syntax-rules ()                              ;  6
    ((_) (f))                                   ;  7
    ((_ a) a)                                   ;  8
    ((_ a b ...)                                ;  9
     (let ((s f))                               ; 10
       (call/cc                                 ; 11
        (lambda (k)                             ; 12
          (set! f (lambda ()                    ; 13
                    (set! f s)                  ; 14
                    (k (amb b ...))))           ; 15
          (k a)))))))                           ; 16
                                                ; 17
(define (cxu-vere? x y)                         ; 18
  (if (equal? x y)                              ; 19
      (list x y)                                ; 20
      (amb)))                                   ; 21
                                                ; 22
(call/cc                                        ; 23
 (lambda (k)                                    ; 24
   (set! f (lambda ()                           ; 25
             (k 'neniuj-elektoj)))))            ; 26

Ĉi tiuj difinoj funkcias ĉe MIT/GNU-skimo, Guile, Scheme48, Scsh, chibi-scheme, Gerbil, Chez-skimo, Chicken, Bigloo, Gauche, kaj Rakido.

Malkonstruado

En ĉi tiu sekcio, la difinon de la amb-operatoro kaj aliaj funkcioj oni malkonstruu. La funkcio cxu-vere? teknike ne estas parto de la difino, tamen ĝin oni uzos por la funkciadon de amb montru.

Jen la malprofundaj paŝoj de la difinoj:

En linio 1-a call/cc bindiĝas al call-with-current-continuation precipe por realigoj kiuj tiun difinon ne havas.
En linio 3-a f bindiĝas al implicita valoro.
En linioj 5-a ĝis 16-a estas la korpo do amb.
En linioj 18-a ĝis 21-a estas ekzempla funckio: se x kaj y egalas, liston ĝi liveras; se ne, amb vokiĝos.
En linioj 23-a ĝis 26-a, call/cc vokiĝas, en kiu la vera komenca valoro de f pravaloriziĝas per lambdo kiu je 'neniuj-elektoj simple liveras.
Oni reiru al la korpo de amb en linioj 5-a ĝis 16-a. En linio 7-a, se amb vokiĝas kiel:
```
(amb)
```
la funkcio f vokiĝos, per kio ajn f povas fari.
En linio 8-a, se amb vokiĝas kiel:
```
(amb "hundo")
```
la argumento "hundo" simple liveriĝas.
Tamen, per pli ol unu argumentoj, la konduto de amb ŝanĝiĝos. Unue, en linio 10-a, la aktuala valoro de f bindiĝas al s, sekve en linio 11-a, call/cc vokiĝas, la aktualan daŭrigon kaptante al k.
Ene la korpo de la lambdo, novan valoron la tutmonda variablo f havos—alian lambdon—kiu ne estas taksota ĝis ĝi estas specife petata. En tiu korpo, la valoron de s antaŭe f havos, tiam k vokiĝos per la valoro b ..., kiu estas la ceteraj argumentoj por amb.
Laste, en linio 16-a, la k funkcio—la restanta komputo—aplikiĝos al la valoro a.

Taksado

Je cxu-vere? uzante, la paŝojn en la uzado de amb oni rigardos. Se la jenan esprimon oni havas,

(cxu-vere? (amb "hundo" "kato" 9) (amb "muso" 9))

jen la pli simpligitaj taksadaj paŝoj:

(amb "hundo" "kato" 9) taksiĝos;
Pro tio, ke pli ol unu argumento estas pasitaj al amb oni iru al linio 9-a;
La aktualan valoron de f de la plej supra nivelo la loka variablo s havos;
```
(lambda () (k 'neniuj-elektoj))
```
La lambdo en linio 12-a vokiĝos kun la restanta komputo al k;
En linio 13-a novan valoron f havos. La valoro estos lambdo;
Kiam la lambdo vokiĝos, la valoron de s—kiu estas la lambdo de paŝo 3-a—k denove havos;

k aplikiĝos al a, en kiu, (k a) estas:

((lambda (v) (cxu-vere? v (amb "muso" 9))) "hundo")

kiu konsekvece fariĝas

((lambda (v) ((lambda (w) (cxu-vere? v w)) "hundo")) "muso")

pro la voko (amb "muso" 9);

Pro tio, ke "hundo" ne egalas al "muso" la amb operatoro vokiĝos, kiel:
```
(amb)
```
Pro tio, ke argumenton (amb) ne havas, la esprimo en linio 7-a okazos;
```
(f)
```
en kiu la valoro de f estas la lambdo en la linioj 13-a ĝis 15-a. La valoro de f denove fariĝas:
```
(lambda () (k 'neniuj-elektoj))
```
Tiam, en linio 15-a, k vokiĝos kiel (k "kato" 9).

La paŝoj ripetiĝos, je cxu-vere? vokante plurfoje. La paŝoj aspektos kiel:

(cxu-vere? "hundo" "muso")
(cxu-vere? "hundo" 9)
(cxu-vere? "kato" "muso")
(cxu-vere? "kato" 9)
(cxu-vere? 9 "muso")
(cxu-vere? 9 9)

Pro tio, ke 9 egalas al 9, la esprimo
```
(list 9 9)
```
taksiĝos en la korpo de cxu-vere? kiu finfine liveras na
```
'(9 9)
```

Finrimarkoj

En ĉi tiu artikolo, oni rimarkis, ke per call/cc nedeterminismon per retroiĝado oni povis atingi facile per amb kaj bazaj skimaj funkcioj. Tamen, estas aliaj pli detalaj kaj pli bonaj metodoj por ĉi tion atingi.

La tipo de daŭrigoj, kiun oni traktis estis nelimigita daŭrigo (angle) kontraste al limigita daŭrigo (angle). Mi ankaŭ devas mencii, ke estas argumento kontraŭ la uzado de call/cc.

Mi esperas, ke iel, bonan ion oni lernis el ĉi tiu afiŝo.