Jakie są funkcje etapowe (koncepcyjnie)?

W niedawnym artykule CACM [1] autorzy przedstawiają implementację funkcji etapowych . Używają tego terminu, jakby był dobrze znany, i żadne z odniesień nie wygląda jak oczywiste wprowadzenie.

Podają krótkie wyjaśnienie (zmieniono moje wyróżnienie i numer referencyjny; w oryginale jest 22)

W kontekście generowania programu, programowanie wieloetapowe (MSP, w skrócie inscenizacja), jak ustalili Taha i Sheard [2], pozwala programistom na wyraźne opóźnienie oceny wyrażenia programu na późniejszy etap (tym samym inscenizację wyrażenia). Obecny etap skutecznie działa jako generator kodu, który tworzy (i ewentualnie wykonuje) program następnego etapu.

Jednak Taha i Sheard piszą (moje podkreślenie):

Program wieloetapowy to taki, który obejmuje generowanie, kompilację i wykonywanie kodu, wszystko w tym samym procesie. Języki wieloetapowe wyrażają programy wieloetapowe. Programowanie etapowe, a co za tym idzie programowanie wieloetapowe, zaspokaja potrzebę rozwiązań ogólnego zastosowania, które nie przynoszą kosztów interpretacyjnych w czasie wykonywania.

Następnie przechodzą do kilku odniesień do starszych prac, które rzekomo pokazują, że inscenizacja jest skuteczna, co sugeruje, że koncepcja jest jeszcze starsza. Nie podają odniesienia do samego terminu.

Te stwierdzenia wydają się ortogonalne, jeśli nie sprzeczne; może to, co piszą Rompf i Odersky, to zastosowanie tego, co proponują Taha i Sheard, ale może to inna perspektywa na to samo. Wydaje się, że zgadzają się, że ważną kwestią jest to, że programy (re) zapisują części siebie w czasie wykonywania, ale nie wiem, czy jest to niezbędna i / lub wystarczająca zdolność.

Więc, co jest inscenizacja odpowiednio są interpretacje inscenizacja w tym kontekście? Skąd pochodzi ten termin?

1. Lightweight Modular Staging: Pragmatyczne podejście do generowania kodu wykonawczego i skompilowanych DSL przez T. Rompfa i M. Odersky'ego (2012)
2. MetaML i programowanie wieloetapowe z wyraźnymi adnotacjami W. Taha i T. Sheard (2000)

O ile mi wiadomo, w tym artykule Bill Scherlis po raz pierwszy użył terminu obliczenia etapowe . Wcześniej termin „ częściowa ocena ” był używany w odniesieniu do tej samej koncepcji, ale idea obliczeń etapowych jest nieco inna. Oba pomysły są związane z twierdzeniem Smene'a Kleene'a .

