Определение языков программирования
Прежде чем анализировать конкретные парадигмы программирования, рассматривается задача определения систем программирования. Строится простейшее определение семантики языка программирования в виде интерпретатора, задающего операционную семантику на примере подмножества языка Лисп.
Обычно при разработке системы программирования различают три уровня: синтаксис, семантика и прагматика реализуемого языка. Разграничение уровней носит условный характер, но можно констатировать, что синтаксис определяет внешний вид программ, семантика задает класс процессов, порождаемых программами, а прагматика реализует процессы в рамках конкретных условий применения программ. При изучении парадигм программирования центральную роль играет семантика, а синтаксис и прагматика используются как вспомогательные построения на примерах. Венская методика определения языков программирования с помощью операционной семантики, использующей концепции программирования при спецификации систем программирования, удобна для сравнения парадигм программирования [[74]].
Венский метод (ВМ) определения языков программирования был разработан в 1968 году в Венской лаборатории IBM под руководством П. Лукаса на основе идей, восходящих к Дж. Маккарти [[74],[75]]. Благодаря хорошо разработанной концепции абстрактных объектов, позволяющей концентрировать внимание лишь на существенном и игнорировать второстепенные детали, Венский метод годится для описания и машин, и алгоритмов, и структур данных, особенно при обучении основам системного программирования. По мнению В.Ш. Кауфмана Венский метод вне конкуренции в области описания абстрактных процессов, в частности, процессов интерпретации программ на языках программирования. Согласно концепции абстрактных объектов (абстрактный синтаксис, абстрактная машина, абстрактные процессы) интерпретирующий автомат содержит в качестве компоненты состояния управляющую часть, содержимое которой может изменяться с помощью операций, подобно прочим данным, имеющимся в этом состоянии [[53]].
Модель автомата с состояниями в виде древовидных структур данных, созданного согласно Венской методике для интерпретации программ, является достаточно простой. Тем не менее она позволяет описывать основные нетривиальные понятия программирования, включая локализацию определений по иерархии блоков вычислений, вызовы процедур и функций, передачу параметров. Такая модель дает представление понятий программирования, полезное в качестве стартовой площадки для изучения разных парадигм программирования и сравнительного анализа стилей программирования.
Определение языка программирования (ЯП) по Венской методике начинается с четкого отделения существа семантики от синтаксического разнообразия определяемого языка [[74]]. С этой целью задается отображение конкретного синтаксиса (КС) ЯП в абстрактный (АС), вид которого инвариантен для семейства эквивалентных языков.
Семантика ЯП определяется как универсальная интерпретирующая функция (ИФ), дающая смысл любой программе, представленной в терминах АС. Такая функция использует определенную языком схему команд - языково ориентированную абстрактную машину (АМ), позволяющую смысл программ формулировать без конкретики компьютерных архитектур.
Выбор команд абстрактной машины представляет собой компромисс между уровнем базовых средств языка и сложности их реализации на предполагаемых конкретных машинах (КМ), выбор которых осуществляется на уровне прагматики.
Способ такого определения семантики языка программирования с помощью интерпретатора над языково ориентированной абстрактной машиной называют операционной семантикой языка. Принятая в операционной семантике динамика управления обладает большей гибкостью, чем это принято в стандартных системах программирования (СП) компилирующего типа. Это показывает резервы развития СП навстречу современным условиям разработки и применения информационных систем с повышенными требованиями к надежности и безопасности.
Синтаксис программ в языке программирования сводится к правилам представления данных, операторов и выражений языка.
Начнем с выбора абстрактного синтаксиса на примере определения небольшого, но функционально полного подмножества языка Лисп [[75]].
Конкретный синтаксис языков программирования принято представлять в виде простых БНФ (Формул Бекуса-Наура). Данные языка Лисп - это атомы, списки и более общие структуры из бинарных узлов - пар, строящихся из любых данных:
<атом> ::= <БУКВА> <конец_атома>
<конец_атома> ::= <пусто> | <БУКВА> <конец_атома> | <цифра> <конец_атома>
<данное> ::= <атом> | (<данное> ... ) -- список
Пример 2.1. Синтаксис данных языка Лисп
Это правило констатирует, что данные - это или атомы, или списки из данных.
/Три точки означают, что допустимо любое число вхождений предшествующего вида объектов, включая ни одного./
Согласно такому правилу () есть допустимое данное. Оно в языке Лисп по соглашению эквивалентно атому Nil.
Такая единая структура данных вполне достаточна для представления сколь угодно сложных программ. Дальнейшее определение языка Лисп можно рассматривать как восходящий процесс генерации семантического каркаса, по ключевым позициям которого распределены семантические действия по обработке программ. Позиции распознаются как вызовы соответствующих семантических функций.
Другие правила представления данных нужны лишь при расширении и специализации лексики языка (числа, строки, имена особого вида и т.п.). Они не влияют ни на общий синтаксис языка, ни на строй его понятий, а лишь характеризуют разнообразие сферы его конкретных приложений.
Абстрактный синтаксис программ является утончением синтаксиса данных, а именно - выделением подкласса вычислимых выражений (форм), т.е. данных, имеющих смысл как выражения языка и приспособленных к вычислению. Внешне это выглядит как объявление объектов, заранее известных в языке, и представление разных форм, вычисление которых обладает определенной спецификой.
Операционная семантика языка определяется как интерпретация абстрактного синтаксиса, представляющего выражения, имеющие значение.
Учитывая исследованность проблем синтаксического анализа и существование нормальных форм, гарантирующих генерацию оптимальных распознавателей программными инструментами типа YACC-LEX, в качестве абстрактного синтаксиса для Лиспа выбрано не текстовое, а списочное представление программ. Такое решение снимает задачу распознавания конструкций языка - она решается простым анализом первых элементов списков. Одновременно решается и задача перехода от конкретного синтаксиса текстов языка к абстрактному синтаксису его понятийной структуры. Переход получается просто чтением текста, строящим древовидное представление программы.
Ниже приведены синтаксические правила для обычных конструкций, к которым относятся идентификаторы, переменные, константы, аргументы, формы и функции. (Правила упорядочены по сложности взаимосвязи формул.)
<идентификатор> ::= <атом>
Идентификатор - это подкласс атомов, используемых при именовании неоднократно используемых объектов программы - функций и переменных. Предполагается, что идентифицируемые объекты размещаются в памяти так, что по идентификатору их можно найти.
<форма> ::= <константа> | <переменная> | (<функция> <аргумент> ... >) | (IF <предикат> <форма> <форма> )
<константа> ::= (QOUTE <данное>)
<переменная> ::= <идентификатор>
<аргумент> ::= <форма>
<предикат> ::= <форма>
Пример 2.2. Синтаксис выражений подмножества языка Лисп
Переменная - это подкласс идентификаторов, которым сопоставлено многократно используемое значение, ранее вычисленное в подходящем контексте. Подразумевается, что одна и та же переменная в разных контекстах может иметь разные значения.
Таким образом, класс форм - это объединение класса переменных и подкласса списков, начинающихся с QUOTE, IF или с представления некоторой функции.
Форма - это выражение, которое может быть вычислено.
Форма, представляющая собой константу, выдает эту константу как свое значение.
В таком случае нет необходимости в вычислениях, независимо от вида константы. Константные значения могут быть любой сложности, включая вычислимые выражения. Чтобы избежать двусмысленности, предлагается константы изображать как результат специальной функции QUOTE, блокирующей вычисление. Представление констант с помощью QOUTE устанавливает границу, далее которой вычисление не идет. Константные значения аргументов характерны при тестировании и демонстрации программ.
Если форма представляет собой переменную, то ее значением должно быть данное, связанное с этой переменной до момента вычисления формы. (Динамическое связывание, в отличие от традиционного правила, требующего связывания к моменту описания формы, т.е. статического связывания.)
Третья ветвь определения формы гласит, что можно написать функцию, затем перечислить ее аргументы, и все это как общий список заключить в скобки.
Аргументы представляются формами. Это означает, что допустимы композиции функций. Обычно аргументы вычисляются в порядке вхождения в список аргументов. Позиция "аргумент" выделена для того, чтобы было удобно в дальнейшем локализовать разные схемы обработки аргументов в зависимости от категории функций. Аргументом может быть любая форма, но метод вычисления аргументов может варьироваться. Функция может не только учитывать тип обрабатываемого данного, но и управлять временем обработки данных, принимать решения по глубине и полноте анализа данных, обеспечивать продолжение счета при исключительных ситуациях и т.п.
Последняя ветвь определяет формат условного выражения. Согласно этому формату условное выражение строится из синтаксически различимых позиций для предиката и двух обычных форм. Значение условного выражения определяется выбором по значению предиката первой или второй формы. Первая форма вычисляется при истинном значении предиката, иначе вычисляется вторая форма. Любая форма может играть роль предиката.
<функция> ::= <название> | (LAMBDA <список_переменных> <форма>) | (LABEL <название> <функция>)
<список_переменных> ::= (<переменная> ... )
<название> = <идентификатор>
Пример 2.3. Синтаксис функций подмножества языка Лисп
Название - это подкласс идентификаторов, определение которых хранится в памяти, но оно может не подвергаться влиянию контекста вычислений.
Таким образом, класс функций - это объединение класса названий и подкласса трехэлементных списков, начинающихся с LAMBDA или LABEL.
Функция может быть представлена просто именем. В таком случае ее смысл должен быть заранее известен. Функция может быть введена с помощью лямбда-выражения, устанавливающего соответствие между аргументами функции и связанными переменными, упоминаемыми в теле ее определения (в определяющей ее форме). Форма из определения функции может включать переменные, не включенные в лямбда-список, - так называемые свободные переменные. Их значения должны устанавливаться на более внешнем уровне. Если функция рекурсивна, то следует объявить ее имя с помощью специальной функции LABEL.
Используемые в реальных Лисп-системах функции DEFUN или DEFINE, по существу, совмещает эффекты специальных функций LABEL и LAMBDA.
<форма> ::= <переменная> | (QOUTE <данное>) --- константа | (IF <предикат> <форма> <форма>) --- условное выражение | (<функция> <аргумент> ... <аргумент>) --- вызов функции
<предикат> ::= <форма> <аргумент> ::= <форма> <переменная> ::= <идентификатор>
<функция> ::= <название> --- ранее определенная функция | (LAMBDA <список_переменных> <форма>) --- безымянная функция | (LABEL <название> <функция>) --- рекурсивная функция
<список_переменных> ::= (<переменная> ... )
<название> ::= <идентификатор> <идентификатор> ::= <атом>
Листинг 2.1. Синтаксическая сводка подмножества языка Лисп
Можно показать, что полученная система правил сводима к нормальным формам, гарантирующим возможность автоматического построения как автомата распознавания текстов, принадлежащих заданному этими формулами языку, так и автомата генерации списочных структур, эквивалентных этому языку.
Поэтому приведенное определение может одновременно рассматриваться как определение и множества текстов языка - конкретный синтаксис, и множества структурных представлений программ - абстрактный синтаксис. Это снимает необходимость здесь рассматривать задачу перехода от конкретного синтаксиса к абстрактному.
Согласно Венской методике абстрактный синтаксис языка образуют распознаватели и селекторы для распознавания языковых понятий и выделения значимых позиций, используемых при параметризации семантических обработчиков.
Пусть e - обозначение вычисляемого выражения, а fn - обозначение применяемой функции. Для списочного представления программ на данном подмножестве Лиспа можно задать следующие распознаватели:
(atom e) --- переменная (eq (car e) 'QUOTE) --- константа (eq(car e) 'IF) --- условное выражение
(atom fn) --- название известной функция (eq(car fn)'LAMBDA) --- конструирование безымянной функции (eq (car fn) 'LABEL) --- конструирование рекурсивной функции
Следует отметить, что полученные БНФ могут рассматриваться лишь как семантический каркас функционального языка программирования. Отсутствует привязка к структурам данных Лиспа и средствам их обработки. Такая обработка обеспечивается набором встроенных базовых функций, смысл которых должен быть заранее определен. Для каждой такой функции интерпретатор должен иметь возможность вычислить результат применения функции к ее аргументам. Набор встроенных функций задает основную область применения языка. Для Лиспа это обработка списочных структур данных:
(eq fn 'CAR) --- вызов функции CAR (eq fn 'CDR) --- вызов функции CDR (eq fn 'CONS) --- вызов функции CONS (eq fn 'ATOM) --- вызов функции ATOM (eq fn 'EQ) --- вызов функции EQ
Селекторы основных позиций списочного представления программ P сводятся к композициям функций обработки списков:
(Car P ) (Cdr P ) (Caar P ) = (Car (Car P )) (Cadr P ) = (Car (Cdr P )) (Cdar P ) = (Cdr (Car P )) (Caddr P ) = (Car (Cdr (Cdr P )))
