Hacker News Digest

tinylisp — лисп-интерпретатор всего на 99 строк C.
Включает 21 примитив, сборщик мусора и REPL.
Доступны варианты с оптимизацией хвостовой рекурсии для ускорения и экономии памяти.

• Участники обсуждают крошечную реализацию Lisp, которую, по словам одного комментатора, могли писать для карманного компьютера Casio AI-1000 1989 г.
• Код раскритикован за «ужасный» стиль на C: злоупотребление double, нарушения strict aliasing и эндиан-зависимость.
• Предложены альтернативы: 100-строчный Lisp на Python, tinylisp, lispy.py Питера Норвига.
• Найдена синтаксическая ошибка в tinylisp (лишняя скобка) и отмечено отсутствие TCO, из-за чего Y-комбинатор не работает без доработки.

Хвостовая рекурсия превращает рекурсию в цикл: компилятор заменяет вызов на безусловный jmp, поэтому стек не растёт.

Обычная рекурсия кладёт промежуточные значения в стек, тратит O(n) памяти и вытесняет кэш.
Цикл же держит результат в аккумуляторе, использует O(1) памяти и линейное время.

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

Пример суммы списка

Обычная версия:

(define (sum l)
  (if (empty? l) 0
      (+ (first l) (sum (rest l)))))

Хвостовая версия:

(define (sum l acc)
  (if (empty? l) acc
      (sum (rest l) (+ acc (first l)))))

Аргументы l и acc перезаписываются «на месте», как переменные цикла.

Упражнение 1 — счётчик чётных/нечётных:

(define (even-odd l [e 0] [o 0])
  (if (empty? l) (cons e o)
      (let ([x (first l)])
        (if (even? x)
            (even-odd (rest l) (add1 e) o)
            (even-odd (rest l) e (add1 o))))))

Упражнение 2 — сглаживание дерева:
используйте аккумулятор-список и обход в обратном порядке, чтобы сохранить хвостовой вызов.

• Теоретически хвостовая рекурсия и циклы эквивалентны: любую хвостовую рекурсию можно превратить в цикл (и наоборот), но взаимно-рекурсивные функции требуют дополнительной работы.
• На практике циклы чаще проще для чтения и не ломают стек, тогда как хвостовая рекурсия нуждается в оптимизации (TCO), которую не все языки поддерживают (Python, V8 её нет).
• Некоторые языки (Scala, Clojure, F#) дают компромиссные конструкции (@tailrec, recur), сохраняющие функциональный стиль и гарантирующие отсутствие переполнения стека.
• Вместо явной хвостовой рекурсии часто достаточно высокоуровневых комбинаторов вроде fold/map, но они не всегда позволяют досрочный выход и могут расходовать O(N) памяти.
• Участники сходятся во мнении: владеть обоими подходами полезно, выбор зависит от языка, задачи и привычек команды.