{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming Paradigms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **imperative programming**: modifying mutable variables, using assignments, and control\n",
    "structures such as if-then-else, loops, continue, return, etc\n",
    "inspired by Von Neumann architecture of computers.\n",
    "\n",
    "* **functional programming**\n",
    "programming without mutable variables, assignments, loops,\n",
    "other imperative control structures; programming with functions;\n",
    "functions become values that are produced, consumed, and composed;\n",
    "functions can be passed as parameters and returned as values.\n",
    "\n",
    "* **logic programming**\n",
    "programming in logic; use logical deductions to run a program; programs\n",
    "are a set of logical rules and facts; solutions focus on “what” aspect of\n",
    "the problem and let the system figure out “how” to solve them.\n",
    "\n",
    "Orthogonal to\n",
    "\n",
    "* **Object-oriented programming**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functional Programming in Scala"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scala Basics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres0\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m232\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "87 + 145"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36msize\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m2\u001b[39m"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val size = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m10\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5*size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"jp-RenderedText\">\n",
       "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">pi</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Double</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">3.14</span></span></code></pre>\n",
       "</div>"
      ],
      "text/plain": [
       "\u001b[36mpi\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m3.14\u001b[39m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var pi = 3.14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"jp-RenderedText\">\n",
       "<pre><code><span style=\"color: rgb(0, 187, 187)\"><span class=\"ansi-cyan-fg\">radius</span></span>: <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">Double</span></span> = <span style=\"color: rgb(0, 187, 0)\"><span class=\"ansi-green-fg\">21.5</span></span></code></pre>\n",
       "</div>"
      ],
      "text/plain": [
       "\u001b[36mradius\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m21.5\u001b[39m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "var radius = 21.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres5\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m135.02\u001b[39m"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(2 * pi) * radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msquare\u001b[39m"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def square(x: Double) =\n",
    "    x*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres7\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m4.0\u001b[39m"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres8\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m81.0\u001b[39m"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(5+4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres9\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m256.0\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square(square(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumOfSquares\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumOfSquares(x: Double, y: Double) = \n",
    "    square(x) + square(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres11\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m25.0\u001b[39m"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumOfSquares(3,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mpower\u001b[39m"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def power(x: Double, y: Int): Double = \n",
    "    scala.math.pow(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres13\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m8.0\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "power(2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function Evaluation Method (CBV: call by value strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Evaluate all function arguments from left to right\n",
    "* Replace the function application by the function’s right hand side (body), and\n",
    "at the same time replace the formal parameters of the function by the actual arguments (like the beta-reduction of Lambda Calculus)\n",
    "\n",
    "e.g.\n",
    "\n",
    "```scala\n",
    "sumOfSquares(3, 2+2)\n",
    "sumOfSquares(3, 4)\n",
    "square(3) + square(4)\n",
    "3 * 3 + square(4)\n",
    "9 + square(4)\n",
    "9 + 4 * 4\n",
    "9 + 16\n",
    "25\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The above strategy is also called the \"substitution model\"\n",
    "* The evaluation reduces the expression to a value\n",
    "* The substitution model is formalized in the Lambda Calculus\n",
    "* Does every expression evaluate to a value in finite steps? No. \n",
    "\n",
    "```scala\n",
    "def loop: Int = \n",
    "    loop\n",
    "\n",
    "loop\n",
    "loop\n",
    "…\n",
    "…\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Another Function Evaluation Method (CBN: call by name strategy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Do not reduce the function arguments to values but delay evaluating until very end\n",
    "\n",
    "```scala\n",
    "sumOfSquares(3, 2+2)\n",
    "square(3) + square(2+2)\n",
    "3*3 + square(2+2)\n",
    "9 + square(2+2)\n",
    "9 + (2+2) * (2+2)\n",
    "9 + 4*(2+2)\n",
    "9 + 4*4\n",
    "9+16\n",
    "25\n",
    "```\n",
    "\n",
    "call-by-name and call-by-value both result in the same value if\n",
    "\n",
    "* the reduced expression consists of pure functions and\n",
    "* both evaluation strategies terminate\n",
    "\n",
    "call-by-value evaluates arguments once\n",
    "\n",
    "call-by-name delays evaluation and can get lucky in not evaluating if argument not needed!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CBV vs CBN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtest\u001b[39m"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Consider the function test\n",
    "def test(x: Int, y: Int) = \n",
    "    x * x\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```test(2,3)```\n",
    "\n",
    "CBV, CBN: test(2,3) = 2*2 = 4\n",
    "\n",
    "```test(3+4,8)```\n",
    "\n",
    "CBV: test(3+4,8) = test(7,8) = 7\\*7 = 49\n",
    "\n",
    "CBN: test(3+4,8) = (3+4)\\*(3+4) = 7\\*(3+4) = 7\\*7 = 49\n",
    "\n",
    "```test(7,2*4)```\n",
    "\n",
    "CBV: test(7,2\\*4) = test(7,8) = 7\\*7 = 49\n",
    "\n",
    "CBN: test(7,2\\*4) = 7\\*7 = 49\n",
    "\n",
    "```test(3+4,2*8)```\n",
    "\n",
    "Try this on your own…"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scala's Evaluation Strategy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Scala normally uses CBV\n",
    "* But if type of function parameter is preceded by => Scala uses CBN \n",
    "\n",
    "**Example:**\n",
    "```scala\n",
    "def constOne(x: Int, y: =>Int) = \n",
    "    1\n",
    "```\n",
    "\n",
    "constOne(1+2, loop) = constOne(3,loop) = 1\n",
    "\n",
    "constOne(loop, 1+2) = ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### CBV, CBN, Termination\n",
    "\n",
    "* As long as both methods terminate, the end result is the same\n",
    "* What if termination is not guaranteed?\n",
    "* if CBV terminates then CBN will also terminate not vice versa\n",
    "\n",
    "#### Example of CBN terminating but CBV not terminating\n",
    "\n",
    "```scala\n",
    "def first(x: Int, y: Int) = \n",
    "    x\n",
    "```\n",
    "\n",
    "```scala\n",
    "first(1,loop)\n",
    "```\n",
    "\n",
    "under CBN will terminate but will loop forever under CBV\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## val vs var vs def"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**val and var use CBV semantics**\n",
    "\n",
    "i.e. expression is evaluated on definition\n",
    "\n",
    "**val defines a fixed value**\n",
    "\n",
    "**var defines a variable - which can be modified**\n",
    "\n",
    "```scala\n",
    "val x = (1+2)\n",
    "val y = 3\n",
    "var z = 2*y\n",
    "x = 9 //  error \n",
    "z = 12 // ok\n",
    "```\n",
    "\n",
    "**def uses CBN semantics** \n",
    "\n",
    "i.e. expression is evaluated when needed\n",
    "\n",
    "**Example** \n",
    "\n",
    "```scala\n",
    "def x = 1 + 2\n",
    "```\n",
    "at this point ```x``` is not evaluated to ```3```\n",
    "\n",
    "```scala\n",
    "val y = 2 * x\n",
    "```\n",
    "at this point ```2*(1+2)``` is evaluated to make ```y = 6```\n",
    "\n",
    "Normally we use def for function definitions!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conditional Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scala provides an ```if-else``` for expressions to be able to choose from two alternatives.\n",
    "\n",
    "```scala\n",
    "def abs(x: Int) = \n",
    "    if (x >= 0) x else -x\n",
    "```\n",
    "\n",
    "Here ```(x >= 0)``` is a predicate with type ```Boolean```\n",
    "\n",
    "Boolean expressions can be composed of\n",
    "\n",
    "```scala\n",
    "true \n",
    "false\n",
    "!b\n",
    "b && b\n",
    "b || b\n",
    "```\n",
    "\n",
    "and of the usual comparison operations\n",
    "\n",
    "```scala\n",
    "<=, >=, <, >, ==, !=\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rewrite Rules for Booleans/if-then-else expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```!true```      —> ```false```\n",
    "\n",
    "```!false```     —> ```true```\n",
    "\n",
    "```true && e```  —> ```e```\n",
    "\n",
    "```false && e``` —> ```false```\n",
    "\n",
    "```true || e```  —> ```true```\n",
    "\n",
    "```false || e``` —> ```e```\n",
    "\n",
    "\n",
    "```&&```, ```||``` use short-circuit evaluation (second operand need not be evaluated)\n",
    "\n",
    "**Rewrite rule for** ```if (b) e1 else e2```\n",
    "\n",
    "```if (true)  then e1 else e2``` —> ```e1```\n",
    "\n",
    "```if (false) then e1 else e2``` —> ```e2```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## and/or functions using conditional expressions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mand\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mor\u001b[39m\n",
       "\u001b[36mres15_2\u001b[39m: \u001b[32mBoolean\u001b[39m = false\n",
       "\u001b[36mres15_3\u001b[39m: \u001b[32mBoolean\u001b[39m = false"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def and(x: Boolean, y: Boolean): Boolean =\n",
    "    if (x) y else false\n",
    "\n",
    "def or(x: Boolean, y: Boolean): Boolean =\n",
    "  if (x) true else y\n",
    "\n",
    "and(true,false)\n",
    "or(false,false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example Program to compute square root using Newton's Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**To compute sqrt(x):**\n",
    "\n",
    "Start with initial estimate ```y``` (let ```y = 1```)\n",
    "\n",
    "Repeatedly improve the estimate by taking the mean of ```y``` and ```x/y```\n",
    "\n",
    "Let x = 2\n",
    "\n",
    "Estimate (y) | Quotient (x/y) | Mean (y+x/y)/2\n",
    "---------|----------|-----\n",
    "1        |       2/1 = 2           | 1.5\n",
    "1.5      |      2/1.5= 1.333       | 1.4167\n",
    "1.4167   |  2/1.4167=1.4118        | 1.4142\n",
    "1.4142   |                    |\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrt\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrtIter\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mimprove\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36misGoodEnough\u001b[39m\n",
       "\u001b[36mres17_4\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.4142156862745097\u001b[39m"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Take 1\n",
    "\n",
    "def sqrt(x: Double) = \n",
    "    sqrtIter(1.0, x)\n",
    "\n",
    "def sqrtIter(guess: Double, x: Double): Double = \n",
    "    if (isGoodEnough(guess, x)) guess else sqrtIter(improve(guess,x), x)\n",
    "\n",
    "def improve(guess: Double, x: Double) =\n",
    "    (guess + x/guess)/2\n",
    "\n",
    "def isGoodEnough(guess: Double, x: Double) =\n",
    "    scala.math.abs(guess*guess-x) < 0.001\n",
    "\n",
    "sqrt(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: Recursive functions in Scala need an explicit return type.\n",
    "\n",
    "Remark: This version is not very accurate for very very small numbers such \n",
    "0.001, 0.1e-20 and for very large numbers it may not terminate! e.g. for 1.0e20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Blocks and Lexical Scope"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrt\u001b[39m\n",
       "\u001b[36mres18_1\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.4142156862745097\u001b[39m"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Take 2\n",
    "\n",
    "def sqrt(x: Double) = {\n",
    "    def sqrtIter(guess: Double, x: Double): Double = \n",
    "        if (isGoodEnough(guess, x)) guess else sqrtIter(improve(guess,x), x)\n",
    "\n",
    "    def improve(guess: Double, x: Double) =\n",
    "        (guess + x/guess)/2\n",
    "\n",
    "    def isGoodEnough(guess: Double, x: Double) =\n",
    "        scala.math.abs(guess*guess-x) < 0.001\n",
    "\n",
    "    sqrtIter(1.0, x)\n",
    "}\n",
    "\n",
    "sqrt(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A block is delimited by braces {…}\n",
    "\n",
    "* It contains a sequence of definitions or expressions\n",
    "\n",
    "* The last element of a block is an expression that defines the block\n",
    "\n",
    "* A block is itself an expression (whose value is the value of the last expression)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m2\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mf\u001b[39m\n",
       "\u001b[36mresult\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m18\u001b[39m"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val x = 2\n",
    "def f(y: Int) = y + 1\n",
    "val result = {\n",
    "  val x = f(3)\n",
    "  x * x\n",
    "} + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msqrt\u001b[39m\n",
       "\u001b[36mres20_1\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.4142156862745097\u001b[39m"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Take 3; x visible inside block\n",
    "\n",
    "def sqrt(x: Double) = {\n",
    "    def sqrtIter(guess: Double): Double = \n",
    "        if (isGoodEnough(guess)) guess else sqrtIter(improve(guess))\n",
    "\n",
    "    def improve(guess: Double) =\n",
    "        (guess + x/guess)/2\n",
    "\n",
    "    def isGoodEnough(guess: Double) =\n",
    "        scala.math.abs(guess*guess-x) < 0.001\n",
    "\n",
    "    sqrtIter(1.0)\n",
    "}\n",
    "\n",
    "sqrt(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tail Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recap of Function Application\n",
    "\n",
    "```\n",
    "def f(x1,...,xn) =\n",
    "      B\n",
    "```\n",
    "```\n",
    "f(e1,...,en)\n",
    "```\n",
    "\n",
    "* evaluate expressions ```e1,…,en``` resulting in values ```v1,…,vn```\n",
    "* replace f(e1,…,en) by body of function ```B``` in which actual arguments replace formal parameters of f; i.e.\n",
    "\n",
    "```\n",
    "f(e1,...,en)\n",
    "```\n",
    "is replaced by\n",
    "```B[x1:=v1, ...xn:=vn]```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**GCD**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mgcd\u001b[39m\n",
       "\u001b[36mres0_1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m7\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// famous Euclid Algorithm\n",
    "def gcd(a: Int, b: Int): Int =\n",
    "    if (b == 0) a else gcd(b, a%b)\n",
    "\n",
    "gcd(14,21)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "gcd(14,21)\n",
    "\n",
    "if (21 == 0) 14 else gcd(21, 14%21)\n",
    "\n",
    "if (false)14 else gcd(21, 14%21)\n",
    "\n",
    "gcd(21, 14%21)\n",
    "\n",
    "gcd(21, 14)\n",
    "\n",
    "if (14 == 0) 21 else gcd(14, 21%14)\n",
    "\n",
    "if (false) 21 else gcd(14, 21%14)\n",
    "\n",
    "gcd(14, 21%14)\n",
    "\n",
    "gcd(14, 7)\n",
    "\n",
    "if (7 == 0) 14 else gcd(7, 14%7)\n",
    "\n",
    "if (false)14 else gcd(7, 14%7)\n",
    "\n",
    "gcd(7, 14%7)\n",
    "\n",
    "gcd(7, 0)\n",
    "\n",
    "if (0 == 0) 7 else gcd(0, 7%0)\n",
    "\n",
    "7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Tail Recursion is better\n",
    "* If a function calls itself as its last action, the function’s stack can be reused. This is called tail recursion\n",
    "* Tail recursive functions are essentially iterative processes\n",
    "* In Scala, tail-recursive functions can be annotated\n",
    "```\n",
    "@tailrec\n",
    "def gcd(a: Int, b: Int): Int = …\n",
    "```\n",
    "\n",
    "* Factorial\n",
    "\n",
    "```scala\n",
    "def factorial(n: Int): Int =\n",
    "    if n <= 0 1 else n* factorial(n-1)\n",
    "```\n",
    "\n",
    "* Tail recursive version of factorial:\n",
    "\n",
    "```scala\n",
    "def factorial(n: Int): Int =\n",
    "     fact(1,n)\n",
    "\n",
    "def fact(answer: Int, n: Int): Int =\n",
    "     if (n == 0) answer else fact(n*answer, n - 1)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}