Когда от отвёртки требуют быть айфоном
Мужчина должен быть лишь чуть-чуть красивее обезьяны, а C — лишь чуть-чуть удобнее ассемблера.
Lisp: большая задача в маленькой формуле
Рекурсивное описание решения «Башен Ханоя» на Scheme, диалекте Lisp.
Стопку дисков нужно перенести на другой стержень, каждый раз снимая только верхний диск и не помещая большой поверх маленького. «Башни Ханоя» быстро становятся неудобной головоломкой, если перебирать ходы вручную. Рекурсивная формула на картинке описывает решение для любого количества дисков.
Lisp появился в 1958 году: Джон Маккарти разрабатывал его для задач искусственного интеллекта и работы с символами. Функции, списки и рекурсивные определения позволяли записывать сложные вычисления компактно. Непривычные скобки подчиняются простому правилу: сначала операция, затем её аргументы. Например, "(+ 2 3)" означает сложение двух чисел.
Алонзо Чёрч — создатель лямбда-исчисления.
За этим подходом стоит более ранняя математическая история. В 1930-х годах Алонзо Чёрч разработал лямбда-исчисление — систему, в которой вычисления описываются через функции и их применение. Функция может принимать другую функцию и возвращать новую. Из небольших преобразований складываются более сложные. Маккарти заимствовал у Чёрча лямбда-обозначение для записи функций в Lisp.
Решение головоломки строится из трёх частей: перенести верхние "n − 1" дисков на свободный стержень, перенести нижний диск на целевой, затем поставить на него маленькую стопку. Оба переноса меньшей стопки выполняются по тому же правилу. В этой записи "move" обозначает чистое преобразование состояния башен, а "compose" соединяет преобразования, применяя их справа налево. Поэтому строки внутри него читаются снизу вверх. При нуле дисков остаётся "identity" — преобразование, которое ничего не меняет. Эти вспомогательные определения опущены, чтобы оставить на виду саму рекурсию.
Как видите, всё элементарно, поэтому мнение, будто для программирования нужен особый склад ума, совершенно беспочвенно.
Показать полностью
1