Understanding computation
Я в полном восторге от книги. По содержанию - это введение в теорию вычислений. По форме - пошаговые инструкции на руби по реализации разных интерпретаторов и виртуальных машин. Она состоит из трёх больших разделов.
Первый про языки и интерпретаторы. Пробуем по разному задать семантику языка, собрать синтаксическое дерево и написать простой интерпретатор. Возня с парсерами естественно решена одной рубёвой библиотекой.
Второй про модели вычислений. Всё классически: детерминированые-недетерминированные машины с состояниями, машины с состояниями и памятью, разбор языков с их помощью. Только собственно берём и программируем их. Машина Тьринга, лямбда-исчисление. Чувак реально пишет fizz-buzz на одних лямбдах! Не то чтобы я не верил другим книжкам, но вот прям взял и убедился что оно реально рaботает. Под конец рассказывает о SKI и еще нескольких экзотических моделях.
Третья часть больше про теорию. Кратко и уже только с эскизами кода рассматриваем решаемые/нерешаемые машиной Тьюринга задачи. Ковыряем задачу останова. Смотрим на некоторые опции model-checking и пишем простой чекер.
В общем всё самое интересное и хоть как-то соотносящееся с практикой программирования в одном издании. У меня новая #1 рекомендованная книга по CS.