Навигация
Главная
Поиск
Форум
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
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Создание отчето... 63514
Модуль Forms 63356
ТЕХНОЛОГИИ ДОСТ... 60108
Пример работы с... 59153
Имитационное мо... 55566
Реклама
Сейчас на сайте
Гостей: 17
На сайте нет зарегистрированных пользователей

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

Метод половинного деления для нахождения корня уровнения на Turbo Pascal...
Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...
Метод конечных разностей для интерполяции/экстраполяции на Delphi

Реклама



Подписывайся на 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 Комментариев · 1845 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Info
Форма в форме
RbControls
Billenium Effects...
Факториал [Исходн...
ComboBox97
IpEditAdress
PHP5. Профессиона...
Программирование ...
Динамические за...
Abbrevia
Модифицированная ...
Пример OpenGL гра...
Панель поиска
EMS QuickExport S...
WinPopup
Иллюстрированный ...
Импорт новостей ...
Электронный магаз...
Разработка клиент...

Топ загрузок
Приложение Клие... 100443
Delphi 7 Enterp... 85583
Converter AMR<-... 20065
GPSS World Stud... 12438
Borland C++Buil... 11512
Borland Delphi ... 8474
Turbo Pascal fo... 7020
Visual Studio 2... 4987
Калькулятор [Ис... 4722
FreeSMS v1.3.1 3533
Случайные статьи
Одной из мощных ко...
Раскрутка, путем р...
Invision Power Board
Подпрограмма Input...
Параметрические ко...
NetWare BinderyАут...
Что содержит конфи...
Блоки работы с лог...
Динамическая памят...
1.4.1. Адаптеры да...
Снова интерфейс и ...
5.2. АНТИПАТТЕРН: ...
Измерение бесплатн...
Об этой книге XXXII
Освоение приложени...
Выбор переключателя
Перестановка парам...
Структура компонен...
Событие OnDragDrop
Что Delphi знает о...
Выкуп авто
Файлы в Турбо Прол...
Старший и младший ...
Функция binary_sea...
Устройства тестиро...
Статистика



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


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