Навигация
Главная
Поиск
Форум
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
Содержание сайт... 65535
Вызов хранимых ... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Invision Power ... 65292
Организация зап... 63945
Модуль Forms 60857
Создание отчето... 60724
ТЕХНОЛОГИИ ДОСТ... 57045
Создание потоко... 56394
Пример работы с... 54285
Имитационное мо... 52494
Реклама
Сейчас на сайте
Гостей: 8
На сайте нет зарегистрированных пользователей

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

Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
Диплом RSA, ЭЦП, сертификаты, шифрование на C#
Создание последовательности окон и передвижение окон по экрану на Turbo ...

Реклама



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

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Система баннеро...
Х. М. Дейтел, П. ...
Delphix Sample [И...
Borland Delphi 8 ...
Анимированное поя...
HTMLredaktor
Панель поиска
Учебник для продв...
CodeGear RAD Stud...
JBlabel3D
Основы программир...
Динамические за...
Printgrid
Самоучитель C++
Apollovcl61
Encrypt Decrypt
Анекдоты с ostrie.ru
Работа с базами д...
Разработка клиент...
Последнее загруж...

Топ загрузок
Приложение Клие... 100376
Delphi 7 Enterp... 83096
Converter AMR<-... 20046
Borland C++Buil... 11180
GPSS World Stud... 10915
Borland Delphi ... 8128
Turbo Pascal fo... 6973
Visual Studio 2... 4963
Калькулятор [Ис... 4360
FreeSMS v1.3.1 3510
Случайные статьи
Ввод и вывод данны...
GUNZIP
Процедура поиска в...
Основные понятия О...
Еще одна программа...
Окна, шрифт
Протоколы L2TP и РРТР
СТРУКТУРНОЕ ПРОГРА...
Регистрация ActiveX
Полная статистика ...
Приведение типов
No more files
Сайты для обмена и...
4.1. ЦЕЛЬ: СОЗДАНИ...
Да, Microsoft чрез...
Фрирулетка и слоты...
Занятие 2. Аутенти...
Занятие 3
Пространство внутр...
Символы, используе...
15.5. Задачи
«пользователь всег...
Создание БД
Программы для созд...
Получи, клиент, ра...
Статистика



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


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