KNOW INTUIT, Лекция, Функционално програмиране

Изчислителен модел на LISP

За LISP (както и за всеки друг функционален език) 2 A не е необходимо за предотвратяване на хакове и е нежелателно! кажете къде и как са поставени структурите от данни (списъци).

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

1. Преди стъпката за оценкаима списък, включващ името на функцията и нейните аргументи.
2. По време на изпълнениена стъпката на изчисление, това са онези фрагменти от структурата на списъка на зрителното поле, които са достъпни за използване от изчислената функция (по-специално, сред тях има списък, свързан с името на функцията, което определя нейния изчислителен процес).
3. След изпълнениена изчислителната стъпка, това са резултатите от изчислението. Резултатите могат да бъдат разделени на три групи:
4. стойността, върната от извикването на функцията: тя замества изгледа на завършеното извикване на функция;
5. странични ефекти, разпръснати из цялата структура на полето с данни;
6. следващата функция, която ще бъде изчислена по-нататък. В традиционното програмиране обикновено се връща към оценката на функцията, която е извикала прекратената функция. Във функционалното програмиране нещата могат да бъдат различни. Резултатът може да бъде функция, описана в статичния текст на програмата или свързана в хода на изчисленията.

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

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

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

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

1. LISP списъци, които са свързани с последователни изчисления. Структурата на графиката се дефинира като колекция от линейни списъци, които комбинират имена на функции и указатели на аргументи. Главата на списъка се третира като индикация на функция, а опашката се третира като аргументи.
2. Превключващи вериги, които са изградени на базата на разделяне на функции и данни: функциите са представени от върхове на графа и техните аргументи за данни се предават по дъги, свързващи върховете. Дъгите се считат за комуникационни канали. Функцията се активира, когато нейните аргументи се появят в каналите.
3. Асоциативни схеми, в които функционалните възли остават виртуални. Те се формират чрез свързване на данни, които имат един и същ ключ. Ситуацията, когато такива данни се появяват в асоциативната памет, се интерпретира като готовност на аргументите за изчисляване на функцията, идентифицирана от този ключ.

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

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

Това отличава LISP от повечето езици, където такива структурни преходи са или непълни, или неправилно изпълнени.

Освен това всяко описание на функция се счита за блок. Функция се декларира с помощта на функцията defun, която от своя страна се дефинира чрез функцията и ламбда примитивите. Първият от тях уточнява, че името, което е негов аргумент, се третира като функция (често се съкращава в конкретен синтаксис на #’), второто формира стойност от функционалния тип. Името на функцията е и името на функционалния блок.

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

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

Всички параметри на формалната функция са локални променливи. Не се публикуват промени в техните стойности. Но всички останали свойства остават глобални! Да вземем пример.

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

Значението на едно външно наследено име е всичкопак ще е външен! Вижте примера по-долу.

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

Функцията mapcar прилага първия си аргумент към всички членове на втория.

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

И накрая, нека дадем пример 3 Любезно предоставен от L. Gorodnya (ISIS RAS и Новосибирски държавен университет) .

Пример 8.4.2. Тази програма изгражда автомат за намиране на всички срещания на някаква система от думи във входния поток. По-късно се анализира от гледна точка на автоматичното програмиране.

---