Dnia 25-08-2010 o 18:05:15 Marcin 'Qrczak' Kowalczyk <q...@k...org.pl>
napisał(a):
> Mimo wszystko porównałbym to z interpretacją drzewka. Może się okazać,
> że gra jest niewarta świeczki.

Zastanawiałem się nad tym - złożoność obu algorytmów jest praktycznie taka
sama, więc w grę wchodzą głównie szczegóły implementacyjne.

Po pierwsze, nie wystarczy samo drzewo wyrażenia. Wyrażenie f(x,y):=x+y
zostanie rozbite na drzewo, po lewej stronie którego będzie podwieszona
funkcja f(, jej parametry, przecinek składający je w listę i nawias
domykający. Jeśli zdecyduję się na interpretowanie tak skonstruowanego
drzewa, będzie mnie czekać dużo pracy - stwierdzenie, czy lewa gałąź jest
poprawna, zdecydowanie o tym, czy dodawana jest funkcja czy zmienna,
odnalezienie parametrów i wyszukanie ich w prawym poddrzewie i tak dalej.
To będzie na pewno wolne.

Oczywiście mogę wykonać te operacje przed procesem interpretacji, ale
wówczas musiałbym zastanowić się nad specjalnym węzłem drzewa
przechowującym prekompilowane informacje o prototypie funkcji: jej nazwie
oraz liczbie i nazwach jej parametrów. W konsekwencji pojawiłby się
kolejny byt - nie będący ani operatorem ani funkcją ani - w zasadzie -
obiektem liczbowym, dla którego musiałbym przygotować odrębny algorytm
przetwarzania. Zupełnie subiektywnie takie rozwiązanie nie podoba mi się o
tyle, że do drzewa, które służy do zapisu pewnego zestawu operacji niejako
na siłę wstrzyknięty zostanie byt, który znajdzie się tam tylko po to, by
zachować drzewiastą strukturę podczas przetwarzania.

Zaistnienie maszyny wirtualnej wraz z odpowiednim językiem nie budzi już
we mnie sprzeciwów - maszyna jest z założenia wysokopoziomowa, więc
swobodnie mogę dodać jej rozkaz dodający funkcję, zawierający szczegółowe
informacje na jej temat - łącznie ze skompilowanym do zestawu rozkazów
wyrażeniem. Polecenie:

f(x,y):=x+y

Skompilowane zostałoby do następującego pseudo-rozkazu:

ADDFN(
f,
2,
(PUSH PAR1,
PUSH PAR2,
ADD)
);

Kolejnym argumentem przemawiającym za maszyną wirtualną jest prostota jej
implementacji - wykonywanie rozkazu sprowadziłoby się do iteracyjnego
przetworzenia dużej instrukcji switch(), implementowanej wewnętrznie
zazwyczaj jako seria instrukcji goto, które są stosunkowo szybkie. Mniej
danych przechowywanych byłoby również na stosie. Podczas przetwarzania
operacji 2+2*2 na stosie znalazłaby się pojedyncza ramka z informacjami o
pojedynczym wywołaniu operacji przetwarzającej węzeł, zaś w przypadku
maszyny wirtualnej stos (nota bene siedzący w stercie) przechowywałby na
raz tylko dwie liczby - argumenty i pośrednie wyniki obliczeń. Oczywiście
można zaimplementować wersję algorytmu przetwarzającego drzewo bez użycia
rekurencji, ale wówczas trzeba byłoby ją jakoś zasymulować, co
pociągnęłoby za sobą implementację kolejnego stosu.

Nie ukrywam, że nie robiłem żadnych zaawansowanych analiz, powyższe
argumenty stanowią tylko moje przemyślenia i refleksje na temat obu
algorytmów. Bardziej podoba mi się ten z maszyną wirtualną, niemniej nie
upieram się przy nim, ale z drugiej strony chciałbym usłyszeć jakąkolwiek
argumentację przemawiającą za algorytmem przetwarzającym drzewo.

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !