Серия скринкастов "Вычисления"

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

1. Введение в вычисления 

Это краткий обзор тем, которые мы рассмотрим в остальной части этой серии: машины Тьюринга, исчисление лямбда, проблема остановки, эквивалентность Тьюринга и иерархия Хомского. 

2. Вычисление путем изменения 

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

3. Мощность машин Тьюринга 

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

4. Вычисление путем построения 

Мы пишем простую, легко читаемую примерную функцию в Python. Затем удаляем функции Python одну за другой, превратив все это в лямбда-исчисление. В конце нет ничего, кроме (1) определений функций, которые принимают ровно один аргумент и (2) вызова функции с одним аргументом. В конце все еще есть вспомогательные функции, которые используют функции Python. В следующий раз мы удалим все из них, переопределяя числа и логические точки с нуля, используя только функции одного аргумента. 

5.  Мощность исчисления лямбда 

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

Примечание 1 (после того как вы просмотрели этот скринкаст): при преобразовании из цифр Church Numerals в числа Python нет ничего особенного (lambda x: x + 1) (0). Например, мы могли бы использовать (lambda x: x + "A") (""). В этом случае Church numeral 1 будет преобразовано в «А»; 2 будет преобразован в «AA» и тд.

Примечание 2: MULT можно записать немного более просто, поскольку lambda n: lambda m: n (ADD (m)) (ZERO), но более сложная версия, показанная в скринкасте, по-прежнему правильная.  

6. Пределы вычислений 

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

7. Распознавание простых языков 

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

8. Распознавание языков программирования 

Компиляторы и интерпретаторы должны понимать структуру кода для его запуска, так же как нам нужно понять структуру кода для его чтения. Этот скринкаст вводит контекстно-свободные языки, которые используются для определения синтаксисов Python, Lua, Lisp и многих других языков программирования. Начнем с простого синтетического примера, показывающего, почему контекстно-свободные языки более мощные, чем обычные языки. Затем мы рассмотрим фактические определения грамматики языков программирования Python и Lua. Мы анализируем фрагменты кода на каждом языке, используя определения грамматики языков, чтобы увидеть структуру кода так же, как это видит компилятор или интерпретатор. 

9. Самые сложные языки 

Мы заканчиваем иерархию Хомского, рассматривая контекстно-зависимые языки (включая C, JavaScript и многие другие языки программирования) и неограниченные грамматики, которые являются Тьюрингом. Мы также связываем неразрешимые проблемы с иерархией Хомского, рассматривая их как пятый уровень. Удивительно, но есть как минимум один язык программирования, грамматика которого технически неразрешима. 

10. Заключительные замечания по расчетам 

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

(Примечание: grammar-grammar, показанная в этом скринкасте, на самом деле не является грамматикой для себя по тривиальной причине: она использует двойные кавычки для литералов, но описывает только синтаксис с использованием одинарных кавычек. Изменение кавычек на '' " исправило бы проблему, хотя этот синтаксис менее понятен человеку, что не влияет на сделанные выводы.)