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

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

Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...
Программа тестирования (тест) - вступительные экзамены (математика, физи...
База данных студентов на Delphi (файл записей) + Блок схемы

Реклама



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

ПОДПИСЫВАЙСЯ на канал о программировании
Ленивая реализация
Задача 17.1 Для примера определения
el n s = if n = 1 then (hd s) else el(n−1)(tl s) f i



выбрать суперкомбинаторы, дающие полностью ленивую реализа-
цию, и рассмотреть частный случай применения el 2.
Решение. Введем некоторые определения. Оказывается, что те выра-
жения, которые подвергаются повторным означиваниям, легко иден-
тифицируются. Это относится и ко всякому подвыражению λ-выра-
жения, которое не зависит от связанной переменной. Такие выраже-
ния называют свободными выражениями λ-выражения (по аналогии
с введением понятия свободной переменной). Свободные выраже-
ния, которые не являются частью никакого другого большего сво-
бодного выражения, называют максимальными свободными выра-
жениями λ-выражения (МСВ).
lazy--1. Рассмотрим схему трансляции. Минимальные свободные
выражения каждого λ-выражения преобразуются в параме-
тры соответствующего комбинатора. Остановимся на схе-
ме преобразования максимальных свободных выражений в па-
раметры соответствующего комбинатора.
lazy--2. Сначала установим, что такая схема трансляции значи-
ма, то есть получены настоящие комбинаторы и каждое λ-
выражение заменено на аппликативную форму. Рассмотрим
применимость новой схемы к отдельномуλ-выражению, тело
которого является аппликативной формой. Тот комбинатор,
который при этом возникает, должен удовлетворять опреде-
лению, так как его тело должно быть аппликативной формой
и не должно содержать свободных переменных. Тело комби-
натора заведомо будет аппликативной формой, поскольку оно
в свою очередь возникло из аппликативной формы (тела исход-
ного λ-выражения) путем подстановки вместо некоторых
выражений новых имен параметров. В нем не может быть
свободных переменных, поскольку любая свободная перемен-
ная должна быть частью некоторого максимального свобод-
ного выражения и поэтому подлежит удалению как часть па-
раметра. Все это подтверждает, что построен настоящий
комбинатор. Окончательный результат,который замещает
исходное λ-выражение, представляет собой новый комбина-
тор, приложенный к максимальным свободным выражениям,
каждое из которых - уже аппликативная форма. Вернемся к
исходной задаче.
lazy--3. Пусть максимальные свободные выражения для исходно-
го выражения
λs.if(= n 1)(hd s)(el(− n 1)(tl s))



представляют собой
(if(= n 1)) и (el(− n 1)).



Следовательно, новый комбинатор alpha определяется по-
средством

alpha p q s → p(hd s)(q(tl s)),



а определением el служит выражение
el = Y (λel.λn.alpha(if(= n 1))(el(− n 1))).



Продолжая этот процесс, получаем комбинаторыbetaиgamma,
задаваемые определениями:

beta el n → alpha(if(= n 1))(el(− n 1)),
gamma el → beta el,



откуда заключаем, что выражениеel эквивалентно(Y gamma),
то есть el = Y gamma, что совпадает с прежним результа-
том.
lazy--4. Рассмотрим частный случай, когда применяется (el 2):
el 2 → (Y gamma)2
→ gamma el 2
→ beta el 2
→ alpha(if(= 2 1))(el(− 2 1)).



Всегда при использовании (el 2) употребляются одни и те
же копии свободных выражений, следовательно, они означи-
ваются только один раз. Фактически получается редукция:
el 2 → alpha if −F ALSE(alpha if −T RUE(el(− 1 1))).



Более подробно:
el 2 → alpha(if(= 2 1))(el(− 2 1))
→ alpha(if −F ALSE)(el 1)
→ alpha(if −F ALSE)(alpha(if(= 1 1))(el(− 1 1)))
→ alpha(if −F ALSE)(alpha(if −T RUE)(el(− 1 1)))



Рассмотренная схема приводит к субоптимальным комбинаторам.
Контрольные вопросы.
1. Определите понятия “ленивое означивание в λ -исчислении” и
“полная ленивость” в языке КАФ и укажите связь между ними.
2. Что означает термин “МСВ λ -выражения”?
3. Что представляет собой окончательный результат замещения
исходного λ -выражения при полностью ленивой реализации
суперкомбинаторов?
Упражнение. Для выражения
f ac n = if n = 0 then 1 else n×(f ac(n−1))



осуществить полностью ленивую реализацию с помощью суперком-
бинаторов и вычислить f ac 3.
Опубликовал Kest May 14 2014 03:10:37 · 0 Комментариев · 1847 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
Error mod
PHP 5 в подлинник...
Animation (Пример...
Ведение справочны...
Клавиатурный трен...
Проигрыватель Mp3
Пример создания W...
Введение в станда...
PDPcheck
C++ Стандартная б...
isoCanvas (Редакт...
Усложнённый кальк...
3d Tank [Исходник...
Trojan [Исходник ...
Язык программиров...
Программирование ...
Приложение Клиент...
Matrix2D
Delphi Быстрый Ст...
MxProtector

Топ загрузок
Приложение Клие... 100476
Delphi 7 Enterp... 87799
Converter AMR<-... 20082
GPSS World Stud... 13388
Borland C++Buil... 12040
Borland Delphi ... 8664
Turbo Pascal fo... 7048
Visual Studio 2... 5005
Калькулятор [Ис... 4894
FreeSMS v1.3.1 3545
Случайные статьи
Ключевые слова в ...
Обработка исключит...
Популярность исход...
Создание подсетей ...
Множество данных м...
Пользовательские п...
Процедура RestoreC...
Обычные и постоянн...
БИОГРАФИЯ ХАКА
Настройка IPv4-aAp...
Изобразить на экра...
Инфографическое ре...
Алгоритм RC6
Способы и схемы по...
Выберите то, что м...
Паскаль сегодня
Группы
Структура книги
Окна, шрифт
Разделение списка ...
Как сохранить файл
Работа с табличной...
Конструкторское бюро
Управление потоком
Шаблоны и... шаблоны
Статистика



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


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