Компиляция. Венский метод. Операционная семантика
Функциональный подход к программированию наиболее убедительно выражен в Венской методике определения языков программирования. Эта методика разработана в конце 60-х годов [[74]]. Основная идея - использование абстрактного синтаксиса и абстрактной машины при определении семантики языка программирования. Конкретный синтаксис языка отображается в абстрактный - анализ, а абстрактная машина может быть реализована с помощью конкретной машины - кодогенерация, причем и то, и другое может иметь небольшой объем и невысокую сложность. Сущность определения языка концентрируется в виде так называемой семантической функции языка, выполняющей переход от абстрактного синтаксиса к абстрактной машине - трансляцию.
При такой архитектуре компилятор можно рассматривать как три комплекта функций, обеспечивающих анализ программы, ее трансляцию и кодогенерацию. Главная задача анализа - обнаружить основные понятия и выделить, вывести или вычислить по тексту программы значения компонентов структуры, представляющей собой абстрактный синтаксис программы. Эта работа сводится к набору распознавателей и селекторов, названия которых могут быть выбраны в зависимости от смысла понятий, составляющих программу, а реализация варьируется в зависимости от конкретного синтаксиса языка. Тогда при любом конкретном синтаксисе разбор программы выполняется тем же самым определением, что и анализ ее абстрактного представления, которое играет роль спецификации. Любое определение анализа выглядит как перебор распознавателей, передающих управление композициям из селекторов, выбирающих существенные компоненты из анализируемой программы и заполняющих поля определенной структуры или значениями, или программами их вычисления. Содержимое полей предназначено для генерации кода программы, эквивалентной исходному тексту программы, а заодно и ее абстрактной структуре.
Например, если лисповскую форму PROG рассматривать как представление абстрактного синтаксиса для подмножества языка Паскаль, содержащего переменные, константы, арифметические операции и сравнения, пустой оператор, присваивание, последовательное исполнение операторов, условный оператор и безусловный переход goto, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики.
Селекторы имеют смысл лишь при истинности соответствующего распознавателя.
Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка
| (перем 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; |
Определение семантической функции, обеспечивающей корректную трансляцию абстрактного синтаксиса программы в ее абстрактный код, требует реализации соответствия между именами и их значениями в зависимости от контекста и предшествующих определений.
При интерпретации такое соответствие представлялось ассоциативным списком, в котором хранятся связи вида Имя-Смысл, преобразуемые по принципу стека, естественно отражающего динамику вызова функций. При компиляции не принято сохранять имена на время исполнения программы: их роль выполняют сопоставленные именам адреса. Поэтому вместо а-списка вида ((а . 1)(в . 2)(с . 3)...) применяется два списка (а в с ...) и (1 2 3 ...), хранящих имена и их значения на согласованных позициях. Обрабатываются эти два списка синхронно: оба удлиняются или сокращаются на одинаковое число элементов.
Можно переписать Eval-Apply с соответствующей коррекцией и определить функцию подстановки, заменяющую имена их значениями из синхронного списка.
Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).
Важно обратить внимание на учет изменения контекста при последовательном выполнении шагов программы, а также на несовпадение порядка в тексте с очередностью выполнения композиций функций.
Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).
| 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. Определение Лисп-компилятора на Лиспе
Современные методы организации компиляторов и систем программирования претерпевают значительные изменения под давлением изменяющихся условия эксплуатации ИС в сетях, на суперкомпьютерах и в мобильных устройствах. Возрастает роль компиляции "на лету" и организации высокопроизводительных вычислений на многопроцессорных комплексах.
