Пишем интерпретатор LISP на PHP

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

Предыстория


Идея написать свою реализацию LISP родилась у меня когда я решил серьёзно познакомиться с этим языком, когда я только услышал что написать самому лисп интерпретатор довольно просто я подумал, что наверное должно быть очень много различных реализаций этого языка на всём чём только можно писать. Немного погуглив я понял что так и есть. На чём только его не писали Java, Pytho, c#, даже js
Конечно же я нашёл пару реализаций на php, как выяснилось все они если хотябы работали без ошибок, то вычисляли простые выражения чтото вроде (+ 2 2). Но задачка с реализацией замыкания наподобие (def test (lambda (n) (lambda (x) (* x n)))) (def foo10 (test 10)) (print (foo10 2)) была им не под силу. Многие другие простые реализации не поддерживали ни лямбда выражений, ни объявления функций или макросов. Одна реализация на php мне очень понравилась она транслировала lisp код в php, но к сожалению всё с теми-же недостатками (замыкания не работали) то есть транслятор со своей задачей справлялся, и то что он выдавал выглядело вполне логично но работать на php не хотело. Тогда и возникла идея написать «рабочую» реализацию. Чтобы не изобретать велосипед, покопался среди чужого кода нашёл более менее приличную реализацию на питоне.
Решил взять за основу идею которую там увидил. Кроме того там был реализован довольно специфический диалект языка не похожий ни на scheme ни на clisp, его я и унаследовал в своём проекте.

Немного теории


Особенностью лиспа является то что синтаксис его списков (которые одновременно являются выражениями языка) отображает то как эти списки хранятся в памяти поэтому синтаксический анализатор языка преобразует строку в древовидную структуру объектов в памяти компьютера и затем эта структура вычисляется от «ветвей» этого «дерева» к «корню».
Вот как это работает:
Выражение (+ 1 (+ 2 3)) будет приведено к следующему виду:

[ FunctionObject(+), NumberObject(1), 
ListObject([ FunctionObject(+), NumberObject(2), NumberObject(3) ])
]

Вычисляем ListObject получаем:

[ FunctionObject(+), NumberObject(1), NumberObject(5) ]


Вычисляем FunctionObject(+) и получаем NumberObject(6)
(в классической реализации используются ссылочные списки объектов, но поскольку у меня есть массив почему-бы им не воспользоваться).

Подробно теорию вычисления лисп выражения я здесь описывать не буду это можно почитать в интернете, перейдём сразу к делу.

Практическая часть


Объявляем классы для каждого типа данных:
(У меня их 10)

