Детализация базовых функций

Абстрактная Лисп-машина. Система команд

Встраиваемые в ядро интерпретатора операции должны соответствовать стандартным правилам доступа к параметрам и размещения выработанного результата. Таким же правилам должен подчиняться и компилируемый код. Это позволяет формально считать равноправными встроенные и программируемые функции. Компилятор по исходному тексту программы строит код программы, эквивалентный тексту. Особенности процесса компиляции достаточно сложны даже для простых языков, поэтому характеристика результата компиляции часто задается в терминах языково-ориентированных абстрактных машин. Такой подход полезен для решения ряда технологических проблем разработки программных систем (мобильность, надежность, независимость от архитектур и т.п.).

При сравнении императивного и функционального подходов к программированию, П.Лэндин (P.J.Landin) предложил специальную абстрактную машину SECD, удобную для спецификации машинно-зависимых аспектов семантики Лиспа. Подробное описание этой машины можно найти в книгах Хендерсона и Филда-Харрисона по функциональному программированию [3, 4].

Машина SECD работает над четырьмя регистрами: стек для промежуточных результатов, контекст для размещения именованных значений, управляющая вычислениями программа, резервная память (Stack, Environment, Control list, Dump). Регистры приспособлены для хранения выражений в форме атомов или списков. Состояние машины полностью определяется содержимым этих регистров. Поэтому функционирование машины можно описать достаточно точно в терминах изменения содержимого регистров при выполнении команд, что выражается следующим образом:

s e c d => s' e' c' d' — переход от старого состояния к новому.

Для характеристики встроенных команд Лисп-интепретатора и результата компиляции программ базового Лиспа понадобятся следующие команды:

LD — ввод данного из контекста в стек ;

LDC — ввод константы из программы в стек ;

LDF — ввод определения функции в стек ;

AP — применение функции, определение которой уже в стеке ;

RTN — возврат из определения функции к вызвавшей ее программе;

SEL — ветвление в зависимости от активного (верхнего) значения стека ;

JOIN — переход к общей точке после ветвления;

CAR — первый элемент из активного значения стека ;

CDR — без первого элемента активное значение стека ;

CONS — формирование узла по двум верхним значениям стека ;

ATOM — неделимость (атомарность) верхнего элемента стека ;

EQ — равенство двух верхних значений стека ;

SUB1 — вычитание 1 из верхнего элемента стека ;

ADD1 — прибавление 1 к верхнему элементу стека ;

STOP — останов.

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

s e (STOP ) d >> s e (STOP ) d

Следуя Хендерсону, для четкого отделения обрабатываемых элементов от остальной части списка будем использовать следующие обозначения: (x . l ) — это значит, что первый элемент списка — x, а остальные находятся в списке l.

(x y . l ) — первый элемент списка — x, второй элемент списка — y, остальные находятся в списке l и т.д. Теперь мы можем методично описать эффекты всех перечисленных выше команд.

s e(LDC q . c)d           >>  (q . s) e c d 
    (a . s)e(ADD1 . c)d       >>  (a+1 . s) e c d
    (a . s)e(SUB1 . c)d       >>  (a-1 . s) e c d
    (a b . s)e(CONS . c)d     >>  ((a . b) . s) e c d
    ((a . b) . s)e(CAR . c)   >> (a . s) e c d
    ((a . b) . s)e(CDR . c)   >> (b . s) e c d
    (a . s)e(ATOM . c)d       >> (t . s) e c d
    (a b . s)e(EQ . c)d       >> (t . s) e c d

где t — логическое значение.

Для доступа к значениям, расположенным в контексте, можно определить специальную функцию N-th, выделяющую из списка элемент с заданным номером N в предположении, что длина списка превосходит заданный адрес.

(DEFUN N-th (n list )
       (COND
          ((EQ n 0 )(CAR list ))
          (T (N-th (SUB1 n ) (CDR list ) )) ))

Продолжаем описание команд Лисп-машины.

s e (LD n . c) d >> (x . s) e c d

где x — это значение ( N-th n e )

При реализации ветвлений управляющая программа соответствует следующему шаблону:

( ... SEL ( ... JOIN ) ( ... JOIN ) ... )

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

(t . s) e (SEL c1 c0 . c) d >> s e ct (c . d)
    s e (JOIN ) (c . d) >> s e c d

где ct — это c1 или c0 в зависимости от истинностного значения t.

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

s e (LDF f . c) d >> ((f . e) . s) e c d 
      ((f . ef) vf . s) e (AP . c) d 
        >> NIL (vf . ef) f (s e c . d) 
      (x) e (RTN ) (s e c . d) >> (x . s) e c d

где f — тело определения, ef — контекст в момент вызова функции, vf — фактические параметры для вызова функции, x — результат функции.

Упражнение 7.1. Программа имеет вид:

(LD 3 ADD1 LDC 128 EQ STOP)

Напишите последовательность состояний стека при работе программы и сформулируйте, что она делает.

Ответ: Данная программа проверяет, меньше ли на 1 значение, хранящееся в контексте по адресу 3, чем заданная в программе константа 128. При ее работе стек проходит следующие состояния:

NIL (3 ) (4 ) (128 4 ) (NIL )

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

