I.5. Функционално програмиране — Разширена писмена разработка

Разширена писмена разработка. I.5. Функционално програмиране

Подробен авторски текст за подготовка по конспекта на СУ. Краткият вариант е запазен на основната страница на темата. За преговор използвай плана; за обосновка — определенията и разработените примери. Това не е официален изпитен образец.

Кратка разработка и уроци по темата · План за изпита · Покритие · Източници

Обхват от конспекта

Функционално програмиране. Основни конструкции в езиците за функционално програмиране. Дефиниране и използване на функции. Функции от по-висок ред. Модели на оценяване на изрази.

Покритие на конспекта

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

  1. Функционално програмиране — 1. Предмет и цел на функционалното програмиране
  2. Основни конструкции в езиците за функционално програмиране — 2. Основни конструкции; дефиниране и използване на функции
  3. Дефиниране и използване на функции — 2. Основни конструкции; дефиниране и използване на функции
  4. Функции от по-висок ред — 3. Функции от по-висок ред
  5. Модели на оценяване на изрази — 4. Модели на оценяване на изрази

Кратък план за изпита

  1. Функционална парадигма и референтна прозрачност.
  2. Изрази, типове, условни конструкции, образци и рекурсия.
  3. Дефиниране, извикване и област на видимост на функции.
  4. Функции от по-висок ред, композиция и частично прилагане.
  5. Строго, нормално и мързеливо оценяване.
  6. Пример за различно завършване и заключение.

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

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

Чистата функция връща един и същ резултат за едни и същи аргументи и няма наблюдаеми странични ефекти. Референтната прозрачност позволява израз да се замени с неговата стойност, без да се променя поведението на програмата. Например чистото square 5 може да се замени с 25. Операция, която чете текущ час или променя файл, не може безусловно да се разглежда по същия начин.

Функционалният стил не означава липса на вход и изход. В Haskell ефектите са разграничени чрез типове като IO a, а в Scheme могат да се съчетават функционални и изменящи състоянието конструкции. Следователно трябва да различаваме парадигма, чистота на конкретна функция и възможности на езика.

2. Основни конструкции; дефиниране и използване на функции

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

square :: Integer -> Integer
square x = x * x

absolute :: Integer -> Integer
absolute x
  | x < 0     = -x
  | otherwise = x

sumList :: [Integer] -> Integer
sumList [] = 0
sumList (x:xs) = x + sumList xs

Дефиницията свързва име с функция; прилагането square 4 изчислява 16. При sumList празният списък е базов случай, а образецът x:xs отделя глава и опашка. За [2,3,5] получаваме 2+(3+(5+0))=10. Рекурсията се прекратява за краен списък, защото всяка стъпка работи с по-къс остатък. Това е аргумент за завършване, различен от проверката на няколко примера.

Съпоставянето с образци избира подходяща дефиниция според структурата на данните. Условните охрани проверяват логически условия. Изразите let … in … и локалните определения с where именуват помощни изчисления. Лексикалната област на видимост определя коя дефиниция се използва по структурата на програмата, а не по произволния ред на извикванията.

При работа с частични функции трябва да се посочи областта им. Четенето на глава на празен списък не е валидна операция без допълнителен договор. По-надежден интерфейс може да връща вариант „няма резултат“. Не всяка математически изглеждаща дефиниция завършва: loop = loop не определя изчислима крайна стойност.

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

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

map прилага функция към всеки елемент, filter запазва елементите, удовлетворяващи предикат, а foldr обединява елементите чрез операция и начална стойност. В map square [2,3,5] резултатът е [4,9,25]. Изразът filter even [2,3,5,8] дава [2,8]. foldr (+) 0 [2,3,5] изчислява 10. Така сходните рекурсивни схеми се изразяват веднъж.

twice :: (a -> a) -> a -> a
twice f x = f (f x)

add :: Integer -> Integer -> Integer
add x y = x + y

addFive = add 5
result = twice addFive 10  -- 20

