Непейвода Н.Н. Программирование. Раздел 2

Непейвода Н.Н. Программирование. Страница 155

Таким образом, даже столь простой пример показывает, что специализа­ция требует применения различных механизмов преобразования программ. Остаточная программа может оказаться короче или длиннее исходной, но она всегда будет, по крайней мере, не хуже исходной по времени выполнения.

Еще одно замечание. Решение 'заморозить' X в программе 3.9.1 было произвольным, но коль скоро оно принято, все остальные операторы, попав­шие в остаточную программу по индукции, были задержаны 'вынужденно', т. к. их термы зависели от замороженной переменной X.

Что изменилось бы в этих построениях, если бы они исходили из неим­перативной модели вычислений? Прежде всего, изменилось бы понятие ис­тории вычислений, а вслед за ним и то, что понимается под остаточной

программой. К примеру, в исходной программе на языке Prologмы бы уви­дели соотношения, рекурсивно задающие последовательность утверждений, логическая подстановка которых ведет к цели: к получению значения данной функции от двух переменных X и п в качестве запрашиваемого утверждения. Анализ истории подстановок при п = 5 покажет, что некоторые из утвержде­ний становятся лишними, раньше распознаются тупики. Это дает основание для сокращения программы, но здесь практически ничего не достичь без объединения утверждений и их эквивалентных преобразований.

В функциональном языке история вычислений — это последовательность подстановок аргументов функций и применения функций к аргументам. Некоторые из этих действий приводят к выбору конкретного варианта про­должения процесса в зависимости от перерабатываемых данных, иногда они могут быть вычислены заранее, если имеются сведения о данных. Анализи­руя историю, как и в операционном случае, можно определить, как нужно преобразовать программу, чтобы были учтены эти сведения, и, таким об­разом, построить остаточную программу. Программа функции F(x,n), реа­лизующая тот же алгоритм, что был представлен выше, при п — 5 за счет ликвидации разветвлений и раскрытия рекурсии приобретет примерно такой вид: _ _

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама