Теория языков программирования: Книга «Теория и практика языков программирования. Учебник для вузов. 2-е изд. Стандарт 3-го поколения»

Книга «Теория и практика языков программирования. Учебник для вузов. 2-е изд. Стандарт 3-го поколения»

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

В новом издании обсуждаются характеристики, а также последние тенденции развития универсальных языков программирования высокого уровня, таких как Scala, Go и Swift; поясняются главные особенности последних стандартов классических языков C++, Java и C#: лямбда-выражения во всех этих языках, cсылочный тип rvalue и семантика перемещения в языке C++ 11, ковариантность и контрвариантность родовых шаблонов в C#; существенно расширено представление скриптового языка Ruby, рассматриваются его блоки, механизмы единичного наследования и подмешивания, а также утиной типизации; добавлено описание аппарата событий и программирования на основе событий; показано применение стиля функционального программирования в скриптовых и объектно-ориентированных языках Python, Ruby, C#, Java, C++, Scala, Go и Swift.

Отрывок из книги. Язык Scala

Язык был создан в Швейцарской политехнической школе Лозанны (2004 год, главный автор — Мартин Одерски). Он стал результатом исследований, направленных на разработку улучшенной языковой поддержки компонентного ПО. За основу были взяты две идеи:

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

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

Scala была выпущена для использования на платформе JVM в январе 2004 года и на платформе .NET в июне 2004 года. Кроме того, в настоящее время активно разрабатывается целый ряд Scala-компиляторов.

Таким образом, Scala — это мультипарадигменный язык со строгой типизацией, который поддерживает функциональное, объектно-ориентированное и параллельное программирование. Предназначен для реализации на вершине виртуальной машины Java и частично мотивирован известными недостатками языка Java. Обеспечивает наиболее агрессивную интеграцию функциональных характеристик в императивный язык. Имеет функции первого класса и высшего порядка, механизм логического вывода локального типа, отложенные (ленивые) вычисления, сопоставление с образцом, карризацию, хвостовую рекурсию, развитые родовые средства (с ковариантностью и контрвариантностью), параллелизм на основе сообщений, наследование на основе трейтов (что-то среднее между классами и интерфейсами). Энергично используется как в промышленности, так и в науке. Развитие финансируется Европейским исследовательским советом.

В Scala используется чистая объектно-ориентированная модель, похожая на применяемую в Smalltalk: каждое значение является объектом (и числа, и результаты функций), а каждая операция — это отправка сообщения, вызов метода объекта. Например, сложение 2 + 3 интерпретируется как 2.+(3), то есть как вызов в объектеприемнике «2» метода «+» с аргументом «3». Здесь в качестве объекта-источника рассматривается число 3. Этим Scala отличается от Java, поскольку в Java разделены примитивные типы (например, boolean или int) и ссылочные типы, а также нет возможности работать с функциями как со значениями.

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

Перед определением функции ставится ключевое слово def. Определения классов начинаются с зарезервированного слова class. Класс может предотвратить дальнейшее создание подклассов, употребляя зарезервированное слово final. Подобно объектно-ориентированным языкам C++, Java, C#, экземпляр класса может ссылаться на себя, используя слово this. Scala допускает перегруженные методы. Как и в Java, ключевое слово extend объявляет, что класс является подклассом другого класса. Scala не поддерживает множественное наследование. Вместо этого язык применяет смешанное наследование на базе трейтов, обеспечивающих включения общих атрибутов и методов в несколько подклассов. Трейты могут расширять классы или другие трейты. Подкласс в Scala может наследовать методы как от родительского класса, так и от трейтов. Трейты могут также иметь отношения с родительским классом и подклассом. Объявление трейта начинается с ключевого слова trait. Тело трейта выполняется, когда создается экземпляр класса, задействующего этот трейт. Родительским по умолчанию для класса или трейта является класс AnyRef, прямой потомок класса Any.

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

Правила видимости в Scala похожи на Java с некоторыми вариациями. В отличие от C++, по умолчанию в Scala задается «публичная» видимость. Видимость регулируется с помощью ключевых слов protected и private. Видимость указывается в начале объявлений функций, переменных или трейтов. Применение private [this] закрывает объявление для конкретного экземпляра внутри класса.

Определения методов считаются обычными функциями, начинаются с ключевого слова def, за которым следуют необязательные списки аргументов, символ двоеточия «:» и тип возвращаемого значения метода. Абстрактным является метод, у которого отсутствует тело. Методы могут вкладываться друг в друга.

Для иллюстрации представим абстрактный класс для комплексного числа:

class Complex_number (first: Double, second: Double)
{
                  val re = first
                  val im = second
                  override def toString = re + " + " im + "i"
                  def add(that: Complex_number): Complex_number =
                       new Complex_number (this.re + that.re, this.im + that.im)
                  def subtract(that: Complex_number): Complex_number =
                       new Complex(this.re - that.re, this.im - that.im)
}

Определение класса включает только два атрибута: re (действительная часть) и im (мнимая часть). С помощью свойства override операция toString переопределена. Это сделано для облегчения печати результата. Заданы две абстрактные операции: сложение и вычитание. Абстрактные операции записываются в виде двух методов. Каждый метод создает новое комплексное число, которое автоматически печатается на консоли с помощью переопределенного метода toString.

После загрузки этого фрагмента в интерпретатор Scala можно выполнить следующие команды:

