Макет інтерпретатора скриптової мови на основі 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 описані основні класи, що підтримують роботу інтерпретатора, у тому числі:



  1. Вузли – елементи списків, які представляють програму і дані
    TLNode – Базовий клас для всіх вузлів
    TLRefNode – Базовий клас для вузлів з лічильником посилань
    TLNumber – Число
    TLString – Рядок
    TLVariant – Варіант – введений для підтримки OLE – автоматизації
    TLCons – Вузол – список [голова – хвіст]
    TNamedNode – Базовий клас для іменованих об’єктів
    TLAtom – Атом
    TLKFun – Вбудована функція

  2. Словник – 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)
)

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*