Implémentation LISP arithmétique

Question

Je fais un interpréteur Lisp jouet avec D et je ne connais pas très bien la théorie de Lisp. Je me demandais si Lisp pouvait implémenter des fonctions arithmétiques basiques (+, -, ×, ÷) par lui-même. La plupart des dialectes Lisp/Scheme l'ont implémenté avec les builtins de langage C, Java et le surchargent en code Lisp (impléments dupliqués?).

Je veux écrire des fonctions arithmétiques au code Lisp purement. Est-ce possible?

Answer 1

À moins que vous souhaitez utiliser Church numerals ou similaire, à un moment donné, vous allez devoir entrer dans les instructions matérielles de l'arithmétique (add, sub, mul, div) d'une façon ou d'une autre. En descendant la route des instructions matérielles, en fonction de votre implémentation Lisp, il peut être implémenté en utilisant le code C (en particulier pour une implémentation basée sur un interpréteur), ou ces instructions peuvent être émises directement (pour un compilateur JIT). la mise en oeuvre). Si vous essayez d'être en tant que premiers principes, vous pouvez implémenter la multiplication et la division en utilisant des instructions d'addition et de soustraction (à la rigueur, vous pouvez les appliquer de la même manière qu'on vous l'a appris à l'école, utilisez des chiffres de la taille d'un mot, c'est-à-dire, pour une machine 32 bits, chaque chiffre est base-4294967296 au lieu de base-10).

Answer 2

La solution très simple serait toujours d'utiliser votre tour numérique hôte, mais je comprends votre désir de garder les primitives faibles. Le résultat est cependant une langue comme les premiers LISPs qui ont eu une mauvaise réputation sur la performance.

Comme alternative aux chiffres Chris's Church, vous pouvez modéliser des nombres en utilisant des listes. Par exemple. 1234 peut être (+ 4 3 2 1). Vous avez maintenant un type numérique bas comme primitif ou les chiffres que vous voyez sont simplement des symboles d'auto-évaluation que vos fonctions mathématiques connaissent. Si vous avez un type numérique bas, vous pouvez ajouter un exposant pour qu'il devienne (+ 0 4 3 2 1) pour 1234 et (+ 1 4 3 2 1) pour 12340 et (+ -11 4 3 2 1) pour 0.000000. Tout l'arithmétique serait des itérations de liste en utilisant exactement les maths que vous connaissez de l'école. C'est plus efficace que les chiffres d'église et légèrement plus efficace et il est plus facile de l'imprimer et de le lire.

J'ai utilisé ceci sur mon little lisp interpreter qui a seulement des listes et des symboles.

Answer 3

Si vous êtes intéressé par la mise en œuvre bignums à Lisp je peux recommander cette série par André van Meulebrouck:

https://web.archive.org/web/20101208222557/http://www.mactech.com/articles/mactech/Vol.08/08.03/BigNums/index.html

Le lien ci-dessus est le web.archive.org. Pour une raison quelconque, le lien d'origine alors qu'il est encore en ligne ne montre aucun contenu (http://www.mactech.com/articles/mactech/vol.08/08.03/bignums/index.html)