Парадигмы программирования

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


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

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

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

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

Таблица 13.1. Абстрактный синтаксис операторовАбстрактная формаКонкретная форма
(перем X)X
(конст C)C
(плюс А1 А2)(A1 + A2)
(равно А1 А2)(A1 = A2)
(пусто)
(присвоить X A)x := a;
(шаги S1 S2)S1; S2;
(если P ST SF)if p then ST else SF;
(пока P S)while p do S;
Все селекторы сводятся к композиции 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)).

Таблица 13.2. Примеры функциональной реализации операторов и выраженийОператорФункциональный эквивалентАбстрактный синтаксис оператора
C(lambda (v)c)
(конст C)
X

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

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

(плюс А1 А2)
(A1 = A2)

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

(равно А1 А2)
(пусто)



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

x := a;

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

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

(присвоить X A)
S1; S2;

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

(шаги S1 S2)
if e then ST else SF;

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

(если P ST SF)
while e do S;

Циклу соответствует безымянная функция, строящая внутренний контекст: (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))) ))

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

  • все аргументы убраны из стека;
  • результат выражения записан в стек.


(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)) ) ))

Листинг 13.3. Определение Лисп-компилятора на Лиспе

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