Jak wdrożyć leniwą ocenę if ()

10

Obecnie implementuję ewaluator wyrażeń (wyrażenia jednowierszowe, takie jak formuły) w oparciu o:

  • wprowadzone wyrażenie jest tokenizowane w celu oddzielenia literalnych boolanów, liczb całkowitych, dziesiętnych, ciągów, funkcji, identyfikatorów (zmiennych)
  • Zaimplementowałem algorytm Shunting-yard (lekko zmodyfikowany do obsługi funkcji o zmiennej liczbie argumentów), aby pozbyć się nawiasów i uporządkować operatorów z przyzwoitym pierwszeństwem w ustalonej kolejności
  • moje pole manewrowe po prostu tworzy (symulowaną) kolejkę tokenów (za pomocą tablicy mój język Powerbuilder Classic może definiować obiekty, ale tylko macierze dynamiczne jako pamięć natywną - nie jest to prawdziwa lista, brak słownika), które oceniam sekwencyjnie za pomocą prosta maszyna do układania w stosy

Mój ewaluator działa dobrze, ale wciąż mi brakuje if()i zastanawiam się, jak postępować.

Z moją postfuntowaną postfunkcją i oceną stosu, jeśli dodam if()jako inną funkcję z częściami prawdziwą i fałszywą, jeden if(true, msgbox("ok"), msgbox("not ok"))wyświetli obie wiadomości, podczas gdy chciałbym pokazać tylko jedną. Dzieje się tak, ponieważ gdy muszę ocenić funkcję, wszystkie jej argumenty zostały już ocenione i umieszczone na stosie.

Czy możesz dać mi sposób na wdrożenie if()w leniwy sposób?

Myślałem o przetwarzaniu ich jako rodzaju makra, ale na początku nie miałem jeszcze oceny stanu. Być może muszę użyć innej struktury niż kolejka, aby oddzielnie zachować warunek i wyrażenia prawda / fałsz? Na razie wyrażenie jest analizowane przed oceną, ale planuję również przechowywać reprezentację pośrednią jako rodzaj wstępnie skompilowanego wyrażenia do przyszłej oceny.

Edycja : po kilku rozważaniach na temat problemu, myślę, że mógłbym zbudować drzewną reprezentację mojego wyrażenia (AST zamiast liniowego strumienia tokena), z którego mógłbym łatwo zignorować jedną lub drugą gałąź mojego if().

Seki
źródło

Odpowiedzi:

9

Istnieją tutaj dwie opcje.

1) Nie implementuj ifjako funkcji. Zrób z tego funkcję języka ze specjalną semantyką. Łatwe do zrobienia, ale mniej „czyste”, jeśli chcesz, aby wszystko było funkcją.

2) Zaimplementuj semantykę „call by name”, co jest znacznie bardziej skomplikowane, ale pozwala magii kompilatora zająć się leniwym problemem oceny, zachowując ifjako funkcję zamiast elementu języka. Wygląda to tak:

ifjest funkcją, która przyjmuje dwa parametry, z których oba są zadeklarowane jako „z nazwy”. Gdy kompilator zobaczy, że przekazuje coś do parametru nazwy, zmienia kod, który ma zostać wygenerowany. Zamiast oceniać wyrażenie i przekazywać wartość, tworzy zamknięcie, które ocenia wyrażenie i przekazuje je zamiast tego. A podczas wywoływania parametru funkcji w nazwie, kompilator generuje kod do oceny zamknięcia.

Mason Wheeler
źródło
Nie jestem pewien, ale czy „zamknięcie” powinno być „grube”? Hmmm, może nie; właśnie spojrzałem na stronę wikipedii: „thunk to zamknięcie bez parametrów”.
Kiedy mówisz „zadzwoń po imieniu”, masz na myśli cały świat? Alternatywnie do globalnego wywołania według nazwy jest po prostu implementacja typu zamknięcia, a następnie funkcja if po prostu przyjmuje 3 zamknięcia i ocenia dwa (warunek, a potem lub jeszcze), ale nie wszystko musi zostać uznane za zamknięcie, takie jak pełne wywołanie według semantyka imienia
Jimmy Hoffa
@Matt: Termin „zgrzyt” może oznaczać kilka innych rzeczy w kontekście programowania, a „bezparametrowe zamknięcie” nie jest pierwszym, o którym myślę, kiedy go słyszę. „Zamknięcie” jest o wiele bardziej jednoznaczne.
Mason Wheeler
1
@JimmyHoffa: Kiedy mówię „call by name”, mam na myśli określony styl ustawiania argumentu funkcji, który powinien być opcjonalny. Podobnie jak wiele istniejących języków, możesz wybrać przekazanie parametru przez wartość lub odniesienie, w tym scenariuszu musisz wybrać przekazanie nazwy.
Mason Wheeler
Chociaż twoja sugestia dotycząca semantyki „wywołaj po nazwie” pokazała mi kilka interesujących punktów, dla mojego ewaluatora jest to trochę przesada, ponieważ nie jest to kompletny kompilator, ponieważ moje wywołania funkcji są jednowierszowe (pomyśl o formułach MS-excel). Myślę, że mógłbym dodać krok po ustawieniu w kolejce tokenów, wykonując pseudo-ocenę stosu, aby wydedukować drzewo wywołujące. Z drzewa powinno być łatwiej poznać gałęzie, które należy odrzucić.
Seki
3

Zamiast funkcji posiadającej podpis:

object if(bool, object, object)

Podaj podpis:

object if(bool, object function(), object function())

Wtedy twoja iffunkcja wywoła odpowiednią funkcję na podstawie warunku, oceniając tylko jedną z nich.

Hand-E-Food
źródło
1

Jest to dość łatwe, jeśli wszystko leniwie skompilujesz. Musisz mieć jakieś środki, aby sprawdzić, czy wartość jest już oszacowana, czy też wymaga więcej ewaluacji.

Następnie możesz wykonać następujące czynności: Jeśli jest to literał lub zmienna (czy masz je?, Tj. Nazwy funkcji?), Pchnij je na stos. Jeśli jest to zastosowanie funkcji, skompiluj ją osobno i wciśnij punkt wejścia na stosie.

Wykonywanie programu jest więc zapętleniem, dopóki szczyt stosu nie zostanie oceniony, a nie funkcja. Jeśli nie jest to wartościowane lub funkcja, wywołaj kod, na który wskazuje góra stosu.

Ingo
źródło