val c1 = new Complex_number(3, 4) //печать комплексного числа 3.0 + 4.0 i
val c2 = new Complex_number(4, 5) // печать комплексного числа 4.0 + 5.0 i
c1 add c2 // печать комплексного числа 7.0 + 9.0 i
c1 subtract c2 // печать комплексного числа -1.0 + – 1.0

Точка с запятой используется в языке значительно реже: она не ставится в конце оператора, если он записан один в строке. Если строка содержит более одного оператора, точка с запятой обязательна. Scala поддерживает как изменяемые, так и неизменяемые структуры данных Язык обеспечивает полиморфизм, и если тип переменной не указан, то он выводится на основе значения, заданного для переменной.

Scala реализует обширный набор типов данных: массивы, ассоциативные массивы, списки, кортежи и множества. Массивы являются изменяемыми объектами, а списки — неизменяемыми объектами. Списки используются при функциональном программировании, а массивы — при императивном программировании. Множества и ассоциативные массивы могут создаваться как изменяемыми, так и неизменными с помощью трейтов. Напомним, что трейты — это абстрактные интерфейсы, которые расширяют содержание объектов. Например, если имеется класс «транспортное средство» и трейт «четырехколесный», расширяющий транспортные средства, то автомобиль соответствует классу «транспортное средство» с добавлением трейта «четырехколесный». В случае множеств и ассоциативных массивов связывание «изменяемого» и «неизменяемого» трейтов с классом множество или ассоциативный массив обеспечивает, в конечном счете, их изменяемость или неизменность.

Целочисленный массив объявляется как Array [Int] (4). Это означает, что объект является массивом, содержащим четыре целых числа. Индексы переменных записываются внутри пары круглых скобок. Поскольку каждая структура данных является объектом, массив создается с использованием конструктора new. Например, объявление val: studentNames = new array [String] (20) создаст объект массива, содержащий 20 строк. К его строкам можно получить доступ с помощью studentNames(i), где i — индексная переменная типа integer.

Списки могут быть объявлены в форме List (1, 2, 3) или как несколько элементов, соединенных символом «::». Например, List (1, 2, 3) можно записать как 1 :: 2 :: 3 :: Nil. Два списка xl и yl соединяются с помощью символа «:::». Например, List (1, 2) ::: List (3, 4, 5) создают List (1, 2, 3, 4, 5).

Язык Scala поддерживает выражения if-then-else, классы case, операторы while-loop, do-while-loop, итератор foreachloop, определяет итерацию forloop и рекурсивные вызовы функций. Передавая функцию в качестве параметра в другую функцию, можно смоделировать композицию. Кроме того, Scala поддерживает обновление в индексированных переменных, что позволяет разрабатывать программы на основе обычных итераций.

Рассмотрим еще один пример объявления функции:

def factorial(n: Int): Int =
{                  if (n == 0) 1
                   else n * factorial(n – 1)
}

Здесь функция описывает факториал и объявляет тип аргумента и тип результата как целочисленный. Предусмотрен рекурсивный вызов функции.

Scala является блочно-структурированным языком, где функции могут вкладываться внутрь других функций. Локальные переменные имеют область действия внутри блоков, где они были объявлены. Внутри вложенного блока переменные, объявленные во внешних блоках, могут быть перекрыты. Scala поддерживает концепцию модуля с использованием пакетов Java и может импортировать методы по предложению import. По умолчанию Scala импортирует все библиотеки классов Java и любую предопределенную библиотеку в Scala перед выполнением программы. Для передачи параметров Scala использует передачу по значению, а также передачу по имени. Синтаксис передачи по имени: : ‘=>’ , тогда как синтаксис передачи по значению имеет вид : . Scala использует возможности обработки исключений Java.

Примеры программного кода на Scala

def add7(n: Int): Int = {n + 7} // функция добавляет 7 к числу

Функция add7 добавляет 7 к входному параметру n и возвращает значение. Обратите внимание, что тип параметра и тип результата функции объявлены явно. Тело функции является блоком и заключено в фигурные скобки.

def int_square(x: Int): Int = {x * x} // возведение в квадрат целых
def square_add(x: Int): Int = int_square(add7(x)) // композиция

Функция square_add показывает композицию двух функций: square и add7. Сначала функция add7 применяется для генерации числа, которое на 7 больше входного параметра, а затем сгенерированное значение возводится в квадрат. Например, square_add (5) эквивалентно square (5 + 7) = 144.

def power_rec(x: Double, n:Int): Double =
{if (n == 0) 1 else x * power_rec(x, n-1)} // if-then-else и рекурсия

Функция power_rec иллюстрирует использование выражения if-then-else и рекурсии в Scala. Обратите внимание, что предикат заключен в круглые скобки и нет никакой мутации (изменения значений переменных).

def power_iter(x : Int, n: Int): Int = //итерационная версия power
{                var a = n; var b = 1;
                  while(a > 0 ) {b = x * b; a = a - 1}// обновление переменных
}

Напротив, функция power_iter использует локальные изменяемые переменные a и b для вычисления значения функции xn. Значение накапливается в аккумуляторе b и, наконец, возвращается после завершения цикла while.

def sum_list(xl:List[Int]): Int = // рекурсия над списками
{                if (xs.isEmpty) 0
                   else xl.head + sum_list(xs.tail)
}

Функция sum_list добавляет все целые числа в список, используя рекурсивный вызов в остальной части списка. Встроенный метод isEmpty используется для проверки пустого списка, метод head применяется для доступа к первому элементу списка, а метод tail обеспечивает доступ к остальным элементам списка.

