Оптимизация программ

Смешанные вычисления

Идея смешанных вычислений с точки зрения реализации близка технике ленивых вычислений, но сложилась концептуально из несколько иных предпосылок, и именно из опыта разработки оптимизирующих трансляторов для языков высокого уровня []. Рассматривается пара Программа-Данные при недостаточных данных, отображаемая в так называемую остаточную программу, которая может дать нужный результат, если дать недостающие данные. Для определения такого отображения понадобилась разметка действий программы на исполнимые и задерживаемые. Если такую разметку не связывать с отсутствием данных, то получается модель, практически подобная вычислениям с задержками и возобновлением.

Не всегда неопределенность части данных мешает организовать вычисление. Рассмотрим

(If (< X Y) Z T)

или эквивалент

if X < Y then Z else T

Если X и Y не определены, но известно, что X лежит в интервале [1, 4], а Y в интервале [5, 6], то логическое выражение X<Y определено, и можно сделать вывод относительно выбора ветви условного выражения и, возможно, получить его значение.

Изучение смешанных вычислений может исходить из разных толкований понятия частичности, т.е. функций, определенных не на всей области их существования.

Первые работы Lombardi в этой области посвящены частичным вычислениям, т.е. обработке частично определенных выражений над числами. Реализация такой обработки на Лиспе осуществляла выполнимые операции и строила из полученных частичных результатов и невыполнимых операций некоторый промежуточный результат - выражение, доопределив которое, можно получить полный результат.

В работах по семантике стандартных языков программирования принято сведение к неопределенности значений любых операций, зависящих от неопределенных данных.

Это приводит на практике к необоснованным потерям части определенной информации и результатов.

A_1+...+A_100_000_000_000 + неопределенность -> неопределенность

Можно обратить внимание, что невелика практическая разница в уровне определенности данных вида (A …) и (A F), где F - рецепт вычисления, про который не всегда известно, приведет ли он к получению результата. Поэтому лучше было бы неопределенные данные "накрывать" рецептами, использующими специальные функции, нацеленные на раскрытие неопределенностей.

Например, роль такой функции может сыграть запрос у пользователя дополнительной информации:

(A …) => (A  . ||(read))

В определении интерпретатора обработка неопределенностей сосредоточена в функции ERROR.

