Языки программирования. Практический сравнительный анализ




Языки программирования. Практический сравнительный анализ - стр. 45


Вместе с тем по своей алгоритмической мощности аппликативные модели не уступают другим моделям вычислений.

Задача. Доказать, что модель М алгоритмически полна, т.е. для всякого нормального алгоритма А найдется эквивалентная ему рефал-программа (допускается заменять алфавит, в котором работает А).

Однако, пока наша модель М бедна в том отношении, что ко всем термам применяется одна и та же функции step. Это плохо и потому, что программу трудно понимать (особенно, если она длинная) и потому, что она будет медленно работать, если каждый раз просматривать все предложения поля определений.

К счастью, модель М легко приспособить к более гибкому стилю аппликативного программирования.

 

2.2.9. Структуризация поля определений; рефал-функции

Допустим, что имеется неограниченный набор различных пар функциональных скобок (как это можно обеспечить?). Будем группировать предложения, записывая подряд друг за другом такие предложения, левая часть которых заключена в одинаковые функциональные скобки.

Тогда ведущий терм будет однозначно указывать на соответствующую группу предложений (в ней и только в ней достаточно искать согласование).

В этом случае функция step распадается на отдельные функции, а программа - на определения этих функций (за что соответствующее поле, где помещается рефал-программа, мы и назвали полем определений).

Достаточно различать только левые функциональные скобки (почему?).

Будем считать левой функциональной скобкой название (идентификатор) функции вместе с непосредственно следующей за ним открывающей фигурной скобкой.

Например, программу перевода в ПОЛИЗ запишем так:

    перевод {e1+e2}R -> перевод {e1}  перевод {e2} +

         перевод {e1*e2}R -> перевод {e1}  перевод {e2} *

         перевод {(e)} -> перевод {e}

         перевод {e} -> e.

Такую совокупность подстановок естественно считать определением рефал-функции "перевод". Его удобно использовать в  большой программе среди других подобных определений.

Поле зрения с исходными данными для перевода может выглядеть при этом так:




Содержание  Назад  Вперед