Навигация
Главная
Поиск
Форум
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
Создание отчето... 65024
Модуль Forms 64813
Пример работы с... 63181
ТЕХНОЛОГИИ ДОСТ... 61529
Имитационное мо... 57368
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

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

Моделирование работы ЭВМ на GPSS + Пояснительная записка
Информационная система - продуктовый магазин на Turbo Pascal (База данны...
Игра Sokoban на 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 Комментариев · 1893 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Самоучитель C++
Exe in exe
Globus VCL Extent...
PHP 5. Практика с...
WebReg v1.3
AboutSystem
Система баннеро-о...
ScreenSaver [Исхо...
WinPopup
Delphi 6 программ...
3d Tank [Исходник...
Strawberry Prolog...
DiZsubmit
Анекдоты с ostrie.ru
Delphi 2005 Учимс...
MicroGPSS Studen ...
PHP: Полезные приемы
Text3D
База игр
Графика в проекта...

Топ загрузок
Приложение Клие... 100464
Delphi 7 Enterp... 86597
Converter AMR<-... 20076
GPSS World Stud... 12626
Borland C++Buil... 11746
Borland Delphi ... 8555
Turbo Pascal fo... 7037
Visual Studio 2... 4998
Калькулятор [Ис... 4759
FreeSMS v1.3.1 3541
Случайные статьи
Более оптимальные ...
Приближение "нулев...
Тильда (~)
цифровую подпись с...
Триггеры операций ...
Целые числа: удиви...
Каковы правила игр...
Наша цель
Интернет магазин с...
Обзор текстовых ба...
Сообщения об ошибках
Литература - Проло...
Поток с использова...
Свойства информаци...
Ошибки неоднозначн...
4. Как изменить ср...
CN=Configuration, ...
Каталог алгоритмов
Обычный режим UNICAST
Глава 8. Базовы...
Разбиения множества
Модификации лэптопов
Функция GraphErrorMsg
Редактирование и у...
Настройка дизайн-т...
Статистика



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


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