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

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

1+63/2

. Чтобы полностью охарактеризовать язык арифметики. Нужно ответить на три вопроса:

  • Синтаксис: Какова структура арифметического выражения?
  • Статическая семантика: Какое подмножество арифметических выражений имеет значение?
  • Динамическая семантика: Что означает данное арифметическое выражение?

Синтаксис

Языки начинаются с примитивов, или объектов. Представляющих атомарные единицы значения.

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

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

Мы можем записать структуру арифметики как контекстно-свободную грамматику:

Number nNBinop  ^ ::= +^  ^  ^  /^ Expression e::=ne1 ^ e2

Грамматика-это метаязыковое понятие. Инструмент описания структуры языка. Показанная конкретная грамматическая нотация является вариантом канонической формы Бэкуса-Наура для указания контекстно-свободных грамматик. Каждое правило (или “производство”) определяет различные способы создания определенной структуры.

Вы можете прочитать его так: “двоичный оператор

 ^ 

это может быть один из четырех символов:

 +^ 

,

 ^ 

,

 ^ 

, или

 /^ 

… Выражение лица

e

может быть одно из двух: число

n

, или комбинация двух подвыражений

e1 ^ e2

” Например,

1

,

1 +^ 2

, и

2 ^ 3 /^ 1

являются ли все синтаксически допустимыми выражениями. В то время как

2 ^  +^ 1

не является.

Символы

e,n, ^ 

являются метавариаблями в том смысле. Что они являются заполнителями синтаксиса. А не фактическими переменными в описываемом языке. То есть,

1 +^ e

не является арифметическим выражением. Потому что наш арифметический язык не имеет понятия переменных.

(И все же!) Но мы можем сказать

1 +^ 2

это арифметическое выражение. Где

e1=1,e2=2, ^ = +^ 

.

Синтаксические деревья

Мы должны быть осторожны при обсуждении структуры. Чтобы понять истинную форму нашего языка. При передаче в тексте арифметическое выражение выглядит как последовательная строка символов. Например

1 +^ 2 ^ 3

но это всего лишь ограничение текста как носителя. Контекстно-свободные грамматики описывают древовидные структуры. И линейный текст неявно описывает это дерево:

С этой точки зрения мы можем определить синтаксис как базовую структуру языка. Синтаксис-это не только фигурные скобки. пробел или charvs uint8_t. Это иногда различают как абстрактный синтаксис языка и его конкретный синтаксис. Где абстрактное относится к структуре. А конкретное-к символам. Язык может иметь несколько конкретных синтаксисов для одного и того же абстрактного синтаксиса, например. Наши диаграммы и текстовые представления арифметики. Дерево, соответствующее фрагменту синтаксиса. Впоследствии называется абстрактным синтаксическим деревом, или AST.

Деревья и контекстно-свободные грамматики часто рассматриваются как фундаментальные для языков программирования. Но это интересный и открытый вопрос об альтернативных представлениях для синтаксиса языка. Например, если мы введем переменные в наш арифметический язык:

Expression e::=let x=e1 in e2

И тогда у вас есть такая программа. Как

(let x=1 in x+x)

, суть структуры программы больше не является строго древовидной. Так как подвыражение

x+x

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

Двусмысленность и приоритет

Задача разбора строки в дерево часто недооценивается перед лицом неоднозначной грамматики. В нашей грамматике строка

1 +^ 2 /^ 3

может быть разбор как

(1 +^ 2) /^ 3

или

1 +^ (2 /^ 3)

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

На этом занятии наша главная задача при обсуждении грамматики-понять простейшую сущность нашей языковой структуры. Поэтому мы не будем пытаться усложнять грамматику. Чтобы избежать двусмысленностей. Вместо этого мы сформулируем (на английском языке) правила приоритета и ассоциативности. Для арифметики можно принять стандартные правила ассоциативности и приоритета (PEMDAS).

Источники смысла

