Пол Грэм описывает LISP как точку схождения всех языков программирования. По его наблюдению, по мере взросления языков средний язык продолжает сползать в сторону LISP. Поэтому понимание LISP означает понимание фундаментальной модели современного программирования.

Другие рекламируют LISP как необходимый инструмент для того, чтобы стать лучшим программистом. Эрик Рэймонд зашел так далеко, что сказал, что понимание LISP — это «глубокий опыт просветления».

В поисках этого понимания я обратился к источнику. Оригинальная статья Джона Маккарти Рекурсивные функции символьных выражений и их машинное вычисление, положившая начало LISP.

Это плотная исследовательская статья, написанная гением для первых ученых-компьютерщиков. Неудобоваримая часть документации, предназначенная для того, чтобы помочь другим понять LISP. Я мучился с каждым предложением, прежде чем наткнулся на статью Пола Грэма Корни LISP. Его ясность помогла мне прийти к неуловимому чувству понимания.

Но только когда я написал эту статью, я полностью понял язык и его возможности. Я оставляю свои шаги здесь для тех, кто прошел по тому же пути и все еще пытается понять.

Верный Полу Грэму, я реализовал эту версию LISP в Arc. Полный код вы можете найти здесь.

Список выражений

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

; S-expression
((ab . c) . d . nil)
; M-expression
eq[x; x]
; returns t

Однако на компьютере, на котором они впервые реализовали LISP, отсутствовали квадратные скобки, поэтому все было записано в нотации S-выражения. Точки были опущены, и предполагается, что nil завершает списки.

Таким образом, приведенное выше M-выражение становится

(eq x x)
; returns t

который стал стандартным синтаксисом для LISP, сделав язык синтаксически унифицированным.

Элементарные функции

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

Краткое введение в синтаксис LISP полезно, потому что некоторые аспекты не интуитивно понятны. В частности, котировки и оценка наизнанку.

Кавычки необходимы для LISP, потому что нет разделения данных и кода. Последовательности символов могут интерпретироваться как переменные или значения в зависимости от их контекста. Цитирование символов решает эту проблему, заставляя буквальную интерпретацию значений.

Вооружившись этим базовым пониманием, вы готовы к 5 элементарным функциям, необходимым для LISP.

атом

Проверяет, является ли элемент одним символом.