def apply_all(my_func:Int => Int, xl:List[Int]): List[Int] =
{xl map my_func}

Scala использует встроенную функцию отображения map, которая обеспечивает возможность применения функциональной формы apply_all. Здесь в теле функции сначала записывается параметр (xl), затем функция отображения высшего порядка (map), а затем имя функции (my_func). В этом случае apply_all (int_square, List (1, 2, 3)) будет генерировать список List (1, 4, 9). Следует отметить способ объявления типа для функции my_func. Тип функции объявлен как Int => Int, что означает, что он принимает входной аргумент типа integer и генерирует выходное значение типа integer.

def construct(my_funcs:List[Int => Int], n:Int): List[Int] = // разработка
{                if (my_funcs.isEmpty) Nil
                    else my_funcs.head(n)::construct(my_funcs.tail, n)
}

Наконец, функция construct берет последовательность функций, применяемых к одному и тому же аргументу, и генерирует последовательность выходных значений. Например, construct (List (add7, int_square), 5) будет генерировать список List (12, 25). Программа с функцией construct возвращает нулевой список, если список функций пуст. В противном случае она вызывает рекурсивно из списка остальные функции и объединяет результат применения первой функции с остальной частью выходной последовательности, полученной путем применения остальных функций к этому же аргументу.

Рецензенты:

Соколов Б. В., д. т. н., профессор, руководитель лаборатории информационных технологий
в системном анализе и моделировании Санкт-Петербургского института информатики
и автоматизации РАН;

Пасмуров А. Я., д. т. н., доцент, senior member of IEEE, руководитель учебного центра ФГУП

«ЗащитаИнфоТранс» Министерства транспорта РФ, Санкт-Петербургский филиал.

» Более подробно с книгой можно ознакомиться на сайте издательства

» Оглавление

» Отрывок

Для Хаброжителей скидка 20% по купону — Орлов

Теория языков программирования и методы трансляции

Определение 1

Теория языков программирования и методы трансляции — это основы автоматизации написания программных продуктов.

Введение

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

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

Готовые работы на аналогичную тему

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

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

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

Классификация языков программирования

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

• Первым поколением языков программирования являются машинные языки.
• Вторым поколением считаются языки ассемблера.
• Языками третьего поколения являются языки высокого уровня типа Фортан, Алгол и другие.
• Языками четвёртого поколения считаются программные языки, которые разработаны для отдельных специальных сфер использования, где достичь желаемых итогов можно только применением проблемно ориентированных языков, которые используют понятия конкретной узконаправленной сферы. Каждый язык этого поколения разрабатывался, чтобы снизить затраты времени на формирование программ. К четвёртому поколению относятся языки обращения к базам данных, обрабатывания данных и средства генерации программных кодов для языков третьего поколения.
• Языками пятого поколения являются языки программирования, которые базируются на логических принципах или ограничениях (Prolog и OPS5).

Существует и другой способ классификации языков программирования, который базируется на четырёх принципах, описывающих реальные способы написания программ:

1. Императивный.
2. Функциональный.
3. Декларативный.
4. Объектно-ориентированный.

Императивные программные языки дают описание вычислительного процесса в формате команд, которые меняют состояние программы. Этот тип языков был написан для компьютеров класса Фон Неймана, у которых информационные данные и управляющая программа находятся вместе в оперативной памяти. Центральный процессор выбирает из оперативной памяти текущую команду, выполняет её декодирование, считывает из памяти нужную информацию, осуществляет выполнение команды и отправляет снова в память итоги выполнения команды. Базовыми компонентами императивных языков считаются переменные, которые моделируют ячейки памяти компьютера.

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

Декларативными языками называются языки, которые дают указание на то, какие вычислительные операции требуется исполнить. В качестве примера таких языков можно привести языки, базирующиеся на логическом программировании, то есть на наборе инструкций. Выполнение команд в этом логическом языке осуществляется не в очерёдности их написания, а в очерёдности, которую определяет система, реализующая правила. Самым известным языком этого типа считается язык Prolog. Языки декларативного типа используются, главным образом, в экспертных системах, системах работы с текстом на обычных языках.

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

НОУ ИНТУИТ | Теория и реализация языков программирования

Форма обучения:

дистанционная

Стоимость самостоятельного обучения:

бесплатно

Доступ:

свободный

Документ об окончании:

Уровень:

Профессионал

Длительность:

22:52:00

Выпускников:

589

Качество курса:

4.45 | 4.29

В курсе излагаются основные разделы
теории разработки компиляторов. Рассматриваются такие
средства автоматизации процесса разработки трансляторов, как LEX, YACC, СУПЕР, методы генерации оптимального кода.

Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора.

Теги: beta, FPA, objective-c, YACC, автоматы, алгоритмы, анализ, внутренняя вершина, вычисления, дерево вывода, компиляторы, левая рекурсия, нетерминал, подцепочка, поиск, программирование, процедуры, регулярное множество, регулярные выражения, статическая цепочка, трансляторы, указатели, функция расстановки, элементы

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

2 часа 30 минут

—

Введение

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

—

Языки и их представление

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

—

Лексический анализ

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

—

Синтаксический анализ

В данной лекции рассматривается понятие синтаксического анализа. Приводятся определения понятий упорядоченного графа, дерева вывода, автомата с магазинной памятью и его конфигурации. Приведены примеры задач, алгоритмов и доказательства теорем синтаксического анализа.

—

Элементы теории
перевода

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

—

Проверка контекстных условий

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

