Пример за функционално програмиране. Недостатъци на функционалното програмиране

Езиците, подобни на функционалните, използват по-малко строга концепция. Една функция в математиката не може да промени средата, която я извиква и да запомни резултатите от нейната работа, а само предоставя резултата от изчислението на функцията. Използване на програмиране математическа концепцияфункции причинява някои трудности, следователно функционалните езици в една или друга степен също предоставят задължителни възможности, което влошава дизайна на програмата (например възможността за безболезнени по-нататъшни промени). Допълнителна разлика от императивните езици за програмиране е декларативният характер на описанията на функциите. Текстове на програми на функционални езици за програмиране описвам„как да се реши проблем“, но не предписвампоследователност от действия за решение. Първият проектиран функционален език беше Lisp. Вариант на този език се използва широко в системата компютърно проектиране AutoLISP

Следното обикновено се счита за основните свойства на функционалните езици за програмиране:

краткост и простота;
силно писане;
модулност;
функциите са изчислителни обекти;
отложени (мързеливи) изчисления.

Някои функционални езици за програмиране

Миранда (какво семейство?)

Връзки

http://roman-dushkin.narod.ru/fp.html - Курс от лекции по функционално програмиране, изнасян в MEPhI от 2001 г.

Фондация Уикимедия. 2010 г.

Вижте какво е „функционален език за програмиране“ в други речници:

Език за програмиране, който ви позволява да посочите програма като набор от функционални дефиниции. Във функционалните езици за програмиране: функциите обменят данни помежду си, без да използват междинни променливи и присвоявания;... ... Финансов речник

функционален език- Език за програмиране, в който действията върху данните се изразяват като извиквания на функционални процедури. [GOST 19781 90] Предмети на поддръжка. системи за обработка информация софтуер EN функционален език... Ръководство за технически преводач

Ruby Семантика: мулти-парадигма Тип на изпълнение: интерпретатор Появява се през: 1995 г. Автор(и): Юкихиро Мацумото Последна версия: 1.9.1 ... Уикипедия

Функционален език- 37. Функционален език Функционален език Език за програмиране, в който действията върху данните се изразяват под формата на извиквания на функционални процедури Източник: GOST 19781 90: Софтуерна поддръжка за системи за обработка на информация. Условия и ... ... Речник-справочник на термините на нормативната и техническата документация

Erlang Файл:Erlang logo.png Семантика: мулти-парадигма: състезателно, функционално програмиране Появява се през: 1987 г. Автор(и): Типизиране на данни: строго, динамично Основни реализации: E ... Wikipedia

Семантика на схемата: функционален Тип на изпълнение: интерпретатор или компилатор Появява се през: 1970 г. Автор(и): Гай Стийл и Джералд Съсман Въвеждане на данни ... Wikipedia

Този термин има и други значения, вижте Миранда. Miranda е функционален език за програмиране, създаден през 1985 г. от Дейвид Търнър като стандартен функционален език. Има строга система от полиморфни типове, ... ... Wikipedia

Hope е функционален език за програмиране, разработен в началото на 1980 г.; е предшественик на езиците Miranda и Haskell. Списание Byte, август 1985 г., за първи път публикува ръководство за езика Hope. Пример за изчислителна програма... ... Wikipedia

Този термин има и други значения, вижте SASL. SASL е напълно функционален език за програмиране, разработен от Дейвид Търнър в университета Сейнт Андрюс през 1972 г., базиран на приложното подмножество на ISWIM. През 1976 г.... ... Уикипедия

Този термин има и други значения, вижте Scala. Езиков клас Scala: Мултипарадигма: функц... Уикипедия

Книги

Програмиране в Clojure. Практиката за използване на Lisp в света на Java, Emerick Ch., Carper B., Grand K.. Защо много хора избират Clojure? Това е функционален език за програмиране, който не само ви позволява да използвате Java библиотеки, услуги и други JVM ресурси, но също така се конкурира с...

String reverse(String arg) ( if(arg.length == 0) ( return arg; ) else ( return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1); ) )
Тази функция е доста бавна, защото се извиква многократно. Тук може да има изтичане на памет, защото временните обекти се създават много пъти. Но това е функционален стил. Може да ви се стори странно как хората могат да програмират по този начин. Е, тъкмо щях да ти кажа.

Ползи от функционалното програмиране

Вероятно си мислите, че не мога да направя случай, за да оправдая чудовищната функция по-горе. Когато за първи път започнах да уча функционално програмиране, и аз мислех така. Сгреших. Има много добри аргументи за този стил. Някои от тях са субективни. Например програмистите твърдят, че функционални програмипо-лесно за разбиране. Няма да излагам такива аргументи, защото всеки знае, че лекотата на разбиране е много субективно нещо. За мое щастие все още има много обективни аргументи.

Единично тестване

Тъй като всеки символ в FP е неизменен, функциите нямат странични ефекти. Не можете да промените стойностите на променливите и функцията не може да промени стойност извън нейния обхват и по този начин да повлияе на други функции (както може да се случи с полета на клас или глобални променливи). Това означава, че единственият резултат от изпълнението на функцията е върнатата стойност. И единственото нещо, което може да повлияе на върнатата стойност, са аргументите, предадени на функцията.

Ето я, синята мечта на модулните тестери. Можете да тествате всяка функция в програма, като използвате само необходимите аргументи. Няма нужда да извиквате функции в правилния ред или да пресъздавате правилното външно състояние. Всичко, което трябва да направите, е да подадете аргументи, които съответстват на крайните случаи. Ако всички функции във вашата програма преминат единични тестове, тогава можете да сте много по-уверени в качеството на вашия софтуер, отколкото в случая с императивните езици за програмиране. В Java или C++ проверката на върнатата стойност не е достатъчна – функцията може да промени външното състояние, което също подлежи на проверка. Във ФП такъв проблем няма.

Отстраняване на грешки

Ако една функционална програма не се държи както очаквате, тогава отстраняването на грешки е лесно. Винаги можете да възпроизведете проблема, тъй като грешката във функцията не зависи от външен код, който е бил изпълнен преди това. В императивна програма грешката се появява само за известно време. Ще трябва да преминете през редица стъпки без грешки поради факта, че работата на функцията зависи от външното състояние и страничните ефекти на други функции. При FP ситуацията е много по-проста - ако върнатата стойност е неправилна, тогава тя винаги ще бъде неправилна, без значение какви части от кода са били изпълнени преди това.

След като възпроизведете грешката, намирането на източника й е тривиална задача. Дори е приятно. Веднага след като спрете програмата, ще имате целия стек от повиквания пред вас. Можете да видите аргументите за всяко извикване на функция, точно както в императивен език. С тази разлика, че в една императивна програма това не е достатъчно, защото функциите зависят от стойностите на полета, глобални променливи и състояния на други класове. Една функция в FP зависи само от своите аргументи и тази информация е точно пред очите ви! Нещо повече, в една императивна програма проверката на върнатата стойност не е достатъчна, за да се каже дали дадена част от кода се държи правилно. Ще трябва да преследвате десетки обекти извън функцията, за да сте сигурни, че всичко работи правилно. Във функционалното програмиране всичко, което трябва да направите, е да погледнете върнатата стойност!

Докато преминавате през стека, обръщате внимание на предадените аргументи и върнатите стойности. След като върнатата стойност се отклони от нормата, задълбочавате във функцията и продължавате напред. Това се повтаря няколко пъти, докато откриете източника на грешката!

Многопоточност

Функционалната програма е незабавно готова за паралелизиране без никакви промени. Не е нужно да се притеснявате за задънени блокажи или условия на състезание, защото нямате нужда от ключалки! Нито една част от данните във функционална програма не се променя два пъти от една и съща нишка или от различни. Това означава, че можете лесно да добавяте нишки към вашата програма, без изобщо да се притеснявате за проблемите, присъщи на императивните езици.

Ако това е така, тогава защо функционалните езици за програмиране се използват толкова рядко в многонишкови приложения? Всъщност по-често, отколкото си мислите. Компанията Ericssonразработи функционален език, наречен Erlang, за използване на устойчиви на грешки и мащабируеми телекомуникационни комутатори. Мнозина отбелязаха предимствата на Erlang и започнаха да го използват. Говорим за системи за телекомуникации и контрол на трафика, които не са толкова лесни за мащабиране, колкото типичните системи, разработени на Уолстрийт. Всъщност системите, написани на Erlang, не са толкова мащабируеми и надеждни, колкото системите на Java. Системите Erlang са просто супер надеждни.

Историята на многопоточността не свършва дотук. Ако пишете по същество еднонишково приложение, компилаторът все още може да оптимизира функционалната програма за използване на множество процесори. Нека да разгледаме следващата част от кода.

Компилаторът на функционален език може да анализира кода, да класифицира функциите, които произвеждат редове s1 и s2 като отнемащи време функции, и да ги изпълнява паралелно. Това е невъзможно да се направи в императивен език, тъй като всяка функция може да промени външното състояние и кодът непосредствено след извикването може да зависи от нея. Във FP автоматичният анализ на функциите и търсенето на подходящи кандидати за паралелизиране е тривиална задача, като автоматичното вграждане! В този смисъл функционалният стил на програмиране е устойчив на бъдещето. Разработчиците на хардуер вече не могат да накарат процесора да работи по-бързо. Вместо това те увеличават броя на ядрата и претендират за четирикратно увеличение на скоростта на многонишкови изчисления. Разбира се, те забравят да кажат навреме, че вашият нов процесорще покаже увеличение само в програмите, разработени, като се вземе предвид паралелизацията. Има много малко такива сред императивния софтуер. Но 100% от функционалните програми са готови за многопоточност от кутията.

Горещо внедряване

В старите времена трябваше да рестартирате компютъра си, за да инсталирате актуализации на Windows. Много пъти. След инсталиране на нова версия на мултимедийния плейър. Имаше значителни промени в Windows XP, но ситуацията все още е далеч от идеалната (днес стартирах Актуализация на Windowsна работа и сега досадното напомняне няма да ме остави на мира, докато не рестартирам). Unix системите имаха по-добър модел за актуализиране. За да инсталирам актуализации, трябваше да спра някои компоненти, но не и цялата ОС. Въпреки че ситуацията изглежда по-добре, тя все още не е приемлива за голям клас сървърни приложения. Телекомуникационните системи трябва да бъдат включени 100% от времето, защото ако актуализация попречи на човек да се обади на линейка, животите могат да бъдат загубени. Фирмите от Wall Street също не искат да затварят сървъри през уикенда, за да инсталират актуализации.

