imagesperevesti-s-matematicheskogo-jazyka-na-jazyk-programmirovanija-thumb.jpg

Ускоренный курс по нотациям в теории языков программирования

Основной строительный блок, который мы используем в ТЯП — это множество, т.е. коллекция объектов (или элементов). При этом программа остаётся на исходном языке и не может быть запущена без интерпретатора. Программа на интерпретируемом языке может быть зачастую запущена на разных типах машин и операционных систем без дополнительных усилий.

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

Синтаксис языка и грамматики

И обычно мы так и делаем в ТЯП. Есть несколько различных стилей отношений. Отступление: Рассматриваемый здесь порядок «слева направо» я выбрал как дизайнер языка. Я мог бы не определять порядок, позволяя быть ему неопределенным.

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

Если вы знакомы с языком C, можете читать e1 e2 как e1(e2). Со времени создания первых программируемых машин человечество придумало более восьми тысяч языков программирования (включая нестандартные, визуальные и эзотерические языки). Они традиционно известны под наименованием языков ассемблера и автокодов. Позднее языки второго поколения были усовершенствованы: в них появилась поддержка макрокоманд. С середины 1950-х начали появляться языки третьего поколения, такие как Фортран, Лисп и Кобол.

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

Если программа написана на интерпретируемом языке, то интерпретатор непосредственно выполняет (интерпретирует) исходный текст без предварительного перевода. Для любого интерпретируемого языка можно создать компилятор — например, язык Лисп, изначально интерпретируемый, может компилироваться без каких бы то ни было ограничений. Кроме того, скомпилированная программа может выполняться только на том же типе компьютеров и, как правило, под той же операционной системой, на которую был рассчитан компилятор.

Этим постом я хочу помочь моим друзьям с чтением других моих постов. Я подозреваю, что многие читатели будут знакомы с множествами, кортежами и отношениями, но если вы не знакомы с индуктивными определениями, тогда прочитайте секцию ниже «определение правилами».

Например множество {0, 2, 1}, тоже же самое множество, что и приведенное сверху. Нотация ∈ означает «в». Таким образом 1 ∈ {0, 1, 2} истина и 3 ∈ {0, 1, 2} ложь. Множества могут содержать бесконечное количество элементов. Отношение — это множество кортежей. Основной способ, которым мы определяем бесконечные множества в ТЯП — предоставляем набор правил, описывающих, какие элементы входят в множество.

Так (0, 0) не входит в R, потому что с помощью указанных правил нельзя обосновать, что (0, 0) туда входит. Некоторые наборы правил бессмысленны и не определяют множество. Учебник по ТЯП описывает ограничения для «хороших» наборов правил, но мы не будем в это углубляться. Скажем только, что хотя бы одно правило должно быть нерекурсывным и подобные логические противоречия должны отсутствовать. Общераспространенная нотация для правил, как выше, использует горизонтальную черту между «if» и «then».

Часто, «корректный тип», это что-то о чем можно догадаться из контекста беседы. Я пометил каждый шаг в выводе номером правила. Предположим, что нам нужно определить простой язык для целочисленной арифметики. Описать язык, значит описать, что произойдет при запуске программы на этом языке. Именно это делает операционная семантика. В случае с Arith нам нужно указать целочисленный результат для каждой программы.

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

Не проходите мимо: