Можете ли вы реализовать какую-либо чистую функцию LISP, используя десять примитивов? (т.е. без предикатов типа)

Некоторые числа могут быть представлены только этими примитивами, это довольно неудобно и сложно представить себе в первый раз, когда вы их видите.

Подобно тому, как натуральные числа представляются с увеличивающимися в размере наборами, они могут быть смоделированы в Лиспе как вложенные cons-ячейки.

Ноль будет пустым списком или () . Одной из них может быть одноэлементная cons-ячейка или ((). ()) . Два будет один плюс один или преемник одного, где мы определяем преемником x как (cons () x) , что, конечно же, (( ). ((). ())) . Если вы принимаете Аксиому Бесконечности (и некоторые другие, но пока что для наших целей в основном это Аксиома Бесконечности) и игнорируете ограничения памяти реальных компьютеров, это может точно представить все натуральные числа.

Достаточно легко расширить это, чтобы представить все целые числа, а затем рациональные числа [1], но представить действительные числа в этой нотации было бы (я думаю) невозможным. К счастью, это не мешает нам веселиться, поскольку мы все равно не можем представить все реальные значения на наших компьютерах; мы обходимся поплавками и двойниками. Так что наше представление столь же мощно.

В некотором смысле, 1 - это просто синтаксический сахар для ((). ()) .

Ура теории множеств! Ура Лиспу!

РЕДАКТИРОВАТЬ Ах, для дальнейшего пояснения позвольте мне ответить на ваш вопрос о предикатах типов, хотя на данном этапе это может быть ясно. Поскольку ваши числа имеют различную форму, вы можете протестировать эти связанные списки с помощью созданной вами функции, которая проверяет эту конкретную структуру. Моя схема уже недостаточно хороша, чтобы писать ее на Scheme, но я могу попытаться сделать это на Clojure.

Тем не менее, вы можете сказать, что это может дать вам ложные срабатывания: возможно, вы просто пытаетесь представить множества, и в итоге вы получаете ту же структуру, что и число в этой системе. На это я отвечаю: ну, в таком случае у вас действительно есть номер.

Как видите, у нас здесь довольно приличное представление чисел, не считая того, сколько памяти они занимают (не наша забота) и насколько некрасиво они выглядят при печати в REPL (также, не наша забота) и насколько неэффективно будет работать с ними (например, мы должны определить наше добавление и т. д. с точки зрения операций со списком: медленные и немного сложные). Но ни один из них не вызывает беспокойства: скорость действительно должна и может зависеть от детали реализации, а не то, что вы делаете на этом языке.

Итак, здесь, в Clojure (но используя только те вещи, к которым у нас в основном есть доступ в нашем простом Лиспе, это numberp . (Надеюсь, не стесняйтесь поправлять меня, я чертовски слаб и т. оправдания и т. д.)

(defn numberp 
    [x]
      (cond 
        (nil? x) true
        (and (coll? x) (nil? (first x))) (numberp (second x))
        :else false))

[1] Для целых чисел представьте их как cons-ячейки натуральных чисел. Пусть первый элемент в cons-ячейке будет «отрицательной» частью целого числа, а второй элемент - «положительной» частью целого числа. .Таким образом, -2 можно представить как (2, 0) или (4, 2) или (5, 3) и т. Д. Что касается рациональных чисел, пусть они будут представлены как cons-ячейки целых чисел: например, (-2, 3) и т. Д. Это дает нам возможность иметь одну и ту же структуру данных, представляющую одно и то же число: однако это можно исправить, написав функции, которые проверяют два числа, чтобы увидеть, эквивалентны ли они: мы бы определяли эти функции в терминах уже существующей теории множеств отношений эквивалентности предлагает нам. Интересные вещи :)