Jak języki programowania definiują funkcje?

28

Jak języki programowania definiują i zapisują funkcje / metody? Tworzę zinterpretowany język programowania w Ruby i próbuję wymyślić, jak zaimplementować deklarację funkcji.

Moim pierwszym pomysłem jest zapisanie treści deklaracji na mapie. Na przykład, gdybym zrobił coś takiego

def a() {
    callSomething();
    x += 5;
}

Następnie dodałbym wpis do mojej mapy:

{
    'a' => 'callSomething(); x += 5;'
}

Problem polega na tym, że stałoby się ono rekurencyjne, ponieważ musiałbym wywołać moją parsemetodę na łańcuchu, który następnie zadzwoniłby parseponownie, gdy się napotkał doSomething, a następnie w końcu zabrakłoby miejsca na stosie.

Jak zatem radzą sobie z tym języki interpretowane?

Klamka
źródło
Aha, i to jest mój pierwszy post na Programmers.SE, więc proszę o informację, jeśli robię coś źle lub jest to nie na temat. :)
Klamka
W przeszłości zapisywałem je wszystkie wewnątrz tokenów, a wywołania funkcji są po prostu skokami do określonego przesunięcia (podobnie jak etykiety w zestawie). Czy tokenizujesz skrypt? Lub parsowanie za każdym razem?
Simon Whitehead,
@ SimonWhitehead Podzielę ciąg na tokeny, a następnie przeanalizuję każdy token osobno.
Klamka
3
Jeśli dopiero zaczynasz projektować i wdrażać język programowania, warto zapoznać się z literaturą na ten temat. Najpopularniejszym jest „Dragon Book”: en.wikipedia.org/wiki/… , ale są też inne, bardziej zwięzłe teksty, które są również bardzo dobre. Na przykład: Wdrażanie języków programowania przez Aarne Ranta można uzyskać bezpłatnie tutaj: bit.ly/15CF6gC .
evilcandybag,
1
@ddyer Thanks! Poszukałem tłumacza lisp w różnych językach i to naprawdę pomogło. :)
Klamka

Odpowiedzi:

31

Czy miałbym rację zakładając, że twoja funkcja „parsuj” nie tylko analizuje kod, ale także wykonuje go w tym samym czasie? Jeśli chcesz to zrobić w ten sposób, zamiast zapisywać zawartość funkcji na mapie, zapisz jej położenie .

Ale jest lepszy sposób. To wymaga nieco więcej wysiłku z góry, ale daje znacznie lepsze wyniki wraz ze wzrostem złożoności: użyj abstrakcyjnego drzewa składni.

Podstawową ideą jest to, że parsujesz kod tylko raz, zawsze. Następnie masz zestaw typów danych reprezentujących operacje i wartości i tworzysz ich drzewo, tak jak to:

def a() {
    callSomething();
    x += 5;
}

staje się:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(Jest to tylko tekstowa reprezentacja struktury hipotetycznej AST. Rzeczywiste drzewo prawdopodobnie nie byłoby w formie tekstowej.) W każdym razie parsujesz swój kod na AST, a następnie albo uruchamiasz interpretera bezpośrednio nad AST, lub użyj drugiego przejścia („generowanie kodu”), aby zmienić AST w jakąś formę wyjściową.

W przypadku twojego języka prawdopodobnie zrobiłbyś mapę, która odwzorowuje nazwy funkcji na funkcje AST, zamiast nazw funkcji na ciągi funkcji.

Mason Wheeler
źródło
Okej, ale problem nadal występuje: używa rekurencji. W końcu zabraknie mi miejsca na stosie, jeśli to zrobię.
Klamka
3
@Doorknob: Co konkretnie wykorzystuje rekurencję? Każdy język programowania o strukturze blokowej (który jest każdym nowoczesnym językiem na wyższym poziomie niż ASM) jest z natury oparty na drzewach, a zatem ma charakter rekurencyjny. W jakim konkretnym aspekcie obawiasz się przepełnienia stosu?
Mason Wheeler,
1
@Doorknob: Tak, to nieodłączna właściwość każdego języka, nawet jeśli jest skompilowany do kodu maszynowego. (Stos wywołań jest przejawem tego zachowania.) Właściwie jestem współtwórcą systemu skryptów, który działa w sposób opisany przeze mnie. Dołącz do mnie na czacie na chat.stackexchange.com/rooms/10470/... a omówię z tobą niektóre techniki efektywnej interpretacji i minimalizacji wpływu na rozmiar stosu. :)
Mason Wheeler,
2
@ Dooobnob: Nie ma tu problemu z rekurencją, ponieważ wywołanie funkcji w AST odwołuje się do funkcji po nazwie , nie potrzebuje odniesienia do faktycznej funkcji . Jeśli kompilowałeś do kodu maszynowego, to w końcu potrzebujesz adresu funkcji, dlatego większość kompilatorów wykonuje wiele przejść. Jeśli chcesz mieć kompilator jednoprzebiegowy , potrzebujesz „do przodu deklaracji” wszystkich funkcji, aby kompilator mógł wcześniej przypisać adresy. Kompilatory bajtowe nawet się tym nie przejmują, jitter obsługuje wyszukiwanie nazw.
Aaronaught
5
@Doorknob: To rzeczywiście rekurencyjne. I tak, jeśli twój stos zawiera tylko 16 wpisów, nie uda ci się parsować (((((((((((((((( x ))))))))))))))))). W rzeczywistości stosy mogą być znacznie większe, a złożoność gramatyczna prawdziwego kodu jest dość ograniczona. Z pewnością jeśli ten kod musi być czytelny dla człowieka.
MSalters
4

