3.6. Интерпретаторы для языков с абстракцией

Вычислительные языки предоставляют средства для комбинирования вложенных вызовов выражений. Однако мы не можем определить новые операторы, присвоить значения именам или выразить общие вычислительные методы. В целом, вычислительный язык не поддерживает абстракции каким-либо образом. Поэтому он не является особенно мощным или универсальным языком программирования. Теперь мы переходим к определению универсального языка программирования, который поддерживает абстракцию путём связывания имён с значениями и определения новых операций.

Мы не расширяем простой вычислительный язык, а начинаем заново и разрабатываем интерпретатор для языка Logo. Logo — это не язык, разработанный специально для этого курса, а классический командный язык с множеством реализаций интерпретаторов и собственным сообществом разработчиков.

В предыдущей главе мы представили полный интерпретатор в виде исходного кода Python. В этой главе мы используем описательный подход. Для выполнения концепции, представленной здесь, вам потребуется построить полноценный функциональный интерпретатор Logo.

3.6.1. Язык Scheme

Scheme — это диалект Lisp, Lisp — это второй старейший (после Fortran) язык программирования, широко используемый сегодня. Scheme был впервые описан Джеральдом Суссманом и Гаем Стилом в 1975 году. В введении к Revised(4) Report on the Algorithmic Language Scheme говорится:

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

Мы рекомендуем этот отчёт в качестве подробного справочника по языку Scheme. Здесь мы затронем только основные моменты. В следующем описании мы будем использовать примеры из отчёта.

Хотя Scheme очень прост, это настоящий язык программирования, во многом похожий на Python, но с минимальным количеством «синтаксического сахара». По сути, все операторы являются формой вызова функции. Здесь мы опишем демонстрируемый подмножество полного языка Scheme, как описано в отчёте.

Scheme имеет множество доступных реализаций, которые добавляют дополнительные процедуры. В UCB мы используем модифицированную версию интерпретатора Stk, которая также доступна на нашем учебном сервере как stk. К сожалению, она не строго соответствует официальному стандарту, но подходит для наших целей.

Использование интерпретатора. Как и в случае с интерпретатором Python, выражения, вводимые в Stk, оцениваются и печатаются в цикле «чтение-оценка-печать»:

>>> 3
3
>>> (- (/ (* (+ 3 7 10) (- 1000 8)) 992) 17)
3
>>> (define (fib n) (if (< n 2) n (+ (fib (- n 2)) (fib (- n 1)))))
fib
>>> '(1 (7 19))
(1 (7 19))

Значения в Scheme обычно соответствуют значениям в Python.

Логические значения

Истинные и ложные значения представлены #t и #f. В Scheme единственное ложное значение (в смысле Python) — это #f.

Числовые значения

Это включает целые числа произвольной точности, рациональные числа, комплексные числа и «неточные» (обычно плавающие) числа. Целые числа могут быть представлены стандартными десятичными числами или другими основаниями, используя префиксы #o (восьмеричное), #x (шестнадцатеричное) или #b (двоичное).

Символы

Символ — это строка, не заключённая в кавычки. Допустимые символы включают буквы, цифры и:

!  $  %  &  *  /  :  <  = >  ?  ^  _  ~  +  -  .  @

При использовании функции read для ввода, она считывает выражение Scheme (то же самое, что и интерпретатор использует для ввода текста программы), не различая регистр символов в STk реализации (которая преобразует их в нижний регистр). Два символа с одинаковым представлением обозначают один и тот же объект (а не два объекта, случайно имеющих одинаковое содержимое).

Пары и списки

Пара — это объект, состоящий из двух членов (любого типа), называемых car и cdr. Пара с car, равным A, и cdr, равным B, может быть представлена как (A . B). Пары (подобно кортежам в Python) могут представлять списки, деревья и любые иерархические структуры.

Стандартный список Scheme содержит пустой список значений (()) или пару, car которой является первым элементом списка, а cdr — оставшейся частью списка. Таким образом, список, содержащий целые числа 1, 2, 3, можно представить следующим образом:

(1 . (2 . (3 . ())))

Списки встречаются повсюду, Scheme позволяет нам сокращать (a . ()) до (a) и (a . (b ...)) до (a b ...). Поэтому приведённый выше список обычно записывается так:

(1 2 3)

Процедуры (функции)

Как и в Python, процедуры (или функции) представляют собой вычисления, которые можно вызывать, предоставляя им параметры. Процедуры либо примитивны и предоставляются системой времени выполнения Scheme, либо конструируются из выражений Scheme и среды (как в Python). Нет прямого представления для значений функций, но есть несколько привязок к базовым функциям и предопределённым идентификаторам, а также некоторые выражения Scheme, которые создают новые значения функций при оценке.

Другие типы

Scheme также поддерживает символы и строки (аналогичные строкам Python, за исключением того, что Scheme различает символы и строки), а также векторы (похожие на списки Python).

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

(+ x (* 10 y))

Зависит от того, как оно используется, оно может представлять собой список из трёх элементов (его последний элемент также является списком из трёх элементов) или выражение для вычисления x + 10y. Чтобы оценить значение Scheme как программу, нам нужно рассмотреть тип значения и оценить его следующим образом:

• Целые числа, логические значения, символы, строки и векторы оцениваются сами по себе. Следовательно, выражение 5 оценивается как 5.
• Чистые символы рассматриваются как переменные. Их значения определяются текущей оцениваемой средой, аналогично Python.
• Непустые списки интерпретируются двумя способами в зависимости от их первого элемента:
  • Если первый элемент является специальной формой (описанной ниже), оценка выполняется в соответствии с правилами этой специальной формы.
  • Во всех остальных случаях (называемых комбинациями) члены списка оцениваются в неуказанном порядке (рекурсивно). Первый элемент должен быть значением функции. Это значение вызывается с оставшимися членами списка в качестве параметров.