—

Организация таблиц
символов

В данной лекции рассматривается организация таблиц символов. Рассмaтриваются некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные деревья и реализация блочной структуры. Приведены также примеры программного кода и графическая интерпретация таблиц символов и идентификаторов.

—

Промежуточное
представление
программы

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

—

Генерация кода

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

—

Системы автоматизации построения трансляторов

В данной лекции рассматриваются системы автоматизации построения трансляторов на примере систем автоматизации построения трансляторов СУПЕР и YACC. Приведены структуры этих систем, основные термины и определения и части программного кода реализации систем автоматизации построения трансляторов.

—

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

Программисты часто сталкиваются с проблемами чтения математических нотаций, когда пытаются разобраться с теоретическими основами какого-либо языка программирования. Также с ними толкнулся и я в своих теоретических изысканиях. К счастью, мне очень помогла замечательная статья Джереми Сиека (Jeremy Siek), чьим переводом я хочу с вами поделиться. Надеюсь она поможет многим программистам-«не математикам».

Вступление

Этим постом я хочу помочь моим друзьям с чтением других моих постов. Это ускоренный курс по нотациям, используемым в теории языков программирования (ТЯП). Для гораздо лучшего изучения темы я рекомендую «Types and Programming Languages» от Benjamin C. Pierce и «Semantic Engineering with PLT Redex» от Felleisen, Findler, and Flatt. Я предполагаю, что читатель опытный программист, но не так хорош в математике и ТЯП. Я начну с базовых определений и попытаюсь быстро ввести вас в курс дела.

Множества, кортежи, отношения и определения правилами

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

Множества

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

Кортежи

Другой строительный блок — это кортеж, т.е. упорядоченная коллекция объектов. Т.о. (0, 1, 2) является кортежем из трех элементов и он отличается от кортежа (0, 2, 1). Подстрочая нотация t_i означает i-й (с индексом i) элемент кортежа t. Например, если t = (0, 2, 1), тогда t₁ = 0, t₂ = 2, t₃ = 1. Кортежи всегда содержат конечное количество элементов и обычно достаточно немного. Иногда для обозначения кортежей используются угловые скобки вместо круглых: .

Отношения

Комбинируя кортежи и множества мы получаем отношения. Отношение — это множество кортежей.

{(0, 1), (1,2), (2, 3), (3, 4), …}

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

Определение правилами

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

1. (0, 1) ∈ R.
2. Для любых натуральных чисел n и m, если (n, m) ∈ R, то (n + 1, m + 1) ∈ R.

Когда мы используем правила для определения множества, мы подразумеваем, что элемент не входит в множество, если нет способа использовать данные правила, чтобы оправдать нахождение этого элемента в множестве. Так (0, 0) не входит в R, потому что с помощью указанных правил нельзя обосновать, что (0, 0) туда входит.
Некоторые наборы правил бессмысленны и не определяют множество. Например, правила не должны противоречить друг другу, как здесь:

1. (0, 1) ∈ R.
2. (0, 1) ∉ R.

Учебник по ТЯП описывает ограничения для «хороших» наборов правил, но мы не будем в это углубляться. Скажем только, что хотя бы одно правило должно быть нерекурсывным и подобные логические противоречия должны отсутствовать.
Общераспространенная нотация для правил, как выше, использует горизонтальную черту между «if» и «then». Например, эквивалентное определение для R дается следующим образом.
Мы опустили «для любых натуральных чисел n и m» из правила 2. Используется соглашение, согласно которому переменные, такие как n и m, которые появляются в правиле, могут быть заменены любым объектом корректного типа. В данном случае натуральным числом. Часто, «корректный тип», это что-то о чем можно догадаться из контекста беседы. В данном случае — натуральные числа.
Предположим, я утверждаю, что некоторый элемент входит в R. Скажем, (2, 3) ∈ R. Вы можете ответить, что не верите мне. Чтобы вас убедить, мне нужно показать, как правила оправдывают, тот факт, что (2, 3) ∈ R. Я должен показать вам вывод. Вывод — это цепочка правил, в которой переменные, такие как n и m, заменяются конкретными значениями и предпосылки, такие как (n, m) ∈ R, заменяются более конкретными выводами.
Я пометил каждый шаг в выводе номером правила. Причудливое название для того, что я называю «определение правилами» — индуктивное определение.

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

Оказывается, что использование правил для определения множеств, как мы делали выше, подходит и для определения синтаксиса языка программирования. Предположим, что нам нужно определить простой язык для целочисленной арифметики. Назовем его Arith. Он будет содержать выражения, такие как 1 + 3 и -(5 + 2). Вспомним, что Z — множество целых чисел. Тогда множество правил, описывающих Arith, будет таким:

• Для любого i ∈ Z верно, что i ∈ Arith.
• Для любого e, если e ∈ Arith, тогда -e ∈ Arith.
• Для любого e1 и e2, если e1 ∈ Arith и e2 ∈ Arith, тогда e1 + e2 ∈ Arith.
• Для любого e, если e ∈ Arith, тогда (e) ∈ Arith.

Бэкуса-Наура форма (БНФ) — другая распространенная нотация для записи правил, определяющих синтаксис языка, которая означает тоже самое. (Существует несколько вариантов БНФ. Я забыл, какую именно использую здесь.) Набор правил называется грамматикой.

Arith ::= integer
Arith ::= "-" Arith
Arith ::= Arith "+" Arith
Arith ::= "(" Arith ")"

