Я делаю игрушечный интерпретатор Лиспа с D, и я не очень хорошо знаю теорию Лиспа.
Мне было интересно, может ли Lisp реализовать основные арифметические функции (+, -, ×, ÷) сам по себе. Большинство диалектов Lisp/Scheme реализовали его с помощью встроенных функций C, Java-подобного языка и перегрузили его как код lisp (дублированные реализации?).
Я хочу писать арифметические функции исключительно в коде Лиспа. Является ли это возможным?
Если вы не хотите использовать церковные цифры и т.п., в какой-то момент вам придется аппаратные арифметические инструкции (add, sub, mul, div) так или иначе.
Если идти по маршруту аппаратных инструкций, то, в зависимости от вашей реализации Lisp, это может быть реализовано с использованием кода C (особенно для реализации на основе интерпретатора) или эти инструкции могут быть выданы напрямую (для реализации на основе компилятора JIT).
Если вы пытаетесь максимально придерживаться первых принципов, вы можете реализовать умножение и деление, используя инструкции сложения и вычитания (в крайнем случае, вы можете реализовать их так же, как вас учили в школе, хотя вы используете слова). -размерные цифры, т. е. для 32-разрядной машины каждая цифра имеет основание 4294967296 вместо основания 10).
Очень простым решением всегда было бы использовать числовую башню вашего хоста, но я понимаю ваше желание сохранить примитивы на низком уровне. Однако в результате появился язык, похожий на первые LISP, который имел плохую репутацию в отношении производительности.
В качестве альтернативы числам Криса Черча вы можете моделировать числа с помощью списков. Например. 1234 может быть (+ 4 3 2 1). Теперь у вас либо низкий числовой тип как примитивный, либо цифры, которые вы видите, являются просто самооценивающими символами, которые ваши математические функции знают, что такое. Если у вас низкий числовой тип, вы можете добавить показатель степени, чтобы он стал (+ 0 4 3 2 1) для 1234 и (+ 1 4 3 2 1) для 12340 и (+ -11 4 3 2 1) для 0.00000001234. Вся арифметика будет состоять из итераций списка с использованием именно той математики, которую вы знаете из школы. Это более эффективно, чем цифры Черча, и немного более эффективно, и его легче распечатать и прочитать.
Я использовал это в своем маленьком интерпретаторе lisp, в котором есть только списки и символы.
Если вы заинтересованы в реализации bignums в Lisp, я могу порекомендовать эту серию статей Андре ван Мелебрука:
Ссылка выше — это web.archive.org. По какой-то причине исходная ссылка, пока она еще активна, не показывает содержимого ( http://www.mactech.com/articles/mactech/vol.08/08.03/bignums/index.html )
Вся арифметика Пеано основана на трех функциях:
zerop или zero? в зависимости от диалекта;add1; если на вашем диалекте его нет, вам все равно придется реализовать + на вашем языке начальной загрузки;equal.С этими тремя функциями вы можете построить всю арифметику, но это будет непросто!
На мой взгляд, было бы разумно построить свои арифметические примитивы Лиспа (сложение, вычитание, умножение, деление) на языке реализации. Это особенно важно, если вы хотите иметь первоклассные коэффициенты и большие числа.
