Przykład programowania funkcjonalnego. Wady programowania funkcyjnego

Języki podobne do funkcjonalnych używają mniej rygorystycznej koncepcji. Funkcja w matematyce nie może zmienić środowiska, które ją wywołuje i zapamiętuje wyniki jej działania, a jedynie udostępnia wynik obliczenia funkcji. Programowanie za pomocą koncepcja matematyczna funkcje powodują pewne trudności, dlatego języki funkcjonalne w takim czy innym stopniu zapewniają także możliwości imperatywne, co pogarsza konstrukcję programu (na przykład możliwość bezbolesnego dalszego wprowadzania zmian). Dodatkową różnicą w stosunku do imperatywnych języków programowania jest deklaratywny charakter opisów funkcji. Teksty programów w funkcjonalnych językach programowania opisać„jak rozwiązać problem”, ale nie przepisać sekwencja działań w celu rozwiązania. Pierwszym zaprojektowanym językiem funkcjonalnym był Lisp. W systemie szeroko stosowana jest odmiana tego języka projektowanie wspomagane komputerowo AutoLISP

Za główne właściwości funkcjonalnych języków programowania uważa się zwykle:

zwięzłość i prostota;
mocne pisanie;
modułowość;
funkcje są obiektami obliczeniowymi;
odroczone (leniwe) obliczenia.

Niektóre funkcjonalne języki programowania

Miranda (jaka rodzina?)

Spinki do mankietów

http://roman-dushkin.narod.ru/fp.html - Kurs wykładów z programowania funkcyjnego prowadzony w MEPhI od 2001 roku.

Fundacja Wikimedia. 2010.

Zobacz, co oznacza „język programowania funkcjonalnego” w innych słownikach:

Język programowania umożliwiający określenie programu jako zestawu definicji funkcji. W funkcjonalnych językach programowania: funkcje wymieniają między sobą dane bez użycia zmiennych pośrednich i przypisań;... ... Słownik finansowy

funkcjonalny język- Język programowania, w którym działania na danych wyrażane są jako wywołania procedur funkcjonalnych. [GOST 19781 90] Przedmioty wsparcia. systemy przetwarzania Informacja oprogramowanie EN język funkcjonalny... Przewodnik tłumacza technicznego

Ruby Semantyka: wieloparadygmat Typ wykonania: interpreter Opublikowano w: 1995 Autor(zy): Yukihiro Matsumoto Ostatnia wersja: 1.9.1 ... Wikipedia

Funkcjonalny język- 37. Język funkcjonalny Język funkcjonalny Język programowania, w którym działania na danych wyrażane są w formie wywołań procedur funkcjonalnych Źródło: GOST 19781 90: Oprogramowanie wspomagające systemy przetwarzania informacji. Warunki i... ... Słownik-podręcznik terminów dokumentacji normatywnej i technicznej

Erlang Plik:Erlang logo.png Semantyka: multi-paradygmat: konkurencyjne, programowanie funkcjonalne Opublikowano w: 1987 Autor(zy): Typowanie danych: ścisłe, dynamiczne Główne implementacje: E... Wikipedia

Schemat Semantyka: funkcjonalna Typ wykonania: interpreter lub kompilator Ukazał się w: 1970 Autor(zy): Guy Steele i Gerald Sussman Wpisywanie danych... Wikipedia

Termin ten ma inne znaczenia, patrz Miranda. Miranda to funkcjonalny język programowania stworzony w 1985 roku przez Davida Turnera jako standardowy język funkcjonalny. Ma ścisły system typów polimorficznych, ... ... Wikipedię

Hope to funkcjonalny język programowania opracowany na początku lat 80-tych; jest poprzednikiem języków Miranda i Haskell. Magazyn Byte z sierpnia 1985 roku po raz pierwszy opublikował przewodnik po języku Hope. Przykład programu obliczeniowego... ... Wikipedia

Termin ten ma inne znaczenia, patrz SASL. SASL to w pełni funkcjonalny język programowania opracowany przez Davida Turnera na Uniwersytecie St Andrews w 1972 roku, oparty na aplikacyjnym podzbiorze ISWIM. W 1976... ...Wikipedia

Termin ten ma inne znaczenia, patrz Scala. Scala Klasa języka: Wieloparadygmat: funk... Wikipedia

Książki

Programowanie w Clojure. Praktyka używania Lispa w świecie Javy, Emerick Ch., Carper B., Grand K.. Dlaczego wiele osób wybiera Clojure? Jest to funkcjonalny język programowania, który nie tylko pozwala na korzystanie z bibliotek Java, usług i innych zasobów JVM, ale także konkuruje z...

String odwrócony(String arg) ( if(arg.długość == 0) ( return arg; ) else ( return odwrotny(arg.substring(1, arg.length)) + arg.substring(0, 1); ) )
Ta funkcja jest dość powolna, ponieważ wywołuje się wielokrotnie. Może wystąpić wyciek pamięci, ponieważ obiekty tymczasowe są tworzone wiele razy. Ale to jest styl funkcjonalny. Może się wydawać dziwne, jak ludzie potrafią programować w ten sposób. Cóż, właśnie miałem ci powiedzieć.

Korzyści z programowania funkcjonalnego

Prawdopodobnie myślisz, że nie mogę uzasadnić tej potwornej cechy powyżej. Kiedy zaczynałem uczyć się programowania funkcjonalnego, też tak myślałem. Myliłem się. Za tym stylem przemawiają bardzo dobre argumenty. Niektóre z nich są subiektywne. Tak twierdzą na przykład programiści programy funkcjonalnełatwiej zrozumieć. Nie będę wysuwał takich argumentów, bo każdy wie, że łatwość zrozumienia to rzecz bardzo subiektywna. Na szczęście dla mnie nadal istnieje wiele obiektywnych argumentów.

Testów jednostkowych

Ponieważ każdy symbol w FP jest niezmienny, funkcje nie mają żadnych skutków ubocznych. Nie można zmieniać wartości zmiennych, a funkcja nie może zmieniać wartości poza swoim zakresem i w ten sposób wpływać na inne funkcje (co może się zdarzyć w przypadku pól klas lub zmiennych globalnych). Oznacza to, że jedynym wynikiem wykonania funkcji jest wartość zwracana. Jedyną rzeczą, która może mieć wpływ na wartość zwracaną, są argumenty przekazywane do funkcji.

Oto niebieskie marzenie testerów jednostkowych. Możesz przetestować każdą funkcję w programie, używając tylko wymaganych argumentów. Nie ma potrzeby wywoływania funkcji w odpowiedniej kolejności ani odtwarzania prawidłowego stanu zewnętrznego. Wszystko, co musisz zrobić, to przekazać argumenty pasujące do przypadków brzegowych. Jeśli wszystkie funkcje Twojego programu przejdą testy jednostkowe, możesz być znacznie bardziej pewny jakości swojego oprogramowania niż w przypadku imperatywnych języków programowania. W Javie czy C++ sprawdzenie zwracanej wartości nie wystarczy – funkcja może zmienić stan zewnętrzny, co również podlega sprawdzeniu. W FP nie ma takiego problemu.

Debugowanie

Jeśli program funkcjonalny nie zachowuje się zgodnie z oczekiwaniami, debugowanie to bułka z masłem. Zawsze możesz odtworzyć problem, ponieważ błąd w funkcji nie jest zależny od zewnętrznego kodu, który został wcześniej wykonany. W programie imperatywnym błąd pojawia się tylko na chwilę. Będziesz musiał przejść przez szereg kroków bez błędów, ponieważ działanie funkcji zależy od stanu zewnętrznego i skutków ubocznych innych funkcji. W FP sytuacja jest znacznie prostsza - jeśli zwrócona wartość będzie niepoprawna, to zawsze będzie niepoprawna, niezależnie od tego, jakie fragmenty kodu zostały wcześniej wykonane.

Po odtworzeniu błędu znalezienie jego źródła jest zadaniem trywialnym. To nawet miłe. Gdy tylko zatrzymasz program, będziesz miał przed sobą cały stos wywołań. Możesz przeglądać argumenty każdego wywołania funkcji, tak jak w języku imperatywnym. Z tą różnicą, że w programie imperatywnym to nie wystarczy, gdyż funkcje zależą od wartości pól, zmiennych globalnych i stanów innych klas. Funkcja w FP zależy tylko od swoich argumentów, a ta informacja jest tuż przed Twoimi oczami! Co więcej, w programie imperatywnym sprawdzenie wartości zwracanej nie wystarczy, aby stwierdzić, czy fragment kodu zachowuje się poprawnie. Będziesz musiał upolować dziesiątki obiektów poza funkcją, aby upewnić się, że wszystko działa poprawnie. W programowaniu funkcjonalnym wystarczy spojrzeć na wartość zwracaną!

Przeglądając stos, zwracasz uwagę na przekazane argumenty i zwracane wartości. Gdy wartość zwracana odbiega od normy, zagłębiasz się w funkcję i kontynuujesz. Powtarza się to kilka razy, aż znajdziesz źródło błędu!

Wielowątkowość

Program funkcjonalny jest od razu gotowy do równoległości bez żadnych zmian. Nie musisz się martwić zakleszczeniami ani warunkami wyścigowymi, ponieważ nie potrzebujesz zamków! Ani jedna część danych w programie funkcjonalnym nie jest zmieniana dwukrotnie przez ten sam wątek lub przez różne wątki. Oznacza to, że możesz łatwo dodawać wątki do swojego programu, nie martwiąc się o problemy nieodłącznie związane z językami imperatywnymi.

Jeśli tak jest, to dlaczego funkcjonalne języki programowania są tak rzadko używane w aplikacjach wielowątkowych? Właściwie częściej niż myślisz. Firma Ericsson opracował funkcjonalny język o nazwie Erlang do użytku w odpornych na uszkodzenia i skalowalnych przełącznikach telekomunikacyjnych. Wielu zauważyło zalety Erlanga i zaczęło go używać. Mówimy o systemach telekomunikacyjnych i kontroli ruchu, które nie są tak łatwo skalowalne, jak typowe systemy tworzone na Wall Street. Tak naprawdę systemy napisane w Erlangu nie są tak skalowalne i niezawodne jak systemy Java. Systemy Erlang są po prostu super niezawodne.

Na tym historia wielowątkowości się nie kończy. Jeśli piszesz aplikację zasadniczo jednowątkową, kompilator może nadal zoptymalizować program funkcjonalny pod kątem korzystania z wielu procesorów. Spójrzmy na kolejny fragment kodu.

Kompilator języka funkcjonalnego może analizować kod, klasyfikować funkcje generujące linie s1 i s2 jako funkcje czasochłonne i uruchamiać je równolegle. Nie da się tego zrobić w języku imperatywnym, ponieważ każda funkcja może zmienić stan zewnętrzny i kod bezpośrednio po wywołaniu może od tego zależeć. W FP automatyczna analiza funkcji i wyszukiwanie odpowiednich kandydatów do zrównoleglenia jest zadaniem trywialnym, jak automatyczne inline! W tym sensie funkcjonalny styl programowania jest przyszłościowy. Twórcy sprzętu nie mogą już przyspieszać pracy procesora. Zamiast tego zwiększają liczbę rdzeni i żądają czterokrotnego wzrostu szybkości obliczeń wielowątkowych. Oczywiście zapominają w odpowiednim czasie powiedzieć, że twoje nowy procesor wzrost wykaże jedynie w programach opracowanych z uwzględnieniem równoległości. Wśród oprogramowania imperatywnego jest ich bardzo niewiele. Ale 100% programów funkcjonalnych jest gotowych do wielowątkowości od razu po wyjęciu z pudełka.

Gorące wdrożenie

W dawnych czasach aby zainstalować aktualizacje systemu Windows, trzeba było ponownie uruchomić komputer. Wiele razy. Po zainstalowaniu nowej wersji odtwarzacza multimedialnego. W Windows XP zaszły spore zmiany, jednak sytuacja nadal jest daleka od ideału (dziś uruchomiłem Aktualizacja systemu Windows w pracy i teraz irytujące przypomnienie nie daje mi spokoju, dopóki nie uruchomię komputera ponownie). Systemy Unix miały lepszy model aktualizacji. Aby zainstalować aktualizacje, musiałem zatrzymać niektóre komponenty, ale nie cały system operacyjny. Choć sytuacja wygląda lepiej, to w dalszym ciągu jest ona nie do przyjęcia dla dużej klasy aplikacji serwerowych. Systemy telekomunikacyjne muszą być włączone przez cały czas, bo jeśli aktualizacja uniemożliwi wezwanie karetki, może to spowodować śmierć. Firmy z Wall Street również nie chcą wyłączać serwerów na weekend w celu zainstalowania aktualizacji.