Вообще, может быть трудно говорить о языках. Потому что мы обязательно должны использовать язык для того. Чтобы передавать языковые понятия. Мы остановимся на некоторых деталях. Чтобы прояснить некоторые различия. Здесь мы используем обозначение шляпы на двоичных операторах. Чтобы сделать абсолютно ясным. Что символы

 +^ 

а друзья не имеют абсолютно никакого значения. Это символы без семантики. И у нас есть только грамматика. Которая определяет. Как эти символы могут быть объединены. Они не то же самое. Что

+,,,/

символы с их общепринятой семантикой в стандартной арифметике.

Семантика

Синтаксис определяет набор допустимых форм в нашем языке. Структуру нашей предметной области. Следующим шагом в определении языка программирования является установление его семантики и свойств. Как мы говорим о том. Что означает арифметическое выражение или имеет ли оно вообще смысл?

Семантика языка имеет богатую историю. Охватывающую логику. Информатику, философию. Лингвистику и многие другие области. В естественном языке мы часто думаем о семантике иерархически—присвоение значения фразе “Will went to the store” начинается с понимания “Will”. “went” и “store”. А затем объединение этих значений в субъектно-глагольно-объектную композицию. Это приводит к абстрактному значению. Которое идентично другому конкретному синтаксису. Такому как “Will去了商店”. Этот стиль понимания значения близок к денотативной семантике.

Для языков программирования нас больше интересует понятие вычислений как семантики. Например, наша цель состоит не в том. Чтобы присвоить семантику строке. А в "hello"том, чтобы программист мог решить. Как интерпретировать ее содержимое в данном приложении. Скорее, программа-это структура . Которая может быть вычислена, например"hello" + " world", сводится к "hello world". В более общем плане. Учитывая язык. Который определяет выражения. Наша цель-определить семантику. Которая может свести выражение к примитивной форме. Как-то мы должны выбраться отсюда.

1 +^ 2 ^ 3

Для

7

.

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

int main() { FILE* f = fopen("/tmp/foo"); fwrite(f, "bar"); fclose(f); return 0; } 

Что мы можем сказать. Что эта программа “означает”? Конечно, это означает больше. Чем просто его код возврата—это эффекты запуска программы, например. Запись в файл. Которые являются важными частями. Каждый оператор в этой программе имеет эффект. Но сам по себе не представляет объект/datum/value. Линия return 0является чисто управляющим потоком. Она не имеет значения.

Напротив, выражения имеют значения. Церковные языки ориентированы на выражение в том смысле. Что вся программа представляет собой одно выражение. Поэтому программа представляет собой одно значение. В арифметическом языке любая программа (арифметическое выражение) соответствует одному числу. Полученному в результате ее вычисления. Может показаться странным. Что сложная программа со многими эффектами может быть представлена таким образом. Но мы углубимся в это соответствие ниже.

Операционная семантика

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

e

, он может находиться в одном из двух состояний: либо он сводим, что означает. Что вычисление может быть выполнено . Либо выражение является значением, что означает. Что оно достигло окончательной формы. Мы формализуем эти состояния как логические суждения. Записанные как

ee

для “

e

шаги к

e

” и

e val

для “

e

это ценность”. Затем мы определяем формальную систему для доказательства этих суждений о выражениях. Ниже приводится полная операционная семантика арифметики:

n val(D-Num)e1e1e1 ^ e2e1 ^ e2(D-Left)e1 vale2e2e1 ^ e2e1 ^ e2(D-Right)n1n2=n3n1 ^ n2n3(D-)

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

ab

это то же самое. Что

ab

Таким образом, первое правило-это аксиома, читающаяся как “безусловно, любое число

n

это ценность.” Второе правило гласит: “если

e1

шаги к

e1

затем

e1 ^ e2

шаги к

e1 ^ e2

Если правило содержит несколько посылок, разделенных пробелами, то все они необходимы для доказательства вывода (то есть И, а не ИЛИ).