Nie powinieneś nazywać parsowaniem po zobaczeniu callSomething()(zakładam, że miałeś na myśli callSomethingraczej niż doSomething). Różnica między ai callSomethingpolega na tym, że jedna jest definicją metody, a druga jest wywołaniem metody.

Gdy zobaczysz nową definicję, będziesz chciał sprawdzić, czy możesz dodać tę definicję, więc:

  • Sprawdź, czy funkcja nie istnieje jeszcze z tym samym podpisem
  • Upewnij się, że deklaracja metody jest wykonywana we właściwym zakresie (tzn. Czy metody mogą być deklarowane w innych deklaracjach metod?)

Zakładając, że testy zostaną zaliczone, możesz dodać je do mapy i rozpocząć sprawdzanie zawartości tej metody.

Po znalezieniu takiego wywołania metody callSomething()należy wykonać następujące kontrole:

  • Czy callSomethingistnieje na twojej mapie?
  • Czy jest poprawnie wywoływany (liczba argumentów pasuje do znalezionego podpisu)?
  • Czy argumenty są poprawne (jeśli używane są nazwy zmiennych, czy są zadeklarowane? Czy można uzyskać do nich dostęp w tym zakresie?)?
  • Czy callCoś można wywołać z miejsca, w którym się znajdujesz (czy to prywatne, publiczne, chronione?)?

Jeśli uznasz, że callSomething()jest to w porządku, to w tym momencie to, co chcesz zrobić, naprawdę zależy od tego, jak chcesz do tego podejść. Ściśle mówiąc, kiedy już wiesz, że takie wywołanie jest w tej chwili w porządku, możesz zapisać nazwę metody i argumenty bez wchodzenia w dalsze szczegóły. Po uruchomieniu programu wywołujesz metodę z argumentami, które powinieneś mieć w czasie wykonywania.

Jeśli chcesz pójść dalej, możesz zapisać nie tylko ciąg znaków, ale link do faktycznej metody. Byłoby to bardziej wydajne, ale jeśli musisz zarządzać pamięcią, może to być mylące. Radziłbym najpierw po prostu trzymać się sznurka. Później możesz spróbować zoptymalizować.

Zauważ, że wszystko to zakłada, że ​​leksykowałeś swój program, co oznacza, że ​​rozpoznałeś wszystkie tokeny w swoim programie i wiesz, czym one . Nie oznacza to, że wiesz, czy mają one jeszcze sens razem, co jest fazą analizy. Jeśli jeszcze nie wiesz, jakie są tokeny, sugeruję, abyś najpierw skupił się na uzyskaniu tych informacji.

Mam nadzieję że to pomogło! Witamy w Programmers SE!

Neil
źródło
2

Czytając twój post, zauważyłem dwa pytania w twoim pytaniu. Najważniejszy z nich to jak analizować. Istnieje wiele rodzajów analizatorów (np Recursive zejście parser , LR parser , packrat parserami ) i generatory parsera (np GNU bizon , ANTLR ) można użyć, aby przechodzić program tekstowy „rekurencyjnie” podane gramatyki (explicite lub implicite).

Drugie pytanie dotyczy formatu pamięci dla funkcji. Gdy nie wykonujesz tłumaczenia ukierunkowanego na składnię , tworzysz pośrednią reprezentację swojego programu, która może być abstrakcyjnym drzewem składni lub jakimś niestandardowym językiem pośrednim, w celu dalszego przetwarzania z nim (kompilacja, transformacja, wykonywanie, pisanie dalej plik itp.).

Thiago Silva
źródło
1

Z ogólnego punktu widzenia definicja funkcji jest niewiele więcej niż etykietą lub zakładką w kodzie. Większość innych operatorów pętli, zakresu i warunków jest podobnych; są one dostępne dla podstawowych poleceń „skok” lub „goto” na niższych poziomach abstrakcji. Wywołanie funkcji sprowadza się zasadniczo do następujących poleceń komputerowych niskiego poziomu:

  • Połącz dane wszystkich parametrów oraz wskaźnik do następnej instrukcji bieżącej funkcji w strukturę znaną jako „ramka stosu wywołań”.
  • Wciśnij tę ramkę na stos wywołań.
  • Przejdź do przesunięcia pamięci pierwszego wiersza kodu funkcji.

Instrukcja „return” lub podobna będzie wtedy wykonywać następujące czynności:

  • Załaduj wartość do zwrócenia do rejestru.
  • Załaduj wskaźnik do dzwoniącego do rejestru.
  • Pop bieżącą ramkę stosu.
  • Przejdź do wskaźnika dzwoniącego.

Dlatego funkcje są po prostu abstrakcjami w specyfikacji języka wyższego poziomu, które pozwalają ludziom organizować kod w bardziej konserwowalny i intuicyjny sposób. Po skompilowaniu w asemblerze lub w języku pośrednim (JIL, MSIL, ILX), a na pewno w renderowaniu jako kod maszynowy, prawie wszystkie takie abstrakcje znikają.

KeithS
źródło