05-embedded-dsl.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br><br><br><br><br>\n",
    "\n",
    "# Embedded DSLs: using an existing language's syntax\n",
    "\n",
    "<br><br><br><br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do we need a new language?\n",
    "\n",
    "Or more specifically, do we need a new syntax?\n",
    "\n",
    "An **embedded DSL** is a domain-specific language that is implemented in another language. The difference between an embedded DSL and an ordinary library is subjective.\n",
    "\n",
    "For example:\n",
    "\n",
    "   * [Numpy](https://docs.scipy.org/doc/numpy/reference/) implements array programming idioms in Python, which had been language features in MATLAB, R, and APL.\n",
    "   * My [awkward-array](https://github.com/scikit-hep/awkward-array) is an embedded DSL for physics: `(muons[:, 0] + muons[:, 1]).mass` → Z peak.\n",
    "   * [Akka](https://akka.io/) implements the actor model of concurrency, which had been a language feature in Erlang.\n",
    "   * [Boost.Proto](https://www.boost.org/doc/libs/1_58_0/doc/html/proto.html) provides tools to build DSLs in C++.\n",
    "   * [Scala's syntax rules](https://scalac.io/encog-dsl-scala-part1) are flexible enough for some radical DSLs (next pages).\n",
    "\n",
    "Libraries are more on the \"embedded DSL\" end of the spectrum if they consist of shallow functions that only do interesting things when combined, like the constructs of a programming language."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Scala, a class's methods can be accessed through a dot `.` (like most languages) or a space ` `. Methods taking a single argument need not have parentheses `(` `)`, and they can be named with unicode characters.\n",
    "\n",
    "The following are equivalent:\n",
    "\n",
    "```scala\n",
    "a.cross(b)      // a and b are ThreeVectors, which has a cross method\n",
    "a cross b       // the dot and parentheses may be omitted\n",
    "a × b           // cross can also be named ×\n",
    "```\n",
    "\n",
    "Scala also lets functions decide whether they want to be eagerly or lazily evaluated, and has Lisp-like macros. This leads to some extreme DSLs, like [ScalaTest](http://www.scalatest.org/):\n",
    "\n",
    "```scala\n",
    "x should not equal 1\n",
    "\n",
    "List(\"one\", \"two\", \"three\") should contain (\"two\")\n",
    "\n",
    "an [IndexOutOfBoundsException] should be thrownBy string.charAt(-1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Chisel](https://chisel.eecs.berkeley.edu/) library specifies circuits for FPGAs several times more succinctly than Verilog. This is a vending machine:\n",
    "\n",
    "```scala\n",
    "class VendingMachine extends Component {\n",
    "  val io = new Bundle {\n",
    "    val nickel = Bool(INPUT)\n",
    "    val dime   = Bool(INPUT)\n",
    "    val ready  = Bool(OUTPUT)\n",
    "  }\n",
    "  val s_idle :: s_5 :: s_10 :: s_15 :: s_ok :: Nil = Enum(5){ UFIx() }\n",
    "  val state = Reg(resetVal = s_idle)\n",
    "  switch (state) {\n",
    "    is (s_idle) { when (io.nickel) { state := s_5 }  when (io.dime) { state := s_10 } }\n",
    "    is (s_5)    { when (io.nickel) { state := s_10 } when (io.dime) { state := s_15 } }\n",
    "    is (s_10)   { when (io.nickel) { state := s_15 } when (io.dime) { state := s_ok } }\n",
    "    is (s_15)   { when (io.nickel) { state := s_ok } when (io.dime) { state := s_ok } }\n",
    "    is (s_ok)   { state := s_idle }\n",
    "  }\n",
    "  io.ready := (state === s_ok)\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "But most physicists use Python for high-level analysis.\n",
    "\n",
    "Python's syntax is not nearly as flexible as Scala's, nor does it give control over eager/lazy evaluation like Scala and C# (unless you ask the user to always pass functions as arguments!), so options for embedded DSLs in Python are limited.\n",
    "\n",
    "<br>\n",
    "\n",
    "In all the demos I've shown so far, we've defined new grammars.\n",
    "\n",
    "   * This has the _advantage_ of complete freedom in syntax and interpretation.\n",
    "   * This has the _disadvantage_ that the language must always live in quoted strings or separate files.\n",
    "\n",
    "It's okay for small snippets of the new language, like regular expressions or SQL queries, but for longer programs, the user will be limited by their favorite editor not interpreting the language for syntax highlighting, auto-indentation, tab-completion, integrated documentation...\n",
    "\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'|\\x00d\\x01\\x13\\x00|\\x01d\\x01\\x13\\x00\\x17\\x00S\\x00'\n"
     ]
    }
   ],
   "source": [
    "# Best of both? Code in Python FUNCTIONS are syntax-checked but otherwise unevaluated.\n",
    "\n",
    "def function(x, y):\n",
    "    return x**2 + y**2\n",
    "\n",
    "# The source code has been compiled for Python's virtual machine, which is another language,\n",
    "# but that language can be parsed (not by humans).\n",
    "\n",
    "print(function.__code__.co_code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "stmts\n",
       "    sstmt\n",
       "        stmt\n",
       "            return (2)\n",
       "                 0. ret_expr\n",
       "                    expr\n",
       "                        binary_expr (3)\n",
       "                             0. expr\n",
       "                                binary_expr (3)\n",
       "                                     0. expr\n",
       "                                        L.  10       0  LOAD_FAST                'x'\n",
       "                                     1. expr\n",
       "                                                     2  LOAD_CONST            2  2\n",
       "                                     2. binary_op\n",
       "                                                     4  BINARY_POWER     \n",
       "                             1. expr\n",
       "                                binary_expr (3)\n",
       "                                     0. expr\n",
       "                                                     6  LOAD_FAST                'y'\n",
       "                                     1. expr\n",
       "                                                     8  LOAD_CONST            2  2\n",
       "                                     2. binary_op\n",
       "                                                    10  BINARY_POWER     \n",
       "                             2. binary_op\n",
       "                                            12  BINARY_ADD       \n",
       "                 1.             14  RETURN_VALUE     "
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys, uncompyle6.parser, uncompyle6.scanner\n",
    "\n",
    "def parse(function):\n",
    "    code = function.__code__\n",
    "    scanner = uncompyle6.scanner.get_scanner(float(sys.version[0:3]))\n",
    "    parser = uncompyle6.parser.get_python_parser(float(sys.version[0:3]), compile_mode=\"exec\")\n",
    "    tokens, customize = scanner.ingest(code)\n",
    "    return uncompyle6.parser.parse(parser, tokens, customize)\n",
    "\n",
    "parse(lambda x, y: x**2 + y**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Make our own AST, not that parsing tree or Python's own AST. We want to control the interpretation.\n",
    "\n",
    "class AST:\n",
    "    _fields = ()\n",
    "    def __init__(self, *args):\n",
    "        for n, x in zip(self._fields, args):\n",
    "            setattr(self, n, x)\n",
    "\n",
    "class Literal(AST):\n",
    "    _fields = (\"value\",)\n",
    "    def __str__(self): return str(self.value)\n",
    "\n",
    "class Symbol(AST):\n",
    "    _fields = (\"symbol\",)\n",
    "    def __str__(self): return self.symbol\n",
    "\n",
    "class Call(AST):\n",
    "    _fields = (\"function\", \"arguments\")\n",
    "    def __str__(self):\n",
    "        return \"{0}({1})\".format(str(self.function), \", \".join(str(x) for x in self.arguments))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "add(pow(x, 2), pow(y, 2))\n"
     ]
    }
   ],
   "source": [
    "# Now we just need a toaster for uncompyle6's parsing tree.\n",
    "\n",
    "def toast(ptnode):\n",
    "    if ptnode.kind == \"binary_expr\":\n",
    "        return Call(toast(ptnode[2]), [toast(x) for x in ptnode[:2]])\n",
    "    elif ptnode.kind == \"BINARY_ADD\":\n",
    "        return Symbol(\"add\")\n",
    "    elif ptnode.kind == \"BINARY_POWER\":\n",
    "        return Symbol(\"pow\")\n",
    "    elif ptnode.kind == \"LOAD_FAST\":\n",
    "        return Symbol(ptnode.pattr)\n",
    "    elif ptnode.kind == \"LOAD_CONST\":\n",
    "        return Literal(ptnode.pattr)\n",
    "    else:\n",
    "        # a lot of nodes are purely structural\n",
    "        return toast(ptnode[0])\n",
    "\n",
    "# It's incomplete, but it covers enough for our example.\n",
    "print(toast(parse(lambda x, y: x**2 + y**2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Python's grammar](https://docs.python.org/3/reference/grammar.html) is not very large, not hard to fully translate—at least the expressions (86 rules, 36 are for expressions):\n",
    "\n",
    "```\n",
    "test:           or_test ['if' or_test 'else' test] | lambdef\n",
    "test_nocond:    or_test | lambdef_nocond\n",
    "lambdef:        'lambda' [varargslist] ':' test\n",
    "lambdef_nocond: 'lambda' [varargslist] ':' test_nocond\n",
    "or_test:        and_test ('or' and_test)*\n",
    "and_test:       not_test ('and' not_test)*\n",
    "not_test:       'not' not_test | comparison\n",
    "comparison:     expr (comp_op expr)*\n",
    "comp_op:        '<'|'>'|'=='|'>='|'<='|'<>'|'!='|'in'|'not' 'in'|'is'|'is' 'not'\n",
    "star_expr:      '*' expr\n",
    "expr:           xor_expr ('|' xor_expr)*\n",
    "xor_expr:       and_expr ('^' and_expr)*\n",
    "and_expr:       shift_expr ('&' shift_expr)*\n",
    "shift_expr:     arith_expr (('<<'|'>>') arith_expr)*\n",
    "arith_expr:     term (('+'|'-') term)*\n",
    "term:           factor (('*'|'@'|'/'|'%'|'//') factor)*\n",
    "factor:         ('+'|'-'|'~') factor | power\n",
    "power:          atom_expr ['**' factor]\n",
    "atom_expr:      ['await'] atom trailer*\n",
    "atom:           ('(' [yield_expr|testlist_comp] ')' | '[' [testlist_comp] ']' |\n",
    "                '{' [dictorsetmaker] '}' | NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False')\n",
    "testlist_comp:  (test|star_expr) ( comp_for | (',' (test|star_expr))* [','] )\n",
    "trailer:        '(' [arglist] ')' | '[' subscriptlist ']' | '.' NAME\n",
    "subscriptlist:  subscript (',' subscript)* [',']\n",
    "subscript:      test | [test] ':' [test] [sliceop]\n",
    "sliceop:        ':' [test]\n",
    "exprlist:       (expr|star_expr) (',' (expr|star_expr))* [',']\n",
    "testlist:       test (',' test)* [',']\n",
    "dictorsetmaker: (((test ':' test | '**' expr) (comp_for | (',' (test ':' test | '**' expr))* [','])) |\n",
    "                ((test | star_expr) (comp_for | (',' (test | star_expr))* [','])))\n",
    "arglist:        argument (',' argument)*  [',']\n",
    "argument:       ( test [comp_for] | test '=' test | '**' test | '*' test )\n",
    "comp_iter:      comp_for | comp_if\n",
    "sync_comp_for:  'for' exprlist 'in' or_test [comp_iter]\n",
    "comp_for:       ['async'] sync_comp_for\n",
    "comp_if:        'if' test_nocond [comp_iter]\n",
    "yield_expr:     'yield' [yield_arg]\n",
    "yield_arg:      'from' test | testlist\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "add(pow(x, 2), pow(y, 2))\n"
     ]
    }
   ],
   "source": [
    "# And the whole apparatus can be wrapped up in a Python decorator.\n",
    "# (Numba uses the same mechanism to specify that a function is to be compiled.)\n",
    "\n",
    "def quote(function):                   # like Lisp's \"quote\"\n",
    "    return toast(parse(function))\n",
    "\n",
    "@quote\n",
    "def sum_quadrature(x, y):\n",
    "    return x**2 + y**2\n",
    "\n",
    "print(sum_quadrature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the ability to turn any Python function into an AST, we can add\n",
    "\n",
    "   * lazy evaluation or a declarative interpretation;\n",
    "   * type-checking, possibly with physics-motivated features, like refinement types;\n",
    "   * compilation through C++ or directly into bytecode (though Numba does that);\n",
    "   * AST transformations, such as derivatives (Calculus);\n",
    "   * AST rewriting, such as algebraic simplifications;\n",
    "   * ...\n",
    "\n",
    "New syntax vs Python syntax is a _separate question_ from the above features. It's also possible to have two syntaxes for the same language (different parsing steps produce the same ASTs).\n",
    "\n",
    "Using Python as a syntax limits us to Python syntax rules and Pythonic expectations (users would be upset if we changed the _meaning_ of the operators), but it provides a better editing experience.\n",
    "\n",
    "I started thinking along these lines in a project called [rejig](https://github.com/diana-hep/rejig)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}