Chodzi o to, że naprawdę nie ma wiele swobody w zakresie kodowania funkcji. Oto główne opcje:
Przepisywanie terminów: przechowujesz funkcje jako ich abstrakcyjne drzewa składniowe (lub ich pewne kodowanie. Kiedy wywołujesz funkcję, ręcznie przechodzisz przez drzewo składniowe, aby zastąpić jego parametry argumentem. Jest to łatwe, ale strasznie nieefektywne pod względem czasu i miejsca .
Zamknięcia: masz jakiś sposób reprezentowania funkcji, może drzewo składniowe, bardziej prawdopodobny kod maszynowy. W tych funkcjach odwołujesz się do argumentów przez odniesienie w jakiś sposób. Może być przesunięciem wskaźnika, może być liczbą całkowitą lub indeksem De Bruijn, może być nazwą. Następnie reprezentujesz funkcję jako zamknięcie : funkcja „instrukcje” (drzewo, kod itp.) W połączeniu ze strukturą danych zawierającą wszystkie wolne zmienne funkcji. Kiedy funkcja jest rzeczywiście zastosowana, w jakiś sposób wie, jak wyszukać wolne zmienne w swojej strukturze danych, używając środowisk, arytmetyki wskaźnika itp.
Jestem pewien, że istnieją inne opcje, ale są to podstawowe i podejrzewam, że prawie każda inna opcja będzie wariantem lub optymalizacją podstawowej struktury zamknięcia.
Pod względem wydajności zamknięcia prawie ogólnie działają lepiej niż przepisywanie terminów. Która z odmian jest lepsza? Zależy to w dużej mierze od twojego języka i architektury, ale podejrzewam, że „kod maszynowy ze strukturą zawierającą wolne zmienne” jest najbardziej wydajny. Ma wszystko, czego potrzebuje funkcja (instrukcje i wartości) i nic więcej, a wywoływanie nie kończy się przechodzeniem przez dłuższy czas.
Interesuje mnie zarówno bieżący algorytm kodowania, jak popularne języki funkcjonalne (Haskell, ML)
Nie jestem ekspertem, ale jestem 99%, że większość smaków ML używa pewnych odmian zamknięć, które opisuję, aczkolwiek z pewnymi optymalizacjami. Zobacz to z perspektywy (prawdopodobnie nieaktualnej).
Haskell robi coś nieco bardziej skomplikowanego ze względu na leniwą ocenę: wykorzystuje Ponowne Pisanie Grafów Bez Tagu .
a także w najbardziej wydajnym, jaki można osiągnąć.
Co jest najbardziej wydajne? Nie ma implementacji, która byłaby najbardziej wydajna dla wszystkich danych wejściowych, więc otrzymujesz implementacje, które są średnio wydajne, ale każda z nich będzie wyróżniać się w różnych scenariuszach. Dlatego nie ma określonego rankingu najbardziej lub najmniej wydajnych.
Tu nie ma magii. Aby zapisać funkcję, musisz w jakiś sposób zapisać jej wolne wartości, w przeciwnym razie kodujesz mniej informacji niż sama funkcja. Być może możesz zoptymalizować niektóre z darmowych wartości za pomocą częściowej oceny, ale jest to ryzykowne z punktu widzenia wydajności i musisz być ostrożny, aby upewnić się, że zawsze się zatrzymuje.
A może możesz użyć jakiegoś rodzaju kompresji lub sprytnego algorytmu, aby uzyskać oszczędność miejsca. Ale wtedy albo zamieniasz czas na przestrzeń, albo jesteś w sytuacji, w której zoptymalizowałeś się w niektórych przypadkach, a spowolniłeś w przypadku innych.
Można zoptymalizować dla wspólnej sprawy, ale co wspólna sprawa to może zmienić się na języku, obszar zastosowania, itp rodzaj kodu, który jest szybki do gier wideo (liczba skrzypienie, ciasne pętle z dużym wejściem) jest prawdopodobnie inny niż co jest szybkie dla kompilatora (przechodzenie przez drzewa, listy robocze itp.).
Punkt bonusowy: Czy istnieje takie kodowanie, które odwzorowuje liczby całkowite zakodowane w funkcji na liczby całkowite natywne (krótkie, całkowite itp. W C). Czy to w ogóle możliwe?
Nie, to nie jest możliwe. Problem polega na tym, że rachunek lambda nie pozwala introspekcji terminów. Gdy funkcja pobiera argument tego samego typu co liczba kościelna, musi być w stanie ją wywołać, bez sprawdzania dokładnej definicji tej liczby. Tak właśnie jest z kodowaniem Kościoła: jedyne, co możesz z nimi zrobić, to zadzwonić do nich i możesz symulować wszystko, co jest przydatne, ale nie bez kosztów.
Co ważniejsze, liczby całkowite zajmują każde możliwe kodowanie binarne. Więc jeśli lambdy byłyby reprezentowane jako ich liczby całkowite, nie byłoby sposobu reprezentowania lambd nie liczących kościoła! Lub wprowadziłbyś flagę wskazującą, czy lambda jest liczbą, czy nie, ale wtedy wszelka pożądana wydajność prawdopodobnie zniknie z okna.
EDYCJA: Od momentu napisania tego, uświadomiłem sobie trzecią opcję implementacji funkcji wyższego rzędu: defunkcjonalizację . Tutaj każde wywołanie funkcji zmienia się w dużą switchinstrukcję, w zależności od tego, która abstrakcja lambda została podana jako funkcja. Kompromis polega na tym, że jest to transformacja całego programu: nie można osobno skompilować części, a następnie połączyć w ten sposób, ponieważ trzeba wcześniej przygotować komplet abstrakcji lambda.