Как и большая часть абстрактной математики. Теория PL использует неявный контекст для упрощения своей нотации. Например, в правиле D-Num мы полагаемся на то. Что

n

ранее было установлено. Что представление чисел означает. Что правило D-Num применимо только к числам. Более того, правило неявно квантифицировано по всем числам, т. Е. Мы могли бы формально записать правило как:

nN.n val(D-Num)

Аналогично, D-Left имеет неявное

e1,e2Expression

впереди. Если вас когда-либо смущали неустановленные предположения в правиле. Обязательно спросите!

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

n

, это ценность. Так что мы закончили. Следующие два правила определяют порядок операций, но не в традиционном смысле PEMDAS. Скорее, они отвечают на вопрос: если у меня есть выражение с двумя сводимыми подвыражениями. Такими как

(1 +^ 2)(4 /^ 2)

, какую субэпрессию мы уменьшаем в первую очередь? Для арифметики ответ (неудовлетворительно) состоит в том. Что это не имеет значения. Наш язык настолько прост. Что мы всегда придем к одному и тому же значению при любой стратегии сокращения. Поэтому мы произвольно выбираем сначала уменьшить левое выражение. Следовательно. Правило D-Left гласит. Что если левая сторона может быть уменьшена. То уменьшите ее. D-Right говорит. Что если левая сторона не может быть уменьшена. А правая сторона может. То уменьшите правую сторону.

Наконец, мы приходим к

D-

Это правило гласит. Когда у нас есть двоичный оператор

 ^ 

с двумя подвыражениями. Которые оба являются числами. Затем выполните соответствующую арифметическую операцию. Это нотационно выражается снятием этой шляпы. Неявно предполагая. Что если

 ^ = +^ 

затем

=+

и так далее. Что это значит и почему это работает? По сути, мы говорим: семантика нашего языка существует в рамках внешней теории арифметических двоичных операторов. Поэтому мы предполагаем, что в другом месте мы формально определили, как вычислять

n1+n2

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

На следующей неделе мы увидим. Как определить теорию арифметики, внутреннюю для языка. То есть мы можем построить то. Что

n1+n2

означает чисто от примитивов языка. А пока подумайте сами—как бы вы формально определили поведение сложения некруглым способом? В качестве подсказки вам нужно будет переосмыслить наше представление чисел. Например, какое свойство определяет. Что 5 на 1 больше. Чем 4?

Доказательство сокращения срока

Чтобы увидеть эти правила в действии. Давайте попробуем доказать простое сокращение:

1 +^ 6 ^ 3 /^ 2

оценивает до 10. Мы будем использовать синтаксис

e1e2

означать “

e1

сводится к

e2

после нуля или более шагов”. Поэтому наша цель доказательства

1 +^ 6 ^ 3 /^ 210

. Полная оценка займет много шагов. Поэтому мы просто попытаемся доказать первое сокращение. Следуя нашим правилам приоритета, мы начнем с

e1=1

,

e2=6 ^ 3 /^ 2

, и

 ^ = +^ 

. Используя нашу барную нотацию. Мы можем начать наше доказательство следующим образом:

1 +^ 6 ^ 3 /^ 2?(?)

Эта визуальная структура говорит: наша цель-доказать. Что выражение шагает к чему-то. Но мы не знаем. К чему это приведет и какое правило применить. Стратегия доказательства здесь довольно проста: поиск грубой силы. Есть четыре возможных правила. Которые могут быть применимы к нашему термину. Мы можем рассмотреть каждый из них по очереди. Чтобы решить. Какой из них применим.

  • D-Num: выражение не является числом. Поэтому D-Num не применяется.
  • D-Left: это правило применяется. Если
    e1

    может ступить.

    e1=1

    и

    e1 val

    , поэтому D-Left не применяется.

  • D-⊕: это правило применяется. Если оба
    e1

    и

    e2

    это числа.

    e2

    не является числом. Поэтому D-⊕ не применяется.

  • D-Right: это правило применяется. Если
    e1

    является значением (это). И если

    e2

    может шагнуть. Похоже, это может быть применимо. Поэтому мы можем начать наше доказательство здесь.