Вертикальная черта (означающая «или») часто используется для того, чтобы сделать синтаксис более кратким.

Arith ::= integer | «-» Arith | Arith «+» Arith | «(» Arith «)»

В ТЯП мы используем своеобразный вариант БНФ, который заменяет имя определяемого языка, в данном случае Arith, на переменную, которая используется для прохода по элементам Arith. Теперь предположим, что используем переменную i как заполнитель (placeholder) для целых чисел и e как заполнитель для элементов Arith. Тогда мы можем записать нашу грамматику так:

e ::= i ∣ −e ∣ e + e

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

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

Описать язык, значит описать, что произойдет при запуске программы на этом языке. Именно это делает операционная семантика. В случае с Arith нам нужно указать целочисленный результат для каждой программы. Как было сказано выше, мы можем использовать отношения для отображения входных данных на результат. И обычно мы так и делаем в ТЯП. Есть несколько различных стилей отношений. Первый, который мы рассмотрим, это семантика большого шага (big-step semantics), которая отображает программу прямо на её результат.

Семантика большого шага (big-step semantics)

Определим отношение Eval, которое отображает элементы Arith на целые числа. Например, должно выполняться условие (−(2 + −5), 3) ∈ Eval. Это отношение будет бесконечным (потому что существует бесконечное количество программ на Arith). И снова мы будем использовать набор правил для определения Eval. Но перед тем как мы начнем, введем сокращение: означает (e, i) ∈ Eval. Ниже мы опишем правила, определяющие Eval с использованием нотации с горизонтальной чертой. Чтобы убедиться, что не пропустим ни одной программы, создадим одно правило для каждого синтаксического правила Arith (их три). Будем говорить, что правила синтаксически-ориентированные, когда одно правило соответствует каждому синтаксическому правилу языка.
Это может показаться немного странным, что я определил «-» в терминах «-» и «+» в терминах «+». Не циклическая ли это зависимость? Ответ — нет. Плюс и минус — это обычные арифметические операции для целых чисел, которые каждый проходит в школе. В этом смысле более странным для Arith было бы не использовать 32 или 64-битную арифметику. Программист, реализующий Arith, мог бы использовать пакет для работы с BigInteger, чтобы обрабатывать арифметику.

Семантика малого шага (small-step semantics)

Второй и наиболее распространенный стиль операционной семантики — это семантика малого шага. В этом стиле отношение не отображает программу на её результат. Вместо этого оно отображает программу на слегка упрощенную программу, в которой какое-то подвыражение заменяется его результатом. Можно думать об этом стиле, как о текстовой замене. Чтобы дать пример этого стиля, определим отношение Step. Это отношение будет содержать следующие элементы, как и многие другие:

(-(2 + -5), -(-3)) ∈ Step
        (-(-3), 3) ∈ Step

Снова введем сокращение: означает (e1, e2) ∈ Step. И если мы соединим шаги вместе, то будет означать и . Синонимом для шага (step) будет термин «сократить» (reduce). Предыдущий пример из двух шагов может быть записан теперь так:

Теперь перейдем к правилам, определяющим отношение Step. Здесь пять правил, которые мы объясним ниже.

Правила (1) и (2) наиболее интересные. Они выполняют арифметику. Мы называем их «вычислительные правила сокращения» (computational reduction rules). Правила (3-5) позволяют нам заходить в подвыражения для выполнения вычислений. Они часто называются правилами соответствия (congruence rules) по причинам в которые мы сейчас не будем вдаваться. Использование переменной i в правиле (5) означает, что сокращение происходит слева направо. В частности, мы не позволяем сокращать правое выражение от знака + до тех пор, пока левое выражение не будет сокращено до целого числа.

Отступление: Рассматриваемый здесь порядок «слева направо» я выбрал как дизайнер языка. Я мог бы не определять порядок, позволяя быть ему неопределенным. Наш язык не имеет побочных эффектов, поэтому порядок не имеет значения. Однако, большинство языков имеют побочные эффекты и они определяют порядок (но не все), поэтому я подумал, что нужно рассмотреть пример того, как обычно определяет порядок.

Время для примера. Посмотрим на вывод для шага:

Мы определили один шаг вычислений, т.е. отношения Step. Но мы не совсем закончили. Мы ещё должны определить, что значит выполнить программу до завершения. Мы сделаем это с помощью определения Eval’ в терминах отношения Step. Иными словами, отношение Eval’ будет содержать любые пары (e, i) если выражение e сокращается до целого i за ноль или более шагов. Здесь присутствует новая нотация, которая объясняется далее.

Нотация {…∣…} определяет конструктор множества. Выражение слева от вертикальной черты определяет шаблон для типичного элемента множества и выражение справа — ограничения на элементы множества. Нотация означает ноль или более шагов. Я бы определил эти многошаговые отношения с помощью правил:

(Я думаю об этом в терминах Lisp-подобных списков. Так, первому правилу соответствует nil, а второму cons.)

Системы типов (с лямбда-исчислением в качестве примера)

Многие языки программирования статически типизированы, т.е. компилятор выполняет некоторые проверки корректности прежде, чем выполнить реальную компиляцию. Обычно, во время проверки компилятор убеждается в том, что объекты используются так, как должны. Например, что никто не пытается использовать целое число как функцию. Способ, которым разработчик языка указывает какие именно проверки должны быть выполнены, является определение системы типов для языка. Язык Arith настолько прост, что в нем нет никаких интересных проверок типов. Рассмотрим более сложный язык, который снова и снова используется в ТЯП — лямбда-исчисление (технически, лямбда-исчисление с упрощенной типизацией). Лямбда-исчисление состоит только из анонимных функций. Мы же расширим лямбда-исчисление так, чтобы оно включало наши арифметические выражения. Тогда наш язык будет определяться следующей грамматикой.

