spec.php

<?php namespace spec {
    abstract class spec {
        abstract function desc   ()   : string;
        abstract function derive ($c) : spec; 
        abstract function sigma  ()   : spec; 
    }

    class spec_ok extends spec {
        function desc   ()   : string { return "ok"; }
        function derive ($_) : spec   { return $this; }
        function sigma  ()   : spec   { return $this; }
    }
    function spec_ok () : spec {
        static $instance; 
        if (!$instance) { $instance = new spec_ok; }
        return $instance;
    }
    class spec_null extends spec {
        function desc   ()   : string { return "null"; }
        function derive ($_) : spec   { return $this; }
        function sigma  ()   : spec   { return $this; }
    }
    function spec_null () : spec {
        static $instance; 
        if (!$instance) { $instance = new spec_null; }
        return $instance;
    }
    class spec_or extends spec { 
        public $left, $right;
        function __construct (spec $left, spec $right) { $this->left = $left; $this->right = $right; }        
        function derive ($c) : spec { 
            return spec_or(
                $this->left->derive($c), 
                $this->right->derive($c));
        }
        function sigma () : spec { 
            return spec_or(
                $this->left->sigma(), 
                $this->right->sigma()); 
        }
        function desc () : string { return "(or ".$this->left->desc()." ".$this->right->desc().")"; }
    }
    function spec_or (spec ...$specs) : spec {
        if (empty($specs)) return spec_null();
        if (count($specs) == 1) return $specs[0];
        if (count($specs) > 2) return spec_or($specs[0], spec_or(...array_slice($specs, 1)));

        list($left, $right) = $specs;
        if ($left instanceof spec_null) return $right;
        if ($right instanceof spec_null) return $left;

        return new spec_or($left, $right);
    }
    class spec_and extends spec { 
        public $left, $right;
        function __construct (spec $left, spec $right) { $this->left = $left; $this->right = $right; }        
        function derive ($c) : spec { 
            return spec_and(
                $this->left->derive($c), 
                $this->right->derive($c));
        }
        function sigma () : spec { 
            return spec_and(
                $this->left->sigma(), 
                $this->right->sigma()); 
        }
        function desc () : string { return "(and ".$this->left->desc()." ".$this->right->desc().")"; }
    }
    function spec_and (spec ...$specs) : spec {
        if (empty($specs)) return spec_null();
        if (count($specs) == 1) return $specs[0];
        if (count($specs) > 2) return spec_and($specs[0], spec_and(...array_slice($specs, 1)));

        list($left, $right) = $specs;
        if (
            $left instanceof spec_null
            or 
            $right instanceof spec_null
        ) return spec_null();

        if (
            $left instanceof spec_ok
            or 
            $right instanceof spec_ok
        ) return spec_ok();


        return new spec_and($left, $right);
    }
    class spec_seq extends spec {
        public $first, $second; 
        function __construct (spec $first, spec $second) { $this->first = $first; $this->second = $second; }
        function derive ($c) : spec { 
            return spec_or(
                spec_seq($this->first->derive($c), $this->second),
                spec_seq($this->first->sigma(), $this->second->derive($c)));
        }
        function sigma () : spec { 
            return spec_seq(
                $this->first->sigma(), 
                $this->second->sigma()); 
        }
        function desc () : string { return "(seq ".$this->first->desc()." ".$this->second->desc().")"; }
    }

    function spec_seq (spec ...$specs) : spec {
        if (empty($specs)) return spec_null();
        if (count($specs) == 1) return $specs[0];
        if (count($specs) > 2) return spec_seq($specs[0], spec_seq(...array_slice($specs, 1)));
        
        list ($first, $second) = $specs;
        if (
            $first instanceof spec_null 
            or 
            $second instanceof spec_null
        ) return spec_null();

        if ($first instanceof spec_ok) return $second;

        if ($second instanceof spec_ok) return $first;

        return new spec_seq($first, $second);
    }
    class spec_rep extends spec {
        public $spec; 
        function __construct (spec $spec) { $this->spec = $spec; }
        function derive ($c) : spec { return spec_seq($this->spec->derive($c), $this); }
        function sigma () : spec { return spec_ok(); }
        function desc () : string { return "(rep ".$this->spec->desc().")"; }
    }
    function spec_rep (spec $spec) : spec {
        if (
            $spec instanceof spec_null
            or 
            $spec instanceof spec_ok
        ) return spec_ok();

        return new spec_rep($spec);
    }
    class id extends spec {
        public $value; 
        function __construct ($value) { $this->value = $value; } 
        function derive ($c) : spec {
            return $this->value == $c? 
                spec_ok(): 
                spec_null();
        }
        function sigma () : spec { return spec_null(); }
        function desc () : string { return \var_export($this->value, true); }
    }
    function id ($value) : spec { return new id($value); }

    class spec_pred extends spec {
        public $predicate, $name;
        function __construct (callable $predicate, string $name) { $this->predicate = $predicate; $this->name = $name; }
        function derive ($c) : spec {
            return \call_user_func($this->predicate, $c)?
                spec_ok(): 
                spec_null();
        }
        function sigma () : spec { return spec_null(); }
        function desc () : string { return $this->name; }
    }
    function spec_pred (callable $pred, string $name) : spec { return new spec_pred($pred, $name); }

    function array_match (array $arr, spec $spec, bool $verbose = false) : bool {
        if ($verbose) {
            echo 
                "---------------\n".
                "in: ".\var_export($arr, true)."\n".
                "spec: ".$spec->desc()."\n";
        }
        if (empty($arr)) {
            return $spec->sigma() instanceof spec_ok; 
        }
        $first = $arr[0];
        $rest = array_slice($arr, 1);
        return array_match($rest, $spec->derive($first), $verbose);
    }

}

namespace sandbox {
    use \spec as s;
    use function spec\array_match; 
    $posInt = function ($n) : bool { 
        if (!is_numeric($n)) return false; 
        return $n > 0; };
    $even = function ($n) : bool { 
        if (!is_numeric($n)) return false; 
        return $n % 2 == 0; };
    $odd = function ($n) : bool { 
        if (!is_numeric($n)) return false; 
        return $n % 2 == 1; };

    $spec = s\spec_seq(
        s\spec_or(
            s\id("foo"),
            s\id("bar")
        ),
        s\spec_and(
            s\spec_pred($posInt, 'posInt?'),
            s\spec_pred($even, "even?")
        ),
        s\spec_rep(s\spec_pred($odd, 'odd?'))
    ); 
    // \var_dump(s\spec_or( s\id("foo"), s\spec_pred($even))->derive("foo"));
    \var_dump(
        array_match( ["foo", 12],           $spec)
        , array_match( ["foo", 12, 1, 3, 5],  $spec, true)
        , array_match( ["bar", 12, 1, 3, 5],  $spec)
        , array_match( ["bar", -1, 1],        $spec)
    );
}