В данном разделе будут рассмотрены вопросы, относящиеся к понятийному аппарату, истории развития, существующим подходам и выразительным возможностям семантического представления формальных теорий и языков программирования.
В ходе изложения будут рассмотрены важнейшие научные исследования, относящиеся к эволюции подходов к математическому моделированию семантического представления формальных теорий и языков программирования. При этом будет предпринята попытка классификации существующих видов семантики.
Далее будет представлено неформальное введение в наиболее адекватный целям этой книги и достаточно широко распространенный на сегодня подход к семантике, а именно, так называемый денотационный подход. Теоретические рассуждения о семантике в формальных теориях (на примере теории вычислений Д.Скотта) будут проиллюстрированы представлением денотационной семантики подмножества языка программирования SML, ограниченного наиболее важными, основополагающими конструкциями.
При этом существенное внимание будет также уделено сопоставлению и сравнительному анализу синтаксического и семантического аспектов наиболее важных с точки зрения программирования классов конструкций языка программирования SML.
Значение слова семантика. Что такое семантика.
Раздел завершится обзором литературы для более глубокого исследования материала.
Кратко остановимся на наиболее значительных (с точки зрения целей этой книги) этапах эволюции теории и практики семантического анализа языков программирования.
В 60-х г.г. X. Барендрегтом (Н. Barendregt) была детально описана семантика ламбда-исчисления — математической формализации, поддерживающей языки функционального программирования.
Позднее, в конце 60-х г.г., Д. Скоттом (Dana S. Scott) было предложено использовать для формализации семантики математических теорий так называемые домены (пока будем неформально понимать их как особый вид множеств). При этом на основе доменов Д. Скоттом был предложен так называемый денотационный подход к семантике. Такой подход предполагает анализ синтаксически корректных конструкций языка (или, иначе, денотатов) с точки зрения возможности вычисления их значений посредством специализированных функций.
Далее, в 70-х г.г., М. Гордоном (Michael J.C. Gordon) был исследован аппарат денотационной семантики применительно к языкам функционального программирования и сделал вывод об адекватности и практической эффективности применения этого подхода для решения поставленной задачи.
Параллельным направлением изучения семантики был подход, исследовавший изменения, которые происходили в процессе работы программы на основе отслеживания смены состояний программы.
Одним из практических результатов работ в этом направлении стала разработка П. Лендином (Peter J. Landin) семантики модели языка программирования в форме абстрактной машины, существенно использовавшей понятие состояния.
Альтернативный подход к формализации семантики (который был осуществлен в рамках исследования так называемой операционной семантики языков программирования) привел к созданию Ч. Хоаром (Charles A.R. Ноаге) аксиоматического метода, моделирующего отношения и причинно-следственные связи, возникающие между операторами языка программирования.
Э, что такое Общая семантика?
Развитие операционной семантики языков программирования привело Р. Флойда (Robert W. Floyd) к созданию так называемого метода индуктивных утверждений, который использовался для формализации семантики протекания информации в программе. При этом существенным преимуществом предложенного Р. Флойдом метода стала возможность интуитивно прозрачной и наглядной графической иллюстрации, основанной на блок-схемах, формализующих последовательность протекания информации.
Перейдем к рассмотрению неформальной семантики языков программирования.
Для построения адекватной и удобной в использовании семантики необходимо, прежде всего, определить критерии, характеризующие «хороший» язык программирования.
Попытаемся сформулировать обобщенные требования, предъявляемые к описанию языков программирования.
Во-первых, необходимо потребовать от языка программирования соблюдения принципа полноты, т.е. оснастить язык программирования таким набором конструкций, который позволяет описать синтаксис (и семантику) всех допустимых конструкций языка без пропусков существенных аспектов.
Во-вторых, язык программирования должен удовлетворять интуитивному требованию ясности, а именно, объективно обеспечивать удобочитаемость программ, а также легкость и результативность поиска ответов на вопросы, возникающие в процессе разработки программных проектов.
Немаловажной характеристикой языка программирования является естественность, под которой мы будем понимать интуитивную близость языка к терминологии разработчика, а также использование унифицированных, стандартных, привычных обозначений.
Наконец, необходимо учитывать и такой важный параметр, как реализм, который понимается как учет естественных ограничений на среду реализации языка программирования, а именно: объем оперативной памяти, время реакции и целый ряд других существенных факторов.
После обсуждения обобщенных и концептуально важных требований к языкам программирования в целом, перейдем к неформальному обсуждению семантического подхода, способного обеспечить реализацию этих требований.
Прежде всего, расширим наивное представление о семантике языка программирования (или формальной теории) хотя и предварительным, но более конкретным определением этого понятия.
Семантикой будем называть интерпретацию (или, иначе, смысловое значение) абстрактного синтаксиса (а точнее, множества допустимых видов конструкций языка), представленное в терминах той или иной математически строгой формальной модели.
Как оказывается, все многообразие возможных подходов к семантике можно в основном представить всего двумя типами семантик, а именно, семантиками, ориентированными на компиляцию и семантиками, ориентированными на интерпретацию.
В дальнейшем под подходами к семантике, ориентированными на компиляцию, будем понимать такие подходы, в которых семантика представляет собой множество преобразований над синтаксической моделью в той или иной форме.
В отличие от предыдущего подхода, под подходами к семантике, ориентированными на интерпретацию, будем понимать такие подходы, в которых семантика представляет собой множество описанных на специально построенном метаязыке преобразований синтаксически правильных конструкций языка программирования.
Сразу заметим, что целям этой книги в большей степени соответствует второй подход, как более универсальный в силу того обстоятельства, что в нем используется метатеория, т.е. формализация, моделирующая преобразования текста программ.
Выделим основные направления, существующие в рамках подхода к семантике, ориентированного на интерпретацию и свяжем их с рассмотренными нами в данном разделе направлениями исследований.
Оказывается, что существуют три основных вида семантик, ориентированных на интерпретацию.
Во-первых, необходимо упомянуть об операционных семантиках. Значение конструкций языка в таких семантиках выражается в терминах переходов той или иной абстрактной машины из одного состояния в другое. В качестве показательных примеров абстрактных машин можно привести, в частности, так называемую SECD-машину П. Лендина, а также категориальную абстрактную машину. Обе формализации будут детализированы ниже.
Другим типом семантик, ориентированных на интерпретацию, являются так называемые препозиционные семантики. В отличие от операционных семантик, значение конструкций языка в таких семантиках выражается в терминах множества формул, описывающих состояния объектов программы. В качестве примеров можно, привести, в частности, аксиоматический метод Хоара и метод индуктивных утверждений Флойда.
Наконец, наиболее значимым для нас типом семантик, ориентированных на интерпретацию, являются денотационные семантики, в которых смысл конструкций языка представляется в терминах абстракции функций, оперирующих состояниями программы. В частности, данный подход иллюстрирует теория вычислений Д. Скотта, основанная на семантических доменах, которую и предлагаем вашему вниманию.
Напомним, что теория вычислений Д. Скотта была создана до появления большинства современных языков программирования, а именно в конце 60-х г.г.
Существенно, что именно эта теория (в отличие от, скажем, классической логики и ряда других формальных систем) позволяет произвести адекватную (а именно, полную и непротиворечивую) формализацию семантики языков программирования.
Теория вычислений Д. Скотта основана на фундаментальном понятии домена, который будем пока неформально понимать как некоторый аналог множества, впрочем, в отличие от традиционных множеств, адекватно формализующий рекурсивно (т.е. на основе самоприменения) определенные функции и множества.
Сформулируем последовательность изложения теории вычислений Д. Скотта.
Для построения теории вычислений необходимо, во-первых, перечислить так называемые стандартные, или, точнее, наиболее часто используемые в рамках данной формализации, домены.
После перечисления стандартных доменов необходимо определить так называемые конечные домены, или, точнее, домены, элементы которых возможно перечислить явным образом.
Наконец, после перечисления доменов перейдем к определению конструкторов доменов, под которыми понимаются операции построения новых доменов на основе имеющихся, или, иначе, определим способы комбинирования доменов.
Перечислив основные типы элементарных доменов, перейдем к их комбинированию посредством конструкторов.
Заметим, что, подобно ламбда-исчислению и комбинаторной логике, теория вычислений обладает весьма лаконичным набором способов комбинирования доменов. Как мы увидим далее, существуют всего четыре типа конструкторов. Тем не менее, такой набор является вполне достаточным для построения домена, моделирующего семантику сколь угодно сложной предметной области или языка программирования.
Приведем определения перечисленных способов комбинирования доменов.
Под функциональным пространством из домена D, в домен D2 будем понимать домен [D1-»D2], содержащий всевозможные функции с областью определения из домена D] и областью значений из домена D2:
Под декартовым (или, иначе, прямым) произведением доменов D., D,, . Dn будем понимать домен всевозможных n-ок вида
Под последовательностью D* будем понимать домен всевозможных конечных последовательностей вида
из элементов d1,d„. dn, — домена D, где п>0.
Наконец, под дизъюнктной суммой будем понимать домен с определением
(v)Value = Int + Bool
Заметим, что состояние программы в произвольный момент времени определяется состоянием «памяти» абстрактной машины той или иной формы. При этом под памятью понимается отображение из домена идентификаторов в домен значений (т.е. аналог связывания переменной со значением в ламбда-исчислении). Для корректной обработки исключительных ситуаций, возникающих в случае свободных переменных, вводится дополнительный элемент unbound. Домен значений представляет собой дизъюнктную сумму доменов, содержащих существующие в языке SMalL типы Int и Bool.
В соответствии с намеченной схемой рассуждений, перейдем к описанию семантических предложений, которые описывают значение денотатов (т.е. правильно построенных конструкций) языка SMalL.
Приведем семантические предложения для выражений языка программирования SMalL:
Е : Exp —> [State [[Value х State] + ]];
E[E]s = (v,s’), если v — значение Е в s, s’- состояние после означивания;
E[E]s = error, если возникает ошибка несоответствия типов .
Из приведенных соотношений следует, что вычисление значения выражения языка программирования SMalL приводит к такому изменению состояния, что происходит связывание переменной со значением, либо (в случае невозможности связывания по причине несоответствия типов переменной и значения) вырабатывается ошибка. При этом состояние программы изменяется с s на s’.
Приведем семантические предложения для команд языка программирования SMalL:
С : Com [State —> [ State + ]] .
Из приведенных соотношений следует, что вычисление значения команды языка программирования SMalL приводит, вообще говоря, к изменению состояния, причем возможно возникновение ситуации (например, несоответствия типов в ходе присваивания), при которой вырабатывается ошибка.
В соответствии с намеченной схемой рассуждений, перейдем к описанию семантических предложений, которые описывают значение конкретных денотатов (т.е. правильно построенных конструкций) языка SMalL. Рассмотрим семантические предложения для денотатов констант целочисленного типа языка SMalL:
Как видно из приведенных соотношений, денотатами констант целочисленного типа являются значения этих констант (в форме упорядоченных пар вида «значение»-«состояние»), причем смены состояния программы не происходит. Рассмотрим семантические предложения для денотатов констант логического типа языка SMalL:
Е [true] s = (true, s);
Е [false] s = (false, s) ;
Как видно из приведенных соотношений, денотатами констант логического типа являются значения этих констант (в форме упорядоченных пар вида «зна-чение»-«состояние»), причем смены состояния программы не происходит. Рассмотрим семантическое предложение для денотатов идентификаторов языка SMalL:
Е [I] s = (m, I = unbound) error, —> (т, I, s) .
Как видно из приведенного соотношения, при возможности связывания денотатами идентификаторов являются идентификаторы, связанные со значениями (в форме упорядоченных троек вида «значение в памяти»-«идеитификатор»-«состояние»), причем смены состояния программы не происходит, а при невозможности — выдается сообщение об ошибке.
Рассмотрим семантические предложения для денотатов выражений языка SMalL:
Е [~Е] s = (Е [Е] s=(v, s’)) (isBool (not
v, s’ ) , error, si = (v2, S2) )
= (V2, S2)) -> error), error.
E [E1=E2] s = (E [E1]s = (vi, si)) -4- (E [E2]
—> (vi = V2, S2), error), error;
E [E1+E2] S = (E [El] S=(V1, Si)) (E [E2] SI
(IsNum vi and IsNum V2 —> vi + V2, S2), error),
Проанализируем полученные соотношения.
Денотатом отрицания выражения является отрицание его значения; причем состояние программы изменяется. В случае несоответствия типов или небуле-вости выражения генерируется сообщение об ошибке.
Денотатом присваивания является присвоенное значение в новом состоянии. В случае несоответствия типов генерируется сообщение об ошибке.
Денотатом сложения присваивания является значение суммы в новом состоянии. В случае несоответствия типов генерируется сообщение об ошибке.
В качестве упражнения предлагается самостоятельно разработать семантические предложения для денотатов команд языка программирования SMalL.
Кратко резюмируем итоги раздела.
В разделе была представлена классификация подходов к семантике языков программирования, признан целесообразным денотационный подход, который проиллюстрирован на примере языка SMalL — ограниченного подмножества SML.
По итогам обсуждения можно сделать следующие выводы:
- 1) семантика языков функционального программирования достаточно близка к семантике формальных теорий, на которых они основаны (в частности, это справедливо для ламбда-исчисления и языка SML);
- 2) теория вычислений является актуальной и адекватной формализацией семантики;
- 3) денотационный подход является наиболее целесообразным для моделирования семантики языков программирования.
К сожалению, в рамках раздела можно лишь в общих чертах охарактеризовать семантику языка программирования. Для более детального ознакомления с особенностями, достижениями и проблемами в области семантики рекомендуется следующий список литературы: [24], [35], [40], [42], [45], [52], [67], [70].
Кратко остановимся на источниках. Работа [24] является энциклопедией ламбда-исчисления, основной формализации языков функционального программирования. В работах [40,67] рассматриваются вопросы, связанные с развитием денотационной семантики, и в частности, с ее представлением посредством доменов. Работа [52] содержит формализацию системы вычислений, основанной на состояниях. В работе [45] представлен вариант операторного подхода к семантике в форме аксиоматического метода.
В работе [35] излагается метод индуктивных утверждений, одно из математических оснований операционной семантики. В работах [42,70] рассматриваются вопросы, связанные с основами и развитием денотационной семантики, в частности, с ее формальными моделями и их приложением к реализации языков программирования.
Задание к разделу
Задание: В чем состоит основное назначение семантики?
Ответ 1. Формализация вида и формы конструкций языка.
Ответ 2. Формализация значения конструкций языка (+).
Ответ 3. Формализация абстрактной машины для реализации языка.
Задание: Каковы требования к описанию формального языка?
Ответ 1. Ясность, полнота, естественность, реализм (+).
Ответ 2. Корректность, естественность, удобство использования.
Ответ 3. Строгость, полнота, простота, эффективность.
Задание: Что из перечисленного является формализацией семантики?
Ответ 1. Теория вычислений Д. Скотта (+).
Ответ 2. Комбинаторная логика Х.Карри.
Ответ 3. Абстрактная машина П.Лендина (+).
Вопрос 2.
Задание: Какая из теорий не является формализацией семантики?
Ответ 1. Аксиоматический метод Хоара.
Ответ 2. Формы Бэкуса-Наура (+).
Ответ 3. Метод индуктивных утверждений Р.Флойда.
Задание: Что понимается под семантикой?
Ответ 1. Модель интерпретации абстрактного синтаксиса (+).
Ответ 2. Модель реализации языка программирования.
Ответ 3. Модель предметной области.
Задание: На что ориентированы основные подходы к семантике?
Ответ 1. На компиляцию (+).
Ответ 2. На интерпретацию (+).
Ответ 3. На корректность типизации.
Вопрос 3.
Задание: Каковы виды семантик, ориентированные на интерпретацию?
Ответ 1. Операционные, препозиционные, денотационные (+).
Ответ 2. Операционные, композиционные, денотационные.
Ответ 3. Операционные, аппликативные, денотационные.
Задание: Какая формализация относится к денотационным семантикам?
Ответ 1. Теория вычислений Д. Скотта (+).
Ответ 2. Аксиоматический метод Ч. Хоара.
Ответ 3. Абстрактная машина П. Лендина.
Задание: Какая формализация относится к операционным семантикам?
Ответ 1. Теория вычислений Д. Скотта.
Ответ 2. Аксиоматический метод Ч. Хоара.
Ответ 3. Абстрактная машина П. Лендина (+).
Глава IV
Источник: bstudy.net
Семантика языков программирования
Существует несколько подходов к определению семантики языков программирования.
Наиболее широко распространены разновидности следующих трёх: операционного, денотационного (математического) и деривационного (аксиоматического).
При описании семантики в рамках операционного подхода обычно исполнение конструкций языка программирования интерпретируется с помощью некоторой воображаемой (абстрактной) ЭВМ.
Деривационная семантика описывает последствия выполнения конструкций языка с помощью языка логики и задания пред- и постусловий. Денотационная семантика оперирует понятиями, типичными для математики — множества, соответствия, а также суждения, утверждения и др.
Язык программирования строится в соответствии с той или иной базовой моделью вычислений и парадигмой программирования.
Несмотря на то, что большинство языков ориентировано на императивную модель вычислений, задаваемую фоннеймановской архитектурой ЭВМ, существуют и другие подходы. Можно упомянуть языки со стековой вычислительной моделью (Forth, Factor, Postscript и др.), а также функциональное (Лисп, Haskell, ML и др.) и логическое программирование (Пролог) и язык Рефал, основанный на модели вычислений, введённой советским математиком А.А. Марковым-младшим.
В настоящее время также активно развиваются проблемно-ориентированные, декларативные и визуальные языки программирования.
Компилируемые и интерпретируемые языки
Языки программирования могут быть разделены на компилируемые и интерпретируемые.
Программа на компилируемом языке при помощи специальной программы компилятора преобразуется (компилируется) в набор инструкций для данного типа процессора (машинный код) и далее записывается в исполнимый модуль, который может быть запущен на выполнение как отдельная программа. Другими словами, компилятор переводит исходный текст программы с языка программирования высокого уровня в двоичные коды инструкций процессора.
Если программа написана на интерпретируемом языке, то интерпретатор непосредственно выполняет (интерпретирует) исходный текст без предварительного перевода. При этом программа остаётся на исходном языке и не может быть запущена без интерпретатора. Можно сказать, что процессор компьютера — это интерпретатор машинного кода.
Кратко говоря, компилятор переводит исходный текст программы на машинный язык сразу и целиком, создавая при этом отдельную исполняемую программу, а интерпретатор выполняет исходный текст прямо во время исполнения программы.
Разделение на компилируемые и интерпретируемые языки является несколько условным. Так, для любого традиционно компилируемого языка, как, например, Паскаль, можно написать интерпретатор. Кроме того, большинство современных «чистых» интерпретаторов не исполняют конструкции языка непосредственно, а компилируют их в некоторое высокоуровневое промежуточное представление (например, с разыменованием переменных и раскрытием макросов).
Для любого интерпретируемого языка можно создать компилятор — например, язык Лисп, изначально интерпретируемый, может компилироваться без каких бы то ни было ограничений. Создаваемый во время исполнения программы код может так же динамически компилироваться во время исполнения.
Как правило, скомпилированные программы выполняются быстрее и не требуют для выполнения дополнительных программ, так как уже переведены на машинный язык. Вместе с тем, при каждом изменении текста программы требуется её перекомпиляция, что создаёт трудности при разработке. Кроме того, скомпилированная программа может выполняться только на том же типе компьютеров и, как правило, под той же операционной системой, на которую был рассчитан компилятор. Чтобы создать исполняемый файл для машины другого типа, требуется новая компиляция.
Интерпретируемые языки обладают некоторыми специфическими дополнительными возможностями (см. выше), кроме того, программы на них можно запускать сразу же после изменения, что облегчает разработку. Программа на интерпретируемом языке может быть зачастую запущена на разных типах машин и операционных систем без дополнительных усилий.
Однако интерпретируемые программы выполняются заметно медленнее, чем компилируемые, кроме того, они не могут выполняться без дополнительной программы-интерпретатора.
Некоторые языки, например, Java и C#, находятся между компилируемыми и интерпретируемыми. А именно, программа компилируется не в машинный язык, а в машинно-независимый код низкого уровня, байт-код. Далее байт-код выполняется виртуальной машиной. Для выполнения байт-кода обычно используется интерпретация, хотя отдельные его части для ускорения работы программы могут быть транслированы в машинный код непосредственно во время выполнения программы по технологии компиляции «на лету» (Just-in-time compilation, JIT). Для Java байт-код исполняется виртуальной машиной Java (Java Virtual Machine, JVM), для C# — Common Language Runtime.
Подобный подход в некотором смысле позволяет использовать плюсы как интерпретаторов, так и компиляторов. Следует упомянуть также оригинальный язык Форт(Forth) имеющий и интерпретатор и компилятор.
Современные языки программирования рассчитаны на использование ASCII, то есть доступность всех графических символов ASCII является необходимым и достаточным условием для записи любых конструкций языка. Управляющие символы ASCII используются ограниченно: допускаются только возврат каретки CR, перевод строки LF и горизонтальная табуляция HT (иногда также вертикальная табуляция VT и переход к следующей странице FF).
Подробнее по этой теме см.: Переносимый набор символов.
Ранние языки, возникшие в эпоху 6-битных символов, использовали более ограниченный набор. Например, алфавит Фортрана включает 49 символов (включая пробел): A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 = + — * / () . , $ ‘ :
Заметным исключением является язык APL, в котором используется очень много специальных символов.
Использование символов за пределами ASCII (например, символов KOI8-R или символов Юникода) зависит от реализации: иногда они разрешаются только в комментариях и символьных/строковых константах, а иногда и в идентификаторах. В СССР существовали языки, где все ключевые слова писались русскими буквами, но большую популярность подобные языки не завоевали (исключение составляет. Встроенный язык программирования 1С: Предприятие).
Подробнее по этой теме см.: Русские языки программирования.
Расширение набора используемых символов сдерживается тем, что многие проекты по разработке программного обеспечения являются международными. Очень сложно было бы работать с кодом, где имена одних переменных записаны русскими буквами, других — арабскими, а третьих — китайскими иероглифами. Вместе с тем, для работы с текстовыми данными языки программирования нового поколения (Delphi 2006, C#, Java) поддерживают Unicode.
Источник: studbooks.net
Лекция 9. Семантика языков программирования
Представим построение денотационной семантики важнейших функций языка программирования SML.
Напомним, что история развития теории и практики семантического анализа языков программирования была рассмотрена во вступительной лекции.
Прежде всего, рассмотрим неформальную семантику языков программирования.
Для построения адекватной и удобной в использовании семантики необходимо, прежде всего, определить критерии, характеризующие «хороший» язык программирования.
Попытаемся сформулировать обобщенные требования, предъявляемые к описанию языков программирования.
Во-первых, необходимо потребовать от языка программирования соблюдения принципа полноты, т.е. оснастить его таким набором конструкций, который позволяет описать синтаксис (и семантику) всех допустимых конструкций языка без пропусков существенных аспектов.
Во-вторых, язык программирования должен удовлетворять интуитивному требованию ясности, а именно, объективно обеспечивать удобочитаемость программ, а также легкость и результативность поиска ответов на вопросы, возникающие в процессе разработки программных проектов.
Немаловажной характеристикой языка программирования является естественность, под которой мы будем понимать интуитивную близость языка терминологии разработчика, а также использование унифицированных, стандартных, привычных обозначений.
Наконец, необходимо учитывать и такой важный параметр, как реализм, который понимается как учет естественных ограничений на среду реализации языка программирования, а именно, объем оперативной памяти, время реакции и целый ряд других существенных факторов.
После обсуждения концептуально важных требований к языкам программирования в целом перейдем к неформальному обсуждению семантического подхода, способного обеспечить реализацию этих требований.
Прежде всего, расширим представление о семантике языка программирования (или формальной теории) хотя и предварительным, но более конкретным определением этого понятия.
Семантикой будем называть интерпретацию (или, иначе, смысловое значение) абстрактного синтаксиса (а точнее, множества допустимых видов конструкций языка), представленное в терминах той или иной математически строгой формальной модели.
Оказывается, все многообразие возможных подходов к семантике можно в основном представить всего двумя типами семантик, а именно, семантиками, ориентированными на компиляцию, и семантиками, ориентированными на интерпретацию.
В дальнейшем под подходами к семантике, ориентированными на компиляцию, будем понимать такие подходы, в которых семантика представляет собой множество преобразований над синтаксической моделью в той или иной форме.
В отличие от предыдущего подхода, под подходами к семантике, ориентированными на интерпретацию, будем понимать такие подходы, в которых семантика представляет собой множество описанных на специально построенном метаязыке преобразований синтаксически правильных конструкций языка программирования.
Сразу отметим, что целям нашего курса в большей степени соответствует второй подход, как более универсальный в силу того обстоятельства, что в нем используется метатеория, т.е. формализация, моделирующая преобразования текста программ.
Выделим основные направления, существующие в рамках подхода к семантике, ориентированного на интерпретацию, и свяжем их с рассмотренными нами в ходе лекции направлениями исследований.
Оказывается, существует три основных вида семантик, ориентированных на интерпретацию.
Во-первых, необходимо упомянуть об операционных семантиках. Значение конструкций языка в таких семантиках выражается в терминах переходов той или иной абстрактной машины из одного состояния в другое. В качестве показательных примеров абстрактных машин можно привести, в частности, так называемую SECD-машину П. Лендина, а также категориальную абстрактную машину. Обе формализации будут рассмотрены подробнее в ходе дальнейших лекций.
Другим типом семантик, ориентированных на интерпретацию, являются так называемые пропозиционные семантики. В отличие от операционных семантик, значение конструкций языка в таких семантиках выражается в терминах множества формул, описывающих состояния объектов программы. В качестве примеров можно привести, в частности, аксиоматический метод Хоара и метод индуктивных утверждений Флойда.
Наконец, наиболее значимым для нас типом семантик, ориентированных на интерпретацию, являются денотационные семантики, в которых смысл конструкций языка представляется в терминах абстракции функций, оперирующих состояниями программы. В частности, данный подход иллюстрирует теория вычислений Д. Скотта, основанная на семантических доменах, которую мы и предлагаем вниманию читателя.
Напомним, что теория вычислений Д. Скотта была создана до появления большинства современных языков программирования, а именно в конце 60-х годов.
Существенно, что именно эта теория (в отличие от, скажем, классической логики и ряда других формальных систем) позволяет произвести адекватную (а именно, полную и непротиворечивую) формализацию семантики языков программирования.
Теория вычислений Д. Скотта основана на фундаментальном понятии домена, который будем пока неформально понимать как некоторый аналог множества, впрочем, в отличие от традиционных множеств, адекватно формализующий рекурсивно (т.е. на основе самоприменения) определенные функции и множества.
Сформулируем последовательность изложения теории вычислений Д. Скотта.
Для построения теории вычислений необходимо, во-первых, перечислить так называемые стандартные, или, точнее, наиболее часто используемые в рамках данной формализации, домены.
После перечисления стандартных доменов необходимо определить так называемые конечные домены, или, точнее, домены, элементы которых можно перечислить явным образом.
Наконец, после перечисления доменов перейдем к определению конструкторов доменов, под которыми понимаются операции построения новых доменов на основе имеющихся. Иначе говоря, определим способы комбинирования доменов.
Перечислив основные типы элементарных доменов, перейдем к их комбинированию посредством конструкторов.
Заметим, что, подобно ламбда-исчислению и комбинаторной логике, теория вычислений обладает весьма лаконичным набором способов комбинирования доменов. Как мы увидим далее, существует всего четыре типа конструкторов. Тем не менее, такой набор является вполне достаточным для построения домена, моделирующего семантику сколь угодно сложной предметной области или языка программирования.
Приведем определения перечисленных способов комбинирования доменов.
Под функциональным пространством из домена D1 в домен D2 будем понимать домен [D1->D2], содержащий всевозможные функции с областью определения из домена D1 и областью значений из домена D2 :
Под декартовым (или, иначе, прямым) произведением доменов
D1, D2, . Dn будем понимать домен всевозможных n-ок вида
Под последовательностью D* будем понимать домен всевозможных конечных последовательностей вида d=(d1,d2. dn) из элементов d1,d2. dn. домена D, где n>0.
Наконец, под дизъюнктной суммой будем понимать домен с определением
где принадлежность элементов di компонентам Di однозначно устанавливается специальными функциями принадлежности.
Поставим задачу формализации семантики языка функционального программирования SML. Отметим сразу, что в рамках данного курса будет рассматриваться не все множество возможных конструкций данного языка, а весьма ограниченное (хотя и вполне достаточное для иллюстрации основных идей курса) их подмножество, которое условно назовем языком программирования SMalL и будем именовать так в дальнейшем.
Прежде всего, рассмотрим синтаксис языка SMalL, т.е. перечислим основные типы конструкций, составляющих его.
Язык SMalL содержит множество выражений E, которые формализуются посредством БНФ в следующем виде:
E ::= true | false | 0 | 1 | I | -E |
Заметим, что выражения включают логические (true и false) и целочисленные (в ограниченном объеме: 0 и 1) константы, множество идентификаторов (I), а также операции отрицания (-E), сравнения (E1==E2) и сложения (E1+E2).
Кроме того, язык SMalL содержит множество команд С, которые формализуются посредством БНФ в следующем виде:
С ::= I=E | if (E) C1 else C2 |
Отметим, что команды включают присваивание (I=E), условие (if (E) C1 else C2), цикл с предусловием (while(E) C), а также последовательность команд (C1;C2).
Деление синтаксиса языка SMalL на выражения и команды во многом является условным и служит иллюстративным целям.
Как уже отмечалось, в качестве математической формализации, моделирующей семантику языков программирования (в частности, языка SMalL), будет использоваться теория вычислений Д. Скотта.
Приведем порядок построения формальной модели семантики языка программирования SMalL согласно ранее представленному формальному описанию синтаксиса языка в терминах БНФ.
Прежде всего, необходимо дать определение синтаксических доменов (т.е. доменов, характеризующих основные синтаксические категории) для идентификаторов (домен Ide), выражений (домен Exp) и команд (домен Com).
Далее, следует представить определение вычислительной модели на основе синтаксических доменов.
Затем необходимо перейти к определению семантических функций (E для домена Exp, C для домена Com и т.д.), которые отображают синтаксические конструкции языка программирования в соответствующие им семантические представления.
Наконец, следует сформулировать определение семантических предложений в терминах смены состояний программы.
Заметим, что при выполнении программы (в частности, написанной на языке программирования SMalL) происходит изменение состояния памяти (m, memory), которое в простейшем случае характеризует соответствие идентификаторов и значений (то есть, по сути, связывание переменной со значением), либо имеет значение unbound (характеризующее отсутствие связи идентификатора со значением, т.е. аналог свободной переменной).
В соответствии с намеченной схемой рассуждений перейдем к описанию синтаксических доменов, которые в полной мере определяют синтаксис языка SMalL:
Совокупность всех возможных идентификаторов языка SMalL организуем в домен Ide, команд — в домен Com, и, наконец, выражений — в домен Exp.
Далее, сформулируем вычислительную модель на основе состояний программы языка SMalL, для наглядности представив ее в виде следующей таблицы 8.1:
Таблица 8.1. Вычислительная модель на основе состояний программы языка SMalL
Источник: vuzlit.com