О чем пойдет речь?
Мне очень часто приходится проводить собеседования, нанимая на работу PHP-программистов. 2-3 человека в день — это вполне нормально, хотя и на грани выносливости.
Все кандидаты разные, кто-то просто великолепен, кто-то похуже. Но у тех, кто похуже, всегда одни и те же ошибки.
Во-первых они совершенно не интересуются развитием языка, на котором пишут, и вопрос «А что нового в PHP 5.3» ставит их в тупик, а уж предложение порассуждать на тему «Чтобы Вы добавили в будущие версии языка» — просто пугает.
Во-вторых они категорически не представляют, что PHP может быть хоть чем-то кроме «скриптов для сайтов». Особенно печально это в свете того, что на работе им придется заниматься далеко не сайтами и даже скорее всего не сайтами.
Ну и в третьих кандидаты, которые похуже, с трудом представляют себе процесс построения архитектуры программы. Паттерны — знают, и много, а вот как из паттернов сложить целостную систему, чтобы за нее не было мучительно стыдно — это уже с трудом.
Таким кандидатам и посвящается этот топик. С уважением к их нелегкой доле (а быть программистом на самом деле непросто) и с надеждой, что он подтолкнет их вперед по пути самосовершенствования.
Что мы будем делать?
Давайте попробуем сделать интерпретатор Форта на PHP!
Форт меня всегда манил, как далекая галактика из антиматерии. Стек, слова в словаре, обратная польская нотация… Это только кажется сложным, но на самом деле очень просто, зато здорово «просветляет» и расширяет кругозор.
Давайте сделаем наше приложение консольным, никаких браузеров и серверов. Давайте писать его на PHP 5.3, стараясь использовать язык на 100%. И, конечно же, попробуем изначально сделать так, чтобы пришедшие после нас не повесились от нашего кода в первый же день.
Архитектура приложения
Мы с самого начала договорились с вами, что пишем на PHP 5.3, а это значительно облегчает работу системному архитектору. Примем сразу несколько принципов, которых будем придерживаться в ходе разработки:
- Для разделения уровней приложения используем пространства имен
- Каждое имя класса должно однозначно указывать на его место в файловой системе
- Один класс — один файл
- Все классы включаются только через автозагрузку
- Все ошибки обрабатываем исключениями, классы исключений подчиняем общим правилам
Возьмем в качестве корневого пространства имен для нашего приложения \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
Список литературы
- 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
- ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA
- 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
- Вдохновлявшая меня советская книга про Форт, фиолетовая такая, для детей старшего школьного возраста, не помню ни название, ни выходные данные...