Hacker News Digest

Эта работа представляет спецификацию алгебраического языка для манипуляции символьными выражениями, разработанного Джоном Маккарти. Язык предназначен для программирования формальных математических процессов (алгебраическое упрощение, дифференцирование, интегрирование), написания компиляторов (кроме ввода/вывода) и эвристических программ, где удобно представлять деревья альтернативных действий. Он особенно эффективен для работы с выражениями переменной длины и структуры, имеющими подобподвыражения, но менее удобен для списков фиксированной длины.

Выражения в языке представляются списками, где каждый элемент занимает машинное слово, содержащее данные и адрес следующего элемента. Маккарти отмечает, что удобство алгебраической нотации связано с возможностью композиции функций без именования промежуточных результатов и построения сложных структур путем вложения вызовов функций, формирующих списки. Ключевыми особенностями языка являются поддержка рекурсии с автоматическим сохранением промежуточных результатов в структурах списков и мощные условные выражения, решающие проблему выбора операций на основе результатов тестов. Маккарти ссылается на ранние работы Ньюэлла, Саймона и Шоу по эвристическому программированию и Гелентера в геометрической программе как предшественников.

• Появление первых отчетов о LISP в 1958 году стало поворотным моментом, поскольку они ввели ключевые концепции, которые позже стали основой для многих языков программирования.
• Исторически важно, что McCarthy и его команда в MIT в 1958 году разработали и документировали эти ранние отчеты, включая в них идеи, которые до сих пор используются в современных языках.
• Отчеты показали, как LISP влиял на развитие компьютерных наук, включая идеи о списковой обработке, рекурсии, и функциональном программировании.
• Несмотря на то, что эти отчеты были написаны более 60 лет назад, они до сих пор влияют на разработку языков программирования и остаются актуальными для изучения истории ИИ и вычислительных наук.
• Некоторые участники обсуждения подчеркнули, что эти отчеты не только исторически важны, но и могут быть использованы для образовательных целей, чтобы изучать основы компьютерных наук и эволюцию языков программирования.

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

Автор мотивирует необходимость рекурсивных макросов возможностью обрабатывать переменное количество аргументов, что особенно ценно для создания безопасных вариадических функций. Цель статьи — создать макрос, считающий количество аргументов, что позволит автоматически добавлять проверки и избегать ошибок, связанных с ручным подсчётом. Хотя система макросов кажется устаревшей, она остаётся единственным механизмом компиляции времени в C, делая изучение этих техник важным для разработчиков.

• Обсуждение охватывает историю и ограничения препроцессора C, включая его влияние на языки C и C++, а также затрагивает вопросы безопасности (DoS-риски) и читаемости кода.
• Участники обсуждают, что препроцессор не предназначен для сложной метапрограммирования, и что современные языки предлагают более безопасные и выразительные альтернативы.
• Также обсуждается, что хотя препроцессор и может быть использован для продвинутых задач метапрограммирования, он требует нестандартных и сложных приемов, что делает его использование непрактичным и потенциально опасным.
• Некоторые участники упоминают, что препроцессор может быть использован для создания сложных макросов, которые могут быть использованы для создания DSL или для экспериментов с синтаксисом языка, хотя это может быть опасным.
• В целом, обсуждение подчеркивает, что хотя препроцессор может быть использован для сложных задач, он не предназначен для этого и что современные языки предлагают более безопасные и выразительные средства для решения таких задач.

Автор рассказывает о своем пути к любви к Erlang, начавшегося с непонимания базовых концепций программирования в восемь лет, когда столкнулся с выражением "X = X + 1" в BASIC, показавшимся ему математической ложью. В университете он столкнулся с такими же трудностями при изучении C, но продолжил учиться через практику и эксперименты. Переломный момент наступил, когда партнер по бриджу спросил, как суммировать числа от 1 до 10 без циклов, что привело его к открытию рекурсии в Prolog — математически чистого подхода, где описывалось "что" является, а не "как" вычислять.

Знакомство с Erlang произошло случайно на турнире по бриджу от шведского игрока, который описал его как функциональный язык для распределенных, отказоустойчивых систем. Автор был поражен возможностью простого обмена сообщениями между разными узлами без сложных протоколов, демонстрируя пример ping-pong на Erlang. Этот язык, сочетающий функциональность, распределенность и отказоустойчивость, стал тем, что он искал с детства — способом программирования, где математика говорит правду.

• @az09mugen отмечает полезность функции > cd .. в конце статьи за простоту и мобильную доступность.
• @az09mugen предполагает наличие пасхалки (easter egg) в этой функции.
• @Gleamball выражает благодарность за выступление и обмен информацией.

Репозиторий показывает, как в Racket писать анонимные рекурсивные функции без letrec и имен.
Ключевая идея — Y-комбинатор: лямбда получает себя как аргумент и вызывает его для следующего шага.

(define Y
  (λ (f)
    ((λ (x) (x x))
     (λ (x) (f (λ (a) ((x x) a)))))))

((Y (λ (fact)
      (λ (n)
        (if (zero? n) 1 (* n (fact (sub1 n)))))))
 5) ; 120

Такой приём работает для любой рекурсии: факториал, fib, обход списков и т.д.

• Обсуждение началось с примера анонимной рекурсии на Racket; оказалось, что код совместим с любым R6RS-Scheme, включая проект scheme-rs.
• Участники сравнили подходы: в Clojure нужен явный recur, в Racket хвостовые вызовы оптимизируются автоматически.
• Кто-то спросил, стоит ли брать Racket для повторного изучения ФП; советуют почитать «zen of Racket» и быть готовым к узкой, но мощной экосистеме.
• Появились порты идеи на Python и Go (через 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) памяти.
• Участники сходятся во мнении: владеть обоими подходами полезно, выбор зависит от языка, задачи и привычек команды.