Навигация
Главная
Поиск
Форум
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
21 ошибка прогр... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Имитационное мо... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Реклама
Сейчас на сайте
Гостей: 9
На сайте нет зарегистрированных пользователей

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

Выбор наилучших альтернатив с использованием методов оптимизации на Delp...
Медиа плейер на Delphi + Пояснительная записка
Моделирование регулировочного участка цеха на GPSS + Пояснительная записка

Перестановка параметров
Задача 18.1 Для исходного определения:
el = Y (λel.λnλs.IF(= n1)(hd s)(el(− n 1)(tl s)))



получить выражение с оптимальным (по двум критериям) упорядо-
чением параметров комбинатора.
Решение. Напомним, что двумя основными критериями оптимально-
сти порядка параметров комбинатора являются минимальное число
МСВ и максимальное устранение избыточных параметров. Оптими-
зируем наше определение последовательно по обоим критериям.
opt--1. Для максимизации размера и минимизации числа МСВ сле-
дующего вложенного λ -выражения все МСВ подвергаемого
компиляции λ -выражения, которые в то же самое время
являются свободными выражениями следующего вложенного
λ -выражения, должны появиться прежде МСВ, не обладаю-
щих указанным свойством. Оптимальное упорядочение пара-
метров по этому критерию можно сформулировать следую-
щим образом. Все Ei являются свободными выражениями λ
-выражения, которое подлежит компилированию, однако оно
может быть свободным выражением одного или большего
числа вложенных λ -выражений. Назовем самое внутреннее
λ -выражение, в котором выражение Ei не является свобод-
ным, порождающим λ -выражением. Если порождающее λ -
выражение Ei включает порождающее λ-выражение Ej, то
в оптимальном упорядочении Ei предшествет Ej. Отсюда
не следует, что с необходимостью однозначно определяется
оптимальное упорядочение, поскольку выражения с одним и
тем же порждающимλ-выражением могут входить в любом
порядке. Тем не менее всякое упорядочение, удовлетворяющее
этому условию, является оптимальным, как и всякое другое.
opt--2. Рассмотрим аппликативную форму (alpha(hd s)n(tl s)),
в которой параметры alpha можно расположить в любом
порядке. Если непосредственно вложенное λ -выражение свя-
зывает n , то максимальные свободные выражения (МСВ)
из формы представляют собой (alpha(hd s)) и (tl s). Если же
выполнить переупорядочение формы вида(alpha(hd s)(tl s)n),
то МСВ единственно:
(alpha(hd s)(tl s)).



opt--3. Если, с другой стороны, непосредственно вложенное λ -
выражение связывает s, то оптимальным упорядочением па-
раметров служит
(alpha n (hd s)(tl s)),



откуда единственное МСВ представляет собой (alpha n).
opt--4. Получив оптимальное упорядочение по одному критерию,
обратимся к другому. В качестве “естественных” параме-
тров можно принять
alpha beta el hd tl.



Компилятор должен так расположить параметры, чтобы
происходило максимальное устранение избыточных параме-
тров. У компилятора только тогда есть выбор, когда один
комбинатор прямо определяется как вызов другого. В каче-
стве примера рассмотрим редукцию:
beta p q r s → alpha . . . s . . . .



Кроме последнего параметра, других избыточных параметров
нет, но последний параметр комбинатора всегда должен быть
связанной переменной того λ -выражения, из которого был
осуществлен вывод. В данном случае параметр s является
связанной переменнойλ-выражения, непосредственно включа-
ющего alpha. Если параметры уже упорядочены оптимально
по рассмотренным правилам, то все параметры, в которых
участвует s, перемещаются в конец его списка параметров.
Если имеется только один такой параметр, и это s, то s
оказывается избыточным параметром beta и может быть
устранен. На этом основании вызов alpha следует задавать
в виде (alpha E1 . . . En s), где s не имеет вхождений ни в
одно из выражений Ei. Это означает, что все Ei свободны в
beta, что распространяется и на (alpha E1 . . . En s). Следо-
вательно, фактически, если имеются какие-либо Ei, то beta
надо определить посредством редукции
beta p s → p s,