(defun eval (e AL)
 …
      ((assoc e AL)(cdr (assoc e AL)))
      (T(ERROR '"неопределенная переменная"))
…
)

Определение функции ERROR можно доопределить обращением к READ, обрамленным сообщением о ситуации с информацией о контексте.

(defun apply (f  args  AL)
 …
       ((assoc f AL)(apply (cdr (assoc f AL))(evlis args AL)AL))
       (T (ERROR '"неопределенная функция"))
…
)

При отладке сложных комплексов часто неразработанные определения замещают временными "заглушками", которые помогают разобраться в будущей программе по частям. Такую работу можно стандартизировать заданием предварительных определений функций в виде отображения типа аргументов в тип результата. Соответственно, исполнение предопределенной таким образом функции можно интерпретировать как проверку аргументов на соответствие типу аргументов и выдачу в качестве результата вариантов значения, принадлежащего типу результата.

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

(cond (e  r)(T g)) => (assoc e (list (cons T (eval r AL))
                                     (cons Nil (eval g AL))) )

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

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

(defun f  (x y z a b c … v t u) (g …))
(defun Fi (x y z ) (f x y z ai bi ci … vi ti ui))

Примерно это и делает необязательный параметр вида optional.

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

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

X * 0 = 0
car (A …) = A
X*1 = X    ;; при любом X
X-X = 0
X/X = 1

Представление функции в некоторых точках при отладке можно задать ассоциативной таблицей:

(setq f '((a1 . r1)(a2 . r2)(a3 . r3) …))
(defun f (x) (assoc x f))

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

Возможны и другие, обеспечивающие оптимизацию, компиляцию, предвычисления, макрогенерацию текста программы, что в перспективе может покрыть полное пространство обработки программ в рамках единой методики. Например, основой единого подхода может быть так называемый трансформационный подход, заключающийся в сведении смешанных вычислений к преобразованию программ посредством набора базовых трансформаций.

Компилятор и требования к коду программы

Компиляция программ может рассматриваться как один из методов оптимизации процессов, осуществляемый как символьное преобразование - трансляция с исходного языка высокого уровня на язык низкого уровня, допускающий оптимизирующую кодогенерацию [,,,,,].

Описанная ранее абстрактная машина SECD удобна для спецификации машинно-зависимых аспектов семантики Лиспа. Такой подход позволяет не загромождать определение компилятора, добиться его прозрачности, но главное, такое определение может быть машинно-независимым и переносимым [].

В этом отношении следует отметить:

Компилятор - это средство оптимизации, позволяющее программам работать во много раз быстрее, чем было бы при интерпретации.

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

Программист получает следующие преимущества:

Последнее требование проясняет роль типового контроля в стандартных, ориентированных на компиляцию без интерпретации, системах программирования. Компиляция всех объектов осуществляется без анализа фактических данных, а это и означает, что на момент компиляции переменные, как правило, являются свободными. Интерпретация располагает более полной информацией, связывающей необходимые для вычислений переменные с конкретными значениями, тип которых определен.

Когда переменная используется как свободная, это значит, что она должна быть связана на более высоком уровне. При интерпретации функций может быть обнаружена переменная, не связанная вообще, о чем система известит пользователя соответствующим диагностическим сообщением об ошибке.

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

Компиляция. Венский метод. Операционная семантика

Функциональный подход к программированию наиболее убедительно выражен в Венской методике определения языков программирования. Эта методика разработана в конце 60-х годов []. Основная идея - использование абстрактного синтаксиса и абстрактной машины при определении семантики языка программирования. Конкретный синтаксис языка отображается в абстрактный - анализ, а абстрактная машина может быть реализована с помощью конкретной машины - кодогенерация, причем и то, и другое может иметь небольшой объем и невысокую сложность. Сущность определения языка концентрируется в виде так называемой семантической функции языка, выполняющей переход от абстрактного синтаксиса к абстрактной машине - трансляцию.

При такой архитектуре компилятор можно рассматривать как три комплекта функций, обеспечивающих анализ программы, ее трансляцию и кодогенерацию. Главная задача анализа - обнаружить основные понятия и выделить, вывести или вычислить по тексту программы значения компонентов структуры, представляющей собой абстрактный синтаксис программы. Эта работа сводится к набору распознавателей и селекторов, названия которых могут быть выбраны в зависимости от смысла понятий, составляющих программу, а реализация варьируется в зависимости от конкретного синтаксиса языка. Тогда при любом конкретном синтаксисе разбор программы выполняется тем же самым определением, что и анализ ее абстрактного представления, которое играет роль спецификации. Любое определение анализа выглядит как перебор распознавателей, передающих управление композициям из селекторов, выбирающих существенные компоненты из анализируемой программы и заполняющих поля определенной структуры или значениями, или программами их вычисления. Содержимое полей предназначено для генерации кода программы, эквивалентной исходному тексту программы, а заодно и ее абстрактной структуре.

Например, если лисповскую форму PROG рассматривать как представление абстрактного синтаксиса для подмножества языка Паскаль, содержащего переменные, константы, арифметические операции и сравнения, пустой оператор, присваивание, последовательное исполнение операторов, условный оператор и безусловный переход goto, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики. Селекторы имеют смысл лишь при истинности соответствующего распознавателя.

Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка

Все селекторы сводятся к композиции car-cdr, выполняемой после соответствующего распознавателя. Так, в приведенных выше формах поля X, C, A1, S1, P можно выделить селектором, определенным как (lambda (fm) (car(cdr fm))) - выделение второго элемента списка, а поля A2, S2, ST, S, расположенные третьими в списках - как (lambda (fm) (car(cdr(cdr fm)))), поле SF - как (lambda (fm) (car(cdr(cdr(cdr fm))))). Такие определения практически не требуют отладки, работают с первого предъявления.

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

При интерпретации такое соответствие представлялось ассоциативным списком, в котором хранятся связи вида Имя-Смысл, преобразуемые по принципу стека, естественно отражающего динамику вызова функций. При компиляции не принято сохранять имена на время исполнения программы: их роль выполняют сопоставленные именам адреса. Поэтому вместо а-списка вида ((а . 1)(в . 2)(с . 3)...) применяется два списка (а в с ...) и (1 2 3 ...), хранящих имена и их значения на согласованных позициях. Обрабатываются эти два списка синхронно: оба удлиняются или сокращаются на одинаковое число элементов.

Можно переписать Eval-Apply с соответствующей коррекцией и определить функцию подстановки, заменяющую имена их значениями из синхронного списка.

Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).

Важно обратить внимание на учет изменения контекста при последовательном выполнении шагов программы, а также на несовпадение порядка в тексте с очередностью выполнения композиций функций.

Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).

(lambda (v) (assoc-i X N v))
N - свободная переменная, задающая список имен, известных в программе

(lambda (v) (+(Е А1)(У А2)))

(lambda (v)(=(Е А1)(У А2)))

(lambda (v)v)
 Состояние памяти неизменно

Замена происходит по указанному адресу

(lambda (v)(replace N v X (E A)))

(lambda (v) (E S2 (E S1 v)))

(lambda (v) (funcall 
     (cond (((E P)v)
                (E S1))
            (T(E S2)) ) v)

Циклу соответствует безымянная 
функция, строящая внутренний
контекст:
(lambda (W) ((lambda (v)
         (cond (((E P)v)(w ((E S)v)))
                   (T v)))
 (lambda (v)
        (cond (((E P)v) (w ((E S)v)))
                  (T v)))  ))

При определении компилятора на уровне абстрактной машины должно быть выделено описание реализационного минимума языка Лисп, послужившего базой для раскрутки Лиспа и основой для функционального программирования. Необходимо лишь ввести некоторые ограничения, гарантирующие при переходе к низкоуровневому программированию сохранение важнейших свойств функциональных программ. Эти ограничения формулируются как чистый результат правильного выражения:

(defun compile-(s)(append (comp- s Nil)"(Ap Stop)))

(defun comp- (S N)(cond

   ((atom S)   (list "LD (adr S N)))

   ((eq (car S)"QUOTE) (list "LDC (cadr S)))
   ((eq (car S)"CONS)   (append (comp-(caddr S)N) (comp-(cadr S)N) "CONS))
   ((eq (car S)"CAR)     (append (comp-(cadr S)N) "CAR))
   ((eq (car S)"+)        (append (comp-(cadr S)N) (comp-(caddr S)N) "ADD))

   ((eq (car S)"IF)    (let  ( (then (list (comp-(caddr S)N) "(JOIN)))
                                     (else (list (comp-(cadddr S)N) "(JOIN))))
                                    (append (comp-(cadr S)N) (list "SEL then else))))

   ((eq (car S)"LAMBDA)  (list "LDF (comp-(caddr S) (append (cadr S) N)) "RTN))

   ((eq (car S)"LET)    (let*   ((args (value (cddr S)))
                                      (mem (cons (var (cddr S)) N))
                                      (body (append (comp-(cadr S)mem) "RTN)))
                                    ((append (map #"(lambda(x)(comp- x N)) args)
                                             (list body 'AP)))))

   ((eq (car S)"LABEL) (let* ((args (value (cddr S)))
                                     (mem (cons (var (cddr S)) N))
                                     (body (append (comp-(cadr S)mem) "RTN)))
                                   ((append "(DUM) (map #"(lambda(x)(comp- x mem)) args)
                                                         (list "LDF body "RAP)))))

   (T (append (map #"(lambda(x)(comp- x N)) (cdr S))
               (list body "AP)) )
))

Современные методы организации компиляторов и систем программирования претерпевают значительные изменения под давлением изменяющихся условия эксплуатации ИС в сетях, на суперкомпьютерах и в мобильных устройствах. Возрастает роль компиляции "на лету" и организации высокопроизводительных вычислений на многопроцессорных комплексах.