В идеалния случай трябва да актуализирате всички необходими секции на кода, без да спирате системата по принцип. В императивния свят това е невъзможно [прев. в Smalltalk е много възможно]. Представете си, че разтоварвате Java клас в движение и презареждате нова версия. Ако направим това, тогава всички екземпляри на класа ще станат неработещи, защото състоянието, което съхраняват, ще бъде загубено. Ще трябва да напишем труден код за контрол на версиите. Ще трябва да сериализираме всички създадени екземпляри на класа, след това да ги унищожим, да създадем екземпляри на нов клас, да се опитаме да заредим сериализираните данни с надеждата, че миграцията ще мине гладко и новите екземпляри ще бъдат валидни. И освен това кодът за миграция трябва да се пише ръчно всеки път. И кодът за миграция трябва да запазва връзките между обектите. На теория всичко е наред, но на практика никога няма да работи.

Във функционална програма цялото състояние се съхранява в стека като аргументи на функцията. Това прави горещото внедряване много по-лесно! По същество всичко, което трябва да направите, е да изчислите разликата между кода на производствения сървър и новата версия и да инсталирате промените в кода. Останалото ще бъде направено автоматично от езиковите инструменти! Ако смятате, че това е научна фантастика, помислете два пъти. Инженерите, които работят с Erlang, обновяват своите системи от години, без да спират работата си.

Машинно подпомагани доказателства и оптимизации

Друго интересно свойство на функционалните езици за програмиране е, че те могат да бъдат научени от математическа гледна точка. Тъй като функционалният език е реализация на формална система, всички математически операции, използвани на хартия, могат да бъдат приложени към функционални програми. Компилаторът, например, може да преобразува част от код в еквивалентна, но по-ефективна част, като същевременно математически обоснове тяхната еквивалентност. Релационни бази данниданните са били подложени на такива оптимизации от години. Нищо не ви пречи да използвате подобни техники в обикновените програми.

Освен това можете да използвате математика, за да докажете коректността на секции от вашите програми. Ако желаете, можете да напишете инструменти, които анализират вашия код и автоматично да създават Unit тестове за крайни случаи! Тази функционалност е безценна за твърди системи. При разработването на системи за мониторинг на пейсмейкър или системи за управление на въздушното движение, такива инструменти са задължителни. Ако вашите разработки не са в критичната зона важни приложения, след това инструментите автоматична проверкапак ще ви даде огромно предимство пред вашите конкуренти.

Функции от по-висок ред

Не забравяйте, че когато говорих за предимствата на FP, отбелязах, че „всичко изглежда хубаво, но е безполезно, ако трябва да пиша на тромав език, на който всичко е окончателно“. Това беше погрешно схващане. Използването на final навсякъде изглежда тромаво само в императивни езици за програмиране като Java. Функционалните езици за програмиране работят с други видове абстракции, такива, които ви карат да забравите, че някога сте харесвали промяната на променливи. Един такъв инструмент са функциите от по-висок ред.

В FP една функция не е същата като функция в Java или C. Това е надмножество - те могат да правят същото като функциите на Java и дори повече. Да кажем, че имаме функция в C:

Int add(int i, int j) ( return i + j; )
Във FP това не е същото като обикновена C функция. Нека разширим нашия Java компилатор, за да поддържа тази нотация. Компилаторът трябва да превърне декларацията на функцията в следния код на Java (не забравяйте, че навсякъде има имплицитен финал):

Клас add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Символът за добавяне всъщност не е функция. Това е малък клас с един метод. Сега можем да предадем add като аргумент на други функции. Можем да го запишем в друг символ. Можем да създадем екземпляри на add_function_t по време на изпълнение и те ще бъдат унищожени от събирача на отпадъци, ако вече не са необходими. Функциите стават основни обекти, като числа и низове. Функциите, които оперират с функции (приемат ги като аргументи), се наричат функции от по-висок ред. Нека това не ви плаши. Концепцията за функции от по-висок ред е почти същата като концепцията за Java класове, които работят един върху друг (можем да предаваме класове на други класове). Можем да ги наречем „класове от по-висок порядък“, но никой не се занимава с това, защото зад Java няма строга академична общност.

Как и кога трябва да използвате функции от по-висок ред? Радвам се, че попита. Вие пишете програмата си като едно голямо монолитно парче код, без да се притеснявате за йерархията на класовете. Ако видите, че част от кода се повтаря на различни места, вие го премествате в отделна функция (за щастие, училищата все още учат как да направите това). Ако забележите, че част от логиката във вашата функция трябва да се държи различно в някои ситуации, тогава създавате функция от по-висок ред. объркани? Ето един реален пример от моята работа.

Да приемем, че имаме част от Java код, който получава съобщение, трансформира го по различни начини и го предава на друг сървър.

