Шаг 119.
Практическое занятие №9. Расширение учебного интерпретатора языка LISP

    На этом шаге мы рассмотрим задачи, расширяющие возможности учебного интерпретатора языка 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)

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

  1. Расширьте учебный интерпретатор, включив интерпретацию:
    • функции, которая возвращает копию списка;
    • функции, возвращающей наибольший элемент одноуровневого числового списка LST;
    • функции, позволяющей "склеивать" два списка.

       

  2. Рассмотрите расширение учебного интерпретатора посредством включения в него:
    • функции CDRN такой, что (CDRN N L) будет эквивалентна функции (CDDD...DR L), в имени которой имеется N букв D;
    • функции, возвращающей список, построенный из первых N элементов заданного списка LST;
    • функции, возвращающей длину списка.

       

  3. Определите версию учебного интерпретатора, которая включает в себя интерпретацию:
    • функции, записывающей элементы списка в порядке, обратном данному;
    • функции, возвращающей N-й элемент списка LST;
    • функции, удаляющей N-й элемент списка LST.

       

  4. Дополните интерпретатор так, чтобы он включал интерпретацию:
    • функции, вставляющей элемент X на N-ю позицию в список LST;
    • функции, осуществляющей сортировку списка LST;
    • функцию DISTL (распределение слева), действие которой рассмотрим на примере:
           (A (B1 B2 ... BN)) --> ((A B1) (A B2) ... (A BN))
      

       

  5. Расширьте учебный интерпретатор, включив в него интерпретацию:
    • функции 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, возвращающей последний элемент списка.

       

  6. Определите расширение учебного интерпретатора для следующих функций:
    • функции DEPTH, такой, что (DEPTH L) возвращает максимальную глубину подсписков списка L. Так, если L есть (1 4 (2 6 (3 7) 8)), то (DEPTH L) возвращает 3;
    • функции LIST;
    • функции, возвращающей список, построенный из последних N элементов данного списка.

       

  7. Перепишите интерпретатор так, чтобы он включал интерпретацию:
    • функции INSLIST, зависящую от трех аргументов N, U и V, вставляющей в список U, начиная с N-го элемента, список V;
    • функции, удаляющей повторные вхождения элементов в список, например: (A B D D A) --> (A B D);

       

  8. Расширьте учебный интерпретатор, включив в него:
    • логические операции NOT, AND и OR;
    • логические операции: импликацию и эквивалентность.
    • предикат ALL (квантор всеобщности) и предикат EXIST (квантор существования) с синтаксисом: (ALL X E) и (EXIST X E).

          При вычислении предиката ALL выражение E вычисляется дважды, сначала переменная T получает значение T, а затем NIL. К результатам применяется операция AND. Аналогично предикат EXIST также требует вычисления выражения E при двух различных значениях переменной. К результатам применяется затем операция OR. Такой интерпретатор является вычислительной формой пропозиционального исчисления.

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




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