Pull to refresh

Заметки об архитектуре или Интерпретатор Forth на PHP 5.3

PHPForth

О чем пойдет речь?


Мне очень часто приходится проводить собеседования, нанимая на работу PHP-программистов. 2-3 человека в день — это вполне нормально, хотя и на грани выносливости.

Все кандидаты разные, кто-то просто великолепен, кто-то похуже. Но у тех, кто похуже, всегда одни и те же ошибки.

Во-первых они совершенно не интересуются развитием языка, на котором пишут, и вопрос «А что нового в PHP 5.3» ставит их в тупик, а уж предложение порассуждать на тему «Чтобы Вы добавили в будущие версии языка» — просто пугает.

Во-вторых они категорически не представляют, что PHP может быть хоть чем-то кроме «скриптов для сайтов». Особенно печально это в свете того, что на работе им придется заниматься далеко не сайтами и даже скорее всего не сайтами.

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

Таким кандидатам и посвящается этот топик. С уважением к их нелегкой доле (а быть программистом на самом деле непросто) и с надеждой, что он подтолкнет их вперед по пути самосовершенствования.

Что мы будем делать?

Давайте попробуем сделать интерпретатор Форта на PHP!

Форт меня всегда манил, как далекая галактика из антиматерии. Стек, слова в словаре, обратная польская нотация… Это только кажется сложным, но на самом деле очень просто, зато здорово «просветляет» и расширяет кругозор.

Давайте сделаем наше приложение консольным, никаких браузеров и серверов. Давайте писать его на PHP 5.3, стараясь использовать язык на 100%. И, конечно же, попробуем изначально сделать так, чтобы пришедшие после нас не повесились от нашего кода в первый же день.

Архитектура приложения

Мы с самого начала договорились с вами, что пишем на PHP 5.3, а это значительно облегчает работу системному архитектору. Примем сразу несколько принципов, которых будем придерживаться в ходе разработки:
  1. Для разделения уровней приложения используем пространства имен
  2. Каждое имя класса должно однозначно указывать на его место в файловой системе
  3. Один класс — один файл
  4. Все классы включаются только через автозагрузку
  5. Все ошибки обрабатываем исключениями, классы исключений подчиняем общим правилам

Возьмем в качестве корневого пространства имен для нашего приложения \FORTH. Основные классы Форт-машины положим в \FORTH\SYSTEM, а исключения будем располагать в \FORTH\EXCEPTIONS, которое само по себе тоже разделим на несколько, например — \FORTH\EXCEPTIONS\SYSTEM для исключений, возникающих в самой Форт-системе и, скажем, \FORTH\EXCEPTIONS\STACK для исключительных ситуаций, связанных со стеком.

В соответствии с 2 принципом архитектуры будем пространства имен однозначно преобразовывать к директориям в ФС, а имена классов — к именам файлов в этих директориях.

Получается примерно такой код:

<?php

$autoload = function ($class) {

	$path = explode('\\', $class);

	if ( 'FORTH' != array_shift($path) )
		throw new \FORTH\EXCEPTIONS\SYSTEM\NamespaceIsWrong();

	$filename = array_pop($path);

	require __DIR__ . '/' .
		implode('/', array_map('strtolower', $path)) . '/' . 
		$filename . '.php';

};

spl_autoload_register($autoload);


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

Берем этот код и кладем его в файл autoload.php в корне проекта.

Настраиваем запуск

Перед тем, как писать реальный код Форт-машины, нам нужна точка входа. Ее обеспечат три файла — forth.php будет инициализировать приложение и реализовывать главный цикл, а forth.bat и forth.sh будут играть вспомогательную роль, помогая запустить наш скрипт в режиме командной строки в разных ОС.

Под Windows файл forth.bat может выглядеть примерно так:
@echo off
SET PHP_PATH=Z:/usr/local/bin
%PHP_PATH%/php -q ./forth.php %1 > output.txt
type output.txt | more
pause


Я уверен, что читатели этого топика с легкостью его улучшат и с удовольствием создадут аналог для запуска нашего приложения под sh/csh/bash или любой другой командный интерпретатор.

Точку входа приложения, файл forth.php, оставим пока почти пустым, внесем в него лишь две строчки — объявление пространства имен и инициализацию автозагрузки
namespace FORTH;
require __DIR__ . '/autoload.php';


Стек и очередь команд

Настало время реализовать две главные части нашей Форт-машины: стек и очередь команд.

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

В PHP стек LIFO отлично реализуется массивами и операциями array_pop и array_push, поэтому не будет изобретать велосипед, а воспользуемся этими средствами. Учтем, что в данной реализации стек у нас может быть только один, поэтому сделаем класс стека синглтоном. У нас получится примерно такой код:

<?php

namespace FORTH\SYSTEM;

class Stack extends Singleton {

	private $stack = array();

	public function push($obj) {

		array_push(
			$this->stack,
			$obj
		);

	}

	public function pop() {

		if ( $this->isEmpty() )
			throw new \FORTH\EXCEPTIONS\STACK\StackIsEmpty();
		
		return array_pop(
			$this->stack
		);

	}

	public function isEmpty() {

		return empty($this->stack);

	}

}


Позвольте, скажете вы — а где же синглтон? Где же закрытый конструктор, привычный метод getInstance()?

