Skip to content

Instantly share code, notes, and snippets.

@lorisleiva
Created March 21, 2021 17:08
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save lorisleiva/1f217a3b04735b83e3586fe9dc28099a to your computer and use it in GitHub Desktop.
<?php
// Nodes.
abstract class Node implements Visitable {}
class Number extends Node {
public function __construct(public float $value){}
public function accept(Visitor $visitor) {
return $visitor->visitNumber($this);
}
}
class Add extends Node {
public function __construct(public Node $left, public Node $right){}
public function accept(Visitor $visitor) {
return $visitor->visitAdd($this);
}
}
class Substract extends Node {
public function __construct(public Node $left, public Node $right){}
public function accept(Visitor $visitor) {
return $visitor->visitSubstract($this);
}
}
class Minus extends Node {
public function __construct(public Node $node){}
public function accept(Visitor $visitor) {
return $visitor->visitMinus($this);
}
}
class Assign extends Node {
public function __construct(public string $variable, public Node $node){}
public function accept(Visitor $visitor) {
return $visitor->visitAssign($this);
}
}
class Get extends Node {
public function __construct(public string $variable){}
public function accept(Visitor $visitor) {
return $visitor->visitGet($this);
}
}
class Calculator extends Node {
public function __construct(public array $statements){}
public function accept(Visitor $visitor) {
return $visitor->visitCalculator($this);
}
}
// Visitor contracts.
interface Visitable {
public function accept(Visitor $visitor);
}
abstract class Visitor {
abstract public function visitNumber(Number $node);
abstract public function visitAdd(Add $node);
abstract public function visitSubstract(Substract $node);
abstract public function visitMinus(Minus $node);
abstract public function visitAssign(Assign $node);
abstract public function visitGet(Get $node);
abstract public function visitCalculator(Calculator $node);
}
// Evaluating through a visitor.
class EvaluateVisitor extends Visitor
{
protected array $assignments;
public function __construct(array $preDefinedAssignments = [])
{
$this->assignments = $preDefinedAssignments;
}
public function visitNumber(Number $node)
{
return $node->value;
}
public function visitAdd(Add $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return $leftValue + $rightValue;
}
public function visitSubstract(Substract $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return $leftValue - $rightValue;
}
public function visitMinus(Minus $node)
{
$childValue = $node->node->accept($this);
return - $childValue;
}
public function visitAssign(Assign $node)
{
// Evaluate the child node.
$childValue = $node->node->accept($this);
// Store its value.
$this->assignments[$node->variable] = $childValue;
// Use the child value as the "Assign" value too.
return $childValue;
}
public function visitGet(Get $node)
{
if (! isset($this->assignments[$node->variable])) {
throw new \RuntimeException("Variable [{$node->variable}] was not assigned.");
}
return $this->assignments[$node->variable];
}
public function visitCalculator(Calculator $node)
{
if (empty($node->statements)) {
throw new \RuntimeException('The Calculator node requires at least one statement.');
}
$lastStatementValue = null;
foreach ($node->statements as $statement) {
$lastStatementValue = $statement->accept($this);
}
return $lastStatementValue;
}
}
// Calculator example.
$firstStatement = new Assign('foo', new Add(new Number(1), new Number(5)));
$secondStatement = new Substract(new Number(100), new Minus(new Get('foo')));
$calculator = new Calculator([$firstStatement, $secondStatement]);
// Evaluation.
$evaluateVisitor = new EvaluateVisitor();
echo $firstStatement->accept($evaluateVisitor) . "\n"; // Returns: 6
// echo $secondStatement->accept($evaluateVisitor) . "\n"; // Throws: Variable [foo] was not assigned.
echo $calculator->accept($evaluateVisitor) . "\n"; // Returns: 106
// Evaluation with predefined assignments.
$thirdStatement = new Add(new Get('answerToLifeTheUniverseAndEverything'), new Number(8));
$evaluateVisitorWithPredefinedAssignments = new EvaluateVisitor([
'answerToLifeTheUniverseAndEverything' => 42,
]);
echo $thirdStatement->accept($evaluateVisitorWithPredefinedAssignments) . "\n"; // Returns: 50
// Printing through a visitor.
class PrintVisitor extends Visitor
{
public function visitNumber(Number $node)
{
return $node->value;
}
public function visitAdd(Add $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return "$leftValue + $rightValue";
}
public function visitSubstract(Substract $node)
{
$leftValue = $node->left->accept($this);
$rightValue = $node->right->accept($this);
return "$leftValue - $rightValue";
}
public function visitMinus(Minus $node)
{
$childValue = $node->node->accept($this);
return "- $childValue";
}
public function visitAssign(Assign $node)
{
$childValue = $node->node->accept($this);
return "\${$node->variable} = $childValue";
}
public function visitGet(Get $node)
{
return "\${$node->variable}";
}
public function visitCalculator(Calculator $node)
{
$print = '';
foreach ($node->statements as $statement) {
$print .= $statement->accept($this) . ";\n";
}
return $print;
}
}
$printVisitor = new PrintVisitor();
echo $calculator->accept($printVisitor);
// Returns:
// $foo = 1 + 5;
// 100 - - $foo;
// Chaining visitors.
class RemoveDoubleNegationVisitor extends Visitor
{
protected bool $negative = false;
public function visitNumber(Number $node)
{
// Take both the negative boolean and the value into account
// So that we ensure the number's value is kept positive.
$negativeValue = ($this->negative xor ($node->value < 0));
$newNode = new Number(abs($node->value));
return $negativeValue ? new Minus($newNode) : $newNode;
}
public function visitAdd(Add $node)
{
// Give the same negative values to both branches
// And they will sort themselves out.
$negativeAddition = $this->negative;
$newLeft = $node->left->accept($this);
$this->negative = $negativeAddition;
$newRight = $node->right->accept($this);
// Bonus: Since we now know the right branch has no double negatives
// we can make an optimisation and replace "A + - B" with "A - B".
if ($newRight instanceof Minus) {
return new Substract($newLeft, $newRight->node);
}
return new Add($newLeft, $newRight);
}
public function visitSubstract(Substract $node)
{
// Since "A - B" is equivalent to "A + (-B)", let's
// transform our node and delegate to the `visitAdd` method.
$addition = new Add($node->left, new Minus($node->right));
return $addition->accept($this);
}
public function visitMinus(Minus $node)
{
// We inverse the negative boolean and let
// the child handle the change of sign.
$this->negative = ! $this->negative;
$newChild = $node->node->accept($this);
return $newChild;
}
public function visitAssign(Assign $node)
{
// Keep track of the current negative boolean.
$negativeAssignment = $this->negative;
// Reset it for the descedants.
$this->negative = false;
$newChild = $node->node->accept($this);
$newAssignment = new Assign($node->variable, $newChild);
// If the assignement was negative, wrap it in a Minus node
// since the Minus nodes auto-delete themselves in this visitor.
return $negativeAssignment ? new Minus($newAssignment) : $newAssignment;
}
public function visitGet(Get $node)
{
$newNode = new Get($node->variable);
return $this->negative ? new Minus($newNode) : $newNode;
}
public function visitCalculator(Calculator $node)
{
$newStatements = [];
foreach ($node->statements as $statement) {
// We reset the negative boolean for each statement.
$this->negative = false;
$newStatements[] = $statement->accept($this);
}
return new Calculator($newStatements);
}
}
$calculatorWithoutDoubleNegative = $calculator->accept(new RemoveDoubleNegationVisitor());
echo $calculatorWithoutDoubleNegative->accept(new PrintVisitor());
// Returns:
// $foo = 1 + 5;
// 100 + $foo;
@junneyang
Copy link

junneyang commented Dec 29, 2022

abstract class Visitor {
abstract public function visitNumber(Number $node);
abstract public function visitAdd(Add $node);
abstract public function visitSubstract(Substract $node);
abstract public function visitMinus(Minus $node);
abstract public function visitAssign(Assign $node);
abstract public function visitGet(Get $node);
abstract public function visitCalculator(Calculator $node);
}

great job !
all the visitor function returns nothing,
but EvaluateVisitor, PrintVisitor, RemoveDoubleNegationVisitor returns different types,
how to restrict the return types if we use another language like java?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment