Типичный способ реализации языка программирования заключается в реализации транслятора с языка программирования на язык команд целевой ЭВМ или на некоторый другой реализованный язык программирования, а также реализации поддержки исполнения.
В классификации, представленной в конце разд. 1.1, это соответствует реализации виртуального процессора. Применение оптимизации в процессе трансляции программ для императивных языков позволяет получать вполне эффективные программы. Однако для функциональных языков не удается достичь приемлемой эффективности даже с помощью изощренной оптимизации. Подобная перспектива неэффективности оттранслированной программы ожидает также и реализацию языка предикатного программирования P методом прямой автоматической трансляции.
Для языка P разрабатывается метод управляемой полуавтоматической трансляции применением последовательности трансформаций, преобразующих предикатную программу в эффективную императивную программу на императивном расширении языка P (см. разд. 6.11). Базовыми трансформациями являются:
· склеивание переменных, реализующее замену нескольких переменных одной;
· замена хвостовой рекурсии циклом;
· подстановка определения предиката на место его вызова;
· кодирование структурных объектов низкоуровневыми структурами с использованием массивов и указателей.
Для всех определений предикатов сначала применяется склеивание переменных, затем замена хвостовой рекурсии циклом. Тела предикатов с устраненной рекурсией подставляются на место вызовов. После этого можно провести другие упрощающие преобразования, в частности константные вычисления. Наконец, структурные объекты (списки, деревья и др.) кодируются посредством массивов и указателей. С помощью данных трансформаций можно получить программу предельной эффективности, однако трудно это сделать автоматически. На втором этапе полученная императивная программа конвертируется на любой из императивных языков: C, C++, ФОРТРАН и др. В настоящее время при программировании на языке P применяется метод ручной трансформации предикатной программы.
Трансформация замены хвостовой рекурсии циклом является весьма эффективной, поскольку открывает возможность применения серии других оптимизирующих преобразований. Однако рекурсия в наиболее простом решении задачи обычно не является хвостовой. Существует ряд подходов по приведению рекурсии к хвостовому виду, как правило, автоматическими преобразованиями. В технологии предикатного программирования предлагается универсальный метод обобщения исходной задачи для получения решения с хвостовой формой рекурсии. Этот метод нередко оказывается ключевым для эффективной реализации предикатных программ.
В программировании регулярно возникают ситуации, когда традиционными конструкциями языка программирования невозможно адекватно представить некоторый фрагмент алгоритма. Предлагаемый аппарат гиперфункций позволяет гибко декомпозировать программу произвольным образом.