Example.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4b997884",
   "metadata": {},
   "outputs": [],
   "source": [
    "from circuit import op, circuit\n",
    "from bfcl import gate, operation\n",
    "#See the following video for a full walkthrough: https://youtu.be/cnijtOVRwgg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ba529a22",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Implementation of a selector circuit\n",
    "c = circuit()\n",
    "#The first input is the selector. \n",
    "#If selector=1, then the second bit is passed to the output.\n",
    "#If selector=0, then the third bit is passed to the output.\n",
    "g0 = c.gate(op.id_, is_input=True)\n",
    "g1 = c.gate(op.id_, is_input=True)\n",
    "g2 = c.gate(op.id_, is_input=True)\n",
    "\n",
    "g3 = c.gate(op.not_, [g0])\n",
    "g4 = c.gate(op.and_, [g0, g1])\n",
    "g5 = c.gate(op.and_, [g3, g2])\n",
    "g6 = c.gate(op.or_, [g4, g5])\n",
    "\n",
    "g7 = c.gate(op.id_, [g6], is_output=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b5f4fe6a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n"
     ]
    }
   ],
   "source": [
    "print(c.evaluate([0,0,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "de7928f4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0]\n",
      "[1]\n",
      "[0]\n",
      "[1]\n",
      "[0]\n",
      "[0]\n",
      "[1]\n",
      "[1]\n"
     ]
    }
   ],
   "source": [
    "inputs = [[0,0,0],\n",
    "         [0,0,1],\n",
    "         [0,1,0],\n",
    "         [0,1,1],\n",
    "         [1,0,0],\n",
    "         [1,0,1],\n",
    "         [1,1,0],\n",
    "         [1,1,1]]\n",
    "for i in inputs:\n",
    "    print(c.evaluate(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b0f7ae89",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 8\n",
      "1 3\n",
      "1 1\n",
      "1 1 0 3 INV\n",
      "2 1 0 1 4 AND\n",
      "2 1 3 2 5 AND\n",
      "2 1 4 5 6 LOR\n",
      "1 1 6 7 LID\n"
     ]
    }
   ],
   "source": [
    "#Output the circuit in the Bristol Fashion\n",
    "#Run the next segment of code first.\n",
    "for line in bfc(c).emit().split('\\n'):\n",
    "    print(line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b23b6ca0",
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import annotations\n",
    "\n",
    "class bfc():\n",
    "    \"\"\"\n",
    "    Data structure for circuits represented using the Bristol Fashion.\n",
    "    A string representing a circuit that conforms to the Bristol Fashion\n",
    "    syntax can be parsed into an instance of this class.\n",
    "\n",
    "    >>> circuit_string = ['7 36', '2 4 4', '1 1']\n",
    "    >>> circuit_string.extend(['2 1 0 1 15 AND', '2 1 2 3 16 AND'])\n",
    "    >>> circuit_string.extend(['2 1 15 16 8 AND', '2 1 4 5 22 AND'])\n",
    "    >>> circuit_string.extend(['2 1 6 7 23 AND', '2 1 22 23 9 AND'])\n",
    "    >>> circuit_string.extend(['2 1 8 9 35 AND'])\n",
    "    >>> circuit_string = \"\\\\n\".join(circuit_string)\n",
    "    >>> c = bfc(circuit_string)\n",
    "\n",
    "    The string representation can be recovered from an instance of this\n",
    "    class, as well.\n",
    "\n",
    "    >>> c.emit() == circuit_string\n",
    "    True\n",
    "    >>> for line in c.emit().split(\"\\\\n\"):\n",
    "    ...     print(line)\n",
    "    7 36\n",
    "    2 4 4\n",
    "    1 1\n",
    "    2 1 0 1 15 AND\n",
    "    2 1 2 3 16 AND\n",
    "    2 1 15 16 8 AND\n",
    "    2 1 4 5 22 AND\n",
    "    2 1 6 7 23 AND\n",
    "    2 1 22 23 9 AND\n",
    "    2 1 8 9 35 AND\n",
    "\n",
    "    We could just add a '1 1 35 36 LID' line, and increment '8 16', but the\n",
    "    `force_id_outputs` is perhaps not as lazy as it could be and performs a\n",
    "    full `bfc`->`circuit_`->`bfc` conversion to get the identity gates,\n",
    "    hence the wire renumbering.\n",
    "    >>> for line in c.emit(force_id_outputs=True).split(\"\\\\n\"):\n",
    "    ...     print(line)\n",
    "    8 16\n",
    "    2 4 4\n",
    "    1 1\n",
    "    2 1 0 1 8 AND\n",
    "    2 1 2 3 9 AND\n",
    "    2 1 8 9 10 AND\n",
    "    2 1 4 5 11 AND\n",
    "    2 1 6 7 12 AND\n",
    "    2 1 11 12 13 AND\n",
    "    2 1 10 13 14 AND\n",
    "    1 1 14 15 LID\n",
    "\n",
    "    A circuit can also be consructed using an instance of the\n",
    "    :obj:`~circuit.circuit.circuit` class defined in the\n",
    "    `circuit <https://pypi.org/project/circuit/>`_ library (see the\n",
    "    documentation for the :obj:`circuit.circuit` method defined as part of\n",
    "    this class).\n",
    "\n",
    "    Common properties of the circuit can be found in the attributes of\n",
    "    an instance.\n",
    "\n",
    "    >>> c.gate_count\n",
    "    7\n",
    "    >>> c.wire_count\n",
    "    36\n",
    "    >>> c.value_in_count\n",
    "    2\n",
    "    >>> c.value_in_length\n",
    "    [4, 4]\n",
    "    >>> c.value_out_count\n",
    "    1\n",
    "    >>> c.wire_in_count\n",
    "    8\n",
    "    >>> c.wire_in_index\n",
    "    [0, 1, 2, 3, 4, 5, 6, 7]\n",
    "    >>> c.wire_out_count\n",
    "    1\n",
    "    >>> c.wire_out_index\n",
    "    [35]\n",
    "\n",
    "    The individual gates are stored within a list consisting of zero or\n",
    "    more instances of the :obj:`gate` class.\n",
    "\n",
    "    >>> (c.gate[0].wire_in_index, c.gate[0].wire_out_index)\n",
    "    ([0, 1], [15])\n",
    "    >>> (c.gate[1].wire_in_index, c.gate[1].wire_out_index)\n",
    "    ([2, 3], [16])\n",
    "    >>> (c.gate[2].wire_in_index, c.gate[2].wire_out_index)\n",
    "    ([15, 16], [8])\n",
    "    >>> (c.gate[3].wire_in_index, c.gate[3].wire_out_index)\n",
    "    ([4, 5], [22])\n",
    "    >>> (c.gate[4].wire_in_index, c.gate[4].wire_out_index)\n",
    "    ([6, 7], [23])\n",
    "    >>> (c.gate[5].wire_in_index, c.gate[5].wire_out_index)\n",
    "    ([22, 23], [9])\n",
    "    >>> (c.gate[6].wire_in_index, c.gate[6].wire_out_index)\n",
    "    ([8, 9], [35])\n",
    "    >>> {c.gate[i].operation for i in range(7)} == {op.and_}\n",
    "    True\n",
    "\n",
    "    A circuit can also be evaluated an on a sequence of input bit vectors\n",
    "    using the :obj:`bfcl.evaluate` method.\n",
    "\n",
    "    >>> from itertools import product\n",
    "    >>> inputs = list(product(*([[0, 1]]*4)))\n",
    "    >>> pairs = product(inputs, inputs)\n",
    "    >>> outputs = ([0]*255) + [1]\n",
    "    >>> [c.evaluate(p)[0][0] for p in pairs] == outputs\n",
    "    True\n",
    "    \"\"\"\n",
    "    def __init__(self: bfc, raw=None):\n",
    "        \"\"\"Initialize a bfc data structure instance.\"\"\"\n",
    "        self.gate_count = 0\n",
    "        self.wire_count = 0\n",
    "        self.value_in_count = 0\n",
    "        self.value_in_length = []\n",
    "        self.value_out_count = 0\n",
    "        self.value_out_length = []\n",
    "\n",
    "        # The four fields below are technically redundant but included\n",
    "        # to support cleaner algorithm implementations.\n",
    "        self.wire_in_count = 0\n",
    "        self.wire_in_index = []\n",
    "        self.wire_out_count = 0\n",
    "        self.wire_out_index = []\n",
    "\n",
    "        self.gate = []\n",
    "\n",
    "        # Convert a string or circuit input.\n",
    "        if isinstance(raw, str):\n",
    "            self.parse(raw)\n",
    "        elif isinstance(raw, circuit):\n",
    "            self.circuit(raw)\n",
    "\n",
    "    def circuit(self: bfc, c: circuit=None) -> Union[Type[None], circuit]:\n",
    "        \"\"\"\n",
    "        Populate this Bristol Fashion circuit instance using an instance of the\n",
    "        :obj:`~circuit.circuit.circuit` class defined in the\n",
    "        `circuit <https://pypi.org/project/circuit/>`_ library.\n",
    "\n",
    "        >>> c_ = circuit_.circuit()\n",
    "        >>> c_.count()\n",
    "        0\n",
    "        >>> g0 = c_.gate(op.id_, is_input=True)\n",
    "        >>> g1 = c_.gate(op.id_, is_input=True)\n",
    "        >>> g2 = c_.gate(op.and_, [g0, g1])\n",
    "        >>> g3 = c_.gate(op.id_, [g2], is_output=True)\n",
    "        >>> c_.count()\n",
    "        4\n",
    "        >>> c = bfc(c_)\n",
    "        >>> c.emit().split(\"\\\\n\")\n",
    "        ['2 4', '1 2', '1 1', '2 1 0 1 2 AND', '1 1 2 3 LID']\n",
    "        >>> c_reparsed = bfc(bfc(c_).circuit())\n",
    "        >>> c_reparsed.emit().split(\"\\\\n\")\n",
    "        ['2 4', '1 2', '1 1', '2 1 0 1 2 AND', '1 1 2 3 LID']\n",
    "        \"\"\"\n",
    "        if c:\n",
    "            sig = c.signature\n",
    "            self.gate_count =\\\n",
    "                c.count(lambda g: not (len(g.inputs) == 0 and len(g.outputs) > 0))\n",
    "            self.wire_count = len(c.gates)\n",
    "            self.value_in_count =\\\n",
    "                1 if sig.input_format is None else len(sig.input_format)\n",
    "            self.value_in_length =\\\n",
    "                [self.wire_count - self.gate_count]\\\n",
    "                if sig.input_format is None else\\\n",
    "                sig.input_format\n",
    "            self.value_out_count =\\\n",
    "                1 if sig.output_format is None else len(sig.output_format)\n",
    "            self.value_out_length =\\\n",
    "                [c.count(lambda g: len(g.outputs) == 0)]\\\n",
    "                if sig.output_format is None else\\\n",
    "                sig.output_format\n",
    "\n",
    "            self.wire_in_count = self.wire_count - self.gate_count\n",
    "            self.wire_in_index = list(range(0, self.wire_in_count))\n",
    "            self.wire_out_count = c.count(lambda g: len(g.outputs) == 0)\n",
    "            self.wire_out_index =\\\n",
    "                list(range(self.wire_count - self.wire_out_count, self.wire_count))\n",
    "\n",
    "            self.gate = []\n",
    "            for g in c.gates:\n",
    "                if len(g.inputs) > 0:\n",
    "                    self.gate.append(gate(\n",
    "                        len(g.inputs), 1,\n",
    "                        [ig.index for ig in g.inputs], [g.index],\n",
    "                        operation(g.operation)\n",
    "                    ))\n",
    "            return None\n",
    "        #else if (c == None):\n",
    "        input_format = self.value_in_length\n",
    "        output_format = self.value_out_length\n",
    "        c = circuit(signature(input_format, output_format))\n",
    "\n",
    "        self_gate = list(self.gate)\n",
    "        # Don't mutate the real gate list (only protects from the `.extend` call in the `if` block).\n",
    "\n",
    "        if not (\n",
    "                all(self.gate[gate_index].operation == circuit.op.id_ for gate_index in\n",
    "                    range(self.gate_count - self.wire_out_count, self.gate_count))\n",
    "                and self.wire_out_index == list(\n",
    "                    range(self.wire_count - self.wire_out_count, self.wire_count)\n",
    "                )\n",
    "        ):\n",
    "            # raise NotImplementedError(\n",
    "            #     \"The bfcl library only supports converting to a circuit \"\n",
    "            #     \"object for circuits with in-order identity-gate outputs.\"\n",
    "            # )\n",
    "            # Update circuit to new output format.\n",
    "            self_gate.extend(\n",
    "                [\n",
    "                    gate(\n",
    "                        1,\n",
    "                        1,\n",
    "                        [i - self.wire_out_count],\n",
    "                        [i],\n",
    "                        operation(circuit.op.id_)  # operation.parse('LID')\n",
    "                    )\n",
    "                    for i in range(self.wire_count, self.wire_count + self.wire_out_count)\n",
    "                ]\n",
    "            )\n",
    "\n",
    "        intermediate_gates = self_gate[:]\n",
    "        output_gates = self_gate[-self.wire_out_count:]\n",
    "        wires = {}\n",
    "        for wire_index in range(self.wire_in_count):#input_gates:\n",
    "            wires[wire_index] = c.gate(\n",
    "                circuit.op.id_,\n",
    "                is_input=True\n",
    "            )\n",
    "        for g in intermediate_gates:\n",
    "            assert len(g.wire_in_index) > 0\n",
    "            assert len(g.wire_out_index) > 0\n",
    "            _g = c.gate(\n",
    "                g.operation,\n",
    "                list(map(lambda i : wires[i], g.wire_in_index))\n",
    "            )\n",
    "            for wire_out_index in g.wire_out_index:\n",
    "                assert wire_out_index > self.wire_in_count - 1  # Ord. gate inputs to circuit inputs\n",
    "                wires[wire_out_index] = _g\n",
    "        for g in output_gates:\n",
    "            assert len(g.wire_in_index) > 0\n",
    "            c.gate(\n",
    "                g.operation,  # This should always be `circuit_.op.id_`.\n",
    "                list(map(lambda i : wires[i], g.wire_in_index)),\n",
    "                is_output=True\n",
    "            )\n",
    "        c.prune_and_topological_sort_stable()  # really only need to prune chained identity gates\n",
    "\n",
    "        return c\n",
    "\n",
    "    def parse(self: circuit, raw: str):\n",
    "        \"\"\"\n",
    "        Parse a string representation of a circuit that conforms to the Bristol\n",
    "        Fashion syntax.\n",
    "\n",
    "        >>> s = ['7 36', '2 4 4', '1 1']\n",
    "        >>> s.extend(['2 1 0 1 15 AND', '2 1 2 3 16 AND'])\n",
    "        >>> s.extend(['2 1 15 16 8 AND', '2 1 4 5 22 AND'])\n",
    "        >>> s.extend(['2 1 6 7 23 AND', '2 1 22 23 9 AND'])\n",
    "        >>> s.extend(['2 1 8 9 35 AND'])\n",
    "        >>> s = \"\\\\n\".join(s)\n",
    "        >>> c = bfc()\n",
    "        >>> c.parse(s)\n",
    "        >>> for line in c.emit().split(\"\\\\n\"):\n",
    "        ...     print(line)\n",
    "        7 36\n",
    "        2 4 4\n",
    "        1 1\n",
    "        2 1 0 1 15 AND\n",
    "        2 1 2 3 16 AND\n",
    "        2 1 15 16 8 AND\n",
    "        2 1 4 5 22 AND\n",
    "        2 1 6 7 23 AND\n",
    "        2 1 22 23 9 AND\n",
    "        2 1 8 9 35 AND\n",
    "        \"\"\"\n",
    "        rows = [\n",
    "            [tok.strip() for tok in r.strip().split(\" \")]\n",
    "            for r in raw.split(\"\\n\") if r.strip() != \"\"\n",
    "        ]\n",
    "\n",
    "        self.gate_count = int(rows[0][0])\n",
    "        self.wire_count = int(rows[0][1])\n",
    "\n",
    "        # Determine total number of input and output wires.\n",
    "        self.wire_in_count = 0\n",
    "        for i in range(1, len(rows[1])):\n",
    "            length = int(rows[1][i])\n",
    "            self.value_in_count += 1\n",
    "            self.value_in_length.append(length)\n",
    "            self.wire_in_count += length\n",
    "\n",
    "        self.wire_out_count = 0\n",
    "        for i in range(1, len(rows[2])):\n",
    "            length = int(rows[2][i])\n",
    "            self.value_out_count += 1\n",
    "            self.value_out_length.append(length)\n",
    "            self.wire_out_count += length\n",
    "\n",
    "        # Collect input/output wire indices for easier processing.\n",
    "        self.wire_in_index = list(range(0, self.wire_in_count))\n",
    "        self.wire_out_index =\\\n",
    "            list(range(self.wire_count-self.wire_out_count, self.wire_count))\n",
    "\n",
    "        # Parse the individual gates.\n",
    "        self.gate = [gate.parse(row) for row in rows[3:self.gate_count+3]]\n",
    "\n",
    "    def emit(self: circuit, force_id_outputs=False, progress=lambda _: _) -> str:\n",
    "        \"\"\"\n",
    "        Emit a string representation of a Bristol Fashion circuit definition.\n",
    "\n",
    "        In the example below, a circuit object is first constructed using the\n",
    "        `circuit <https://pypi.org/project/circuit/>`_ library.\n",
    "\n",
    "        >>> c_ = circuit_.circuit()\n",
    "        >>> c_.count()\n",
    "        0\n",
    "        >>> g0 = c_.gate(op.id_, is_input=True)\n",
    "        >>> g1 = c_.gate(op.id_, is_input=True)\n",
    "        >>> g2 = c_.gate(op.and_, [g0, g1])\n",
    "        >>> g3 = c_.gate(op.id_, [g2], is_output=True)\n",
    "\n",
    "        The ``c_`` object above can be converted into an instance of the\n",
    "        class :obj:`circuit`.\n",
    "\n",
    "        >>> c = bfc(c_)\n",
    "\n",
    "        This method can be used to emit a string representation of an object,\n",
    "        where the string conforms to the Bristol Fashion syntax.\n",
    "\n",
    "        >>> c.emit().split(\"\\\\n\")\n",
    "        ['2 4', '1 2', '1 1', '2 1 0 1 2 AND', '1 1 2 3 LID']\n",
    "\n",
    "        >>> c.emit(True).split(\"\\\\n\")\n",
    "        ['2 4', '1 2', '1 1', '2 1 0 1 2 AND', '1 1 2 3 LID']\n",
    "        \"\"\"\n",
    "        _self = bfc(self.circuit()) if force_id_outputs else self  # temporarily process if flag set\n",
    "        lines = [\n",
    "            [str(_self.gate_count), str(_self.wire_count)],\n",
    "            [str(_self.value_in_count)] + list(map(str, _self.value_in_length)),\n",
    "            [str(_self.value_out_count)] + list(map(str, _self.value_out_length))\n",
    "        ]\n",
    "        lines.extend([[g.emit()] for g in progress(_self.gate)])\n",
    "        return \"\\n\".join(\" \".join(line) for line in lines)\n",
    "\n",
    "    def evaluate(\n",
    "            self: circuit,\n",
    "            inputs: Sequence[Sequence[int]]\n",
    "        ) -> Sequence[Sequence[int]]:\n",
    "        \"\"\"\n",
    "        Evaluate a circuit on a sequence of input bit vectors.\n",
    "\n",
    "        >>> s = ['7 36', '2 4 4', '1 1']\n",
    "        >>> s.extend(['2 1 0 1 15 AND', '2 1 2 3 16 AND'])\n",
    "        >>> s.extend(['2 1 15 16 8 AND', '2 1 4 5 22 AND'])\n",
    "        >>> s.extend(['2 1 6 7 23 AND', '2 1 22 23 9 AND'])\n",
    "        >>> s.extend(['2 1 8 9 35 AND'])\n",
    "        >>> c = bfc(\"\\\\n\".join(s))\n",
    "        >>> c.evaluate([[1, 0, 1, 1], [1, 1, 1, 0]])\n",
    "        [[0]]\n",
    "        >>> c.evaluate([[1, 1, 1, 1], [1, 1, 1, 1]])\n",
    "        [[1]]\n",
    "\n",
    "        The example below confirms that the circuit ``c`` defined above has correct\n",
    "        behavior when evaluated on all compatible inputs (*i.e.*, inputs consisting\n",
    "        of a pair of 4-bit vectors).\n",
    "\n",
    "        >>> from itertools import product\n",
    "        >>> inputs = list(product(*([[0, 1]]*4)))\n",
    "        >>> pairs = product(inputs, inputs)\n",
    "        >>> outputs = ([0]*255) + [1]\n",
    "        >>> [c.evaluate(p)[0][0] for p in pairs] == outputs\n",
    "        True\n",
    "        \"\"\"\n",
    "        # It is assumed that the number of input wires in the circuit matches\n",
    "        # the total number of bits across all inputs in the inputs vector.\n",
    "        inputs = [b for bs in inputs for b in bs]\n",
    "        wire = inputs + [0]*(self.wire_count-len(inputs))\n",
    "\n",
    "        # This total is useful in case output wire indices are absent.\n",
    "        wire_in_count = len(inputs)\n",
    "\n",
    "        # Evaluate the gates.\n",
    "        for (ig, g) in enumerate(self.gate):\n",
    "            # If no output wire index is present, use the gate count as the index.\n",
    "            wire_out_index =\\\n",
    "                g.wire_out_index[0] if hasattr(g, 'wire_out_index') else\\\n",
    "                wire_in_count + ig\n",
    "\n",
    "            # Compute the operation and store the result.\n",
    "            wire[wire_out_index] =\\\n",
    "                g.operation(*[wire[i] for i in g.wire_in_index])\n",
    "\n",
    "        # Format and return the output bit vectors.\n",
    "        return list(parts(\n",
    "            wire[-self.wire_out_count:],\n",
    "            length=self.value_out_length\n",
    "        ))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}