где p соответствует (alpha E1 . . . En s). Если у alpha един-
ственный параметр s, то beta следует определять посред-
ством beta s → s.
В первом случае beta эквивалентен комбинатору I. Порожда-
ющее beta λ -выражение замещается на аппликацию
(beta(alpha E1 . . . En s)),



то есть на (I(alpha E1 . . . En s)). Кроме того, beta мож-
но целиком опустить, и λ -выражение замещается непосред-
ственно на (alpha E1 . . . En s).
Во втором случае beta эквивалентно alpha. Можно видеть,
что оптимальное упорядочение, получаемое по второму кри-
терию, удовлетворяет также первому и, кроме того, суще-
ственно упрощает работу по нахождению избыточных па-
раметров.
opt--5. Рассматриваемое выражениеelопределяется равенством:
el = Y (λel.λn.λs.IF(= n 1)(hd s)(el(− n 1)(tl s))).



У самого внутреннего λ -выражения имеются два МСВ:
(IF(= n 1)) и (el(− n 1)).



Примем их за параметры p и q. Оба этих МСВ имеют одно
и то же порождающее λ -выражение, поэтому их порядок
несущественен, и alpha можно определить редукцией:
alpha p q s → p(hd s)(q(tl s)),



поэтому
el = Y (λel.λn.alpha(IF(= n 1))(el(− n 1))).



Теперь оказывается, что у следующего λ-выражения только
одно МСВ и это el. Следовательно, beta определяется редук-
цией

beta el n → alpha (IF(= n 1))(el(− n 1)),



по которой
el = Y (λel.beta el).



Далее следует применять редукцию
gamma el → beta el,



и поскольку комбинатор gamma эквивалентен комбинатору
beta, то gamma порождать не следует.
Окончательно получаем, что gamma эквивалентен (Y beta).
Контрольные вопросы.
1. Какие преимущества дает использование правил оптимизации?
2. Назовите два основных критерия оптимизации.
3. На что влияет порядок параметров суперкомбинаторов?
Упражнение. Получить выражение с оптимальным порядком супер-
комбинаторов для определения:
f ac n = IF n = 0 then 1 else n×(f ac(n−1)).


Опубликовал Kest May 13 2014 23:12:52 · 0 Комментариев · 3355 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
JanComp
Delphi 2005 для .NET
Панель Наша Кнопка
Программирование ...
Расширенный загру...
Trojan [Исходник ...
EditButton
Rotolabel
Geo-Whois
Matrix2D
Меню проводника в...
Borland Delphi 6....
Самоучитель PHP 5...
DS_Group
PDF
MP3 Архив v.2.0
Bitmap [для кнопок]
Панель для реклам...
100 компонентов о...
DirHTMLReportBuil...

Топ загрузок
Приложение Клие... 100771
Delphi 7 Enterp... 97788
Converter AMR<-... 20259
GPSS World Stud... 17014
Borland C++Buil... 14186
Borland Delphi ... 10267
Turbo Pascal fo... 7372
Калькулятор [Ис... 5968
Visual Studio 2... 5205
Microsoft SQL S... 3661
Случайные статьи
Ограничение ущерба
Язык программирова...
Сообщения имеют сл...
Casino Parimatch
Главная угроза веб...
Закон поглощения л...
Мягкая мебель
Windows Server 200...
The Bat!
12.4. Принципы
Инкремент и декремент
Как быть, если мас...
Очистка кэша в Int...
Онлайн казино Вулкан
Введение в язык XSLT
Капри – итальянска...
Осуществление запи...
Где купить сила им...
Официальный сайт к...
Ускорение процедур...
Безызбыточное коди...
Определение кодово...
А.4. ЗДРАВЫЙ СМЫСЛ
Тепловой фронт
Настройка фонового...
Статистика



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


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