1 val(D-Num)6 ^ 3 /^ 2?(?)1 +^ 6 ^ 3 /^ 2?(D-Right)

Теперь вы можете начать видеть полную стратегию доказательства. Учитывая конечную цель. Мы рекурсивно доказываем ее предположения. Пока не достигнем аксиом. Как только каждая часть дерева доказательств полностью обоснована. У нас есть полное доказательство. Многократно применяя эту стратегию доказательства к нашему подвыражению. Мы в конечном счете приходим к следующему доказательству:

1 val(D-Num)63=18(arithmetic)6 ^ 318(D-)6 ^ 3 /^ 218 /^ 2(D-Left)1 +^ 6 ^ 3 /^ 21 +^ 18 /^ 2(D-Right)

Это только первая редукция—нам нужно было бы аналогично доказать. Что

1 +^ 18 /^ 21 +^ 9

и

1 +^ 910

чтобы завершить полное доказательство. Я оставлю эти шаги в качестве упражнения для читателя.

Что, если правило D-Right не применяется в нижней части доказательства? Это означало бы . Что наша операционная семантика для арифметики несостоятельна, то есть существуют приводимые выражения (а не значения). Для которых не может быть доказан ни один шаг. В контексте реального мира это означает. Что наш язык имеет неопределенное поведение, и компилятор/интерпретатор может выбрать произвольные действия с выражением. Это приводит к нашему первоначальному второму вопросу: какое подмножество арифметических выражений имеет значение? На данный момент ответ “все они”. Но мы вернемся к этому вопросу на следующей неделе для языков. Требующих системы типов.

Структурная индукция

В предыдущем разделе было показано. Как использовать нашу семантику для доказательства суждения о конкретном выражении, т. е. Поднимая уровень абстракции. Давайте теперь докажем кое-что о нашем языке, имея в виду универсальное утверждение над всеми возможными программами. В частности. Мы хотим продемонстрировать. Что все программы на нашем языке являются тотальными или завершающими. Неофициально это означает. Что каждая программа всегда оценивает значение. Программа никогда не застревает (никакие правила не применяются). Не вызывает ошибку или не зацикливается навсегда (“расходится”). Формально мы можем записать эту теорему в виде:

Совокупность арифметики: для всех выражений

e

, существует

e

такое. Что

ee

и

e val

.

Наша стратегия доказательства здесь отличается от предыдущего доказательства. Поскольку мы доказываем утверждение обо всех выражениях. А не об одном. Как мы должны это делать? Вспомните нашу грамматику и структуру нашего языка. Каждое выражение является либо примитивом (числом). Либо композицией под-выражений. Это близко отражает структуру индуктивного доказательства: базовый случай и индуктивный случай.

Прежде чем погрузиться в индукцию на нашем языке. Давайте обсудим. Как мы можем вывести принципы индукции с нуля. Когда вы узнали об индукции в 103 или где-то еще. Вам был предоставлен принцип индукции для натуральных чисел:

Индукция над натуральными числами:

(nN.P(n))(P(0)(nN.P(n)P(n+1)))

Этот принцип позволяет нам доказать универсальное утверждение (предложение

P

) для всех натуральных чисел. Показывая базовый случай

P(0)

и индуктивный случай

P(n)P(n+1)

. Затем вам было дано интуитивное обоснование этого принципа с помощью таких диаграмм, как эта:

Несмотря на свою креативность. Эта схема не является доказательством. Как можно формально доказать принцип индукции для натуральных чисел? Это становится намного проще. Если мы раскрываем лежащую в основе индуктивную структуру чисел. В частности. Мы можем использовать числа Пеано:

