Witam!

Piszę interpreter wyrażeń matematycznych. Będzie on jednak rozszerzony o
dodatkowe funkcjonalności, m.in rejestrowanie w locie makr:

f(x,y):=x+y

Poprzednia wersja była nieco ograniczona w tym zakresie, ponieważ parser
sprawdzał po prostu, czy w wyrażeniu nie występuje symbol ":=" i w
zależności od tego zachowywał się inaczej.

Chciałbym uogólnić działanie interpretera, traktując := jako operator,
który nie zwróci żadnej wartości (lub zwróci specjalny obiekt
reprezentujący wynik operacji kontrolnej). Problem polega jednak na tym,
że "f(x,y)" może być potraktowane zarówno jako left-hand-side, jak i
right-hand-side (wystarczy zdefiniować zmienne x i y, by f(x,y) stało się
poprawnym wywołaniem obliczeń). Prawą stronę również należy interpretować
inaczej, traktując x i y jako parametry funkcji, a nie - zmienne.

W jaki sposób - podczas przetwarzania wyrażenia - mógłbym ustalić, czy
wczytany fragment wyrażenia jest lhs, czy rhs?

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! \/) \ !

do góry

Wojciech "Spook" Sura wrote:
> Piszę interpreter wyrażeń matematycznych. Będzie on jednak rozszerzony o
> dodatkowe funkcjonalności, m.in rejestrowanie w locie makr:
>
> f(x,y):=x+y
>
> Poprzednia wersja była nieco ograniczona w tym zakresie, ponieważ parser
> sprawdzał po prostu, czy w wyrażeniu nie występuje symbol ":=" i w
> zależności od tego zachowywał się inaczej.
>
> Chciałbym uogólnić działanie interpretera, traktując := jako operator,
> który nie zwróci żadnej wartości (lub zwróci specjalny obiekt
> reprezentujący wynik operacji kontrolnej). Problem polega jednak na tym,
> że "f(x,y)" może być potraktowane zarówno jako left-hand-side, jak i
> right-hand-side (wystarczy zdefiniować zmienne x i y, by f(x,y) stało się
> poprawnym wywołaniem obliczeń). Prawą stronę również należy interpretować
> inaczej, traktując x i y jako parametry funkcji, a nie - zmienne.
>
> W jaki sposób - podczas przetwarzania wyrażenia - mógłbym ustalić, czy
> wczytany fragment wyrażenia jest lhs, czy rhs?

Chyba czegoś nie rozumiem.
Skoro symbol ":=" określa miejsce podziału na część lewo i prawostronną, to
w czym problem?

Pozdrawiam,
- Bastek -

do góry

> Chyba czegoś nie rozumiem.
> Skoro symbol ":=" określa miejsce podziału na część lewo i prawostronną,
> to w czym problem?

Chciałbym potraktować := jako operator. Do tej pory interpretowałem
wyrażenie warunkowo - jeśli występował w nim ":=", interpreter działał w
innym trybie. Teraz chciałbym to uogólnić (być może wprowadzając więcej
operatorów wyższego poziomu), więc podczas przetwarzania od lewej do
prawej nie jestem w stanie stwierdzić, co jest lewo-, a co - prawostronne.

Wstępny pomysł jest taki, by wprowadzić dodatkowy poziom abstrakcji -
skoro := jest operatorem działającym na wyrażeniach, myślę o
zaprojektowaniu obliczeń na całych wyrażeniach. Wówczas wejściowe
wyrażenie kompilowane byłoby do meta-ONP, zbudowanej z wyrażeń i
operatorów wyrażeniowych. Po przetworzeniu meta-ONP interpreter
oczekiwałby na stosie wyrażeń pojedynczego wyrażenia będącego wynikiem
meta-obliczeń, które z kolei zostałoby obliczone już normalnie.

Coś pokroju:

f(x,y):=x+y przetworzone byłoby na:

wyrażenie(f(x,y)) wyrażenie(x+y) operator-wyrażeniowy(:=)

To obliczone zostałoby do

wyrażenie(<Informacja o efekcie działania operatora :=>)

Z kolei

2+2*2 przetworzone byłoby na:

wyrażenie(2+2*2)

Jest to stała z punktu widzenia obliczeń na wyrażeniach, więc nie trzeba
już nic robić, następnie obliczone byłoby samo wyrażenie do:

wyrażenie(6)

Trochę głośno myślę, ale być może jest to sensowne rozwiązanie?
Wielokrotne obliczanie wyrażeń straciłoby trochę na wydajności (najpierw
musiałoby zostać obliczone meta-wyrażenie), ale byłby to czynnik liniowy -
jeśli nie stały, więc nie jest też aż tak źle.

Jest w miarę jasne to, co napisałem?

> Pozdrawiam,
> - Bastek -

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

On Aug 24, 8:56 am, "Wojciech \"Spook\" Sura"
<s...@s...please.op.pl> wrote:

> Wstępny pomysł jest taki, by wprowadzić dodatkowy poziom abstrakcji -  
> skoro := jest operatorem działającym na wyrażeniach, myślę o  
> zaprojektowaniu obliczeń na całych wyrażeniach. Wówczas wejściowe  
> wyrażenie kompilowane byłoby do meta-ONP, zbudowanej z wyrażeń i  
> operatorów wyrażeniowych. Po przetworzeniu meta-ONP interpreter  
> oczekiwałby na stosie wyrażeń pojedynczego wyrażenia będącego wynikiem  
> meta-obliczeń, które z kolei zostałoby obliczone już normalnie.

