Основы функционального программирования

       

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


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

Здесь же определим общий цикл выполнения программ на 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)


Содержание раздела