defined object MyList
Meeting 06 - Inductive Data Types
What questions does your neighbor have?
In-Class Slides
In-Class Jupyter
Book Chapter
Announcements
- Lab 1 due this Friday 9/13 6pm
- Use GitHub and VS Code: Submit
Lab1.scala
. Just read Jupyter notebook or use it for scratch work. - No autograder on Gradescope. Submit via GitHub.
- Take advantage of lab section Friday to finish!
- Use GitHub and VS Code: Submit
Today
- Inductive Data Types
- Triage Your Questions
- Lab 1?
- Revisit and Go Deeper On:
- Recursion (Meeting 05)
- Data Types (Meeting 04), if time permits
- Binding and Scope (Meeting 03), if time permits
Questions?
- Review:
- What’s tail recursion? How does it relate loops?
Questions?
MyList
A list is an inductive data type:
The List
type constructor from Scala library is very close to the above.
What makes this inductive?
Observe that List[A]
is a recursive type with the tail
field of ::
.
Recursion on Lists
defined function length
defined function length res28_1: Int = 3
Without Pattern Matching
defined function length
Could l.tail
fail?
Append
defined function append
Now, we see why append
(and :::
in the Scala library) has to be linear time.
defined function append xlyl_append: List[Int] = List(1, 2, 3, 4, 5, 6) xlyl_:::: List[Int] = List(1, 2, 3, 4, 5, 6) res31_3: Boolean = true
Buggy Append
What does buggyAppend
do?
defined function buggyAppend
xlyl_buggyAppend: List[Int] = List(3, 2, 1, 4, 5, 6)
Reverse
defined function reverse
defined function reverse res35_1: List[Int] = List(5, 4, 3, 2, 1)
Exercise: Tail-Recursive Reverse
defined function reverse
defined function reverse res37_1: List[Int] = List(5, 4, 3, 2, 1)
reverse(List(1, 2, 3, 4, 5))
-->* loop(List(1, 2, 3, 4, 5), List())
-->* loop(List(2, 3, 4, 5), List(1))
-->* loop(List(3, 4, 5), List(2, 1))
-->* loop(List(4, 5), List(3, 2, 1))
-->* loop(List(5), List(4, 3, 2, 1))
-->* loop(List(), List(5, 4, 3, 2, 1))
List(5, 4, 3, 2, 1)
defined function reverse res38_1: List[Int] = List(5, 4, 3, 2, 1)
Previously, our discussion about tail recursion was simply about efficiency because the operators we considered were commutative. Now, with a non-commutative operator, we see that there is something more.
The accumulator parameter enables us to “do something” as we “recurse down” the list. And the stack in a non-tail recursive function enables us to “do something” as we “return up”.
Trees
:
Compilation Failed
defined trait BinaryTree defined object Empty defined class Node defined function height t: Node = Node( l = Node(l = Empty, d = 2, r = Empty), d = 10, r = Node(l = Empty, d = 14, r = Node(l = Empty, d = 17, r = Empty)) ) res39_5: Int = 3
defined trait BinaryTree defined class Empty defined class Node
Persistent Data Structures
m: Map[Int, List[String]] = Map( 2 -> List("two", "dos", "\u4e8c"), 10 -> List("ten", "diez", "\u5341") ) newm: Map[Int, List[String]] = Map( 2 -> List("two", "dos", "\u4e8c"), 10 -> List("ten", "diez", "\u5341"), 14 -> List("fourteen", "catorce", "\u5341\u56db") )
mOf10: List[String] = List("ten", "diez", "\u5341") newmOf10: List[String] = List("ten", "diez", "\u5341") res42_2: Boolean = true res42_3: Boolean = false res42_4: Boolean = true
Such data structures are called persistent because multiple versions can persist at the same time.
An Object Language
Since we want to study small sub-languages common to programming languages in general, we don’t care much about concrete syntax.
Let’s consider JavaScripty to be the subset of JavaScript we want to study at the moment, for example, number literals and +
:
3 + 7 + 4.2
Our goal is to implement semantics following JavaScript (for this small JavaScripty).
Parsing and Abstract Syntax
The process of converting a program in concrete syntax (i.e., as a string) to a program in abstract syntax (i.e., as a tree) is called parsing.
The first thing we have to consider is how to represent a JavaScripty program as data in Scala, that is, we need to be able to represent a program in our object/source language JavaScripty as data in our meta/implementation language Scala.
Abstract Syntax Trees (ASTs)
:
Compilation Failed
defined trait Expr defined class N defined class Plus three: N = N(n = 3.0) seven: N = N(n = 7.0) four_point_two: N = N(n = 4.2) three_plus_seven: Plus = Plus(e1 = N(n = 3.0), e2 = N(n = 7.0)) three_plus_seven_plus_four_point_two: Plus = Plus( e1 = Plus(e1 = N(n = 3.0), e2 = N(n = 7.0)), e2 = N(n = 4.2) )
Eval
defined function eval
defined function eval res45_1: Double = 1.66 res45_2: Double = 5.6 res45_3: Double = 14.2