Number n::=ZS(n)

Это говорит: “любое число является либо Z (нулем), либо преемником (+1) предыдущего числа.” Так например,

Z=0

,

S(Z)=1

,

S(S(S(Z)))=3

и так далее. Теперь давайте вернемся к нашему принципу индукции в этом альтернативном представлении чисел:

(n.P(n))(P(Z)(n.P(n)P(S(n))))

Теперь каждая часть принципа индукции более четко вытекает из его индуктивной структуры. Если

n=Z

, то мы должны доказать

P(Z)

. Если

n=S(n)

, то мы должны доказать

P(n)P(S(n))

В более общем плане любая индуктивная структура имеет соответствующий индукционный принцип. Для каждого элемента структуры. Если он не имеет под-частей. То это базовый случай (например, ноль). Если он имеет под-части (например, преемник). То это индуктивный случай. Индуктивная гипотеза состоит в том. Чтобы предположить. Что пропозиция справедлива для субчастей. И доказать. Что пропозиция справедлива для композиции.

Эта идея называется структурной индукциейи обобщает математическую индукцию. Я не могу переоценить его важность. Потому что этот метод доказательства лежит в основе почти всех теорий в языках программирования. Так как индуктивные структуры чрезвычайно распространены. Знание этого принципа индукции позволяет вам использовать индуктивные доказательства для произвольных структур. Которые вы определили. А не только санкционированные. Которым вы научились (например. Натуральные числа). Давайте применим эту идею к нашему арифметическому языку. Напомним что выражения имеют такую структуру:

Expression e::=ne1 ^ e2

Из этой грамматики мы выводим следующий принцип индукции:

(e.P(e))((n.P(n))(e1,e2, ^ .P(e1)P(e2)P(e1 ^ e2)))

Это говорит: предложение истинно для всех выражений в нашем языке. Если оно безусловно истинно для всех чисел. И условно истинно для всех составных выражений. Если оно истинно для под-выражений.

Доказательство тотальности

Наконец, давайте применим этот принцип для доказательства тотальности арифметики. Напомним, что теорема:

Совокупность арифметики: Для всех выражений

e

, существует

e

такое. Что

ee

и

e val

.

Для этого доказательства примем следующую лемму (доказательство-упражнение для читателя):

Инверсия арифметических значений: Для всех выражений

e

, если

e val

, тогда

e

это число

n

.

Для тотальности мы докажем каждый случай по очереди.

  1. Позволь

    e=n

    . Затем для

    e=n

    , мы тривиально имеем

    ee

    , и

    e val

    по D-Num.

  2. Позволь

    e=e1 ^ e2

    .

    • Предположим. Что совокупность для
      e1

      и

      e2

      . По индукционной гипотезе. Пусть

      e1,e2

      такие. Что

      e1e1

      и

      e2e2

      и

      e1 val,e2 val

      .

    • По лемме инверсии,
      e1=n1

      и

      e2=n2

      .

    • По Д-Левому,
      e1 ^ e2n1 ^ e2

      .

    • По Д-Праву, потому что
      n1 val

      по D-Num,

      n1 ^ e2n1 ^ n2

      .

    • Позволь
      n3=n1n2

      . Затем

      en3

      и

      n3 val

      по D-Num. Так держится тотальность.

Вот оно! Мы доказали тотальность (окончание) для всех выражений в нашем языке. Как мы увидим на следующей неделе. По мере развития нашего языка мы просто будем добавлять все больше и больше случаев к нашему индуктивному доказательству. С точки зрения стратегии доказательства. Хитрая часть обычно тщательно формулирует предположения в индуктивных случаях и применяет соответствующие леммы. Например, теперь кажется очевидным. Что

e vale=n

Однако языки часто имеют более одного вида значений (например. Числа и строки). И поэтому основная лемма инверсии показывает только то. Что

e vale=ne=s

.