Владимир Баскаков
дата публикации 17-10-2005 03:53 Макет интерпретатора скриптового языка на основе Lisp.
Представленная библиотека реализует интерпретатор подмножества языка 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")
)
(LET* (( WordSel (GETPROP WordApp "Selection") ))
(CALLMETHOD WordSel "TypeText" " Здравствуй Word!")
)
)
и сокращенный вариант:
(owith (oleobject "Word.Application")
(oset "visible" 't)
(owith (oget "Documents")
(ocall "Add")
)
(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
))
(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)
)
)
( defun check_pair (pairs pair)
(if pairs
(if (check1_pair (car pairs) pair) (check_pair (cdr pairs) pair) nil)
t
)
)
( 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)
)
(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)
)
| |
К материалу прилагаются файлы:
[Синтаксический анализ, разбор выражений, парсинг] [Средства разработки. Языки программирования.]
 Обсуждение материала нет сообщений |