Idealnie byłoby, gdybyś zaktualizował wszystkie niezbędne sekcje kodu bez zatrzymywania systemu. W świecie imperatywnym jest to niemożliwe. w Smalltalk jest to bardzo możliwe]. Wyobraź sobie, że wyładowujesz klasę Java w locie i ponownie ładujesz nową wersję. Gdybyśmy to zrobili, wszystkie instancje klasy przestałyby działać, ponieważ przechowywany w nich stan zostałby utracony. Musielibyśmy napisać skomplikowany kod do kontroli wersji. Musielibyśmy serializować wszystkie utworzone instancje klasy, następnie je zniszczyć, utworzyć instancje nowej klasy, spróbować załadować serializowane dane w nadziei, że migracja przebiegnie sprawnie i nowe instancje będą prawidłowe. Poza tym kod migracji trzeba za każdym razem pisać ręcznie. Kod migracji musi zachować połączenia między obiektami. W teorii wszystko jest w porządku, ale w praktyce to nigdy nie zadziała.

W programie funkcjonalnym cały stan jest przechowywany na stosie jako argumenty funkcji. To znacznie ułatwia wdrażanie na gorąco! Zasadniczo wystarczy obliczyć różnicę między kodem na serwerze produkcyjnym a nową wersją i zainstalować zmiany w kodzie. Reszta zostanie wykonana automatycznie przez narzędzia językowe! Jeśli myślisz, że to science fiction, zastanów się dwa razy. Inżynierowie współpracujący z Erlangiem od lat aktualizują swoje systemy, nie przerywając pracy.

Wspomagane maszynowo testy i optymalizacje

Kolejną interesującą właściwością funkcjonalnych języków programowania jest to, że można się ich nauczyć z matematycznego punktu widzenia. Ponieważ język funkcjonalny jest implementacją systemu formalnego, wszystkie operacje matematyczne stosowane na papierze można zastosować w programach funkcjonalnych. Kompilator może na przykład przekonwertować fragment kodu na równoważny, ale bardziej wydajny fragment, matematycznie uzasadniając ich równoważność. Relacyjne bazy danych dane poddawane są takim optymalizacjom od lat. Nic nie stoi na przeszkodzie, aby zastosować podobne techniki w zwykłych programach.

Dodatkowo możesz użyć matematyki, aby udowodnić poprawność sekcji swoich programów. Jeśli chcesz, możesz napisać narzędzia, które analizują Twój kod i automatycznie tworzą testy jednostkowe dla przypadków brzegowych! Ta funkcjonalność jest nieoceniona w przypadku solidnych systemów. Przy opracowywaniu systemów monitorowania rozruszników serca lub systemów zarządzania ruchem lotniczym takie narzędzia są koniecznością. Jeśli Twoje zmiany nie znajdują się w obszarze krytycznym ważne aplikacje, a następnie narzędzia automatyczna kontrola nadal zapewni Ci gigantyczną przewagę nad konkurencją.

Funkcje wyższego rzędu

Pamiętajcie, mówiąc o zaletach FP, zauważyłem, że „wszystko wygląda ładnie, ale na nic się to nie zda, jeśli będę musiał pisać niezdarnym językiem, w którym wszystko jest ostateczne”. To było błędne przekonanie. Użycie final wszędzie wygląda nieporadnie tylko w imperatywnych językach programowania, takich jak Java. Funkcjonalne języki programowania operują innymi rodzajami abstrakcji, takimi, które sprawiają, że zapominasz, że kiedykolwiek lubiłeś zmieniać zmienne. Jednym z takich narzędzi są funkcje wyższego rzędu.

W FP funkcja nie jest tym samym, co funkcja w Javie lub C. Jest to nadzbiór - mogą robić to samo, co funkcje Java, a nawet więcej. Powiedzmy, że mamy funkcję w C:

Int add(int i, int j) ( return i + j; )
W FP nie jest to to samo, co zwykła funkcja C. Rozszerzmy nasz kompilator Java, aby obsługiwał tę notację. Kompilator musi zamienić deklarację funkcji na następujący kod Java (pamiętaj, że wszędzie istnieje ukryty kod końcowy):

Klasa add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Symbol dodawania nie jest tak naprawdę funkcją. To mała klasa z jedną metodą. Teraz możemy przekazać add jako argument do innych funkcji. Możemy zapisać to w innym symbolu. Możemy utworzyć instancje add_function_t w czasie wykonywania i zostaną one zniszczone przez moduł wyrzucający elementy bezużyteczne, jeśli nie będą już potrzebne. Funkcje stają się podstawowe obiekty, podobnie jak liczby i ciągi znaków. Funkcje, które operują na funkcjach (przyjmują je jako argumenty), nazywane są funkcjami wyższego rzędu. Nie pozwól, żeby cię to przestraszyło. Koncepcja funkcji wyższego rzędu jest prawie taka sama, jak koncepcja klas Java, które działają na sobie (możemy przekazywać klasy innym klasom). Można je nazwać „klasami wyższego rzędu”, ale nikt się tym nie przejmuje, ponieważ za Javą nie stoi rygorystyczna społeczność akademicka.

Jak i kiedy należy używać funkcji wyższego rzędu? Cieszę się, że zapytałeś. Piszesz swój program jako jeden duży, monolityczny fragment kodu, nie martwiąc się o hierarchię klas. Jeśli widzisz, że jakiś fragment kodu powtarza się w różnych miejscach, przenosisz go do osobnej funkcji (na szczęście szkoły wciąż uczą, jak to zrobić). Jeśli zauważysz, że część logiki Twojej funkcji powinna zachowywać się inaczej w niektórych sytuacjach, tworzysz funkcję wyższego rzędu. Zdezorientowany? Oto prawdziwy przykład z mojej pracy.

Załóżmy, że mamy fragment kodu Java, który odbiera wiadomość, przekształca ją na różne sposoby i przesyła na inny serwer.