Void handleMessage(Message msg) ( // ... msg.setClientCode("ABCD_123"); // ... sendMessage(msg); ) // ... )
Сега си представете, че системата се е променила и сега трябва да разпространявате съобщения между два сървъра вместо един. Всичко остава непроменено с изключение на клиентския код - вторият сървър иска да получи този код в различен формат. Как можем да се справим с тази ситуация? Можем да проверим къде трябва да отиде съобщението и въз основа на това да зададем правилния клиентски код. Например така:

Клас MessageHandler ( void handleMessage(Message msg) ( // ... if(msg.getDestination().equals("server1") ( msg.setClientCode("ABCD_123"); ) else ( msg.setClientCode("123_ABC") ; ) // ... sendMessage(msg); ) // ... )
Но този подход не се мащабира добре. С добавянето на нови сървъри функцията ще расте линейно и извършването на промени ще се превърне в кошмар. Обектно-ориентираният подход се състои от изолиране на общ суперклас MessageHandler и подкласиране на логиката за дефиниране на клиентския код:

Абстрактен клас MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) абстрактен низ getClientCode(); // ... ) клас MessageHandlerOne разширява MessageHandler ( String getClientCode() ( return "ABCD_123"; ) ) клас MessageHandlerTwo разширява MessageHandler ( String getClientCode() ( return "123_ABCD"; ) )
Сега за всеки сървър можем да създадем екземпляр от съответния клас. Добавянето на нови сървъри става по-удобно. Но за това дребни паритвърде много текст. Трябваше да създам два нови типа само за да добавя поддръжка за различен клиентски код! Сега нека направим същото на нашия език с поддръжка за функции от по-висок ред:

Клас MessageHandler ( void handleMessage(Message msg, Function getClientCode) ( // ... Message msg1 = msg.setClientCode(getClientCode()); // ... sendMessage(msg1); ) // ... ) String getClientCodeOne( ) ( return "ABCD_123"; ) String getClientCodeTwo() ( return "123_ABCD"; ) MessageHandler handler = new MessageHandler(); handler.handleMessage(someMsg, getClientCodeOne);
Не създадохме нови типове или усложнихме йерархията на класовете. Ние просто предадохме функцията като параметър. Постигнахме същия ефект като в обектно-ориентирания аналог, но с някои предимства. Не сме се обвързали с никаква йерархия на класове: можем да предадем всякакви други функции на времето за изпълнение и да ги променим по всяко време, като същевременно поддържаме високо ниво на модулност с по-малко код. По същество компилаторът създаде обектно-ориентирано лепило за нас! В същото време всички други предимства на FP се запазват. Разбира се, абстракциите, предлагани от функционалните езици, не свършват дотук. Функциите от по-висок ред са само началото

Къри

Повечето хора, които срещам, са чели книгата Design Patterns от Gang of Four. Всеки уважаващ себе си програмист ще каже, че книгата не е обвързана с конкретен език за програмиране и моделите са приложими за разработката на софтуер като цяло. Това е благородно твърдение. Но за съжаление е далеч от истината.

Функционалните езици са невероятно изразителни. В един функционален език няма да имате нужда от шаблони за проектиране, защото езикът е на толкова високо ниво, че можете лесно да започнете да програмирате в концепции, които елиминират всички познати модели за програмиране. Един от тези шаблони е Адаптерът (по какво се различава от Фасадата? Изглежда, че някой трябваше да подпечата още страници, за да изпълни условията на договора). Този модел се оказва ненужен, ако езикът поддържа къри.

Моделът Adapter най-често се прилага към "стандартната" единица за абстракция в Java - класа. Във функционалните езици моделът се прилага към функции. Моделът взема интерфейс и го трансформира в друг интерфейс според определени изисквания. Ето пример за модела на адаптера:

Int pow(int i, int j); int square(int i) ( return pow(i, 2); )
Този код адаптира интерфейса на функция, която повишава число на произволна степен, към интерфейса на функция, която повдига число на квадрат. В академичните среди тази проста техника се нарича къри (на името на логика Хаскел Къри, който извърши серия от математически трикове, за да формализира всичко). Тъй като функциите се използват навсякъде като аргументи във FP, къри се използва много често, за да доведе функции до интерфейса, необходим на едно или друго място. Тъй като интерфейсът на функцията е нейните аргументи, къри се използва за намаляване на броя на аргументите (както в примера по-горе).

Този инструмент е вграден във функционални езици. Не е необходимо ръчно да създавате функция, която обвива оригинала. Един функционален език ще направи всичко вместо вас. Както обикновено, нека разширим нашия език, като добавим къри.

Square = int pow(int i, 2);
С този ред автоматично създаваме функция за повдигане на квадрат с един аргумент. Новата функция ще извика функцията pow, замествайки 2 като втори аргумент. От гледна точка на Java това би изглеждало така:

Клас square_function_t ( int square(int i) ( return pow(i, 2); ) ) square_function_t square = new square_function_t();
Както можете да видите, ние просто написахме обвивка върху оригиналната функция. Във FP кърирането е просто прост и удобен начин за създаване на обвивки. Вие се фокусирате върху задачата, а компилаторът пише необходимия код вместо вас! Много е просто и се случва всеки път, когато искате да използвате шаблона на адаптера (обвивката).

Мързелива оценка

Мързеливата (или отложена) оценка е интересна техника, която става възможна, след като разберете функционалната философия. Вече видяхме следната част от кода, когато говорим за многопоточност:

Низ s1 = somewhatLongOperation1(); Низ s2 = somewhatLongOperation2(); Низ s3 = конкатенация (s1, s2);
В императивните езици за програмиране редът на изчисление не повдига никакви въпроси. Тъй като всяка функция може да повлияе или да зависи от външното състояние, е необходимо да се поддържа ясен ред на извикванията: първо somewhatLongOperation1, след това somewhatLongOperation2 и свързване в края. Но не всичко е толкова просто във функционалните езици.

Както видяхме по-рано, somewhatLongOperation1 и somewhatLongOperation2 могат да се изпълняват едновременно, тъй като е гарантирано, че функциите не засягат или зависят от глобалното състояние. Но какво, ако не искаме да ги изпълним едновременно, трябва ли да ги извикаме последователно? Отговорът е не. Тези изчисления трябва да се изпълняват само ако някоя друга функция зависи от s1 и s2. Дори не е необходимо да ги изпълняваме, докато не се нуждаем от тях вътре в concatenate. Ако вместо concatenate заместим функция, която в зависимост от условието използва един от двата аргумента, тогава вторият аргумент може дори да не бъде изчислен! Haskell е пример за мързелив език за оценка. Haskell не гарантира никакъв ред на повикване (изобщо!), защото Haskell изпълнява код според нуждите.

Мързеливите изчисления имат редица предимства, както и някои недостатъци. В следващия раздел ще обсъдим предимствата и ще обясня как да живеем с недостатъците.

Оптимизация

Мързеливата оценка предоставя огромен потенциал за оптимизации. Мързеливият компилатор гледа на кода по същия начин, по който математикът гледа на алгебричните изрази - той може да отмени неща, да отмени изпълнението на определени части от кода, да промени реда на извикванията за по-голяма ефективност, дори да подреди кода по такъв начин, че да намали броя на грешки, като същевременно се гарантира целостта на програмата. Това е най-голямото предимство на описанието на програма със строги формални примитиви - кодът се подчинява на математическите закони и може да бъде изучаван математически методи.

Абстрахиране на контролни структури

Мързеливите изчисления осигуряват толкова високо ниво на абстракция, че невероятни неща стават възможни. Например, представете си прилагането на следната контролна структура:

Unless(stock.isEuropean()) ( sendToSEC(stock); )
Искаме функцията sendToSEC да се изпълнява само ако акциите не са европейски. Как можете да приложите, освен ако? Без мързелива оценка бихме имали нужда от макро система, но в езици като Haskell това не е необходимо. Можем да декларираме освен като функция!

Void unless(булево условие, List code) ( if(!condition) code; )
Имайте предвид, че кодът няма да бъде изпълнен, ако условие == true. В строги езици това поведение не може да се повтори, защото аргументите ще бъдат оценени преди това, освен ако не бъде извикано.

Безкрайни структури от данни

Мързеливите езици ви позволяват да създавате безкрайни структури от данни, които са много по-трудни за създаване в строги езици. - просто не в Python]. Например, представете си редицата на Фибоначи. Очевидно е, че не можем да изчислим безкраен списък за крайно време и пак да го съхраняваме в паметта. В строги езици като Java, ние просто бихме написали функция, която връща произволен член на последователността. В езици като Haskell можем да се абстрахираме и просто да декларираме безкраен списък от числа на Фибоначи. Тъй като езикът е мързелив, ще бъдат изчислени само необходимите части от списъка, които действително се използват в програмата. Това ви позволява да се абстрахирате от голямо числопроблеми и погледнете на тях с повече високо ниво(например, можете да използвате функции за обработка на списъци върху безкрайни последователности).

недостатъци

Със сигурност безплатно сиренеслучва се само в капан за мишки. Мързеливите изчисления идват с редица недостатъци. Това са главно недостатъци от мързел. В действителност много често е необходим директен ред на изчисления. Вземете например следния код:

На мързелив език, никой не гарантира, че първият ред ще бъде изпълнен преди втория! Това означава, че не можем да правим I/O, не можем да използваме собствените функции нормално (в края на краищата, те трябва да бъдат извикани в определен ред, за да се отчетат техните странични ефекти) и не можем да взаимодействаме с външния свят! Ако въведем механизъм за нареждане на изпълнението на кода, ще загубим предимството на математическата строгост на кода (и тогава ще загубим всички предимства на функционалното програмиране). За щастие не всичко е загубено. Математиците се заеха с работа и измислиха няколко техники, за да гарантират, че инструкциите се изпълняват в правилния ред, без да се губи функционалният дух. Имаме най-доброто от двата свята! Такива техники включват продължения, монади и въвеждане на уникалност. В тази статия ще работим с продължения и ще оставим монадите и недвусмисленото писане за следващия път. Интересно е, че продълженията са много полезно нещо, което се използва не само за задачи строг редизчисления. Ще говорим и за това.

Продължения

Продълженията в програмирането играят същата роля като Шифърът на Да Винчи в човешката история: изненадващо разкритие на най-голямата мистерия на човечеството. Е, може би не точно така, но определено късат кориците, точно както сте се научили да извличате корен от -1 навремето.

Когато разгледахме функциите, научихме само половината истина, защото предположихме, че функцията връща стойност на функцията, която я извиква. В този смисъл продължението е обобщение на функциите. Една функция не трябва да връща контрола на мястото, от което е извикана, но може да се върне на всяко място в програмата. „Продължи“ е параметър, който можем да предадем на функция, за да посочи точка на връщане. Звучи много по-страшно, отколкото е в действителност. Нека да разгледаме следния код:

Int i = add(5, 10); int j = квадрат (i);
Функцията add връща числото 15, което се записва в i на мястото, където е извикана функцията. След това стойността на i се използва при извикване на квадрат. Обърнете внимание, че мързеливият компилатор не може да промени реда на изчисленията, защото вторият ред зависи от резултата от първия. Можем да пренапишем този код, като използваме стил за предаване на продължение (CPS), където add връща стойност на квадратната функция.

Int j = add(5, 10, square);
В този случай add получава допълнителен аргумент - функция, която ще бъде извикана, след като add приключи. И в двата примера j ще бъде равно на 225.

Това е първата техника, която ви позволява да укажете реда, в който се изпълняват два израза. Нека се върнем към нашия I/O пример.

System.out.println("Моля, въведете вашето име: "); System.in.readLine();
Тези два реда са независими един от друг и компилаторът е свободен да промени реда им, както пожелае. Но ако го пренапишем в CPS, по този начин ще добавим необходимата зависимост и компилаторът ще трябва да извършва изчисления едно след друго!

System.out.println("Моля, въведете вашето име: ", System.in.readLine);
В този случай println ще трябва да извика readLine, като му предаде резултата и накрая върне резултата от readLine. В тази форма можем да сме сигурни, че тези функции ще бъдат извикани на свой ред и че readLine изобщо ще бъде извикана (все пак компилаторът очаква да получи резултата от последната операция). В случай на Java println връща void. Но ако се върне някаква абстрактна стойност (която може да служи като аргумент на readLine), това ще реши проблема ни! Разбира се, изграждането на такива вериги от функции значително влошава четливостта на кода, но това може да се реши. Можем да добавим синтактични функции към нашия език, които ще ни позволят да пишем изрази както обикновено, а компилаторът автоматично ще веригира изчисленията. Сега можем да извършваме изчисления във всякакъв ред, без да губим предимствата на FP (включително възможността да изучаваме програмата с помощта на математически методи)! Ако това е объркващо, не забравяйте, че функциите са само екземпляри на клас с един член. Пренапишете нашия пример, така че println и readLine да са екземпляри на класове, това ще ви го направи по-ясно.

Но ползите от продълженията не свършват дотук. Можем да напишем цялата програма с помощта на CPS, така че всяка функция да се извиква с допълнителен параметър, продължение, в което се предава резултатът. По принцип всяка програма може да бъде преведена в CPS, ако всяка функция се третира като специален случай на продължения. Това преобразуване може да се извърши автоматично (всъщност много компилатори го правят).

Веднага щом преобразуваме програмата в CPS форма, става ясно, че всяка инструкция има продължение, функция, на която ще бъде предаден резултатът, което в нормална програма би било точката на повикване. Нека вземем всяка инструкция от последния пример, например add(5,10) . В програма, написана във формата на CPS, е ясно какво ще бъде продължението - това е функцията, която add ще извика след приключване на работата. Но какво ще бъде продължението в случай на програма, която не е CPS? Ние, разбира се, можем да конвертираме програмата в CPS, но необходимо ли е това?

Оказва се, че това не е необходимо. Разгледайте внимателно нашето CPS преобразуване. Ако започнете да пишете компилатор за него, ще откриете, че CPS версията не се нуждае от стек! Функциите никога не връщат нищо, в традиционния смисъл на думата „връщане“, те просто извикват друга функция, замествайки резултата от изчислението. Няма нужда да изпращате аргументи в стека преди всяко извикване и след това да ги връщате обратно. Можем просто да съхраняваме аргументите в някакво фиксирано място в паметта и да използваме jump вместо нормално извикване. Не е нужно да съхраняваме оригиналните аргументи, защото те никога повече няма да са необходими, защото функциите не връщат нищо!

По този начин програмите в стил CPS не се нуждаят от стек, но съдържат допълнителен аргумент под формата на функция, която да бъде извикана. Програмите без CPS стил нямат допълнителен аргумент, но използват стек. Какво се съхранява в стека? Само аргументи и указател към мястото в паметта, където функцията трябва да се върне. Е, познахте ли вече? Стекът съхранява информация за продължения! Указателят към точка за връщане в стека е същият като функцията, която трябва да бъде извикана в CPS програми! За да разберете какво е продължението на add(5,10), просто вземете точката за връщане от стека.

Не беше трудно. Продължение и указател към точка за връщане са наистина едно и също нещо, само че продължението е изрично указано и следователно може да се различава от мястото, където е извикана функцията. Ако си спомняте, че продължението е функция, а функцията на нашия език се компилира в екземпляр на клас, тогава ще разберете, че указател към точка за връщане в стека и указател към продължение всъщност са едно и също нещо , защото нашата функция (като екземпляр на клас) е просто указател. Това означава, че по всяко време във вашата програма можете да поискате текущото продължение (по същество информация от стека).

Добре, сега разбираме какво е текущото продължение. Какво означава? Ако вземем текущото продължение и го запишем някъде, по този начин ще запазим Сегашно състояниепрограма - да я замразим. Това е подобно на режима на хибернация на ОС. Обектът за продължение съхранява информацията, необходима за възобновяване на изпълнението на програмата от точката, в която обектът за продължение е поискан. операционна системаправи това с вашите програми през цялото време, когато превключва контекст между нишки. Единствената разлика е, че всичко е под контрола на ОС. Ако поискате обект за продължение (в Scheme това става чрез извикване на функцията call-with-current-continuation), тогава ще получите обект с текущото продължение - стека (или в случая на CPS, следващата функция за извикване ). Можете да запишете този обект в променлива (или дори на диск). Ако решите да "рестартирате" програмата с това продължение, тогава състоянието на вашата програма се "трансформира" до състоянието в момента, в който е бил взет обектът за продължение. Това е същото като превключване към спряна нишка или събуждане на операционната система след хибернация. С изключение на това, че можете да правите това много пъти подред. След като операционната система се събуди, информацията за хибернация се унищожава. Ако това не беше направено, тогава би било възможно да се възстанови състоянието на ОС от същата точка. Това е почти като пътуване във времето. С продължения можете да си го позволите!

В какви ситуации ще бъдат полезни продълженията? Обикновено, ако се опитвате да емулирате състояние в системи, които по своята същност са лишени от състояние. Отлично използване на продълженията е намерено в уеб приложенията (например в рамката Seaside за езика Smalltalk). ASP.NET на Microsoft полага големи усилия, за да запази състоянието между заявките, за да улесни живота ви. Ако C# поддържаше продължения, сложността на ASP.NET можеше да бъде намалена наполовина чрез просто запазване на продължението и възстановяването му при следваща заявка. От гледна точка на уеб програмист няма да има нито едно прекъсване - програмата ще продължи работата си от следващия ред! Продълженията са невероятно полезна абстракция за решаване на някои проблеми. С все повече и повече традиционни дебели клиенти, които се преместват в мрежата, важността на продълженията само ще нараства с времето.

Съвпадащ модел

Съпоставянето на шаблони не е толкова нова или иновативна идея. Всъщност това няма много общо с функционалното програмиране. Единствената причина, поради която често се свързва с FP, е, че от известно време функционалните езици имат съвпадение на шаблони, но императивните езици не.

Нека започнем нашето въведение в съпоставянето на шаблони със следния пример. Ето функция за изчисляване на числата на Фибоначи в Java:

Int fib(int n) ( if(n == 0) връща 1; if(n == 1) връща 1; връща fib(n - 2) + fib(n - 1); )
И ето един пример на Java-подобен език с поддръжка за Pattern matching

Int fib(0) (връщане 1; ) int fib(1) (връщане 1; ) int fib(int n) (връщане fib(n - 2) + fib(n - 1); )
Каква е разликата? Компилаторът реализира разклоняването вместо нас.

Помислете само, това е много важно! Наистина не е толкова важно. Беше забелязано, че голям брой функции съдържат сложни структури на превключватели (това е отчасти вярно за функционалните програми) и беше решено да се подчертае тази точка. Дефиницията на функцията е разделена на няколко варианта и е установен модел на мястото на аргументите на функцията (това напомня за претоварване на метод). Когато възникне извикване на функция, компилаторът сравнява аргументите с всички дефиниции в движение и избира най-подходящия. Обикновено изборът пада върху най-специализираната дефиниция на функция. Например int fib(int n) може да се извика, когато n е 1, но няма, защото int fib(1) е по-специализирана дефиниция.

Съпоставянето на шаблони обикновено изглежда по-сложно, отколкото в нашия пример. Например сложна система за съвпадение на шаблони ви позволява да напишете следния код:

Int f(int n< 10) { ... } int f(int n) { ... }
Кога съпоставянето на шаблони е полезно? Списъкът с такива случаи е учудващо дълъг! Всеки път, когато използвате сложни вложени if конструкции, съпоставянето на шаблони може да свърши по-добра работа с по-малко код. Добър пример, който идва на ум, е функцията WndProc, която е внедрена във всяка Win32 програма (дори ако е скрита от програмиста зад висока ограда от абстракции). Обикновено съпоставянето на шаблон може дори да провери съдържанието на колекциите. Например, ако подадете масив към функция, тогава можете да изберете всички масиви, чийто първи елемент е равен на 1 и чийто трети елемент е по-голям от 3.

Друго предимство на Pattern matching е, че ако правите промени, няма да се налага да ровите в една огромна функция. Всичко, което трябва да направите, е да добавите (или промените) някои дефиниции на функции. Така се отърваваме от цял слой шаблони от известната книга на Бандата на четиримата. Колкото по-сложни и разклонени са условията, толкова по-полезно ще бъде използването на съвпадение на шаблони. След като започнете да ги използвате, ще се чудите как сте се справяли без тях.

Затваряния

Досега обсъждахме характеристиките на FP в контекста на „чисто“ функционални езици - езици, които са имплементации на ламбда смятане и не съдържат функции, които противоречат на официалната църковна система. Въпреки това, много характеристики на функционалните езици се използват извън ламбда смятането. Въпреки че прилагането на аксиоматична система е интересно от гледна точка на програмиране по отношение на математически изрази, това може да не винаги е приложимо на практика. Много езици предпочитат да използват елементи от функционални езици, без да се придържат към строга функционална доктрина. Някои такива езици (например Common Lisp) не изискват променливите да бъдат окончателни - техните стойности могат да бъдат променяни. Те дори не изискват функциите да зависят само от техните аргументи - на функциите е разрешен достъп до състояние извън техния обхват. Но в същото време те включват такива характеристики като функции от по-висок ред. Предаването на функция в нечист език е малко по-различно от еквивалентната операция в ламбда смятането и изисква интересна функция, наречена лексикално затваряне. Нека да разгледаме следния пример. Запомнете това в в такъв случайпроменливите не са окончателни и функцията може да има достъп до променливи извън своя обхват:

Функция makePowerFn(int power) ( int powerFn(int base) ( return pow(base, power); ) return powerFn; ) Функция square = makePowerFn(2); квадрат (3); // връща 9
Функцията make-power-fn връща функция, която приема един аргумент и го повишава до определена степен. Какво се случва, когато се опитаме да оценим square(3)? Променливата мощност е извън обхвата на powerFn, тъй като makePowerFn вече е завършен и неговият стек е унищожен. Как тогава работи квадратът? Езикът трябва по някакъв начин да съхрани значението на силата, за да може квадратната функция да работи. Ами ако създадем друга кубична функция, която повдига число на трета степен? Езикът ще трябва да съхранява две стойности на мощността за всяка функция, създадена в make-power-fn. Феноменът на съхраняване на тези стойности се нарича затваряне. Затварянето не само запазва аргументите на функцията top. Например затварянето може да изглежда така:

Функция makeIncrementer() ( int n = 0; int increment() ( return ++n; ) ) Функция inc1 = makeIncrementer(); Функция inc2 = makeIncrementer(); inc1(); // връща 1; inc1(); // връща 2; inc1(); // връща 3; inc2(); // връща 1; inc2(); // връща 2; inc2(); // връща 3;
По време на изпълнение стойностите на n се съхраняват и броячите имат достъп до тях. Освен това всеки брояч има собствено копие на n, въпреки факта, че те трябваше да изчезнат след изпълнение на функцията makeIncrementer. Как компилаторът успява да компилира това? Какво се случва зад кулисите на затварянията? За щастие имаме магически пропуск.

Всичко е направено съвсем логично. На пръв поглед е ясно, че локалните променливи вече не са обект на правила за обхват и животът им е недефиниран. Очевидно те вече не се съхраняват в стека - те трябва да се държат в купчината. Следователно затварянето се прави като нормалната функция, която обсъдихме по-рано, с изключение на това, че има допълнителна препратка към заобикалящите променливи:

Клас some_function_t ( SymbolTable parentScope; // ... )
Ако затварянето има достъп до променлива, която не е в локалния обхват, то взема предвид родителския обхват. Това е всичко! Затварянето свързва функционалния свят със света на ООП. Всеки път, когато създавате клас, който съхранява някакво състояние и го предавате някъде, помнете за затварянията. Затварянето е просто обект, който създава "атрибути" в движение, изваждайки ги извън обхвата, така че не е нужно да го правите сами.

Сега какво?

Тази статия докосва само върха на айсберга на функционалното програмиране. Можете да копаете по-дълбоко и да видите нещо наистина голямо, а в нашия случай нещо добро. В бъдеще планирам да пиша за теория на категориите, монади, функционални структури от данни, типови системи във функционални езици, функционална многонишковост, функционални бази данни и много други неща. Ако мога да пиша (и да уча в процеса) дори за половината от тези теми, животът ми няма да е напразен. Междувременно, Google- вашият верен приятел.

Ползи от функционалното програмиране

Вероятно си мислите, че не мога да направя случай, за да оправдая чудовищната функция по-горе. Когато за първи път започнах да уча функционално програмиране, и аз мислех така. Сгреших. Има много добри аргументи за този стил. Някои от тях са субективни. Например програмистите твърдят, че функционалните програми са по-лесни за разбиране. Няма да излагам такива аргументи, защото всеки знае, че лекотата на разбиране е много субективно нещо. За мое щастие все още има много обективни аргументи.

Единично тестване

Отстраняване на грешки

Многопоточност

Ако това е така, тогава защо функционалните езици за програмиране се използват толкова рядко в многонишкови приложения? Всъщност по-често, отколкото си мислите. Ericsson разработи функционален език, наречен Erlang, за използване на устойчиви на грешки и мащабируеми телекомуникационни комутатори. Мнозина отбелязаха предимствата на Erlang и започнаха да го използват. Говорим за системи за телекомуникации и контрол на трафика, които не са толкова лесни за мащабиране, колкото типичните системи, разработени на Уолстрийт. Всъщност системите, написани на Erlang, не са толкова мащабируеми и надеждни, колкото системите на Java. Системите Erlang са просто супер надеждни.

Компилаторът на функционален език може да анализира кода, да класифицира функциите, които произвеждат редове s1 и s2 като отнемащи време функции, и да ги изпълнява паралелно. Това е невъзможно да се направи в императивен език, тъй като всяка функция може да промени външното състояние и кодът непосредствено след извикването може да зависи от нея. Във FP автоматичният анализ на функциите и търсенето на подходящи кандидати за паралелизиране е тривиална задача, като автоматичното вграждане! В този смисъл функционалният стил на програмиране е устойчив на бъдещето. Разработчиците на хардуер вече не могат да накарат процесора да работи по-бързо. Вместо това те увеличават броя на ядрата и претендират за четирикратно увеличение на скоростта на многонишкови изчисления. Разбира се, те забравят да кажат точно навреме, че вашият нов процесор ще показва печалби само в програми, проектирани с успоредяване. Има много малко такива сред императивния софтуер. Но 100% от функционалните програми са готови за многопоточност от кутията.

Горещо внедряване

В старите времена трябваше да рестартирате компютъра си, за да инсталирате актуализации на Windows. Много пъти. След инсталиране на нова версия на мултимедийния плейър. Имаше значителни промени в Windows XP, но ситуацията все още е далеч от идеалната (днес пуснах Windows Update на работа и сега досадното напомняне не ме оставя на мира, докато не рестартирам). Unix системите имаха по-добър модел за актуализиране. За да инсталирам актуализации, трябваше да спра някои компоненти, но не и цялата ОС. Въпреки че ситуацията изглежда по-добре, тя все още не е приемлива за голям клас сървърни приложения. Телекомуникационните системи трябва да бъдат включени 100% от времето, защото ако актуализация попречи на човек да се обади на линейка, животите могат да бъдат загубени. Фирмите от Wall Street също не искат да затварят сървъри през уикенда, за да инсталират актуализации.

Машинно подпомагани доказателства и оптимизации

Друго интересно свойство на функционалните езици за програмиране е, че те могат да бъдат научени от математическа гледна точка. Тъй като функционалният език е реализация на формална система, всички математически операции, използвани на хартия, могат да бъдат приложени към функционални програми. Компилаторът, например, може да преобразува част от код в еквивалентна, но по-ефективна част, като същевременно математически обоснове тяхната еквивалентност. Релационните бази данни правят тези оптимизации от години. Нищо не ви пречи да използвате подобни техники в обикновените програми.

Освен това можете да използвате математика, за да докажете коректността на секции от вашите програми. Ако желаете, можете да напишете инструменти, които анализират вашия код и автоматично да създават Unit тестове за крайни случаи! Тази функционалност е безценна за твърди системи. При разработването на системи за мониторинг на пейсмейкър или системи за управление на въздушното движение, такива инструменти са задължителни. Ако вашите разработки не са в областта на критични за мисията приложения, тогава автоматизираните инструменти за проверка ще ви дадат огромно предимство пред вашите конкуренти.

Функции от по-висок ред

Клас add_function_t ( int add(int i, int j) ( return i + j; ) ) add_function_t add = new add_function_t();
Символът за добавяне всъщност не е функция. Това е малък клас с един метод. Сега можем да предадем add като аргумент на други функции. Можем да го запишем в друг символ. Можем да създадем екземпляри на add_function_t по време на изпълнение и те ще бъдат унищожени от събирача на отпадъци, ако вече не са необходими. Функциите стават основни обекти, точно като числата и низовете. Функциите, които оперират с функции (приемат ги като аргументи), се наричат функции от по-висок ред. Нека това не ви плаши. Концепцията за функции от по-висок ред е почти същата като концепцията за Java класове, които работят един върху друг (можем да предаваме класове на други класове). Можем да ги наречем „класове от по-висок порядък“, но никой не се занимава с това, защото зад Java няма строга академична общност.

Абстрактен клас MessageHandler ( void handleMessage(Message msg) ( // ... msg.setClientCode(getClientCode()); // ... sendMessage(msg); ) абстрактен низ getClientCode(); // ... ) клас MessageHandlerOne разширява MessageHandler ( String getClientCode() ( return "ABCD_123"; ) ) клас MessageHandlerTwo разширява MessageHandler ( String getClientCode() ( return "123_ABCD"; ) )
Сега за всеки сървър можем да създадем екземпляр от съответния клас. Добавянето на нови сървъри става по-удобно. Но има много текст за такава малка промяна. Трябваше да създам два нови типа само за да добавя поддръжка за различен клиентски код! Сега нека направим същото на нашия език с поддръжка за функции от по-висок ред:

Къри

Мързелива оценка

Оптимизация

Мързеливата оценка предоставя огромен потенциал за оптимизации. Мързеливият компилатор гледа на кода по същия начин, по който математикът гледа на алгебричните изрази - той може да отмени неща, да отмени изпълнението на определени части от кода, да промени реда на извикванията за по-голяма ефективност, дори да подреди кода по такъв начин, че да намали броя на грешки, като същевременно се гарантира целостта на програмата. Това е най-голямото предимство на описанието на програма с помощта на строги формални примитиви - кодът се подчинява на математическите закони и може да бъде изследван с помощта на математически методи.

Абстрахиране на контролни структури

Безкрайни структури от данни

Мързеливите езици ви позволяват да създавате безкрайни структури от данни, които са много по-трудни за създаване в строги езици. - просто не в Python]. Например, представете си редицата на Фибоначи. Очевидно е, че не можем да изчислим безкраен списък за крайно време и пак да го съхраняваме в паметта. В строги езици като Java, ние просто бихме написали функция, която връща произволен член на последователността. В езици като Haskell можем да се абстрахираме и просто да декларираме безкраен списък от числа на Фибоначи. Тъй като езикът е мързелив, ще бъдат изчислени само необходимите части от списъка, които действително се използват в програмата. Това ви позволява да се абстрахирате от голям брой проблеми и да ги погледнете от по-високо ниво (например можете да използвате функции за обработка на списъци на безкрайни последователности).

недостатъци

Разбира се, безплатното сирене идва само в капан за мишки. Мързеливите изчисления идват с редица недостатъци. Това са главно недостатъци от мързел. В действителност много често е необходим директен ред на изчисления. Вземете например следния код:

На мързелив език, никой не гарантира, че първият ред ще бъде изпълнен преди втория! Това означава, че не можем да правим I/O, не можем да използваме собствените функции нормално (в края на краищата, те трябва да бъдат извикани в определен ред, за да се отчетат техните странични ефекти) и не можем да взаимодействаме с външния свят! Ако въведем механизъм за нареждане на изпълнението на кода, ще загубим предимството на математическата строгост на кода (и тогава ще загубим всички предимства на функционалното програмиране). За щастие не всичко е загубено. Математиците се заеха с работа и измислиха няколко техники, за да гарантират, че инструкциите се изпълняват в правилния ред, без да се губи функционалният дух. Имаме най-доброто от двата свята! Такива техники включват продължения, монади и въвеждане на уникалност. В тази статия ще работим с продължения и ще оставим монадите и недвусмисленото писане за следващия път. Интересно е, че продълженията са много полезно нещо, което се използва не само за определяне на строг ред на изчисления. Ще говорим и за това.

Продължения

Но ползите от продълженията не свършват дотук. Можем да напишем цялата програма с помощта на CPS, така че всяка функция да се извиква с допълнителен параметър, продължение, на което се предава резултатът. По принцип всяка програма може да бъде преведена в CPS, ако всяка функция се третира като специален случай на продължения. Това преобразуване може да се извърши автоматично (всъщност много компилатори го правят).

Добре, сега разбираме какво е текущото продължение. Какво означава? Ако вземем текущото продължение и го запазим някъде, по този начин запазваме текущото състояние на програмата - замразяваме го. Това е подобно на режима на хибернация на ОС. Обектът за продължение съхранява информацията, необходима за възобновяване на изпълнението на програмата от точката, в която обектът за продължение е поискан. Операционната система прави това с вашите програми през цялото време, когато превключва контекста между нишките. Единствената разлика е, че всичко е под контрола на ОС. Ако поискате обект за продължение (в Scheme това става чрез извикване на функцията call-with-current-continuation), тогава ще получите обект с текущото продължение - стека (или в случая на CPS, следващата функция за извикване ). Можете да запишете този обект в променлива (или дори на диск). Ако решите да "рестартирате" програмата с това продължение, тогава състоянието на вашата програма се "трансформира" до състоянието в момента, в който е бил взет обектът за продължение. Това е същото като превключване към спряна нишка или събуждане на операционната система след хибернация. С изключение на това, че можете да правите това много пъти подред. След като операционната система се събуди, информацията за хибернация се унищожава. Ако това не беше направено, тогава би било възможно да се възстанови състоянието на ОС от същата точка. Това е почти като пътуване във времето. С продължения можете да си го позволите!

Съвпадащ модел

Затваряния

Досега обсъждахме характеристиките на FP в контекста на „чисто“ функционални езици - езици, които са имплементации на ламбда смятане и не съдържат функции, които противоречат на официалната църковна система. Въпреки това, много характеристики на функционалните езици се използват извън ламбда смятането. Въпреки че прилагането на аксиоматична система е интересно от гледна точка на програмиране по отношение на математически изрази, това може да не винаги е приложимо на практика. Много езици предпочитат да използват елементи от функционални езици, без да се придържат към строга функционална доктрина. Някои такива езици (например Common Lisp) не изискват променливите да бъдат окончателни - техните стойности могат да бъдат променяни. Те дори не изискват функциите да зависят само от техните аргументи - на функциите е разрешен достъп до състояние извън техния обхват. Но в същото време те включват такива характеристики като функции от по-висок ред. Предаването на функция в нечист език е малко по-различно от еквивалентната операция в ламбда смятането и изисква интересна функция, наречена лексикално затваряне. Нека да разгледаме следния пример. Не забравяйте, че в този случай променливите не са окончателни и функцията има достъп до променливи извън нейния обхват:

Сега какво?

Мързеливи изчисления

В традиционните езици за програмиране (като C++), извикването на функция кара всички аргументи да бъдат оценени. Този метод за извикване на функция се нарича извикване по стойност. Ако във функцията не е използван аргумент, резултатът от изчислението се губи, следователно изчислението е направено напразно. В известен смисъл обратното на повикване по стойност е повикване по необходимост. В този случай аргументът се оценява само ако е необходим за изчисляване на резултата. Пример за това поведение е операторът за свързване от C++ (&&), който не оценява стойността на втория аргумент, ако първият аргумент е false.

Ако функционален език не поддържа мързелива оценка, тогава той се нарича строг. Всъщност в такива езици редът на оценка е строго определен. Примерите за стриктни езици включват Scheme, Standard ML и Caml.

Езиците, които използват мързелива оценка, се наричат нестроги. Haskell е свободен език, точно като Gofer и Miranda, например. Леките езици често са чисти.

Много често строгите езици включват поддръжка за някои от полезните функции, открити в нестроги езици, като безкрайни списъци. Standard ML идва със специален модул за поддръжка на отложени изчисления. В допълнение, Objective Caml поддържа допълнителната запазена дума lazy и конструкция за списъци със стойности, изчислени според нуждите.

Този раздел предоставя Кратко описаниенякои функционални езици за програмиране (много малко).

§ Lisp(Списъчен процесор). Счита се за първия функционален език за програмиране. Без тип. Той съдържа много императивни свойства, но като цяло насърчава функционалния стил на програмиране. Използва извикване по стойност за изчисления. Има обектно-ориентиран диалект на езика - CLOS.

§ АЗ ПЛУВАМ(Ако разбирате какво имам предвид). Функционален езиков прототип. Разработен от Landin през 60-те години на 20-ти век, за да демонстрира какъв може да бъде функционален език за програмиране. Заедно с езика Landin разработи и специална виртуална машина за изпълнение на програми на ISWIM. Това виртуална машина, базиран на извикване по стойност, се нарича SECD машина. Синтаксисът на много функционални езици се основава на синтаксиса на езика ISWIM. Синтаксисът на ISWIM е подобен на този на ML, особено Caml.

§ Схема. Диалект на Lisp, предназначен за научни изследвания в областта на компютърните науки. Схемата е проектирана с акцент върху елегантността и простотата на езика. Това прави езика много по-малък от Common Lisp.

§ М.Л.(Мета език). Семейство от стриктни езици с разработена система от полиморфен тип и модули с възможност за параметризиране. ML се преподава в много западни университети (някои дори като първи език за програмиране).

§ Стандартен ML. Един от първите типизирани функционални езици за програмиране. Съдържа някои задължителни свойства като връзки към променливи стойностии следователно не е чист. Използва извикване по стойност за изчисления. Много интересна реализация на модулността. Мощна система от полиморфен тип. Най-новият езиков стандарт е стандарт ML-97, за който има формални математически дефиниции на синтаксиса, както и на статичната и динамична семантика на езика.

§ Caml LightИ Обектив Caml. Подобно на Standard ML, той принадлежи към семейството на ML. Objective Caml се различава от Caml Light главно в поддръжката си за класическо обектно-ориентирано програмиране. Точно като Standard ML е строг, но има известна вградена поддръжка за мързелива оценка.

§ Миранда. Разработен от Дейвид Търнър като стандартен функционален език, който използва мързелива оценка. Има строга система от полиморфен тип. Подобно на ML, той се преподава в много университети. Той имаше голямо влияние върху разработчиците на езика Haskell.

§ Haskell. Един от най-разпространените нестроги езици. Има много развита система за писане. Модулната система е малко по-слабо развита. Най-новият езиков стандарт е Haskell-98.

§ Gofer(Добър за еквационално разсъждение). Опростен диалект на Haskell. Предназначен за обучение по функционално програмиране.

§ Чисто. Специално проектиран за паралелно и разпределено програмиране. Синтаксисът е подобен на Haskell. Чисто. Използва отложени изчисления. Компилаторът идва с набор от библиотеки (I/O библиотеки), които ви позволяват да програмирате графичен потребителски интерфейс под Win32 или MacOS.

Нека ви го напомним най-важната характеристикаФункционалният подход е фактът, че всяка програма, разработена на функционален език за програмиране, може да се разглежда като функция, чиито аргументи също могат да бъдат функции.

Функционалният подход породи цяло семейство от езици, чийто предшественик, както вече беше отбелязано, беше езикът за програмиране LISP. По-късно, през 70-те години, е разработена оригиналната версия на езика ML, която впоследствие се развива по-специално в SML, както и в редица други езици. От тях може би „най-младият“ е езикът Haskell, създаден съвсем наскоро, през 90-те години.

Важно предимство на внедряването на функционални езици за програмиране е автоматизираното динамично разпределение на компютърната памет за съхранение на данни. В този случай програмистът се отървава от необходимостта да контролира данните и, ако е необходимо, може да стартира функцията „събиране на боклук“ - изчистване на паметта от данни, които програмата вече няма да се нуждае.

Комплексните програми във функционалния подход се изграждат чрез агрегиране на функции. В този случай текстът на програмата е функция, някои от аргументите на която също могат да се разглеждат като функции. Така повторното използване на кода се свежда до извикване на предварително описана функция, чиято структура, за разлика от императивна езикова процедура, е математически прозрачна.

Тъй като функцията е естествен формализъм за функционалните езици за програмиране, внедряването на различни аспекти на свързаното с функцията програмиране е значително опростено. Писането на рекурсивни функции става интуитивно прозрачно, т.е. функции, които се самоизвикват като аргумент. Прилагането на обработка на рекурсивни структури от данни също става естествено.

Поради внедряването на механизъм за съвпадение на шаблони, функционалните езици за програмиране като ML и Haskell са добри за символна обработка.

Естествено, функционалните езици за програмиране не са без някои недостатъци.

Те често включват нелинейната структура на програмата и относително ниската ефективност на изпълнение. Въпреки това, първият недостатък е доста субективен, а вторият е успешно преодолян от модерни реализации, по-специално, редица скорошни SML езикови преводачи, включително компилатор за Microsoft .NET среда.

За да разработите професионален софтуер на функционални езици за програмиране, трябва да разберете задълбочено естеството на функцията.

Обърнете внимание, че терминът „функция“ в математическата формализация и софтуерната реализация се отнася до различни концепции.

По този начин, математическа функция f с домейн на дефиниция A и диапазон от стойности B е набор от подредени двойки

такъв, че ако

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

От своя страна функцията на езика за програмиране е конструкция на този език, която описва правилата за преобразуване на аргумент (т.нар. действителен параметър) в резултат.

За да се формализира понятието „функция“, е изградена математическа теория, известна като ламбда смятане. По-точно, това смятане трябва да се нарича смятане на ламбда преобразувания.

Преобразуването се отнася до трансформирането на обекти на смятане (и в програмирането, функции и данни) от една форма в друга. Оригиналната задачав математиката имаше желание да се опрости формата на изразите. В програмирането тази конкретна задача не е толкова важна, въпреки че, както ще видим по-късно, използването на ламбда смятане като първоначална формализация може да помогне за опростяване на типа програма, т.е. водят до оптимизиране на програмния код.

Освен това преобразуванията осигуряват преход към нововъведени обозначения и по този начин правят възможно представянето на предметната област в по-компактна или по-подробна форма, или, с други думи, математически език, променете нивото на абстракция по отношение на предметна област. Тази функция също се използва широко от обектно-ориентирани и структурно-модулни езици за програмиране в йерархията на обекти, програмни фрагменти и структури от данни. Взаимодействието на компонентите на приложението в .NET се основава на същия принцип. В този смисъл преходът към нови нотации е един от най-важните елементи на програмирането като цяло и именно ламбда смятането (за разлика от много други клонове на математиката) представлява адекватен начин за формализиране на ренотациите.

Нека систематизираме еволюцията на теориите, залегнали в съвременния подход към ламбда смятането.

Нека разгледаме еволюцията на езиците за програмиране, развиващи се в рамките на функционалния подход.

Ранните функционални езици за програмиране, които произхождат от класическия език LISP (LIST Processing), са предназначени за обработка на списъци, т.е. символична информация. В този случай основните типове бяха атомен елемент и списък от атомни елементи, а основният акцент беше върху анализирането на съдържанието на списъка.

Развитието на ранните езици за програмиране се превърна в функционални езици за програмиране със силно типизиране, типичен пример тук е класическият ML и неговият пряк наследник SML. В строго типизираните езици всяка конструкция (или израз) трябва да има тип.

Въпреки това, в по-късните функционални езици за програмиране няма нужда от изрично присвояване на тип и типовете първоначално недефинирани изрази, както в SML, могат да бъдат изведени (преди програмата да бъде стартирана) въз основа на типовете изрази, свързани с тях .

Следващата стъпка в развитието на функционалните езици за програмиране беше поддръжката на полиморфни функции, т.е. функции с параметрични аргументи (аналози математическа функцияс параметри). По-специално, полиморфизмът се поддържа в SML, Miranda и Haskell.

На настоящия етап на развитие се появиха езици за функционално програмиране от „ново поколение“ със следните разширени възможности: съпоставяне на шаблони (Scheme, SML, Miranda, Haskell), параметричен полиморфизъм (SML) и така наречените „мързеливи“ (като необходими) изчисления (Haskell, Miranda, S.M.L.).

Семейството от функционални езици за програмиране е доста голямо. Това се доказва не толкова от значителния списък от езици, а от факта, че много езици са породили цели тенденции в програмирането. Нека си припомним, че LISP даде началото на цяло семейство от езици: Scheme, InterLisp, COMMON Lisp и т.н.

Езикът за програмиране SML не беше изключение, който беше създаден под формата на езика ML от R. Milner в MIT (Масачузетски технологичен институт) и първоначално беше предназначен за логически изводи, по-специално доказване на теореми. Езикът е различен силно писане, липсва параметричен полиморфизъм.

Развитието на „класическия“ ML се превърна в три модерни езика с почти идентични възможности (параметричен полиморфизъм, съвпадение на шаблони, „мързеливи“ изчисления). Това е езикът SML, разработен във Великобритания и САЩ, CaML, създаден от група френски учени в института INRIA, SML/NJ - диалект на SML от Ню Джърси, а също и руска разработка - mosml (" московски“ диалект на ML).

Близостта до математическата формализация и първоначалната функционална ориентация доведоха до следните предимства на функционалния подход:

1. лекота на тестване и проверка на програмния код въз основа на възможността за конструиране на строго математическо доказателство за коректността на програмите;

2. унифициране на представянето на програмата и данните (данните могат да бъдат капсулирани в програмата като аргументи на функцията, обозначаването или изчисляването на стойността на функцията може да се направи според нуждите);

3. безопасно въвеждане: невалидни операции с данни са изключени;

4. динамично въвеждане: възможно е да се открият грешки при въвеждане по време на изпълнение (отсъствието на това свойство в ранните функционални езици за програмиране може да доведе до запълване на RAM на компютъра);

5. независимост на софтуерната реализация от машинното представяне на данни и системната архитектура на програмата (програмистът е фокусиран върху детайлите на реализацията, а не върху характеристиките на машинното представяне на данни).

Обърнете внимание, че реализирането на предимствата, които функционалните езици за програмиране предоставят, зависи значително от избора на софтуерна и хардуерна платформа.

Ако .NET технологията е избрана като софтуерна платформа, почти независимо от хардуерната реализация, програмист или мениджър софтуерен проектдопълнително получава следните предимства:

1. интегриране на различни функционални езици за програмиране (докато се максимизират предимствата на всеки език, по-специално, Scheme осигурява механизъм за съвпадение на шаблони, а SML осигурява възможност за изчисляване според нуждите);

2. интегриране на различни подходи към програмирането, базирани на междуезичната обща езикова инфраструктура или CLI (по-специално, възможно е да се използва C#, за да се осигурят предимствата на обектно-ориентиран подход и SML - функционален, както в този курс) ;

3. обща унифицирана система за въвеждане Common Type System, CTS (унифицирана и безопасно управлениетипове данни в програмата);

4. многоетапна, гъвкава система за осигуряване на сигурността на програмния код (по-специално въз основа на механизма за сглобяване).

Основните характеристики на функционалните езици за програмиране, които ги отличават както от императивните езици, така и от езиците за логическо програмиране, са референтна прозрачност и детерминизъм. Във функционалните езици има значителни вариации в параметри като правила за въвеждане и изчисление. В много езици редът на оценяване е строго определен. Но понякога строгите езици съдържат поддръжка за някои полезни елементи, присъщи на нестрогите езици, като безкрайни списъци (Standard ML има специален модул за поддръжка на мързелива оценка). За разлика от тях, нестриктните езици позволяват енергично изчисление в някои случаи.

По този начин Miranda има мързелива семантика, но ви позволява да укажете стриктни конструктори, като маркирате аргументите на конструктора по определен начин.

Много съвременни функционални езици за програмиране са строго типизирани езици (строго типизиране). Силното въвеждане осигурява по-голяма сигурност. Много грешки могат да бъдат коригирани на етапа на компилация, така че етапът на отстраняване на грешки и общото време за разработка на програмата са намалени. Силното въвеждане позволява на компилатора да генерира по-ефективен код и по този начин да ускори изпълнението на програмата. Наред с това има функционални езици с динамично писане. Типът данни в такива езици се определя по време на изпълнение на програмата (Глава 3). Понякога се наричат "безтипни". Техните предимства включват факта, че програмите, написани на тези езици, имат по-голяма общност. Недостатък може да се счита за приписването на много грешки на етапа на изпълнение на програмата и свързаната с това необходимост от използване на функции за проверка на типа и съответно намаляване на общоприетостта на програмата. Типизираните езици допринасят за генерирането на по-„надежден“ код, докато типизираните езици произвеждат по-„общ“ код.

Следващият критерий, по който функционалните езици за програмиране могат да бъдат класифицирани, може да бъде наличието на императивни механизми. В същото време е обичайно да наричаме функционални езици за програмиране, които са лишени от императивни механизми, „чисти“, а тези, които ги имат, се наричат „нечисти“. В прегледа на функционалните езици за програмиране по-долу езиците за програмиране ще бъдат наричани „практически“ и „академични“. „Практически“ езици се разбират като езици, които имат търговско приложение (в тях са разработени реални приложения или има търговски системи за програмиране). Академичните езици за програмиране са популярни в изследователските среди и в областта компютърно образование, но практически няма търговски приложения, написани на такива езици. Те остават просто инструмент за провеждане на теоретични изследвания в областта на компютърните науки и се използват широко в учебния процес.

Списък с най-популярните функционални езици за програмиране е даден по-долу, като се използват следните критерии: обща информация; писане; вид изчисление; чистота.

Common Lisp. Версия на Lisp, която от 1970 г. може да се счита за езиков стандарт, благодарение на подкрепата от лабораторията изкуствен интелектМасачузетски технологичен институт, безтипов, енергичен, с голям набор от императивни включвания, които позволяват присвояване и унищожаване на структури. Практичен. Достатъчно е да се каже, че векторният графичен редактор AutoCAD е написан на Lisp.

Схема. Диалект на Lisp, предназначен за научни изследвания в компютърните науки и преподаване на функционално програмиране. Благодарение на липсата на императивни включвания, езикът е много по-малък от Common Lisp. Датиращ от език, разработен от J. McCarthy през 1962 г. Академичен, безтипов, енергичен, чист.

Рефал. Семейство от езици, разработено от V. F. Turchin. Най-старият член на това семейство е реализиран за първи път през 1968 г. в Русия. Все още се използва широко в академичните среди. Съдържа елементи за логическо програмиране (съвпадение на шаблони). Следователно в това се предлага езикът Refal учебниккато език за самообучение.

Миранда. Строго типизиран, поддържа потребителски типове данни и полиморфизъм. Разработено от Turner въз основа на по-ранните езици SALS и KRC. Има мързелива семантика. Без наложителни включвания.

Haskell. Развитието на езика се случи в края на миналия век. Широко известен в академичните среди. В някои западни университети той се използва като основен език за обучение на студентите. Един от най-мощните функционални езици. Мързелив език. Чисто функционален език. Написано. Haskell е страхотен инструмент за учене и експериментиране със сложни функционални типове данни. Програмите, написани на Haskell, имат значителен размер на обектния код и ниска скорост на изпълнение.

Чисто. Диалект на Haskell, съобразен с нуждите на практическото програмиране. Подобно на Haskell, той е мързелив, чисто функционален език, съдържащ типови класове. Но Clean съдържа и интересни функции, които нямат еквивалент в Haskell. Например, императивните функции в Clean се основават на уникални типове, чиято идея е заимствана от линейната логика. Clean съдържа механизми, които могат значително да подобрят ефективността на програмите. Тези механизми изрично потискат мързеливите изчисления. Внедряването Clean е търговски продукт, но е налична безплатна версия за изследователски и образователни цели.

ML (мета език). Разработено от група програмисти, ръководени от Робърт Милиер в средата на 70-те години. в Единбург (Единбургска логика за изчислими функции). Идеята на езика беше да се създаде механизъм за конструиране на формални доказателства в система от логика за изчислими функции. През 1983 г. езикът е преработен, за да включва понятия като модули. Нарича се стандартен ML. ML е силен въведен езиксъс статична проверка на типа и изпълнение на приложна програма. Той придоби голяма популярност в изследователските среди и в областта на компютърното образование.

Функционално програмиране

1. Въведение

Програми на традиционни езици за програмиране като C, Pascal, Java и др. Те се състоят от поредица от модификации на стойностите на определен набор от променливи, който се нарича състояние. Ако не вземем предвид I/O операциите и също така не вземем предвид факта, че програмата може да работи непрекъснато (т.е. без спиране, както в случая със сървърните програми), можем да направим следната абстракция. Преди програмата да започне да се изпълнява, състоянието има някаква начална стойност σ0, която представлява входните стойности на програмата. След като програмата приключи, състоянието има нова стойност σ0, която включва това, което може да се счита за „резултат“ от програмата. По време на изпълнение всяка команда променя състоянието; следователно състоянието преминава през някаква крайна последователност от стойности:

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

Състоянието се променя с помощта на команди за присвояване, записани като v=E или v:=E, където v е променлива и E е някакъв израз. Тези команди следват една след друга; Изявления като if и while ви позволяват да промените реда, в който тези команди се изпълняват в зависимост от стойността на текущото състояние. Този стил на програмиране се нарича императивен или процедурен.

Функционалното програмиране представлява парадигма, която е фундаментално различна от модела, представен по-горе. Функционалната програма е израз (в математически смисъл); изпълнението на програмата означава изчисляване на стойността на този израз.1 Като се вземе предвид горната нотация, като се има предвид, че резултатът от работата

1 Използването на термина „изчисление“ не означава, че програмата може да работи само с числа; Резултатът от изчислението може да бъде низове, списъци и като цяло всякакви структури от данни, разрешени в езика.

императивната програма е напълно и еднозначно определена от нейния вход, можем да кажем, че крайното състояние (или всяко междинно) е някаква функция (в математическия смисъл) на първоначалното състояние, т.е. σ0 = f(σ). Функционалното програмиране използва тази гледна точка: програмата е израз, съответстващ на функцията f. Функционалните езици за програмиране поддържат изграждането на такива изрази, предоставям широк изборсъответните езикови конструкции.

Когато сравнявате функционалния и императивния подход към програмирането, можете да забележите следните свойства на функционалните програми:

Функционалните програми не използват променливи в смисъла, в който думата се използва в императивното програмиране. По-специално, функционалните програми не използват оператора за присвояване.

Като следствие от предходната точка, във функционалните програми няма цикли.

Изпълнението на последователност от команди във функционална програма е безсмислено, тъй като една команда не може да повлияе на изпълнението на следващата.

Функционалните програми използват функциите по много по-сложни начини. Функциите могат да се предават на други функции като аргументи и да се връщат като резултат и дори като цяло да извършват изчисления, които водят до функция.

Вместо цикли, функционалните програми широко използват рекурсивни функции.

На пръв поглед функционалният подход към програмирането може да изглежда странен, необичаен и малко полезен, но трябва да се вземат предвид следните съображения.

На първо място, императивният стил в програмирането не е твърдо кодирана необходимост. Много от характеристиките на императивните езици за програмиране са резултат от абстракция от детайли на компютърната реализация на ниско ниво, от машинен код до асемблерни езици до езици като Fortran и т.н. Въпреки това, няма причина да се смята, че такива езици отразяват най-естествения език

начин човек да съобщи намеренията си на машина. Може би по-правилният подход е, че езиците за програмиране се раждат като абстрактни системи за писане на алгоритми и след това се превеждат на императивен компютърен език.

Освен това функционалният подход има редица предимства пред императивния. На първо място, функционалните програми съответстват по-директно на математическите обекти и следователно позволяват строго разсъждение. Задайте стойността на императивната програма, т.е. функцията, която изпълнява, може да бъде доста трудна за оценка. Обратно, значението на функционална програма може да бъде изведено почти директно.

Например, помислете следващата програмав Haskell:

факториел n = ако n == 0 тогава 1 иначе n * факториел (n - 1)

Почти веднага можете да видите, че тази програма отговаря на следната частична функция:

f(n) = n! n ≥ 0

(Тук символът означава, че функцията е недефинирана, тъй като програмата не прекратява за отрицателни стойности на аргумента.) Въпреки това, за C програма това съответствие не е очевидно:

int x = 1; докато (n > 0)

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

Трябва да се отбележи и използването на термина „функция“ в езици като C, Java и др. В математически смисъл „функциите“ на езика C не са функции, защото:

Значението им може да зависи не само от аргументите;

Резултатът от прилагането им може да бъде различенстранични ефекти(например промяна на стойностите на глобалните променливи)

Две извиквания на една и съща функция с едни и същи аргументи могат да доведат до различни резултати.

В същото време функциите във функционалните програми са наистина функции в смисъла, в който това се разбира в математиката. Съответно коментарите, направени по-горе, не се отнасят за тях. От това следва, че оценката на всеки израз не може да има странични ефекти и следователно редът, в който се оценяват неговите подизрази, не влияе на резултата. По този начин функционалните програми могат лесно да бъдат паралелизирани, тъй като отделните компоненти на изразите могат да бъдат оценени едновременно.

2 Основи на ламбда смятането

Точно както теорията на машината на Тюринг е в основата на императивните езици за програмиране, ламбда смятането служи като основа и математическа "основа", на която се основават всички функционални езици за програмиране.

Ламбда смятането е изобретено в началото на 30-те години на миналия век от логика А. Чърч, който се надява да го използва като формализъм, за да оправдае математиката. Скоро бяха открити проблеми, които направиха невъзможно използването му в това качество (сега има причина да се смята, че това не е напълно вярно) и ламбда смятането остана като един от начините за формализиране на концепцията за алгоритъм.

В момента ламбда смятането е основната формализация, използвана в изследванията, свързани с езиците за програмиране. Това вероятно се дължи на следните фактори:

Това е единствената формализация, която, макар и с някои неудобства, всъщност може да се използва директно за писане на програми.

Ламбда смятанепредоставя прост и естествен модел за важни концепции като рекурсия и вложени среди.

Повечето конструкции в традиционните езици за програмиране могат да бъдат повече или по-малко директно картографирани към конструкцияламбда смятане.

Функционалните езици са основно удобна форма на синтактична нотация за конструкции на различни варианти на ламбда смятане. Някои съвременни езици (Haskell, Clean) имат

100% съответствие на неговата семантика със семантиката на подразбиращите се конструкции на ламбда смятане.

В математиката, когато е необходимо да се говори за функция, е обичайно да се даде име на тази функция и впоследствие да се използва, както например в следното твърдение:

Нека f: R → R е определено от следния израз:

	(x2 sin(1/x2),

Тогава f0 (x) не е интегрируем на интервала .

Много езици за програмиране също позволяват функциите да бъдат дефинирани само чрез присвояване на някои имена към тях. Например в езика C функцията винаги трябва да има име. Това изглежда естествено, но тъй като функциите се използват навсякъде във функционалното програмиране, този подход може да доведе до сериозни проблеми. Представете си, че винаги трябва да работим с аритметични изрази в подобен стил:

Нека x = 2 и y = 4. Тогава xx = y.

Ламбда нотацията ви позволява да дефинирате функции със същата лекота, както другите математически обекти. Ламбда изразще наричаме конструкция на формата

където E е някакъв израз, вероятно използващ променливата x.

Пример. λx.x2 е функция, която повдига аргумента си на квадрат.

Използването на ламбда нотация ни позволява ясно да разделим случаите, когато под израз на формата f(x) имаме предвид самата функция f и нейната стойност в точка x. В допълнение, ламбда нотацията ви позволява да формализирате почти всички видове математически нотации. Ако започнете с константи и променливи и изградите изрази, използвайки само ламбда изрази и функционални приложения върху аргументи, можете да си представите много сложни математически изрази.

Ще обозначим приложението на функцията f към аргумента x като f x, т.е., за разлика от обичайното в математиката, няма да използваме скоби2. По причини, които ще станат ясни по-късно, ще приемем, че прилагането на функция към аргумент е ляво асоциативно, т.е. f x y

2 Обърнете внимание, че в математиката изрази като sin x се пишат без скоби.

означава (f(x))(y). Като стенограма за изрази от формата λx.λy.E ще използваме нотацията λx y.E (подобно за по-голям брой аргументи). Ще приемем също, че „обхватът“ на ламбда израза се простира възможно най-надясно, т.е. например λx.x y означава λx.(x y), а не (λx.x)y.

На пръв поглед изглежда, че трябва да въведем специална нотация за функции от няколко аргумента. Съществува обаче къри операция 3, която ви позволява да пишете такива функции в обикновена ламбда нотация. Идеята е да се използват изрази от формата λx y.x + y. Такъв израз може да се разглежда като функция R → (R → R), т.е. ако се приложи към един аргумент, резултатът е функция, която след това приема друг аргумент. По този начин:

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

Променливите в ламбда изразите могат да бъдат свободни или обвързани. В израз от формата x2 + x, променливата x е свободна; стойността му зависи от стойността на променливата x и по принцип не може да бъде

Ако промените нотацията j, значението на израза няма да се промени.

Трябва да се разбере, че във всеки подизраз една променлива може да бъде свободна (както в израза под интеграла), но в целия израз тя е обвързана с някои операция за свързване на променливи, като например операцията за сумиране. Извиква се частта от израза, която е "вътре" в операцията за свързване обхватпроменлива.

В ламбда смятането изразите λx.E[x] и λy.E[y] се считат за еквивалентни (това се нарича α-еквивалентност, а процесът на преобразуване между такива двойки се нарича α-трансформация). Разбира се, необходимо е да се наложи условието y да не е свободна променлива в E[x].

3 от фамилията на известния логик Хаскел Къри, на когото е кръстен езикът за програмиране Хаскел

3 Ламбда смятанекато формална система

Ламбда смятането се основава на формалната нотация на ламбда термин, съставен от променливи и някакъв фиксиран набор от константи, използвайки операцията на прилагане на функция и ламбда абстракция. Това означава, че всички ламбда изрази могат да бъдат разделени на четири категории:

1. Променливи: обозначават се с произволни низове, съставени от букви и цифри.

2. Константи: също се означават с низове; ще определим разликата от променливи от контекста.

3. Комбинации: , т.е. прилагане на функция S към аргумент T; и S и T могат да бъдат произволни ламбда членове. Комбинацията е написана като S T.

4. Абстракции на произволен ламбда терм S по отношение на променливата x, означена като λx.S.

По този начин ламбда терминът се дефинира рекурсивно и неговата граматика може да се дефинира като следната форма на Бекус-Наур:

Exp = Var| Const| Exp Exp| λВар. Exp

Според тази граматика ламбда термините са представени като синтактични дървета, а не като последователности от знаци. От това следва, че споразуменията относно асоциативността на операцията за прилагане на функция, еквивалентността на изрази от формата λx y.S и λx.λy.S, неяснотата в имената на константите и променливите произтичат само от необходимостта да се представят ламбда термини в удобна за хората форма и не са част от формалната система.

3.1 Свободни и обвързани променливи

IN В този раздел ние формализираме дадената по-рано интуитивна идея за свободни и обвързани променливи. Много безплатни

променливи F V (S) ламбда терминът S може да бъде дефиниран рекурсивно, както следва:

По подобен начин наборът от свързани променливи BV (S) се определя от следните формули:

BV(x) =

BV(c) =

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

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

Тук се приема, че c е някаква константа.

Пример. За термина S = (λx y.x) (λx.z x) може да се покаже, че F V (S) = (z) и

BV(S) = (x, y).

3.2 Замени

Интуитивно прилагането на термина λx.S като функция към аргумент T води до термин S, в който всички свободни появявания на x са заменени с T . Изненадващо, формализирането на тази интуиция не е лесно.

Ще обозначим операцията по заместване на термин S за променлива x в друг термин T като T. Точно както при дефиницията на свободни и обвързани променливи, правилата за заместване също могат да бъдат дефинирани рекурсивно. Трудността е, че е необходимо да се наложи допълнителни ограничения, което ви позволява да избягвате конфликти в имената на променливите.

3.3 Преобразуване

Ламбда смятането се основава на три операции за преобразуване, които ви позволяват да преминете от един член към друг, който е еквивалентен на него. Според установената традиция тези преобразувания се означават с гръцките букви α, β и η. Те се определят, както следва:

α-конверсия: λx.S −→ λy.S при условие, че y / F V (S).

Например λu.u v −→ λw.w u.

β-конверсия: (λx.S) T −→ S.

β-преобразуването е най-важно за нас, тъй като то съответства на изчисляването на стойността на функция от аргумент. α-преобразуването е спомагателен механизъм за промяна на имената на обвързани променливи, а η-преобразуването представлява интерес главно когато се разглежда ламбда смятането от логическа, а не от програмна гледна точка.

3.4 Равенство на ламбда членове

Използвайки въведените правила за преобразуване, можем формално да дефинираме концепцията за равенство на ламбда членовете. Два термина са равни, ако човек може да премине от единия към другия, използвайки крайна последователност от преобразувания. Нека дефинираме концепцията за равенство чрез следните изрази, в които хоризонталните линии трябва да се разбират като „ако твърдението над линията е изпълнено, тогава твърдението също е вярно

под него":

Необходимо е да се разграничи понятието равенство, дефинирано с тези формули, от понятието синтактична еквивалентност, което ще обозначим със специалния символ ≡. Например λx.x 6≡λy.y, но λx.x = λy.y. Често е възможно да се разгледа синтактичната еквивалентност на термините до α-конверсии. Такава еквивалентност ще означаваме със символа ≡α. Тази връзка се дефинира по същия начин като равенството на ламбда членовете, с изключение на това, че от всички преобразувания са разрешени само α-преобразувания. Така λx.x ≡α λy.y.

3.5 Екстензивност

η-преобразуването в ламбда смятане изразява принципа екстензионност. В общ философски смисъл се казва, че две свойства са екстензивно еквивалентни, ако принадлежат на абсолютно едни и същи обекти. В математиката например е възприет разширителен изглед на множествата, т.е. две групи се считат за еднакви, ако съдържат едни и същи елементи. По подобен начин казваме, че две функции са равни, ако имат една и съща област и за всякакви стойности на аргумента в тази област те изчисляват един и същ резултат.