• Другие значения Scheme (особенно не являющиеся списками пары) являются ошибкой в программе.

Например:

>>> 5              ; A literal.
5
>>> (define x 3)   ; A special form that creates a binding for symbol
x                   ; x.
>>> (+ 3 (* 10 x)) ; A combination.  Symbol + is bound to the primitive
33                  ; add function and * to primitive multiply.

Основные специальные формы. Специальные формы представляют вещи как управляющие структуры, вызовы функций или определения классов в Python: они не просто немедленно оцениваются при вызове.

Во-первых, некоторые общие структуры используются таким образом:

EXPR-SEQ

Просто последовательность выражений, например:

(+ 3 2) x (* y z)

Когда он появляется в определении ниже, он обозначает последовательность выражений слева направо, причём последнее выражение в последовательности является его значением.

BODY

Некоторые структуры имеют «тело», которое представляет собой EXPR-SEQ, как указано выше, возможно, обрабатываемое одним или несколькими определениями. Его значение — это значение EXPR-SEQ. Определения этих интерпретаций см. в разделе «Внутренние определения».

Вот репрезентативное подмножество этих специальных форм:

Определения

Определения могут появляться на верхнем уровне программы (то есть не содержаться в других структурах).

(define SYM EXPR)

Оценивает EXPR и связывает его значение с символом SYM в текущей среде.

(define (SYM ARGUMENTS) BODY)

Эквивалентно (define SYM (lambda (ARGUMENTS) BODY)).

(lambda (ARGUMENTS) BODY)

Оценено как функция. ARGUMENTS обычно представляет собой (возможно, пустой) список различных символов, предоставляющих имена параметров функции, и указывает их количество. ARGUMENTS также может иметь следующую форму: В запросе представлен текст на языке Scheme.

В Scheme:

(sym1 sym2 ... symn . symr) — это список, в котором последний элемент symr связан со значением последнего параметра (n+1-го параметра).

Когда создаётся функция, значения ARGUMENTS связываются с аргументами функции в новой среде, которая расширяется из среды выражения lambda (как в Python). Затем вычисляется BODY, и его значение возвращается как значение вызова функции.

(if COND-EXPR TRUE-EXPR OPTIONAL-FALSE-EXПР) — если значение COND-EXPR не равно #f, то вычисляется TRUE-EXPR, и результат становится значением if. Если значение COND-EXPR равно #f и OPTIONAL-FALSE-EXPR существует, оно вычисляется и становится значением if. В противном случае значение if не определено.

(set! SYMBOL EXPR) — значение EXPR заменяет привязку SYMBOL. SYMBOL должен быть уже привязан, иначе возникнет ошибка. В отличие от Python, замена происходит в первом фрейме определения, а не в самом глубоком фрейме.

quote EXPR или 'EXPR — данные структуры Scheme используются для представления программы в виде текста. quote возвращает EXPR как есть, без дальнейшего вычисления (альтернативная форма использует одинарные кавычки, которые преобразуются интерпретатором Scheme в форму quote). Например:

