Макет интерпретатора скриптового языка на основе Lisp

Владимир Баскаков

Автор: Владсилав Баскаков, Королевство Delphi

Краткое описание проекта.

Представленная библиотека реализует интерпретатор подмножества языка Lisp. Библиотека является экспериментальной, она не претендует ни на полноту реализации, ни на высокое быстродействие, ни на тщательное тестирование. Показателем ее относительной работоспособности является успешная интерпретация нескольких простых программ:

программы рекурсивного вычисления чисел Фибоначчи

(progn

;определим функцию
(defun fibo (x)
(cond
 ((eq x 1) 1)
 ((eq x 0) 0)
 ( 't (+ (fibo (- x 1)) (fibo (- x 2))))
)
)
;и вычислим ее
(fibo 30)
)

программа, формирующая небольшой документ Word через вызов методы OLE - автоматизации:

традиционный синтаксис

(LET*  ((WordApp (oleobject "Word.Application")));создадим объект

     (SETPROP WordApp "visible" 't) ;покажем главное окно
     (LET* ((  WordDocs  (GETPROP WordApp "Documents")   ))
          (CALLMETHOD WordDocs "Add");cоздадим документ
    )
     (LET* ((  WordSel  (GETPROP WordApp "Selection")   ))
          (CALLMETHOD WordSel   "TypeText"  " Здравствуй Word!")
    )
)

и сокращенный вариант:

(owith (oleobject "Word.Application") ;создадим объект

     (oset "visible" 't) ;покажем главное окно
     (owith (oget "Documents")  
           (ocall "Add") 
      ) ;cоздадим документ
     (owith  (oget "Selection") ;и внесем текст 
          (ocall "TypeText" "Здравствуй Word!     ")
    )
)

программа, решающая задачу размещения ферзей на шахматной доске

приведена в конце статьи.

Состав библиотеки.

Библиотека состоит из модулей uNodes, uEval, uPars, ulMathLib, ulFormsLib, ulOleLib. В модуле uNodes описаны основные классы, поддерживающие работу интерпретатора, в том числе:

Узлы - элементы списков, представляющих программу и данные

TLNode  - Базовый класс для всех узлов
	TLRefNode - Базовый класс для узлов со счетчиком ссылок
		TLNumber - Число
		TLString -  Строка 
		TLVariant  - Вариант - введен для поддержки OLE - автоматизации
		TLCons - Узел - список [голова - хвост]

TNamedNode - Базовый класс для именованных объектов
	TLAtom - Атом
	TLKFun - Встроенная функция

Словарь - TLDict - владелец объектов - узлов, отвечает за их создание, поиск и уничтожение.

В модуле uEval вводится порожденный от TLDict класс TLEval, включающий в себя функции - члены, реализующие основные ключевые слова интерпретатора:

стандартные:: car,cdr,atom,list,cond,cons,defun,eq,aply,defmacro, backquote (функциональность реализована частично, поддерживается только макрорасширение comma), progn (реализовано только последовательное выполнение команд, нет локальных переменных, go, return), set, setq
и нестандартные:: getprop, setprop, callmethod - обеспечивают работу со свойствами и методами IDispatch;
car!, cdr!, cons!, eq! - макросы - аналоги функций, работают быстрее, но не совместимы с aply

Объект класса TLEval при создании создает и загружает дополнительные функции из объектов - библиотек (экземпляров классов TLMathLib, TLFormsLib, TLOleLib, описанных в модулях ULMathLib, ULFormsLib, ULOleLib соответственно).

TLMathLib содержит реализацию стандартных функций + - * / и нестандартных +! и -! - арифметических макросов (исполняются быстрее соответствующих функций, но несовместимы с aply)

TLFormsLib содержит реализацию стандартных конструкций if, while, let*, do* и нестандартных oWith, oCall, oGet, oSet, предназначенных для упрощения работы со свойствами и методами IDispatch.

TLOleLib содержит реализация нестандартной функции OleObject- скриптового аналога CreateOleObject.

В модуле uPars описан унаследованый от TLEval класс TLParser. Он и предназначен для трансляции входной строки - программы во внутреннее представление - узел-список, экземпляр TLConsNode, и обратного преобразования узла - результата исполнения программы в итоговую строку.

Принцип работы интерпретатора.

Программа передается на исполнение через метод TLParser.Run(Prg: String): String. При исполнении этого метода интерпретатор преобразует входную строку ко внутреннму представлению в виде списка (function TLParser.Compile(s: String): TLNode), сформированный узел-программа возвращает значение (function TLNode.Eval: TLNode), которое конвертируется в строку функцией TLNode.PutToStream(s: TStream) , сохраняющей текстовое представление узла в потоке.

Функция Compile состоит из двух частей. Первая часть - procedure TLParser.Parse(s: String); разбирает входную строку на слова и размещает их в списке TLParser.tokens: TstringList. В процессе разбора отсекаются комментарии. Эта часть реализована как конечный автомат, состояние автомата фиксируется в поле onChar:TcharProc, содержащем текущую функцию обработки очередного символа строки. Всего таких фукций 4:

    procedure TLParser.pBlank(c:Char);
    procedure TLParser.pComment(c:Char);
    procedure TLParser.pString(c:Char).
    procedure TLParser.pToken(c:Char);

Они соответствуют 4 состояниям автомата - неизвестное состояние/пробельные символы; комментарий, начинающийся с символа ";"; строковая константа, начинающаяся с символа "двойной кавычки"; другое слово (атом, число, спец.символы).

Вторая часть функции Compile - рекурсивная функция function TLParser.CompileNext:TLNode, последовательно перебирающая элементы полученного списка строк и формирующая итоговый объект - узел.

Метод function TLNode.Eval: TLNode - виртуальный, он перегружен для узлов разных типов. Так, для узлов - строк, чисел, вариантов, встроенных функций и макросов (TLNumber, TLString, TLVariant, TLKFun) он возвращает сам узел; для узлов-именованных атомов (TLAtom) - возвращает верхушку стека значений; для списков (TLCons)- рассматривает голову списка как функцию или макрос, и применяет ее к оставшейся части списка, рассматриваемой как аргументы.

Функция обработки аргументов function TLNode.ProcessArgs(args: TLNode): TLNode при необходимости вычисляет значения аргументов и передает их список перегружаемой функции function TLNode.Apply(args: TLNode): TLNode. Реализация метода Apply во встроенной функции (TLKFun) обрабатывает аргументы непосредственно; пользовательские функции представлены списками (TLCons), реализация Apply в списках предполагает связывание аргументов с формальными параметрами (TLNode.AddValue) и исполнением тела функции.

При тестировании библиотеки выяснилось, что исполнение рекурсивных функций по обработке списков с большой глубиной рекурсии, требует постоянного создания и освобождения объектов, что существенно увеличивает время интерпретации. Для ускорения работы освобождаемые объекты не уничтожаются, а помещаются в списки неиспользованных (TLDict: ConsHeap: TLCons, NumHeap: TLNumber; StrHeap:TLString; VarHeap:TLVariant;) перегружаемой функцией TLNode.Util, и при необходимости извлекаются оттуда (TLDict.NewNumber, TLDict.NewNumber, TLDict.NewVariant, TLDict.Cons).

Заключение

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

С другой стороны, логическая стройность концепций функционального программирования делает Lisp удобным и интересным полигоном для начинающего программиста. Представленная библиотека разрабатывалась в течении долгого времени как логическая игрушка, прошу не судить меня за отсутствие полноценных комментариев или описания библиотеки!

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

Кроме того, в статье не описан механизм обращения к методам и свойствам объектов OLE - автоматизации. Основа для функции доступа к свойствам OLE объектов (TLVariant.GetProp и TLVariant.SetProp) была найдена в стандартном модуле ComObj; идея вызова метода OLE - объекта взята из модуля OLE2AUTO широко известной библиотеки RX.

Главным источником информации по основам функционального программирования была для меня книга 'Введение в теорию программирования. Функциональный подход', являющаяся частью учебного курса "Интернет университета информационных технологий", она размещена на сайте проекта http://www.intuit.ru/department/se/tppfunc/. Программа компилировалась под Delphi 6 и не использует сторонних библиотек.

Приложение: Программа "Ферзи"

(progn

(defun null(x)
(if (eq x nil) t  nil) 
)

(defun append (a b)
(if a (cons (car a) (append (cdr a) b)) b
))

;проверим, что 2 ферзя, заданных парами p1 и p2 не бьют друг друга
(defun check1_pair (p1 p2)
(cond
 (( eq (- (car p1) (cdr p1)) (- (car p2) (cdr p2))) nil)
 (( eq (+ (car p1) (cdr p1)) (+ (car p2) (cdr p2))) nil)
 ('t 't)
)
); check1_pair

;проверим, что ферзь pair совместим не бьет ни одного из списка pairs 
( defun check_pair (pairs pair)
(if pairs 
    (if (check1_pair (car pairs) pair) (check_pair (cdr pairs) pair) nil)
    t
)
);check_pair

;переберем все строчки на текущей колонке

( defun hypot ( fer  cols rows allrows )
( if cols
    (if rows 
          ( append 
           ( hyp fer cols (car rows) allrows) 
            (hypot fer cols (cdr rows) allrows) 
           )
        nil
    )
    (list fer)
))

(defun  fr(cols row)
  (cons (car cols) row)
)

;исключим x из списка l
(defun exclude (l x)
(if l
   (let* (  (car_l (car l))  )
       (if (eq (car l) x) (cdr l) (cons (car l) (exclude (cdr l) x)) )
   )
nil
))

;попытаемся поставить очередного ферзя, если получится - 
;перейдем к следующей колонке
( defun hyp (fer cols row rows)
 (if cols  
      (if  (check_pair fer (fr cols row))       
          (let* ((nxtrws (exclude rows row)))
             (hypot   (cons (fr cols row) fer)   (cdr cols) nxtrws nxtrws )      
          )
          nil
        )
   (list fer)
  )
)

(defun ferz (l)    (hypot nil l l l   )
)

(defun lnum(x)
(cond 
  ((eq x 1) (list 1))
  ('t (cons x (lnum (- x 1))))
)
)

(defun cdrs(x)
(if x 
  (cons (cdr (car x)) (cdrs (cdr x))  )  
  nil
)
)


(defun allcdrs(x)
( if x  (cons 
          (cdrs (car x))
          (allcdrs (cdr x))
          )   nil )
)

;возвращает список всех расстановок ферзей на доске
(defun ferzi (x)
(allcdrs 
(ferz (lnum x)
)
)
)

 (ferzi 11)

)

Ссылки по теме