Meeting 06 - Inductive Data Types

Bor-Yuh Evan Chang

Thursday, September 12, 2024

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

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!

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:

defined object MyList

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