>>> (+ 1 2)
3
>>> '(+ 1 2)
(+ 1 2)
>>> (define x 3)
x
>>> x
3
>>> (quote x)
x
>>> '5
5
>>> (quote 'x)
(quote x)

Производные формы:

begin EXPR-SEQ — просто вычисляет и возвращает значение последовательности выражений EXPR-SEQ. Эта структура используется для выполнения последовательности или выражений в контексте, где требуется одно выражение.

and EXPR1 EXPR2... — каждый EXPR вычисляется слева направо до тех пор, пока не встретится значение #f или не будут исчерпаны все EXPRs. Значение является последним вычисленным EXPR, если список EXPRs пуст, значение равно #t. Например:

>>> (and (= 2 2) (> 2 1))
#t
>>> (and (< 2 2) (> 2 1))
#f
>>> (and (= 2 2) '(a b))
(a b)
>>> (and)
#t

or EXPR1 EXPR2... — каждый EXPR оценивается слева направо, пока не будет найдено значение, отличное от #f, или пока не будут исчерпаны все EXPRs. Значением является последний вычисленный EXPR, а если список EXPRs пуст, значением является #f. Например:

>>> (or (= 2 2) (> 2 3))
#t
>>> (or (= 2 2) '(a b))
#t
>>> (or (> 2 2) '(a b))
(a b)
>>> (or (> 2 2) (> 2 3))
#f
>>> (or)
#f

cond CLAUSE1 CLAUSE2... — каждая CLAUSEi обрабатывается последовательно, пока одна из них не завершится успешно, и её значение станет значением cond. Если ни один из пунктов не завершается успешно, значение не определено. Каждый пункт может иметь три формы:

• Если TEST-EXPR оценивается как не равное #f значение, форма (TEST-EXPR EXPR-SEQ) успешна. В этом случае вычисляется EXPR-SEQ, и его значение становится значением cond. EXPR-SEQ можно опустить, и тогда значением будет сам TEST-EXPR.
• Последний пункт может быть в форме (else EXPR-SEQ), что эквивалентно (#t EXPR-SEQ).
• Наконец, если форма (TEST_EXPR => EXPR) успешна при оценке TEST_EXPR как значения, отличного от #f (называемого V), то значение cond является результатом вызова (EXPR V). То есть EXPR должен оцениваться как функция с одним параметром, и значение TEST_EXPR используется в качестве аргумента. Например:

>>> (cond ((> 3 2) 'greater)
...        ((< 3 2) 'less)))
greater
>>> (cond ((> 3 3) 'greater)
...        ((< 3 3) 'less)
...        (else 'equal))
equal
>>> (cond ((if (< -2 -3) #f -3) => abs)
...        (else #f))
3

case KEY-EXPR CLAUSE1 CLAUSE2... — значение KEY-EXPR вычисляется, создавая значение K. Затем K сопоставляется с каждым CLAUSEi по очереди, пока один из них не будет успешным, и его значение будет возвращено. Если ни одно из предложений не было успешным, значение не определено. Каждое предложение имеет форму ((DATUM1 DATUM2 ...) EXPR-SEQ), где DATUMs являются значениями Scheme (они не оцениваются). Если K соответствует значению одного из DATUM (определяемому функцией eqv?), предложение считается успешным, и вычисляется его EXPR-SEQ, а его значение становится значением case. Последний пункт может быть (else EXPR-SEQ), который всегда успешен, например:

>>> (case (* 2 3)
...     ((2 3 5 7) 'prime)
...     ((1 4 6 8 9) 'composite))
composite
>>> (case (car '(a . b))
...    ((a c) 'd)
...    ((b 3) 'e))
d
>>> (case (car '(c d))
...    ((a e i o u) 'vowel)
...    ((w y) 'semivowel)
...    (else 'consonant))
consonant

let BINDINGS BODY — BINDINGS представляет собой список пар, где VARs — разные символы, а INITs — выражения. Сначала вычисляются выражения INIT, затем создаются новые привязки для этих значений к VARs, после чего в новой среде вычисляется BODY и возвращается его значение. Другими словами, это эквивалентно вызову

((lambda (VAR1 VAR2 ...) BODY)
INIT1 INIT2 ...)

Поэтому любые ссылки на VARs в выражениях INIT относятся к этим символам вне определения let (если они существуют), например:

>>> (let ((x 2) (y 3))
...       (* x y))
6
>>> (let ((x 2) (y 3))
...       (let ((x 7) (z (+ x y)))
...            (* z x)))
35

let* BINDINGS BODY — синтаксис такой же, как у let. Это эквивалентно

(let ((VAR1 INIT1))
...
(let ((VARn INITn))
BODY))

То есть он работает так же, как let, за исключением того, что новые привязки VAR1 видны в последовательности INITs и в BODY, аналогично VAR2 и т. д., например:

>>> (define x 3)
x
>>> (define y 4)
y
>>> (let ((x 5) (y (+ x 1))) y)
4
>>> (let* ((x 5) (y (+ x 1))) y)
6

letrec BINDINGS BODY — синтаксически похож на let. Здесь сначала создаются новые привязки (с неопределёнными значениями), затем INITs вычисляются и присваиваются им. Если какой-либо INIT использует значение VAR, которое не было инициализировано, результат не определён. Эта форма в основном используется для определения взаимно рекурсивных функций (lambda сама по себе не использует значения, на которые она ссылается; это происходит только при их вызове). Например:

(letrec ((even?
      (lambda (n)
             (if (zero? n)
                  #t
                  (odd? (- n 1)))))
     (odd?
      (lambda (n)
              (if (zero? n)
                  #f
                  (even? (- n 1))))))
(even? 88))

Внутренние определения: когда BODY начинается с последовательности определений define, они рассматриваются как «внутренние определения» и обрабатываются несколько иначе, чем определения верхнего уровня. В частности, они похожи на letrec. Сначала создаются привязки для всех имён, определённых с помощью define, с неопределёнными значениями. Затем значения заполняются определениями. Таким образом, внутренние определения функций являются взаимно рекурсивными, подобно тому, как вложенные определения def в Python:

>>> (define
``` **Предопределённые функции**

Предопределённых функций существует много, все они связаны с именами в глобальной среде, мы покажем лишь некоторые из них. Остальные перечислены в [Revised(4) Scheme](http://people.csail.mit.edu/jaffer/r4rs_toc.html). Вызов функции не является «особенным», поскольку все они используют одно и то же полностью унифицированное правило вычисления: рекурсивно вычисляются все элементы (включая операторы), а затем оператор применяется к значению своих операндов (которое должно быть функцией).

* **Арифметика:** Scheme предоставляет стандартные арифметические операторы, многие из которых имеют знакомые обозначения, хотя все они появляются перед своими операндами:

```scheme
>>> ; Semicolons introduce one-line comments.
>>> ; Compute (3+7+10)*(1000-8) // 992 - 17
>>> (- (quotient (* (+ 3 7 10) (- 1000 8))) 17)
3
>>> (remainder 27 4)
3
>>> (- 17)
-17

Аналогично существуют общие математические операторы сравнения, которые расширяются для принятия более двух аргументов:

>>> (< 0 5)
#t
>>> (>= 100 10 10 0)
#t
>>> (= 21 (* 7 3) (+ 19 2))
#t
>>> (not (= 15 14))
#t
>>> (zero? (- 7 7))
#t

Кстати, not — это функция, а не особая форма and или or, потому что её оператор должен быть оценён, поэтому нет необходимости рассматривать его особым образом.

• Списки и пары. Многие операции используются для обработки пар и списков (которые также строятся из пар и пустого списка).

>>> (cons 'a 'b)
(a . b)
>>> (list 'a 'b)
(a b)
>>> (cons 'a (cons 'b '()))
(a b)
>>> (car (cons 'a 'b))
a
>>> (cdr (cons 'a 'b))
b
>>> (cdr (list a b))
(b)
>>> (cadr '(a b))   ; An abbreviation for (car (cdr '(a b)))
b
>>> (cddr '(a b))   ; Similarly, an abbreviation for (cdr (cdr '(a b)))
()
>>> (list-tail '(a b c) 0)
(a b c)
>>> (list-tail '(a b c) 1)
(b c)
>>> (list-ref '(a b c) 0)
a
>>> (list-ref '(a b c) 2)
c
>>> (append '(a b) '(c d) '() '(e))
(a b c d e)
>>> ; All but the last list is copied.  The last is shared, so:
>>> (define L1 (list 'a 'b 'c))
>>> (define L2 (list 'd))
>>> (define L3 (append L1 L2))
>>> (set-car! L1 1)
>>> (set-car! L2 2)
>>> L3
(a b c 2)
>>> (null? '())
#t
>>> (list? '())
#t
>>> (list? '(a b))
#t
>>> (list? '(a . b))
#f

• Равенство: оператор = используется для числовых значений. Обычно для проверки равенства значений в Scheme различают eq? (аналогично Python is), eqv? (похоже на него, но аналогично числовому =) и equal? (сравнивает содержимое списков или строк). Как правило, за исключением случаев сравнения символов, логических значений или пустых списков, мы используем eqv? и equal?.

>>> (eqv? 'a 'a)
#t
>>> (eqv? 'a 'b)
#f
>>> (eqv? 100 (+ 50 50))
#t
>>> (eqv? (list 'a 'b) (list 'a 'b))
#f
>>> (equal? (list 'a 'b) (list 'a 'b))
#t

• Типы. Каждое значение имеет только один базовый тип утверждения.

>>> (boolean? #f)
#t
>>> (integer? 3)
#t
>>> (pair? '(a b))
#t
>>> (null? '())
#t
>>> (symbol? 'a)
#t
>>> (procedure? +)
#t

• Ввод и вывод: интерпретатор Scheme обычно выполняет цикл «чтение-вычисление-печать», но мы можем явно выводить данные под программным управлением, используя те же функции, что и внутри интерпретатора:

>>> (begin (display 'a) (display 'b) (newline))
ab

Таким образом, (display x) похож на Python print(str(x), end=""), и (newline) аналогичен print().

Для ввода данных (read) считывает выражение Scheme из текущего «порта». Оно не интерпретирует выражение, а считывает его как данные:

>>> (read)
>>> (a b c)
(a b c)

• Вычисление. Функция apply обеспечивает прямой доступ к операциям вызова функций:

>>> (apply cons '(1 2))
(1 . 2)
>>> ;; Apply the function f to the arguments in L after g is
>>> ;; applied to each of them
>>> (define (compose-list f g L)
...     (apply f (map g L)))
>>> (compose-list + (lambda (x) (* x x)) '(1 2 3))
14

Этот расширитель позволяет начальным параметрам появляться:

>>> (apply + 1 2 '(3 4 5))
15

Следующая функция не входит в [Revised(4) Scheme], но присутствует в нашей версии интерпретатора (предупреждение: нестандартные процедуры в последующих версиях Scheme не определяются таким образом):

>>> (eval '(+ 1 2))
3

То есть eval оценивает кусок выражения Scheme, которое представляет собой правильное выражение Scheme. В нашей версии оно оценивается в глобальной среде. Наш интерпретатор также предоставляет способ указать конкретную среду оценки:

>>> (define (incr n) (lambda (x) (+ n x)))
>>> (define add5 (incr 5))
>>> (add5 13)
18
>>> (eval 'n (procedure-environment add5))
5 ### 3.6.2 Язык Logo  

Logo — это ещё один диалект Lisp. Он был разработан для образовательных целей, поэтому многие дизайнерские решения в Logo направлены на то, чтобы сделать язык более дружелюбным для новичков. Например, большинство процедур в Logo вызываются с использованием префиксной формы (сначала идёт имя процедуры, затем параметры), но арифметические операторы предоставляются в общепринятой инфиксной форме. Преимущество Logo заключается в том, что его простой и понятный синтаксис всё ещё предоставляет впечатляющие возможности для опытных программистов.  

Основная концепция Logo — встроенные типы контейнеров, также известные как списки Logo (или просто списки), которые могут легко хранить исходный код Logo. Программы Logo могут писать и выполнять выражения Logo как часть процесса оценки. Многие динамические языки поддерживают генерацию кода, включая Python, но ни один из них не делает процесс генерации кода таким интересным и простым в использовании, как Logo.  

Возможно, вы захотите загрузить полную версию интерпретатора Logo, чтобы попробовать этот язык. Стандартная реализация — Berkeley Logo (также известный как UCBLogo), разработанный Брайаном Харви и его студентами из Беркли. Для пользователей Apple ACSLogo совместим с последней версией Mac OSX и включает руководство пользователя Logo, которое знакомит с множеством функций языка.  

**Основы.** Logo предназначен для работы в интерактивном режиме. Подсказка для цикла чтения-оценки — вопросительный знак (`?`), который создаёт вопрос «Что мне делать дальше?». Мы естественным образом хотим, чтобы он печатал число:  
```logo
? print 5
5

В Logo используется нестандартный синтаксис вызова выражений, который не использует скобки для разделения аргументов. В этом примере параметр 5 передаётся процедуре print, которая выводит его значение. Термины, используемые для описания структуры программы в Logo, несколько отличаются от терминов, используемых в Python. В Logo есть процедуры, а не функции, эквивалентные Python, и процедуры возвращают значения, а не возвращают их. Как и в Python, print всегда возвращает None, но также выводит строку представления аргумента в качестве побочного эффекта. (В Logo аргументы процедур обычно называются входами, но для ясности в этой статье мы будем называть их параметрами.)

Наиболее распространённым типом данных в Logo является слово, представляющее собой строку без пробелов. Слова используются для представления чисел, имён и логических значений. Знаки, которые можно интерпретировать как числа или логические значения, такие как 5, непосредственно оцениваются как слова. С другой стороны, имена, подобные five, интерпретируются как вызовы процедур:

? 5
Вы не говорите, что делать с 5.
? five
Я не знаю, как пять.

5 и five интерпретируются по-разному, и цикл чтения-оценки в Logo также выдаёт разные сообщения об ошибках. Первая проблема заключается в том, что интерфейс верхнего уровня в Logo не оценивает выражение и выдаёт ошибку. Здесь мы видим первое отличие Logo от калькулятора; первый имеет интерфейс чтения-интерпретации-цикла, ожидающий, что пользователь напечатает результат. Второй использует более общий интерфейс чтения-вычисления-печати, автоматически печатающий возвращаемое значение. Python использует смешанный подход, используя repr для принудительного преобразования не-None значений в строки и автоматической печати.

Строка в Logo может содержать несколько выражений подряд. Интерпретатор оценивает каждое выражение по очереди. Если любое выражение верхнего уровня в строке не оценивается как None, интерпретатор выдаст ошибку. После возникновения ошибки остальные выражения в строке игнорируются.

? print 1 print 2
1
2
? 3 print 4
Вы не говорите, что делать с 3.

Вызов процедур в Logo может быть вложенным. В реализации Logo каждая процедура принимает фиксированное количество параметров. Поэтому, когда количество операндов во вложенных вызовах процедур становится полным, интерпретатор может однозначно определить операцию. Рассмотрим две процедуры sum и difference, которые соответственно выводят сумму или разность двух параметров:

? print sum 10 difference 7 3
14

Из этого примера мы можем видеть, что разделительные скобки и запятые для вызовов процедур не являются обязательными. В интерпретаторе калькулятора пунктуация позволяет нам построить дерево выражений без каких-либо суждений об операторах. В Logo мы должны использовать свои знания о количестве параметров, принимаемых каждой процедурой, чтобы получить правильную структуру вложенных выражений. Более подробно эта проблема рассматривается в следующем разделе.

Логотип также поддерживает инфиксные операторы, такие как + и *. Приоритет операторов определяется стандартными правилами алгебры. Умножение и деление имеют более высокий приоритет, чем сложение и вычитание:

? 2 + 3 * 4
14

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

Ссылки. Имя интерпретируется как начало выражения вызова, но мы также хотим использовать слова в качестве ссылок на данные. Выражения, начинающиеся с двойных кавычек, интерпретируются буквально. Обратите внимание, что буквальные значения слов в Logo не имеют двойных кавычек в конце.

? print "hello
hello

В диалектах Lisp (а Logo — один из них) любое неоценённое выражение называется ссылкой. Эта концепция ссылок происходит из классической философии вещей. Например, собака может свободно бегать и лаять, а слово «собака» — это просто языковая конструкция, обозначающая эту вещь. Когда мы используем «собаку» в кавычках, мы не имеем в виду конкретную собаку, а скорее само слово. В языке кавычки позволяют нам говорить о самом языке, и то же самое верно и для Logo. Мы можем ссылаться на процедуру sum, не вызывая её, используя её имя следующим образом:

? print "sum
sum

Помимо слов, Logo содержит списки, которые представляют собой последовательности, заключённые в квадратные скобки. Процедура print не будет печатать скобки, чтобы сохранить стиль Logo, но скобки можно распечатать с помощью процедуры show:

? print [hello world]
hello world
? show [hello world]
[hello world]

Списки также можно создавать с помощью трёх различных бинарных процедур. Процедура sentence объединяет параметры в список. Это полиморфная процедура: если параметр является словом, она помещает его в новый список; если параметр уже является списком, она объединяет его. Результатом обычно является список:

? show sentence 1 2
[1 2]
? show sentence 1 [2 3]
[1 2 3]
? show sentence [1 2] 3
[1 2 3]
? show sentence [1 2] [3 4]
[1 2 3 4]

Процедура list создаёт список из двух элементов, позволяя пользователям создавать иерархические структуры данных:

? show list 1 2
[1 2]
? show list 1 [2 3]
[1 [2 3]]
? show list [1 2] 3
[[1 2] 3]
? show list [1 2] [3 4]
[[1 2] [3 4]]

Наконец, процедура fput создаёт список, добавляя первый элемент к остатку списка, подобно конструктору RList из предыдущей главы Python:

? show fput 1 [2 3]
[1 2 3]
? show fput [1 2] [3 4]
[[1 2] 3 4]

Мы можем вызывать процедуры sentence, list и fput в Logo для создания списков. Разбиение списков на первый элемент и оставшуюся часть (называемую butfirst) в Logo очень прямолинейно, поэтому у нас также есть набор процедур выбора для списков.

? print first [1 2 3]
1
? print last [1 2 3]
3
? print butfirst [1 2 3]
[2 3]

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

? show [print sum 1 2]
[print sum 1 2]

Цель использования выражений Logo в виде списков обычно состоит не в их печати, а в оценке с помощью процедуры run.

? run [print sum 1 2]
3

Комбинируя ссылки и процедуры построения списков, а также процедуру run, мы получаем мощный инструмент, который может создавать выражения Logo на лету и оценивать их:

? run sentence "print [sum 1 2]
3
? print run sentence "sum sentence 10 run [difference 7 3]
14

Последний пример подчёркивает, что хотя процедуры sum и difference не являются первоклассными конструкторами в Logo (их нельзя поместить непосредственно в список), их имена являются первоклассными, и процедура run может интерпретировать их как вызываемые процедуры.

Представление кода в виде данных и последующее его интерпретирование как части программы является особенностью языков стиля Lisp. Программы могут переписывать себя для выполнения, что является мощной концепцией и основой ранних исследований искусственного интеллекта (ИИ). Lisp был предпочтительным языком для исследователей ИИ на протяжении десятилетий. Язык Lisp был изобретён Джоном Маккарти, который также придумал термин «искусственный интеллект», и сыграл ключевую роль в определении этой области. Характеристики «кода как данных» языков Lisp, их лаконичность и элегантность продолжают привлекать программистов Lisp сегодня.

Turtle graphics. Все реализации Logo основаны на... Logo: язык программирования для практики и графики

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

В процессе выполнения программы Logo черепашка (или «черепаха», англ. turtle) на экране всегда имеет координаты и направление движения. Она перемещается по экрану, оставляя за собой след. Команды, которые управляют движением черепашки, называются командами черепахи. Они похожи на команды forward и right в других языках программирования. В языке Logo есть сокращённые обозначения для этих команд: forward также можно записать как fd, а другие команды имеют аналогичные сокращения.

Все команды черепахи встроены в модуль Python turtle. Некоторые из них представлены в этом тексте.

Присвоение значений

Язык Logo поддерживает связывание имён с определёнными значениями. Подобно тому, как это происходит в Python, среда Logo состоит из последовательности кадров, и каждое имя может быть связано только с одним значением в каждом кадре. Для связывания имени с определённым значением используется команда make. Эта команда принимает имя и значение в качестве аргументов.

make "x 2

Любое слово, начинающееся с двоеточия, называется переменной. Значение переменной — это значение, связанное с её именем в текущем окружении.

Команда make и оператор присваивания в Python выполняют разные функции. Если имя уже связано со значением, make повторно связывает его с новым значением в первом кадре, где оно было найдено. Если же имя не связано ни с каким значением, то make связывает его со значением во всём глобальном окружении. Это поведение отличается от семантики оператора присваивания в Python. Оператор присваивания всегда связывает имя с первым кадром текущего окружения.

Процедуры

В языке Logo пользователь может определять процедуры, используя ключевое слово to. Определение процедуры — это последний тип выражения в Logo. После определения процедуры следует вызов этой процедуры.

Определение процедуры начинается с указания её имени, за которым следуют аргументы в скобках. Затем идёт тело процедуры, которое может занимать несколько строк. Тело процедуры заканчивается строкой, содержащей только ключевое слово end. Команда > используется для ввода тела процедуры. Процедура output используется для вывода значения.

to double :x
output sum :x :x
end
print double 4

Вызов процедуры в языке Logo похож на вызов функции в Python. При вызове процедуры создаётся новый кадр, в котором аргументы процедуры связаны с переданными значениями, после чего выполняется тело процедуры.

Оператор output в языке Logo аналогичен оператору return в Python: он завершает выполнение тела процедуры и возвращает значение. Также существует процедура stop, которая не возвращает никакого значения.

to count
print 1
print 2
stop
print 3
end
count

Область видимости

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

Динамическая область видимости позволяет упростить реализацию языка. Каждый раз, когда вызывается функция, создаётся новый кадр, расширяющий текущий кадр. Например, при вызове функции print_x создаётся кадр, расширяющий кадр, в котором была вызвана функция print_x. Поэтому функция print_last_x может получить доступ к имени x, связанному с функцией print_x, хотя оно не было связано в глобальном кадре.

Динамическая область видимости имеет свои преимущества. Процессы в таком языке могут не требовать большого количества аргументов. Функция print_last_x не принимает никаких аргументов, но её поведение всё равно зависит от аргументов функции print_x.

Обычное программирование

На этом мы заканчиваем наше путешествие по языку Logo. Мы рассмотрели основные концепции, такие как движение черепашки и процедуры, но не затронули более сложные темы, такие как объекты, высокоуровневые процедуры или операторы. Эффективное программирование в Logo требует понимания основных принципов и их правильного применения.

В языке Logo нет условных выражений. Вместо этого используются процедуры if и ifelse. Процедура if принимает два аргумента: логическое выражение и действие, которое должно быть выполнено, если логическое выражение истинно. Важно отметить, что действие не будет выполнено, если оно не требуется.

Процедура ifelse принимает три аргумента: логическое выражение, действие, выполняемое, если выражение истинно, и действие, выполняемое, если выражение ложно. Используя соответствующие имена аргументов, можно создать процедуру ifelse2, которая будет вести себя аналогично процедуре ifelse.

Рекурсивные процедуры в Logo не требуют специальной синтаксической поддержки. Их можно реализовать с помощью процедур run, sentence, first и butfirst. Рекурсия может быть реализована путём вызова процедуры с параметрами, полученными из исходного списка. Если параметр является словом, его необходимо заключить в кавычки.

Наконец, мы рассмотрим пример использования рекурсии для рисования фрактала. С помощью рекурсивного алгоритма можно нарисовать треугольник Серпинского, который состоит из трёх меньших треугольников, каждый из которых, в свою очередь, также состоит из трёх ещё меньших треугольников. Этот процесс повторяется до тех пор, пока глубина рекурсии не достигнет заданного значения. Этот раздел описывает типичную структуру интерпретатора Logo. Хотя эта глава является независимой, она также ссылается на сопутствующий проект. Завершение этого проекта позволит создать эффективную реализацию интерпретатора, описанного в этой главе.

Интерпретатор Logo может иметь ту же структуру, что и интерпретаторы калькуляторов. Анализатор создаёт структуры данных выражений, которые интерпретируются оценщиком. Оценщик проверяет форму выражения и для вызова выражения вызывает функцию с некоторыми параметрами для применения определённого процесса. Однако существуют некоторые структурные различия, чтобы соответствовать специфической грамматике Logo.

Строки. Анализатор Logo не считывает строку кода по одной строке, а считывает несколько выражений, возможно, упорядоченных в одной строке. Он не возвращает дерево выражений, а возвращает предложение Logo.

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

>>> parse_line('print sum 10 difference 7 3')
['print', 'sum', '10', 'difference', '7', '3']

Анализ выполняется очень мало, потому что динамические характеристики Logo требуют от оценщика анализа структуры вложенных выражений.

Анализатор не раскрывает структуру предложения, предложение представлено в виде вложенного списка Python.

>>> parse_line('print sentence "this [is a [deep] list]')
['print', 'sentence', '"this', ['is', 'a', ['deep'], 'list']]

Полная реализация parse_line находится в logo_parser.py сопутствующего проекта.

Оценка. Логотип оценивает одну строку за раз. Рамочная реализация оценщика определяется в сопутствующем проекте logo.py. Предложение, возвращённое из parse_line, передаётся функции eval_line, которая оценивает каждое выражение в строке. Функция eval_line многократно вызывает logo_eval, который оценивает следующее полное выражение, пока строка не будет полностью оценена, после чего возвращает последнее значение. Функция logo_eval оценивает отдельное выражение.

logo_eval функция оценивает различные формы выражений: базовые, переменные, определения, ссылки и вызовы, мы уже представили их в предыдущем разделе. Форма многоэлементных выражений в Logo может быть определена путём проверки первого элемента. Каждое выражение имеет свои собственные правила оценки.

1. Базовые выражения (которые могут быть истолкованы как числа, True или False слова) оцениваются сами по себе.
2. Переменные ищутся в среде. Среда будет подробно обсуждаться в следующем разделе.
3. Определения обрабатываются как особые случаи. Пользовательские определённые процессы также будут подробно обсуждены в следующем разделе.
4. Ссылки на выражения оцениваются как текст, на который они ссылаются, который представляет собой строку без ведущих кавычек. Предложения (представленные в виде списков Python) также рассматриваются как ссылки, они оцениваются сами по себе.
5. Вызовы выражений ищут оператор в текущей среде и вызывают процедуру, связанную с этим оператором.

Ниже приведена простая реализация logo_apply. Мы опустили некоторые проверки ошибок, чтобы сосредоточиться на обсуждении. Сопутствующий проект содержит более надёжную реализацию.

>>> def logo_eval(line, env):
        """Evaluate the first expression in a line."""
        token = line.pop()
        if isprimitive(token):
            return token
        elif isvariable(token):
            return env.lookup_variable(variable_name(token))
        elif isdefinition(token):
            return eval_definition(line, env)
        elif isquoted(token):
            return text_of_quotation(token)
        else:
            procedure = env.procedures.get(token, None)
            return apply_procedure(procedure, line, env)

В приведённом выше последнем случае вызывается вторая процедура, представленная функцией apply_procedure. Чтобы вызвать процедуру, названную оператором, оператор будет найден в текущей среде. В приведённой выше реализации env — это экземпляр класса Environment, который будет описан в следующем разделе. Атрибут env.procedures представляет собой словарь, содержащий сопоставление между операторами и процедурами. В Logo среда содержит отображение слов, и в ней нет локальных определённых процедур. Кроме того, Logo поддерживает отдельные отображения имён процедур и имён переменных, называемые разделённым пространством имён. Тем не менее совместное использование имён не рекомендуется.

Вызов процедуры. Вызов процедуры начинается с вызова функции apply_procedure, которой передаётся функция, найденная logo_apply, вместе со строкой кода и текущей средой. Процесс вызова в Logo более универсален, чем calc_apply в калькуляторах. В частности, apply_procedure должен проверять процедуру, которую предполагается вызвать, чтобы определить количество параметров n перед оценкой n операторов выражений. Здесь мы видим, почему анализатор Logo не может просто построить дерево выражений на основе синтаксического анализа, поскольку структура дерева определяется процессом.

Функция apply_procedure вызывает функцию collect_args, которая должна многократно вызывать logo_eval для оценки следующих n выражений строки. После завершения оценки параметров процедуры apply_procedure затем вызывает logo_apply, который фактически вызывает процедуру с параметрами. Следующий рисунок вызова иллюстрирует этот процесс.

Наконец, функция logo_apply принимает два параметра: базовую процедуру и пользовательскую определённую процедуру, обе из которых являются экземплярами Procedure. Procedure — это объект Python, который имеет имя процедуры, количество аргументов, тело и два логических атрибута. Тело может иметь различные типы. Базовая процедура реализована в Python, поэтому её телом является функция Python. Тело пользовательской определённой процедуры (не базовой) определено в Logo, поэтому его телом является список строк кода Logo. Procedure также имеет два булевых атрибута. Один указывает, является ли процедура базовой, а другой указывает, требуется ли доступ к текущей среде.

>>> class Procedure():
        def __init__(self, name, arg_count, body, isprimitive=False,
                     needs_env=False, formal_params=None):
            self.name = name
            self.arg_count = arg_count
            self.body = body
            self.isprimitive = isprimitive
            self.needs_env = needs_env
            self.formal_params = formal_params

Базовая процедура применяет тело к списку аргументов и возвращает результат в качестве вывода процедуры.

>>> def logo_apply(proc, args):
        """Apply a Logo procedure to a list of arguments."""
        if proc.isprimitive:
            return proc.body(*args)
        else:
            """Apply a user-defined procedure"""

Тело пользовательской определённой процедуры представляет собой список строк кода, каждая из которых является предложением Logo. Чтобы применить процедуру к списку параметров, мы оцениваем тело в новой среде, добавляя новый фрейм к текущей среде, связывая формальные параметры процедуры с фактическими параметрами в этом фрейме. Важным структурированным абстракцией пользовательского определённого процесса является оценка тела, которая требует рекурсивного вызова eval_line.

Рекурсия оценки/применения. Функции, реализующие оценку процесса, eval_line и logo_eval, а также функции, реализующие применение процесса, apply_procedure, collect_args и logo_apply, рекурсивно вызывают друг друга. Оценка операции требуется всякий раз, когда обнаруживается вызов выражения. Применение операции использует оценку для оценки фактических параметров и оценки тела пользовательской определённой процедуры. Эта общая структура взаимных рекурсий распространена в интерпретаторах: оценка используется для применения определений, а применение использует оценку для определения параметров.

Этот рекурсивный цикл завершается базовыми типами языка. Условием оценки базовых выражений является определение переменных, ссылок на выражения или определений. Условием применения вызова процедуры является вызов базовой процедуры. Эта взаимная рекурсивная структура, обрабатывающая формы выражений в оценочных функциях и обрабатывающая функции и их параметры в функциях применения, составляет суть процесса оценки. Перевод текста на русский язык:

Класс позволяет корректно поддерживать присвоение значений, определение процедур и поиск переменных с использованием динамической области видимости. Экземпляр Environment представляет собой связанное множество с общим доступом, доступное в определённой точке выполнения программы. Связывание в кадре организовано и реализуется через Python-словарь. Кадр содержит связывание имён переменных, но не процедур. Связывание между именами операторов и экземплярами Procedure в Logo хранится отдельно. В этой реализации кадр, содержащий связывание имён переменных, сохраняется как список словарей в свойстве _frames объекта Environment, а связывание имён процедур сохраняется как словарь в свойстве procedures.

Доступ к кадру осуществляется через два метода объекта Environment: lookup_variable и set_variable_value. Первый реализует процесс поиска, аналогичный процессу поиска из модели вычислительной среды, представленной в первой главе. Если имя найдено, возвращается связанное значение. Если нет, поиск продолжается в расширенном фрейме.

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

Вызов метода logo_eval вызывает метод lookup_variable при разрешении имени переменной. Метод set_variable_value вызывается методом logo_make и служит телом основного процесса make в Logo.

Помимо переменных и основного процесса make, наш интерпретатор поддерживает первую абстрактную операцию: связывание имени с значением. Теперь в Лого мы можем повторить первый шаг абстракции из первой главы.

? make "radius 10
? print 2 * :radius
20

Присвоение значения является лишь ограниченной формой абстракции. С самого начала курса мы видели, что даже для небольших программ пользовательские функции являются ключевым инструментом управления сложностью. Для реализации пользовательских процессов в Лого нам необходимы два улучшения. Во-первых, мы должны описать реализацию eval_definition, которая будет вызываться функцией Python при определении текущей строки. Во-вторых, нам нужно завершить наше описание в logo_apply, которое вызывает пользовательский процесс по некоторым параметрам. Оба изменения требуют использования класса Procedure, определённого в предыдущем разделе.

Определение достигается путём создания нового экземпляра Procedure, представляющего пользовательский процесс. Рассмотрим следующее определение процедуры в Лого:

? to factorial :n
> output ifelse :n = 1 [1] [:n * factorial :n - 1]
> end
? print fact 5
120

Первая строка определения предоставляет имя процесса factorial и формальный параметр n. Несколько следующих строк составляют тело процесса. Эти строки не оцениваются немедленно, а сохраняются для будущего использования. То есть эти строки считываются и анализируются eval_definition, но не передаются eval_line. Тело процесса читается до тех пор, пока не встретится строка, содержащая только end. В Лого end не является процессом, который необходимо оценить, и не является частью тела процесса. Это синтаксический маркер конца определения функции.

Экземпляр Procedure создаётся на основе имени процесса, списка формальных параметров и тела, и регистрируется в словаре атрибутов procedures в среде. В отличие от Python, в Лого, как только процесс связан с именем, другие определения не могут повторно использовать это имя.

Процесс logo_apply применяет экземпляр Procedure к некоторым параметрам, представленным в виде строкового значения (для слов) или списка (для предложений). Для пользовательского процесса logo_apply создаёт новый кадр, объект словаря, где ключи являются формальными параметрами процесса, а значения — фактическими параметрами. В языке с динамической областью видимости, таком как Лого, этот новый кадр всегда расширяется из текущего окружения в месте вызова процесса. Поэтому мы добавляем новый созданный кадр к текущему окружению. Затем каждая строка тела последовательно передаётся eval_line. Наконец, после завершения оценки тела мы можем удалить новый созданный кадр из окружения. Поскольку Лого не поддерживает первоклассные или эквивалентные процессы, во время выполнения программы нам не требуется отслеживать более одного окружения одновременно.

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

? to f :x
> make "z sum :x :y
> end
? to g :x :y
> f sum :x :x
> end
? g 3 7
? print :z
13

Оценка этих выражений создаёт окружение, состоящее из процессов и кадров, которые поддерживаются в отдельных пространствах имён. Порядок кадров определяется порядком вызовов.

3.6.5 Данные как программа

Размышляя о значении выражений в Лого, может быть полезно провести аналогию с программой. Одна из точек зрения на смысл программы заключается в том, что программа является описанием абстрактной машины. Например, рассмотрим ещё раз вычисление факториала:

? to factorial :n
> output ifelse :n = 1 [1] [:n * factorial :n - 1]
> end

Мы можем выразить это на Python как эквивалентную программу, используя традиционные выражения.

>>> def factorial(n):
        return 1 if n == 1 else n * factorial(n - 1)

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

Аналогично, мы можем рассматривать интерпретатор Лого как очень специфическую машину, которая принимает описания машин в качестве входных данных. Учитывая этот ввод, интерпретатор может настроить себя так, чтобы имитировать описанную машину. Например, если мы введём определение факториала в интерпретатор, он сможет вычислить факториал.

С этой точки зрения наш интерпретатор Лого можно рассматривать как универсальную машину. Когда на вход подаётся описание программы в Лого, он может имитировать другие машины. Он работает с данными объектами в программировании, действуя как связующее звено между самим языком программирования и его данными. Представьте себе, что пользователь вводит выражение в Лого в нашем работающем интерпретаторе Лого. С точки зрения пользователя, такое выражение, как sum 2 2, является выражением в языке программирования, которое должно быть оценено интерпретатором. Однако с точки зрения интерпретатора выражение представляет собой просто предложение из слов, которое можно манипулировать в соответствии с набором заранее определённых правил.

Программа пользователя — это данные интерпретатора, и это не должно вызывать путаницы. Фактически, иногда игнорирование этого различия может быть более удобным и позволить пользователю явно оценивать данные объекты как выражения. В Лого, независимо от того, когда мы используем процесс run, мы используем эту способность. В Python существует аналогичная функция: функция eval оценивает выражение Python, а функция exec оценивает оператор Python, поэтому:

>>> eval('2+2')
4

и

>>> 2+2
4

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