Jeśli masz funkcję dwóch argumentów, ale znasz jeden argument, powiedzmy , możesz od razu wykonać część obliczeń funkcji, korzystając z wiedzy pierwszego argumentu. funkcja której obliczenia zależą tylko od drugiego, nieznanego argumentu.m ϕ m ( n $\phi(m,n)$$m$$\phi_m(n)$

Pomysł częściowego oceny jest obliczenie wyspecjalizowanych funkcji automatycznie . Biorąc pod uwagę kod oryginalnej funkcji , częściowa analiza dokonuje analizy statycznej w celu ustalenia, które bity kodu zależą od a które bity zależą od , i przekształca go w funkcję która przy danym konstruuje . Drugi argument można następnie podać tej specjalizowanej funkcji.ϕ m n ϕ ′ m ϕ m$\phi_m(n)$ $\phi$$m$$n$$\phi'$$m$$\phi_m$$n$

Ideą obliczeń etapowych jest najpierw zastanowienie się nad funkcją . Nazywa się to funkcją „etapową”, ponieważ działa w wielu etapach. Gdy podamy mu pierwszy argument , konstruuje kod dla funkcji specjalistycznej . To jest „pierwszy etap”. W drugim etapie drugi argument jest przekazywany do który wykonuje resztę zadania. m ϕ m ϕ $\phi'$$m$$\phi_m$$\phi_m$

Tak więc zadaniem częściowej oceny jest przekształcenie kodu funkcji zwykłej w funkcję etapową . Scherlis przewidział, że transformacji tej można dokonać za pomocą bardziej ogólnych mechanizmów niż wcześniejsze metody częściowej oceny. Temat „obliczeń etapowych” dotyczy teraz takich zagadnień, jak:ϕ $\phi$$\phi'$

• Jak zdefiniować funkcje etapowe?
• Jakie języki programowania i systemy typów należy stosować do definiowania funkcji etapowych?
• Jaka jest semantyka takich języków?
• Jak zapewniamy spójność i poprawność funkcji etapowych?
• Jakie techniki są przydatne do automatycznego lub półautomatycznego konstruowania funkcji etapowych?
• Jak udowodnić poprawność takich technik?

Obliczenia etapowe mogą być bardzo ważne w praktyce. W rzeczywistości każdy kompilator jest obliczeniem etapowym. Biorąc pod uwagę program źródłowy, konstruuje on przetłumaczony i zoptymalizowany program docelowy, który może następnie pobrać dane wejściowe i obliczyć wynik. W praktyce ciężko jest pisać etapowe programy obliczeniowe, ponieważ musimy żonglować wieloma etapami i upewnić się, że właściwe rzeczy zostały wykonane we właściwym czasie. Każdy, kto napisał kompilator, borykał się z takimi problemami. Trudno jest także pisać programy, które piszą inne programy, mogą to być programy w języku maszynowym (kompilatory), zapytania SQL (manipulowanie bazami danych) lub kod HTML / Server Pages / JavaScript (aplikacje internetowe) i mnóstwo innych aplikacji.

Chociaż pozostałe odpowiedzi są technicznie poprawne, nie sądzę, aby dobrze rozumiały, dlaczego informatycy są zainteresowani funkcjami etapowymi.

Tworząc funkcje etapowe, definiujesz programy generujące programy. Jednym z głównych celów współczesnej praktycznej teorii języka jest maksymalizacja potencjalnego ponownego wykorzystania. Chcemy umożliwić pisanie bibliotek, które są nie tylko przydatnymi funkcjami i obiektami, ale które pomagają programistom, zapewniając konstrukcje architektoniczne wyższego rzędu.

Byłoby wspaniale, gdybyśmy mogli pozbyć się całego kodu na płycie głównej. Powinniśmy być w stanie zminimalizować język specyfikacji. Jeśli chcemy, na przykład, programu sterującego opartego na zdarzeniach, komunikującego się z innymi programami dyspozytorskimi o danym projekcie wątku, powinniśmy być w stanie to określić w sposób zwięzły, a wszystkie nasłuchiwania we / wy oraz obiekty kolejki i połączenia wątków powinny być możliwe do zbudowania na podstawie tej specyfikacji.

Języki domen to zwykle te zwięzłe reprezentacje, których szukamy. Kiedy ludzie pracują w domenie przez jakiś czas, język, którego używają, powoduje, że większość duplikatów informacji staje się szczupłą specyfikacją. Tak więc teoria inscenizacji ma tendencję do przekształcania się w system tłumaczenia z języków domenowych na język wykonawczy.

Kompilatory są technicznie zaawansowane, ale nie trafiają w cel. Celem współczesnej inscenizacji jest umożliwienie budowania programów, które budują programy, aby zmaksymalizować ponowne użycie i zautomatyzować konstrukcję programów tam, gdzie to możliwe. Byłoby wspaniale, gdyby pewnego dnia wymagania funkcjonalne programu były programem.

Patrz „Programowanie generatywne” Czarneckiego i Eiseneckera (ISBN-13: 978-0201309775).

Odpowiedź znajduje się w części z perspektywy technicznej dla danego artykułu [1]. Rozważany problem dotyczy obszaru napięć między kodem ogólnym a szczegółowym:

Programy mogą być napisane jako programy ogólnego lub specjalnego przeznaczenia. Zaletą kodu ogólnego jest to, że można go używać w różnych sytuacjach, podczas gdy kod specjalnego przeznaczenia może być napisany w sposób, który wykorzystuje unikalne cechy środowiska wykonawczego, a tym samym zwiększa wydajność kosztem ponownego użycia.

Oczywiście chcemy rozwiązać to napięcie, czyli osiągnąć ogólny kod i konkretne wdrożenie:

Możemy zadać pytanie: czy można napisać kod, aby był on przeznaczony do ogólnego użytku, ale czy następnie automatycznie specjalizuje się w sytuacji podczas wykonywania?

Doprowadziło to do tego, że (ogólne) programy (re) piszą się w czasie wykonywania, aby dostosować się do konkretnej sytuacji:

W rezultacie ważny kierunek badań obejmował poszukiwanie technologii języka i kompilatora, które mogą pozwolić programistom na pisanie kodu ogólnego przeznaczenia, który jest następnie poprawnie i wydajnie przekształcany w wysokowydajny specjalistyczny kod w czasie wykonywania.

Myślę, że JIT Javy jest dobrym przykładem. Jednym ze szczególnych pomysłów jest programowanie wieloetapowe, które Lee wyjaśnia w ten sposób:

W tej linii badań jedną z podstawowych idei jest koncepcja inscenizacji. Wyobrażamy sobie wykonanie programu przebiegającego w szeregu etapów, z których każdy oblicza wartości, które są wykorzystywane w późniejszych etapach. Chcemy zatem napisać kod programu, aby w jakiś sposób te etapy stały się widoczne. Jeśli zostanie to osiągnięte, możemy zorganizować kompilację kodu późniejszego etapu w generatory kodu optymalizujące wyniki wyników obliczeń wcześniejszego etapu.

Oznacza to, że „przemieszczanie” to sposób patrzenia na odpowiednie funkcje / kod identyfikujący fazy obliczeń / wykonywania, które można uprościć, znając wyniki poprzednich faz. Obliczenia „opóźniające”, jak w pierwszym cytacie w pytaniu, mogą być niezbędnym efektem ubocznym w celu prawidłowego rozdzielenia etapów, ale nie o to chodzi.

Rompf i Odersky wymieniają szybką transformację Fouriera jako przykład, który może być pouczający.

1. Lis i jeż: perspektywa techniczna Peter Lee (2012)