FunctionObject — Объект функций [+, -, * ....] (+ 5 3).
LambdaObject — Lambda выражения.
ListObject — Список '(1 2 3)
LogicObject — логический обект boolean, реализует [*true*, *false*] (or *true* (not *true*)).
MacroObject — обект макрос ((macro (x) `(+ ,x 5)) 4).
NumberObject — число.
PairObject — точечные пары.
StringObject — строки.
SymbolObject — символьные объекты.
SyntaxObject — элементы синтаксиса языка [if, lambda, let, def ......].

Поскольку каждый из них вычисляемый то они все наследники класса Evalable с методом lispeval() который переопределяется в каждом классе наследнике и реализует то как этот тип данных будет вычислятся.
Например class NumberObject при вычислении вернёт сам себя, то есть число как не вычисляй оно останется числом.

class NumberObject extends Evalable {
//....
  function NumberObject($value) {
   // проверяем $value если это объект NumberObject то достаним из него значение
    if (is_object($value) && get_class($value) == "NumberObject") {
      $value = $value->v;
    }
    $this->v = $value;
  }
 
  function lispeval($env, $args=null) {
    return $this;
  }
//.....
}
* This source code was highlighted with Source Code Highlighter.


Совсем другое дело class FunctionObject при его вычисление происходить немного сложнее.
В лиспе функцией считается то что стоит первым элементом списка остальные элементы это параметры поэтому при инициализации этот объект получает собственно название функции $fn и объект где эта функция описана $t — это реализация объекта с окружением ведь должна быть возможность динамически пополнять список доступных функций.
Имея эти параметры можно выполнить вычисление: $t->{$fn}($env, $args);

class FunctionObject extends Evalable {
 
  var $fn = null;
  var $t = null;
//....
 
  function FunctionObject($fn, $t) {
    $this->fn = $fn;
    $this->t = $t;
  }
 
  public function lispeval($env, $args=null) {
    return $this->t->{$this->fn}($env, $args);
  }
//....
}
* This source code was highlighted with Source Code Highlighter.


В как я уже писал в самом начале парсер разбивает исходный текст программы на языке лисп на простые списки и создаёт из них экземпляры класса ListObject. После чего вызывается метод lispeval() корневого класса ListObject что автоматически инициализирует вычисление всех вложенных списков.
Напомню что первым элементом списка должен быть какой-то функциональный объект, или лябда выражение, или функция, или синтаксическая конструкция (например оператор if), поэтому перед вычислением мы проверяем первый элемент и если он не подходит выдаём ошибку, если же всё в порядке то запускает lispeval() этого первого объекта а в качестве параметра отдаём ему весь оставшийся список.

class ListObject extends Evalable {
 
  var $list = null;
 
  function ListObject($lst=null) {
    if ($lst)
      $this->list = $lst;
    else
      $this->list = array();
  }
 
  function lispeval($env, $args=null) {
    $fn = $this->list[0]->lispeval($env);
    $fn_class = get_class($fn);
    if (
        $fn_class == "LambdaObject" ||
        $fn_class == "MacroObject" ||
        $fn_class == "FunctionObject" ||
        $fn_class == "SyntaxObject"
    ) {
      return $fn->lispeval($env, array_slice($this->list, 1));
    } else {
      echo "Error!!! " . $fn->repr() . " is not applyable";
      exit();
    }
  }
}
* This source code was highlighted with Source Code Highlighter.


Кроме lispeval() эти классы содержат методы которые определяют их поведение при различных операциях над ними (я не стал использовать магические методы для совместимости с php4) например при сравнении, сложении или выводе на экран функцией print.

Так например выгдядит класс NumberObject:

class NumberObject extends Evalable {
 
  var $v = null;
 
  function NumberObject($value) {
    if (is_object($value) && get_class($value) == "NumberObject") {
      $value = $value->v;
    }
    $this->v = $value;
  }
 
  function repr() {
    return $this->v;
  }
 
  function getval() {
    return $this->v;
  }
 
  function lispeval($env, $args=null) {
    return $this;
  }
 
  function nullp() {
    if ($this->v == 0) {
      return new LogicObject(1);
    } else {
      return new LogicObject(0);
    }
  }
 
  function cmp($other) {
    if (get_class($this) == get_class($other)) {
      if ($this->v == $other->v) {
        return 0;
      } elseif ($this->v > $other->v) {
        return 1;
      } else {
        return -1;
      }
    } else {
      if ($this->v == $other) {
        return 0;
      } elseif ($this->v > $other) {
        return 1;
      } else {
        return -1;
      }
    }
  }
 
  function add($other) {
    if (is_object($other) && get_class($this) == get_class($other)) {
      return new NumberObject($this->v + $other->v);
    } else {
      return $this->v + $other;
    }
  }
 
  function sub($other) {
    if (get_class($this) == get_class($other)) {
      return new NumberObject($this->v - $other->v);
    } else {
      return $this->v - $other;
    }
  }
 
  function mul($other) {
    if (get_class($this) == get_class($other)) {
      return new NumberObject($this->v * $other->v);
    } else {
      return $this->v * $other;
    }
  }
 
  function div($other) {
    if (get_class($this) == get_class($other)) {
      return new NumberObject($this->v / $other->v);
    } else {
      return $this->v / $other;
    }
  }
 
  function mod($other) {
    if (get_class($this) == get_class($other)) {
      return new NumberObject($this->v % $other->v);
    } else {
      return $this->v % $other;
    }
  }
}
* This source code was highlighted with Source Code Highlighter.


Основой для этого всего является class Lisper он создаёт окружение и генерирует в нём начальный массив объектов для реализации базовых функций. Также в нём объявлены все базовые алгоритмы для базовых функций.

class Lisper {
 
  var $envData = array(
    'print' => array("FunctionObject", 'do_print'),
    'first' => array("FunctionObject", 'do_first'),
    'car' => array("FunctionObject", 'do_first'),
    'replaca' => array("FunctionObject", 'do_replaca'),
    'second' => array("FunctionObject", 'do_second'),
    'cadr' => array("FunctionObject", 'do_second'),
    'third' => array("FunctionObject", 'do_third'),
//......
    '+' => array("FunctionObject", 'do_add'),
    '-' => array("FunctionObject", 'do_sub'),
    '/' => array("FunctionObject", 'do_div'),
    '%' => array("FunctionObject", 'do_mod'),
    '*' => array("FunctionObject", 'do_mul'),
//......
  );
 
public function do_print($env, $args) {
    foreach ($args as $a) {
      $result = $a->lispeval($env)->repr();
      echo $result;
    }
    echo "\n";
    return new LogicObject(1);
  }
 
  public function do_first($env, $args) {
    return $args[0]->lispeval($env)->first();
  }
 
  public function do_replaca($env, $args) {
    return $args[0]->lispeval($env)->replaca($args[1]->lispeval($env));
  }
 
  public function do_second($env, $args) {
    return $args[0]->lispeval($env)->second();
  }
 
  public function do_third($env, $args) {
    return $args[0]->lispeval($env)->third();
  }
 
//......
 
public function do_add($env, $args) {
    $ans = 0;
    foreach ($args as $n) {
      $ans = $n->lispeval($env)->add($ans);
    }
    return new NumberObject($ans);
  }
 
  public function do_sub($env, $args) {
    $ans = $args[0]->lispeval($env);
 
    if (isset($args[1])) {
      foreach (array_slice($args, 1) as $n) {
        $ans = $ans->sub($n->lispeval($env));
      }
    } else {
      $z = new NumberObject(0);
      $ans = $z->sub($ans);
    }
    return new NumberObject($ans);
  }
 
  public function do_div($env, $args) {
    $ans = $args[0]->lispeval($env);
    if (isset($args[1])) {
      foreach (array_slice($args, 1) as $n) {
        $ans = $ans->div($n->lispeval($env));
      }
    } else {
      # (/ 2) - give inverse
      $one = new NumberObject(1);
      $ans = $one->div($ans);
    }
    return new NumberObject($ans);
  }
 
  public function do_mod($env, $args) {
    $ans = $args[0]->lispeval($env);
    foreach (array_slice($args, 1) as $n) {
      $ans = $ans->mod($n->lispeval($env));
    }
    return new NumberObject($ans);
  }
 
  public function do_mul($env, $args) {
    $ans = $args[0]->lispeval($env);
    foreach (array_slice($args, 1) as $n) {
      $ans = $ans->mul($n->lispeval($env));
    }
    return new NumberObject($ans);
  }
}
* This source code was highlighted with Source Code Highlighter.


В итоге получился интерпретатор который поддерживает основные возможности языка лисп, такие как макросы, лямбда выражения, замыкания, пользовательские функции. Заметно тормозит рекурсия (наверно так и должно быть?).

Вот список выражений которые он может вычислить:

(print (+ 5 3))
(print (- 5 3))
(print (- 3 5))
(print (+ 5 2.3 2.7))
(print (+ 5 (* 2 6.55)))
(print (* 5 (+ 3 4 6) 22 (* 2.4 5 0.001) (- 5 (+ 2 (- 2 4)))))
(print '(+ 5 3))
(print 'a)
(print '(this is "cool"))
(print (first '(a b c)))
(print (rest '(a b c)))
(print (cons 'a '(b c d)))
(print (append '(a b c) '(d e f) (list 1 2 3 4)))
(print (setq fred '(a b c)))
(print (rest fred))
(print (put 'fred 'birthday 'june-12-1973))
(print (get 'fred 'birthday))
(print (logic 0.5))
(print (logic 1.0))
(print (not (logic 0.0)))
(print (not (logic 0.35)))
(print (and *true* (not *true*)))
(print (or *true* (not *true*)))
(print (setq *true* (logic .95)))
(print (and *true* (not *true*)))
(print (or *true* (not *true*)))
(print (setq *true* (logic 1.0)))
(print (> 5 2))
(print (> 2 5))
(print (> 5 (* 3 (+ 2 1))))
(print (> (* 3 (+ 2 1)) (+ 1 2 3)))
(print (== "wow" "fred"))
(print (!= "wow" "fred"))
(print (>= 5 5))
(print (<= "andy" "bobbie"))
(print (if (> 5 2) 'true 'false))
(print (if (< 5 2) 'true 'false))
(print (if (< 5 2) 'true))
(print (if (not (< 5 2)) 'true))
(print (lambda (x y) (* x y)))
(print ((lambda (x y) (* x y)) 5 2))
(print (lambda (x y) (* x y) (+ x y)))
(print ((lambda (x y) (* x y) (+ x y)) 5 2))
(print (def mult (lambda (x y) (* x y))))
(print (mult 5 7))
(print (def dumb (lambda (x y) (if (> x y) (* x y) (/ x y)))))
(print (dumb 5.0 3.0))
(print (dumb 3.0 5.0))
(print (let ((x 5) (y 3)) (+ x y)))
(print (let ((x 5) (y 3) z) (+ x y)))
(print (def dumb (lambda (x) (let ((y 12)) (* x y)))))
(print (dumb 3))
(print `a)
(print `(a b ,fred))
(print `(a b ,@fred))
(print `(a (b (c (d (e (f ,@fred)))))))
(print ((macro (x) `(+ ,x 5)) 4))
(print (def incf (macro (x) `(setq ,x (+ ,x 1)))))
(print (setq whee 33))
(print (incf whee))
(print (def foo (lambda (x y) (if (<= y 0) x (begin (foo (cons y x) (- y 1)))))))
(print (foo '() 12))
(print (let ((x 5)) (def bar (lambda () x))))
(print (bar))
(print (env-set (get-environment bar) 'x 33))
(print (bar))
(print (setq wow (list (cons 'a 'b) (cons 'q 'fun))))
(print (assoc 'a wow))
(print (- 5 (* 2 4)))
(print (- (* 2 4) 5))
(print (/ 17 350))
(print (/ 350 17))


Полный код интерпретатора вы можете посмотреть здесь.

PS: Не судите строго за качество кода изначально я не планировал выпускать этот проект на широкую публику и написал его ради развлечения когда-же решил написать про него то поправил немного код чтобы на php 5.3 не ругался а с точки зрения оптимизации там много работы.


0 комментариев

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.