e ::= i ∣ −e ∣ e + e ∣ x ∣ e e ∣ λx:T.e

Переменная x перечисляет имена параметров, такие как foo и g. Следующие справа два выражения (e e) означают применение функции (или вызов функции). Если вы знакомы с языком C, можете читать e1 e2 как e1(e2). В лямбда-исчислении функции принимают только один параметр, поэтому вызов функции требует только один аргумент. Синтаксис λx:T.e создает функцию с одним параметром x типа T (типы мы скоро определим) и телом, состоящим из выражения e. (Часто люди заблуждаются думая, что x — это имя функции. На самом деле это имя параметра, т.к. функции являются анонимными, т.е. не имеют имени.) Возвращаемым значением функции будет результат выражения e. Теперь подумаем о том, какие объекты будут существовать во время выполнения программы. Это целые числа и функции. Мы создадим множество типов для описания сортов объектов, используя T для перечисления множества типов.

В функциональном типе , T₁ является типом параметра, а T₂ типом возвращаемого значения.

Работа системы типов заключается в том, чтобы прогнозировать, какой тип значения будет у результата выражения. Например, выражение -(5 + 2) должно иметь тип Int, потому что результат -(5 + 2) — это число -3, которое является целым. Также как в случае определения синтаксиса или операционной семантики языка, ТЯП-теоретик использует отношения и правила для определения системы типов. Мы определим отношение WellTyped, которое, в первом приближении, отображает выражения на типы. Например, будет выполнено (-(5 + 2), Int) ∈ WellTyped.

Однако, т.к. лямбда-исчисление включает переменные, мы нуждаемся в неком аналоге таблицы символов, отношении, называемом окружением типов (type environment), для отслеживания какие переменные имеют какой тип. Греческая буква Γ (гамма) обычно используется для этой цели. Мы должны быть способны создать новое окружение типов из старого, с возможностью скрывать переменные из внешних областей видимости. Чтобы определить математический аппарат для этих возможностей, положим, что Γ∖x будет отношением, таким же как Γ, за исключением того, что любой кортеж, начинающийся с x будет исключен. (В зависимости от способа, каким будет определена система типов, может быть 0 или 1 кортеж, который начинается с x, делая окружение типов специальным видом отношения, называемого частичная функция (partial function).) Мы будем писать Γ,x:T для операции расширения окружения типов с помощью переменной x, возможно, переопределяющей предыдущее определение, и определяемой следующим образом:

Предположим, что
Тогда
Окружение типов отличается от глобальной таблицы символов в компиляторе тем, что может существовать более одного окружения типов, по одному для каждой области видимости. Кроме того, мы не обновляем окружение типов, вместо этого мы создаем новое окружение, которое слегка отличается от старого. С точки зрения программирования, математический метаязык, который мы здесь используем, является чистым функциональным (pure functional), т.е. он не содержит побочных эффектов. Читатель может беспокоится о том, что это ведет к неэффективности, но вспомните, что мы не пишем здесь программу, мы пишем спецификацию! Наибольшее значение для нас имеет понятность. И оставаясь чистыми мы можем писать более понятные вещи.
Возвращаясь к отношению WellTyped, вместо того, чтобы содержать кортежи из двух элементов (2-кортежи, пары) оно будет содержать кортежи из трех элементов (3-кортежи, тройки) вида (Γ, e, T). Таким образом мы будем приписывать типы выражениям в контексте окружения типов. Введем ещё одно сокращение (ТЯП-теоретики любят сокращения!). Будем писать вместо (Γ, e, T) ∈ WellTyped. Теперь мы готовы перечислить правила, определяющие WellTyped.
Подведем итог для правил выше. Арифметические операторы работают с целыми числами. Переменные получают свои типы из окружения. Лямбды являются функциональными типами основанными на типе их параметра и выводимом типе результата. Тело лямбды проверено с использованием окружения из точки создания (lexical scoping), расширенного с помощью параметра этой лямбды. И применение функции не нарушает логики языка до тех пор, пока тип аргумента совпадает с типом параметра.

Заключение

На этом заканчивается этот ускоренный курс по нотациям, используемым в теории языков программирования. Этот пост только описывает основы, но очень много дополнительных нотаций, которые вам понадобятся, являются вариациями рассмотренных здесь. Счастливого чтения и не стесняйтесь задавать вопросы в комментариях.

Теория и реализация языков программирования — ФУПМ

1. Введение

1.1. Место компилятора в программном обеспече­нии   

1.2. Структура компилятора

2. Языки и их представление

2.1. Алфавиты, цепочки и языки.

2.2. Представление языков

2.3. Грамматики

       2.3.1. Формальное определение грамматики

       2.3.2. Типы грамматик и их
свойства.

2.4. Машины Тьюринга

       2.4.1. Неразрешимость проблемы останова

       2.4.2. Класс рекурсивных множеств

2.5. Связь машин Тьюринга и грамматик типа
0

2.6. Линейно-ограниченные автоматы и их связь с
контекстно-зависимыми грамматиками

3. Лексический анализ

3.1. Регулярные множества и
выражения.

3.2. Конечные автоматы

