Особенности семантики языков программирования

ВЕСТН. МОСК. УН-ТА. СЕР. 7. ФИЛОСОФИЯ. 2007. № 6

ФИЛОСОФИЯ И МЕТОДОЛОГИЯ НАУКИ

А.Е. Казакова

ОСОБЕННОСТИ СЕМАНТИКИ ЯЗЫКОВ

ПРОГРАММИРОВАНИЯ

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

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

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

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

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

Предельная модель абстрактного вычислителя была описана Аланом Тьюрингом в 1936 г.2 Подробное описание этой машины приводится во множестве учебников и работ, посвященных математической логике3. Логические решения, осуществленные с помощью этой абстрактной машины, представляют особый интерес в разговоре о языках программирования, но не укладываются в рамки данной статьи. Здесь же мы опишем вычислитель лишь функционально.

Базовыми операциями для любого вычислителя являются: переход на заданный шаг алгоритма, сравнение, сложение и присваивание4. На каком бы языке ни была написана программа, любые, даже сложнейшие ее конструкции должны стать понятны вычислителю, другими словами, должны быть проинтерпретированы для вычислителя. Таким образом, именно к этим четырем операциям в конечном счете сводятся все синтаксические конструкции, используемые при написании текста программы. По сути текст программы представляет собой последовательность операций, адресованных вычислителю и заданных в соответствии с определенным алгоритмом. Алгоритм в данном случае требуется для конкретизации этой последовательности и ее оптимизации для решения задачи за конечное число шагов, что гарантирует конечность вычислений.

Развитие языков программирования во многом определялось задачей сблизить язык конечного вычислителя с языком, на котором формулируется задача, ему адресованная, в идеальном варианте это естественный язык. Фактически это выражается в том, что по отношению к машинному языку (языку вычислителя) образовалась иерархическая надстройка (структура) языков более высокого уровня, стремящихся снизить так называемый семантический разрыв между языком, на котором осуществляется первичная формализация задачи, и машинным кодом5.

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

Способы построения схем преобразования данных с помощью формального языка в большинстве случаев программирование заимствует из математики. Проектировщики многих первых компьютеров пытались формулировать задания для них с помо-

щью алгебраической записи, но создать действительно работающий компилятор удалось только в 1952 г. Его написала для компьютера UNIVAC Грейс Мюррей Хоппер (1906—1992), работавшая тогда в компании «Remington Rand».

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

На основании степени удаленности языка постановки задачи от машинного кода, т.е. степени снижения семантического разрыва, выделяют три поколения языков программирования: 1) машинные языки (команды записываются в виде последовательности битов — «0» и «1»); семантический разрыв наиболее высок; 2) языки ассемблера (машинно зависимый мнемонический код); представляют собой множество сокращений, взаимно однозначно соответствующих операторам машинного языка; 3) языки высокого уровня; семантический разрыв снижается за счет введения дополнительных абстрактных конструкций, облегчающих процесс формализации задачи. Создание подобной иерархической структуры осуществляется благодаря возможности однозначного определения примитивов. В качестве примера приведем наиболее современную конструкцию, названную объектно ориентированной. Она дает возможность моделировать задачу в терминах объектов и отношений между ними. Главное преимущество языка высокого уровня в том, что он намного превосходит ассемблер в легкости изучения и использования. Кроме того, программа, написанная на языке высокого уровня, понятнее, является переносимой, т.е. независимой от конфигурации конкретного вычислителя. Таким образом, ее создатель избавлен от необходимости вникать в тонкости архитектуры компьютера, на котором она будет работать. Эту задачу берет на себя специально разработанный для этого компилятор, интерпретирующий текст программы для вычислителя. Результат работы компилятора представляет собой так называемый исполняемый файл, адресованный конкретному типу вычислителей (процессоров). Получается, что теоретизация и анализ семантики языка происходят в процессе создания компилятора, а не в процессе написания программы, а процесс формализации задачи и алгоритма ее решения представляет собой перевод с естественного языка на язык программирования.

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

