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

[cs0ip]

Если у кого-то не отображаются какие-то символы юникода, то пишите в ЛС или на e-mail из профиля. А я пока по возможности буду заменять на картинки. Выяснилось, что у некоторых пользователей с этим проблемы.

[leshabirukov]

А языки с зависимыми типами в данную схему типизации укладываются?

[cs0ip]

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

[Atakua]

По этой же теме (теоретические основы CS для простых программистов) недавно наткнулся на отличную книгу:
Том Стюарт. Теория вычислений для программистов / Пер. с анг. А.А. Слинкин. — Москва, ДМК Пресс, 2014. — 384 с.
Я был удивлён, как в довольно простой форме, шаг за шагом, в ней объясняются те вещи, которые я не мог понять долгое время из других публикаций, например, числа Чёрча. Все примеры кода в ней на Руби, который я не очень знаю, но опять же, оказалось, что выбранный автором подход очень удачно использует динамический язык для иллюстрации всех идей.

[vadimr]

Описать язык, значит описать, что произойдет при запуске программы на этом языке. Именно это делает операционная семантика.

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

А в целом хорошая статья.