Автор - А.А. Марков, отдавал предпочтение транскрипции алгори ф м. Нормальные алгорифмы Маркова
представляются нормальной схемой подстановок, которая состоит из совокупности подстановок,
расположенных в определенном порядке. Подстановки имеют вид: P ® (·) Q (P ® Q – (простая)
подстановка, P ® · Q – заключительная подстановка).
Говорят, что строка R входит в строку L, если L имеет вид L1RL2.
Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки,
входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки
правой.Две особые подстановки:
P ® - аннулирующая.
® Q - порождающая.
Механизм работы нормальных алгорифмов:
Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема
подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.
1) Слово всегда просматривается слева направо.
Схема подстановок просматривается всегда начиная с первой подстановки и, если подстановку можно
применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.
2) Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо.использована
заключительная подстановка.
Примеры.
Нормальная схема преобразуемое
подстановок слово МУХА
xx ® y xx xyyyzzz Х ® К МУКА
xy ® x y xy yyzzz М ® Р РУКА
yzy ® x y xy yzzz КА ® ЛОН РУЛОН
zz ®. z y xy zzz РУ ®. СЛ СЛОН
yy ® x yx zz z
yxzz
Примеры алгорифмов, использ. специальные символы, аннулирующие и порождающие подстановки:
Удвоение исходной строки Обращение исходной строки
aх ® хbхa aa ® ba
aу ® уbуa ba ® b
bхх ® хbх bх ® хb
bху ® уbх bу ® уb
bух ® хbу b ®
bуу ® уbу aху® уaх
b ® aух ® хaу
a ®. ® a
® a
Рефал
LISP, созданный в начале 60-х годов, не единственный функциональный язык, хотя и самый распростран.
Интересный функциональный язык РЕФАЛ был разработан в 70-х годах нашим соотечественником
Турчиным и исподльзовал математическую модель нормальных алгорифмов Маркова.
 | |
 |
21. Язык РЕФАЛ.
k………., │ - конкретизирующие скобки
«~» - эквивалент «®»
«……» - текст (название программы, комментарий)
Выделение первого элемента:
k «пер» Se|~ «S»
k «пер» e ~
 |  |
22. 
Лямбда-исчисление. ЛИСП.
l-исчисление, основоположником которого считают Алонзо Черча, фактически, и стало основой
теории алгоритмов и первой конкретизации алгоритма. l-исчисление рассматривают также как основу
таких важных разделов математики, как функциональное программирование и комбинаторная логика.
l-исчисление (нотация, способ записи) формализует понятие функции не как множества или графика, а как
правила.
В основе l-исчисления лежит операция аппликации.
Аппликация - применение функции к аргументу (можно применить только известную функцию).
Язык состоит из: l-терм:
1. Множества переменных (х1...). 1. Переменная или константа - l-терм.
2. Множества констант(с1...). 2. Если х - переменная, и М - некоторый l-терм, то lх.М тоже l-терм.
3. Символа аппликации.. 3. Если М и N l-термы, то MN тоже l-терм.
4. Символа абстракции l.
5. Символа равенства =.
Формула - любое выражение вида M=N, где M и N l-термы.
Замечание. В литературе прикладного плана нередко используется несколько иная терминология и форма
записи.
f = lx.x + x
f - название, ранее не названной функции.
l - оператор.
х - аргумент.
.-комбинатор.
х + х - выражение, задающее значение функции.
Аксиомы:
1. M = M.
2. (lx.M)N = M {N/x} b-редукция. где {N/x} – подстановка N вместо всех вхождений x в М.
[В альтернативном представлении часто используемая b-редукция записывается, например, так
(lx.f(x))(a) = f(a)]
3. lx.M = ly.M при {y/x} a-конверсия.
где {у/x} – подстановка у вместо всех вхождений x в М.
Правила вывода:
M = N; N = M.; M = N, N = P; M = P.; M = N; PM = PN. M = N; MP = NP.; M = N lx.M = lx.N.
Рассмотрим примеры b-редукции (в прикладной варианте записи)
(lх.х + 2у)(а) = а + 2у, (lу.х + 2у)(а) = х + 2а
(lх.(lу.х + 2у))(а)(b) = (lу.а + 2у)(b) = a + 2b, (lx.((ly.xy)u))(lv.v) = (ly.(lv.v)y)u = (lv.v)u
(lx.((ly.xy)u))(lv.v) = (lx.xu)(lv.v) = (lv.v)u, (lx.xx) (lx.xx) = (lx.xx) (lx.xx) = (lx.xx) (lx.xx) =…
((lx.x*3) (ly.if y > 4 then e = 2 else x/2) (ly.y>2)) (5) = 2*5 = 10
(ln.(lx.x-n))(2) = lx.x-2, (lf.2*f(8) – f(f(8)))(half) = 2*8/2 – (8/2)/2 = 6 (half – половина).
Лисп
Первым языком функционального программирования был язык LISP и многие базовые понятия этого языка
стали классикой функционального программирования.
Базовые функции функционального программирования:
car(x) - дает первый элемент списка х;
cdr(х) - хвост списка (список без первого элемента);
cons(x,y) - добавляет элемент х к списку у;
append(x,y) - добавляет список y к списку x;
Примеры.
Пусть x = (1, 2, 3) y = (4, 5)
car(x) = (1);
cdr(х) = (2, 3);
cons(x,y) = ((1, 2, 3), 4, 5);
append(x,y) = (1, 2, 3, 4, 5).
Синтаксис LISP достаточно архаичный, поэтому воспользуемся способом записи функциональных
программ с помощью специальной нотации, ставшей популярной с легкой руки Хендерсона.
Примеры.
Функция дл вычисления длины списка
Для (х) º if(x) = nil then 0 else дл(cdr(x)) + 1
Вычислим функцию для конкретного списка.
дл(A, B, C) = дл(B, C) + 1
дл(B, C) = дл(C) + 1
дл(C) = дл(nil) + 1
дл (nil) = 0
"Пройдя" в обратном направлении можно получить числовое значение.
Обращение списка обр, то есть список A, B, C обратится в список C, B, A
обр(x, y) º if x = nil then y else обр(cdr(x), cons(car(x), y))
Вычислим функцию для конкретного списка
обр(A, B, C, nil) = обр((B, C), (A))
обр((B, C), (A)) = обр((C), (B, A))
обр((C), (B, A)) = обр((nil), C, B, A)
Здесь использован популярный прием функционального программирования "сумка". Это позволяет
получить результат сразу, без обратного прохода.
 | |
 |