Механизмы создания формальных языков типа языков программирования, используемые для описания их синтаксиса, часто называют грамматиками. Это формальное описание синтаксиса неявно задает семантику по отношению к вычислителю. Первоначально такую задачу удалось решить Джону Бэкусу, разработчику языжа ALGOL 58 (1950-е гг.). Позже эта запись была модифицирована Питером Науром для описания языка ALGOL 60 (1960 г.). Переработанный метод описания синтаксиса стал известен как форма Бэкуса—Наура, или сокращенно БНФ. Он является метаязыком для языков программирования и все еще остается наиболее распространенным методом краткого описания синтаксиса языка программирования. Для описания синтаксических структур БНФ использует специальные абстракции. Определяемые абстракции называют нетерминальными символами (нетерминалы), они помещаются слева от условного знака отношения Справа от знака отношения располагается определение этих абстракций (терминалы), представляющее собой грамматические лексемы или ссылки на другие определяемые абстракции. Все определение в целом называется правилом, или продукцией6. Строка описания языка С7 методом БНФ выглядит следующим образом:

<присвоить> ^ <переменная> = <выражение>.

Таким образом, БНФ является набором правил построения синтаксических выражений и, несмотря на свою внешнюю простоту, представляет мощное средство описания подавляющего большинства языков программирования. Кроме того, БНФ используется не только как распознающая (аналитическая) грамматика, но и как порождающее8 устройство для определения языков программирования. Предложения языка создаются с помощью последовательности правил, а создание предложения называется

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

В рамках поставленной задачи принципиально отметить, что похожую форму записи для теоретического описания естественных языков (точнее, английского языка) разработал Ноам Хом-ский, построив трансформационную порождающую грамматику9. Хомский описал четыре класса порождающих устройств, или грамматик, определяющих четыре10 класса языков. Два последних класса из четырех, названные контекстно свободной и регулярной грамматиками11, оказались применимы для описания синтаксиса языков программирования и практически полностью совпадают с формой Бэкуса—Наура. Контекстно-свободные грамматики определяются тем правилом, что левая часть предложения должна состоять не более чем из одного нетерминала. Регулярные же грамматики, являющиеся подклассом контекстно свободных, задаются по аналогии с описанием конечного автомата12 и соответствуют определению множества регулярных выражений языка.

Важно отметить, что Н. Хомский был в первую очередь лингвистом и изначально не ставил себе задачу описывать искусственные формализованные языки, его интересовала теоретическая природа естественных языков. В теории порождающей грамматики принципиально различие между тем, что говорящий на языке знает неявным образом (компетенция), и тем, что он делает с помощью языка (употребление языка)13. Грамматика, согласно Н.Хомскому, занимается изучением компетенции. «Компетенция говорящего—слушающего может быть представлена как система правил, связывающих сигналы с семантическими интерпретациями этих сигналов»14. В этой терминологии становится возможным объяснить тот факт (о котором упоминалось выше), что профессиональный программист при написании программы, т.е. применяя язык, не обращается к семантике напрямую. Более того, прежде чем была получена надежная основа для построения семантики языков программирования и появились методы явного их описания, прошел достаточно длительный (для истории этих языков) период.

Ставя перед собой задачу создать систему правил, описывающую компетенцию говорящего—слушающего, Н. Хомский указал на незыблемый базис, присущий человеку, пользующемуся языком. То, что этот базис сохраняется для искусственных языков, может объясняться, как полагал сам Хомский, либо априорным для пользователя языка характером этих структур, либо неотъем-

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

В заключение хотелось бы сказать, что на смену контекстно свободным грамматикам для описания структур языков программирования пришли атрибутивные грамматики, расширенные за счет возможности описать правила совместимости типов абстрактных объектов. Эта возможность достигается путем добавления атрибутивных вычислительных и предикативных функций. Концепция атрибутивной грамматики создается уже в рамках заранее заданной так называемой статической семантики. Статическую семантику относят к классу операционных15, поскольку смысл конструкциям языка придается с точки зрения их влияния на функции переходов в состояние абстрактного вычислителя. Более совершенными являются пропозициональные и денотационные семантики. В первой более высокий уровень абстракций достигается за счет замены множества состояний абстрактного вычислителя множеством формул некоторой логической системы, во второй операционное определение заменяется денотацион-ным16, чем обеспечивается возможность еще более глубокого анализа. Такие семантики задаются, например, для языков, строящихся в соответствии с упомянутым ранее объектно ориентированным подходом.

Описание всех возможных семантик17 представляет собой весьма сложную задачу, однако многообразие способов построения семантик для современных языков программирования может считаться дополнительным подтверждением тезиса о продолжающемся поиске наиболее совершенного способа абстрагирования посредством формализованного языка. А тот факт, что поиски этого способа происходят в рамках языков программирования, ориентированных на решение практических задач, обеспечивает почву для дальнейших исследований в этой области18.

ПРИМЕЧАНИЯ

1 Так, первым языком программирования считается язык, о котором говорит А. Лавлейс в комментариях к теоретическому описанию абстрактной машины Ч. Бэббиджа. (Sketch of The Analytical Engine Invented by Charles Babbage.

2 Tyring A. On computable numbers with an application to the Entscheindungs — problem. L., 1936.

3 Наиболее известными и общепринятыми среди них считаются Клини, Чёрч.

4 В современных вычислительных машинах эти операции заложены в устройстве процессора.

5 В данном случае понятия «машинный язык» и «машинный код» употребляются идентичным образом.

6 Описание БНФ приводится по: Себеста Р.У. Основные концепции языков программирования. М.; СПб.; Киев, 2001. С. 127.

7 C — название одного из самых распространенных языков программирования, имеющее значительную для этой области историю разработки и применений.

8 В общем случае языки программирования могут формально определяться двумя различными способами: путем распознавания (указания принадлежности конкретного предложения конкретному языку) и путем порождения (задания правил правильного построения предложения языка — правил вывода).

9 Chomsky N. Three Models for the Description of Language // IRE Transactions on Information Theory. 1956. Vol. 2. N 2. P. 113—123 (в русском переводе «Три модели описания языка»).

10 Четвертый класс языков: Chomsky N. Syntactic Structures. Mouton. The Hague, 1957.

11 К первым двум типам грамматик относятся так называемые «неограниченные грамматики» и «контекстно зависимые грамматики». Каждый последующий тип является более ограниченным подмножеством предыдущего и, следовательно, легче поддается анализу.

12 Математическая абстракция теории алгоритмов в данном контексте функционально может быть соотнесена с конечным вычислителем.

13 См.: Хомский Н. Вопросы теории порождающей грамматики // Философия языка / Пер. с англ.; ред.-сост. Дж.Р. Сёрл; М., 2004.

15 Там же. С. 101

15 Подразделение существующих семантик на категории операционных, пропозициональных и денотационных приводится по: Волъфенгаген В.Э. Конструкции языков программирования. М., 2001. С. 77—80.

16 Денотат в данном случае понимается как идеализированный математический объект, посредством высокой степени абстракции представляющий (моделирующий) другие объекты.

17 За рамками рассмотрения остались по меньшей мере аксиоматическая и алгебраическая семантики.

18 Для написания статьи были использованы следующие материалы: Knuth D.E. Semantics of Context-Free Languages // Mathematical Systems Theory. 1968. Vol. 2. N 2. P. 127—145 (на русском языке: Кнут Д. Семантика контекстно свободных языков // Семантика языков программирования. М., 1980); Вейль Г. Математическое мышление / Пер. с англ. и нем.; сост. Ю.А. Данилов; под ред. Б.В. Бирюкова, А.Н. Паршина. М., 1989; Математическая логика и ее применения / Под ред. Э. Нагела, П. Саппса, А. Тарского; пер. с англ. под ред. А.И. Мальцева. М., 1965; Смирнова Е.Д. Логика и философия. М., 1996; Хомский Н. Язык и проблемы знания. 1999.