Podczas gdy główny nurt przerabia programowanie obiektowe i powolutku zaczyna trawić paradygmat funkcyjny, powstało już bardzo wiele bardzo ciekawych podejść do programowania. Ostatnio bardzo mi się spodobało programowanie przez dopasowanie (w angielskiej literaturze: nondeterministic programming, o tym czemu takie tłumaczenie za chwilę).
Angielska nazwa, jak rozumiem, bierze się od NDFA (ang. nondeterministic finite automata), będącego modelem obliczeniowym, który od dobrze znanego automatu skończonego (finite state machine) różni się tym, że w FSM przejście między stanami jest określone wyłącznie stanem początkowym i symbolem wejściowym; również każde przejście musi pobierać symbol wejściowy (innymi słowy, nie ma spontanicznej zmiany stanu).
Programowanie przez dopasowanie zawęża nieco tę definicję i oznacza tyle, że pozwala zdefiniować kilka alternatywnych sposobów wykonania zadania bez podania z góry warunku wybrania jednego z nich (jak to ma miejsce w konstrukcji if-then-else). Zwykle tylko niektóre z nich prowadzą do właściwego wyniku. Innymi słowy, wykonanie programu ma, w niesprecyzowany w kodzie sposób, wykorzystać te możliwości aby uzyskać właściwy wynik.
Stąd moja propozycja nazwy — sens podejścia leży w dopasowaniu sposobu działania do konkretnego przypadku. Z kolei określenie niedeterministyczny kojarzy się z algorytmem niedeterministycznym, czyli takim, którego wynik nie wynika wyłącznie z danych wejściowych, przede wszystkim algorytmy oparte o losowość, np. Metoda Monte Carlo. Pojęcia te są zasadniczo niezależne, jedno drugiego nie implikuje (ani na odwrót).
Dodatkowo, nazywa ono podejście cechą, której przecież nie chcemy. Któż chce, żeby jego program był nieprzewidywalny? OK, niektórym może się podobać: „O! nie wiem jak ten program działa, TO MAGIA!”. Brzmi efektownie, ale ja tego nie kupuję, chcę wiedzieć jak mój program działa i tu dobre wieści — wbrew angielskiej nazwie, paradygmat ten może czynić program czytelniejszym.
Podstawowym sposobem realizacji tej idei jest wprowadzenie dwóch działań: przypisania zmiennej kilku równoprawnych wartości; oraz wyboru wartości w oparciu o podany warunek. Rozważmy następującą funkcję sprawdzającą czy liczba jest pierwsza (pseudokod, pełna implementacja w Common Lispie)
pierwsza?(n):
zmienna x w przedziale <2;sqrt(n)>
zwróć: nie (czy x dzieli n bez reszty?)W Common Lispie napisałem taki kod (definicje funkcji choice i must-have — link powyżej).
(defun prime? (n)
(let ((x (apply #'choice
(loop for i from 2 to (- n 1)
collect i))))
(let ((divisors (must-have `(eql (mod ,n ,x) 0))))
(if divisors
(format t "~%~A is not prime, it has divisors: ~{~A~}"
n divisors))
(eql divisors nil))))
(print (prime? 5)) ; T
(print (prime? 6)) ; NIL (2 and 3)
(print (prime? 73)) ; T
(print (prime? 111)); NIL (3 and 37)
(print (prime? 199)); TJako skutek uboczny, mogę podać od razu czynniki pierwsze dla liczby złożonej. Oczywiście kod jest równoważny prostej iteracji (już bez wymieniania dzielników):
(defun prime?(n)
(loop for x from 2 to (floor (sqrt n))
do (if (eql (mod n x) 0) (return-from prime? NIL)))
T)Jednak choć te funkcje dają taki sam wynik, różnią się. Przede wszystkim, wersja przez dopasowanie bezpośrednio wyraża fakt, że nie ma znaczenia w jakiej kolejności będziemy próbować kolejne wartości. Może być to pomocne zarówno dla programisty jak i kompilatora/interpretera. Myślę, że takie postawienie sprawy też lepiej wyraża intencję.
To może lepszy przykład:
(defun repeat (count val)
(loop for i from 1 to count
collect val))
(defun coins (sum)
(let ((coin (choice 0.01 0.02 0.05 0.1 0.2 0.5 1 2 5)))
(loop for count from 1
do (let ((combos (must-have
`(= ,sum
(+ ,@(repeat count coin))))))
(if combos (return-from coins combos))))))Ten program podaje jak, w najmniejszej liczbie monet, wydać daną sumę pieniędzy. Ten problem już nie jest taki trywialny, takie podejście problem znacząco upraszcza. Prościej można chyba tylko tak (Prolog):
coin(X) :-
X = 0.01; X = 0.02; X = 0.05; X = 0.1;
X = 0.2; X = 0.5; X = 1; X = 2; X = 5.
coins(X, [X]) :- coin(X).
coins(X, [H|T]) :-
coin(H), coins(Y, T), X is H + Y.Właściwie, to jest to samo, wyraża tę samą ideę, choć mogą być inaczej implementowane: moja implementacja szybko wyczerpuje stos (bo zbiera wszystkie możliwe kombinacje w liście), a gprolog zupełnie sobie nie radzi z ułamkami i ma dziwną tendencję do wydłużania listy zamiast sprawdzić najpierw wszystkie możliwości. Tym niemniej implementacje można łatwo poprawić, zaś dobry sposób na wyrażanie idei ma wielką wartość.
Może się zrobić jeszcze ciekawiej jeśli zauważymy, że taką wieloznaczną wartość można zwrócić w funkcji, przekazać jako parametr, a implementując w lepszy sposób (np. jako monadę), można wykonywać wielokrotne przekształcenia, w wielu różnych miejscach programu. Ile razy wykonujemy w pętli działania, które dla wszystkich iteracji pętli dają ten sam wynik? Często nawet nie zdajemy sobie sprawy, bo mamy piękną jednolinijkową pętlę z paroma wywołaniami funkcji i nie myślimy co w nich się dzieje. Użycie programowania przez dopasowanie może pozwolić zredukować ilość niepotrzebnych obliczeń.
Szczerze mówiąc, z trudem przychodzi mi przytaczanie praktycznych przykładów zastosowania. Ewidentnie wymaga to zupełnie innego sposobu myślenia, a to jeszcze kolejna wartość… Coś jest w myśli Alana Perilsa: „Język, który nie wpływa na to jak myślisz o programowaniu, nie jest warty, żeby go znać.”.
Najprostszym sposobem na zaimplementowanie takiego mechanizmu jest, podobnie jak w mojej szkicowej implementacji, są listy możliwości. Wówczas pozostaje sprawdzić wszystkie możliwe kombinacje. Dużym jednak problemem jest to, że takie listy szybko się rozrastają. Pierwsze co przychodzi na myśl to zastąpić listę szeregiem, innymi słowy generować kolejne elementy w momencie gdy zaistnieje potrzeba. Jeśli język nie wspiera, można to łatwo zrobić w praktycznie każdym porządnym języku, choćby (Python):
def fibonaci():
yield 0
yield 1
yield 1
a = 1
b = 1
while 1:
c = a + b
b = a
a = c
yield c
fib = fibonaci()
print(fib.next()) # 0
print(fib.next()) # 1
print(fib.next()) # 1
print(fib.next()) # 2
print(fib.next()) # 3
print(fib.next()) # 5Jednak taka prosta struktura ma tę słabość, że słabo się komponuje. Dobrze pójść o krok dalej i stworzyć monadę. Przykład takiej implementacji w Haskellu można obejrzeć tutaj.
Innym podejściem jest zastosowanie kontynuacji. Między innymi, tak implementuje się operator amb zaproponowany przez Johna McCarthy'ego, twórcę Lispu. Zamiast przekazywać na okrągło wszystkie wartości, stosuje kontynuacje, to znaczy, że za każdym razem gdy napotka na błąd, wróci z wykonywaniem programu w miejsce, gdzie zwracał wartość i tym razem zwróci inną. Nie będę przytaczał typowej implementacji w Scheme, przy użyciu call/cc, bo póki co nawet mnie to przerasta. Za to mogę zaproponować użycie funkcji z nagłówka setjmp.h, ze standardu POSIX:
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
void amb(int count, int *values, void (*action)(int, jmp_buf*)) {
jmp_buf x;
for (uint i = 0; i < count; i++) {
if(setjmp(x) == 0) {
action(values[i], &x);
return;
}
}
fprintf(stderr, "amb exhausted\n");
exit(1);
}
void isodd(int i, jmp_buf *cont) {
if((i % 2) == 0)
longjmp(*cont, 1);
printf("i = %d\n", i);
}
int main() {
amb(5, (int[]){4, 2, 12, 3, 7}, &isodd);
return 0;
}
// wynik:
// i = 3Trochę nieporęczna to implementacja, niestety standardowe rozwiązanie nie zapisuje całej zawartości stosu, więc nie możemy takiej wartości zwrócić( jednak to potrafi), więc musimy użyć funkcji w parametrze (funkcje anonimowe z C++11 mogłyby tę niedogodność załagodzić). Dla pokazania idei, myślę że działa całkiem dobrze, po prostu ilekroć nie pasuje nam jakaś wartość, przywracamy stan działania programu do momentu wyboru wartości i wybieramy kolejną.
Wreszcie, zdecydowanie najciekawsza opcja, dająca największe możliwości optymalizacji takiego rozwiązania są transformatory kodu (code walkers), czyli programy, które modyfikują kod innego programu. Wydaje się, że Lisp jest jedynym językiem wysokiego poziomu, w którym takie podejście ma sens (może jeszcze prolog, też jest homoikoniczny).
Oczywiście każdy szanujący się kompilator robi coś takiego w trakcie optymalizacji. Większość języków ma zbyt złożoną składnię żeby się w coś takiego bawić, już lepiej byłoby pracować na poziomie assemblera (czy to kodu maszynowego czy jeszcze lepiej, dla ułatwienia, kodu bajtowego).
Takie podejście mogłoby sprawić, że dopasowanie wartości zachodziłoby niezauważenie, a w przypadku mieszania zmiennych wieloznacznych z innymi, wynik automatycznie byłby konwertowany na wieloznaczny.
Nic mi nie wiadomo, żeby ktoś zaimplementował coś takiego, jednak jest to prawdopodobnie ciekawy trop dla kogoś, kto chciałby dogłębnie zająć się tematem.
Programowanie przez dopasowanie to wciąż świeża koncepcja, myślę, że jest tutaj wiele do zbadania. Najoczywistszym zastosowaniem wydaje się sztuczna inteligencja, bo jak zobaczyliśmy, takie podejście może znacząco wyabstrahować złożoność problemu. Nic dziwnego, że ta idea zasadniczo leży u podstaw języka Prolog, który znajduje zastosowanie właśnie w tej dziedzinie.
Z drugiej strony, jak zobaczyliśmy, nie tylko sztuczna inteligencja może tu skorzystać. Potencjalnie, zastosowanie niejednoznacznych zmiennych może przynieść przyspieszenie działania programu kosztem złożoności pamięciowej.
Poza tym, myślę, że koncepcja bardzo pobudza wyobraźnię, poszerza horyzonty. Również ciekawe, gdzie dalej może nas zawieść koncepcja wieloznaczności, wszak wspomniane już NDFA jest pojęciem znacznie bardziej pojemnym.