AnatomyOfJuliaPt1draft.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Anatomy of Julia: Part 1: Multiple Dispatch (Draft)\n",
    "\n",
    "Prior to writing this, I had a number of questions I wanted to address\n",
    "\n",
    "* What disadvantages are there for using multiple dispatch as opposed to single-dispatch (like most OO languages), and are the trade-offs worth it?\n",
    "* Why multiple dispatch as opposed to typeclasses?\n",
    "* Whether subtyping is expressive enough to have multiple classes inhabiting a type?\n",
    "\n",
    "Most of these were answered Julia PhD paper, sections 3.2, 3.3, and 3.5 respectively.\n",
    "\n",
    "<!--- In programming languages, one often has to come across having to resolve a namespace, that is, looking up what entitity an identifier is bound to.--->\n",
    "\n",
    "### Method or function?\n",
    "\n",
    "The language becomes a little bit unclear with this as *method* usually implies that it applies to some object or class, so multiple dispatch is also called multimethods as a method is dispatched not only on one argument, but multiple arguments. We clarify that in Julia functions inhabit namespace, and that methods belong to functions. E.G.  \n",
    "\n",
    "```\n",
    "julia> methods(+)\n",
    "# 171 methods for generic function \"+\":\n",
    "...\n",
    "```\n",
    "\n",
    "In this case \"+\" would be the function, which would dispatch over many methods based on the arguments.\n",
    "\n",
    "<!--- TODO: Concrete example porting from Python to Julia? Discussion of Subtyping vs Subclasses? --->\n",
    "\n",
    "## The Expression problem\n",
    "\n",
    "The expression problem [as summed up](http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt)\n",
    "\n",
    "\n",
    "> The Expression Problem is a new name for an old problem.  The goal is\n",
    "to define a datatype by cases, where one can add new cases to the\n",
    "datatype and new functions over the datatype, without recompiling\n",
    "existing code, and while retaining static type safety (e.g., no\n",
    "casts)...\n",
    "\n",
    "> Whether a language can solve the Expression Problem is a salient\n",
    "indicator of its capacity for expression.  One can think of cases as\n",
    "rows and functions as columns in a table.  In a functional language,\n",
    "the rows are fixed (cases in a datatype declaration) but it is easy to\n",
    "add new columns (functions).  In an object-oriented language, the\n",
    "columns are fixed (methods in a class declaration) but it is easy to\n",
    "add new rows (subclasses).  We want to make it easy to add either rows\n",
    "or columns.\n",
    "\n",
    "In the Julia PhD paper, section 3.3, there is a discussion on how implementing multimethods comes out of the need to simplify methods on multiple cases. At the end of 3.3.1, there is discussion of \"external dispatch\", the syntax of which originally motivated this article. The essence of this idea is that for methods to be defined outside of a respective class. This is more reflective of the semantics of the language, as the first argument of a function (```self``` in many Object-oriented language no longer has any special significance).\n",
    "\n",
    "Note how the structure of the code changes through section 3.3 (Reproduced below). The first implementation is a chain of conditionals, but as we add classes, the code is organized around the object which contains methods, but as we add external dispatch, the code is organized around the function, which has multiple methods.\n",
    "\n",
    "With the focus on the functions, one could argue that the syntax is functional as opposed to object-oriented. However, these distinctions tend to be a bit fuzzy.\n",
    "\n",
    "<!--- Haskell, by comparison, favors type safety in its approach, with typeclasses over subtype. This approach also brings more logic in the type system, and further decouples supertype from subtype, but comes at the cost of invoking the expression problem again. --->\n",
    "\n",
    "<!--- Julia uses subtyping to implement type polymorphism.--->\n",
    "\n",
    "## Disadvantages of Multiple Dispatch\n",
    "\n",
    "Multiple dispatch induces additional overhead, as it needs to dispatch on every argument as well as the structure of a composite types, however, this does not affect compiled code. (Table 3.1 in Abstraction in Technical computing). If one wishes to include predicate dispatch, you have even more overhead. \n",
    "\n",
    "The Class-based dispatch syntax Object.method(argument) naturally follows the ordering of subject-verb-object in the English language, so this lowers a conceptual barrier to entry for english-speakers. Another advantage is tab-completion in an IDE or shell session, one quickly figure out everything an object contains simply by typing \"Object.\" and then the *tab* key, however, this is not to say that Julia could not implement an IDE which facilitates developement using ```methodswith```.\n",
    "\n",
    "## External resources\n",
    "\n",
    "* http://www.cis.upenn.edu/~bcpierce/sf/current/Sub.html\n",
    "* https://groups.google.com/d/topic/julia-dev/V1HJcHQz4JE/discussion\n",
    "* https://en.wikipedia.org/wiki/Python_syntax_and_semantics\n",
    "* https://existentialtype.wordpress.com/2011/03/19/dynamic-languages-are-static-languages/\n",
    "* http://c2.com/cgi/wiki?MultiMethods\n",
    "* http://docs.julialang.org/en/release-0.3/manual/noteworthy-differences/?highlight=dispatch#noteworthy-differences-from-python\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!--- Something that would look like this in Python\n",
    "\n",
    "class Foo:\n",
    "   def __init__(self, a=123):\n",
    "       self.a = a\n",
    "       \n",
    "would look like this in julia\n",
    "\n",
    "\n",
    "       --->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### A hierarchy of dispatch\n",
    "\n",
    "*The grey text indicates that this section was taken from 3.3.2 of Jeff Bezanson's [Abstraction in Technical Computing (pdf)](https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf) PhD Thesis*\n",
    "\n",
    "<div style=\"color: #5A6D6A;\">\n",
    "It is possible to illustrate a hierarchy of such mechanisms. As an\n",
    "example, consider a simple simulation, and how it can be written under a\n",
    "series of increasingly powerful paradigms. First, written-out imperative\n",
    "code:\n",
    "\n",
    "    while running\n",
    "        for a in animals\n",
    "            b = nearby_animal(a)\n",
    "            if a isa Rabbit\n",
    "                if b isa Wolf then run(a)\n",
    "                if b isa Rabbit then mate(a,b)\n",
    "            else if a isa Wolf\n",
    "                if b isa Rabbit then eat(a,b)\n",
    "                if b isa Wolf then follow(a,b)\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "\n",
    "We can see how this would get tedious as we add more kinds of animals\n",
    "and more behaviors. Another problem is that the animal behavior is\n",
    "implemented directly inside the control loop, so it is hard to see what\n",
    "parts are simulation control logic and what parts are animal behavior.\n",
    "Adding a simple object system leads to a nicer implementation [^2]:\n",
    "\n",
    "    class Rabbit\n",
    "        method encounter(b)\n",
    "            if b isa Wolf then run()\n",
    "            if b isa Rabbit then mate(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "    class Wolf\n",
    "        method encounter(b)\n",
    "            if b isa Rabbit then eat(b)\n",
    "            if b isa Wolf then follow(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "    while running\n",
    "        for a in animals\n",
    "            b = nearby_animal(a)\n",
    "            a.encounter(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "Here all of the simulation’s animal behavior has been compressed into a\n",
    "single program point: `a.encounter(b)` leads to all of the behavior by\n",
    "selecting an implementation based on the first argument, `a`. This kind\n",
    "of criterion is essentially indexed lookup; we can imagine that `a`\n",
    "could be an integer index into a table of operations.\n",
    "\n",
    "The next enhancement to “selection criteria” adds a hierarchy of\n",
    "behaviors, to provide further opportunities to avoid repetition. Here\n",
    "`A<:B` is used to declare a subclass relationship; it says that an `A`\n",
    "is a kind of `B`:\n",
    "\n",
    "    abstract class Animal\n",
    "        method nearby()\n",
    "            # search within some radius\n",
    "        end\n",
    "    end\n",
    "\n",
    "    class Rabbit <: Animal\n",
    "        method encounter(b::Animal)\n",
    "            if b isa Wolf then run()\n",
    "            if b isa Rabbit then mate(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "    class Wolf <: Animal\n",
    "        method encounter(b::Animal)\n",
    "            if b isa Rabbit then eat(b)\n",
    "            if b isa Wolf then follow(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "    while running\n",
    "        for a in animals\n",
    "            b = a.nearby()\n",
    "            a.encounter(b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "We are still essentially doing table lookup, but the tables have more\n",
    "structure: every `Animal` has the `nearby` method, and can inherit a\n",
    "general purpose implementation.\n",
    "\n",
    "This brings us roughly to the level of most popular object-oriented\n",
    "languages. But still more can be done. Notice that in the first\n",
    "transformation we replaced one level of `if` statements with method\n",
    "lookup. However, inside of these methods a structured set of `if`\n",
    "statements remains. We can replace these by adding another level of\n",
    "dispatch.\n",
    "\n",
    "    class Rabbit <: Animal\n",
    "        method encounter(b::Wolf) = run()\n",
    "        method encounter(b::Rabbit) = mate(b)\n",
    "    end\n",
    "\n",
    "    class Wolf <: Animal\n",
    "        method encounter(b::Rabbit) = eat(b)\n",
    "        method encounter(b::Wolf) = follow(b)\n",
    "    end\n",
    "\n",
    "We now have a *double dispatch* system, where a method call uses two\n",
    "lookups, first on the first argument and then on the second argument.\n",
    "This syntax might be considered a bit nicer, but the design begs a\n",
    "question: why is $n=2$ special? It isn’t, and we could consider even\n",
    "more method arguments as part of dispatch. But at that point, why is the\n",
    "first argument special? Why separate methods in a special way based on\n",
    "the first argument? It seems arbitrary, and indeed we can remove the\n",
    "special treatment:\n",
    "\n",
    "    abstract class Animal\n",
    "    end\n",
    "\n",
    "    class Rabbit <: Animal\n",
    "    end\n",
    "\n",
    "    class Wolf <: Animal\n",
    "    end\n",
    "\n",
    "    nearby(a::Animal)               = # search\n",
    "    encounter(a::Rabbit, b::Wolf)   = run(a)\n",
    "    encounter(a::Rabbit, b::Rabbit) = mate(a,b)\n",
    "    encounter(a::Wolf, b::Rabbit)   = eat(a, b)\n",
    "    encounter(a::Wolf, b::Wolf)     = follow(a, b)\n",
    "\n",
    "    while running\n",
    "        for a in animals\n",
    "            b = nearby(a)\n",
    "            encounter(a, b)\n",
    "        end\n",
    "    end\n",
    "\n",
    "Here we made two major changes: the methods have been moved “outside” of\n",
    "any classes, and all arguments are listed explicitly. This is sometimes\n",
    "called *external dispatch*. This change has significant implications.\n",
    "Since methods no longer need to be “inside” classes, there is no\n",
    "syntactic limit to where definitions may appear. Now it is easier to add\n",
    "new methods after a class has been defined. Methods also now naturally\n",
    "operate on combinations of objects, not single objects. The shift to\n",
    "thinking about combinations of objects is fairly revolutionary. Many\n",
    "interesting properties only apply to combinations of objects, and not\n",
    "individuals. We are also now free to think of more exotic kinds of\n",
    "combinations. We can define a method for *any number* of objects:\n",
    "\n",
    "    encounter(ws::Wolf...) = pack(ws)\n",
    "\n",
    "We can also abstract over more subtle properties, like whether the\n",
    "arguments are two animals of the same type:\n",
    "\n",
    "    encounter{T<:Animal}(a::T, b::T) = mate(a, b)\n",
    "\n",
    "</span>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.3.11",
   "language": "julia",
   "name": "julia-0.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.3.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}