Кърирането представя функция с няколко аргумента като последователност от функции с по един аргумент. Типът Integer -> Integer -> Integer се чете като функция, която получава цяло число и връща функция. Частичното прилагане add 5 оставя втория аргумент за по-късно. Ламбда-изразът \x -> x + 5 задава същото преобразуване без собствено име.

Композицията f . g означава първо да се приложи g, после f. Типът на резултата от g трябва да съответства на входа на f. Затварянето, или closure, съчетава функция с нужната лексикална среда. Това значение на „затваряне“ е различно от затварянето на множество атрибути при функционални зависимости в базите от данни.

4. Модели на оценяване на изрази

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

Мързеливото оценяване, или call-by-need, съчетава отлагане със споделяне на вече изчислен резултат. То се различава от call-by-name, при което повторна употреба може да повтори изчислението. Haskell има нестрога семантика, която типично се реализира чрез мързеливо оценяване. „Нестрог“ описва семантично свойство, а „мързелив“ — механизъм за изпълнение; термините не трябва да се смесват без пояснение.

Нека first x y = x и loop = loop. При строгото оценяване first 7 loop не завършва, защото се опитва да изчисли и втория аргумент. При нестрого оценяване може да се получи 7, понеже y не е нужен. Това показва, че изборът на стратегия може да влияе не само върху скоростта, а и върху завършването.

Мързеливостта позволява крайна употреба на безкрайни структури: take 3 [1..] дава [1,2,3], без да конструира всички естествени числа. Но отложените изрази могат да задържат памет, а някои алгоритми са по-ефективни със строго натрупване. Следователно мързеливото оценяване не е универсална гаранция за по-нисък разход.

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

Функции от по-висок ред върху познати структури

Сверка със СУ 2: §2.3.4: ориг. 108–112 / нов PDF 102–107; двоични дървета: ориг. 175–177 / нов PDF 167–170.

Функцията от по-висок ред приема функция като аргумент или връща функция. В учебника map, filter и accumulate приемат операция/предикат и го прилагат върху елементите. За [2,5,8] map с „добави 1“ дава [3,6,9], filter с „четно“ дава [2,8], а accumulate със събиране и начален акумулатор 0 дава 15. Примерът показва обща схема вместо три отделни ръчно написани обхождания.

Редът е част от договора. При ляво натрупване с изваждане и начало 0 получаваме ((0−2)−5)−8=−15; операцията не е асоциативна, затова промяна на реда може да промени резултата. При дърво трябва да заявим и реда на посещение; разглежданият accumulate работи в ред ляво–корен–дясно.

Това, че C++ функцията приема друга функция, не прави целия език чисто функционален. Реализацията може да използва изменяем списък, указатели и цикъл; аргументите обичайно се оценяват преди извикването. Примерите от този учебник дават мост към понятието, но не са доказателство за лениво оценяване в Haskell. За чистота, заместване, нормален/апликативен ред и отложено оценяване се запазват СУ 6 и СУ 9.

СУ 2: учебник, проверен код и таблица за всички 20 теми · Допълнение по точните страници на учебника

Литературна опора и граници на сверяването

Официална библиография на СУ — номерата по-долу са от нея.

  • СУ 6 — Simon Thompson, Haskell: The Craft of Functional Programming, 3. изд., 2011. Наличен е авторският PDF на третото издание, публикуван през 2023 г.. Основни конструкции: глави 3–5; функции от по-висок ред: глави 10–11; лениво оценяване: глава 17, особено §17.1–17.2. Страниците на авторския PDF не се отъждествяват автоматично с печатния тираж от 2011 г.
  • СУ 9 — Abelson, Sussman, Structure and Interpretation of Computer Programs, 2. изд., 1996. Наличен е пълен текст: MIT PDF. PDF е преформатирана Texinfo версия от 2016 г.; използваме номера на раздели, не предполагаеми страници на печатното издание. §1.1.5 (модел на заместване), §1.2 (процеси), §1.3 (функции от по-висок ред), §4.2 (лениво оценяване).

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

Обратно към кратката разработка и уроците