Пользовательская функция '+' (сумма) в lisp

Question

Я читал Roots of Lisp от Paul Graham, где он утверждает, что любая функциональность lisp может быть построена с использованием комбинации из 7 базовых функций: quote, atom, eq, cond, cons , автомобиль, cdr.

Вопрос: диалекты Лиспа действительно основаны исключительно на этих функциях? Как мы можем определить функцию «sum» или «plus», используя вышеупомянутые 7 примитивных функций? например Наша собственная функция (+ 1 2)

Примечание: Я полностью новичок в Lisp, но я также очень рад этому языку. Цель этого вопроса - исключительно неподдельный интерес

Answer 1

Автор относится к очень известной статье, написанной в 1960 году Премией Тьюринга и изобретателем Лиспа Джоном Маккарти “Recursive Functions of Symbolic Expressions and Their Computation by Machine”, в которой он определил семантику Лиспа как новый вычислительный формализм, эквивалентный у власти к машине Тьюринга.

В статье (и в Lisp 1.5 Manual) Маккарти описал интерпретатор языка, который может быть полностью написан с использованием только семи примитивных функций, упомянутых Грэмом.

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

Как говорит Грэм в заметке на стр. 11 «Корень Лиспа»: «Возможно, сделать арифметику в Лиссабоне Маккарти в 1960 году, используя, например, список n атомов для представления числа n ", поэтому выполнение суммы просто эквивалентно добавлению двух списков.

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

Answer 2

Насколько я помню, был также подход, чтобы сделать это, используя уровень вложенности списка (не помните, где). Начиная с () как ноль, (()) == 1 и так далее. Тогда вы можете просто определить, как inclist и dec в car:

CL-USER> (defun zero? (x) (eq() x)) 
ZERO? 

CL-USER> (zero? nil) 
T 

CL-USER> (zero? 1) 
NIL 

CL-USER> (defparameter *zero*()) 
*ZERO* 

CL-USER> (defun inc (x) (list x)) 
INC 

CL-USER> (defun dec (x) (car x)) 
DEC 

CL-USER> (defun plus (x y) 
      (if (zero? y) x (plus (inc x) (dec y)))) 
PLUS 

CL-USER> (plus *zero* (inc (inc *zero*))) 
((NIL)) 

CL-USER> (defparameter *one* (inc *zero*)) 
*ONE* 

CL-USER> (defparameter *two* (inc *one*)) 
*TWO* 

CL-USER> (defparameter *three* (inc *two*)) 
*THREE* 

CL-USER> (plus *two* *three*) 
(((((NIL))))) 

CL-USER> (equal *two* (dec (dec (dec (plus *two* *three*))))) 
T 

Answer 3

TL; DR: №. Современные системы lisp имеют намного больше примитивов, чем первый lisp, и новые примитивы необходимы для каждого нового примитивного типа данных.

У первого Лиспа не было номеров, но оно было полным. Это означает, что он может делать любые вычисления, которые возможны на любом другом языке, но это не значит, что это было бы практично. Число не было трудно подражать, но расчеты были медленными. Сегодня есть слухи о медленной арифметике, датируемой pre Lisp 1.5.

Когда я сделал свой первый интерпретатор lisp, мне не сильно понравились цифры. Это не очень интересный аспект переводчика. Я тем не менее реализовать fibonacci в качестве примера, и вот как это выглядит:

;; This is NOT Common Lisp code. It's Zozotez 
(setq + (lambda (x y) 
    (if x (cons (car x) 
       (+ (cdr x) y)) 
     y))) 

(setq - (lambda (z w) 
    (if w (- (cdr z) 
      (cdr w)) 
     z))) 

(setq fibonacci 
    (lambda (n a1 a2) 
    (if n 
     (fibonacci (- n '(1)) 
        a2 
        (+ a2 a1)) 
     a1))) 

(fibonacci '(1 1 1 1 1 1 1 1 1)() '(1)) 
; ==> (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) 

Нет номеров!(1 на моем языке является символом, поэтому его нужно котировать, иначе он будет оцениваться как переменная)

В качестве альтернативной системы чисел я применил систему позиционирования, в значительной степени похожую на то, как мы пишем числа с одинаковыми правилами для добавления/умножения и т. д. Возможно, чуть быстрее, чем lits длины n, но сложнее сделать.

Если у Lisp есть закругления, вы можете сделать церковные цифры. Используя то же самое, что и лямбда-исчисление, вы можете вычислить что угодно, просто закрыв. Вам нужен только один примитив, lambda. (Опять же, не самый простой для работы)