makenowjust

require "bigdecimal"
require "bigdecimal/math"

def measure(name, &block)
  s = Process.clock_gettime(Process::CLOCK_MONOTONIC)
  r = block.call
  t = Process.clock_gettime(Process::CLOCK_MONOTONIC)

  time = t - s
  STDERR.puts "#{name}: #{time} s"

makenowjust

// An implementation of the RPNI (Regular Positive and Negative Inference) algorithm.

import scala.annotation.tailrec
import scala.collection.mutable
import scala.math.Ordering.Implicits.seqOrdering
import scala.util.boundary

final case class Dfa[Q, A](
    initialState: Q,
    acceptStateSet: Set[Q],

makenowjust

// This is an implementation of the MAT* algorithm in Scala 3.
//
// The MAT* algorithm is a learning algorithm for symbolic finite automata, proposed by
// George Argyros and Loris D'Antoni, "The Learnability of Symbolic Automata"
// https://doi.org/10.1007/978-3-319-96145-3_23.

import scala.annotation.tailrec
import scala.util.hashing.MurmurHash3

/** `BoolAlg` represents an effective Boolean algebra on the domain `D`.

makenowjust

// This is an implementation of the Λ* algorithm in Scala 3.
//
// The Λ* algorithm is a learning algorithm for symbolic automata, proposed by
// Samuel Drews and Loris D'Antoni (2017), "Learning Symbolic Automata"
// https://doi.org/10.1007/978-3-662-54577-5_10.

import scala.collection.mutable

/** `BoolAlg` represents an effective Boolean algebra on the domain `D`.
  *

makenowjust

$b = []

def op_proto(version)
  $b.concat([0x80, version])
end

def op_global(mod, name)
  $b.concat("c#{mod}\n#{name}\n".unpack("C*"))
end

makenowjust

import scala.util.boundary
import scala.collection.mutable
import scala.compiletime.ops.double
import scala.annotation.tailrec

final case class Mealy[Q, I, O](
    initial: Q,
    transition: Map[(Q, I), (O, Q)]
):
  type State = Q

makenowjust

// kv.scala - an implementation of the Kearns & Vazirani algorithm

import scala.annotation.tailrec
import scala.collection.mutable
import scala.compiletime.ops.double

/** A type for states. */
type Q = String

/** A deterministic finite-state automaton (DFA). */

makenowjust

import { Octokit } from 'octokit';

const { rest: github } = new Octokit();

const OWNER = 'makenowjust-labs';
const REPO = 'recheck';
const BRANCH = 'main';
const STATUS = 'success';
const WORKFLOW_ID = 'main.yml';
const PER_PAGE = 100;

makenowjust

require "benchmark"

require "rexml/document"

n = 10000

xml = REXML::Document.new(<<~XML)
  <?xml version="1.0" encoding="UTF-8"?>
  <breakfast_menu>
  <food>

makenowjust

// An implementation of Glushkov's construction in Scala.
//
// See https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm.

/** Nfa represents an non-deterministic finite state automaton.
  *
  * @tparam A
  *   an alphabet type
  * @tparam Q
  *   a state type