Все просто — мы вынесли весь фунционал паттерна в специальный системный абстрактный класс \FORTH\SYSTEM\Singleton. Если Вы внимательно посмотрите код этого класса, то поймете основную идею — как LSB, появившееся в PHP 5.3 позволяет разделять абстрактное описание паттерна и его конкретную реализацию.

Совершенно аналогично с помощью массива организуем очередь, только используя функции array_push и array_shift.

Словарь

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

Слово будем представлять в виде объекта класса \FORTH\SYSTEM\Word, а словарь — \FORTH\SYSTEM\Dictionary, реализацию этих классов вы найдете в исходном коде приложения.

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

Стоит отметить, что класс словаря тоже несомненно должен быть реализован как синглтон, кроме того словарь уже при старте Форт-машины должен содержать в себе некий минимальный стандартный набор слов, так что кроме непосредственно класса \FORTH\SYSTEM\Dictionary нам потребуется реализовать класс StandartDictionary, выполняющий инициализацию словаря стандартными словами, а также добавить инициализацию стандартного словаря в точке входа в приложение.

Для начала реализуем в качестве стандартных слов четыре основные арифметические операции, «DUP» — удвоение числа на вершине стека, «SWAP» — перестановку двух верхних чисел со стека и "." — вывод числа с вершины стека. Особой сложности это не составит, вот как выглядит пример для сложения двух чисел:


		/*
		 * Сложение двух верхних чисел, помещение результата на стек
		 */
		$dict->addWord(
			new Word(
				'+',
				2,
				2,
				function ($a, $b) {
					return (array)($a+$b);
				}
			)
		);


Общаемся с внешним миром

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

Набросаем следующий код в forth.php:
$data = \file_get_contents($argv[1]);

$parser = SYSTEM\Parser::getInstance();
$parser->loadRawData($data);
$dataForQueue = $parser->makeQueue();

$queue = SYSTEM\Queue::getInstance();
$queue->loadArray($dataForQueue);

$stack = SYSTEM\Stack::getInstance();

$executor = SYSTEM\Executor::getInstance();
$executor->setStack($stack);
$executor->execute($queue);


Очевидно, что нам теперь нужно реализовать некий парсер, который будет принимать на вход строку, являющуюся Форт-программой и разбирать ее на составляющие — либо числа, либо слова словаря Форта. На выходе парсер должен вернуть нам массив с почти готовой очередью команд для Форт-машины, которую мы отдадим системной очереди команд. Ну и последние строки — собственно уже выполнение команд из очереди по очереди -))

Ничего сложного в коде «парсера» нет, наша задача очень проста — разбить строку по пробельным символам, а далее обработать. Если мы встречаем число, то просто поставить его в очередь, если же некий символьный литерал — спросить словарь, не является ли он словом, и если это действительно так — поставить в очередь объект-слово.

Гораздо интереснее код «палача». Исполнитель по сути представляет собой ядро Форт-машины — именно он оперирует со стеком и исполняет слова. Мы передадим ему объект нашего системного стека, загрузим в него очередь команд и попросим эту очередь над данным стеком выполнить.

Задача исполнителя — определить, чем является элемент очереди: числом, которое нужно положить на стек, либо словом, которое необходимо выполнить. Если с числом все просто, то слово потребует несколько больше умственных усилий — нужно снять со стека заданное количество чисел, сформировать из них массив аргументов и вызвать код слова, передав ему эти аргументы. Полученный результат, возможно, потребуется поместить на стек.

Выглядит это примерно так:


$args = array();

for ( $i = 1; $i <= $word->getStackPopCount(); $i++ )
	$args[] = $this->stack->pop();

$args = \array_slice($args, 0, $word->getOperandsCount());

$result = \call_user_func_array($word->getCallback(), $args);

if ( !\is_null($result) ) {
	foreach ( $result as $res ) {
		$this->stack->push($res);
	}
}


Что получилось?

А в результате у нас получился интерпретатор языка Форт на PHP — Форт-машина. Пусть код зияет большими пробелами (например мы нигде пока не ловим исключения, совершенно упущен момент с тестами), пусть много можно улучшить, но это улучшение уже не составит труда, основная работа сделана.

Для кого-то этот топик, возможно, откроет что-то новое — я буду только рад.
Кто-то прочтет и скажет «ну это же элементарно, что тут нового» — отлично.

А если кто-то знает, как сделать еще лучше — приходите в нашу команду, мы очень любим и высоко ценим профессионалов, которые, в свою очередь, любят и ценят язык, на котором программируют.

А я пошел спать -))

Исходный код

По мере написания этой статьи я выкладывал то, что получалось, в специально созданный проект на Google Code, откуда вы можете взять исходные коды: code.google.com/p/php-forth/source/browse/trunk

Код лицензирован под GPL v.3

Список литературы

  1. ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D1%82_%28%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%29
  2. ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA
  3. ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%BD%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F
  4. Вдохновлявшая меня советская книга про Форт, фиолетовая такая, для детей старшего школьного возраста, не помню ни название, ни выходные данные...
Tags:forthphpphp 5.3
Hubs: PHP Forth
Total votes 77: ↑61 and ↓16 +45
Views3.5K

Popular right now

Top of the last 24 hours