-
1. Data: 2014-11-09 14:03:03
Temat: Makra w jezyku Scheme
Od: g...@g...com
W zeszle wakacje, sprowokowany przez firra i Edka, opowiedzialem nieco
o swoich doswiadczeniach z jezykiem Scheme i programowaniem funkcyjnym.
Poniewaz moje objasnienia spotkaly sie z dosc cieplym przyjeciem,
postanowilem tym razem opowiedziec co nieco o higienicznych makrach
w jezyku Scheme.
Struktura tekstu jest nastepujaca. W rozdziale pierwszym omawiam podstawowe
wyrazenia z jezyka Scheme, a nastepnie w rozdziale drugim opisuje potrzebe
zdefiniowania kilku nowych form specjalnych, oraz ogolna uzytecznosc mozliwosci
definiowania tych form.
W rozdziale trzecim omawiam system makr w stylu Common Lispa (define-macro)
i implementuje w nim wprowadzone we wczesniejszym rozdziale przyklady.
W rozdziale czwartym zamierzam omowic system makr higienicznych R5RS
(syntax-rules) opracowany przez Kenta Dybviga i zaimplementowac w nim
wczesniej zaimplementowane formy, wskazujac na wady i zalety tego systemu.
W rozdziale piatym chcialym podac rozne sposoby obchodzenia ograniczen
systemu syntax-rules, mianowicie (1) ogolniejszy system makr "syntax-case",
(2) zaproponowana przez Olega Kiselyova implementacje maszyny abstrakcyjnej
CK oraz (3) makra pisane "w stylu przekazywania kontynuacji" (continuation
-passing-style)
W rozdziale szostym chcialbym opowiedziec o kilku zastosowaniach makr, ktore
w innym przypadku bylyby trudne do uzyskania. W szczegolnosci zamierzam
zaprezentowac pattern-matcher Wrighta-Shinna.
Na poczatek przesylam pierwsze 3 rozdzialy, a to z dwoch powodow. Po pierwsze
dlatego, ze sa to jedyne rozdzialy, jakie do tej pory napisalem, a po drugie
tekst juz w tym momencie jest znacznie dluzszy, niz pierwotnie planowalem.
Kazdy rozdzial bede wysylal w osobnym poscie. Ponizej zalaczam spis tresci
odnoszacy sie do tego, co napisalem do tej pory:
1. JEZYK SCHEME -- KROTKIE OMOWIENIE
1.1 EWALUACJA WYRAZEN
1.2 FORMY SPECJALNE
1.2.1 FORMA "quote"
1.2.2 FORMA "lambda"
1.2.3 FORMA "define"
1.2.4 FORMA "if"
1.2.5 FORMA "set!"
1.2.6 FORMA "begin"
1.3 FUNKCJE WBUDOWANE
1.3.1 FUNKCJA "apply"
1.3.2 FUNKCJE "values" i "call-with-values"
1.3.3 FUNKCJE "cons", "car" i "cdr"
1.3.4 PREDYKATY POROWNUJACE: "=", "<", "<=", ">", ">=", "eq?"
1.3.5 UWAGI O FUNKCJI "call-with-current-continuation" ("call/cc")
2. POTRZEBA NOWYCH FORM SPECJALNYCH
2.1 UWAGI WSTEPNE
2.2 ZMIENNE LOKALNE -- FORMA "let"
2.3 LOGICZNE SPOJNIKI "and" i "or"
2.4 FORMA SPECJALNA "cond"
2.5 PETLA "while" ORAZ FUNKCJA "call/cc"
2.6 INNE FORMY SPECJALNE
3. MAKRA PROCEDURALNE (define-macro)
3.1 DEFINICJA FORMY "let"
3.1.1 PRELIMINARIA -- ZWYKLA FUNKCJA TRANSFORMUJACA LISTE
3.1.1.1 DEKONSTRUKCJA LISTY WEJSCIOWEJ
3.1.1.2 KONSTRUKCJA FORMY WYJSCIOWEJ
3.1.2 DEFINICJA MAKRA
3.1.2.1 SPECJALNA SKLADNIA DO BUDOWANIA LIST -- FORMA "quasiquote"
3.2 DEFINICJA SPOJNIKOW LOGICZNYCH "or" i "and"
3.3 DEFINICJA FORMY "cond"
3.4 DEFINICJA FORMY "while"
Tekst jest sformatowany zgodnie z wytycznymi trybu ORG dla emacsa.
Fragmenty kodu/ewaluacji rozpoczynam ciagiem znakow ": ", poniewaz
niektore programy usuwaja biale znaki na poczatku linii podczas wyswietlania.
Symbol "===>" nalezy czytac jako "ewaluuje sie do".
Po ukonczeniu wszystkich rozdzialow wrzuce linke do PDFa. Jezeli ktos
bylby zainteresowany, moge tez gdzies wrzucic wygenerowanego PDFa z tym,
co napisalem do tej pory.
Bede wdzieczny za wszelkie pytania, uwagi i komentarze.
-
2. Data: 2014-11-09 14:12:17
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
* JEZYK SCHEME -- KROTKIE OMOWIENIE
** EWALUACJA WYRAZEN
Do glownych zalet Scheme'a nalezy to, ze laczy on w sobie prostote
i semantyczna sile rachunku lambda z prostota i syntaktyczna sila
lispa. Dzieki tym dwom cechom mozna z latwoscia rozszerzac jezyk
o nowe wyrazenia, w naturalny sposob komponujace sie ze starymi,
a takze zmieniac sposob interpretacji istniejacych wyrazen.
Skladnia jezyka Scheme (podobnie jak wszystkich innych lispow)
jest bardzo prosta i stanowi "w pelni onawiasowana notacje polska".
Programy w lispie sa zlozone z nawiasow (przy czym kazdy nawias
otwierajacy musi miec odpowiadajacy nawias zamykajacy), symboli
(czyli dowolnych ciagow znakow oprocz nawiasow oraz znakow "`",
",", "'", ".", "#", podwojnych cudzyslowiow i bialych znakow.
Dodatkowy warunek jest taki, ze -- aby ciag byl uznany za symbol
-- nie moze byc interpretowany jako liczba) oraz liczb. (Standard
Scheme'a definiuje rowniez inne podstawowe jednostki leksykalne, m.in.
stringi, znaki czy wektory, jednak ze wzgledu na prostote
pominiemy sobie tutaj te kwestie)
Przykladowe wyrazenie arytmetyczne w Schemie mogloby miec zatem
postac:
: (+ (* 3 4) (/ 20 5))
Regula ewaluacji jest prosta: oczekujemy, ze wartoscia pierwszego
elementu listy bedzie funkcja (np. dodawanie, mnozenie itd.),
zas aby poznac wartosc calego wyrazenia, musimy zastosowac
funkcje do wartosci argumentow. Jezeli zatem symbole +, * i /
sa zwiazane z konwencjonalnymi dzialaniami arytmetycznymi,
powyzsze wyrazenie mozemy zgodnie z ta regula najpierw przeksztalcic do
: (+ 12 4)
a nastepnie do
: 16
** FORMY SPECJALNE
*** FORMA "quote"
Ciekawa wlasnoscia lispa jest tzw. homoikonicznosc: kod zrodlowy
programow stanowi liste symboli, liczb i ewentualnie innych list,
zas listy, symbole i liczby sa typami danych, na ktorych programy
lispowe moga operowac. Aby powstrzymac ewaluator przed interpretowaniem
symbolu, trzeba uzyc operatora "quote". Wartoscia wyrazenia
: (quote x)
bedzie
: x
Operator "quote" dziala inaczej, niz uzyte powyzej operatory arytmetyczne.
Operatory arytmetyczne (domyslnie) stanowia zwykle funkcje, zas "quote"
jest forma specjalna, ktora charakteryzuje sie tym, ze nie ewaluuje swoich
argumentow. Lisp traktuje zapis 'x rownowaznie z zapisem (quote x).
Aby uzyskac liste symboli (a b c), moglibysmy uzyc funkcji "list":
: (list 'a 'b 'c)
: ===>
: (a b c)
Operator "quote" dziala jednak nie tylko na symbole, ale rowniez na cale
wyrazenia, wiec powyzszy wynik moglibysmy uzyskac rowniez piszac po prostu
: '(a b c)
: ===>
: (a b c)
*** FORMA "lambda"
Oprocz operatora "quote", w jezyku Scheme wystepuje 5 innych podstawowych
form specjalnych. Jedna z nich jest forma "lambda", ktora ma nastepujaca
postac:
: (lambda (argumenty ...) cialo + ...)
Forma "lambda" jest bardzo potezna i w zasadzie wzieta sama w sobie
stanowi kompletny jezyk programowania, pozwalajacy na wyrazenie instrukcji
warunkowych "if-then-else" oraz liczb naturalnych. Osobom zainteresowanym
tym zagadnieniem polecam kurs programowania funkcyjnego autorstwa Johna
Harrisona:
http://www.cl.cam.ac.uk/teaching/Lectures/funprog-jr
h-1996/index.html
Mowiac najkrocej, wyrazenie lambda tworzy nowa funkcje. Najprostszy
przyklad moglby wygladac nastepujaco:
: (lambda (x y)(+ x (* x y)))
W wyniku dostajemy funkcje dwuargumentowa, ktora dodaje swoj pierwszy
argument do iloczynu obu argumentow. Gdybysmy chcieli uzyc tej funkcji,
moglibysmy napisac:
: ((lambda (x y)(+ x (* x y))) 3 4)
Aplikacje wyrazenia lambda mozna pojmowac w taki sposob, ze zastepujemy
cale wyrazenie lambda jego cialem, w ktorym symbole uzyte jako argumenty
zastepujemy wartosciami tych argumentow. W powyzszym przypadku byloby to:
: (+ 3 (* 3 4))
Choc moze to wygladac niepozornie, majac do dyspozycji te regule, mozemy
wyrazic dowolna funkcje rekurencyjna (za sprawa tzw. kombinatorow punktu
stalego, w szczegolnosci -- kombinatora Y).
Dodatkowo Scheme pozwala nam zdefiniowac funkcje mogaca przyjmowac dowolnie
wiele argumentow, jezeli zamiast listy argumentow podamy pojedynczy symbol.
Wowczas z owym symbolem zostaje w ciele funkcji zwiazana lista wszystkich
przekazanych argumentow:
: ((lambda args args) 1 2 3)
: ===>
: (1 2 3)
*** FORMA "define"
Kolejna forma specjalna jest forma "define", ktora pozwala nam nazywac
rozne obiekty. Na przyklad moglibysmy zdefiniowac podnoszenie do kwadratu:
: (define square (lambda (x) (* x x)))
Operacja ta wiaze funkcje, ktora mnozy swoj jedyny argument przez siebie,
z symbolem "square". Zapis
: (square 5)
jest rownowazny zapisowi
: ((lambda (x) (* x x)) 5)
co na mocy wczesniejszej reguly mozna przeksztalcic do
: (* 5 5)
Formy "define" mozna rowniez uzyc do wprowadzenia definicji w zasiegu
wyrazenia "lambda", np.
: (define x 5) ; zasieg zewnetrzny
: x
: ===> 5
: ((lambda () (define x 20) x))
: ====> 20
: x
: ===> 5 ; wartosc w zasiegu zewnetrznym nie ulegla zmianie
Warto wiedziec, ze formalnie nie uznaje sie definicji za wyrazenia,
i na przyklad zapis
: (lambda () (define x 20))
jest bledny, poniewaz cialo wyrazenia lambda musi zawierac przynajmniej
jedno wyrazenie.
*** FORMA "if"
Kolejna forma specjalna, ktora zasluguje na uwage, jest forma
warunkowa "if", o nastepujacej skladni:
: (if warunek wyrazenie-gdy-warunek-spelniony)
lub
: (if warunek
: wyrazenie-gdy-warunek-spelniony
: wyrazenie-w-przeciwnym-razie)
Forma "if" dziala w taki sposob, ze najpierw dokonuje ewaluacji warunku,
i jezeli wartosc warunku jest rozna od wartosci falszu (zapisywanej w Schemie
jako "#f" albo -- wg. najnowszego standardu -- jako "#false"), to
wartoscia calego wyrazenia staje sie wartosc *wyrazenia-gdy-warunek-spelniony*,
zas w przeciwnym razie wartosc wyrazenia albo jest nieokreslona (dla wariantu
pierwszego), albo jest wartoscia *wyrazenia-w-przeciwnym-razie*.
Forma "if" pozwala na definiowanie zlozonych funkcji. Klasycznym przykladem
jest funkcja "silnia":
: (define ! (lambda (n) (if (= n 0) 1 (* n (! (- n 1))))))
Zgodnie z regulami ewaluacji, wyrazenie
: (! 5)
mozna zinterpretowac nastepujaco:
: ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 5)
: ===>
: (if (= 5 0) 1 (* 5 (! (- 5 1))))
: ===>
: (* 5 (! 4))
: ===>
: (* 5 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 4))
: ===>
: (* 5 (if (= 4 0) 1 (* 4 (! (- 4 1)))))
: ===>
: (* 5 (* 4 (! 3)))
: ===>
: (* 5 (* 4 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 3)))
: ===>
: (* 5 (* 4 (if (= 3 0) 1 (* 3 (! (- 3 1))))))
: ===>
: (* 5 (* 4 (* 3 (! 2))))
: ===>
: (* 5 (* 4 (* 3 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 2))))
: ===>
: (* 5 (* 4 (* 3 (if (= 2 0) 1 (* 2 (! (- 2 1)))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (! 1)))))
: ===>
: (* 5 (* 4 (* 3 (* 2 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 1)))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (if (= 1 0) 1 (* 1 (! (- 1 1))))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 (! 0))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 ((lambda (n) (if (= n 0) 1 (* n (! (- n 1))))) 0))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 (if (= 0 0) 1 (* 0 (! (- 0 1)))))))))
: ===>
: (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
: ===> ... ===>
: 120
*** FORMA "set!"
Forma "set!" powoduje przypisanie nowej wartosci do istniejacej (tzn. zwiazanej)
zmiennej. Zmienna moze byc zwiazana albo przy pomocy formy "define", albo
jako parametr formalny w formie "lambda"
: (define x 5)
: x
: ===> 5
: ((lambda (x) (set! x (+ x 1)) x) 7) ; zmiana wartosci zmiennej lokalnej
: ===> 8
: x
: ===> 5
: ((lambda () (set! x (+ x 1)))) ; zmiana wartosci zmiennej zewnetrznej
: x
: ===> 6
*** FORMA "begin"
Formy "begin" uzywamy do grupowania wyrazen, np. wewnatrz ktorejs galezi
formy "if". Warto jednak zwrocic uwage, ze zapis
: (begin definicje/wyrazenia ...)
nie jest rownowazny zapisowi
: ((lambda () definicje/wyrazenia ...))
poniewaz forma "begin" nie wprowadza nowego zasiegu. W szczegolnosci
forma "begin" moze zawierac wylacznie definicje, i np. zapis
: (begin (define symbol-1 wartosc-1) (define symbol-2 wartosc-2))
jest rownowazny zapisowi:
: (define symbol-1 wartosc-1)
: (define symbol-2 wartosc-2)
** FUNKCJE WBUDOWANE
Lista funkcji wbudowanych nie jest szczegolnie istotna. W dotychczasowych
przykladach uzywalem funkcji +,*,-,/,= oraz list.
*** FUNKCJA "apply"
Jest jednak kilka funkcji, ktore zasluguja na szczegolna uwage. Pierwsza
z nich jest "apply". Zapis
: (funkcja argumenty ...)
jest rownowazny zapisowi
: (apply funkcja (list argumenty ...)).
Na przyklad zamiast
: (+ 1 2)
mozna napisac
: (apply + '(1 2))
Ponadto funkcja "apply" moze byc uzyta z dodatkowymi argumentami pomiedzy
argumentem funkcyjnym a lista. Wowczas elementy pomiedzy pierwszym a ostatnim
argumentem zostana dopisane na poczatku ostatniego argumentu. W zwiazku z tym
nastepujace wywolania sa rownowazne:
: (+ 1 2 3)
: (apply + '(1 2 3))
: (apply + 1 '(2 3))
: (apply + 1 2 '(3))
: (apply + 1 2 3 '())
*** FUNKCJE "values" i "call-with-values"
Pewna specyficzna cecha Scheme'a jest to, ze zdefiniowane w nim funkcje moga
zwracac wiecej niz jedna wartosc. Do zwracania wielu wartosci sluzy funkcja
"values", ktora pobiera dowolnie wiele argumentow:
: (values 1 2 3)
: ===> 1
: ===> 2
: ===> 3
Do przechwycenia tych wartosci sluzy funkcja call-with-values, ktora pobiera
dwie funkcje -- producenta (0-argumentowego) i konsumenta (n-argumentowego), np.
: (call-with-values (lambda()(values 1 2 3)) (lambda(a b c)(+ a b c)))
*** FUNKCJE "cons", "car" i "cdr"
Do tej pory w kilku przykladach uzylem dowolnie-wielo-argumentowej funkcji
"list", ktorej wartoscia jest lista podanych do niej argumentow. Warto
jednak wiedziec nieco wiecej o architektonice list. Po pierwsze, istnieje
w Schemie specjanly symbol na oznaczenie listy pustej, a jest on zapisywany tak:
: '()
Po drugie, listy skonstruowane sa z par. Do tworzenia par sluzy funkcja cons:
: (cons 'a 'b)
: ===> (a . b)
Po trzecie, funkcje car i cdr sluza do pobrania odpowiednio pierwszego
i drugiego elementu pary:
: (car (cons 'a 'b))
: ===> a
: (cdr (cons 'a 'b))
: ===> b
Elementy (car x) i (cdr x) bedziemy od tej pory nazywac odpowiednio glowa
i ogonem listy.
Po czwarte, zapis
: (a . (b . (c . ())))
jest rownowazny zapisowi
: (a b c)
zas zapis
: (a . (b . (c . d)))
zapisowi
: (a b c . d)
dla dowolnych dopuszczalnych wartosci a, b, c, d). Jezeli drugi element
ostatniej pary listy nie jest lista pusta, to taka liste nazywamy
"lista kropkowana" ("dotted list").
Stad tez (list 1 2 3) jest rownowazne (cons 1 (cons 2 (cons 3 '()))).
*** PREDYKATY POROWNUJACE: "=", "<", "<=", ">", ">=", "eq?"
Oprocz uzytej w jednym z poprzednich przykladow funkcji "=", sprawdzajacej
rownosc numeryczna, Scheme definiuje kilka innych uzytecznych predykatow
do operowania na liczbach, m.in. "<" (mniejszy od), ktory zwraca
prawde wtw jej argumenty (liczbowe) stanowia ciag rosnacy, np.
: (< 1 3 7)
: ===> #t ; gdzie #t to specjalna wartosc odpowiadajaca prawdzie logicznej
: (< 3 7 1)
: ===> #f
Pozostale funkcje porownujace ("<=", ">", ">=") dzialaja tak, jak mozna
sie po nich spodziewac. Na uwage zasluguje predykat eq?, ktory sprawdza,
czy dwa obiekty sa tym samym obiektem -- na przyklad, czy dwa symbole
sa tym samym symbolem. W przypadku list dzialanie tej funkcji moze byc
zaskakujace:
: (define a '(1 2 3))
: (define b '(1 2 3))
: (eq? a b)
: ===> #f
Wynika to stad, ze listy a i b stanowia osobne obiekty w pamieci.
(W pewnych przypadkach niektore kompilatory moglyby zoptymalizowac powyzszy
kod w taki sposob, ze a i b bylyby tym samym obiektem, i wowczas uzycie
funkcji eq? moze zwrocic #t).
Lista pusta jest zawsze tozsama ze soba, tj.
: (eq? '() '())
: ===> #t
*** UWAGI O FUNKCJI "call-with-current-continuation" ("call/cc")
Ostatnia osobliwa funkcja jest call-with-current-continuation, zazwyczaj
skracana jako call/cc. Z pewnych wzgledow omowie ja dopiero pozniej, gdy
bede mial mozliwosc zademonstrowania jej dzialania na konkretnym przykladzie.
-
3. Data: 2014-11-09 14:34:11
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
* POTRZEBA NOWYCH FORM SPECJALNYCH
** UWAGI WSTEPNE
Dotychczas omowilem zaledwie 6 podstawowych form specjalnych potrzebnych
do tego, zeby budowac zlozone programy. Brakuje tutaj jednak wielu rodzajow
wyrazen, ktore znamy z innych jezykow programowania, takich jak mozliwosc
wprowadzania zmiennych pomocniczych w ciele funkcji, albo logicznych operatorow
koniunkcji i alternatywy (negacje moglibysmy bowiem zdefiniowac jako funkcje:
(define not (lambda (x) (if x #f #t)))).
W tym celu musielibysmy dysponowac jeszcze przynajmniej jedna forma specjalna,
pozwalajaca nam na definiowanie nowych form specjalnych. Nie powinno to byc
trudne, poniewaz -- jak sobie powiedzielismy na poczatku -- programy w lispie
sa listami symboli, wiec wystarczyloby zmodyfikowac reguly ewaluacji w taki
sposob, zeby wszystkie nowe formy specjalne byly przed wykonaniem przeksztalcane
do postaci zawierajacej wylacznie funkcje i pierwotne formy specjalne.
Taka procedura przeksztalcajaca jakies wyrazenie (liste) w inne wyrazenie
(liste) nazywana jest *makrem*. Zanim poznamy szczegoly dotyczace tego,
jak mozna definiowac makra, sprobujemy sie zastanowic, jak bysmy mogli
chciec uzywac danego wyrazenia, oraz jak moglaby wygladac nasza forma
wynikowa. Jedyne ograniczenie jest takie, ze nasza skladnia musi byc
zgodna ze skladnia lispa.
UWAGA! WSZYSTKIE MAKRA PRZEDSTAWIONE W TYM ROZDZIALE SA CZESCIA JEZYKA
SCHEME I NIE TRZEBA ICH DEFINIOWAC. GDYBY CZYTELNIK ZECHCIAL ZDEFINIOWAC
SWOJE WERSJE PONIZSZYCH FORM SPECJALNYCH, ZALECAM NADANIE IM INNYCH NAZW.
** ZMIENNE LOKALNE -- FORMA "let"
Czasem wygodnie jest przechowac dana wartosc w zmiennej pomocniczej.
: (let ((x^2 (* x x))
: (y^2 (* y y)))
: (/ (- x^2 y^2) (+ x^2 y^2)))
W tym wypadku uzylismy zmiennych lokalnych o nazwach "x^2" i "y^2"
do zapamietania wyniku obliczenia dzialan (* x x) i (* y y) (przy zalozeniu,
ze zmienne "x" i "y" sa zwiazane w kontekscie wyrazenia). W przeciwnym
razie musielibysmy dwukrotnie wyliczyc wynik mnozenia, zas glowne wyrazenie
staloby sie rozwleklejsze:
: (/ (- (* x x) (* y y)) (+ (* x x) (* y y)))
Zauwazmy, ze pozadany efekt mozemy uzyskac przy pomocy formy "lambda":
: ((lambda(x^2 y^2)(/ (- x^2 y^2) (+ x^2 y^2))) x y)
Dlatego chcielibysmy, zeby formy postaci
: (let ((nazwa wartosc) ...) cialo + ...)
byly przed ewaluacja transformowane do postaci
: ((lambda (nazwa ...) cialo + ...) wartosc ...)
** LOGICZNE SPOJNIKI "and" i "or"
Moglibysmy zdefiniowac operatory logiczne "and" i "or" jako funkcje:
: (define and2 (lambda (p q) (if p q #f)))
: (define or2 (lambda (p q) (if p p q)))
Z taka definicja sa jest jednak pewien problem: mianowicie, nasz operator
ewaluuje wsztstkie swoje argumenty, choc teoretycznie jezeli pierwszy
argument ma wartosc falszu, to moglibysmy zaniechac ewaluacji kolejnych
argumentow (taka metoda ewaluacji nosi nazwe "short-circit evaluation"
albo "McCarthy evaluation", i implementuja je wlasciwie wszystkie
wspolczesnie uzywane jezyki programowania).
Moglibysmy zatem zyczyc sobie, zeby kod
: (or p q)
byl przed wykonaniem transformowany do postaci
: (if p p q)
jednak wowczas problemem byloby to, ze wyrazenie "p" -- o ile jego wartoscia
nie bylby falsz logiczny -- byloby ewaluowane dwukrotnie. Moglibysmy temu
zapobiec transformujac nasza alternatywe do postaci
: (if p #t q)
albo, pragnac zachowac wartosc wyniku ewaluacji, przeksztalcic ja nastepujaco:
: (let ((T p)) (if T T q))
gdzie T jest symbolem niewystepujacym w q. Moglibysmy tez uogolnic operator
"or" w taki sposob, zeby mogl przyjmowac dowolnie wiele argumentow, i zeby
wyrazenia postaci
: (or p q r ...)
byly transformowane do postaci
: (let ((T p)) (if T T (or q r ...)))
Analogicznie moglibysmy oczekiwac, zeby wyrazenia postaci
: (and p q)
byly przed ewaluacja przeksztalcane do postaci
: (if p q #f)
i ogolniej, interpretowac wyrazenia
: (and p q r ...)
jako
: (if p q (and r ...))
** FORMA SPECJALNA "cond"
Wiekszosc popularnych jezykow programowania posiada specjalna konstrukcje
dla wyboru sekwencyjnego, np.
: if warunek { dzialania ... }
: else if inny_warunek { inne_dzialania ... }
: ...
: else { ostateczne_dzialania ... }
W Schemie moglibysmy uzyc kaskady instrukcji "if":
: (if warunek
: (begin dzialania ...)
: (if inny_warunek
: (begin inne_dzialania ...)
: ... (begin ostateczne_dzialania ...) ...))
Taki kaskadowy kod osiaga jednak dosc szybko duzy poziom zaglebienia
i staje sie nieprzyjemny do czytania. Definiujac Lispa, John McCarthy
wprowadzil forme "cond" o nastepujacej skladni:
: (cond (warunek dzialania ...)
: (inny_warunek inne_dzialania ...)
: ...
: (else ostateczne_dzialania ...))
"else" jest w kontekscie formy "cond" symbolem specjalnym. Powyzszy kod
moglby byc przeksztalcony do postaci rekurencyjnej:
: (if warunek
: (begin dzialania ...)
: (cond (inny_warunek inne_dzialania ...)
: ...
: (else ostateczne_dzialania ...)))
zas forme z jednym warunkiem (przypadek brzegowy), np.
: (cond (ostatni_warunek srodki_ostateczne ...))
moglibysmy interpretowac rownowaznie z
: (if ostatni_warunek (begin srodki_ostateczne ...))
** PETLA "while" oraz funkcja "call/cc"
W sekcji objasniajacej dzialanie formy specjalnej "if" podalem przyklad
funkcji obliczajacej silnie. Podany przeze mnie kod byl czysto funkcyjny,
dzieki czemu mozna bylo dokonac analizy jego dzialania za pomoca prostych
podstawien.
Osoby przyzwyzajone do stylu imperatywnego moglyby zapewne chciec zdefiniowac
silnie nastepujaco:
: (define !!
: (lambda (n)
: (let ((result 1))
: (while (> n 0)
: (set! result (* result n))
: (set! n (- n 1)))
: result)))
Uzylismy tutaj petli "while", ktorej zasada dzialania powinna byc znana
wiekszosci programistow. Moglibysmy ja wyrazic przy pomocy wprowadzonych
dotychczas srodkow. Mianowicie chcielibysmy, zeby kod
: (while warunek dzialania ...)
byl transformowany do postaci
: (begin
: (define LOOP
: (lambda ()
: (if warunek
: (begin dzialania ... (LOOP)))))
: (LOOP))
W tym kontekscie warto omowic dzialanie "call/cc". Otoz jest to specjalna
procedura, ktora pobiera jeden argument, bedacy lambda-wyrazeniem od jednego
argumentu. Tym argumentem jest tzw. kontunuacja -- procedura (mogaca przyjmowac
dowolnie wiele argumentow), ktorej wywolanie spowoduje przerwanie wykonywania
biezacej funkcji i przekazanie sterowania do wyrazenia nastepujacego
bezposrednio po wywolaniu call/cc. Owo wyjasnienie moze brzmiec niezrozumiale,
dlatego warto posluzyc sie przykladem:
: (call/cc
: (lambda (return)
: (display "a")
: (return)
: (display "b")))
: (display "c")
Powyzsze wywolanie wypisze ciag znakow "ac" (wypisanie "b" zostanie pominiete).
Procedure call/cc mozemy zastosowac do zaimplementowania instrukcji "break",
znanej z takich jezykow jak C czy Python. Na przyklad, moglibysmy transformowac
powyzsza petle "while" do postaci
: (call/cc
: (lambda (break)
: (define LOOP
: (lambda ()
: (if warunek
: (begin dzialania ... (LOOP)))))
: (LOOP)))
Kontynuacje (czyli pojecie, pod ktore podpadaja takie konstrukcje z jezykow
imperatywnych, jak "exit" w kontekscie programu, "return", "yield" czy "goto"
w kontekscie funkcji, "continue" i "break" w kontekscie petli oraz "throw" i
"catch" w kontekscie wyjatkow) maja w jezyku Scheme status obiektow, ktore
moga byc przekazywane, zachowywane i wielokrotnie wywolywane. Spora ogolnosc
kontynuacji byla przedmiotem krytyki z powodu pewnych trudnosci implementacji,
duzego zuzycia zasobow i niskiej wydajnosci, co sklonilo teoretykow jezykow
programowania do wprowadzenia roznych wariantow kontynuacji o ograniczonym
zasiegu. Osoby zaintersowane szczegolowa dyskusja odsylam do strony
http://okmij.org/ftp/continuations/against-callcc.ht
ml
Tymczasem dodanie do petli "while" instrukcji "continue" pozostawiam jako
cwieczenie dla ciekawskich.
** INNE FORMY SPECJALNE
Podana powyzej lista form specjalnych jest podzbiorem form specjalnych
definiowanych przez standard Scheme'a. Oprocz nich definiuje sie rowniez
m.in. formy "let*", "letrec" czy "do". Moim celem nie jest jednak omowienie
wszystkich form obecnych w jezyku Scheme, ale zarysowanie, w jaki sposob
obecnosc makr zwieksza sile wyrazu jezyka, oraz zademonstrowanie roznych
podejsc do tego, w jaki sposob mozna owe formy specjalne definiowac.
Pod koniec tekstu podam kilka mniej trywialnych zastosowan dla makr,
a tymczasem przejde do omowienia mozliwych (praktycznych) implementacji.
-
4. Data: 2014-11-09 14:38:54
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
* MAKRA PROCEDURALNE (define-macro)
Niektore wersje Scheme'a obsluguja proste markra proceduralne w stylu
Common Lispa. Pomysl jest taki, ze traktujemy wyrazenie wejsciowe jako
liste, i piszemy procedure, ktora przeksztalca te liste do innej listy.
Do zdefiniowania takiej formy specjalnej uzywamy specjalnej formy
define-macro o nastepujacej postaci:
: (define-macro (nazwa-makra argumenty ...)
: cialo + ...)
gdzie "cialo + ..." powinno zwracac wyrazenie, ktore ma zostac ewaluowane
(lub dalej przeksztalcone). Przyklady powinny nieco te kwestie rozjasnic.
** DEFINICJA FORMY "let"
Gwoli przypomnienia, powiedzielismy sobie w poprzednim rozdziale, ze
forma "let" powinna byc przed ewaluacja transformowana z postaci
: (let ((nazwa wartosc) ...) cialo + ...)
do postaci
: ((lambda (nazwa ...) cialo + ...) wartosc ...)
*** PRELIMINARIA -- ZWYKLA FUNKCJA TRANSFORMUJACA LISTE
Zanim przystapimy do zdefiniowania makra, sprobujmy napisac zwykla funkcje,
ktora przetransformuje liste
: (let ((nazwa-1 wartosc-1) (nazwa-2 wartosc-2)) cialo-1 cialo-2)
do postaci
: ((lambda (nazwa-1 nazwa-2) cialo-1 cialo-2) wartosc-1 wartosc-2)
Nazwijmy pierwsza z powyzszych list (te zawierajaca symbol "let") X, a druge
(te zaczynajaca sie od listy zaczynajacej sie od symbolu "lambda") -- Y.
**** DEKONSTRUKCJA LISTY WEJSCIOWEJ
Zauwazmy, ze:
: (car X) = let
: (cdr X) = (((nazwa-1 wartosc-1) (nazwa-2 wartosc-2)) cialo-1 cialo-2)
: (car (cdr X)) = ((nazwa-1 wartosc-1) (nazwa-2 wartosc-2))
: (cdr (cdr X)) = (cialo-1 cialo-2)
Dla ogolnego przypadku mozemy zatem zdefiniowac sobie:
: (define macro-body (lambda (macro) (cdr macro)))
: (define let-bindings (lambda (macro-body) (car macro-body)))
: (define let-body (lambda (macro-body) (cdr macro-body)))
Jest jasne, ze lista wiazan zwracana przez "let-bindings" ma postac
: ((nazwa wartosc) ...)
Chcielibysmy miec mozliwosc oddzielenia od siebie nazw i wartosci, tzn.
dysponowac funkcjami
: (define bindings-names (lambda (let-bindings) ??))
: (define bindings-values (lambda (let-bindings) ??))
o takich wlasnosciach, ze
: (bindings-names '((nazwa-1 wartosc-1) (nazwa-2 wartosc-2)))
da w wyniku
: (nazwa-1 nazwa-2)
zas
: (bindings-values '((nazwa-1 wartosc-1) (nazwa-2 wartosc-2)))
zwroci
: (wartosc-1 wartosc-2)
Wiemy tez, ze skoro kazde pojedyncze wiazanie ma postac
: (nazwa wartosc)
to mozemy zdefiniowac
: (define binding-name (lambda (binding) (car binding)))
: (define binding-value (lambda (binding) (car (cdr binding))))
Funkcje "bindings-names" i "bindings-values" mozemy zdefiniowac rekurencyjnie.
Jezeli lista wiazan jest pusta, to oczywiscie listy nazw [wartosci] tez beda
puste. W przeciwnym razie zwracamy pare, ktorej glowa jest nazwa [wartosc]
z glowy listy, a ogonem -- lista pozostalych nazw [wartosci]:
: (define bindings-names
: (lambda (let-bindings)
: (if (eq? let-bindings '())
: '()
: (cons (binding-name (car let-bindings))
: (bindings-names (cdr let-bindings))))))
: (define bindings-values
: (lambda (let-bindings)
: (if (eq? let-bindings '())
: '()
: (cons (binding-value (car let-bindings))
: (bindings-values (cdr let-bindings))))))
**** KONSTRUKCJA FORMY WYJSCIOWEJ
Teraz, kiedy jestesmy juz w stanie wyekstrahowac poszczegolne elementy
-- listy nazw i wartosci oraz wrazenia z ciala funkcji -- pozostaje nam
do rozwiazania jeszcze jeden problem. Pozadana przez nas lista wyjsciowa
ma miec postac
: ((lambda (nazwa-1 nazwa-2) cialo-1 cialo-2) wartosc-1 wartosc-2)
Z tego powodu nie mozemy napisac
: (list (list 'lambda <lista-nazw> <cialo-funkcji>) <lista-wartosci>)
poniewaz wowczas lista wynikowa mialaby postac
: ((lambda (nazwa-1 nazwa-2) (cialo-1 cialo-2)) (wartosc-1 wartosc-2))
Mozemy jednak uzyc funkcji "apply" w polaczeniu z funkcja "list", zeby
"splaszczyc" ostatnia liste:
: (apply list (apply list 'lambda <lista-nazw> <cialo-funkcji>) <lista-wartosci>)
Dzieki temu mamy wszystko, co niezbedne do tego, zeby przetransformowac liste
X do postaci Y:
: (define transform-let
: (lambda (macro)
: (apply list
: (apply list
: 'lambda
: (bindings-names (let-bindings (macro-body macro)))
: (let-body (macro-body macro)))
: (bindings-values (let-bindings (macro-body macro))))))
*** DEFINICJA MAKRA
Zaopatrzeni w te wiedze, mozemy jej uzyc do zdefiniowania makra:
: (define-macro (let . macro-body)
: (apply list
: (apply list
: 'lambda
: (bindings-names (let-bindings macro-body))
: (let-body macro-body))
: (bindings-values (let-bindings macro-body))))
Naglowek funkcji stanowi liste kropkowana -- to dlatego, ze nasze makro moze
przyjac dowolnie wiele argumentow. Makro rozni sie od funkcji transform-let
tym, ze w funkcji musielismy pominac sama nazwe makra ("let"), natomiast
procesor makr robi to za nas.
Widac tez, ze definiujac makro, nie uzywamy formy lambda. Przy okazji
warto dodac, ze funkcje mozna definiowac analogicznie -- zamiast pisac
: (define funkcja (lambda (argumenty ...) cialo + ...))
mozemy rowniez napisac
: (define (funkcja argumenty ...) cialo + ...)
i wowczas przed ewaluacja ta druga forma zostanie przetransformowana do tej
pierwszej.
Definicja
: (define my-list (lambda x x))
jest przy tym rownowazna definicji
: (define (my-list . x) x)
Oczywiscie, moglibysmy rowniez zdefiniowac makro przyjmujace stala ilosc
argumentow, nie uzywajac listy kropkowanej:
: (define-macro (two-argument-macro a b)
: (list 'quote (list 'argument-a: a 'argument-b: b)))
**** SPECJALNA SKLADNIA DO BUDOWANIA LIST -- FORMA "quasiquote"
Trzeba przyznac, ze postac otrzymanej przez nas funkcji przeksztalcajacej forme
"let" do wyrazenia "lambda" jest skomplikowana i trudna do czytania. Z tego
powodu hakerzy lispa wymyslili specjalna notacje ulatwiajaca budowanie
zlozonych struktur listowych.
Po pierwsze, przyjmijmy, ze -- tak jak zapisy "(quote X)" i "'X" sa rownowazne,
zapisom
: (quasiquote X)
: (unquote X)
: (unquote-splicing X)
odpowiadaja skroty
: `X
: ,X
: ,@X
"quasiquote" jest zas pewna forma specjalna (ktora mozna zdefiniowac np. przy
pomocy "define-macro"), w obrebie ktorej symbole "unquote" i "unquote-splicing"
maja dodatkowo specjalne znaczenie. Na przyklad, zapis
: `(z ,z ,@z)
jest rownowazny zapisowi
: (apply list 'z z z)
i jesli np. wartoscia symbolu "z" bedzie lista (1 2 3), to wyrazenie otrzyma
wartosc:
: (let ((z '(1 2 3)))
: `(z ,z ,@z))
: ===>
: (z (1 2 3) 1 2 3)
Element "unquote-splicing" moze sie pojawic na dowolnej pozycji, w zwiazku
z czym wartoscia wyrazenia
: (let ((z '(1 2 3)))
: `(,z ,@z z))
bedzie
: ((1 2 3) 1 2 3 z)
Takiego efektu nie moglibysmy uzyskac przy pomocy funkcji "apply" (tak naprawde
pierwsze uzycie operatora "quasiquote" tez tego nie robi. W praktyce do laczenia
list sluzy funkcja "append", ktorej definiowania postanowilem uniknac, zeby
nieco uproscic swoj i tak juz chyba nadmiernie skomplikowany wywod)
Dysponujac makrem "quasiquote", mozemy zdefiniowac nasze makro nastepujaco:
: (define-macro (let . macro-body)
: `((lambda ,(bindings-names (let-bindings macro-body))
: ,@(let-body macro-body))
: ,@(bindings-values (let-bindings macro-body))))
Zapis ten jest juz duzo krotszy i czytelniejszy od poprzedniego, choc do
zrozumienia tego makra wymagana jest znajomosc zdefiniowanych wczesniej
funkcji "let-bindings", "let-body", "binding-names" i "binding-values"
-- analiza kodu, choc stosunkowo prosta, jest mimo wszystko nietrywialna.
** DEFINICJA SPOJNIKOW LOGICZNYCH "or" i "and"
Po tym, co juz zostalo powiedziane, definicja spojnikow logicznych powinna
byc stosunkowo prosta. Zaczniemy od definicji koniunkcji:
: (define-macro (and first . rest)
: (if (eq? rest '())
: first
: `(if ,first (and ,@rest) #f)))
Jedyna nowosc, jaka sie tu pojawia, dotyczy tego, ze lista argumentow sklada
sie z dwoch symboli, przy czym pierwszy (first) zostaje zwiazany z pojedynczym
elementem, zas drugi, pojawiajacy sie po kropce (rest) -- z lista pozostalych
argumentow.
W analogiczny sposob mozemy definiowac funkcje, przy czym zapis
: (define (funkcja arg-1 ... arg-n . args) cialo + ...)
jest rownowazny zapisowi
: (define funkcja (lambda (arg1 ... arg-n . args) cialo + ...))
Spojnik "or" moglby byc zdefiniowany rownie prosto, gdybysmy nie chcieli
zachowac wartosci prawdziwego wyrazenia:
: (define-macro (or first . rest)
: (if (eq? rest '())
: first
: `(if ,first #t (or ,@rest))))
Jezeli jednak chcemy te wartosc zachowac, to -- zgodnie ze wczesniejszymi
rozwazaniami -- musimy wprowadzic nowy identyfikator, tzn. chcemy, zeby
formy o postaci
: (or p q r ...)
byly transformowane do postaci
: (let ((T p)) (if T T (or q r ...)))
dla T niewystepujacego w q, r, ...
Jednym ze sposobow byloby ustalenie pewnego T i zabronienie uzywania go
w formie "or". Takie rozwiazanie byloby jednak dosc nieeleganckie. Innym
sposobem byloby przeanalizowanie zawartosci form q, r, ... pod katem uzytych
symboli. Klasycznym rozwiazaniem jest wygenerowanie identyfikatora przy pomocy
funkcji "gensym".
: (define-macro (or first . rest)
: (if (eq? rest '())
: first
: (let ((T (gensym)))
: `(let ((,T ,first))
: (if ,T ,T (or ,@rest))))))
Wprawdzie operator "gensym" nie gwarantuje, ze wygenerowany symbol nie byl
dotychczas uzyty w kodzie zrodlowym, ale gwarantuje, ze kazde kolejne jego
wywolanie wygeneruje nowy symbol, zas wygenerowane przezen symbole sa na tyle
dziwne, ze prawdopodobienstwo uzycia ich w praktycznym kodzie jest nikle.
** DEFINICJA FORMY "cond"
Przypomnijmy, ze (pomijajac warunki brzegowe) chcielismy transformowac kod
: (cond (warunek dzialania ...)
: (inny_warunek inne_dzialania ...)
: ...
: (else ostateczne_dzialania ...))
do postaci
: (if warunek
: (begin dzialania ...)
: (cond (inny_warunek inne_dzialania ...)
: ...
: (else ostateczne_dzialania ...)))
Kazda pojedyncza galaz makra "cond" ma postac
: (warunek dzialania ...)
Mozemy zatem zdefiniowac funkcje destrukturyzujace warunki, tak jak robilismy
to przy definicji makra "let":
: (define (cond-condition cond-branch) (car cond-branch))
: (define (cond-actions cond-branch) (cdr cond-branch))
Dzieki temu mozemy latwo napisac definicje naszej formy "cond"
: (define-macro (cond first-branch . remaining-branches)
: (let ((first-condition (cond-condition first-branch))
: (first-actions (cond-actions first-branch)))
: `(if ,(or (eq? first-condition 'else) first-condition)
: (begin ,@first-actions)
: ,@(if (eq? remaining-branches '())
: '()
: `((cond ,@remaining-branches))))))
** DEFINICJA FORMY "while"
Definicja formy "while" nie powinna juz wymagac dodatkowych objasnien:
: (define-macro (while condition . actions)
: (let ((LOOP (gensym)))
: `(call/cc
: (lambda (break)
: (define ,LOOP
: (lambda ()
: (if ,condition
: (begin ,@actions (,LOOP)))))
: (,LOOP)))))
-
5. Data: 2014-11-09 16:28:38
Temat: Re: Makra w jezyku Scheme
Od: JDX <j...@o...pl>
On 2014-11-09 14:03, g...@g...com wrote:
[...]
> Bede wdzieczny za wszelkie pytania, uwagi i komentarze.
Miałem szczerą chęć poczytania, ale jednak odstraszył mnie okaleczony
tekst pozbawiony polskich znaków (hmmm, gdy tak z 10 lat temu po raz
ostatni używałem Emacsa i XEmaca, to bez problemu można było w nich
pisać z użyciem polskich znaków :-) ). Poza tym tytuły rozdziałów pisane
wielkimi literami i amerykańskie cudzysłowy ("") zamiast polskich (,,")
słabo wyglądają. Nie żebym był jakimś typograficznym ortodoksem ani, za
przeproszeniem, narodowcem, ale poniżej pewnego poziomu to IMO schodzić
nie wypada. :-)
-
6. Data: 2014-11-09 17:39:00
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
W dniu niedziela, 9 listopada 2014 16:28:48 UTC+1 użytkownik JDX napisał:
> > Bede wdzieczny za wszelkie pytania, uwagi i komentarze.
> Miałem szczerą chęć poczytania, ale jednak odstraszył mnie okaleczony
> tekst pozbawiony polskich znaków (hmmm, gdy tak z 10 lat temu po raz
> ostatni używałem Emacsa i XEmaca, to bez problemu można było w nich
> pisać z użyciem polskich znaków :-) ). Poza tym tytuły rozdziałów pisane
> wielkimi literami i amerykańskie cudzysłowy ("") zamiast polskich ("")
> słabo wyglądają. Nie żebym był jakimś typograficznym ortodoksem ani, za
> przeproszeniem, narodowcem, ale poniżej pewnego poziomu to IMO schodzić
> nie wypada. :-)
Oryginalny tekst zostal napisany z uzyciem polskich znakow, ale przed
wklejeniem tekstu na grupe usunalem je, poniewaz pisze tutaj duzo ludzi
z roznymi kodowaniami i nie kazdy ma obsluge unicode'a (jakkolwiek
absurdalnie by to nie brzmialo, wydaje mi sie, ze takie rozwiazanie
jest najmniej konfliktowe).
Jezeli jestes zainteresowany, to wrzucilem PDF do swojego repozytorium
https://bitbucket.org/panicz/slayer/src/df065378709f
226fa09b0c57ac3aeaa453d0aae0/doc/makra.pdf?at=defaul
t
(co prawda cudzyslowy i paragrafy nadal sa amerykanskie, i tytuly rozdzialow
sa wielkimi literami, ale mysle, ze przy odrobinie dobrej woli mozna przymknac
oko na te tymczasowe mankamenty)
-
7. Data: 2014-11-09 19:04:10
Temat: Re: Makra w jezyku Scheme
Od: JDX <j...@o...pl>
On 2014-11-09 17:39, g...@g...com wrote:
[...]
> Oryginalny tekst zostal napisany z uzyciem polskich znakow, ale przed
> wklejeniem tekstu na grupe usunalem je, poniewaz pisze tutaj duzo ludzi
> z roznymi kodowaniami i nie kazdy ma obsluge unicode'a (jakkolwiek
> absurdalnie by to nie brzmialo, wydaje mi sie, ze takie rozwiazanie
> jest najmniej konfliktowe).
E tam, olać ich. Bo IMO to trzeba być niezłym sztukmistrzem, aby w
obecnych czasach nie być w stanie poprawnie widzieć na newsach poprawnie
zakodowanego unikodowego tekstu.
> Jezeli jestes zainteresowany, to wrzucilem PDF do swojego repozytorium
> https://bitbucket.org/panicz/slayer/src/df065378709f
226fa09b0c57ac3aeaa453d0aae0/doc/makra.pdf?at=defaul
t
> (co prawda cudzyslowy i paragrafy nadal sa amerykanskie, i tytuly rozdzialow
> sa wielkimi literami, ale mysle, ze przy odrobinie dobrej woli mozna przymknac
> oko na te tymczasowe mankamenty)
Dzięki, teraz wygląda i czyta się lepiej. W każdym razie nie oczekuj ode
mnie jakichś merytorycznych komentarzy ponieważ ja na temat Scheme wiem
nie wiele więcej ponad to, że istnieje. :-)
P.S. Widzę, że używasz LaTeX-a. W takim razie ten skrypt
(http://www.zsk.p.lodz.pl/~zajaczko/Algorytmy_i_Pods
tawy_Programowania/Ada_95_Skrypt_Wyd_II.pdf)
IMO może posłużyć za wzór elegancko złożonej i dającej się dobrze czytać
na monitorze publikacji.
-
8. Data: 2014-11-09 19:52:09
Temat: Re: Makra w jezyku Scheme
Od: firr <p...@g...com>
W dniu niedziela, 9 listopada 2014 14:12:19 UTC+1 użytkownik g...@g...com
napisał:
> * JEZYK SCHEME -- KROTKIE OMOWIENIE
>
> ** EWALUACJA WYRAZEN
>
> Do glownych zalet Scheme'a nalezy to, ze laczy on w sobie prostote
> i semantyczna sile rachunku lambda z prostota i syntaktyczna sila
> lispa. Dzieki tym dwom cechom mozna z latwoscia rozszerzac jezyk
> o nowe wyrazenia, w naturalny sposob komponujace sie ze starymi,
> a takze zmieniac sposob interpretacji istniejacych wyrazen.
>
> Skladnia jezyka Scheme (podobnie jak wszystkich innych lispow)
> jest bardzo prosta i stanowi "w pelni onawiasowana notacje polska".
> Programy w lispie sa zlozone z nawiasow (przy czym kazdy nawias
> otwierajacy musi miec odpowiadajacy nawias zamykajacy), symboli
> (czyli dowolnych ciagow znakow oprocz nawiasow oraz znakow "`",
> ",", "'", ".", "#", podwojnych cudzyslowiow i bialych znakow.
> Dodatkowy warunek jest taki, ze -- aby ciag byl uznany za symbol
> -- nie moze byc interpretowany jako liczba) oraz liczb. (Standard
> Scheme'a definiuje rowniez inne podstawowe jednostki leksykalne, m.in.
> stringi, znaki czy wektory, jednak ze wzgledu na prostote
> pominiemy sobie tutaj te kwestie)
>
> Przykladowe wyrazenie arytmetyczne w Schemie mogloby miec zatem
> postac:
>
> : (+ (* 3 4) (/ 20 5))
>
> Regula ewaluacji jest prosta: oczekujemy, ze wartoscia pierwszego
> elementu listy bedzie funkcja (np. dodawanie, mnozenie itd.),
> zas aby poznac wartosc calego wyrazenia, musimy zastosowac
> funkcje do wartosci argumentow. Jezeli zatem symbole +, * i /
> sa zwiazane z konwencjonalnymi dzialaniami arytmetycznymi,
> powyzsze wyrazenie mozemy zgodnie z ta regula najpierw przeksztalcic do
>
> : (+ 12 4)
>
> a nastepnie do
>
> : 16
>
> ** FORMY SPECJALNE
>
> *** FORMA "quote"
>
> Ciekawa wlasnoscia lispa jest tzw. homoikonicznosc: kod zrodlowy
> programow stanowi liste symboli, liczb i ewentualnie innych list,
> zas listy, symbole i liczby sa typami danych, na ktorych programy
> lispowe moga operowac. Aby powstrzymac ewaluator przed interpretowaniem
> symbolu, trzeba uzyc operatora "quote". Wartoscia wyrazenia
>
> : (quote x)
>
> bedzie
>
> : x
>
> Operator "quote" dziala inaczej, niz uzyte powyzej operatory arytmetyczne.
> Operatory arytmetyczne (domyslnie) stanowia zwykle funkcje, zas "quote"
> jest forma specjalna, ktora charakteryzuje sie tym, ze nie ewaluuje swoich
> argumentow. Lisp traktuje zapis 'x rownowaznie z zapisem (quote x).
>
> Aby uzyskac liste symboli (a b c), moglibysmy uzyc funkcji "list":
>
> : (list 'a 'b 'c)
> : ===>
> : (a b c)
>
> Operator "quote" dziala jednak nie tylko na symbole, ale rowniez na cale
> wyrazenia, wiec powyzszy wynik moglibysmy uzyskac rowniez piszac po prostu
> : '(a b c)
> : ===>
> : (a b c)
>
spoko, chcesz to mozna troche jeszcze o tym pogadac - co do tego wyzej to jako tako
rozumiem drzewkową składnie (ktora jest fajna)
- jako tako tez ta węzową formę - głowa i argumenty (zawsze tak jest? czy zcasem sa
jakies inne wariacje?) - nie bardzo kojarze jednak to quote, po co to sie moze
przydac jesli w miejscu programu gdzie mial byc kod pojawia sie takie
nieinterpretowalne symbole to nie bedze syntax error?
-
9. Data: 2014-11-09 20:08:50
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
W dniu niedziela, 9 listopada 2014 19:04:43 UTC+1 użytkownik JDX napisał:
> > Oryginalny tekst zostal napisany z uzyciem polskich znakow, ale przed
> > wklejeniem tekstu na grupe usunalem je, poniewaz pisze tutaj duzo ludzi
> > z roznymi kodowaniami i nie kazdy ma obsluge unicode'a (jakkolwiek
> > absurdalnie by to nie brzmialo, wydaje mi sie, ze takie rozwiazanie
> > jest najmniej konfliktowe).
> E tam, olać ich. Bo IMO to trzeba być niezłym sztukmistrzem, aby w
> obecnych czasach nie być w stanie poprawnie widzieć na newsach poprawnie
> zakodowanego unikodowego tekstu.
Chodzi nie tylko o to. Jak taki sztukmistrz odpowie mi na posta, to
nawet moje ogonki zmieniaja sie w jakies dziwne mutanty, i to dopiero
wyglada nieelegancko
> > Jezeli jestes zainteresowany, to wrzucilem PDF do swojego repozytorium
> > https://bitbucket.org/panicz/slayer/src/df065378709f
226fa09b0c57ac3aeaa453d0aae0/doc/makra.pdf?at=defaul
t
> > (co prawda cudzyslowy i paragrafy nadal sa amerykanskie, i tytuly rozdzialow
> > sa wielkimi literami, ale mysle, ze przy odrobinie dobrej woli mozna przymknac
> > oko na te tymczasowe mankamenty)
> Dzięki, teraz wygląda i czyta się lepiej. W każdym razie nie oczekuj ode
> mnie jakichś merytorycznych komentarzy ponieważ ja na temat Scheme wiem
> nie wiele więcej ponad to, że istnieje. :-)
Wszystkie podstawy sa wylozone w pierwszym rozdziale, wiec nie ma sie
co martwic :)
> P.S. Widzę, że używasz LaTeX-a. W takim razie ten skrypt
> (http://www.zsk.p.lodz.pl/~zajaczko/Algorytmy_i_Pods
tawy_Programowania/Ada_95_Skrypt_Wyd_II.pdf)
> IMO może posłużyć za wzór elegancko złożonej i dającej się dobrze czytać
> na monitorze publikacji.
Pisalem skrypt w emacsie zgodnie ze specyfikacja org. To taka ciut
sformalizowana specyfikacja plikow tekstowych (czesto uzywana np. do
formatowania plikow tekstowych na githubie). Tryb emacsa daje mozliwosc
generowania z tego LaTeXa (przyznam, ze pdfa wyprodukowalem na szybko,
nie bardzo wglebiajac sie w rozne opcje)
-
10. Data: 2014-11-09 20:28:14
Temat: Re: Makra w jezyku Scheme
Od: g...@g...com
W dniu niedziela, 9 listopada 2014 19:52:10 UTC+1 użytkownik firr napisał:
> spoko, chcesz to mozna troche jeszcze o tym pogadac - co do tego wyzej to jako tako
rozumiem drzewkową składnie (ktora jest fajna)
> - jako tako tez ta węzową formę - głowa i argumenty (zawsze tak jest? czy zcasem sa
jakies inne wariacje?)
jezeli idzie o reprezentacje list/drzew, to to jest w ogolnosci bardzo
ciekawe zagadnienie. pare lat temu Guy Steele mial wyklad na ten
temat w kontekscie paralelizacji obliczen: http://vimeo.com/6624203
z cala pewnoscia z operatywnego punktu widzenia podzial na glowe i ogon
jest bardzo wygodny, choc uzywanie list laczonych jest w ogolnosci dosc
niewydajne (np. ze wzgledu na liniowy czas dostepu do elementow)
w przypadku makr nie ma to zazwyczaj szczegolnego znaczenia, bo one sa i tak
wykonywane w trakcie kompilacji wyrazenia (choc oczywiscie ktos moglby stworzyc
jakies makro, ktore dzialaloby skrajnie niewydajnie)
> - nie bardzo kojarze jednak to quote, po co to sie moze przydac jesli w miejscu
programu gdzie mial byc kod pojawia sie takie nieinterpretowalne symbole to nie bedze
syntax error?
nie. symbole sa w lispie jednym z podstawowych typow danych, podobnie jak
np. stringi w javascripcie.
dlatego kiedy piszesz
: x
to ewaluator probuje podstawic wartosc zwiazana z symbolem (albo zglasza
blad, jezeli symbol jest niezwiazany), za to jesli piszesz
: (quote x)
czy tez
: 'x
to otrzymujesz symbol "x"
podobnie, kiedy piszesz
(+ 2 3)
to interpreter ewaluuje to wyrazenie do liczby 5, ale jesli napiszesz
'(+ 2 3)
to wartoscia tego wyrazenia bedzie lista, ktorej pierwszym
elementem jest symbol "+", drugim liczba 2, a trzecim liczba 3
przy okazji ciekawostka: o ile wyrazenia '2 i '3 dadza w wyniku
liczby 2 i 3 (czyli zachowaja sie tak samo, ja wyrazenia 2 i 3),
o tyle ''2 i ''3 dadza w wyniku listy
(quote 2)
i
(quote 3)
(czyli listy, ktorych pierwszym elementem jest symbol "quote", a drugim
liczba)
Analogicznie, ''x da w wyniku liste
(quote x)