(atom 'x)
; returns t
(atom '(a b))
; returns nil

eq

Проверяет, совпадают ли два атомарных символа. В Arc это записывается как is.

(eq 'x 'x)
; returns t
(eq 'x 'y)
; returns nil
(eq '(a b) '(a b))
; (a b) is a list and cannot be evaluated by eq
; returns nil

машина

Обозначает содержимое адресного регистра. Он возвращает первый элемент в списке, если он не является атомарным.

(car '(x a))
; returns x
(car '((x a) y))
; returns (x a)

cdr

Обозначает содержимое регистра декремента. Он возвращает все после первого элемента в списке.

(cdr '(x a))
; returns a
(cdr '((x a) y))
; returns y
(cdr '((x a) (y b)))
; returns (y b)

минусы

Используется для создания списка из атомов или других списков.

(cons 'x 'a)
; returns (x . a)
; lists should typically end in nil
; so it is better to write (cons x (cons a nil))
; which returns (x . a . nil)
; and can be written as (x a)
(cons '(x a) 'y)
; returns ((x a) . y)
(cons '(x a) '(y b))
; returns ((x a) y b)

Основные функции

Эти функции образуют ядро ​​«универсальной функции», которая является конечной целью этой реализации.

Если у вас есть проблемы с синтаксисом, я предлагаю сначала прочитать Arc tutorial Пола Грэма.

_нулевой

Проверяет, является ли выражение пустым.

(def _null (x)
  (is x nil))
(_null nil)
; returns t
(_null '(x a))
; returns nil

_и

Оценивает, верны ли оба условия. В Arc t означает истину, а nil — ложь.

(def _and (x y)
  (if (is x t) (is y t) t nil))
(_and 'x 'y)
; returns t
(_and 'x nil)
; returns nil

_нет

Оценивает, является ли условие nil.

(def _not (x)
  (if (is x nil) t))
(_not nil)
; returns t
(_not 'x)
; returns nil

_caar, _cadr, _caddr, _cadar и _caddar

Это сокращение для комбинаций car и cdr. Они встречаются часто, поэтому сокращение сохраняет ваш код СУХИМ.

(def _caar (x)
  (car (car x)))
(def _cadr (x)
  (car (cdr x)))
(def _cadar (x)
  (car (cdr (car x))))
(def _caddr (x)
  (car (cdr (cdr x))))
(def _caddar (x)
  (car (cdr (cdr (car x)))))
(_cadr '(a b c d))
; returns b
(_caddr '(a b c d))
; returns c
(_cadar '((a b c d) (e f g)))
; returns b
(_caddar '((a b c d) (e f g)))
; returns c

_append

Позволяет присоединиться к спискам.

(def _append (x y)
  (if (_null x) y (cons (car x) (_append (cdr x) y))))
(_append '(a b) '(c d))
; returns (a b c d)

_список

Это поддерживает целостность списков, которые вы передаете в качестве аргументов, и устраняет необходимость в дополнительных cons при соединении двух атомов.

(def _list (x y)
  (cons x (cons y nil)))
(_list 'a 'b)
; returns (a b)
(_list '(a b) '(c d))
; returns ((a b) (c d))

_пара

Объединяет два списка, создавая пары на основе положения каждого элемента.

(def _pair (x y)
  (if (_and (_null x) (_null y)) nil
      (_and (_not (atom x)) (_not (atom y)))
      (cons (_list (car x) (car y))
            (_pair (cdr x) (cdr y)))))
(_pair '(x y z) '(a b c))
; returns ((x a) (y b) (z c))

_assoc

Получает значения из пар ключ-значение, где первый аргумент — это ключ, а второй аргумент — это список пар.

(def _assoc (x y)
  (if (is (caar y) x) (_cadar y)
    (_assoc x (cdr y))))
(_assoc 'y '((x a) (y b)))
; returns b
(_assoc 'x '((w (a b)) (x (c d)) (y (e f))))
; returns (c d)

Универсальная функция

Истинная сила LISP заключается в его способности оценивать себя по нескольким строительным блокам. Как и Джон Маккарти, мы будем определять _eval, который может оценивать LISP в LISP.

Это самый удивительный и мощный аспект языка. С 5 примитивами и 12 функциями у вас есть строительные блоки для создания интерпретатора.

(def _eval (e a)
  (if
    (atom e) (_assoc e a)
    (atom (car e)) (if
      (is (car e) 'quote) (_cadr e)
      (is (car e) 'atom)  (atom (_eval (_cadr  e) a))
      (is (car e) 'eq)    (is   (_eval (_cadr  e) a)
                                (_eval (_caddr e) a))
      (is (car e) 'car)   (car  (_eval (_cadr  e) a))
      (is (car e) 'cdr)   (cdr  (_eval (_cadr  e) a))
      (is (car e) 'cons)  (cons (_eval (_cadr  e) a)
                                (_eval (_caddr e) a))
      (is (car e) 'cond)  (_evcon (cdr e) a)
      (_eval (cons (_assoc (car e) a)
                   (cdr e))
             a))
    (is (caar e) 'label)
      (_eval (cons (_caddar e) (cdr e))
             (cons (_list (_cadar e) (car e)) a))
    (is (caar e) 'lambda)
      (_eval (_caddar e)
             (_append (_pair (_cadar e) (_evlis (cdr e) a))
                      a))))
(def _evcon (c a)
  (if (_eval (_caar c) a)
      (_eval (_cadar c) a)
      (_evcon (cdr c) a)))
(def _evlis (m a)
  (if (_null m) nil
      (cons (_eval  (car m) a)
            (_evlis (cdr m) a))))

При использовании _eval синтаксис содержащихся выражений будет зависеть от интерпретатора. Мы больше не пишем на Arc, а на совершенно новом языке. Примитивная форма LISP.

Даже если вы следили за этим, здесь есть что ломать, поэтому давайте пройдемся по нему.

Интерпретация элементарных функций

_eval принимает e как вычисляемое выражение и a как список пар, на которые будет ссылаться e.

Если e является атомарным, _assoc вызывается для возврата значения, которое соответствует ключу e в a.

(_eval 'x '((x a) (y b)))
; returns a
(_eval 'y '((x a) (y b)))
; returns b

В случае quote символ, следующий за quote, возвращается буквально.

(_eval '(quote x) nil)
; nil is needed because _eval requires two arguments
; returns x
(_eval '(quote (x a)) nil)
; returns (x a)

С другими элементарными функциями e принимает форму (function key), где key используется для получения значения из a, которое будет оцениваться function.

Следующее использование _eval эквивалентно гораздо более простому (atom 'y), но оно является ключевым для понимания функции _eval. Обратите внимание, как x используется для ссылки на значение второго параметра, a.

(_eval '(atom x) '((x y)))
; returns t
(_eval '(atom x) '((x (a b))))
; returns nil

Для каждой элементарной функции, кроме quote, выполняются рекурсивные _eval вызовы, пока не будет достигнуто _assoc или quote.

Это шаги, которые _eval предпринимает для оценки atom.

(_eval '(atom x) '((x y)))
; (atom (_eval (_cadr e) a))
; (atom (_eval  x ((x y))))
; (atom (_assoc x ((x y))))
; (atom y)
; returns t

car и cdr имеют структуру, очень похожую на atom, потому что нужно вычислить только одно выражение.

(_eval '(car x) '((x (a b c))))
; returns a
(_eval '(cdr x) '((x (a b c))))
; returns (b c)

cons и eq имеют два выражения, которые необходимо вычислить. Таким образом, a должно содержать две пары.

(_eval '(eq x y) '((x a) (y a)))
; returns t
(_eval '(cons x y) '((x a) (y b)))
; returns (a . b)

cond использует новую функцию _evcon, которая принимает список пар в формате (condition expression). Когда истинное условие найдено, это выражение оценивается.

(def _evcon (c a)
  (if (_eval (_caar c) a)
      (_eval (_cadar c) a)
      (_evcon (cdr c) a)))
(_evcon '(((atom c1) a1) ((atom c2) a2) ((atom c3) a3))
        '((c1 (a b)) (a1 not_atom)
          (c2 (c d)) (a2 still_not_atom)
          (c3 e)     (a3 is_atom)))
; returns is_atom

Вот то же выражение с использованием _eval.

(_eval '(cond ((atom c1) a1) ((atom c2) a2) ((atom c3) a3)) '((c1 (a b)) (a1 not_atom) (c2 (c d)) (a2 still_not_atom) (c3 e) (a3 is_atom))) ; returns is_atom

Интерпретация функций label и lambda

Если e является атомарной, но не элементарной функцией, это должна быть функция label или lambda, определенная пользователем.

lambda выражения принимают формат (lambda (param) (expression) arg), где arg будет передано от expression до param.

(_eval '((lambda (param)
           (cond ((atom param) (quote is_atom))
                 ((quote t)    (quote not_atom))))
          arg)
       '((arg (a b))))
; returns not_atom

Обратите внимание, что (quote t) используется здесь как явное условие else. Arc изящно обрабатывает эти случаи, но, поскольку мы связаны правилами интерпретатора, мы должны использовать этот синтаксис.

Во время оценки приведенное выше выражение lambda становится

(_eval '(cond ((atom param) (quote is_atom))
              ((quote t)    (quote not_atom)))
       '((param (a b)) (arg (a b))))

Обратите внимание, как аргументы расширены, чтобы содержать пару для param. Это использует дополнительную функцию _evlis, которая рекурсивно создает список пар из arg для каждого param в lambda. Это позволяет lambda обрабатывать любой список параметров.

((lambda (p1...pn) e) a1...an) — это формальное определение .

label позволяет вызывать функции по имени, что, возможно, является самой важной особенностью любого языка программирования.

Здесь Маккарти определяет ff как функцию, возвращающую первый атом в списке. Он использует помеченную рекурсию.

(_eval '((label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
         y)
       '((y ((a b) c))))
; returns a

Когда _eval находит label, он сохраняет эту функцию в a для последующего использования. Он также начнет оценку функции lambda, определенной параметром label. Во время оценки приведенное выше выражение становится

(_eval '((lambda (x)
           (cond ((atom x) x)
                 ((quote t) (ff (car x)))))
         y)
       '((ff (label ff (lambda (x)
               (cond ((atom x) x)
                     ((quote t) (ff (car x)))))))
         (y ((a b) c))))

Полная оценка — это, по словам Маккарти, «деятельность, которая больше подходит для электронных компьютеров, чем для людей». Я согласен и не буду перечислять каждый шаг оценки.

Упрощение _eval

Использование _eval в необработанном виде довольно многословно, поэтому Маккарти определил _apply как оболочку для _eval, которая помогает делать выражения короче и легче для понимания.

Это возьмет параметры для _eval и обернет их как (quote (param)). Он также применяет аргументы непосредственно к функции.

(def _appq (m)
  (if (_null m) nil (cons (_list 'quote (car m))
                          (_appq (cdr m)))))
(def _apply (f args)
  (_eval (cons f (_appq args)) nil))

Используя эту функцию, функция ff может быть записана как

(_apply '(label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
        '(a b))

который вызывает _eval как

(_eval '((label ff (lambda (x)
                     (cond ((atom x) x)
                           ((quote t) (ff (car x))))))
          (quote a) (quote b))
       'nil)

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

Выводы

Возможность определять новые языки и контролировать их внутреннее состояние делает LISP превосходным языком для исследований и экспериментов.

Исчезло волшебство компиляции и исполняемых файлов. Вы сами видите каждый шаг оценки. Это делает упражнение по спотыканию в архаичном синтаксисе выполненным.

Я не вижу себя использующим LISP в продакшене. Тем не менее, я буду продолжать использовать его как инструмент для расширения своего понимания низкоуровневого программирования.

Следующий шаг для меня — понять, как реализовать компилятор, который преобразует это в машинный код. Для этого я планирую прочитать Структура и интерпретация компьютерных программ.

Кроме того, я хотел бы модернизировать этот интерпретатор. Как писал Пол Грэм: «В языке, который он [Джон Маккарти] написал в 1960 году, многого не хватало. У него нет побочных эффектов, последовательного выполнения, практических чисел и динамической области действия». Но это можно решить.

Пол Грэм намекает на статью Стила и Сассмана Искусство переводчика, не вдаваясь в подробности. Возможно, я рассмотрю их в другой статье.

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

Первоначально опубликовано на https://joshbradley.me 4 апреля 2020 г.