Язык Бэкуса.
формальная система определения синтаксиса, в которой одни синтаксические категории последовательно
определяются через другие. Используется для описания контекстно-свободных формальных грамматик.
Как и в БНФ, описание грамматики в РБНФ представляет собой набор правил, определяющих отношения
между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).
Терминальные символы — это минимальные элементы грамматики, не имеющие собственной
грамматической структуры. В РБНФ терминальные символы — это либо предопределённые
идентификаторы (имена, считающиеся заданными для данного описания грамматики), либо цепочки —
последовательности символов в кавычках или апострофах.
Нетерминальные символы — это элементы грамматики, имеющие собственные имена и структуру.
Каждый нетерминальный символ состоит из одного или более терминальных и/или нетерминальных
символов, сочетание которых определяется правилами грамматики. В РБНФ каждый нетерминальный
символ имеет имя, которое представляет собой строку символов.
Правила
Правило в РБНФ имеет вид:
идентификатор = выражение.
где идентификатор — имя нетерминального символа, а выражение — соответствующая правилам РБНФ
комбинация терминальных и нетерминальных символов и специальных знаков. Точка в конце —
специальный символ, указывающий на завершение правила.
Семантика правила РБНФ — нетерминальный символ, заданный идентификатором слева от знака
«равно», представляет собой определяемую выражением комбинацию терминальных и нетерминальных
символов.
Полное описание грамматики представляет собой набор правил, который последовательно определяет
все нетерминальные символы грамматики так, что каждый нетерминальный символ может быть сведён
к комбинации терминальных символов путём последовательного (рекурсивного) применения правил.
В определении РБНФ нет никаких специальных предписаний относительно порядка записи правил, хотя
такие предписания могут вводиться при использовании РБНФ программными средствами,
обеспечивающими автоматическую генерацию программ синтаксического разбора по описанию
грамматики.
(/+)○(α*)○Т:<<1,2,3>>, <<4,5,6>>
/ - Ветовка
○ – операция композиции
Т – транспозиция
(/+)○(α*)○Т: <<1,6>>, <<2,5>>, <<3,4>>
(/+):<<6,10,12>>
□:28
Программа не динамична APL
| |||
 |