3.3. Алгоритмы построения конечных
автоматов

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

       3.3.2. Построение детерминированного конечного автомата
по недетерминированному

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

       3.3.4. Построение детерминированного конечного автомата
с минимальным числом состояний

3.4. Связь регулярных множеств, конечных автоматов и
регулярных грамматик

3.5. Программирование лексического анализа.

3.6. Конструктор лексических анализаторов
LEX

4. Синтаксический анализ

4.1. Контекстно-свободные грамматики и автоматы с
магазинной памятью

4.2. Преобразования КС-грамматик

       4.2.1. Алгоритм Кока-Янгера-Касами

4.3. Предсказывающий разбор
сверху-вниз

       4.3.1. Алгоритм разбора сверху-вниз.

       4.3.2. Функции FIRST и FOLLOW .
.

       4.3.3. Конструирование таблицы предсказывающего
анализатора.

       4.3.4. LL(l)-грамматики. ..

       4.3.5. Удаление левой рекурсии

       4.3.6. Левая факторизация. .

       4.3.7. Рекурсивный спуск.

       4.3.8. Восстановление анализа после
синтаксических ошибок

4.4. Разбор снизу-вверх типа
сдвиг-свертка.

       4.4.1.Основа

       4.4.2. LR(l)-анализаторы

       4.4.3. Конструирование LR(l)-таблицы

       4.4.4. LR(l)-грамматики.

       4.4.5. Восстановление анализа после синтак­сических
ошибок. . . . . .

       4.4.6. Варианты LR-анализаторов

5. Элементы теории перевода

5.1. Преобразователи с магазинной памятью

5.2. Синтаксически управляемый перевод.
.

       5.2.1. Схемы синтаксически управляемого перевода.
.

       5.2.2. Обобщенные схемы синтаксически управляемого
перевода

5.3. Атрибутные грамматики

       5.3.1. Определение атрибутных
грамматик

       5.3.2. Классы атрибутных грамматик и их реализация            
.

       5.3.3. Язык описания атрибутных
грамматик

Теория языков программирования и методы трансляции

54

Саратовский
государственный технический университет
им.

Гагарина
Ю.А.

конспект
лекций

составил
Сайкин А.И.

Саратов,
2015

Данный
конспект представляет собой краткое
изложение лекционного курса, читавшегося
студентам по специальности «Программирование
вычислительной техники и автоматизированных
систем» в объёме 54 часа.

СОДЕРЖАНИЕ

Введение………………………………………………………………………..
4 1. Языки
и кризис программирования…………………………………………6

2.
Математические методы описания языков.
Формальные языки и

грамматики……………………………………………………………………8

3.
Основные понятия и определения…………………………………………..9

4.
Этапы построения трансляторов…………………………………………….16

5.
Основные методы поиска ошибок в исходных
текстах программ………..18

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

трансляторов………………………………………………………………….19

7.
Лексический анализ. Интуитивный
подход……………………………….21

8.
Классы лексем и их особенности…………………………………………..21

9.
Формирование таблиц лексем и построение
дескрипторного текста

исходной
программы………………………………………………………23

10.
Синтаксический анализ. Метод рекурсивного
спуска………………….26

11.
Пример грамматики упрощенного языка
Паскаль……………………..26

12.
Пример программы на упрощенном
Паскале…………………………..27

13.
Алгоритм синтаксического анализа по
методу рекурсивного спуска…31

14.
Формализация методов построения
трансляторов. Формальные

языки
и грамматики. Классификация формальных
языков

по
Хомскому………………………………………………………………..36

15.
Лексический анализ, регулярные грамматики
и конечные автоматы…39

16.
S-грамматики
и магазинные автоматы………………………………..…42

17.
Грамматики типа LL(k).
Алгоритмы построения магазинных

анализаторов……………………………………………………………….45

18.
Детерминированный синтаксический
анализ сверху вниз……………..50

19.
Правила определения детерминированного
МП-преобразователя

по
LL(1)
грамматике………………………………………………………52

20.
Заключение………………………………………………………………….54

Литература………………………………………………………………….54

Введение.

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

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

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

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

Таким
образом, современное программирование
возможно только на алгоритмических
языках, а применение их возможно только
при наличии трансляторов с них.

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

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

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

Теория категорий для программистов: предисловие / Хабр

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

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

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

Во-вторых, есть много различных видов математики, и все они предназначены для разных аудиторий. У вас может быть аллергия на математический анализ или алгебру, но это не означает, что вам не понравится теория категорий. Не побоюсь утверждать, что теория категорий — это именно тот вид математики, который особенно хорошо подходит для мышления программистов. Это потому, что теория категорий вместо того, чтобы иметь дело с деталями, оперирует структурой. Она оперирует такими понятиями, которые делают программы компонуемыми.

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

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

Конечно, с помощью размахивания руками вы рискуете сказать что-то откровенно неверное, поэтому я постараюсь убедиться, что позади неформальных аргументов в этой книге есть твердая математическая теория. У меня есть потертая копия книги Сандерса МакЛейна «Теория категорий для математиков» на моей тумбочке.

Поскольку эта книга о теории категорий для программистов, я проиллюстрирую все основные понятия, используя компьютерные программы. Вы, наверное, знаете, что функциональные языки ближе к математике, чем более популярные императивные языки. В них так же можно создавать более мощные абстракции. У меня было естественное искушение сказать: вы должны научиться Haskell, прежде чем теория категорий станет вам доступна, но это означало бы, что теория категорий не имеет никакого применения за пределами функционального программирования, а это просто неправда. Так что, я приведу много примеров на C++. Конечно, придется преодолеть уродливый синтаксис, и увидеть паттерны будет сложнее из за многословия, и вам, возможно, придется делать много copy-paste, вместо использования абстракций высшего порядка, но это и так большая часть жизни C++-программиста.

