Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 59443
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,109
новичок: syqwe
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование работы перекрёстка по регулированию движения на GPSS + Поя...
Моделирование круглосуточного интернет кафе на GPSS + Отчет
Принадлежит ли точка пересечению двух окружностей на Turbo Pascal + Отче...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Ответы к упражнениям
0не имеет свободных переменных (1) и символов абстракции (3);[x].+x1
имеет переменную x, которая является связанной (1); + x 1 не содер-
жит абстракций (2);[f].f([x].+ x x) не имеет свободных переменных (1),
[x].+ x x является суперкомбинатором (2).
16.2
[x].x y z содержит свободные переменные y и z, нарушается пункт (1)
определения 16.1; [x].[y].+ (+ x y)z имеет свободную переменную z.
16.3
Например, [x].[y].x y([z].z x).
16.4
Выражение $XY 5 вычислить нельзя, так как оно не является редексом;
$XY 5 7 вычислимо, $XY 3 4 7 вычислимо.
16.5
1)
([x].([y].− y x)x)5:



(1) самой внутренней абстракцией является [y].− y x;
(2) вынесем x как экстрапараметр ([x].[y].− y x)x и подставим его в
исходную программу
([x].([v].[y].− y v)x x)5;



(3) присвоим суперкомбинатору имя $Y :
$Y v y = − y v
([x].$Y x x)5



(4) [x].-абстракция также является суперкомбинатором, которому
можно дать имя и который можно сопоставить скомпилированному коду:
$Y v y = − y v
$X x = $Y x x
$X 5



Полученная программа выполняется следующим образом:
$X 5 = $Y 5 5 = − 5 5 = 0.



2)
([z].+ z (([x].([y].× y x)x)4)2 :



(1) внутренняя абстракция: [y].× y x;
(2) вынесем x как экстрапараметр:
([x].[y].× y x)x
([z].+ z(([x].([w].[y].× y w)x x)4))2;
(3)
$Y w y = × y w
([z].+ z([x].$Y x x)4)2



(4) [x].-абстракция является суперкомбинатором:
$Y w y = × y w
$X x = $Y x x
([z].+ z($X 4))2



Теперь видно, что [z].-абстракция является суперкомбинатором:
$Y w y = × y w
$X x = $Y x x
$Z z = + z ($X 4)
$Z 2



Выполнение программы:
$Z 2 = + 2 ($X 4) = + 2 ($Y 4 4) = + 2 (× 4 4) = + 2 16 = 18.



16.6
inf находится на уровне и не содержит внутренних абстракций. Поэтому
inf уже является суперкомбинатором:

$inf v = letrec vs = cons 0 vs in vs
$P rog = $inf 4
$P rog



16.7
Запишем эту программу в терминах абстракций:
letrec apply = [m].letrec constr = [n].(IF > n m)NIL
(cons n (constr (+ n 1)))
in fold КВАДРАТ (constr 1)
fold = [f].[ns].IF(= ns NIL)NIL(cons(f(head ns))
(fold(f(tail ns))))
in apply 5



(1) внутренняя абстракция имеет вид:
([n].IF(> n m)NIL(cons n(constr(+ n 1)));



(2) вынесем переменные constr и m в указанном порядке:
([constr].[m].[n].IF(> n m)NIL(cons n(constr(+ n 1)))constr m;



(3) присвоим полученному суперкомбинатору имя $constr:
$constr constr m n = IF(> n m)NIL(cons n(constr(+ n 1)));



(4) заменим вхождение [n].-абстракции в программу на
($constr constr m n);
$constr constr m n = IF(> n m)NIL(cons n(constr(+ n 1)))
letrec
apply = [m].letrec
constr = $constr constr m
in fold КВАДРАТ (constr 1)
fold = [f].[ns].IF(= ns NIL)NIL
(cons(f(head ns))(fold f(tail ns)))
in apply 5



(5) выражения apply и fold являются суперкомбинаторами:
$constr constr m n = IF(> n m)NIL(cons m(constr(+ n 1)))
$fold f ns = IF(= ns NIL)NIL(cons(f(head ns))
(fold(f (tail ns))))
$apply m = letrec constr = $constr constr m
in $fold КВАДРАТ (constr 1)
$P rog = $apply 5
$P rog



16.8
Поднимем [n].-абстракцию, абстрагируя переменную m, но не constr, и
заменим все вхождения constr на ($constr m):

$constr m n = IF(> n m)NIL(cons n($constr m(+ n 1)))
letrec
apply = [m].fold(КВАДРАТ)($constr m 1)
fold = [f].[ns].IF(= ns NIL)NIL(cons(f(head ns))
(fold(f(tail ns))))
in apply 5



В данном случае и apply, и fold являются суперкомбинаторами:
$constr m n = IF(> n m)NIL(cons n($constr m(+ n 1)))
$fold f ns = IF(= ns NIL)NIL(cons(f(head ns))
($fold f(tail ns)))
$apply m = $fold КВАДРАТ ($constr m 1)
$P rog = $apply 5
$P rog



16.9
а) Запись в виде абстракции:
letrec f = g 2
g = [x].[y].× y (КВАДРАТ x)
in × (f 3)(f 1)



Вычисление выражения:
× (f 3)(f 1) → (. 3)(. 1)
−→ ([x].[y].× y (КВАДРАТ x))2
→ × (. 3)(. 1)
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3)(× 1 (КВАДРАТ 2))
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3) 4
−→ ([y].× y (КВАДРАТ 2))
→ × (× 3 (КВАДРАТ 2)) 4
→ × 12 4
→ 48.



б) Данное выражение компилируется в:
$g x y = × y (КВАДРАТ x)
$f = $g 2
$P rog = × ($f 3)($f 1)
$P rog



Последовательность редукций:
$P rog → (× (. 3)(. 1))
−→ ($g 2)
→ × (. 3)(× 1 (КВАДРАТ 2))
−→ ($g 2)
→ × (. 3) 4
−→ ($g 2)
→ × (× 3 (КВАДРАТ 2)) 4
→ × (× 3 4) 4
→ × 12 4
→ 48.



16.10
× (f 3)(f 1) → × (. 3)(. 1)
−→ (([x].[y].× y (КВАДРАТ x))2)
→ × (. 3)(× 1 .)
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3) 4 (× 1 .)
−→ ([y].× y 4)
→ × (. 3) 4
−→ ([y].× y 4)
→ × (× 3 .) 4
−→ 4
→ × 12 4
→ 48



Выражение (КВАДРАТ 2) вычисляется единственный раз.
16.11
Функция g содержит абстракцию: [x].[y].× y (КВАДРАТ x):
(1) самой внутренней абстракцией является
[y].× y (КВАДРАТ x);



(2) (КВАДРАТ x) представляет собой МСВ, которую вынесем в каче-
стве экстрапараметра:

[КВАДРАТx].[y].× y (КВАДРАТx)КВАДРАТx.



Подставим полученное выражение в абстракцию:
[x].[КВАДРАТx].[y].× y (КВАДРАТx)КВАДРАТx ;



(3) присвоим полученному суперкомбинатору имя:
$g1 = [КВАДРАТx].[y].× y КВАДРАТx
[x].$g1 (КВАДРАТ x)



(4) [x].-абстракция также является суперкомбинатором, которому
дадим имя $g и который сопоставим скомпилированному коду:

$g1 КВАДРАТx y = × y КВАДРАТx
$g x = $g1 (КВАДРАТ x)
$f = $g 2
$P rog = × ($f 3)($f 1)
$P rog



16.12
Данная программа компилируется в:
$el el n s = (IF(= n 1)(head s)(el(− n 1)(tail s)))
$g x = letrec el = $el el
in (cons x (el 3 (A, B, C)))
(cons ($g R)($g L))



Поскольку определение el не зависит от x, можно вынести letrec для el:
letrec el = [n].[s].(IF(= n 1)(head s)
(el(−n1)(tails)))
in let g = [x].cons x (el 3 (A, B, C))
in (cons (g R)(g L))



В результате применения ламбда-подъема получим:
$el n s = (IF(= n 1)(head s)(el(− n 1)(tail s)))
$el3(A, B, C) = $el 3 (A, B, C)
$g x = cons x $el3(A, B, C)
$P rog = cons ($g R)($g L)
$P rog



В ходе компилирования программы порождаются новые комби-
наторы, параметрами которых являются конкретные МСВ. Другими
словами, компилятор выполняет соотнесение с заложенным в нем
способом вычленения из исходного кода программы объектов и по-
рождает объекты-индивиды. Поскольку порожденные объекты явля-
ются комбинаторами, то вполне безопасно добавить их к системе-
оболочке в качестве новых инструкций. Все порожденные комбина-
торы дают вполне индивидуализированное представление исходной
программы: это система объектов.
Возможно, лучше объяснять в терминах соотнесения системы-
оболочки (λ-исчисления) с совокупностью МСВ. Тогдаλ-исчисление
как концептдает систему индивидов (скомпилированных программ):
они образуют класс эквивалентности (конвертируются друг к другу)
относительно критериев оптимальности.
Опубликовал Kest May 04 2014 21:34:34 · 0 Комментариев · 1999 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
AVIwriter
Панель для реклам...
База для Allsubmi...
Разработка распре...
PRNDbgrid
Проигрыватель Mp3
Dealer
VksButton
Xrumer 4 Platinum...
PolyFlow
Секреты программи...
JanButtonsV
SODA [Исходник на...
около 291 статьи ...
Иллюстрированный ...
IconCut [Исходник...
PDA версия сайта
Базы данных в Инт...
ATComponents
Cooltray

Топ загрузок
Приложение Клие... 100512
Delphi 7 Enterp... 90220
Converter AMR<-... 20092
GPSS World Stud... 14974
Borland C++Buil... 12703
Borland Delphi ... 8943
Turbo Pascal fo... 7093
Калькулятор [Ис... 5127
Visual Studio 2... 5018
FreeSMS v1.3.1 3554
Случайные статьи
записями в Active ...
Следование правилам
Как обеспечить сов...
Элементы управлени...
Карта RESET
Структура сообщени...
Играть в Кекс на с...
Открытие документа
Уже забыли пароль?
Тип документа XHTM...
Листинг 9.6. Двоич...
Контроль доступа
Где клэптон койл к...
Разрешение адреса
Алгоритмы для слож...
Как найти резидент...
Иногда требуется б...
Представления дере...
Настройка Windows ...
Invalid variable r...
Выполнение лаборат...
ПРИМЕР ЭЛЕКТРОННОГ...
Управление Выводом...
может быть установ...
Основанные принцип...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?