Czym różnią się języki rozkazujące od języków funkcjonalnych?

Czytam Simona Peytona Jonesa Implementation of Functional Programming Languages i jest jedno zdanie, które mnie trochę zaskoczyło (na stronie 39):

W znacznie większym stopniu niż w przypadku języków imperatywnych języki funkcjonalne są w dużej mierze odmianami składniowymi, przy stosunkowo niewielkich różnicach semantycznych.

Teraz zostało to napisane w 1987 roku i na moje przemyślenia na ten temat mogą mieć wpływ nowocześniejsze języki programowania, których wówczas nie było ani nie były popularne. Jednak trudno mi w to uwierzyć. Na przykład, myślę, że opisany język programowania Miranda (wczesny poprzednik Haskella) ma znacznie więcej różną semantykę w porównaniu do ścisłego języka, takiego jak ML, niż powiedzmy, że C ma Pascala, a może nawet C musi mówić po cichu (chociaż zrezygnuję z tego C ++ zapewnia pewną weryfikację swojego punktu :-).

Ale znowu opieram to na moim intuicyjnym zrozumieniu. Czy Simon Peyton Jones w dużej mierze ma rację, czy to kontrowersyjny punkt?

Simon ma zasadniczo rację z ekstensywnego punktu widzenia. Doskonale wiemy, czym jest semantyka współczesnych języków funkcjonalnych i są to tak naprawdę stosunkowo niewielkie odmiany - każdy z nich reprezentuje nieco inne tłumaczenia na monadyczny metaljęzyk. Nawet język taki jak Scheme (dynamicznie wpisany język imperatywny wyższego rzędu z pierwszorzędną kontrolą) ma semantykę zbliżoną do ML i Haskella.

$V$

Ale aby dostać się do kategorii odpowiedniej do interpretacji współczesnych języków funkcjonalnych, wszystko staje się dość przerażające. Zasadniczo kończy się konstruowanie wzbogaconej ultrametrycznie kategorii relacji częściowej równoważności w tej dziedzinie. (Jako przykład zob. Birkedal, Stovring i Thamsborg w „Realizowalności semantyki polimorfizmu parametrycznego, referencje ogólne i typy rekurencyjne”). Ludzie, którzy preferują semantykę operacyjną, znają to jako relacje logiczne indeksowane krokowo. (Na przykład zobacz Ahmed, Dreyer i Rossberg „Niezależność reprezentacji państwowej”.) Niezależnie od tego, zastosowane techniki są stosunkowo nowe.

Powodem tej matematycznej złożoności jest to, że musimy być w stanie jednocześnie interpretować parametryczny polimorfizm i stan wyższego rzędu. Ale kiedy już to zrobisz, jesteś w zasadzie wolny od domu, ponieważ ta konstrukcja zawiera wszystkie trudne elementy. Teraz możesz interpretować typy ML i Haskell za pomocą zwykłych tłumaczeń monadycznych. Rygorystyczne effectful funkcji miejsca ML a -> bprzekłada się i leniwa funkcji miejsca Haskell'a przekłada się ⟨ ⟩ → ⟨ b ⟩ z T ( A ) w monadycznej rodzaju skutków ubocznych interpretacji IO monadę z Haskell i$\left<a\right> \to T\left<b\right>$$\left<a\right> \to \left<b\right>$$T(A)$ Jest interpretacja typu ML lub Haskell typui → jest wykładniczy w tej kategorii os.$\left<a\right>$a$\to$

Jeśli chodzi o teorię równań, ponieważ oba te języki można opisać tłumaczeniem na nieco odmienne podzbiory tego samego języka, całkiem słusznie jest nazywać je odmianami składniowymi.

Różnica w odczuciu między ML i Haskell faktycznie wynika z intensywnych właściwości dwóch języków - to znaczy czasu wykonania i zużycia pamięci. ML ma model wydajności kompozycji (tj. Koszt czasu / przestrzeni programu można obliczyć na podstawie kosztów czasu / przestrzeni jego podtermów), podobnie jak prawdziwy język nazw według nazw. Rzeczywisty Haskell jest implementowany z wezwaniem na żądanie, rodzajem zapamiętywania, w wyniku czego jego działanie nie jest kompozycyjne - czas potrzebny na ocenę wyrażenia związanego ze zmienną zależy od tego, czy użyto go wcześniej, czy nie. Nie jest to modelowane w semantyce, o której wspomniałem powyżej.

Jeśli chcesz poważniej potraktować właściwości intensywne, ML i Haskell zaczynają wykazywać poważniejsze różnice. Prawdopodobnie nadal można opracować dla nich wspólny język języka, ale interpretacja typów będzie się różniła w znacznie bardziej systematyczny sposób, związany z teoretyczną ideą skupienia . Dobrym miejscem do nauczenia się o tym jest praca doktorska Noama Zeilbergera.