Zapomnij o ONP. Niech parser wyprodukuje drzewko wyrażenia. To pozwala
je potem interpretować bez ograniczeń.

do góry

Dnia 24-08-2010 o 10:29:27 Marcin 'Qrczak' Kowalczyk <q...@k...org.pl>
napisał(a):
> Zapomnij o ONP. Niech parser wyprodukuje drzewko wyrażenia. To pozwala
> je potem interpretować bez ograniczeń.

To akurat nie jest większym problemem - szczególnie, że ONP jest w sumie
drzewem - tyle że zapisanym w pewien szczególny sposób. Faktycznie -
drzewo pozwala na dowolne przetwarzanie wczytanego wyrażenia, bo operator
może zdecydować, czy jako dane wejściowe przyjmie wartość obliczoną z
poddrzew, czy całe poddrzewa - jak byłoby w przypadku operatora
przypisania.

Zastanawiam się tylko nad wydajnością takiego rozwiązania. Poprzedni
interpreter rozwiązałem w ten sposób, że wyrażenie jest najpierw
kompilowane do ONP, zaś później postać skompilowana jest interpretowana. W
ten sposób można przygotować skompilowany wzór jakiejś funkcji, a potem
szybko wielokrotnie go interpretować, co jest przydatne - przykładowo -
podczas rysowania wykresu.

Przetwarzanie przygotowanego drzewa musiałoby odbywać się rekurencyjnie. Z
drugiej strony ONP też jest obliczane rekurencyjnie, tyle że rekurencja
jest niejawna, korzysta się tylko z pomocniczego stosu obliczonych
(pod)wyrażeń. Być może można byłoby przetworzyć je do jakiejś
wydajniejszej struktury, ale nie przychodzi mi obecnie żadna na myśl. Być
może jednak wersja rekurencyjna będzie dostatecznie szybka?

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! \/) \ !

do góry

"Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl> wrote:

> Przetwarzanie przygotowanego drzewa musiałoby odbywać się rekurencyjnie. Z
> drugiej strony ONP też jest obliczane rekurencyjnie, tyle że rekurencja
> jest niejawna, korzysta się tylko z pomocniczego stosu obliczonych
> (pod)wyrażeń. Być może można byłoby przetworzyć je do jakiejś
> wydajniejszej struktury, ale nie przychodzi mi obecnie żadna na myśl. Być
> może jednak wersja rekurencyjna będzie dostatecznie szybka?

Prosta wirtualna maszyna, która ma push, pop, add, sub itp.

w.

do góry

Dnia 24-08-2010 o 22:07:28 Wojciech Muła
<w...@p...null.onet.pl.invalid> napisał(a):
> Prosta wirtualna maszyna, która ma push, pop, add, sub itp.

Bardzo mi się podoba ten pomysł! Konstruowanie "programów" dla takiej
maszyny będzie stosunkowo łatwe, a działanie będzie chyba nawet szybsze od
ONP, bo zniknie sporo instrukcji warunkowych.

Sądzę, że instrukcje kontrolne również mogłyby być realizowane
odpowiednimi komendami takiej maszyny wirtualnej. W końcu każda instrukcja
może być klasą przechowującą dowolne dane - nic nie stoi na przeszkodzie,
by przechowywała kod dodawanej funkcji, coś pokroju:

ADDFN "F", 2, {PUSH PAR 1; PUSH PAR 2; ADD;};

Kroi się ciekawy projekt :)

> w.

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

On Aug 25, 7:19 am, "Wojciech \"Spook\" Sura"
<s...@s...please.op.pl> wrote:
> Dnia 24-08-2010 o 22:07:28 Wojciech Muła  
> <w...@p...null.onet.pl.invalid> napisał(a):
>
> > Prosta wirtualna maszyna, która ma push, pop, add, sub itp.
>
> Bardzo mi się podoba ten pomysł! Konstruowanie "programów" dla takiej  
> maszyny będzie stosunkowo łatwe, a działanie będzie chyba nawet szybsze od  
> ONP, bo zniknie sporo instrukcji warunkowych.

Mimo wszystko porównałbym to z interpretacją drzewka. Może się okazać,
że gra jest niewarta świeczki.

do góry

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! \/) \ !

do góry

W dniu 2010-08-25 19:38, Wojciech "Spook" Sura pisze:
> 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,
Pobieznie sadzac, przecinkow, nawiasow juz ma nie byc w AST. To zadanie
parsera. Jesli zrozumialem. Sprawdzenie syntaxu masz zagwarantowane,
semantyke oczywiscie sprawdzasz.

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

Zrobilem jezyk na Antlr, interpreter to zadna tam VM, tylko wprost
dziedziczy z ich 'tree walker'. W realnych warunkach, jak raz
zapomnialem o optymalizacji, nigdy sobie nie przypomnialem ;)

Te wyrazenie ile razy bedziesz wartosciowal? W wewnętrznej petli CAD-a
lub gry fesnascie tysiecy / sek, czy kilka-naście razy w ogole?

Aha. W filozofii Antlr mozna element drzewa sobie poszerzyc,
odziedziczyc, wiec markery wg twojego pomyslu są do dodania. Co nie
znaczy ze wciskam narzedzie. Interpretacja wprost z drzewa jest naprawde
do rozwazenia. Tyle refleksji na marginesie.

do góry