Однако, не все так просто с Haskell. Не нужно становиться программистом на нем, но придется его освоить в качестве языка для зарисовок идей, которые позже будут реализованы на C++. Именно так я и начал программировать на Haskell. Его краткий синтаксис и мощная система типов очень помогли мне с пониманием и реализацией C++-шаблонов, структур данных и алгоритмов. Однако, так как я не могу ожидать, что читатели уже знают Haskell, я введу его постепенно и объясню все на ходу.

Если вы опытный программист, вы можете думать: я давно программирую и не беспокоюсь ни о какой теории категорий или функциональных методах, зачем же что-то менять? Конечно, вы не можете не заметить, что в императивных языках устойчивый тренд на добавление новых функциональных возможностей. Даже Java, бастион объектно-ориентированного программирования, добавила лямбды. C++ недавно начал развиваться бешеными темпами, — новые стандарты каждые несколько лет, — пытается догнать меняющийся мир. Вся эта деятельность — подготовка к разрушительным изменениям или, как мы, физики, называем это, смена фазы. Если вы нагреваете воду, она в конце концов закипит. Сейчас мы находимся в положении лягушки, которая должна решить, продолжать ли плавание в нагревающейся воде, или начать искать альтернативы.

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

Даже при отсутствии параллелизма, растущая сложность программных систем испытывает пределы масштабируемости императивного программирования. Проще говоря, побочные эффекты выходят из-под контроля. Функции с побочными эффектами легко и удобно писать. Побочные эффекты могут, в принципе, быть закодированы в их названиях и комментариях. Функция с названием SetPassword или WriteFile, очевидно, изменяет некое состояние и имеет побочные эффекты, и мы к этому привыкли. И только тогда, когда мы начинаем писать функции, имеющие побочные эффекты, работающие с другими функциями, имеющими побочные эффекты, и так далее, тогда вещи начинают становиться сложными. Не то чтобы побочные эффекты изначально плохи, плохо то, что они скрыты от глаз. Из за этого, в более крупных масштабах, становится невозможным ими управлять. Побочные эффекты не масштабируемы, а императивное программирование полностью построено на побочных эффектах.

Изменения в железе и растущая сложность программного обеспечения заставляют нас переосмыслить основы программирования. Так же, как строители великих готических соборов Европы, мы, в нашем ремесле, подходим к пределам материалов и структуры. В Бове, во Франции, есть недостроенный готический собор, который стоит свидетелем этой человеческой борьбы с естественными ограничениями. Задумывалось, что он побьет все предыдущие рекорды высоты и легкости, но в процессе постройки произошел ряд обрушений. От полного разрушения его защищают «костыли»: железные прутья и деревянные опоры. С современной точки зрения, чудо, что так много готических сооружений было успешно завершено без помощи современного материаловедения, компьютерного моделирования, анализа методом конечных элементов и общей математики и физики. Я надеюсь, что будущие поколения будут так же восхищены навыками программирования, которые мы демонстрируем, строя сложные операционные системы, веб-сервера и интернет-инфраструктуру. И, честно говоря, они и должны, потому что мы сделали все это на очень хлипкой теоретической основе. Наша задача — улучшить эти основы, если мы хотим двигаться вперед.

Костыли, защищающие собор в Бове от разрушения.

Продолжение следует.

Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Категории Клейсли

Содержание | Основы языка программирования в Agda

Эта книга представляет собой введение в теорию языков программирования с использованием
помощник доказательства Агда.

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

Фасад

Часть 1: Логические основы

Часть 2: Основы языка программирования

• Лямбда: Введение в лямбда-исчисление
• Недвижимость: Прогресс и Сохранение
• DeBruijn: внутренне типизированное представление де Брюйна
• Подробнее: Дополнительные конструкции простого типизированного лямбда-исчисления
• Бисимуляция: относящиеся системы редукций
• Вывод: двунаправленный вывод типа
• Нетипизированный: нетипизированное лямбда-исчисление с полной нормализацией
• Слияние: Слияние нетипизированных лямбда-исчислений
• BigStep: семантика большого шага нетипизированного лямбда-исчисления

Часть 3: денотационная семантика

• Денотационный: Денотационная семантика нетипизированного лямбда-исчисления
• Композиционный: денотационная семантика является композиционной
• Разумность: Разумность редукции относительно денотационной семантики
• Адекватность: Адекватность денотационной семантики по отношению к операционной семантике
• ContextualEquivalence: Денотационное равенство подразумевает контекстную эквивалентность

Приложение

Backmatter

Списки рассылки

• плфа-проценты @ инф.ed.ac.uk:
  Список рассылки для пользователей книги.
  Здесь можно задать вопросы и ответить на них или прокомментировать содержание книги.
• [email protected]:
  Список рассылки для участников.
  Это место, где обсуждаются изменения и новые дополнения в книге с мельчайшими подробностями.

Читаемые курсы по учебнику

2020

2019

2018

Расскажите, пожалуйста, о других!

.

новейших вопросов по теории языка — qaru

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

2. Авторизоваться
   зарегистрироваться

3. текущее сообщество
   

   • Переполнение стека

     Помогите

.

No related posts.