Void handleMessage(Wiadomość) ( // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); ) // ... )
Teraz wyobraź sobie, że system się zmienił i teraz musisz dystrybuować wiadomości między dwoma serwerami zamiast jednego. Wszystko pozostaje bez zmian poza kodem klienta - drugi serwer chce otrzymać ten kod w innym formacie. Jak możemy sobie poradzić z tą sytuacją? Możemy sprawdzić, dokąd ma trafić wiadomość i na tej podstawie ustawić prawidłowy kod klienta. Na przykład tak:

Klasa MessageHandler ( void handleMessage(Message msg) ( // ... if(msg.getDestination().equals("server1") ( msg.setClientCode("ABCD_123"); ) else ( msg.setClientCode("123_ABC") ; ) // ... sendMessage(msg); ) // ... )
Ale to podejście nie sprawdza się dobrze. W miarę dodawania nowych serwerów funkcja będzie się rozwijać liniowo, a wprowadzanie zmian stanie się koszmarem. Podejście obiektowe polega na wyizolowaniu wspólnej nadklasy MessageHandler i podklasie logiki służącej do definiowania kodu klienta:

Klasa abstrakcyjna MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) streszczenie String getClientCode(); // ... ) klasa MessageHandlerOne rozszerza MessageHandler ( String getClientCode() (zwróć "ABCD_123"; ) ) class MessageHandlerTwo rozszerza MessageHandler ( String getClientCode() ( zwróć "123_ABCD"; ) )
Teraz dla każdego serwera możemy stworzyć instancję odpowiedniej klasy. Dodawanie nowych serwerów staje się wygodniejsze. Ale za to mała zmiana za dużo tekstu. Musiałem utworzyć dwa nowe typy, aby dodać obsługę innego kodu klienta! Teraz zróbmy to samo w naszym języku z obsługą funkcji wyższego rzędu:

Klasa MessageHandler ( void handleMessage(Wiadomość msg, funkcja getClientCode) ( // ... Wiadomość msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); ) // ... ) String getClientCodeOne( ) (zwróć "ABCD_123"; ) String getClientCodeTwo() (zwróć "123_ABCD"; ) MessageHandler handler = nowy MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Nie stworzyliśmy nowych typów ani nie skomplikowaliśmy hierarchii klas. Po prostu przekazaliśmy tę funkcję jako parametr. Osiągnęliśmy ten sam efekt, co w odpowiedniku obiektowym, ale z pewnymi zaletami. Nie przywiązaliśmy się do żadnej hierarchii klas: dowolne inne funkcje możemy przekazać do środowiska uruchomieniowego i zmieniać je w dowolnym momencie, zachowując przy tym wysoki poziom modułowości przy mniejszej liczbie kodu. Zasadniczo kompilator stworzył dla nas klej obiektowy! Jednocześnie zachowane są wszystkie pozostałe zalety FP. Oczywiście na tym nie kończą się abstrakcje oferowane przez języki funkcjonalne. Funkcje wyższego rzędu to dopiero początek

Curry

Większość ludzi, których spotykam, czytała książkę „Wzorce projektowe” autorstwa Gangu Czterech. Każdy szanujący się programista powie, że książka nie jest powiązana z żadnym konkretnym językiem programowania, a wzorce mają zastosowanie w ogóle do tworzenia oprogramowania. To szlachetne stwierdzenie. Ale niestety jest to dalekie od prawdy.

Języki funkcjonalne są niezwykle wyraziste. W języku funkcjonalnym nie będziesz potrzebował wzorców projektowych, ponieważ język jest na tak wysokim poziomie, że możesz łatwo rozpocząć programowanie od koncepcji eliminujących wszystkie znane wzorce programistyczne. Jednym z takich wzorów jest Adapter (czym się różni od Fasady? Wygląda na to, że ktoś musiał podstemplować więcej stron, żeby dotrzymać warunków umowy). Ten wzór okazuje się niepotrzebny, jeśli język obsługuje curry.

Wzorzec Adaptera jest najczęściej stosowany do „standardowej” jednostki abstrakcji w Javie – klasy. W językach funkcjonalnych wzór jest stosowany do funkcji. Wzorzec pobiera interfejs i przekształca go w inny interfejs zgodnie z określonymi wymaganiami. Oto przykład wzorca Adaptera:

Int pow(int i, int j); int kwadrat(int i) ( return pow(i, 2); )
Ten kod dostosowuje interfejs funkcji podnoszącej liczbę do dowolnej potęgi do interfejsu funkcji podnoszącej liczbę do kwadratu. W kręgach akademickich tę prostą technikę nazywa się curry (od nazwiska logika Haskella Curry'ego, który wykonał serię matematycznych sztuczek, aby to wszystko sformalizować). Ponieważ funkcje są używane wszędzie jako argumenty w FP, bardzo często stosuje się curry, aby wprowadzić funkcje do interfejsu potrzebnego w tym czy innym miejscu. Ponieważ interfejsem funkcji są jej argumenty, curry służy do zmniejszania liczby argumentów (jak w powyższym przykładzie).

To narzędzie jest wbudowane w języki funkcjonalne. Nie musisz ręcznie tworzyć funkcji, która otacza oryginał. Język funkcjonalny zrobi wszystko za Ciebie. Tradycyjnie poszerzamy nasz język o curry.

Kwadrat = int pow(int i, 2);
Za pomocą tej linii automatycznie tworzymy funkcję kwadratową z jednym argumentem. Nowa funkcja wywoła funkcję pow, podstawiając 2 jako drugi argument. Z perspektywy Javy wyglądałoby to tak:

Klasa kwadrat_funkcja_t ( int kwadrat(int i) ( return pow(i, 2); ) ) funkcja kwadratowa_t kwadrat = nowa funkcja kwadratowa_t();
Jak widać, po prostu napisaliśmy opakowanie na oryginalną funkcję. W FP curry to po prostu prosty i wygodny sposób tworzenia opakowań. Ty skupiasz się na zadaniu, a kompilator pisze za Ciebie niezbędny kod! Jest to bardzo proste i ma miejsce za każdym razem, gdy chcesz użyć wzorca Adapter (opakowanie).

Leniwa ocena

Leniwa (lub odroczona) ocena to interesująca technika, która staje się możliwa, gdy zrozumiesz filozofię funkcjonalną. Mówiąc o wielowątkowości, widzieliśmy już następujący fragment kodu:

Ciąg s1 = nieco długa operacja1(); String s2 = niecoLongOperation2(); Łańcuch s3 = konkatenacja(s1, s2);
W imperatywnych językach programowania kolejność obliczeń nie rodzi żadnych pytań. Ponieważ każda funkcja może wpływać na stan zewnętrzny lub od niego zależeć, konieczne jest zachowanie jasnej kolejności wywołań: najpierw niecoLongOperation1 , potem niecoLongOperation2 , a na końcu konkatenuj. Ale nie wszystko jest takie proste w językach funkcjonalnych.

Jak widzieliśmy wcześniej, niecoLongOperation1 i niecoLongOperation2 można uruchomić jednocześnie, ponieważ mamy pewność, że funkcje te nie wpływają na stan globalny ani nie są od niego zależne. Ale co, jeśli nie chcemy ich wykonywać jednocześnie, czy powinniśmy wywoływać je sekwencyjnie? Odpowiedź brzmi nie. Obliczenia te należy wykonywać tylko wtedy, gdy jakakolwiek inna funkcja zależy od s1 i s2. Nie musimy ich nawet wykonywać, dopóki nie będziemy ich potrzebować w pliku concatenate . Jeśli zamiast konkatenacji podstawimy funkcję, która w zależności od warunku używa jednego z dwóch argumentów, to drugiego argumentu może w ogóle nie zostać obliczony! Haskell jest przykładem leniwego języka oceny. Haskell nie gwarantuje żadnej kolejności wywołań (w ogóle!), ponieważ Haskell wykonuje kod w razie potrzeby.

Leniwe przetwarzanie danych ma wiele zalet, ale także pewne wady. W następnej części omówimy zalety i wyjaśnię, jak żyć z wadami.

Optymalizacja

Leniwa ocena zapewnia ogromny potencjał optymalizacji. Leniwy kompilator patrzy na kod w ten sam sposób, w jaki matematyk patrzy na wyrażenia algebraiczne - może cofać różne działania, anulować wykonanie niektórych sekcji kodu, zmieniać kolejność wywołań dla większej wydajności, a nawet aranżować kod w taki sposób, aby zmniejszyć liczbę błędów, przy jednoczesnym zapewnieniu integralności programu. To właśnie jest największa zaleta opisywania programu za pomocą ścisłych prymitywów formalnych – kod podlega prawom matematycznym i można go studiować metody matematyczne.

Abstrakcyjne struktury kontrolne

Leniwe przetwarzanie zapewnia tak wysoki poziom abstrakcji, że możliwe stają się niesamowite rzeczy. Wyobraźmy sobie na przykład wdrożenie następującej struktury kontrolnej:

Chyba że(stock.isEuropean()) ( sendToSEC(stock); )
Chcemy, aby funkcja sendToSEC była wykonywana tylko wtedy, gdy akcje nie są europejskie. Jak możesz wdrożyć, chyba że? Bez leniwej oceny potrzebowalibyśmy systemu makr, ale w językach takich jak Haskell nie jest to konieczne. Możemy zadeklarować chyba jako funkcję!

Nieważne, chyba że(warunek logiczny, kod listy) ( kod if(!warunek); )
Zauważ, że kod nie zostanie wykonany, jeśli warunek == true . W językach ścisłych tego zachowania nie można powtórzyć, ponieważ argumenty zostaną ocenione wcześniej, chyba że zostaną wywołane.

Nieskończone struktury danych

Leniwe języki pozwalają na tworzenie nieskończonych struktur danych, które są znacznie trudniejsze do stworzenia w językach ścisłych. - tylko nie w Pythonie]. Wyobraźmy sobie na przykład ciąg Fibonacciego. Oczywiście nie możemy obliczyć nieskończonej listy w skończonym czasie i nadal przechowywać ją w pamięci. W ścisłych językach, takich jak Java, po prostu napisalibyśmy funkcję, która zwraca dowolny element sekwencji. W językach takich jak Haskell możemy abstrahować i po prostu zadeklarować nieskończoną listę liczb Fibonacciego. Ponieważ język jest leniwy, obliczone zostaną tylko niezbędne części listy, które są faktycznie używane w programie. Dzięki temu możesz abstrahować od duża liczba problemy i spójrz na nie z większą uwagą wysoki poziom(na przykład możesz użyć funkcji przetwarzania list w nieskończonych sekwencjach).

Wady

Z pewnością darmowy ser dzieje się tylko w pułapce na myszy. Leniwe obliczenia mają wiele wad. Są to głównie wady wynikające z lenistwa. W rzeczywistości bardzo często potrzebna jest bezpośrednia kolejność obliczeń. Weźmy na przykład następujący kod:

W leniwym języku nikt nie gwarantuje, że pierwsza linia zostanie wykonana przed drugą! Oznacza to, że nie możemy wykonywać operacji we/wy, nie możemy normalnie korzystać z funkcji natywnych (w końcu trzeba je wywoływać w określonej kolejności, aby uwzględnić ich skutki uboczne) i nie możemy wchodzić w interakcję z otoczeniem świat! Jeśli wprowadzimy mechanizm porządkowania wykonywania kodu, stracimy przewagę matematycznej ścisłości kodu (a wtedy stracimy wszystkie zalety programowania funkcjonalnego). Na szczęście nie wszystko stracone. Matematycy zabrali się do pracy i opracowali kilka technik zapewniających wykonanie instrukcji we właściwej kolejności, bez utraty ducha funkcjonalności. Mamy to, co najlepsze z obu światów! Techniki takie obejmują kontynuacje, monady i wpisywanie niepowtarzalności. W tym artykule będziemy pracować z kontynuacjami, a monady i jednoznaczne pisanie zostawimy do następnego razu. Ciekawe, że kontynuacje to bardzo przydatna rzecz, która służy nie tylko do zadań ścisły porządek obliczenia. O tym też porozmawiamy.

Sequele

Kontynuacje w programowaniu odgrywają w historii ludzkości tę samą rolę, co Kod Da Vinci: zaskakujące odkrycie największej tajemnicy ludzkości. No, może nie dokładnie tak, ale na pewno zrywają okładki, tak jak kiedyś nauczyłeś się obliczać pierwiastek z -1.

Kiedy przyjrzeliśmy się funkcjom, dowiedzieliśmy się tylko połowy prawdy, ponieważ założyliśmy, że funkcja zwraca wartość funkcji, która ją wywołuje. W tym sensie kontynuacja jest uogólnieniem funkcji. Funkcja nie musi zwracać sterowania do miejsca, z którego została wywołana, ale może wrócić w dowolne miejsce w programie. „Kontynuuj” to parametr, który możemy przekazać do funkcji w celu wskazania punktu powrotu. Brzmi znacznie straszniej, niż jest w rzeczywistości. Przyjrzyjmy się następującemu kodowi:

Int i = dodaj(5, 10); int j = kwadrat(i);
Funkcja add zwraca liczbę 15, która jest zapisywana w i w miejscu wywołania funkcji. Wartość i jest następnie używana podczas wywoływania kwadratu. Należy pamiętać, że leniwy kompilator nie może zmienić kolejności obliczeń, ponieważ druga linia zależy od wyniku pierwszej. Możemy przepisać ten kod, używając stylu przekazywania kontynuacji (CPS), gdzie add zwraca wartość funkcji kwadratowej.

Int j = add(5, 10, kwadrat);
W tym przypadku add otrzymuje dodatkowy argument - funkcję, która zostanie wywołana po zakończeniu działania add. W obu przykładach j będzie równe 225.

Jest to pierwsza technika pozwalająca określić kolejność wykonywania dwóch wyrażeń. Wróćmy do naszego przykładu wejścia/wyjścia.

System.out.println("Wpisz swoje imię i nazwisko: "); System.in.readLine();
Te dwie linie są od siebie niezależne i kompilator może dowolnie zmieniać ich kolejność. Ale jeśli przepiszemy to w CPS, dodamy w ten sposób niezbędną zależność, a kompilator będzie musiał przeprowadzać obliczenia jeden po drugim!

System.out.println("Wpisz swoje imię i nazwisko: ", System.in.readLine);
W tym wypadku println musiałby wywołać funkcję readLine, przekazać jej wynik i na końcu zwrócić wynik funkcji readLine. W tej formie możemy być pewni, że te funkcje zostaną wywołane po kolei i że w ogóle zostanie wywołana funkcja readLine (w końcu kompilator oczekuje wyniku ostatniej operacji). W przypadku Javy println zwraca wartość void. Ale gdyby zwrócona została jakaś abstrakcyjna wartość (która mogłaby służyć jako argument dla metody readLine), rozwiązałoby to nasz problem! Oczywiście budowanie takich łańcuchów funkcji znacznie pogarsza czytelność kodu, ale da się temu zaradzić. Możemy dodać do naszego języka funkcje syntaktyczne, które pozwolą nam pisać wyrażenia w zwykły sposób, a kompilator automatycznie będzie łączyć obliczenia w łańcuchy. Teraz możemy wykonywać obliczenia w dowolnej kolejności, nie tracąc przy tym zalet FP (w tym możliwości studiowania programu metodami matematycznymi)! Jeśli jest to mylące, pamiętaj, że funkcje to tylko instancje klasy z jednym elementem. Przepisz nasz przykład tak, aby println i readLine były instancjami klas, dzięki temu będzie to dla ciebie jaśniejsze.

Na tym jednak nie kończą się zalety sequeli. Cały program możemy napisać za pomocą CPS, dzięki czemu każda funkcja zostanie wywołana dodatkowy parametr, kontynuacja, do której przekazywany jest wynik. W zasadzie każdy program można przełożyć na CPS, jeśli każdą funkcję potraktujemy jako szczególny przypadek kontynuacji. Ta konwersja może zostać wykonana automatycznie (w rzeczywistości robi to wiele kompilatorów).

Gdy tylko skonwertujemy program do postaci CPS, staje się jasne, że każda instrukcja ma kontynuację, czyli funkcję, do której zostanie przekazany wynik, która w normalnym programie byłaby punktem wywołania. Weźmy dowolną instrukcję z ostatniego przykładu, na przykład add(5,10) . W programie napisanym w formie CPS jest jasne, jaka będzie kontynuacja - jest to funkcja, którą add wywoła po zakończeniu pracy. Ale jaka będzie kontynuacja w przypadku programu innego niż CPS? Możemy oczywiście przekonwertować program na CPS, ale czy jest to konieczne?

Okazuje się, że nie jest to konieczne. Przyjrzyj się uważnie naszej konwersji CPS. Jeśli zaczniesz pisać dla niego kompilator, przekonasz się, że wersja CPS nie potrzebuje stosu! Funkcje nigdy niczego nie zwracają, w tradycyjnym znaczeniu słowa „zwrot”, po prostu wywołują inną funkcję, podstawiając wynik obliczeń. Nie ma potrzeby umieszczania argumentów na stosie przed każdym wywołaniem, a następnie umieszczania ich z powrotem. Możemy po prostu przechowywać argumenty w określonym miejscu pamięci i używać skoku zamiast normalnego wywołania. Nie musimy przechowywać oryginalnych argumentów, ponieważ nigdy więcej nie będą potrzebne, ponieważ funkcje nic nie zwracają!

Zatem programy w stylu CPS nie potrzebują stosu, ale zawierają dodatkowy argument w postaci funkcji, którą mają wywołać. Programy w stylu innym niż CPS nie mają dodatkowego argumentu, ale używają stosu. Co jest przechowywane na stosie? Tylko argumenty i wskaźnik do miejsca w pamięci, do którego funkcja powinna zwrócić. Cóż, czy już zgadłeś? Stos przechowuje informacje o kontynuacjach! Wskaźnik do punktu powrotu na stosie jest tym samym, co funkcja, którą należy wywołać w programach CPS! Aby dowiedzieć się, jaka jest kontynuacja add(5,10), po prostu weź punkt powrotu ze stosu.

Nie było to trudne. Kontynuacja i wskaźnik do punktu powrotu to tak naprawdę to samo, jedynie kontynuacja jest podana jawnie i dlatego może różnić się od miejsca wywołania funkcji. Jeśli pamiętasz, że kontynuacja jest funkcją, a funkcja w naszym języku jest wkompilowana w instancję klasy, to zrozumiesz, że wskaźnik do punktu powrotu na stosie i wskaźnik do kontynuacji to w rzeczywistości to samo , ponieważ nasza funkcja (jako instancja klasy) jest tylko wskaźnikiem. Oznacza to, że w dowolnym momencie programu możesz zażądać bieżącej kontynuacji (zasadniczo informacji ze stosu).

OK, teraz rozumiemy, jaka jest bieżąca kontynuacja. Co to znaczy? Jeśli weźmiemy bieżącą kontynuację i gdzieś ją zapiszemy, w ten sposób zapiszemy Stan aktulany program - zamroźmy go. Przypomina to tryb hibernacji systemu operacyjnego. Obiekt kontynuacji przechowuje informacje potrzebne do wznowienia wykonywania programu od momentu, w którym zażądano obiektu kontynuacji. system operacyjny robi to z twoimi programami przez cały czas, kiedy przełącza kontekst między wątkami. Jedyna różnica polega na tym, że wszystko jest pod kontrolą systemu operacyjnego. Jeśli zażądasz obiektu kontynuacji (w Scheme odbywa się to poprzez wywołanie funkcji call-with-current-continuation), to otrzymasz obiekt z bieżącą kontynuacją - stos (lub w przypadku CPS, funkcję następnego wywołania ). Możesz zapisać ten obiekt do zmiennej (lub nawet na dysk). Jeśli zdecydujesz się na „zrestartowanie” programu z tą kontynuacją, wówczas stan twojego programu zostanie „przekształcony” do stanu z chwili pobrania obiektu kontynuacji. Jest to to samo, co przejście na zawieszony wątek lub wybudzenie systemu operacyjnego po hibernacji. Z tą różnicą, że możesz to zrobić wiele razy z rzędu. Po wznowieniu systemu operacyjnego informacje o hibernacji zostają zniszczone. Gdyby tego nie zrobiono, możliwe byłoby przywrócenie stanu systemu operacyjnego z tego samego punktu. To prawie jak podróż w czasie. Dzięki sequelom możesz sobie na to pozwolić!

W jakich sytuacjach kontynuacje się przydadzą? Zwykle, jeśli próbujesz emulować stan w systemach, które z natury są pozbawione stanu. Doskonałe zastosowanie kontynuacji znaleziono w aplikacjach internetowych (na przykład we frameworku Seaside dla języka Smalltalk). Microsoft ASP.NET dokłada wszelkich starań, aby zapisywać stan pomiędzy żądaniami, aby ułatwić Ci życie. Jeśli C# obsługiwał kontynuacje, złożoność ASP.NET można zmniejszyć o połowę, po prostu zapisując kontynuację i przywracając ją przy następnym żądaniu. Z punktu widzenia programisty WWW nie byłoby ani jednej przerwy – program kontynuowałby swoją pracę od następnej linijki! Kontynuacje są niezwykle przydatną abstrakcją do rozwiązywania niektórych problemów. W miarę jak coraz więcej tradycyjnych, grubych klientów przenosi się do sieci, znaczenie kontynuacji będzie z czasem rosło.

Dopasowanie wzoru

Dopasowywanie wzorców nie jest pomysłem nowym ani innowacyjnym. Tak naprawdę ma to niewiele wspólnego z programowaniem funkcjonalnym. Jedynym powodem, dla którego często kojarzy się go z FP, jest to, że od pewnego czasu języki funkcjonalne mają dopasowywanie wzorców, ale języki imperatywne nie.

Rozpocznijmy nasze wprowadzenie do dopasowywania wzorców od następującego przykładu. Oto funkcja do obliczania liczb Fibonacciego w Javie:

Int fib(int n) ( if(n == 0) zwróć 1; if(n == 1) zwróć 1; zwróć fib(n - 2) + fib(n - 1); )
A oto przykład w języku podobnym do Java z obsługą dopasowywania wzorców

Int fib(0) (zwróć 1; ) int fib(1) ( zwróć 1; ) int fib(int n) ( zwróć fib(n - 2) + fib(n - 1); )
Jaka jest różnica? Kompilator implementuje za nas rozgałęzienie.

Pomyśl tylko, to bardzo ważne! To naprawdę nie jest takie ważne. Zauważono, że duża liczba funkcji zawiera złożone struktury przełączników (częściowo dotyczy to programów funkcjonalnych) i postanowiono podkreślić ten punkt. Definicja funkcji jest podzielona na kilka wariantów, a w miejsce argumentów funkcji ustalany jest wzorzec (przypomina to przeciążanie metody). Kiedy następuje wywołanie funkcji, kompilator na bieżąco porównuje argumenty ze wszystkimi definicjami i wybiera najbardziej odpowiednią. Zwykle wybór pada na najbardziej wyspecjalizowaną definicję funkcji. Na przykład int fib(int n) można wywołać, gdy n wynosi 1, ale tak się nie stanie, ponieważ int fib(1) jest bardziej wyspecjalizowaną definicją.

Dopasowywanie wzorców zwykle wygląda na bardziej skomplikowane niż w naszym przykładzie. Przykładowo złożony system dopasowywania wzorców umożliwia napisanie następującego kodu:

Int f(int n< 10) { ... } int f(int n) { ... }
Kiedy dopasowywanie wzorców jest przydatne? Lista takich przypadków jest zaskakująco długa! Za każdym razem, gdy używasz złożonych zagnieżdżonych konstrukcji if, dopasowywanie wzorców może wykonać lepszą pracę przy mniejszym kodzie. Dobrym przykładem, który przychodzi na myśl, jest funkcja WndProc, która jest zaimplementowana w każdym programie Win32 (nawet jeśli jest ukryta przed programistą za wysokim płotem abstrakcji). Zazwyczaj dopasowywanie wzorców może nawet sprawdzić zawartość kolekcji. Na przykład, jeśli przekażesz tablicę do funkcji, możesz wybrać wszystkie tablice, których pierwszy element jest równy 1, a trzeci element jest większy niż 3.

Kolejną zaletą dopasowywania wzorców jest to, że jeśli dokonasz zmian, nie będziesz musiał przekopywać się przez jedną ogromną funkcję. Wszystko, co musisz zrobić, to dodać (lub zmienić) niektóre definicje funkcji. Pozbywamy się w ten sposób całej warstwy wzorów ze słynnej książki Banda Czterech. Im bardziej złożone i rozgałęzione warunki, tym bardziej przydatne będzie użycie dopasowywania wzorców. Gdy zaczniesz ich używać, będziesz się zastanawiać, jak sobie radziłeś bez nich.

Domknięcia

Do tej pory omawialiśmy cechy FP w kontekście języków „czysto” funkcjonalnych – języków będących implementacjami rachunku lambda i nie zawierających cech sprzecznych z formalnym systemem kościelnym. Jednak wiele cech języków funkcjonalnych wykorzystuje się poza rachunkiem lambda. Chociaż implementacja systemu aksjomatycznego jest interesująca z programistycznego punktu widzenia pod względem wyrażeń matematycznych, nie zawsze może mieć to zastosowanie w praktyce. Wiele języków woli używać elementów języków funkcjonalnych, nie trzymając się ścisłej doktryny funkcjonalnej. Niektóre tego typu języki (np. Common Lisp) nie wymagają, aby zmienne były ostateczne – można zmieniać ich wartości. Nie wymagają nawet, aby funkcje polegały wyłącznie na swoich argumentach — funkcje mogą uzyskiwać dostęp do stanu poza swoim zakresem. Ale jednocześnie zawierają takie cechy, jak funkcje wyższego rzędu. Przekazywanie funkcji w nieczystym języku różni się nieco od równoważnej operacji w rachunku lambda i wymaga interesującej funkcji zwanej domknięciem leksykalnym. Rzućmy okiem na następujący przykład. Pamiętaj o tym w w tym przypadku zmienne nie są ostateczne i funkcja może uzyskać dostęp do zmiennych spoza swojego zakresu:

Funkcja makePowerFn(int potęga) ( int powerFn(int podstawa) ( return pow(podstawa, moc); ) zwraca mocFn; ) Kwadrat funkcji = makePowerFn(2); kwadrat(3); // zwraca 9
Funkcja make-power-fn zwraca funkcję, która przyjmuje jeden argument i podnosi go do określonej potęgi. Co się stanie, gdy spróbujemy obliczyć kwadrat(3)? Zmienna moc jest poza zakresem powerFn, ponieważ funkcja makePowerFn została już ukończona, a jej stos został zniszczony. Jak zatem działa kwadrat? Aby funkcja kwadratowa mogła działać, język musi w jakiś sposób przechowywać znaczenie potęgi. A co jeśli utworzymy kolejną funkcję sześcianu, która podnosi liczbę do trzeciej potęgi? Język będzie musiał przechowywać dwie wartości mocy dla każdej funkcji utworzonej w make-power-fn. Zjawisko przechowywania tych wartości nazywa się domknięciem. Zamknięcie nie tylko zachowuje argumenty funkcji najwyższej. Na przykład zamknięcie może wyglądać następująco:

Funkcja makeInkrementator() ( int n = 0; int inkrement() ( return ++n; ) ) Funkcja inc1 = makeInkrementator(); Funkcja inc2 = makeInkrementator(); inc1(); // zwraca 1; inc1(); // zwraca 2; inc1(); // zwraca 3; inc2(); // zwraca 1; inc2(); // zwraca 2; inc2(); // zwraca 3;
Podczas wykonywania wartości n są zapisywane i liczniki mają do nich dostęp. Co więcej, każdy licznik ma swoją kopię n, mimo że powinny one zniknąć po uruchomieniu funkcji makeInkrementator. Jak kompilator udaje się to skompilować? Co dzieje się za kulisami zamknięć? Na szczęście mamy magiczną przepustkę.

Wszystko odbywa się całkiem logicznie. Na pierwszy rzut oka widać, że zmienne lokalne nie podlegają już regułom zakresu, a ich czas życia jest nieokreślony. Oczywiście nie są już przechowywane na stosie - należy je trzymać na stercie. Zamknięcie jest zatem wykonywane podobnie jak funkcja normalna, o której mówiliśmy wcześniej, z tą różnicą, że ma dodatkowe odniesienie do otaczających zmiennych:

Klasa Some_function_t ( SymbolTable parentScope; // ... )
Jeśli zamknięcie uzyskuje dostęp do zmiennej, która nie znajduje się w zasięgu lokalnym, wówczas uwzględnia zakres nadrzędny. To wszystko! Zamknięcie łączy świat funkcjonalny ze światem OOP. Za każdym razem, gdy tworzysz klasę przechowującą jakiś stan i gdzieś go przekazujesz, pamiętaj o domknięciach. Zamknięcie to po prostu obiekt, który tworzy „atrybuty” w locie, usuwając je poza zakres, więc nie musisz tego robić samodzielnie.

Co teraz?

Ten artykuł dotyka jedynie wierzchołka góry lodowej programowania funkcjonalnego. Można kopać głębiej i zobaczyć coś naprawdę dużego, a w naszym przypadku coś dobrego. W przyszłości planuję pisać o teorii kategorii, monadach, funkcjonalnych strukturach danych, systemach typów w językach funkcjonalnych, funkcjonalnej wielowątkowości, funkcjonalnych bazach danych i wielu innych rzeczach. Jeśli uda mi się napisać (i przy okazji przestudiować) choćby połowę z tych tematów, moje życie nie pójdzie na marne. W międzyczasie, Google- twój wierny przyjaciel.

Korzyści z programowania funkcjonalnego

Prawdopodobnie myślisz, że nie mogę uzasadnić tej potwornej cechy powyżej. Kiedy zaczynałem uczyć się programowania funkcjonalnego, też tak myślałem. Myliłem się. Za tym stylem przemawiają bardzo dobre argumenty. Niektóre z nich są subiektywne. Na przykład programiści twierdzą, że programy funkcjonalne są łatwiejsze do zrozumienia. Nie będę wysuwał takich argumentów, bo każdy wie, że łatwość zrozumienia to rzecz bardzo subiektywna. Na szczęście dla mnie nadal istnieje wiele obiektywnych argumentów.

Testów jednostkowych

Debugowanie

Wielowątkowość

Jeśli tak jest, to dlaczego funkcjonalne języki programowania są tak rzadko używane w aplikacjach wielowątkowych? Właściwie częściej niż myślisz. Firma Ericsson opracowała język funkcjonalny o nazwie Erlang do stosowania w odpornych na uszkodzenia i skalowalnych przełącznikach telekomunikacyjnych. Wielu zauważyło zalety Erlanga i zaczęło go używać. Mówimy o systemach telekomunikacyjnych i kontroli ruchu, które nie są tak łatwo skalowalne, jak typowe systemy tworzone na Wall Street. Tak naprawdę systemy napisane w Erlangu nie są tak skalowalne i niezawodne jak systemy Java. Systemy Erlang są po prostu super niezawodne.

Kompilator języka funkcjonalnego może analizować kod, klasyfikować funkcje generujące linie s1 i s2 jako funkcje czasochłonne i uruchamiać je równolegle. Nie da się tego zrobić w języku imperatywnym, ponieważ każda funkcja może zmienić stan zewnętrzny i kod bezpośrednio po wywołaniu może od tego zależeć. W FP automatyczna analiza funkcji i wyszukiwanie odpowiednich kandydatów do zrównoleglenia jest zadaniem trywialnym, jak automatyczne inline! W tym sensie funkcjonalny styl programowania jest przyszłościowy. Twórcy sprzętu nie mogą już przyspieszać pracy procesora. Zamiast tego zwiększają liczbę rdzeni i żądają czterokrotnego wzrostu szybkości obliczeń wielowątkowych. Oczywiście zapominają w porę powiedzieć, że twój nowy procesor będzie wykazywać zyski tylko w programach zaprojektowanych z myślą o równoległości. Wśród oprogramowania imperatywnego jest ich bardzo niewiele. Ale 100% programów funkcjonalnych jest gotowych do wielowątkowości od razu po wyjęciu z pudełka.

Gorące wdrożenie

W dawnych czasach aby zainstalować aktualizacje systemu Windows, trzeba było ponownie uruchomić komputer. Wiele razy. Po zainstalowaniu nowej wersji odtwarzacza multimedialnego. W Windows XP zaszły spore zmiany, ale sytuacja nadal jest daleka od ideału (dzisiaj uruchomiłem Windows Update w pracy i teraz irytujące przypomnienie nie daje mi spokoju, dopóki nie uruchomię systemu ponownie). Systemy Unix miały lepszy model aktualizacji. Aby zainstalować aktualizacje, musiałem zatrzymać niektóre komponenty, ale nie cały system operacyjny. Choć sytuacja wygląda lepiej, to w dalszym ciągu jest ona nie do przyjęcia dla dużej klasy aplikacji serwerowych. Systemy telekomunikacyjne muszą być włączone przez cały czas, bo jeśli aktualizacja uniemożliwi wezwanie karetki, może to spowodować śmierć. Firmy z Wall Street również nie chcą wyłączać serwerów na weekend w celu zainstalowania aktualizacji.

Wspomagane maszynowo testy i optymalizacje

Kolejną interesującą właściwością funkcjonalnych języków programowania jest to, że można się ich nauczyć z matematycznego punktu widzenia. Ponieważ język funkcjonalny jest implementacją systemu formalnego, wszystkie operacje matematyczne stosowane na papierze można zastosować w programach funkcjonalnych. Kompilator może na przykład przekonwertować fragment kodu na równoważny, ale bardziej wydajny fragment, matematycznie uzasadniając ich równoważność. Relacyjne bazy danych dokonują takich optymalizacji od lat. Nic nie stoi na przeszkodzie, aby zastosować podobne techniki w zwykłych programach.

Dodatkowo możesz użyć matematyki, aby udowodnić poprawność sekcji swoich programów. Jeśli chcesz, możesz napisać narzędzia, które analizują Twój kod i automatycznie tworzą testy jednostkowe dla przypadków brzegowych! Ta funkcjonalność jest nieoceniona w przypadku solidnych systemów. Przy opracowywaniu systemów monitorowania rozruszników serca lub systemów zarządzania ruchem lotniczym takie narzędzia są koniecznością. Jeśli Twoje osiągnięcia nie dotyczą aplikacji o znaczeniu krytycznym, wówczas zautomatyzowane narzędzia weryfikacyjne nadal zapewnią Ci ogromną przewagę nad konkurencją.

Funkcje wyższego rzędu

W FP funkcja nie jest tym samym, co funkcja w Javie lub C. Jest to nadzbiór - mogą robić to samo, co funkcje Java, a nawet więcej. Powiedzmy, że mamy funkcję w C:

Klasa add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Symbol dodawania nie jest tak naprawdę funkcją. To mała klasa z jedną metodą. Teraz możemy przekazać add jako argument do innych funkcji. Możemy zapisać to w innym symbolu. Możemy utworzyć instancje add_function_t w czasie wykonywania i zostaną one zniszczone przez moduł wyrzucający elementy bezużyteczne, jeśli nie będą już potrzebne. Funkcje stają się podstawowymi obiektami, podobnie jak liczby i ciągi znaków. Funkcje, które operują na funkcjach (przyjmują je jako argumenty), nazywane są funkcjami wyższego rzędu. Nie pozwól, żeby cię to przestraszyło. Koncepcja funkcji wyższego rzędu jest prawie taka sama, jak koncepcja klas Java, które działają na sobie (możemy przekazywać klasy innym klasom). Można je nazwać „klasami wyższego rzędu”, ale nikt się tym nie przejmuje, ponieważ za Javą nie stoi rygorystyczna społeczność akademicka.

Załóżmy, że mamy fragment kodu Java, który odbiera wiadomość, przekształca ją na różne sposoby i przesyła na inny serwer.

Klasa abstrakcyjna MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) streszczenie String getClientCode(); // ... ) klasa MessageHandlerOne rozszerza MessageHandler ( String getClientCode() (zwróć "ABCD_123"; ) ) class MessageHandlerTwo rozszerza MessageHandler ( String getClientCode() ( zwróć "123_ABCD"; ) )
Teraz dla każdego serwera możemy stworzyć instancję odpowiedniej klasy. Dodawanie nowych serwerów staje się wygodniejsze. Ale tekstu na tak małą zmianę jest sporo. Musiałem utworzyć dwa nowe typy, aby dodać obsługę innego kodu klienta! Teraz zróbmy to samo w naszym języku z obsługą funkcji wyższego rzędu:

Curry

Leniwa ocena

Leniwe przetwarzanie danych ma wiele zalet, ale także pewne wady. W następnej części omówimy zalety i wyjaśnię, jak żyć z wadami.

Optymalizacja

Leniwa ocena zapewnia ogromny potencjał optymalizacji. Leniwy kompilator patrzy na kod w ten sam sposób, w jaki matematyk patrzy na wyrażenia algebraiczne - może cofać różne działania, anulować wykonanie niektórych sekcji kodu, zmieniać kolejność wywołań dla większej wydajności, a nawet aranżować kod w taki sposób, aby zmniejszyć liczbę błędów, przy jednoczesnym zapewnieniu integralności programu. To właśnie jest największa zaleta opisywania programu przy użyciu ścisłych prymitywów formalnych – kod podlega prawom matematycznym i można go badać metodami matematycznymi.

Abstrakcyjne struktury kontrolne

Leniwe przetwarzanie zapewnia tak wysoki poziom abstrakcji, że możliwe stają się niesamowite rzeczy. Wyobraźmy sobie na przykład wdrożenie następującej struktury kontrolnej:

Nieskończone struktury danych

Leniwe języki pozwalają na tworzenie nieskończonych struktur danych, które są znacznie trudniejsze do stworzenia w językach ścisłych. - tylko nie w Pythonie]. Wyobraźmy sobie na przykład ciąg Fibonacciego. Oczywiście nie możemy obliczyć nieskończonej listy w skończonym czasie i nadal przechowywać ją w pamięci. W ścisłych językach, takich jak Java, po prostu napisalibyśmy funkcję, która zwraca dowolny element sekwencji. W językach takich jak Haskell możemy abstrahować i po prostu zadeklarować nieskończoną listę liczb Fibonacciego. Ponieważ język jest leniwy, obliczone zostaną tylko niezbędne części listy, które są faktycznie używane w programie. Pozwala to na abstrahowanie od dużej liczby problemów i spojrzenie na nie z wyższego poziomu (można np. wykorzystać funkcje do przetwarzania list na ciągach nieskończonych).

Wady

Oczywiście darmowy ser pojawia się tylko w pułapce na myszy. Leniwe obliczenia mają wiele wad. Są to głównie wady wynikające z lenistwa. W rzeczywistości bardzo często potrzebna jest bezpośrednia kolejność obliczeń. Weźmy na przykład następujący kod:

W leniwym języku nikt nie gwarantuje, że pierwsza linia zostanie wykonana przed drugą! Oznacza to, że nie możemy wykonywać operacji we/wy, nie możemy normalnie korzystać z funkcji natywnych (w końcu trzeba je wywoływać w określonej kolejności, aby uwzględnić ich skutki uboczne) i nie możemy wchodzić w interakcję z otoczeniem świat! Jeśli wprowadzimy mechanizm porządkowania wykonywania kodu, stracimy przewagę matematycznej ścisłości kodu (a wtedy stracimy wszystkie zalety programowania funkcjonalnego). Na szczęście nie wszystko stracone. Matematycy zabrali się do pracy i opracowali kilka technik zapewniających wykonanie instrukcji we właściwej kolejności, bez utraty ducha funkcjonalności. Mamy to, co najlepsze z obu światów! Techniki takie obejmują kontynuacje, monady i wpisywanie niepowtarzalności. W tym artykule będziemy pracować z kontynuacjami, a monady i jednoznaczne pisanie zostawimy do następnego razu. Co ciekawe, kontynuacje są bardzo przydatną rzeczą, która służy nie tylko do określenia ścisłej kolejności obliczeń. O tym też porozmawiamy.

Sequele

Int j = add(5, 10, kwadrat);
W tym przypadku add otrzymuje dodatkowy argument - funkcję, która zostanie wywołana po zakończeniu działania add. W obu przykładach j będzie równe 225.

Jest to pierwsza technika pozwalająca określić kolejność wykonywania dwóch wyrażeń. Wróćmy do naszego przykładu wejścia/wyjścia.

Na tym jednak nie kończą się zalety sequeli. Cały program możemy napisać za pomocą CPS, tak aby każda funkcja była wywoływana z dodatkowym parametrem, kontynuacją, do której przekazywany jest wynik. W zasadzie każdy program można przełożyć na CPS, jeśli każdą funkcję potraktujemy jako szczególny przypadek kontynuacji. Ta konwersja może zostać wykonana automatycznie (w rzeczywistości robi to wiele kompilatorów).

OK, teraz rozumiemy, jaka jest bieżąca kontynuacja. Co to znaczy? Jeśli weźmiemy bieżącą kontynuację i gdzieś ją zapiszemy, zapisujemy w ten sposób aktualny stan programu - zamrażamy go. Przypomina to tryb hibernacji systemu operacyjnego. Obiekt kontynuacji przechowuje informacje potrzebne do wznowienia wykonywania programu od momentu, w którym zażądano obiektu kontynuacji. System operacyjny robi to z programami za każdym razem, gdy przełącza kontekst między wątkami. Jedyna różnica polega na tym, że wszystko jest pod kontrolą systemu operacyjnego. Jeśli zażądasz obiektu kontynuacji (w Scheme odbywa się to poprzez wywołanie funkcji call-with-current-continuation), to otrzymasz obiekt z bieżącą kontynuacją - stos (lub w przypadku CPS, funkcję następnego wywołania ). Możesz zapisać ten obiekt do zmiennej (lub nawet na dysk). Jeśli zdecydujesz się na „zrestartowanie” programu z tą kontynuacją, wówczas stan twojego programu zostanie „przekształcony” do stanu z chwili pobrania obiektu kontynuacji. Jest to to samo, co przejście na zawieszony wątek lub wybudzenie systemu operacyjnego po hibernacji. Z tą różnicą, że możesz to zrobić wiele razy z rzędu. Po wznowieniu systemu operacyjnego informacje o hibernacji zostają zniszczone. Gdyby tego nie zrobiono, możliwe byłoby przywrócenie stanu systemu operacyjnego z tego samego punktu. To prawie jak podróż w czasie. Dzięki sequelom możesz sobie na to pozwolić!

Dopasowanie wzoru

Rozpocznijmy nasze wprowadzenie do dopasowywania wzorców od następującego przykładu. Oto funkcja do obliczania liczb Fibonacciego w Javie:

Int fib(int n) ( if(n == 0) zwróć 1; if(n == 1) zwróć 1; zwróć fib(n - 2) + fib(n - 1); )
A oto przykład w języku podobnym do Java z obsługą dopasowywania wzorców

Int fib(0) (zwróć 1; ) int fib(1) ( zwróć 1; ) int fib(int n) ( zwróć fib(n - 2) + fib(n - 1); )
Jaka jest różnica? Kompilator implementuje za nas rozgałęzienie.

Dopasowywanie wzorców zwykle wygląda na bardziej skomplikowane niż w naszym przykładzie. Przykładowo złożony system dopasowywania wzorców umożliwia napisanie następującego kodu:

Domknięcia

Do tej pory omawialiśmy cechy FP w kontekście języków „czysto” funkcjonalnych – języków będących implementacjami rachunku lambda i nie zawierających cech sprzecznych z formalnym systemem kościelnym. Jednak wiele cech języków funkcjonalnych wykorzystuje się poza rachunkiem lambda. Chociaż implementacja systemu aksjomatycznego jest interesująca z programistycznego punktu widzenia pod względem wyrażeń matematycznych, nie zawsze może mieć to zastosowanie w praktyce. Wiele języków woli używać elementów języków funkcjonalnych, nie trzymając się ścisłej doktryny funkcjonalnej. Niektóre tego typu języki (np. Common Lisp) nie wymagają, aby zmienne były ostateczne – można zmieniać ich wartości. Nie wymagają nawet, aby funkcje polegały wyłącznie na swoich argumentach — funkcje mogą uzyskiwać dostęp do stanu poza swoim zakresem. Ale jednocześnie zawierają takie cechy, jak funkcje wyższego rzędu. Przekazywanie funkcji w nieczystym języku różni się nieco od równoważnej operacji w rachunku lambda i wymaga interesującej funkcji zwanej domknięciem leksykalnym. Rzućmy okiem na następujący przykład. Pamiętaj, że w tym przypadku zmienne nie są ostateczne i funkcja może uzyskać dostęp do zmiennych spoza swojego zakresu:

Co teraz?

Leniwe obliczenia

W tradycyjnych językach programowania (takich jak C++) wywołanie funkcji powoduje ocenę wszystkich argumentów. Ta metoda wywoływania funkcji nazywa się call-by-value. Jeżeli w funkcji nie został użyty żaden argument, to wynik obliczeń zostaje utracony, zatem obliczenia zostały wykonane na próżno. W pewnym sensie przeciwieństwem wezwania według wartości jest wezwanie według konieczności. W tym przypadku argument jest oceniany tylko wtedy, gdy jest potrzebny do obliczenia wyniku. Przykładem takiego zachowania jest operator koniunkcji z C++ (&&), który nie ocenia wartości drugiego argumentu, jeśli pierwszy argument jest fałszywy.

Jeśli język funkcjonalny nie obsługuje leniwej oceny, nazywa się go ścisłym. Tak naprawdę w takich językach kolejność oceniania jest ściśle określona. Przykładami języków ścisłych są Scheme, Standard ML i Caml.

Języki korzystające z leniwej oceny nazywane są nieścisłymi. Haskell jest językiem luźnym, podobnie jak na przykład Gofer i Miranda. Języki luźne są często czyste.

Bardzo często języki ścisłe obejmują obsługę niektórych przydatnych funkcji dostępnych w językach nieścisłych, takich jak listy nieskończone. Standard ML jest wyposażony w specjalny moduł obsługujący obliczenia odroczone. Ponadto Objective Caml obsługuje dodatkowe słowo zastrzeżone leniwy i konstrukcję dla list wartości obliczanych według potrzeb.

Ta sekcja zapewnia krótki opis niektóre funkcjonalne języki programowania (bardzo niewiele).

§ Seplenienie(Procesor list). Uważany jest za pierwszy funkcjonalny język programowania. Nietypowane. Zawiera wiele imperatywnych właściwości, ale ogólnie zachęca do funkcjonalnego stylu programowania. Do obliczeń wykorzystuje funkcję call-by-value. Istnieje obiektowy dialekt języka - CLOS.

§ PŁYWAM(Jeśli widzisz co mam na myśli). Prototyp języka funkcjonalnego. Opracowany przez Landina w latach 60. XX wieku, aby zademonstrować, czym mógłby być funkcjonalny język programowania. Oprócz języka Landin opracował także specjalną maszynę wirtualną do wykonywania programów w ISWIM. Ten maszyna wirtualna, w oparciu o call-by-value, nazywa się maszyną SECD. Składnia wielu języków funkcjonalnych opiera się na składni języka ISWIM. Składnia ISWIM jest podobna do ML, zwłaszcza Caml.

§ Schemat. Dialekt Lisp przeznaczony do badań naukowych w dziedzinie informatyki. Schemat został zaprojektowany z naciskiem na elegancję i prostotę języka. To sprawia, że język jest znacznie mniejszy niż Common Lisp.

§ M.L.(Metajęzyk). Rodzina ścisłych języków z rozwiniętym systemem typów polimorficznych i parametryzowalnymi modułami. ML jest wykładane na wielu zachodnich uniwersytetach (niektóre nawet jako pierwszy język programowania).

§ Standardowy ML. Jeden z pierwszych typowych języków programowania funkcjonalnego. Zawiera pewne istotne właściwości, takie jak linki do wartości zmienne i dlatego nie jest czysty. Do obliczeń wykorzystuje funkcję call-by-value. Bardzo ciekawa realizacja modułowości. Potężny system typów polimorficznych. Najnowszym standardem językowym jest Standard ML-97, dla którego istnieją formalne matematyczne definicje składni oraz statycznej i dynamicznej semantyki języka.

§ Światło Camla I Obiektywny Caml. Podobnie jak Standard ML należy do rodziny ML. Objective Caml różni się od Caml Light głównie obsługą klasycznego programowania obiektowego. Podobnie jak standardowe ML jest rygorystyczne, ale ma wbudowaną obsługę leniwej oceny.

§ Miranda. Opracowany przez Davida Turnera jako standardowy język funkcjonalny wykorzystujący leniwą ocenę. Ma ścisły system typów polimorficznych. Podobnie jak ML, jest nauczany na wielu uniwersytetach. Miał wielki wpływ na twórców języka Haskell.

§ Haskell. Jeden z najpopularniejszych języków nieścisłych. Ma bardzo rozwinięty system pisania. System modułowy jest nieco słabiej rozwinięty. Najnowszym standardem językowym jest Haskell-98.

§ Gofera(Dobre dla równania rozumowania). Uproszczony dialekt Haskella. Przeznaczony do nauki programowania funkcjonalnego.

§ Czysty. Zaprojektowany specjalnie do programowania równoległego i rozproszonego. Składnia jest podobna do Haskella. Czysty. Używa odroczonych obliczeń. Do kompilatora dołączony jest zestaw bibliotek (biblioteki I/O), które umożliwiają zaprogramowanie graficznego interfejsu użytkownika pod Win32 lub MacOS.

Przypomnijmy Ci to najważniejsza cecha Podejście funkcjonalne polega na tym, że za funkcję można uznać dowolny program napisany w funkcjonalnym języku programowania, którego argumenty mogą być również funkcjami.

Podejście funkcjonalne dało początek całej rodzinie języków, której przodkiem, jak już wspomniano, był język programowania LISP. Później, w latach 70., opracowano pierwotną wersję języka ML, która następnie rozwinęła się w szczególności w SML i szereg innych języków. Spośród nich być może „najmłodszym” jest język Haskell, powstały całkiem niedawno, bo w latach 90-tych.

Ważną zaletą wdrażania funkcjonalnych języków programowania jest zautomatyzowany dynamiczny przydział pamięci komputera do przechowywania danych. W takim przypadku programista pozbywa się konieczności kontrolowania danych, a w razie potrzeby może uruchomić funkcję „odśmiecania” – czyszczenia pamięci z danych, których program nie będzie już potrzebował.

Złożone programy w podejściu funkcjonalnym buduje się poprzez agregację funkcji. W tym przypadku tekst programu jest funkcją, której niektóre argumenty można również uznać za funkcje. Ponowne wykorzystanie kodu sprowadza się więc do wywołania wcześniej opisanej funkcji, której struktura w odróżnieniu od procedury języka imperatywnego jest matematycznie przejrzysta.

Ponieważ funkcja jest naturalnym formalizmem dla funkcjonalnych języków programowania, wdrażanie różnych aspektów programowania związanego z funkcjami jest znacznie uproszczone. Pisanie funkcji rekurencyjnych staje się intuicyjnie przejrzyste, tj. funkcje, które wywołują siebie jako argument. Naturalne staje się także wdrożenie przetwarzania rekurencyjnych struktur danych.

Dzięki zaimplementowaniu mechanizmu dopasowywania wzorców funkcjonalne języki programowania, takie jak ML i Haskell, dobrze sprawdzają się w przetwarzaniu symbolicznym.

Oczywiście funkcjonalne języki programowania nie są pozbawione pewnych wad.

Często można do nich zaliczyć nieliniową strukturę programu i stosunkowo niską efektywność realizacji. Jednak pierwsza wada jest dość subiektywna, a drugą udało się przezwyciężyć dzięki nowoczesnym wdrożeniom, w szczególności szeregowi najnowszych tłumaczy języka SML, w tym kompilatorowi dla środowiska Microsoft .NET.

Aby stworzyć profesjonalne oprogramowanie w funkcjonalnych językach programowania, musisz głęboko zrozumieć naturę funkcji.

Należy zauważyć, że termin „funkcja” w formalizacji matematycznej i implementacji oprogramowania odnosi się do różnych koncepcji.

Zatem funkcja matematyczna f z dziedziną definicji A i zakresem wartości B jest zbiorem par uporządkowanych

takie, że jeśli

(a,b 1) f i (a,b 2) f,

Z kolei funkcja w języku programowania jest konstrukcją tego języka opisującą zasady konwersji argumentu (tzw. parametru rzeczywistego) na wynik.

Aby sformalizować pojęcie „funkcji”, skonstruowano teorię matematyczną znaną jako rachunek lambda. Dokładniej, rachunek ten należy nazwać rachunkiem konwersji lambda.

Konwersja odnosi się do transformacji obiektów rachunku różniczkowego (a w programowaniu, funkcji i danych) z jednej formy do drugiej. Oryginalne zadanie w matematyce istniała chęć uproszczenia formy wyrażeń. W programowaniu to konkretne zadanie nie jest aż tak istotne, chociaż jak zobaczymy później, zastosowanie rachunku lambda jako wstępnej formalizacji może pomóc w uproszczeniu typu programu, tj. prowadzić do optymalizacji kodu programu.

Ponadto konwersje zapewniają przejście do nowo wprowadzonych zapisów, a tym samym umożliwiają przedstawienie obszaru tematycznego w bardziej zwięzłej lub bardziej szczegółowej formie, czyli inaczej mówiąc język matematyczny, zmień poziom abstrakcji w stosunku do Tematyka. Ta funkcja jest również szeroko stosowana w obiektowych i strukturalno-modularnych językach programowania w hierarchii obiektów, fragmentów programu i struktur danych. Na tej samej zasadzie opiera się interakcja komponentów aplikacji w .NET. W tym sensie przejście do nowych zapisów jest jednym z najważniejszych elementów programowania w ogóle i to właśnie rachunek lambda (w przeciwieństwie do wielu innych działów matematyki) stanowi adekwatny sposób sformalizowania renotacji.

Usystematyzujmy ewolucję teorii leżących u podstaw współczesnego podejścia do rachunku lambda.

Rozważmy ewolucję języków programowania rozwijających się w ramach podejścia funkcjonalnego.

Wczesne funkcjonalne języki programowania, wywodzące się z klasycznego języka LISP (LISt Processing), przeznaczone były do przetwarzania list, czyli tzw. informacja symboliczna. W tym przypadku głównymi typami były element atomowy i lista elementów atomowych, a główny nacisk położono na analizę zawartości listy.

Rozwój wczesnych języków programowania stał się funkcjonalnymi językami programowania z silnym typowaniem, typowym przykładem jest tutaj klasyczny ML i jego bezpośredni potomek SML. W językach silnie typowanych każda konstrukcja (lub wyrażenie) musi mieć typ.

Jednak w późniejszych funkcjonalnych językach programowania nie ma potrzeby jawnego przypisywania typów, a typy początkowo niezdefiniowanych wyrażeń, tak jak w SML, można wywnioskować (przed uruchomieniem programu) na podstawie typów wyrażeń z nimi powiązanych .

Kolejnym krokiem w rozwoju funkcjonalnych języków programowania była obsługa funkcji polimorficznych, tj. funkcje z argumentami parametrycznymi (analogi funkcja matematyczna z parametrami). W szczególności polimorfizm jest obsługiwany w SML, Miranda i Haskell.

Na obecnym etapie rozwoju pojawiły się funkcjonalne języki programowania „nowej generacji” posiadające następujące zaawansowane możliwości: dopasowywanie wzorców (Scheme, SML, Miranda, Haskell), polimorfizm parametryczny (SML) oraz tzw. potrzebne) obliczenia (Haskell, Miranda, S.M.L.).

Rodzina funkcjonalnych języków programowania jest dość duża. Świadczy o tym nie tyle pokaźna lista języków, ile fakt, że wiele języków dało początek całym trendom w programowaniu. Przypomnijmy, że LISP dał początek całej rodzinie języków: Scheme, InterLisp, COMMON Lisp itp.

Język programowania SML nie był wyjątkiem, który został stworzony w formie języka ML przez R. Milnera w MIT (Massachusetts Institute of Technology) i pierwotnie był przeznaczony do dedukcji logicznych, w szczególności do dowodzenia twierdzeń. Język jest inny mocne pisanie, brakuje mu polimorfizmu parametrycznego.

Rozwój „klasycznego” ML stał się trzema nowoczesnymi językami o niemal identycznych możliwościach (polimorfizm parametryczny, dopasowywanie wzorców, „leniwe” obliczenia). Jest to język SML, opracowany w Wielkiej Brytanii i USA, CaML, stworzony przez grupę francuskich naukowców w Instytucie INRIA, SML/NJ – dialekt SML z New Jersey, a także rozwinięcie rosyjskie – mosml („ Moskiewski” dialekt ML).

Bliskość formalizacji matematycznej i wyjściowa orientacja funkcjonalna spowodowały, że podejście funkcjonalne ma następujące zalety:

1. łatwość testowania i weryfikacji kodu programu w oparciu o możliwość skonstruowania rygorystycznego matematycznego dowodu poprawności programów;

2. ujednolicenie prezentacji programu i danych (dane można enkapsulować w programie jako argumenty funkcji, można dokonać wyznaczenia lub obliczenia wartości funkcji w zależności od potrzeb);

3. bezpieczne pisanie: wykluczone są nieprawidłowe operacje na danych;

4. pisanie dynamiczne: możliwe jest wykrycie błędów w czasie wykonywania (brak tej właściwości we wczesnych funkcjonalnych językach programowania może prowadzić do zapełnienia pamięci RAM komputera);

5. niezależność implementacji oprogramowania od maszynowej reprezentacji danych i architektury systemu programu (programista skupia się na szczegółach implementacji, a nie na cechach maszynowej reprezentacji danych).

Należy pamiętać, że uświadomienie sobie korzyści, jakie zapewniają funkcjonalne języki programowania, zależy w dużej mierze od wyboru platformy programowej i sprzętowej.

Jeśli jako platformę programową zostanie wybrana technologia .NET, niemal niezależnie od implementacji sprzętowej, programisty czy menadżera projekt oprogramowania dodatkowo otrzymuje następujące korzyści:

1. integracja różnych funkcjonalnych języków programowania (maksymalizując zalety każdego języka, w szczególności Scheme zapewnia mechanizm dopasowywania wzorców, a SML zapewnia możliwość obliczeń według potrzeb);

2. integracja różnych podejść do programowania w oparciu o międzyjęzykową infrastrukturę Common Language Infrastructure, czyli CLI (w szczególności możliwe jest wykorzystanie języka C# w celu zapewnienia zalet podejścia obiektowego i funkcjonalności SML, jak w tym kursie) ;

3. wspólny ujednolicony system pisania Common Type System, CTS (jednolity i bezpieczne zarządzanie rodzaje danych w programie);

4. wieloetapowy, elastyczny system zapewnienia bezpieczeństwa kodu programu (w szczególności oparty na mechanizmie asemblera).

Głównymi cechami funkcjonalnych języków programowania, które odróżniają je zarówno od języków imperatywnych, jak i języków programowania logicznego, są przejrzystość referencyjna i determinizm. W językach funkcjonalnych występują znaczne różnice w parametrach, takich jak zasady pisania i obliczania. W wielu językach kolejność oceniania jest ściśle określona. Ale czasami języki ścisłe zawierają obsługę niektórych przydatnych elementów właściwych dla języków nieścisłych, takich jak nieskończone listy (Standard ML ma specjalny moduł do obsługi leniwej oceny). Natomiast nieścisłe języki umożliwiają w niektórych przypadkach obliczenia energetyczne.

Zatem Miranda ma leniwą semantykę, ale pozwala określić ścisłe konstruktory poprzez oznaczenie argumentów konstruktora w określony sposób.

Wiele współczesnych języków programowania funkcjonalnego to języki silnie typowane (silne typowanie). Silne pisanie zapewnia większe bezpieczeństwo. Wiele błędów można poprawić na etapie kompilacji, dzięki czemu etap debugowania i całkowity czas tworzenia programu są skrócone. Silne pisanie pozwala kompilatorowi wygenerować bardziej wydajny kod, a tym samym przyspieszyć wykonanie programu. Oprócz tego istnieją języki funkcjonalne z dynamicznym pisaniem. Typ danych w takich językach jest ustalany podczas wykonywania programu (rozdział 3). Czasami nazywane są „bez typu”. Do ich zalet należy fakt, że programy napisane w tych językach mają większą ogólność. Za wadę można uznać przypisanie wielu błędów etapowi wykonania programu i związaną z tym konieczność stosowania funkcji sprawdzania typu i odpowiadające temu zmniejszenie ogólności programu. Języki pisane przyczyniają się do generowania bardziej „niezawodnego” kodu, podczas gdy języki pisane generują bardziej „ogólny” kod.

Kolejnym kryterium klasyfikacji funkcjonalnych języków programowania może być obecność mechanizmów imperatywnych. Jednocześnie zwyczajowo nazywa się funkcjonalne języki programowania pozbawione mechanizmów imperatywnych „czystymi”, a te, które je posiadają, nazywane są „nieczystymi”. W poniższym przeglądzie funkcjonalnych języków programowania, języki programowania będą określane jako „praktyczne” i „akademickie”. Przez języki „praktyczne” rozumie się języki, które mają zastosowanie komercyjne (stworzono w nich rzeczywiste aplikacje lub istniały komercyjne systemy programowania). Akademickie języki programowania są popularne w kręgach badawczych i terenowych edukacja komputerowa, ale praktycznie nie ma aplikacji komercyjnych napisanych w takich językach. Pozostają jedynie narzędziem do prowadzenia badań teoretycznych z zakresu informatyki i znajdują szerokie zastosowanie w procesie edukacyjnym.

Poniżej znajduje się lista najpopularniejszych języków programowania funkcjonalnego według następujących kryteriów: informacje ogólne; pisanie na maszynie; rodzaj obliczeń; czystość.

Wspólny Lisp. Wersja Lispa, która od 1970 roku, dzięki wsparciu laboratorium, może być uznana za standard językowy sztuczna inteligencja Massachusetts Institute of Technology, beztypowy, energetyczny, z dużym zestawem imperatywnych inkluzji, które umożliwiają przypisywanie i niszczenie struktur. Praktyczny. Dość powiedzieć, że edytor grafiki wektorowej AutoCAD został napisany w języku Lisp.

Schemat. Dialekt Lisp przeznaczony do badań naukowych w informatyce i nauczania programowania funkcjonalnego. Dzięki brakowi inkluzji imperatywnych język jest znacznie mniejszy niż Common Lisp. Pochodzi z języka opracowanego przez J. McCarthy'ego w 1962 roku. Akademicki, beztypowy, energiczny, czysty.

Refala. Rodzina języków opracowana przez V. F. Turchina. Najstarszy członek tej rodziny został po raz pierwszy zrealizowany w 1968 roku w Rosji. Jest nadal szeroko stosowany w kręgach akademickich. Zawiera elementy programowania logicznego (dopasowywanie wzorców). Dlatego w tym artykule zaproponowano język Refal podręcznik jako język do samodzielnej nauki.

Miranda. Silnie wpisany, obsługuje typy danych użytkownika i polimorfizm. Opracowany przez Turnera w oparciu o wcześniejsze języki SALS i KRC. Ma leniwą semantykę. Żadnych imperatywnych wtrąceń.

Haskell. Rozwój języka nastąpił pod koniec ubiegłego wieku. Powszechnie znany w kręgach akademickich. Na niektórych zachodnich uniwersytetach jest on używany jako główny język, na którym studiują studenci. Jeden z najpotężniejszych języków funkcjonalnych. Leniwy język. Język czysto funkcjonalny. Wpisane. Haskell to świetne narzędzie do nauki i eksperymentowania ze złożonymi funkcjonalnymi typami danych. Programy napisane w Haskell mają znaczny rozmiar kodu obiektowego i niską prędkość wykonywania.

Czysty. Dialekt Haskella dostosowany do potrzeb praktycznego programowania. Podobnie jak Haskell, jest to leniwy, czysto funkcjonalny język, zawierający klasy typów. Ale Clean zawiera również ciekawe funkcje, które nie mają odpowiednika w Haskell. Na przykład funkcje imperatywne w Clean opierają się na unikalnych typach, których idea jest zapożyczona z logiki liniowej. Clean zawiera mechanizmy, które mogą znacznie poprawić wydajność programów. Mechanizmy te wyraźnie tłumią leniwe obliczenia. Wdrożenie Clean jest produktem komercyjnym, ale dostępna jest darmowa wersja do celów badawczych i edukacyjnych.

ML (metajęzyk). Opracowany przez grupę programistów pod przewodnictwem Roberta Miliera w połowie lat 70-tych. w Edynburgu (Edinburgh Logic for Computable Functions). Ideą języka było stworzenie mechanizmu konstruowania dowodów formalnych w systemie logicznym dla funkcji obliczeniowych. W 1983 roku język został zmieniony, aby uwzględnić takie pojęcia, jak moduły. Zaczęto nazywać standardowym ML. ML jest mocny język wpisany ze statycznym sprawdzaniem typu i wykonaniem programu aplikacyjnego. Zyskała dużą popularność w kręgach naukowych i w dziedzinie edukacji komputerowej.

Programowanie funkcjonalne

1. Wstęp

Programy w tradycyjnych językach programowania takich jak C, Pascal, Java itp. Składają się z sekwencji modyfikacji wartości pewnego zestawu zmiennych, który nazywa się stanem. Jeśli nie weźmiemy pod uwagę operacji I/O, a także nie uwzględnimy faktu, że program może działać w sposób ciągły (czyli bez zatrzymywania, jak w przypadku programów serwerowych), możemy dokonać następującej abstrakcji. Przed rozpoczęciem wykonywania programu stan ma pewną wartość początkową σ0, która reprezentuje wartości wejściowe programu. Po zakończeniu programu stan przyjmuje nową wartość σ0, która uwzględnia to, co można uznać za „wynik” programu. Podczas wykonywania każde polecenie zmienia stan; dlatego stan przechodzi przez pewną skończoną sekwencję wartości:

σ = σ0 → σ1 → σ2 → · · · → σn = σ0

Stan jest modyfikowany za pomocą poleceń przypisania zapisanych jako v=E lub v:=E, gdzie v jest zmienną, a E jest jakimś wyrażeniem. Polecenia te następują jedno po drugim; Instrukcje takie jak if i while umożliwiają zmianę kolejności wykonywania tych poleceń w zależności od aktualnej wartości stanu. Ten styl programowania nazywany jest imperatywnym lub proceduralnym.

Programowanie funkcjonalne reprezentuje paradygmat zasadniczo odmienny od modelu przedstawionego powyżej. Program funkcjonalny jest wyrażeniem (w sensie matematycznym); wykonanie programu oznacza obliczenie wartości tego wyrażenia.1 Biorąc pod uwagę powyższą notację, uznając, że wynik pracy

1 Użycie terminu „obliczenia” nie oznacza, że program może operować wyłącznie na liczbach; Wynikiem obliczeń mogą być ciągi znaków, listy i ogólnie dowolne struktury danych dozwolone w języku.

program imperatywny jest całkowicie i jednoznacznie określony przez jego dane wejściowe, możemy powiedzieć, że stan końcowy (lub dowolny stan pośredni) jest jakąś funkcją (w sensie matematycznym) stanu początkowego, tj. σ0 = f(σ). Programowanie funkcjonalne wykorzystuje ten punkt widzenia: program jest wyrażeniem odpowiadającym funkcji f. Funkcjonalne języki programowania wspierają konstrukcję takich wyrażeń, zapewniam szeroki wybór odpowiednie konstrukcje językowe.

Porównując funkcjonalne i imperatywne podejście do programowania, można zauważyć następujące właściwości programów funkcjonalnych:

Programy funkcjonalne nie używają zmiennych w tym sensie, w jakim słowo to jest używane w programowaniu imperatywnym. W szczególności programy funkcjonalne nie używają operatora przypisania.

Konsekwencją poprzedniego punktu jest to, że w programach funkcjonalnych nie ma pętli.

Wykonanie sekwencji poleceń w programie funkcjonalnym nie ma sensu, ponieważ jedno polecenie nie może mieć wpływu na wykonanie następnego.

Programy funkcjonalne wykorzystują funkcje w znacznie bardziej skomplikowany sposób. Funkcje można przekazywać do innych funkcji jako argumenty i w rezultacie zwracać, a nawet ogólnie przeprowadzać obliczenia, których wynikiem jest funkcja.

Zamiast pętli programy funkcjonalne powszechnie korzystają z funkcji rekurencyjnych.

Na pierwszy rzut oka funkcjonalne podejście do programowania może wydawać się dziwne, niezwykłe i mało przydatne, należy jednak wziąć pod uwagę następujące kwestie.

Po pierwsze, imperatywny styl w programowaniu nie jest koniecznością zakodowaną na stałe. Wiele cech imperatywnych języków programowania wynika z abstrakcji ze szczegółów implementacji komputerów niskiego poziomu, od kodu maszynowego, przez języki asemblera, po języki takie jak Fortran i tak dalej. Nie ma jednak powodu sądzić, że takie języki odzwierciedlają najbardziej naturalny język

sposób, w jaki człowiek może przekazać maszynie swoje zamiary. Być może bardziej poprawne podejście jest takie, że języki programowania rodzą się jako abstrakcyjne systemy do pisania algorytmów, a następnie są tłumaczone na imperatywny język komputerowy.

Co więcej, podejście funkcjonalne ma wiele zalet w porównaniu z podejściem imperatywnym. Przede wszystkim programy funkcjonalne bardziej bezpośrednio odpowiadają obiektom matematycznym, a zatem pozwalają na rygorystyczne rozumowanie. Ustaw wartość programu imperatywnego, tj. funkcja, którą realizuje, może być dość trudna do oceny. Natomiast znaczenie programu funkcyjnego można wywnioskować niemal bezpośrednio.

Rozważmy na przykład następny program w Haskellu:

silnia n = jeśli n == 0 to 1 inaczej n * silnia (n - 1)

Niemal natychmiast widać, że program ten odpowiada następującej funkcji częściowej:

f(n) = n! n ≥ 0

(Tutaj symbol oznacza, że funkcja jest niezdefiniowana, ponieważ program nie kończy się w przypadku ujemnych wartości argumentu.) Jednak w przypadku programu C ta zgodność nie jest oczywista:

int x = 1; podczas gdy (n > 0)

x = x * n; n = n - 1;

Należy również zwrócić uwagę na użycie terminu „funkcja” w językach takich jak C, Java itp. W sensie matematycznym „funkcje” języka C nie są funkcjami, ponieważ:

Ich znaczenie może zależeć od czegoś więcej niż tylko argumentów;

Efekt ich wdrożenia może być różnyskutki uboczne(na przykład zmiana wartości zmiennych globalnych)

Dwa wywołania tej samej funkcji z tymi samymi argumentami mogą dać różne wyniki.

Jednocześnie funkcje w programach funkcjonalnych są rzeczywiście funkcjami w takim sensie, w jakim są rozumiane w matematyce. W związku z tym powyższe uwagi ich nie dotyczą. Wynika z tego, że ocena dowolnego wyrażenia nie może mieć żadnych skutków ubocznych, dlatego też kolejność oceniania jego podwyrażeń nie ma wpływu na wynik. W ten sposób programy funkcjonalne można łatwo zrównoleglić, ponieważ poszczególne składniki wyrażeń można oceniać jednocześnie.

2 Podstawy rachunku lambda

Tak jak teoria maszyn Turinga jest podstawą imperatywnych języków programowania, tak rachunek lambda służy jako podstawa i matematyczny „fundament”, na którym opierają się wszystkie funkcjonalne języki programowania.

Rachunek lambda został wynaleziony na początku lat trzydziestych XX wieku przez logika A. Churcha, który miał nadzieję wykorzystać go jako formalizm uzasadniający matematykę. Wkrótce odkryto problemy, które uniemożliwiły wykorzystanie go w tym charakterze (obecnie istnieją podstawy, aby sądzić, że nie jest to do końca prawdą), a rachunek lambda pozostał jednym ze sposobów sformalizowania koncepcji algorytmu.

Obecnie rachunek lambda jest główną tego typu formalizacją stosowaną w badaniach związanych z językami programowania. Prawdopodobnie wynika to z następujących czynników:

Jest to jedyna formalizacja, która choć wiąże się z pewnymi niedogodnościami, faktycznie może być bezpośrednio wykorzystana do pisania programów.

Rachunek lambda zapewnia prosty i naturalny model dla ważnych pojęć, takich jak rekurencja i środowiska zagnieżdżone.

Większość konstrukcji w tradycyjnych językach programowania można mniej więcej bezpośrednio odwzorować na konstrukcję rachunek lambda.

Języki funkcjonalne są w zasadzie wygodną formą notacji składniowej dla konstrukcji różnych wariantów rachunku lambda. Niektóre współczesne języki (Haskell, Clean) mają

100% zgodność jego semantyki z semantyką implikowanych konstrukcji rachunku lambda.

W matematyce, gdy trzeba mówić o funkcji, zwyczajowo nadaje się tej funkcji nazwę, a następnie jej używa, jak na przykład w następującym stwierdzeniu:

Niech f: R → R będzie określone następującym wyrażeniem:

	(x2 grzech(1/x2 ),

Wtedy f0 (x) nie jest całkowalne na przedziale .

Wiele języków programowania pozwala także na definiowanie funkcji jedynie poprzez nadanie im niektórych nazw. Na przykład w języku C funkcja zawsze musi mieć nazwę. Wydaje się to naturalne, ale ponieważ funkcje są używane wszędzie w programowaniu funkcjonalnym, takie podejście może prowadzić do poważnych problemów. Wyobraź sobie, że zawsze musimy operować wyrażeniami arytmetycznymi w podobnym stylu:

Niech x = 2 i y = 4. Wtedy xx = y.

Notacja lambda umożliwia definiowanie funkcji z taką samą łatwością, jak inne obiekty matematyczne. Wyrażenie lambda nazwiemy konstrukcję formularza

gdzie E jest pewnym wyrażeniem, prawdopodobnie przy użyciu zmiennej x.

Przykład. λx.x2 jest funkcją podnoszącą do kwadratu swój argument.

Zastosowanie notacji lambda pozwala wyraźnie rozdzielić przypadki, gdy przez wyrażenie postaci f(x) rozumiemy samą funkcję f i jej wartość w punkcie x. Ponadto notacja lambda pozwala na sformalizowanie niemal wszystkich typów notacji matematycznej. Jeśli zaczniesz od stałych i zmiennych i zbudujesz wyrażenia używając wyłącznie wyrażeń lambda i aplikacji funkcji na argumentach, możesz sobie wyobrazić bardzo złożone wyrażenia matematyczne.

Zastosowanie funkcji f do argumentu x będziemy oznaczać jako f x, czyli inaczej niż jest to przyjęte w matematyce, nie będziemy używać nawiasów2. Z powodów, które staną się jasne później, założymy, że zastosowanie funkcji do argumentu pozostaje łączne, tj. f x y

2 Należy pamiętać, że w matematyce wyrażenia takie jak sin x zapisuje się bez nawiasów.

oznacza (f(x))(y). Jako skrót wyrażeń w postaci λx.λy.E zastosujemy zapis λx y.E (podobnie dla większej liczby argumentów). Założymy też, że „zakres” wyrażenia lambda rozciąga się maksymalnie w prawo, czyli np. λx.x y oznacza λx.(x y), a nie (λx.x)y.

Na pierwszy rzut oka wydaje się, że należy wprowadzić specjalny zapis dla funkcji kilku argumentów. Istnieje jednak operacja curry 3, która umożliwia zapisanie takich funkcji w zwykłej notacji lambda. Chodzi o to, aby używać wyrażeń w postaci λx y.x + y. Takie wyrażenie można uznać za funkcję R → (R → R), tj. jeśli zostanie zastosowany do jednego argumentu, wynikiem jest funkcja, która następnie przyjmuje inny argument. Zatem:

(λx y.x + y) 1 2 = (λy.1 + y) 2 = 1 + 2.

Zmienne w wyrażeniach lambda mogą być wolne lub powiązane. W wyrażeniu w postaci x2 + x zmienna x jest wolna; jego wartość zależy od wartości zmiennej x i w ogóle nie może być

Jeśli zmienisz zapis j, znaczenie wyrażenia nie ulegnie zmianie.

Należy rozumieć, że w dowolnym podwyrażeniu zmienna może być dowolna (jak w wyrażeniu pod całką), ale w całym wyrażeniu jest związana pewnym zmienna operacja wiązania, takie jak operacja sumowania. Wywoływana jest część wyrażenia znajdująca się „wewnątrz” operacji wiązania zakres zmienny.

W rachunku lambda wyrażenia λx.E[x] i λy.E[y] uważa się za równoważne (nazywa się to α-równoważnością, a proces konwersji pomiędzy takimi parami nazywa się α-transformacją). Oczywiście należy narzucić warunek, że y nie jest zmienną wolną w E[x].

3 od nazwiska słynnego logika Haskell Curry, od którego pochodzi nazwa języka programowania Haskell

3 Rachunek lambda jako system formalny

Rachunek lambda opiera się na formalnym zapisie członu lambda, składającego się ze zmiennych i pewnego ustalonego zestawu stałych, przy użyciu operacji stosowania funkcji i abstrakcji lambda. Oznacza to, że wszystkie wyrażenia lambda można podzielić na cztery kategorie:

1. Zmienne: są oznaczone dowolnymi ciągami znaków składającymi się z liter i cyfr.

2. Stałe: również oznaczane łańcuchami; różnicę określimy od zmiennych z kontekstu.

3. Kombinacje: , tj. zastosowanie funkcji S do argumentu T; oraz S i T mogą być dowolnymi terminami lambda. Kombinacja jest zapisana jako ST.

4. Abstrakcje dowolnego członu lambda S względem zmiennej x, oznaczonej jako λx.S.

Zatem termin lambda jest zdefiniowany rekurencyjnie, a jego gramatykę można zdefiniować jako następującą postać Backusa-Naura:

Exp = Var| Stała| Eksp. Eksp.| λVar. Do potęgi

Zgodnie z tą gramatyką terminy lambda są reprezentowane jako drzewa składniowe, a nie jako sekwencje znaków. Wynika z tego, że ustalenia dotyczące asocjatywności operacji stosowania funkcji, równoważności wyrażeń postaci λx y.S i λx.λy.S, niejednoznaczności w nazwach stałych i zmiennych wynikają jedynie z konieczności przedstawienia wyrazów lambda w postaci formie wygodnej dla człowieka i nie stanowiącej części systemu formalnego.

3.1 Zmienne swobodne i powiązane

W W tej sekcji formalizujemy podaną wcześniej intuicyjną koncepcję zmiennych wolnych i związanych. Dużo darmowych

zmienne F V (S) człon lambda S można zdefiniować rekurencyjnie w następujący sposób:

Podobnie zbiór powiązanych zmiennych BV (S) definiuje się za pomocą następujących wzorów:

BV(x) =

BV(c) =

BV (S T) = BV (S) BV (T)

BV(λx.S) = BV(S)(x)

Tutaj zakłada się, że c jest pewną stałą.

Przykład. Dla wyrazu S = (λx y.x) (λx.z x) można wykazać, że F V (S) = (z) i

BV(S) = (x, y).

3.2 Zastępstwa

Intuicyjnie zastosowanie terminu λx.S jako funkcji do argumentu T daje w wyniku termin S, w którym wszystkie wolne wystąpienia x są zastępowane przez T. O dziwo, sformalizowanie tej intuicji nie jest łatwe.

Operację podstawienia wyrazu S w miejsce zmiennej x w innym członie T będziemy oznaczać jako T. Podobnie jak w przypadku definicji zmiennych wolnych i związanych, zasady podstawienia można również zdefiniować rekurencyjnie. Trudność polega na tym, że trzeba narzucić dodatkowe ograniczenia, co pozwala uniknąć konfliktów w nazwach zmiennych.

3.3 Konwersja

Rachunek lambda opiera się na trzech operacjach konwersji, które pozwalają na przejście z jednego wyrazu na inny, mu równoważny. Zgodnie z ustaloną tradycją konwersje te oznaczane są greckimi literami α, β i η. Są one zdefiniowane w następujący sposób:

α-konwersja: λx.S − → λy.S pod warunkiem, że y / F V (S).

Na przykład λu.u v − → λw.w u.

β-konwersja: (λx.S) T − → S.

Konwersja β jest dla nas najważniejsza, ponieważ odpowiada obliczeniu wartości funkcji argumentu. Konwersja α jest mechanizmem pomocniczym do zmiany nazw powiązanych zmiennych, a konwersja η jest interesująca głównie przy rozpatrywaniu rachunku lambda z logicznego, a nie programistycznego punktu widzenia.

3.4 Równość składników lambda

Korzystając z wprowadzonych reguł konwersji, możemy formalnie zdefiniować pojęcie równości składników lambda. Dwa wyrazy są równe, jeśli można przejść z jednego z nich do drugiego za pomocą skończonej sekwencji konwersji. Zdefiniujmy pojęcie równości za pomocą następujących wyrażeń, w których linie poziome należy rozumieć w ten sposób, że „jeżeli stwierdzenie nad linią jest spełnione, to stwierdzenie jest również prawdziwe

pod tym":

Należy odróżnić pojęcie równości definiowane tymi wzorami od pojęcia równoważności syntaktycznej, które będziemy oznaczać specjalnym symbolem ≡. Na przykład λx.x 6≡λy.y, ale λx.x = λy.y. Często możliwe jest rozważenie równoważności składniowej terminów aż do konwersji α. Oznaczymy taką równoważność symbolem ≡α. Relację tę definiuje się w taki sam sposób, jak równość składników lambda, z tym wyjątkiem, że ze wszystkich konwersji dozwolone są tylko konwersje α. Zatem λx.x ≡α λy.y.

3.5 Rozszerzalność

Konwersja η w rachunku lambda wyraża zasadę ekstensjonalność. W ogólnym sensie filozoficznym mówi się, że dwie właściwości są równoważne ekstensywnie, jeśli należą do dokładnie tych samych obiektów. Na przykład w matematyce przyjmuje się ekstensjonalny pogląd na zbiory, tj. dwa zbiory uważa się za takie same, jeśli zawierają te same elementy. Podobnie mówimy, że dwie funkcje są równe, jeśli mają tę samą dziedzinę i dla dowolnych wartości argumentu w tej dziedzinie obliczają ten sam wynik.