NextGeneration2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Transformation(identity)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "immutable Transformation\n",
    "    self :: Function\n",
    "    deriv :: Function\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Transformation)\n",
    "    print(io, string(\"Transformation(\", m.self, \")\"))\n",
    "end\n",
    "\n",
    "import Core.eval\n",
    "\n",
    "function eval(transformation :: Transformation)\n",
    "    transformation.self\n",
    "end\n",
    "\n",
    "function deriv(transformation :: Transformation)\n",
    "    transformation.deriv\n",
    "end\n",
    "\n",
    "function sigmoid(x)\n",
    "        2. / (1. + exp(-x)) - 1.\n",
    "end\n",
    "\n",
    "function dsigmoid(x)\n",
    "    2. * exp(-x) / (1. + exp(-x)) ^ 2\n",
    "end\n",
    "\n",
    "const Sigmoid = Transformation(sigmoid, dsigmoid)\n",
    "\n",
    "const Identity = Transformation(identity, one) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "apply! (generic function with 1 method)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function calc_norm(array :: Matrix{Float64})\n",
    "  sqrt(sumabs2(array) / size(array, 1))\n",
    "end\n",
    "\n",
    "function calc_norm(vector :: Array{Float64, 1})\n",
    "  sqrt(sumabs2(vector))\n",
    "end\n",
    "\n",
    "function restriction(vector)\n",
    "  vector / (calc_norm(vector) + 0.001)\n",
    "end\n",
    "\n",
    "function init(a...)\n",
    "    restriction(randn(a...))\n",
    "end\n",
    "\n",
    "const DefaultRate = 0.01\n",
    "\n",
    "immutable Class\n",
    "    class_name :: String\n",
    "    type_len :: Int64\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Class)\n",
    "    print(io, string(\"Class(\", m.class_name, \")\"))\n",
    "end\n",
    "\n",
    "immutable Object\n",
    "    obj_name :: String\n",
    "    class :: Class\n",
    "    value :: Array{Float64, 1}\n",
    "end\n",
    "\n",
    "Object(obj_name :: String, class :: Class) = Object(obj_name, class, init(class.type_len))\n",
    "\n",
    "function Base.show(io :: IO, m :: Object)\n",
    "    print(io, string(\"Obj(\", m.obj_name, \"){\", m.class.class_name, \"}\"))\n",
    "end\n",
    "\n",
    "type DFunction\n",
    "    func_name :: String\n",
    "    in_classes :: Array{Class, 1}\n",
    "    out_class :: Class\n",
    "    f_matrix :: Matrix{Float64}\n",
    "    f_transformation :: Transformation\n",
    "    learning_rate :: Float64\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: DFunction)\n",
    "    in_names = join([c.class_name for c in m.in_classes], \",\")\n",
    "    print(io, string(\"Func(\", m.func_name, \"){\", in_names, \"->\", m.out_class.class_name, \"}\"))\n",
    "end\n",
    "\n",
    "function LFunction(func_name, in_classes :: Array{Class, 1}, out_class :: Class, learning_rate = DefaultRate)\n",
    "    in_len = sum([class.type_len for class in in_classes])\n",
    "    out_len = out_class.type_len\n",
    "    DFunction(func_name, in_classes, out_class, init(out_len, in_len), Identity, learning_rate)\n",
    "end\n",
    "\n",
    "function SFunction(func_name, in_classes :: Array{Class, 1}, out_class :: Class, learning_rate = DefaultRate)\n",
    "    in_len = sum([class.type_len for class in in_classes])\n",
    "    out_len = out_class.type_len\n",
    "    DFunction(func_name, in_classes, out_class, init(out_len, in_len), Sigmoid, learning_rate)\n",
    "end\n",
    "\n",
    "function DFunction(func_name, in_classes :: Array{Class, 1}, out_class :: Class, f_transformation = Sigmoid, learning_rate = DefaultRate)\n",
    "    in_len = sum([class.type_len for class in in_classes])\n",
    "    out_len = out_class.type_len\n",
    "    DFunction(func_name, in_classes, out_class, init(out_len, in_len), f_transformation, learning_rate)\n",
    "end\n",
    "\n",
    "function CoFunction(func_name, in_class :: Class, f_transformation = Sigmoid)\n",
    "    DFunction(func_name, [in_class], in_class, diagm(ones(in_class.type_len)), f_transformation, 0.0)\n",
    "end\n",
    "\n",
    "function apply(func :: DFunction, objs :: Array{Object, 1})\n",
    "    inputs = vcat([obj.value for obj in objs]...)\n",
    "    outputs = eval(func.f_transformation).(func.f_matrix * inputs)\n",
    "    Object(\"untitled\", func.out_class, outputs)\n",
    "end\n",
    "\n",
    "function apply!(func :: DFunction, in_objs :: Array{Object, 1}, out_obj :: Object)\n",
    "    inputs = vcat([obj.value for obj in in_objs]...)\n",
    "    out_obj.value .= eval(func.f_transformation).(func.f_matrix * inputs)\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Obj(untitled){Action}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sensor = Class(\"Sensor\", 100)\n",
    "sensor = Object(\"sensor\", Sensor)\n",
    "Action = Class(\"Action\", 120)\n",
    "action = Object(\"action\", Action)\n",
    "act = DFunction(\"act\", [Sensor, Sensor, Action], Action)\n",
    "apply(act, [sensor, sensor, action])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "bottom_up (generic function with 1 method)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type Tree\n",
    "    op\n",
    "    value\n",
    "    subtrees :: Array{Tree, 1}\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Tree)\n",
    "    if length(m.subtrees) > 0\n",
    "        print(io, \"[\")\n",
    "    end\n",
    "    print(io, string(m.op))\n",
    "    if length(m.subtrees) > 0\n",
    "        print(io, \", \")\n",
    "    end\n",
    "    subs = join([string(subm) for subm in m.subtrees], \", \")\n",
    "    print(io, subs)\n",
    "    if length(m.subtrees) > 0\n",
    "        print(io, \"]\")\n",
    "    end\n",
    "end\n",
    "\n",
    "function beautify(m :: Tree, indent :: Int64)\n",
    "    indentation = join([\"    \" for i in 1:indent])\n",
    "    string(indentation, m.op, \"\\n\", join([beautify(sub, indent + 1) for sub in m.subtrees]))\n",
    "end\n",
    "\n",
    "beautify(m :: Tree) = beautify(m, 0)\n",
    "\n",
    "pprint(m) = print(beautify(m))\n",
    "    \n",
    "function _bottom_up(func :: Function, tree :: Tree, dict :: Dict)\n",
    "    function f()\n",
    "        func(tree, [_bottom_up(func, t, dict) for t in tree.subtrees])\n",
    "    end\n",
    "    get!(f, dict, tree)\n",
    "end\n",
    "\n",
    "## bottom_up(func :: Function, tree :: Tree) = _bottom_up(func, tree, Dict())\n",
    "\n",
    "function bottom_up(func :: Function, tree :: Tree)\n",
    "    func(tree, [bottom_up(func, t) for t in tree.subtrees])\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "eval_tree! (generic function with 1 method)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function lens_split(x :: Array, lens :: Array{Int64, 1})\n",
    "    ind = cumsum(lens)\n",
    "    n = length(ind)\n",
    "    ind = [0; ind]\n",
    "    [view(x, (ind[i]+1):ind[i+1]) for i in 1:n]\n",
    "end\n",
    "\n",
    "function init_node!(op :: Object, value :: Dict)\n",
    "    value[:value] = Array{Float64, 1}(op.class.type_len)\n",
    "    value[:d] = Array{Float64, 1}(op.class.type_len)\n",
    "end\n",
    "\n",
    "function init_node!(op :: DFunction, value :: Dict)\n",
    "    value[:pre_matrix] = Array{Float64, 1}(size(op.f_matrix, 2))\n",
    "    value[:pre_transform] = Array{Float64, 1}(op.out_class.type_len)\n",
    "    value[:value] = Array{Float64, 1}(op.out_class.type_len)\n",
    "    value[:inputs] = lens_split(value[:pre_matrix], [c.type_len for c in op.in_classes])\n",
    "    value[:d] = Array{Float64, 1}(op.out_class.type_len)\n",
    "    value[:pre_transform_d] = Array{Float64, 1}(op.out_class.type_len)\n",
    "    value[:pre_matrix_d] = Array{Float64, 1}(size(op.f_matrix, 2))\n",
    "    value[:input_ds] = lens_split(value[:pre_matrix_d], [c.type_len for c in op.in_classes])\n",
    "end\n",
    "\n",
    "function _init_tree!(tree :: Tree, _)\n",
    "    init_node!(tree.op, tree.value)\n",
    "    tree\n",
    "end\n",
    "    \n",
    "function init_tree!(tree :: Tree)\n",
    "    bottom_up(_init_tree!, tree)\n",
    "end\n",
    "\n",
    "function eval_node!(op :: Object, value :: Dict, value_list)\n",
    "    value[:value] .= op.value\n",
    "end\n",
    "\n",
    "function eval_node!(op :: DFunction, value :: Dict, value_list)\n",
    "    i = 1\n",
    "    for v in value_list\n",
    "        value[:inputs][i] .= v[:value]\n",
    "        i += 1\n",
    "    end\n",
    "    ## value[:pre_matrix] .= vcat([v[:post_feature] for v in value_list]...)\n",
    "    A_mul_B!(value[:pre_transform], op.f_matrix, value[:pre_matrix])\n",
    "    value[:value] .= eval(op.f_transformation).(value[:pre_transform])\n",
    "end\n",
    "\n",
    "function _eval_tree!(tree :: Tree, _)\n",
    "    eval_node!(tree.op, tree.value, (t.value for t in tree.subtrees))\n",
    "    tree\n",
    "end\n",
    "    \n",
    "## function eval_tree!(tree :: Tree)\n",
    "##     bottom_up(_eval_tree!, tree)\n",
    "## end\n",
    "    \n",
    "function eval_tree!(tree :: Tree)\n",
    "    foreach(eval_tree!, tree.subtrees)\n",
    "    eval_node!(tree.op, tree.value, (t.value for t in tree.subtrees))\n",
    "    tree\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sensor = Class(\"Sensor\", 100)\n",
    "sensor = Object(\"sensor\", Sensor)\n",
    "Action = Class(\"Action\", 120)\n",
    "action = Object(\"action\", Action)\n",
    "act = DFunction(\"act\", [Sensor, Action], Action)\n",
    "tree = Tree(act, Dict(), [Tree(sensor, Dict(), []), Tree(action, Dict(), [])])\n",
    "init_tree!(tree)\n",
    "sum(abs(eval_tree!(tree).value[:value] - apply(act, [sensor, action]).value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "bp_tree! (generic function with 1 method)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function bp_transformation!(transformation, inputs, d, new_d)\n",
    "    new_d .= deriv(transformation).(inputs)\n",
    "    for i in 1:length(d)\n",
    "        new_d[i] *= d[i]\n",
    "    end\n",
    "end\n",
    "\n",
    "function bp_matrix!(inputs, matrix, d, step, new_d)\n",
    "    ## step = 0.01\n",
    "    ## dmatrix = reshape(d, (length(d), 1)) * reshape(inputs, (1, length(inputs)))\n",
    "    ## matrix[:, :] += step * reshape(d, (length(d), 1)) * reshape(inputs, (1, length(inputs)))\n",
    "    for j in 1:size(matrix, 2)\n",
    "        new_d[j] = 0.0\n",
    "        for i in 1:size(matrix, 1)\n",
    "            matrix[i, j] += step * d[i] * inputs[j]\n",
    "            new_d[j] += matrix[i, j] * d[i]\n",
    "        end\n",
    "    end\n",
    "end\n",
    "\n",
    "function bp_function!(op :: DFunction, value :: Dict)\n",
    "    bp_transformation!(op.f_transformation, value[:pre_transform], value[:d], value[:pre_transform_d])\n",
    "    bp_matrix!(value[:pre_matrix], op.f_matrix, value[:pre_transform_d], op.learning_rate, value[:pre_matrix_d])\n",
    "end\n",
    "\n",
    "function bp_tree!(tree :: Tree)\n",
    "    if typeof(tree.op) == DFunction\n",
    "        bp_function!(tree.op, tree.value)\n",
    "        for i in 1:length(tree.subtrees)\n",
    "            tree.subtrees[i].value[:d] .= tree.value[:input_ds][i]\n",
    "            bp_tree!(tree.subtrees[i])\n",
    "        end\n",
    "        ## ds = lens_split(d, [c.feature_len for c in tree.op.in_classes])\n",
    "        ## for i in 1:length(tree.subtrees)\n",
    "        ##     bp_tree!(tree.subtrees[i], tree.value[:ds][i])\n",
    "        ## end\n",
    "        ## dds = map(bp_class!, tree.op.in_classes, [t.value for t in tree.subtrees], tree.value[:ds])\n",
    "        ## foreach(bp_tree!, tree.subtrees, dds)\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Sensor = Class(\"Sensor\", 100)\n",
    "sensor = Object(\"sensor\", Sensor)\n",
    "Action = Class(\"Action\", 120)\n",
    "action = Object(\"action\", Action)\n",
    "act = DFunction(\"act\", [Sensor, Action], Action)\n",
    "tree = Tree(act, Dict(), [Tree(sensor, Dict(), []), Tree(action, Dict(), [])])\n",
    "init_tree!(tree)\n",
    "d = ones(length(eval_tree!(tree).value[:value])) - eval_tree!(tree).value[:value]\n",
    "for i in 1:5000\n",
    "    tree.value[:d] .= ones(length(eval_tree!(tree).value[:value])) - eval_tree!(tree).value[:value]\n",
    "    bp_tree!(tree)\n",
    "end\n",
    "## maximum(abs(ones(length(eval_tree!(tree).value[:value])) - eval_tree!(tree).value[:value]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(::fs) (generic function with 3 methods)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function toTree(op)\n",
    "    Tree(op, Dict(), [])\n",
    "end\n",
    "\n",
    "function toTree(skeleton :: Array)\n",
    "    op = skeleton[1]\n",
    "    subs = skeleton[2:end]\n",
    "    Tree(op, Dict(), [toTree(s) for s in subs])\n",
    "end\n",
    "\n",
    "function add!(dict :: Dict, dict1 :: Dict)\n",
    "    for key in keys(dict1)\n",
    "        dict[key] = vcat(get!(dict, key, []), dict1[key])\n",
    "    end\n",
    "    dict\n",
    "end\n",
    "\n",
    "function _index(tree :: Tree, inds :: Array)\n",
    "    ind = Dict{Any, Any}(tree.op => [tree])\n",
    "    for ind1 in inds\n",
    "        add!(ind, ind1)\n",
    "    end\n",
    "    ind\n",
    "end\n",
    "\n",
    "index(tree :: Tree) = bottom_up(_index, tree)\n",
    "\n",
    "type Axiom\n",
    "    tree1 :: Tree\n",
    "    tree2 :: Tree\n",
    "    index :: Dict\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Axiom)\n",
    "    print(io, \"Axiom[\")\n",
    "    print(io, m.tree1)\n",
    "    print(io, \", \")\n",
    "    print(io, m.tree2)\n",
    "    print(io, \"]\")\n",
    "end\n",
    "\n",
    "function beautify(m :: Axiom)\n",
    "    string(\"Axiom:\\n\", beautify(m.tree1, 1), \"\\n\", beautify(m.tree2, 1), \"\\n\")\n",
    "end\n",
    "\n",
    "Axiom(tree1 :: Tree, tree2 :: Tree) = Axiom(tree1, tree2, add!(index(tree1), index(tree2)))\n",
    "\n",
    "Axiom(skeleton1, skeleton2) = Axiom(toTree(skeleton1), toTree(skeleton2))\n",
    "\n",
    "function push!(index :: Dict, ops :: Array)\n",
    "    n = length(ops)\n",
    "    for i in 1:n\n",
    "        for t in index[i]\n",
    "            t.op = ops[i]\n",
    "        end\n",
    "    end\n",
    "end\n",
    "\n",
    "function push!(index :: Dict, ops :: Dict)\n",
    "    for key in keys(ops)\n",
    "        if haskey(index, key)\n",
    "            ts = index[key]\n",
    "            for t in ts\n",
    "                t.op = ops[key]\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "end\n",
    "\n",
    "function push!(axiom :: Axiom, ops)\n",
    "    push!(axiom.index, variables)\n",
    "end\n",
    "\n",
    "function distribute(f)\n",
    "    function fs(dict :: Dict, xs...)\n",
    "        for i in values(dict)\n",
    "            fs(i, xs...)\n",
    "        end\n",
    "    end\n",
    "    function fs(arr :: Array, xs...)\n",
    "        for i in arr\n",
    "            fs(i, xs...)\n",
    "        end\n",
    "    end\n",
    "    function fs(xs...)\n",
    "        f(xs...)\n",
    "    end\n",
    "    fs\n",
    "end\n",
    "\n",
    "function init_axiom!(axiom :: Axiom, variables)\n",
    "    push!(axiom.index, variables)\n",
    "    init_tree!(axiom.tree1)\n",
    "    init_tree!(axiom.tree2)\n",
    "end\n",
    "\n",
    "init_axioms! = distribute(init_axiom!)\n",
    "\n",
    "## add some loss function to deal with degenerating problem?\n",
    "\n",
    "function loss(a, b)\n",
    "    b * (1. - a * b)\n",
    "end\n",
    "\n",
    "function train_axiom!(axiom :: Axiom, variables, n = 1, randomize = identity)\n",
    "    push!(axiom.index, variables)\n",
    "    d1 :: Array{Float64, 1} = axiom.tree1.value[:d]\n",
    "    d2 :: Array{Float64, 1} = axiom.tree2.value[:d]\n",
    "    v1 :: Array{Float64, 1} = axiom.tree1.value[:value]\n",
    "    v2 :: Array{Float64, 1} = axiom.tree2.value[:value]\n",
    "    for i in 1:n\n",
    "        randomize(variables)\n",
    "        push!(axiom.index, variables)\n",
    "        eval_tree!(axiom.tree2)\n",
    "        eval_tree!(axiom.tree1)\n",
    "        for j in 1:length(d1)\n",
    "            d1[j] = loss(v1[j], v2[j])\n",
    "            d2[j] = loss(v2[j], v1[j])\n",
    "        end\n",
    "        bp_tree!(axiom.tree1)\n",
    "        bp_tree!(axiom.tree2)\n",
    "    end\n",
    "end\n",
    "\n",
    "train_axioms! = distribute(train_axiom!)\n",
    "\n",
    "## to prevent degeneration problem, we use anti-traing to deal with the problem.\n",
    "\n",
    "function anti_train_axiom!(axiom :: Axiom, n = 1, randomize = identity)\n",
    "    d1 :: Array{Float64, 1} = axiom.tree1.value[:d]\n",
    "    d2 :: Array{Float64, 1} = axiom.tree2.value[:d]\n",
    "    v1 :: Array{Float64, 1} = axiom.tree1.value[:value]\n",
    "    v2 :: Array{Float64, 1} = axiom.tree2.value[:value]\n",
    "    for i in 1:n\n",
    "        randomize(axiom.tree1)\n",
    "        randomize(axiom.tree2)\n",
    "        eval_tree!(axiom.tree2)\n",
    "        eval_tree!(axiom.tree1)\n",
    "        for j in 1:length(d1)\n",
    "            d1[j] = - loss(v1[j], v2[j])\n",
    "            d2[j] = - loss(v2[j], v1[j])\n",
    "        end\n",
    "        bp_tree!(axiom.tree1)\n",
    "        bp_tree!(axiom.tree2)\n",
    "    end\n",
    "end\n",
    "\n",
    "anti_train_axioms! = distribute(anti_train_axiom!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Axiom[[1, [2, 3]], 3]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Sensor = Class(\"Sensor\", 100)\n",
    "sensor = Object(\"sensor\", Sensor)\n",
    "Action = Class(\"Action\", 120)\n",
    "action = Object(\"action\", Action)\n",
    "act = DFunction(\"act\", [Sensor], Action)\n",
    "invact = DFunction(\"invact\", [Action], Sensor)\n",
    "axiom = Axiom([1, [2, 3]], 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "## @time train!(axiom, [invact, act, sensor], 10000)\n",
    "init_axiom!(axiom, [invact, act, sensor])\n",
    "train_axiom!(axiom, [invact, act, sensor], 10000)\n",
    "## @time foreach(i -> eval_tree!(axiom.tree1), 1:10000)\n",
    "maximum(abs(eval_tree!(axiom.tree2).value[:value] - eval_tree!(axiom.tree1).value[:value]))\n",
    "Profile.clear()\n",
    "@profile train_axiom!(axiom, [invact, act, sensor], 1000)\n",
    "## Profile.print()\n",
    "## Profile.print(format = :flat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Pair"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type Pair\n",
    "    class1 :: Class\n",
    "    class2 :: Class\n",
    "    pclass :: Class\n",
    "    \n",
    "    pair :: DFunction\n",
    "    first :: DFunction\n",
    "    second :: DFunction\n",
    "    first! :: DFunction\n",
    "    second! :: DFunction\n",
    "    \n",
    "    axioms :: Array{Axiom, 1}\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Pair)\n",
    "    print(io, string(\"Module.Pair(\", m.class1.class_name, \",\", m.class2.class_name, \"->\", m.pclass.class_name, \")\"))\n",
    "end\n",
    "\n",
    "function Pair(class1 :: Class, class2 :: Class, pclass :: Class, symbols = [:xy, :x, :y])\n",
    "    pair = DFunction(\"pair\", [class1, class2], pclass)\n",
    "    first = DFunction(\"first\", [pclass], class1)\n",
    "    second = DFunction(\"second\", [pclass], class2)\n",
    "    first! = DFunction(\"first!\", [pclass, class1], pclass)\n",
    "    second! = DFunction(\"second!\", [pclass, class2], pclass)\n",
    "    \n",
    "    tsym = symbols[1]\n",
    "    fsym = symbols[2]\n",
    "    ssym = symbols[3]\n",
    "    axiom_first = Axiom([first, [pair, fsym, ssym]], fsym)\n",
    "    axiom_second = Axiom([second, [pair, fsym, ssym]], ssym)\n",
    "    axiom_first! = Axiom([first!, tsym, fsym], [pair, fsym, [second, tsym]])\n",
    "    axiom_second! = Axiom([second!, tsym, ssym], [pair, [first, tsym], ssym])\n",
    "    axioms = [axiom_first, axiom_second, axiom_first!, axiom_second!]\n",
    "    \n",
    "    Pair(class1, class2, pclass, pair, first, second, first!, second!, axioms)\n",
    "end\n",
    "\n",
    "function Pair(class1 :: Class, class2 :: Class, type_len :: Int64, symbols = [:xy, :x, :y])\n",
    "    post_name = string(\"_\", class1.class_name, \"_\", class2.class_name)\n",
    "    pair_name = string(\"Pair\", post_name)\n",
    "    pclass = Class(pair_name, type_len)\n",
    "    Pair(class1, class2, pclass, symbols)\n",
    "end\n",
    "\n",
    "## @time p = Pair(Sensor, Action, 70)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "List"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type List\n",
    "    class :: Class\n",
    "    lclass :: Class\n",
    "    \n",
    "    empty :: Object\n",
    "\n",
    "    cons :: DFunction\n",
    "    first :: DFunction\n",
    "    rest :: DFunction\n",
    "    first! :: DFunction\n",
    "    rest! :: DFunction\n",
    "    \n",
    "    axioms :: Array{Axiom, 1}\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: List)\n",
    "    print(io, string(\"Module.List(\", m.class.class_name, \"->\", m.lclass.class_name, \")\"))\n",
    "end\n",
    "\n",
    "function List(class :: Class, lclass :: Class, symbols = [:xxs, :x, :xs])\n",
    "    empty = Object(\"empty\", lclass)\n",
    "    empty.value .= -1.\n",
    "    \n",
    "    cons = DFunction(\"cons\", [class, lclass], lclass)\n",
    "    first = DFunction(\"first\", [lclass], class)\n",
    "    rest = DFunction(\"rest\", [lclass], lclass)\n",
    "    first! = DFunction(\"first!\", [lclass, class], lclass)\n",
    "    rest! = DFunction(\"rest!\", [lclass, lclass], lclass)\n",
    "    \n",
    "    tsym = symbols[1]\n",
    "    fsym = symbols[2]\n",
    "    rsym = symbols[3]\n",
    "    axiom_first = Axiom([first, [cons, fsym, rsym]], fsym)\n",
    "    axiom_rest = Axiom([rest, [cons, fsym, rsym]], rsym)\n",
    "    axiom_first! = Axiom([first!, tsym, fsym], [cons, fsym, [rest, tsym]])\n",
    "    axiom_rest! = Axiom([rest!, tsym, rsym], [cons, [first, tsym], rsym])\n",
    "    axioms = [axiom_first, axiom_rest, axiom_first!, axiom_rest!]\n",
    "    \n",
    "    List(class, lclass, empty, cons, first, rest, first!, rest!, axioms)\n",
    "end\n",
    "\n",
    "function List(class :: Class, type_len :: Int64, symbols = [:xxs, :x, :xs])\n",
    "    list_name = string(\"List\", \"_\", class.class_name)\n",
    "    lclass = Class(list_name, type_len)\n",
    "    List(class, lclass, symbols)\n",
    "end\n",
    "\n",
    "## @time l = List(Sensor, 70)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Axiom[[Func(f_eval){Prog,Env->Prog}, [Func(cons){Prog,Prog->Prog}, p1, p2], e], [Func(f_eval){Prog,Env->Prog}, p2, [Func(eval){Prog,Env->Env}, p1, e]]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Variable = Class(\"Variable\", 100)\n",
    "Prog = Class(\"Prog\", 100)\n",
    "Bindingc = Class(\"Binding\", 100)\n",
    "Binding = Pair(Variable, Prog, Bindingc, [:b, :v, :p])\n",
    "Framec = Class(\"Frame\", 100)\n",
    "Frame = List(Bindingc, Framec, [:f1, :b, :f2])\n",
    "Envc = Class(\"Env\", 200)\n",
    "Env = List(Framec, Envc, [:e1, :f, :e2])\n",
    "\n",
    "lookup = DFunction(\"lookup\", [Envc, Variable], Prog)\n",
    "set = DFunction(\"set\", [Envc, Variable, Prog], Envc)\n",
    "add_binding = DFunction(\"add_binding\", [Framec, Variable, Prog], Framec)\n",
    "def = DFunction(\"def\", [Envc, Variable, Prog], Envc)\n",
    "extend = DFunction(\"extend\", [Envc, Variable, Prog], Envc)\n",
    "\n",
    "axiom_lookup1 = Axiom([lookup, [Env.cons, [Frame.cons, [Binding.pair, :v, :p], :f], :e], :v], :p)\n",
    "axiom_lookup2 = Axiom([lookup, [Env.cons, [Frame.cons, [Binding.pair, :v1, :p1], :f2], :e2], :v2], \n",
    "                      [lookup, [Env.cons, :f2, :e2], :v2])\n",
    "axiom_lookup3 = Axiom([lookup, [Env.cons, Frame.empty, :e], :v], [lookup, :e, :v])\n",
    "\n",
    "axiom_set1 = Axiom([set, [Env.cons, [Frame.cons, [Binding.pair, :v1, :p1], :f2], :e2], :v1, :p2], \n",
    "                   [Env.cons, [Frame.cons, [Binding.pair, :v1, :p2], :f2], :e2])\n",
    "axiom_set2 = Axiom([set, [Env.cons, [Frame.cons, [Binding.pair, :v1, :p1], :f2], :e2], :v2, :p2], \n",
    "                   [Env.cons, [Frame.cons, [Binding.pair, :v1, :p1], \n",
    "                                           [Env.first, [set, [Env.cons, :f2, :e2], :v2, :p2]]], \n",
    "                              [Env.rest, [set, [Env.cons, :f2, :e2], :v2, :p2]]])\n",
    "axiom_set3 = Axiom([set, [Env.cons, Frame.empty, :e], :v, :p], [Env.cons, Frame.empty, [set, :e, :v, :p]])\n",
    "\n",
    "axiom_add_binding = Axiom([add_binding, :f, :v, :p], [Frame.cons, [Binding.pair, :v, :p], :f])\n",
    "axiom_def = Axiom([def, :e, :v, :p], [Env.first!, :e, [add_binding, [Env.first, :e], :v, :p]])\n",
    "axiom_extend = Axiom([extend, :e, :v, :p], [def, [Env.cons, Frame.empty, :e], :v, :p])\n",
    "\n",
    "var = DFunction(\"var\", [Variable], Prog)\n",
    "definition = DFunction(\"definition\", [Variable, Prog], Prog) \n",
    "assignment = DFunction(\"assignment\", [Variable, Prog], Prog) \n",
    "procedure = DFunction(\"procedure\", [Variable, Prog], Prog)\n",
    "func_call = DFunction(\"func_call\", [Prog, Prog], Prog)\n",
    "Seq = List(Prog, Prog)\n",
    "\n",
    "f_eval = DFunction(\"f_eval\", [Prog, Envc], Prog)\n",
    "s_eval = DFunction(\"eval\", [Prog, Envc], Envc)\n",
    "\n",
    "axiom_var_s = Axiom([s_eval, [var, :v], :e], :e)\n",
    "axiom_var_f = Axiom([f_eval, [var, :v], :e], [lookup, :e, :v])\n",
    "axiom_definition_s = Axiom([s_eval, [definition, :v, :p], :e], [def, [s_eval, :p, :e], :v, [f_eval, :p, :e]])\n",
    "axiom_definition_f = Axiom([f_eval, [definition, :v, :p], :e], [f_eval, :p, :e])\n",
    "axiom_assignment_s = Axiom([s_eval, [assignment, :v, :p], :e], [set, [s_eval, :p, :e], :v, [f_eval, :p, :e]])\n",
    "axiom_assignment_f = Axiom([f_eval, [assignment, :v, :p], :e], [f_eval, :p, :e])\n",
    "axiom_proc_s = Axiom([s_eval, [procedure, :v, :p], :e], :e)\n",
    "axiom_proc_f = Axiom([f_eval, [procedure, :v, :p], :e], [procedure, :v, :p])\n",
    "axiom_func_s1 = Axiom([s_eval, [func_call, :p1, :p2], :e], \n",
    "                      [s_eval, [func_call, [f_eval, :p1, :e], [f_eval, :p2, :e]], :e])\n",
    "axiom_func_f1 = Axiom([f_eval, [func_call, :p1, :p2], :e], \n",
    "                      [f_eval, [func_call, [f_eval, :p1, :e], [f_eval, :p2, :e]], :e])\n",
    "axiom_func_s2 = Axiom([s_eval, [func_call, [procedure, :v, :p1], :p2], :e], \n",
    "                      [Env.rest, [s_eval, :p1, [extend, :e, :v, :p2]]])\n",
    "axiom_func_f2 = Axiom([f_eval, [func_call, [procedure, :v, :p1], :p2], :e], [f_eval, :p1, [extend, :e, :v, :p2]])\n",
    "axiom_seq_s = Axiom([s_eval, [Seq.cons, :p1, :p2], :e], [s_eval, :p2, [s_eval, :p1, :e]])\n",
    "axiom_seq_f = Axiom([f_eval, [Seq.cons, :p1, :p2], :e], [f_eval, :p2, [s_eval, :p1, :e]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "object_init (generic function with 4 methods)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function object_init(dict :: Dict, name, num :: Int64, class :: Class)\n",
    "    dict[Symbol(name, num)] = Object(string(name, num), class)\n",
    "end\n",
    "\n",
    "function object_init(dict :: Dict, name, class :: Class)\n",
    "    dict[Symbol(name)] = Object(string(name), class)\n",
    "end\n",
    "\n",
    "function object_init(dict :: Dict, name_dict :: Dict, num :: Int64)\n",
    "    for k in keys(name_dict)\n",
    "        object_init(dict, k, name_dict[k])\n",
    "        for i in 1:num\n",
    "            object_init(dict, k, i, name_dict[k])\n",
    "        end\n",
    "    end\n",
    "end\n",
    "\n",
    "function object_init(dict :: Dict, name_dict :: Dict)\n",
    "    for k in keys(name_dict)\n",
    "        object_init(dict, k, name_dict[k])\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0.082677 seconds (36.78 k allocations: 3.173 MB, 8.38% gc time)\n",
      " 27.606562 seconds (1.51 M allocations: 26.994 MB, 0.04% gc time)\n",
      " 28.823933 seconds (1.31 M allocations: 20.913 MB, 0.02% gc time)\n"
     ]
    }
   ],
   "source": [
    "# Variable = Class(\"Variable\", 100)\n",
    "# Prog = Class(\"Prog\", 100)\n",
    "# Bindingc = Class(\"Binding\", 100)\n",
    "# Binding = Pair(Variable, Prog, Bindingc, [:b, :v, :p])\n",
    "# Framec = Class(\"Frame\", 100)\n",
    "# Frame = List(Bindingc, Framec, [:f1, :b, :f2])\n",
    "# Envc = Class(\"Env\", 200)\n",
    "# Env = List(Framec, Envc, [:e1, :f, :e2])\n",
    "\n",
    "dict = Dict()\n",
    "ndict = Dict()\n",
    "ndict[:v] = Variable\n",
    "ndict[:p] = Prog\n",
    "ndict[:b] = Bindingc\n",
    "ndict[:f] = Framec\n",
    "ndict[:e] = Envc\n",
    "object_init(dict, ndict, 2)\n",
    "\n",
    "axioms = Dict()\n",
    "axioms_lookup = [axiom_lookup1, axiom_lookup2, axiom_lookup3]\n",
    "axioms_set = [axiom_set1, axiom_set2, axiom_set3]\n",
    "axioms[:base_env] = [Binding.axioms, Frame.axioms, Env.axioms]\n",
    "axioms[:env] = [axioms_lookup, axioms_set, axiom_add_binding, axiom_def, axiom_extend]\n",
    "axioms_v = [axiom_var_s, axiom_var_f]\n",
    "axioms_d = [axiom_definition_s, axiom_definition_f]\n",
    "axioms_a = [axiom_assignment_s, axiom_assignment_f]\n",
    "axioms_p = [axiom_proc_s, axiom_proc_f]\n",
    "axioms_f = [axiom_func_s1, axiom_func_f1, axiom_func_s2, axiom_func_f2]\n",
    "axioms_s = [axiom_seq_s, axiom_seq_f]\n",
    "axioms[:prog] = [axioms_v, axioms_d, axioms_a, axioms_p, axioms_f, axioms_s]\n",
    "\n",
    "naive_randomize = distribute(function(o :: Object) randn!(o.value) end)\n",
    "\n",
    "function another_naive_randomize(tree :: Tree)\n",
    "    foreach(another_naive_randomize, tree.subtrees)\n",
    "    if typeof(tree.op) == Object\n",
    "        randn!(tree.op.value)\n",
    "    end\n",
    "    tree\n",
    "end\n",
    "\n",
    "@time init_axioms!(axioms, dict)\n",
    "@time train_axioms!(axioms, dict, 1000, naive_randomize)\n",
    "@time anti_train_axioms!(axioms, 1000, another_naive_randomize)\n",
    "## init_axioms!(axioms, dict)\n",
    "## train_axioms!(axioms, dict, 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "315.961316 seconds (14.70 M allocations: 254.372 MB, 0.01% gc time)\n"
     ]
    }
   ],
   "source": [
    "## @time anti_train_axioms!(axioms, 10000, another_naive_randomize)\n",
    "@time train_axioms!(axioms, dict, 10000, naive_randomize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Memory"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type Memory\n",
    "    class :: Class\n",
    "    mclass :: Class\n",
    "    \n",
    "    encode :: DFunction\n",
    "    decode :: DFunction\n",
    "    \n",
    "    axioms :: Array{Axiom, 1}\n",
    "end\n",
    "\n",
    "function Base.show(io :: IO, m :: Memory)\n",
    "    print(io, string(\"Module.Memory(\", m.class.class_name, \"->\", m.mclass.class_name, \")\"))\n",
    "end\n",
    "\n",
    "function Memory(class :: Class, mclass :: Class, symbols = [:s, :m])\n",
    "    encode = DFunction(\"encode\", [class], mclass)\n",
    "    decode = DFunction(\"decode\", [mclass], class)\n",
    "    \n",
    "    sym = symbols[1]\n",
    "    msym = symbols[2]\n",
    "    axiom1 = Axiom([decode, [encode, sym]], sym)\n",
    "    axiom2 = Axiom([encode, [decode, msym]], msym)\n",
    "    axioms = [axiom1, axiom2]\n",
    "    \n",
    "    Memory(class, mclass, encode, decode, axioms)\n",
    "end\n",
    "\n",
    "function Memory(class :: Class, type_len :: Int64, symbols = [:s, :m])\n",
    "    memory_name = string(\"Memory\", \"_\", class.class_name)\n",
    "    mclass = Class(memory_name, type_len)\n",
    "    Memory(class, mclass, symbols)\n",
    "end\n",
    "\n",
    "## @time l = List(Sensor, 70)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "readVar (generic function with 1 method)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Binary = Class(\"Binary\", 1)\n",
    "Stream = List(Binary, Variable, [:v, :x, :v1])\n",
    "\n",
    "function readBin(x)\n",
    "    if x == '0'\n",
    "        Object(\"u\", Binary, [-1.0])\n",
    "    else\n",
    "        Object(\"u\", Binary, [1.0])\n",
    "    end\n",
    "end\n",
    "\n",
    "function readVar(xs)\n",
    "    xs = string(xs)\n",
    "    if length(xs) == 0\n",
    "        Stream.empty\n",
    "    else\n",
    "        apply(Stream.cons, [readBin(xs[1]), readVar(xs[2:end])])\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "prog (generic function with 3 methods)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function prog(x :: Symbol)\n",
    "    [var, readVar(x)]\n",
    "end\n",
    "\n",
    "function prog(x :: Expr)\n",
    "    if x.head == :local\n",
    "        [definition, readVar(x.args[1].args[1]), prog(x.args[1].args[2])]\n",
    "    elseif x.head == :(=)\n",
    "        [assignment, readVar(x.args[1]), prog(x.args[2])]\n",
    "    elseif x.head == :function\n",
    "        [procedure, readVar(x.args[1].args[1]), prog(x.args[2])]\n",
    "    elseif x.head == :call\n",
    "        [func_call, prog(x.args[1]), prog(x.args[2])]\n",
    "    elseif x.head == :block\n",
    "        [Seq.cons, prog(x.args[1]), prog(x.args[2:end])]\n",
    "    else\n",
    "        Seq.empty\n",
    "    end\n",
    "end\n",
    "\n",
    "function prog(x :: Array)\n",
    "    if length(x) == 0\n",
    "        Seq.empty\n",
    "    else\n",
    "        [Seq.cons, prog(x[1]), prog(x[2:end])]\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "repl (generic function with 1 method)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type REPL\n",
    "    env :: Object\n",
    "    ans :: Object\n",
    "end\n",
    "\n",
    "function repl(r :: REPL, command :: String)\n",
    "    command = replace(command, \"var \", \"local \")\n",
    "    t = toTree(prog(parse(command)))\n",
    "    init_tree!(t)\n",
    "    eval_tree!(t)\n",
    "    o = Object(\"c\", Prog, t.value[:value])\n",
    "    r.ans = apply(f_eval, [o, r.env])\n",
    "    apply!(s_eval, [o, r.env], r.env)\n",
    "    r.ans\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "REPL(Obj(empty){Env},Obj(empty){Prog})"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "r = REPL(Env.empty, Seq.empty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a1 = repl(r, \"function(x) x end\").value;\n",
    "a2 = repl(r, \"var y = function(x) x end\").value;\n",
    "a3 = repl(r, \"y\").value;\n",
    "a4 = repl(r, \"function(x) x(x) end\").value;\n",
    "a5 = repl(r, \"begin var y = function(x) x end; y end\").value;\n",
    "as = [a1, a2, a3, a4, a5];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result for pair 1 and 2 is 5.984892709471409.\n",
      "Result for pair 1 and 3 is 22.40046154263174.\n",
      "Result for pair 1 and 4 is 15.463385310585727.\n",
      "Result for pair 1 and 5 is 48.13123937413319.\n",
      "Result for pair 2 and 3 is 18.789090900939044.\n",
      "Result for pair 2 and 4 is 14.965660493130034.\n",
      "Result for pair 2 and 5 is 47.93047872653763.\n",
      "Result for pair 3 and 4 is 11.507351605428116.\n",
      "Result for pair 3 and 5 is 45.41266243234243.\n",
      "Result for pair 4 and 5 is 49.44638593501577.\n"
     ]
    }
   ],
   "source": [
    "pair_computation(function(x, y) sum(abs(as[x] - as[y])) end, 1:5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 29.907746 seconds (1.27 M allocations: 19.426 MB, 0.03% gc time)\n",
      "275.925914 seconds (14.70 M allocations: 254.372 MB, 0.01% gc time)\n"
     ]
    }
   ],
   "source": [
    "@time anti_train_axioms!(axioms, 1000, another_naive_randomize)\n",
    "@time train_axioms!(axioms, dict, 10000, naive_randomize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Method definition combination(Array{#T<:Any, 1}) in module Main at In[90]:2 overwritten at In[92]:2.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "combination (generic function with 3 methods)"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function combination{T}(xs :: Array{T, 1})\n",
    "    if length(xs) < 2\n",
    "        []\n",
    "    elseif length(xs) == 2\n",
    "        Array{Tuple{T, T}, 1}([(xs[1], xs[2])])\n",
    "    else\n",
    "        Array{Tuple{T, T}, 1}([[(xs[1], x) for x in xs[2:end]]..., combination(xs[2:end])...])\n",
    "    end\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING: Method definition pair_computation(Function, Any) in module Main at In[63]:2 overwritten at In[65]:2.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "pair_computation (generic function with 1 method)"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function pair_computation(func :: Function, xs)\n",
    "    function compute(x)\n",
    "        print(string(\"Result for pair \", x[1], \" and \", x[2], \" is \", func(x[1], x[2]), \".\\n\"))\n",
    "    end\n",
    "    foreach(compute, combination(xs))\n",
    "end"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Julia 0.5.0",
   "language": "julia",
   "name": "julia-0.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}