3.6_types.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"top\"></a><img src=\"images/chisel_1024.png\" alt=\"Chisel logo\" style=\"width:480px;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Module 3.6: Generators: Types\n",
    "**Prev: [Object Oriented Programming](3.5_object_oriented_programming.ipynb)**<br>\n",
    "**Next: [Introduction to FIRRTL](4.1_firrtl_ast.ipynb)**\n",
    "\n",
    "## Motivation\n",
    "Scala is a strongly-typed programming language.\n",
    "This is a two-edged sword; on one hand, many programs that would compile and execute in Python (a dynamically-typed language) would fail at compile time in Scala.\n",
    "On the other hand, programs that compile in Scala will contain many fewer runtime errors than a similar Python program.\n",
    "\n",
    "In this section, our goal is to familiarize you with types as a first class citizen in Scala.\n",
    "While initially you may feel you have limited productivity, you will soon learn to understand compile-time error messages and how to architect your programs with the type system in mind to catch more errors for you. \n",
    "\n",
    "\n",
    "## Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val path = System.getProperty(\"user.dir\") + \"/source/load-ivy.sc\"\n",
    "interp.load.module(ammonite.ops.Path(java.nio.file.FileSystems.getDefault().getPath(path)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chisel3._\n",
    "import chisel3.util._\n",
    "import chisel3.tester._\n",
    "import chisel3.tester.RawTester.test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Static Types<a name=\"types-in-scala\"></a>\n",
    "\n",
    "## Types in Scala\n",
    "\n",
    "All objects in Scala have a type, which is usually the object's class.\n",
    "Let's see some:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "println(10.getClass)\n",
    "println(10.0.getClass)\n",
    "println(\"ten\".getClass)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you declare your own class, it has an associated type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyClass {\n",
    "    def myMethod = ???\n",
    "}\n",
    "println(new MyClass().getClass)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While not required, it is HIGHLY recommended that you **define input and output types for all function declarations**.\n",
    "This will let the Scala compiler catch improper use of a function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def double(s: String): String = s + s\n",
    "// Uncomment the code below to test it\n",
    "// double(\"hi\")      // Proper use of double\n",
    "// double(10)        // Bad input argument!\n",
    "// double(\"hi\") / 10 // Inproper use of double's output!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functions that don't return anything return type `Unit`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var counter = 0\n",
    "def increment(): Unit = {\n",
    "    counter += 1\n",
    "}\n",
    "increment()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scala vs. Chisel Types<a name=\"scala-vs-chisel-types\"></a>\n",
    "\n",
    "Recap: Module 2.2 discussed the difference between Chisel types and Scala types, for example the fact that\n",
    "```scala\n",
    "val a = Wire(UInt(4.W))\n",
    "a := 0.U\n",
    "```\n",
    "is legal because `0.U` is of type `UInt` (a Chisel type), whereas\n",
    "```scala\n",
    "val a = Wire(UInt(4.W))\n",
    "a := 0\n",
    "```\n",
    "is illegal because 0 is type `Int` (a Scala type).\n",
    "\n",
    "This is also true of `Bool`, a Chisel type which is distinct from `Boolean`.\n",
    "```scala\n",
    "val bool = Wire(Bool())\n",
    "val boolean: Boolean = false\n",
    "// legal\n",
    "when (bool) { ... }\n",
    "if (boolean) { ... }\n",
    "// illegal\n",
    "if (bool) { ... }\n",
    "when (boolean) { ... }\n",
    "```\n",
    "\n",
    "If you make a mistake and mix up `UInt` and `Int` or `Bool` and `Boolean`, the Scala compiler will generally catch it for you.\n",
    "This is because of Scala's static typing.\n",
    "At compile time, the compiler is able to distinguish between Chisel and Scala types and also able to understand that `if ()` expects a `Boolean` and `when ()` expects a `Bool`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Scala Type Coercion<a name=\"type-coercion\"></a>\n",
    "\n",
    "<!-- typeOf. Scala has a function called `typeOf[T]` which returns a type object for `T`. -->\n",
    "<!-- This doesn't actually seem useful to Chisel users... -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### asInstanceOf\n",
    "\n",
    "`x.asInstanceOf[T]` casts the object `x` to the type `T`. It throws an exception if the given object cannot be cast to type `T`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val x: UInt = 3.U\n",
    "try {\n",
    "  println(x.asInstanceOf[Int])\n",
    "} catch {\n",
    "  case e: java.lang.ClassCastException => println(\"As expected, we can't cast UInt to Int\")\n",
    "}\n",
    "\n",
    "// But we can cast UInt to Data since UInt inherits from Data.\n",
    "println(x.asInstanceOf[Data])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Type Casting in Chisel\n",
    "\n",
    "The code below will give an error if you try to run it without removing the comment.\n",
    "What's the problem?\n",
    "It is trying to assign a `UInt` to an `SInt`, which is illegal.\n",
    "\n",
    "Chisel has a set of type casting functions.\n",
    "The most general is `asTypeOf()`, which is shown below.\n",
    "Some chisel objects also define `asUInt()` and `asSInt()` as well as some others.\n",
    "\n",
    "If you remove the `//` from the code block below, the example should work for you.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TypeConvertDemo extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val in  = Input(UInt(4.W))\n",
    "        val out = Output(SInt(4.W))\n",
    "    })\n",
    "    io.out := io.in//.asTypeOf(io.out)\n",
    "}\n",
    "\n",
    "test(new TypeConvertDemo) { c =>\n",
    "      c.io.in.poke(3.U)\n",
    "      c.io.out.expect(3.S)\n",
    "      c.io.in.poke(15.U)\n",
    "      c.io.out.expect(-1.S)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Type Matching<a name=\"type-matching\"></a>\n",
    "\n",
    "## Match Operator\n",
    "Recall that in 3.1 the match operator was introduced.\n",
    "Type matching is especially useful when trying to write type-generic generators.\n",
    "The following example shows an example of a \"generator\" that can add two literals of type `UInt` or `SInt`.\n",
    "Later sections will talk more about writing type-generic generators.\n",
    "\n",
    "**Note: there are much better and safer ways to write type-generic generators in Scala**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConstantSum(in1: Data, in2: Data) extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val out = Output(chiselTypeOf(in1)) // in case in1 is literal then just get its type\n",
    "    })\n",
    "    (in1, in2) match {\n",
    "        case (x: UInt, y: UInt) => io.out := x + y\n",
    "        case (x: SInt, y: SInt) => io.out := x + y\n",
    "        case _ => throw new Exception(\"I give up!\")\n",
    "    }\n",
    "}\n",
    "println(getVerilog(dut = new ConstantSum(3.U, 4.U)))\n",
    "println(getVerilog(dut = new ConstantSum(-3.S, 4.S)))\n",
    "println(getVerilog(dut = new ConstantSum(3.U, 4.S)))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is good to remember that Chisel types generally should not be value matched.\n",
    "Scala's match executes during circuit elaboration, but what you probably want is a post-elaboration comparison.\n",
    "The following gives a syntax error:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InputIsZero extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val in  = Input(UInt(16.W))\n",
    "        val out = Output(Bool())\n",
    "    })\n",
    "    io.out := (io.in match {\n",
    "        // note that case 0.U is an error\n",
    "        case (0.U) => true.B\n",
    "        case _   => false.B\n",
    "    })\n",
    "}\n",
    "println(getVerilog(new InputIsZero))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unapply\n",
    "What's actually going on when you do a match?\n",
    "Why can you do fancy value matching with case classes like this:\n",
    "```scala\n",
    "case class Something(a: String, b: Int)\n",
    "val a = Something(\"A\", 3)\n",
    "a match {\n",
    "    case Something(\"A\", value) => value\n",
    "    case Something(str, 3)     => 0\n",
    "}\n",
    "```\n",
    "\n",
    "As it turns out, the companion object that is created for every case class also contains an **unapply** method, in addition to an **apply** method.\n",
    "What is an **unapply** method?\n",
    "\n",
    "Scala unapply methods are another form of syntactic sugar that give match statements the ability to both match on types and **extract values** from those types during the matching.\n",
    "\n",
    "Let's look at the following example.\n",
    "For some reason, let's say that if the generator is being pipelined, the delay is `3*totalWidth`, otherwise the delay is `2*someOtherWidth`.\n",
    "Because case classes have **unapply** defined, we can match values inside the case class, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "case class SomeGeneratorParameters(\n",
    "    someWidth: Int,\n",
    "    someOtherWidth: Int = 10,\n",
    "    pipelineMe: Boolean = false\n",
    ") {\n",
    "    require(someWidth >= 0)\n",
    "    require(someOtherWidth >= 0)\n",
    "    val totalWidth = someWidth + someOtherWidth\n",
    "}\n",
    "\n",
    "def delay(p: SomeGeneratorParameters): Int = p match {\n",
    "    case sg @ SomeGeneratorParameters(_, _, true) => sg.totalWidth * 3\n",
    "    case SomeGeneratorParameters(_, sw, false) => sw * 2\n",
    "}\n",
    "\n",
    "println(delay(SomeGeneratorParameters(10, 10)))\n",
    "println(delay(SomeGeneratorParameters(10, 10, true)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you look at the `delay` function, you should note that in addition to matching on the type of each character, we are also:\n",
    "- Directly referencing internal values of the parameters\n",
    "- Sometimes, are matching directly on the internal values of the parameters\n",
    "\n",
    "These are possible due to the compiler implementing an `unapply` method. Note that unapplying the case is just syntactic sugar; e.g. the following two cases examples are equivalent:\n",
    "```scala\n",
    "case p: SomeGeneratorParameters => p.sw * 2\n",
    "case SomeGeneratorParameters(_, sw, _) => sw * 2\n",
    "```\n",
    "\n",
    "In addition, there are more syntaxes and styles of matching. The following two cases are also equivalent, but the second allows you to match on internal values while still reference the parent value:\n",
    "```scala\n",
    "case SomeGeneratorParameters(_, sw, true) => sw\n",
    "case sg@SomeGeneratorParameters(_, sw, true) => sw\n",
    "```\n",
    "\n",
    "Finally, you can directly embed condition checking into match statements, as demonstrated by the third of these equivalent examples:\n",
    "```scala\n",
    "case SomeGeneratorParameters(_, sw, false) => sw * 2\n",
    "case s@SomeGeneratorParameters(_, sw, false) => s.sw * 2\n",
    "case s: SomeGeneratorParameters if s.pipelineMe => s.sw * 2\n",
    "```\n",
    "\n",
    "All these syntaxes are enabled by a Scala unapply method contained in a class's companion object. If you want to unapply a class but do not want to make it a case class, you can manually implement the unapply method. The following example demonstrates how one can manually implement a class's apply and unapply methods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Boat(val name: String, val length: Int)\n",
    "object Boat {\n",
    "    def unapply(b: Boat): Option[(String, Int)] = Some((b.name, b.length))\n",
    "    def apply(name: String, length: Int): Boat = new Boat(name, length)\n",
    "}\n",
    "\n",
    "def getSmallBoats(seq: Seq[Boat]): Seq[Boat] = seq.filter { b =>\n",
    "    b match {\n",
    "        case Boat(_, length) if length < 60 => true\n",
    "        case Boat(_, _) => false\n",
    "    }\n",
    "}\n",
    "\n",
    "val boats = Seq(Boat(\"Santa Maria\", 62), Boat(\"Pinta\", 56), Boat(\"Nina\", 50))\n",
    "println(getSmallBoats(boats).map(_.name).mkString(\" and \") + \" are small boats!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partial Functions\n",
    "This is a brief overview; [this guide](https://twitter.github.io/scala_school/pattern-matching-and-functional-composition.html#PartialFunction) has a more detailed overview.\n",
    "\n",
    "Partial functions are functions that are only defined on a subset of their inputs.\n",
    "Like an option, a partial function may not have a value for a particular input.\n",
    "This can be tested with `isDefinedAt(...)`.\n",
    "\n",
    "Partial functions can be chained together with `orElse`.\n",
    "\n",
    "Note that calling a `PartialFunction` with an undefined input will result in a runtime error. This can happen, for example, if the input to the `PartialFunction` is user-defined. To be more type-safe, we recommend writing functions that return an `Option` instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Helper function to make this cell a bit less tedious.\n",
    "def printAndAssert(cmd: String, result: Boolean, expected: Boolean): Unit = {\n",
    "  println(s\"$cmd = $result\")\n",
    "  assert(result == expected)\n",
    "}\n",
    "\n",
    "// Defined for -1, 2, 5, etc.\n",
    "val partialFunc1: PartialFunction[Int, String] = {\n",
    "  case i if (i + 1) % 3 == 0 => \"Something\"\n",
    "}\n",
    "printAndAssert(\"partialFunc1.isDefinedAt(2)\", partialFunc1.isDefinedAt(2), true)\n",
    "printAndAssert(\"partialFunc1.isDefinedAt(5)\", partialFunc1.isDefinedAt(5), true)\n",
    "printAndAssert(\"partialFunc1.isDefinedAt(1)\", partialFunc1.isDefinedAt(1), false)\n",
    "printAndAssert(\"partialFunc1.isDefinedAt(0)\", partialFunc1.isDefinedAt(0), false)\n",
    "println(s\"partialFunc1(2) = ${partialFunc1(2)}\")\n",
    "try {\n",
    "  println(partialFunc1(0))\n",
    "} catch {\n",
    "  case e: scala.MatchError => println(\"partialFunc1(0) = can't apply PartialFunctions where they are not defined\")\n",
    "}\n",
    "\n",
    "// Defined for 1, 4, 7, etc.\n",
    "val partialFunc2: PartialFunction[Int, String] = {\n",
    "  case i if (i + 2) % 3 == 0 => \"Something else\"\n",
    "}\n",
    "printAndAssert(\"partialFunc2.isDefinedAt(1)\", partialFunc2.isDefinedAt(1), true)\n",
    "printAndAssert(\"partialFunc2.isDefinedAt(0)\", partialFunc2.isDefinedAt(0), false)\n",
    "println(s\"partialFunc2(1) = ${partialFunc2(1)}\")\n",
    "try {\n",
    "  println(partialFunc2(0))\n",
    "} catch {\n",
    "  case e: scala.MatchError => println(\"partialFunc2(0) = can't apply PartialFunctions where they are not defined\")\n",
    "}\n",
    "\n",
    "val partialFunc3 = partialFunc1 orElse partialFunc2\n",
    "printAndAssert(\"partialFunc3.isDefinedAt(0)\", partialFunc3.isDefinedAt(0), false)\n",
    "printAndAssert(\"partialFunc3.isDefinedAt(1)\", partialFunc3.isDefinedAt(1), true)\n",
    "printAndAssert(\"partialFunc3.isDefinedAt(2)\", partialFunc3.isDefinedAt(2), true)\n",
    "printAndAssert(\"partialFunc3.isDefinedAt(3)\", partialFunc3.isDefinedAt(3), false)\n",
    "println(s\"partialFunc3(1) = ${partialFunc3(1)}\")\n",
    "println(s\"partialFunc3(2) = ${partialFunc3(2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Type Safe Connections<a name=\"type-safe-connections\"></a>\n",
    "\n",
    "Chisel can check the type for many connections, including:\n",
    "* Bool/UInt to Clock\n",
    "\n",
    "For other types, Chisel will let you connect them, but may truncate/pad bits as appropriate.\n",
    "* Bool/UInt to Bool/UInt\n",
    "* Bundle to Bundle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Bundle1 extends Bundle {\n",
    "  val a = UInt(8.W)\n",
    "}\n",
    "\n",
    "class Bundle2 extends Bundle1 {\n",
    "  val b = UInt(16.W)\n",
    "}\n",
    "\n",
    "class BadTypeModule extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val c  = Input(Clock())\n",
    "    val in = Input(UInt(2.W))\n",
    "    val out = Output(Bool())\n",
    "\n",
    "    val bundleIn = Input(new Bundle2)\n",
    "    val bundleOut = Output(new Bundle1)\n",
    "  })\n",
    "  \n",
    "  //io.out := io.c // won't work due to different types\n",
    "\n",
    "  // Okay, but Chisel will truncate the input width to 1 to match the output.\n",
    "//   io.out := io.in\n",
    "\n",
    "//   // Compiles; Chisel will connect the common subelements of the two Bundles (in this case, 'a').\n",
    "//   io.bundleOut := io.bundleIn\n",
    "}\n",
    "\n",
    "println(getVerilog(new BadTypeModule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Type Generics<a name=\"type-generics\"></a>\n",
    "Scala's generic types (also known as polymorphism) is very complicated, especially when coupling it with inheritance.\n",
    "\n",
    "This section will just get your toes wet; to understand more, check out [this tutorial](https://twitter.github.io/scala_school/type-basics.html).\n",
    "\n",
    "Classes can be polymorphic in their types. One good example is sequences, which require knowing their contained type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val seq1 = Seq(\"1\", \"2\", \"3\") // Type is Seq[String]\n",
    "val seq2 = Seq(1, 2, 3)       // Type is Seq[Int]\n",
    "val seq3 = Seq(1, \"2\", true)  // Type is Seq[Any]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes, the Scala compiler needs help determining a polymorphic type, which requires the user to explicitly put the type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "//val default = Seq() // Error!\n",
    "val default = Seq[String]() // User must tell compiler that default is of type Seq[String]\n",
    "Seq(1, \"2\", true).foldLeft(default){ (strings, next) =>\n",
    "    next match {\n",
    "        case s: String => strings ++ Seq(s)\n",
    "        case _ => strings\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functions can also be polymorphic in their input or output types. The following example defines a function that times how long it takes to run a block of code. It is parameterized based on the return type of the block of code. *Note that the `=> T` syntax encodes an anonymous function that does not have an argument list, e.g. `{ ... }` versus `{ x => ... }`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def time[T](block: => T): T = {\n",
    "    val t0 = System.nanoTime()\n",
    "    val result = block\n",
    "    val t1 = System.nanoTime()\n",
    "    val timeMillis = (t1 - t0) / 1000000.0\n",
    "    println(s\"Block took $timeMillis milliseconds!\")\n",
    "    result\n",
    "}\n",
    "\n",
    "// Adds 1 through a million\n",
    "val int = time { (1 to 1000000).reduce(_ + _) }\n",
    "println(s\"Add 1 through a million is $int\")\n",
    "\n",
    "// Finds the largest number under a million that, in hex, contains \"beef\"\n",
    "val string = time {\n",
    "    (1 to 1000000).map(_.toHexString).filter(_.contains(\"beef\")).last\n",
    "}\n",
    "println(s\"The largest number under a million that has beef: $string\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chisel Type Hierarchy\n",
    "To write type generic code with Chisel, it is helpful to know a bit about the type hierarchy of Chisel.\n",
    "\n",
    "`chisel3.Data` is the base class for Chisel hardware types.\n",
    "`UInt`, `SInt`, `Vec`, `Bundle`, etc. are all instances of `Data`.\n",
    "`Data` can be used in IOs and supports `:=`, wires, regs, etc.\n",
    "\n",
    "Registers are a good example of polymorphic code in Chisel.\n",
    "Look at the implementation of `RegEnable` (a register with a `Bool` enable signal) [here](https://github.com/freechipsproject/chisel3/blob/v3.0.0/src/main/scala/chisel3/util/Reg.scala#L10).\n",
    "The apply function is templated for `[T <: Data]`, which means `RegEnable` will work for all Chisel hardware types.\n",
    "\n",
    "Some operations are only defined on subtypes of `Bits`, for example `+`.\n",
    "This is why you can add `UInt`s or `SInt`s but not `Bundle`s or `Vec`s."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:blue\">**Example: Type Generic ShiftRegister**<a name=\"type-generic-shift-register\"></a></span><br>\n",
    "In Scala, objects and functions aren't the only things we can treat as parameters.\n",
    "We can also treat types as parameters.\n",
    "\n",
    "We usually need to provide a type constraint.\n",
    "In this case, we want to be able to put objects in a bundle, connect (:=) them, and create registers with them (RegNext).\n",
    "These operations cannot be done on arbitrary objects; for example wire := 3 is illegal because 3 is a Scala Int, not a Chisel UInt.\n",
    "If we use a type constraint to say that type T is a subclass of Data, then we can use := on any objects of type T because := is defined for all Data.\n",
    "\n",
    "Here is an implementation of a shift register that take types as a parameter.\n",
    "*gen* is an argument of type T that tells what width to use, for example new ShiftRegister(UInt(4.W)) is a shift register for 4-bit UInts.\n",
    "*gen* also allows the Scala compiler to infer the type T- you can write new ShiftRegister[UInt](UInt(4.W)) if you want to to be more specific, but the Scala compiler is smart enough to figure it out if you leave out the [UInt]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ShiftRegisterIO[T <: Data](gen: T, n: Int) extends Bundle {\n",
    "    require (n >= 0, \"Shift register must have non-negative shift\")\n",
    "    \n",
    "    val in = Input(gen)\n",
    "    val out = Output(Vec(n + 1, gen)) // + 1 because in is included in out\n",
    "    override def cloneType: this.type = (new ShiftRegisterIO(gen, n)).asInstanceOf[this.type]\n",
    "}\n",
    "\n",
    "class ShiftRegister[T <: Data](gen: T, n: Int) extends Module {\n",
    "    val io = IO(new ShiftRegisterIO(gen, n))\n",
    "    \n",
    "    io.out.foldLeft(io.in) { case (in, out) =>\n",
    "        out := in\n",
    "        RegNext(in)\n",
    "    }\n",
    "}\n",
    "\n",
    "visualize(() => new ShiftRegister(SInt(6.W), 3))\n",
    "test(new ShiftRegister(SInt(6.W), 3)) { c => \n",
    "    println(s\"Testing ShiftRegister of type ${c.io.in} and depth ${c.io.out.length}\")\n",
    "    for (i <- 0 until 10) {\n",
    "        c.io.in.poke(i.S) // magic literal creation\n",
    "        println(s\"$i: ${c.io.out.indices.map { index => c.io.out(index).peek().litValue} }\")\n",
    "        c.clock.step(1)\n",
    "    }}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We generally recommend avoiding to use inheritance with type generics.\n",
    "It can be very tricky to do properly and can get frustrating quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Type Generics with Typeclasses\n",
    "\n",
    "The example above was limited to simple operations that could be performed on any instance of `Data` such as `:=` or `RegNext()`.\n",
    "When generating DSP circuits, we would like to do mathematical operations like addition and multiplication.\n",
    "The `dsptools` library provides tools for writing type parameterized DSP generators.\n",
    "\n",
    "Here is an example of writing a multiply-accumulate module.\n",
    "It can be used to generate a multiply-accumulate (MAC) for `FixedPoint`, `SInt`, or even `DspComplex[T]` (the complex number type provided by `dsptools`).\n",
    "The syntax of the type bound is a little different because `dsptools` uses typeclasses.\n",
    "They are beyond the scope of this notebook.\n",
    "Read the `dsptools` readme and documentation for more information on using typeclasses.\n",
    "\n",
    "`T <: Data : Ring` means that `T` is a subtype of `Data` and is also a `Ring` .\n",
    "`Ring` is defined in `dsptools` as a number with `+` and `*` (among other operations).\n",
    "\n",
    "_An alternative to `Ring` would be `Real`, but that would not allow us to make a MAC for `DspComplex()` because complex numbers are not `Real`._\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chisel3.experimental._\n",
    "import dsptools.numbers._\n",
    "\n",
    "class Mac[T <: Data : Ring](genIn : T, genOut: T) extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val a = Input(genIn)\n",
    "        val b = Input(genIn)\n",
    "        val c = Input(genIn)\n",
    "        val out = Output(genOut)\n",
    "    })\n",
    "    io.out := io.a * io.b + io.c\n",
    "}\n",
    "\n",
    "println(getVerilog(new Mac(UInt(4.W), UInt(6.W)) ))\n",
    "println(getVerilog(new Mac(SInt(4.W), SInt(6.W)) ))\n",
    "println(getVerilog(new Mac(FixedPoint(4.W, 3.BP), FixedPoint(6.W, 4.BP))))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: Mac as Object**</span><br>\n",
    "\n",
    "The Mac `Module` has a small number of inputs and just one output.\n",
    "It might be convenient for other Chisel generators to write code like\n",
    "```scala\n",
    "val out = Mac(a, b, c)\n",
    "```\n",
    "\n",
    "Implement an `apply` method in the `Mac` companion object below that implements the `Mac` functionality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "object Mac {\n",
    "    def apply[T <: Data : Ring](a: T, b: T, c: T): T = {\n",
    "        ??? // your code\n",
    "    }\n",
    "}\n",
    "\n",
    "class MacTestModule extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val uin = Input(UInt(4.W))\n",
    "        val uout = Output(UInt())\n",
    "        val sin = Input(SInt(4.W))\n",
    "        val sout = Output(SInt())\n",
    "        //val fin = Input(FixedPoint(16.W, 12.BP))\n",
    "        //val fout = Output(FixedPoint())\n",
    "    })\n",
    "    // for each IO pair, do out = in * in + in\n",
    "    io.uout := Mac(io.uin, io.uin, io.uin)\n",
    "    io.sout := Mac(io.sin, io.sin, io.sin)\n",
    "    //io.fout := Mac(io.fin, io.fin, io.fin)\n",
    "}\n",
    "println(getVerilog(new MacTestModule))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-1\" />\n",
    "<label for=\"check-1\"><strong>Solution</strong> (click to toggle displaying)</label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "\n",
    "        a * b + c\n",
    "\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: Integrator**</span><br>\n",
    "Implement an integrator as pictured below. $n_1$ is the width of `genReg` and $n_2$ is the width of `genIn`.\n",
    "\n",
    "Don't forget that `Reg`, `RegInit`, `RegNext`, `RegEnable`, etc. are templated for types `T <: Data`.\n",
    "\n",
    "<img src=\"images/integrator.svg\" alt=\"Integrator\" style=\"width: 250px;\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Integrator[T <: Data : Ring](genIn: T, genReg: T) extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val in  = Input(genIn)\n",
    "        val out = Output(genReg)\n",
    "    })\n",
    "    \n",
    "    ??? // your code\n",
    "}\n",
    "\n",
    "test(new Integrator(SInt(4.W), SInt(8.W))) { c =>\n",
    "    c.io.in.poke(3.S)\n",
    "    c.io.out.expect(0.S)\n",
    "    c.clock.step(1)\n",
    "    c.io.in.poke(-4.S)\n",
    "    c.io.out.expect(3.S)\n",
    "    c.clock.step(1)\n",
    "    c.io.in.poke(6.S)\n",
    "    c.io.out.expect(-1.S)\n",
    "    c.clock.step(1)\n",
    "    c.io.out.expect(5.S)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-2\" />\n",
    "<label for=\"check-2\"><strong>Solution</strong> (click to toggle displaying)</label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "\n",
    "class Integrator\\[T <: Data : Ring\\](genIn: T, genReg: T) extends Module {\n",
    "    val io = IO(new Bundle {\n",
    "        val in  = Input(genIn.cloneType)\n",
    "        val out = Output(genReg.cloneType)\n",
    "    })\n",
    "    \n",
    "    val reg = RegInit(genReg, Ring[T].zero) // init to zero\n",
    "    reg := reg + io.in\n",
    "    io.out := reg\n",
    "}\n",
    "\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Creating a Custom Type<a name=\"creating-a-custom-type\"></a>\n",
    "\n",
    "One of the things that makes Chisel powerful is its extensibility.\n",
    "You can add your own types that have their own operations and representations that are tailored to your application.\n",
    "This section will introduce ways to make custom types."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:blue\">**Example: DspComplex**</span><br>\n",
    "`DspComplex` is a custom data type defined in **dsptools** [here](https://github.com/ucb-bar/dsptools/blob/v1.0.0/src/main/scala/dsptools/numbers/chisel_concrete/DspComplex.scala#L59).\n",
    "The key line to understand is this:\n",
    "```scala\n",
    "class DspComplex[T <: Data:Ring](val real: T, val imag: T) extends Bundle { ... }\n",
    "```\n",
    "\n",
    "`DspComplex` is a type-generic container.\n",
    "That means the real and imaginary parts of a complex number can be any type as long as they satisfy the type constraints, given by `T <: Data : Ring`.\n",
    "\n",
    "`T <: Data` means `T` is a subtype of `chisel3.Data`, the base type for Chisel objects.\n",
    "This means that `DspComplex` only works for objects that are Chisel types and not arbitrary Scala types.\n",
    "\n",
    "`T : Ring` means that a Ring typeclass implementation for `T` exists.\n",
    "`Ring` typeclasses define `+` and `*` operators as well as additive and multiplicative identities (see [this Wikipedia article](https://en.wikipedia.org/wiki/Ring_(mathematics)) for details about rings).\n",
    "**dsptools** defines typeclasses for commonly used Chisel types [here](https://github.com/ucb-bar/dsptools/tree/v1.0.0/src/main/scala/dsptools/numbers/chisel_types).\n",
    "\n",
    "**dsptools** also defines a `Ring` typeclass for `DspComplex`, so we can reuse our MAC generator with complex numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "println(getVerilog(new Mac(DspComplex(SInt(4.W), SInt(4.W)), DspComplex(SInt(6.W), SInt(6.W))) ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: Sign-magnitude Numbers**</span><br>\n",
    "Suppose you wanted to use a sign-magnitude representation and want to reuse all of your DSP generators.\n",
    "Typeclasses enable this kind of ad-hoc polymorphism.\n",
    "The following example gives the beggining of an implementation of a SignMagnitude type as well as an implementation of a `Ring` typeclass that will allow the type to be used with the Mac generator.\n",
    "\n",
    "Fill in implementations for `+` and `*`.\n",
    "You should pattern them after the implementation for `unary_-()`.\n",
    "The next block contains a test that checks the correctness of a `Mac` that uses `SignMagnitude`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SignMagnitude(val magnitudeWidth: Option[Int] = None) extends Bundle {\n",
    "    val sign = Bool()\n",
    "    val magnitude = magnitudeWidth match {\n",
    "        case Some(w) => UInt(w.W)\n",
    "        case None    => UInt()\n",
    "    }\n",
    "    def +(that: SignMagnitude): SignMagnitude = {\n",
    "        // Implement this!\n",
    "    }\n",
    "    def -(that: SignMagnitude): SignMagnitude = {\n",
    "        this.+(-that)\n",
    "    }\n",
    "    def unary_-(): SignMagnitude = {\n",
    "        val result = Wire(new SignMagnitude())\n",
    "        result.sign := !this.sign\n",
    "        result.magnitude := this.magnitude\n",
    "        result\n",
    "    }\n",
    "    def *(that: SignMagnitude): SignMagnitude = {\n",
    "        // Implement this!\n",
    "    }\n",
    "}\n",
    "trait SignMagnitudeRing extends Ring[SignMagnitude] {\n",
    "    def plus(f: SignMagnitude, g: SignMagnitude): SignMagnitude = {\n",
    "        f + g\n",
    "    }\n",
    "    def times(f: SignMagnitude, g: SignMagnitude): SignMagnitude = {\n",
    "        f * g\n",
    "    }\n",
    "    def one: SignMagnitude = {\n",
    "        val one = Wire(new SignMagnitude(Some(1)))\n",
    "        one.sign := false.B\n",
    "        one.magnitude := 1.U\n",
    "        one\n",
    "    }\n",
    "    def zero: SignMagnitude = {\n",
    "        val zero = Wire(new SignMagnitude(Some(0)))\n",
    "        zero.sign := false.B\n",
    "        zero.magnitude := 0.U\n",
    "        zero\n",
    "    }\n",
    "    def negate(f: SignMagnitude): SignMagnitude = {\n",
    "        -f\n",
    "    }\n",
    "    \n",
    "    // Leave unimplemented for this example\n",
    "    def minusContext(f: SignMagnitude, g: SignMagnitude): SignMagnitude = ???\n",
    "    def negateContext(f: SignMagnitude): SignMagnitude = ???\n",
    "    def plusContext(f: SignMagnitude,g: SignMagnitude): SignMagnitude = ???\n",
    "    def timesContext(f: SignMagnitude,g: SignMagnitude): SignMagnitude = ???\n",
    "}\n",
    "implicit object SignMagnitudeRingImpl extends SignMagnitudeRing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import chisel3.experimental.BundleLiterals._\n",
    "\n",
    "test(new Mac(new SignMagnitude(Some(4)), new SignMagnitude(Some(5)))) { c =>\n",
    "    c.io.a.poke(chiselTypeOf(c.io.a).Lit(_.sign -> false.B, _.magnitude -> 3.U))\n",
    "    c.io.b.poke(chiselTypeOf(c.io.b).Lit(_.sign -> false.B, _.magnitude -> 3.U))\n",
    "    c.io.c.poke(chiselTypeOf(c.io.c).Lit(_.sign -> false.B, _.magnitude -> 2.U))\n",
    "    c.io.out.expect(chiselTypeOf(c.io.out).Lit(_.sign -> false.B, _.magnitude -> 11.U))\n",
    "\n",
    "    c.io.c.sign.poke(true.B)\n",
    "    c.io.out.expect(chiselTypeOf(c.io.out).Lit(_.sign -> false.B, _.magnitude -> 7.U))\n",
    "\n",
    "    c.io.b.sign.poke(true.B)\n",
    "    c.io.out.expect(chiselTypeOf(c.io.out).Lit(_.sign -> true.B, _.magnitude -> 11.U))\n",
    "}\n",
    "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Look at the verilog to see if the output looks reasonable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "println(getVerilog(new Mac(new SignMagnitude(Some(4)), new SignMagnitude(Some(5)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`SignMagnitude` even works with `DspComplex`!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "println(getVerilog(new Mac(DspComplex(new SignMagnitude(Some(4)), new SignMagnitude(Some(4))), DspComplex(new SignMagnitude(Some(5)), new SignMagnitude(Some(5))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-3\" />\n",
    "<label for=\"check-3\"><strong>Solution</strong> (click to toggle displaying)</label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "    // implementations for class SignMagnitude\n",
    "\n",
    "    def +(that: SignMagnitude): SignMagnitude = {\n",
    "      val result = Wire(new SignMagnitude())\n",
    "      val signsTheSame = this.sign === that.sign\n",
    "      when (signsTheSame) {\n",
    "        result.sign      := this.sign\n",
    "        result.magnitude := this.magnitude + that.magnitude\n",
    "      } .otherwise {\n",
    "        when (this.magnitude > that.magnitude) {\n",
    "          result.sign      := this.sign\n",
    "          result.magnitude := this.magnitude - that.magnitude\n",
    "        } .otherwise {\n",
    "          result.sign      := that.sign\n",
    "          result.magnitude := that.magnitude - this.magnitude\n",
    "        }   \n",
    "      }   \n",
    "      result\n",
    "    }\n",
    "    def *(that: SignMagnitude): SignMagnitude = {\n",
    "        val result = Wire(new SignMagnitude())\n",
    "        result.sign := this.sign ^ that.sign\n",
    "        result.magnitude := this.magnitude * that.magnitude\n",
    "        result\n",
    "    }\n",
    "\n",
    "\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "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.12.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}