(CADR e ) 
    (EQ (CAR e) 'QUOTE )
    (COND ((EQ n 0 )(CAR l )) 
               (T (CONS (SUB1 n ) (CDR l ))) )

(Адреса значений e, n, l можно обозначить как @e, @n, @l, соответственно.)

Ответ:

( LD @e CDR CAR )
    ( LD @e CAR LDC QUOTE EQ )
    ( LD @n LDc 0 EQ SEL (LD @l CAR JOIN) 
           (LD @n SUB1 LD @l CDR CONS JOIN) )

Упражнение 7.3. Напишите спецификацию команды SET, сохраняющей активное значение стека в контексте по заданному в программе адресу в предположении, что длина списка превосходит заданный адрес.

Ответ: Нужна функция, заменяющая в списке указанный старый элемент новым.

(DEFUN ASS (e n  l ) 
       (COND
          ((EQ n 0 )(CONS e (CDR l )) )
          (T (CONS (CAR l )
                         (ASS e (SUB1 n ) (CDR l ) )
     ) )  )  )

Тогда можно описать команду SET следующим образом:

(x . s) e (SET n . c) d >> s xne c d

где xne = (ASS x n e) — новое состояние контекста.

Функциональная модель процессора абстрактной машины

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

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

Объявление системы команд машины и их определения:

(DEFUN put (at ind def) (setf (get at ind) def))
    (put 'a 'SYM '(LAMBDA () (setq st (CONS (caar st)
                   (CDR st)))
    ))
    (put 'd 'SYM '(LAMBDA () (setq st (CONS (cadar st)
                   (CDR st)))
    ))
    (put 'at 'SYM '(LAMBDA () (setq st (CONS
                   (ATOM (CAR st))
                   (CDR st)))
    ))
    (put 'co 'SYM'(LAMBDA () (setq st (CONS
                   (CONS (CAR st) (cadr st))
                   (cddr st)))
    ))
    (put 'equ 'SYM '(LAMBDA () (setq st (CONS
                   (EQ (CAR st) (cadr st))
                   (cddr st)))
    ))
    (put 'sum 'SYM '(LAMBDA () (setq st (CONS
                   (+ (CAR st) (cadr st))
                   (cddr st)))
    ))
    (put 'def 'SYM '(LAMBDA () (setq st (CONS
                   (- (CAR st) (cadr st))
                   (cddr st)))
    ))
    (put 'mlt 'SYM '(LAMBDA () (setq st (CONS
                   (* (CAR st) (cadr st))
                   (cddr st)))
    ))
 
    (put 'ldc 'SYM '(LAMBDA ()
    ; CP — продолжение программы вслед за LDC
          (setq st (CONS (CAR cp)
             st))
          (setq cp (CDR cp))
    ; CP — без константы, переданной в стек
    ))
 
    ; Определение интерпретатора машины
 
    (DEFUN secd (LAMBDA ()(cond ((null cp)
    (print "?end-of-program!"))
          ((EQ (CAR cp) 'STOP)
          (print "!normal-finish!"))
          ((get (CAR cp)'SYM)
          (command (CAR cp) (CDR cp))
          (secd))
          (T (print "?error-command!")
          (setq cp (CDR cp))
          (secd))
    )))
    (DEFUN command (LAMBDA (acp dcp) (setq cp dcp)
          (print acp)
          (apply (get acp 'SYM)'())
          (prsecd)
          (read)
    ))
 
    ; Вывод на экран состояния машины
    (DEFUN prsecd (LAMBDA()(prst)(prcp)))
    (DEFUN prst (LAMBDA ()(print (list "stack:=" st 
       ))))
    (DEFUN prcp (LAMBDA ()(print (list "control:=" cp 
       ))))
 
    ; Задание состояния машины :
    ; ST — стек
    ; CP — управляющая программа
    ; ENV — контекст
    ; DM — память для восстановления состояния
    (setq st '())
    (setq cp '(ldc 1 ldc 2 ldc 3 mlt def ldc 4 equ 
       stop ))
    (secd)
    (prsecd)
    (read)
    (system)
 
    (setq st '(a ((1 2) (4 5)) 3 6 7 8 9 11 13 12 14 
       21 25 9 1 0))
    (setq cp '(at de co at equ stop sum def mlt stop))
    (prsecd)
    (secd)
    (prsecd)
       (setq st (cddr st))
    (setq cp (CDR cp))
    (prsecd)
    (secd)
    (prsecd)
       (system)
       (apply (get 'a 'SYM)'())
    (prst)
    (setq st (CDR st))
    (apply (get 'd 'SYM)'())
    (prst)
    (setq st (CDR st))
       (apply (get 'at 'SYM)'())
    (prst)
    (setq st (CDR st))
       (apply (get 'co 'SYM)'())
    (prst)
       (apply (get 'at 'SYM)'())
    (prst)
       (setq st (CDR st))
       (setq st (CDR st))
       (apply (get 'equ 'SYM)'())
    (prst)
    (setq st (CDR st))
       (apply (get 'sum 'SYM)'())
    (prst)
    (setq st (CDR st))
       (apply (get 'def 'SYM)'())
    (prst)
       (setq st (CDR st))
       (apply (get 'mlt 'SYM)'())
    (prst)
    (setq st '(12 12 12) )
    (prst)
    (setq st (CDR st))
       (apply (get 'equ'SYM)'())
    (prst)
    (system)