ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Основные конструкции ядра языка Pascal над целыми числами X Переменные 123 Константы C (A1 + A2) Вычисления (A1 = A2) Отношения ; Пустой оператор X := a Присваивание S1; S2 Последовательные операторы if p then ST else SF Ветвление while P do S Цикл var X Объявление переменной const C = 123 Объявление именованной константы proc Pr (V…) S Определение процедуры Pr (A…) Вызов процедуры Т а б л и ц а 5 31 Основные конструкции ядра Pure Lisp над списками 4 X Переменная (quote C) Константой может быть любое символьное выражение (atom X) Проверка символьного выражения на неделимость (eq X Y) Совпадение адресов (cond (P ST)…(T SF) ) Ветвление (lambda (X …) E…) Безымянная функция (defun F E) Именование функции (F A …) Вызов функции Унификация значений и функций позволяет в базовые средства не включать именование функций, рассматривая такой механизм как вспомогательную семантику «Категории объектов», которые появятся в более полном определении ЯП. Формально Defun можно свести к передаче параметра с помощью Lambda. Следует принять во внимание, что ЯП с общей абстрактной машиной (АМ) равномощны по пространству порождаемых процессов. Т а б л и ц а 6 Абстрактный синтаксис ядра языка Pascal над целыми числами представлен в форме списков X (value X) 123 (value 123) C (value C) var X (var X) const C = 123 (const C 123) (A1 + A2) (sum А1 А2) (A1 = A2) (eq А1 А2) ; (empty) или (NIL) 4 Может сам работать как свой АС. 32 X := a (set X A) S1; S2; (step S1 S2) if p then ST else SF; (if P ST SF) while p do S; (while P S) proc Pr (V…) S (let Pr (V …) S) Pr (A…) (Pr (A…)) Использование списков в качестве абстрактного синтаксиса позволяет распознаватели разных конструкций (var, const, sum, eq, empty, assign, step, if, while) свести к анализу головы списка, что снимает вопрос конструирования или разработки анализатора. Все селекторы (X,C,A1,A2,A,S1,S2,ST,SF,P,S) сводятся к композиции шагов доступа, выполняемых после соответствующего распознавателя. Такие определения, сводящиеся к выбору 2-го, 3-го или 4-го элементов списка, практически не требуют отладки, работают с первого предъявления. Конструкцию while можно в базовую семантику (БС) не включать, т.к. она сводима к func. Можно выделить вспомогательную семантику (ВС) «Представление итераций», которое в полном ЯП будет включать и другие форматы циклов. ЯП с общим АС семантически эквивалентны, они сравнимы по трудоѐмкости отладки программ. Различают два стиля задания семантики ЯП – семантика вычисления значений и семантика изменения состояний памяти. Основой определения интерпретатора для семантики вычисления значений является функция EVAL (evaluation), вычисляющая произвольные выражения языка с учетом состояния таблицы атомов ТА, устроенной как стек. Для семантики изменения состояний памяти функция EXEC (execution) выполняет ту же работу на базе двух устроенных как векторы таблиц TA и TF, раздельно хранящих значения переменных и определения процедур, соответственно. Универсальная функция, или интерпретация – это функция, которая может вычислять значение любой формы, включая формы, сводимые к вычислению любой заданной функции, применяемой к аргументам, представленным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.) Рассмотрим универсальную функцию eval от аргумента expr. Это выражение, являющееся произвольной вычислимой формой языка Lisp. 33 Такая универсальная функция должна предусматривать основные виды вычисляемых форм, задающих значения аргументов, а также представления функций в соответствии со сводом правил языка. При интерпретации выражений учитываются следующие решения, представленные при определении АС: – атом обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида x, elem, смысл которых зависит от контекста, в котором они вычисляются; – константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение «истина»; – условное выражение требует специального алгоритма для перебора предикатов и выбора нужной ветви; – остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций; – если функция представлена своим названием, то среди названий различаются имена встроенных элементарных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенных в программе; – для встроенных функций интерпретация сама «знает», как найти их значение по заданным аргументам, а для введенных в программе функций использует их определение, которое находит подобно переменной по имени в таблице атомов – в контексте 5 ; – если функция построена с помощью λ-конструктора, то, прежде чем еѐ применять, понадобится связывать переменные из λ-списка параметров со значениями аргументов; – если представление функции начинается с DEFUN, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Определения функций накапливаются в «хвосте» системной переменной ТА, то есть работают как глобальные определения. 5 Похоже на резервированные слова, но в реальных СП все функции (более тысячи) равноправно являются встроенными функциями. 34 Таким образом, интерпретация выражений осуществляется как взаимодействие четырех ВС: – обработка структур данных (cons, car, cdr, atom, eq); – конструирование функциональных объектов (lambda); – идентификация объектов (список параметров, set, defun); – управление логикой вычислений и частичными вычислениями (композиции, quote, cond, eval). Идентификация и управление отчасти привязаны к синтаксическим позициям без специальной лексики («синтаксический сахар»). В большинстве ЯП аналоги первых двух подсистем нацелены на обработку элементарных данных и конструирование составных значений, кроме того, иначе установлены границы между подсистемами. Явное определение универсальной функции позволяет достичь четкости механизмов обработки Lisp-программ. При написании на демонстрационном подмножестве Lispа определения функции EVAL согласно приведенной выше спецификации, задаѐтся переход от данного списочного представления выражения E к его значению с учетом заданной таблицы атомов ТА, хранящей значения атомов. Универсальная функция exec для минимального подмножества языка Pascal немного отличается: – атом понимается как переменная или константа; – константы строятся из так называемых литералов и могут быть поименованы; – условное выражение состоит из предиката и двух позиций для выбора нужной ветви; – существуют специальные формы для циклов, определения и вызова процедур и функций и другие схемы управления вычислениями; – выражения обрабатываются с учетом таблицы приоритетов операций и расстановки скобок; – определения переменных и функций или процедур хранятся раздельно. Основные различия: – exec не поддерживает безымянные функции; – eval не поддерживает присваивания переменным; – exec поддерживает раздельное хранение значений и определений функций/процедур; – eval допускает конструирование определений функций в процессе вычислений. 35 2.2. Абстрактная машина Особенности процесса компиляции достаточно сложны даже для простых языков, поэтому спецификация результата компиляции часто задается в терминах языково-ориентированных абстрактных машин (АМ). Система команд АМ представляет собой реализацию БС, дополненную рядом системных действий по передаче параметров и защите областей действия, подразумеваемых ЯП, но не имеющих чѐткого синтаксического представления. Такое определение может быть машинно-независимым и переносимым. АМ различает обычно следующие категории команд: – засылка значений из памяти в стек; – вычисления над безымянными операндами в стеке при обработке выражений; – пересылка значений из стека в память с учетом локализации; – организация ветвлений и циклов; – организация вызовов процедур и функций с сохранением/восстановлением контекста. Могут быть и другие категории команд. При сравнении императивного и функционального подходов к программированию, П. Лэндин (P.J. Landin) предложил специальную абстрактную машину SECD, удобную для спецификации машинно- зависимых аспектов семантики Lispа. Подробное описание этой машины можно найти в книге Хендерсона по функциональному программированию [15]. Машина SECD работает над четырьмя регистрами: стек для промежуточных результатов, контекст для размещения именованных значений, управляющая вычислениями программа, резервная память (Stack, Environment, Control list, Dump). Регистры приспособлены для хранения выражений в форме атомов или списков. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах изменения содержимого регистров при выполнении команд, что выражается следующим образом: s e c d → s' e' c' d' – переход от старого состояния к новому. Встраиваемые в ядро интерпретатора операции должны соответствовать стандартным правилам доступа к параметрам и размещения выработанного 36 результата. Таким же правилам должен подчиняться и компилируемый код. Это позволяет формально считать равноправными встроенные и программируемые функции. Компилятор по исходному тексту программы строит код программы, эквивалентный тексту. Для характеристики встроенных команд интерпретатора и результата компиляции программ базового Lisp-а понадобятся следующие команды: LD – ввод данного из контекста в стек; LDC – ввод константы из программы в стек; LDF – ввод определения функции в стек; AP – применение функции, определение которой уже в стеке; RTN – возврат из определения функции к вызвавшей ее программе; RAP – применение рекурсивной функции DUM – резервирование памяти для хранения аргументов рекурсивной функции. SEL – ветвление в зависимости от активного (верхнего) значения стека; JOIN – переход к общей точке после ветвления; CAR – первый элемент из активного значения стека; CDR – без первого элемента активное значение стека; CONS – формирование узла по двум верхним значениям стека; ATOM – неделимость (атомарность) верхнего элемента стека; EQ – равенство двух верхних значений стека; STOP – останов. Стек устроен традиционно по схеме «первый пришел, последний ушел». Размер стека не ограничен. Каждая команда абстрактной машины «знает» число используемых при ее работе элементов стека, которые она удаляет из стека и вместо них размещает выработанный результат. Исполняются команды по очереди, начиная с первой в регистре управляющей программы. Машина прекращает работу при выполнении команды «останов», которая формально характеризуется отсутствием изменений в состоянии машины: s e (STOP ) d → s e (STOP ) d Следуя Хендерсону, для четкого отделения обрабатываемых элементов от остальной части списка будем использовать следующие обозначения: – (x . L ) – это значит, что первый элемент списка – x, а остальные находятся в списке L; – (x y . L ) – первый элемент списка – x, второй элемент списка – y, остальные находятся в списке L и т. д. 37 Теперь мы можем методично описать эффекты всех перечисленных выше команд. s e(LDC q . c)d → (q . s) e c d (a b . s)e(CONS . c)d → ((a . b) . s) e c d ((a . b) . s)e(CAR . c) → (a . s) e c d ((a . b) . s)e(CDR . c) → (b . s) e c d Для предиката оговариваем, в каких случаях вырабатывается значение «истина». ((a . b) . s)e(ATOM . c)d → (NIL . s) e c d (A . s)e(ATOM . c)d → (T . s) e c d Для неатомарных значений – NIL, , т. е. ложь, истина «Т» - для атомов, (a a . s)e(EQ . c)d → (T . s) e c d (a b . s)e(EQ . c)d → (NIL . s) e c d Истина «Т» – для совпадающих указателей, для несовпадающих – NIL, т. е. ложь. Для доступа к значениям, расположенным в контексте, можно определить специальную функцию N-th, выделяющую из списка элемент с заданным номером N в предположении, что длина списка превосходит заданный адрес: s e (LD n . c) d → (x . s) e c d x – это значение (N-th n e ). При реализации ветвлений управляющая программа соответствует следующему шаблону: ( ... SEL ( ... JOIN ) ( ... JOIN ) ... ) Ветви размещены в подсписках с завершителем JOIN, после которых следует общая часть вычислений. Для большей надежности на время выполнения ветви общая часть сохраняется в дампе – резервной памяти, а по завершении ветви – восстанавливается в регистре управляющей программы: 38 (NIL . s) e (SEL c1 c0 . c) d → s e c0 (c . d) (T . s) e (SEL c1 c0 . c) d → s e c1 (c . d) s e (JOIN ) (c . d) → s e c d Организация вызова процедур требует защиты контекста от локальных изменений, происходящих при интерпретации тела определения. Для этого при вводе определения функции в стек создается специальная структура, содержащая код определения функции и копию текущего состояния контекста. До этого в стеке должны быть размещены фактические параметры процедуры. Завершается процедура командой RTN, восстанавливающей регистры и размещающей в стеке результат процедуры: s e (LDF f . c) d → ((f . e) . s) e c d ((f . ef) vf . s) e (AP . c) d → NIL (vf . ef) f (s e c . d) (x) e (RTN ) (s e c . d) → (x . s) e c d f – тело определения, ef – контекст в момент вызова функции, vf – фактические параметры для вызова функции, x – результат функции. Рекурсивные вызовы функций требуют резервирования памяти для уникальных ссылок на разные поколения фактических аргументов, что достигается путем размещения фиктивного объекта «ω», который функция rplaca, в порядке исключения, замещает на реальные данные: s e (DUM . c) d → s (ω . e) c d ((f . ef) vf . s) e (RAP . c) d → NIL (rplaca vf ef) f (s e c . d) Для SECD реализационное замыкание ядра включает в себя структуро- разрушающие функции rplaca и rplacd, размещающие свой результат непосредственно в памяти второго аргумента. Это требует соответствующих ветвей в определениях синтаксиса и интерпретатора, что можно рассматривать как шаг раскрутки СП. 39 Т а б л и ц а 7 Реализационное дополнение Pure Lisp Новая конструкция Значение Примечание Семантика (RPLACA x (y . z )) (x . z) Добавление новых операций над данными (RPLACD x (y . z)) (y . x) Таким же образом система команд АМ может быть расширена простым дополнением правил. Так, можно еѐ механизм распространить на другие типы данных, например, на целые числа: (a b . s)e(SUM . c)d → ((a + b) . s) e c d (a b . s)e(DIF . c)d → ((a - b) . s) e c d (a b . s)e(MUL . c)d → ((a * b) . s) e c d (a b . s)e(DIV . c)d → ((a / b) . s) e c d (a . s)e(ADD1 . c) → ((a + 1) . s) e c d (a . s)e(MIN1 . c) → ((a - 1) . s) e c d (a . s)e(NUMBER . c) → (t . s) e c d t – истинностное значение NIL или T. Соответствующее расширение ЯП может быть выполнено на уровне лексики, синтаксиса и семантики следующим образом. Т а б л и ц а 8 Расширение Pure Lisp и SECD средствами обработки чисел. Новая конструкция Значение Примечание Лексика Number = digit {digit} целое Новая область данных Синтаксис атом = Number Встраивание новой области в систему понятий ЯП Семантика (SUM x y) (x + y) Добавление операций над новыми данными (DIF x y) (x - y) (MUL x y) (x * y) 40 (DIV x y) (x / y) (ADD1 x y) (x + 1) (MIN1 x y) (x - 1) (NUMBER x) NIL или T Предикат, выделяющий числа Аналогичная машина для языков Pascal и Oberon содержит следующие команды: LD – ввод данного из контекста в стек промежуточных значений; LDC – ввод константы из программы в стек; LDP – ввод определения процедуры; LDW – ввод числа из памяти в стек; STW – сохранение значения в глобальной памяти; STE – сохранение значения в локальном контексте; RET – возврат из процедуры к вызвавшей ее программе; IF – ветвление в зависимости от активного (верхнего) значения стека; EQ – равенство двух верхних значений стека; LT – верхнее значение в стеке меньше, чем второе; INC – увеличение числа на 1; DEC – уменьшение числа на 1; SUB – вычитание из верхнего элемента стека; ADD – прибавление к верхнему элементу стека; MUL – произведение двух чисел; DIV – частное от деления верхнего элемента стека на второй элемент; BR – безусловная передача управления по абсолютному адресу; AP – применение процедуры к аргументам, расположенным в стеке; STOP – останов. Машина SECM, как и SECD, работает над четырьмя регистрами: стек для промежуточных значений, контекст для размещения аргументов, локальных значений переменных и регистра возврата, управляющая вычислениями программа, память (Stack, Environment, Control program, Memory). Регистры приспособлены для хранения данных в форме векторов или списков, не пересекающихся по фактическим адресам. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах изменения содержимого регистров при выполнении команд, что выражается следующим образом: s e c m → s' e' c' m' – переход от старого состояния к новому. 41 Теперь мы можем методично описать эффекты всех перечисленных выше команд. s e (LDC q . c)m → (q . s) e c m (a . s) e (INC . c)m → (a+1 . s) e c m (a . s) e (DEC . c)m → (a-1 . s) e c m (a b . s) e (ADD . c)m → (a+b . s) e c m (a b . s) e (SUB . c)m → (a-b . s) e c m (a b . s) e (MUL . c)m → (a*b . s) e c m (a b . s) e (DIV . c)m → (a/b . s) e c m (a a . s) e (EQ . c)m → (TRUE . s) e c m (a b . s) e (EQ . c)m → (FALSE . s) e c m (a b . s) e (LT . c)m → (t . s) e c m (TRUE . s) e (IF ct cf . c) m → s e (ct . c) m (FALSE . s) e (IF ct cf . c) m → s e (cf . c) m t имеет значение «TRUE» или «FALSE». Далее используем дополнительные обозначения: [x] – содержимое памяти по адресу x; e[n] – содержимое n-го элемента контекста; A(Pr) – число аргументов процедуры Pr; L(Pr) – число локальных переменных процедуры Pr; @c – адрес позиции «c» в программе; _ – Произвольное значение ( _ подчерк). s e(LDW x . c) m → ([x] . s) e c m s e (LD n . c) m → (e[n] . s) e c m (a . s) e (STW x . c) m → s e c (m[x]=a) (a . s) e (STE x . c) m → s (e[x]=a) c m s e (LDP @Pr. c) m → (@f L(Pr) A(Pr) . s) e c m (@Pr KL N a1 ... aN . s) e (AP . c) m → s ((KL+N) _ ... _ a1 ... aN @c . e) Pr m s (K e1 ... eK p . e) (RET . c) m → ( ) e p m s e(BR @Pr . c) m → s e Pr m Разница между SECD и SECM в основном сводится к операциям над данными. Кроме того, SECM имеет дополнительные команды по 42 непосредственной работе с памятью для реализации присваиваний и передаче управления для реализации итераторов. Обе абстрактные машины, как SECD, так и SECM, содержат, кроме образа базовых средств ЯП, дополнительные команды, обеспечивающие пересылки данных между регистрами и реализационные средства, поддерживающие эффективность реализации ЯП (rplaca, BR, метки и др.). В результате АМ способна выполнять вычисления несколько более широкого класса, чем задано БС данного ЯП. Это приводит к идее определения реализационного замыкания ЯП в соответствии с фактическими возможностями АМ. Такое замыкание выполняет роль ядра ЯП. Предстоящие шаги инкрементального, т. е. пошагового, процесса раскрутки СП могут быть связаны с расширением типов обрабатываемых данных, подключением удобных форматов управления вычислениями, специализацией особых категорий функций, созданием программного инструментария и т. д. до полного или практически достаточного покрытия ЯП его реализацией в СП. Дальнейшее развитие СП заключается в пошаговом расширении спектра обрабатываемых данных и присоединении ВС до полного покрытия ЯП его реализацией в СП. Каждую новую область данных подключают к АМ как комплект подпрограмм, реализующий предикат для выяснения принадлежности данного новой области и операции обработки данных. ВС, как правило, могут быть определены в терминах самого ЯП с помощью средств его ядра. Интеграция вспомогательной семантики новых компонент ЯП в ранее реализованную версию СП осуществляется комплексным включением ряда согласованных определений на всех уровнях определения ЯП: – дописывание БНФ; – добавление ветвей в определение интерпретатора; – дополнение АМ новыми командами. В случае SECM кроме образа БС фактически реализована работа с векторами и указателями (адреса в памяти). Поэтому реализационное замыкание учебного концентра языка Pascal естественно будет включать в себя обработку структур данных. Соответствующие, фактически поддержанные на уровне АМ, правила языка: Данные = array of AM: x[i] := y X := y [i] 43 *x := @y доступ по указателю к адресу. Допустимость таких операций существенно зависит от распределения памяти и независимости еѐ частей, что приводит к необходимости контроля границ памяти при индексировании векторов и доступе по указателю. Информация для такого контроля во многих ЯП представляется в форме предписания типа данных (ТД) переменным. Таким образом, реализационное замыкание ЯП над SECM включает в себя представление ТД для всех переменных, включая параметры процедур. Т а б л и ц а 9 |