На этом шаге мы рассмотрим задачи, расширяющие возможности учебного интерпретатора языка LISP.

Тестовые примеры для учебного интерпретатора


   1. <-- ((NLAMBDA1 (X) (CDR1 X)) (1 (TIMES1 1 2) 4))
      --> ((TIMES1 1 2) 4)
      <-- ((NLAMBDA1 (X) (CAR1 X)) ((TIMES1 1 2) (PLUS1 1
      4)))
      --> (TIMES 1 2)
   2. <-- (DEFUN1 SUMMA (LAMBDA1 (LST) (COND1 ((EQUAL1 LST
      NIL1) 0) (T1 (PLUS1 (CAR1 LST) (SUMMA (CDR1 LST))))))
      --> (LAMBDA1 (LST) (COND1 ((EQUAL1 LST NIL1) 0) (T1
      (PLUS1 (CAR1 LST) (SUMMA (CDR1 LST)))))
      <-- (SUMMA (QUOTE1 (1 2 3)))
      --> 6
   3. <-- (DEFUN1 FACT (LAMBDA1 (X) (COND1 ((EQUAL1 X 1) 1)
      (T1 (TIMES1 X (FACT (DIFFERENCE1 X 1)))))))
      --> (LAMBDA1 (X) (COND1 ((EQUAL1 X 1) 1) (T1 (TIMES1
      X (FACT (DIFFERENCE1 X 1))))))
      <-- (FACT 5)
      --> 120
   4. <-- (DEFUN1 TEST (LAMBDA1 (X Y) (CONS1 X Y)))
      --> (LAMBDA1 (X Y) (CONS1 X Y))
      <-- (TEST A B)
      --> (A . B)
   5. <-- (DEFUN1 COPY (LAMBDA1 (E) (COND1 ((ATOM1 E) E) (T
      (CONS1 (COPY (CAR1 E)) (COPY (CDR1 E)))))))
      --> (LAMBDA1 (E) (COND1 ((ATOM1 E) E) (T (CONS1 (COPY
      (CAR1 E)) (COPY (CDR1 E))))))
      <-- (COPY (QUOTE1 (A B C)))
      --> (A B C)
   6. <-- (DEFMACRO1 AAA (NLAMBDA1 (G) (CAR1 G)))
      --> (NLAMBDA1 (G) (CAR1 G))
      <-- (AAA ((TIMES1 2 3) 4 5))
      --> (TIMES1 2 3)

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

Например, определим функцию NULL1 через примитивы системы:

   <-- (DEFUN1 NULL1 (LAMBDA1 (L) (EQUAL1 L NIL1)))
   --> (LAMBDA1 (L) (EQUAL1 L NIL1))

и сразу же воспользуемся ею:

   7. <-- (DEFUN1 MEMBER1 (LAMBDA1 (AL LST) (COND1 ((NULL1
      LST) NIL1) ((EQUAL1 AL (CAR1 LST)) LST) (T1 (MEMBER1
      AL (CDR1 LST))))))
      -->  (LAMBDA1 (AL LST) (COND1 ((NULL1 LST) NIL1)
      ((EQUAL1 AL (CAR1 LST)) LST) (T1 (MEMBER1 AL (CDR1
      LST)))))
      <-- (MEMBER1 (QUOTE1 B) (QUOTE1 (A B C)))
      --> (B C)
   8. <-- (DEFUN1 DEL (LAMBDA1 (A L) (COND1 ((NULL1 L) NIL1)
      ((EQUAL1 (CAR1 L) A) (CDR1 L)) (T1 (CONS1 (CAR1 L)
      (DEL A (CDR1 L)))))))
      --> (LAMBDA1 (A L) (COND1 ((NULL1 L) NIL1) ((EQUAL1
      (CAR1 L) A) (CDR1 L)) (T1 (CONS1 (CAR1 L) (DEL A (CDR1
      L)))))
      <-- (DEL 5 (QUOTE1 (3 4 5)))
      --> (3 4)
   9. <-- (DEFUN1 EVERY (LAMBDA1 (L) (COND1 ((NULL1 L) NIL1)
      ((NULL1 (CDR1 L)) L) (T1 (CONS1 (CAR1 L) (EVERY (CDR1
      (CDR1 L))))))))
      --> (LAMBDA1 (L) (COND1 ((NULL1 L) NIL1) ((NULL1 (CDR1
      L)) L) (T1 (CONS1 (CAR1 L) (EVERY (CDR1 (CDR1 L)))))))
      <-- (EVERY (QUOTE1 (A P R O L D)))
      (A R L)
  10. <-- (DEFUN1 APPEND1 (LAMBDA1 (L1 L2) (COND1 ((NULL1 L1)
      L2) ( T1 (CONS1 (CAR1 L1) (APPEND1 (CDR1 L1) L2)))))))
      --> (LAMBDA1 (L1 L2) (COND1 ((NULL1 L1) L2) ( T1 (CONS1
      (CAR1 L1) (APPEND1 (CDR1 L1) L2))))))
      <-- (APPEND1 (QUOTE1 (A P R)) (QUOTE1 (O L D)))
      (A P R O L D)

Задания для расширения интерпретатора

Расширьте учебный интерпретатор, включив интерпретацию:
- функции, которая возвращает копию списка;
- функции, возвращающей наибольший элемент одноуровневого числового списка LST;
- функции, позволяющей "склеивать" два списка.
Рассмотрите расширение учебного интерпретатора посредством включения в него:
- функции CDRN такой, что (CDRN N L) будет эквивалентна функции (CDDD...DR L), в имени которой имеется N букв D;
- функции, возвращающей список, построенный из первых N элементов заданного списка LST;
- функции, возвращающей длину списка.
Определите версию учебного интерпретатора, которая включает в себя интерпретацию:
- функции, записывающей элементы списка в порядке, обратном данному;
- функции, возвращающей N-й элемент списка LST;
- функции, удаляющей N-й элемент списка LST.
Дополните интерпретатор так, чтобы он включал интерпретацию:
- функции, вставляющей элемент X на N-ю позицию в список LST;
- функции, осуществляющей сортировку списка LST;
- функцию DISTL (распределение слева), действие которой рассмотрим на примере:
```
     (A (B1 B2 ... BN)) --> ((A B1) (A B2) ... (A BN))
```
Расширьте учебный интерпретатор, включив в него интерпретацию:
- функции DISTR (распределение справа), действие которой рассмотрим на примере:
```
     ((A1 A2 ... AN) B) --> ((A1 B) (A2 B) ... (AN B));
```
- функции COPY, такой, что (COPY X N) возвращает список из N копий целого числа X. Например, (COPY 3 5) возвращает список (3 3 3 3 3);
- функции LAST, возвращающей последний элемент списка.
Определите расширение учебного интерпретатора для следующих функций:
- функции DEPTH, такой, что (DEPTH L) возвращает максимальную глубину подсписков списка L. Так, если L есть (1 4 (2 6 (3 7) 8)), то (DEPTH L) возвращает 3;
- функции LIST;
- функции, возвращающей список, построенный из последних N элементов данного списка.
Перепишите интерпретатор так, чтобы он включал интерпретацию:
- функции INSLIST, зависящую от трех аргументов N, U и V, вставляющей в список U, начиная с N-го элемента, список V;
- функции, удаляющей повторные вхождения элементов в список, например: (A B D D A) --> (A B D);
Расширьте учебный интерпретатор, включив в него:
- логические операции NOT, AND и OR;
- логические операции: импликацию и эквивалентность.
- предикат ALL (квантор всеобщности) и предикат EXIST (квантор существования) с синтаксисом: (ALL X E) и (EXIST X E).
  При вычислении предиката ALL выражение E вычисляется дважды, сначала переменная T получает значение T, а затем NIL. К результатам применяется операция AND. Аналогично предикат EXIST также требует вычисления выражения E при двух различных значениях переменной. К результатам применяется затем операция OR. Такой интерпретатор является вычислительной формой пропозиционального исчисления.

Со следующего шага мы начнем приводить задачи с решениями.

Предыдущий шаг Содержание Следующий шаг