Mam wrażenie, że SPJ odnosiło się do języków czysto funkcjonalnych - tj. Języków, które są referencyjnie przejrzyste. Obejmuje to np. Haskell, Miranda, Clean, ale nie ML. Kiedy masz już język czysto funkcjonalny, możesz nadać mu dość czystą i dobrze zdefiniowaną semantykę denotacyjną. Ta semantyka będzie ogólnie wyglądać podobnie do rachunku lambda, z pewnymi poprawkami tu i tam. Ogólnie rzecz biorąc, będziesz miał system typów, który zaprowadzi do czegoś przypominającego wariant Systemu F - być może pod pewnymi względami bardziej wydajny, w innych bardziej ograniczony. To dlatego ekstrakcja kodu do / kompilacja do Haskell, O'Caml itp. Jest stosunkowo prosta od wyrafinowanych asystentów sprawdzających typu zależnego, takich jak Agda.

W tych ramach jest dużo miejsca do zabawy. Z pewnością nadal istnieje różnica między językiem surowym a surowym. Jednak ze względu na brak skutków ubocznych jedyną różnicą jest to, że język nieokreślony zawiera więcej wyrażeń, które nie oznaczają dna - o ile obie strategie oceny nie dają dna, zgadzają się.

Wypowiedź Simona mieści się również w bardzo ważnym kontekście historycznym. W chwili narodzin Haskella (1987) istniała cała gama niesurych języków funkcjonalnych - nie tylko Mirandy, ale Lazy ML, Orwell, Clean i wielu innych. Oprócz niektórych odmian składniowych wszystkie były w tym samym języku. To właśnie była motywacja do utworzenia Komitetu Haskell. Aby uzyskać więcej informacji na ten temat, zobacz „Historia Haskell: leniwość wobec klasy”: http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/ .

Myślę, że SPJ ma rację mówiąc to w przypadku semantyki podstawowej.

Chociaż istnieje wiele zaawansowanych subtelności, na które można wskazać, takich jak domyślna ocena ścisła lub leniwa, jak wspominasz, szczegóły systemów typów lub sposób organizacji większych jednostek kodu (modułów, struktur), model mentalny programu jest bardzo podobne we wszystkich językach funkcjonalnych.

Wybierz konkretną określoną funkcję i napisz ją we wszystkich porównywanych językach, a prawdopodobnie przekonasz się, że struktura i semantyka różnych implementacji będzie bardzo podobna dla wszystkich z nich, w tym poziom abstrakcji, wybrane struktury danych, „ Wszyscy zakładają zbieranie śmieci itp.

Przeciwnie, powiedzmy, że implementacja C w porównaniu z implementacją Smalltalk tej samej funkcji prawdopodobnie będzie miała inną strukturę (funkcje i struktury danych niskiego poziomu w porównaniu z obiektami), skupiając się na różnych poziomach szczegółowości (na przykład ręczne zarządzanie pamięcią vs. ) i działają na różnych poziomach abstrakcji.

Widok świata na funkcjonalną przestrzeń do projektowania języków jest po prostu bardziej konkretny i spójny niż widok „imperatywnego programowania”, które łączy w sobie asembler, C, Smalltalk, Forth i dziesiątki innych radykalnie różnych języków w jedną kategorię catchall.

Myślę, że cytat Simona PJ jest właściwie trochę spostrzeżeniem.

Podobieństwo między językami zależy od tego, jaki konsensus został wygenerowany w społeczności badaczy i projektantów języków. Nie ma wątpliwości, że społeczność programowania funkcjonalnego jest bardziej zgodna niż społeczność programowania imperatywnego. Ale zdarza się również, że funkcjonalne języki programowania są w większości zaprojektowane przez badaczy, a nie praktyków. Jest więc naturalne, że taki konsensus się pojawia.

Prawie wszystkie języki funkcjonalne wykorzystują zarządzanie pamięcią zbierającą śmieci i rekurencyjne struktury danych (pochodzące od Lispa), większość z nich używa „algebraicznych” typów danych i dopasowywania wzorców (pochodzących od Hope), wiele z nich używa funkcji wyższego rzędu i funkcji polimorficznych ( pochodzi od ML). Poza tym konsensus znika. Różnią się one zastosowanymi systemami modułów, sposobem obsługi operacji zmiany stanu i innymi efektami obliczeniowymi oraz kolejnością oceny (nazwa po nazwie vs nazwa po wartości) itp.

Imperatywne języki programowania zwykle używają zagnieżdżonych struktur kontrolnych (pochodzących z Algolu 60) i systemów typów (pochodzących z Algolu 60, ale skonsolidowanych przez Algol 68). Mają na ogół nieporęczną składnię powierzchni (ponownie wracając do Algola 60), podejmują bezmyślne próby obsługi funkcji wyższego rzędu i typów polimorficznych, a także różnią się obsługą struktury bloków i systemów modułów. Prawdopodobnie występuje większa jednorodność w kolejności oceny, ponieważ po latach 60. nazwa w zasadzie zniknęła z języków imperatywnych.

Nie jest więc dla mnie jasne, że różnica między dwiema klasami języków w ich jednolitości jest tak wielka.

Naprawdę warto wprowadzić czystsze i jednolite oznaczenia programowania funkcjonalnego w imperatywnych językach programowania. Widzę, że Scala ma początek w tym kierunku. Dopiero okaże się, czy trend się utrzyma.