Meeting 02 - Expressions

Bor-Yuh Evan Chang

\(\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}} \)

In-Class Slides
Book Chapter

Announcements

• Syllabus Quiz due tomorrow (Friday) 6pm (with the 24-hour grace period for when “stuff happens”)
• Recitation sections are lab sections — bring your laptop!
  • This Week: Getting your development environment set up!
  • Future Weeks (in general): Getting hands-on help to finish assignments for the 6pm deadline — in addition to office hours during the week

Announcements

• Use Piazza for all course communication.
  • Energetically engage in discussions with your classmates to help each other on the learning activities — for your Class Participation score.
  • For course administrative things (e.g., grade issues, GitHub access issues), use private messages on Piazza to “Instructors” instead of email.
• Added notebook links to PPPL Notes.

Today

• Experience from 3155 Alumni
  • Luis Olivas (Workday)
  • Andrew Arnopoulous (Fitbod)
• Getting Your Money’s Worth
• Chapter 3 Expressions
  • 3.1 Is a Program Executed or Evaluated?: Imperative versus functional computation is a false dichotomy.
  • 3.2 Basic Values, Types, and Expressions: A Scala crash course.

Your Questions So Far?

• On the Syllabus?
• On Getting Your Money’s Worth or why study PL?
• On Expectations and Finding Success?

Your Questions So Far?

Syllabus Policies

Requirements

Distinguishes between learning activities:

• Reading
• Quizzes and Exercises (25%)
• Lab Assignments (30%)
• Participation (5%)

And summative assessments:

• In-Class Exams (20%)
• Final Exam (20%)

Highlights

• Integrity of the Course Materials
• Collaboration Policy
• Redo Policy
• No late assignments but one drop
• No make-up exams (unless emergency or special accommodation)
• Special accommodation requests (religious observances) within first four weeks
• Regrades/redo requests within one week

Is a Program Executed or Evaluated?

The imperative versus functional schism?

Imperative

In the imperative computational model, we focus on executing statements for its effects on a memory.

Some Key Terms:

• Execution proceeds by loads/stores from memory
• Underlying architecture for the Java Virtal Machine (JVM), other VMs, and typical hardware
• Types of memory
  • Locals (registers)
  • Stack
  • Heap
• Execute for side effects

Functional

In the functional computational model, we focus on evaluating expressions, that is, rewriting expressions until we obtain a value.

Some Key Terms:

• Evaluation of expressions
• Rewriting

Expression Rewriting

To a first approximation, there is no external memory. Expression rewriting is actually not so unfamiliar. Primary school arithmetic is expression evaluation:

\[ \begin{array}{rcl} (1 + 1) + (1 + 1) & \longrightarrow& 2 + (1 + 1) \\ & \longrightarrow& 2 + 2 \\ & \longrightarrow& 4 \end{array} \]

Pure Expressions and Order of Evaluation

Being effect-free or pure has advantages by being independent of how a machine evaluates expressions (i.e., called referential transparency).

\[ \begin{array}{rcl} (1 + 1) + (1 + 1) & \longrightarrow& 2 + (1 + 1) \\ & \longrightarrow& 2 + 2 \\ & \longrightarrow& 4 \end{array} \]

For example, the final result does not depend on the order of evaluation (e.g., whether the left \((1 + 1)\) or the right \((1 + 1)\) is evaluated first, or whether they are done in parallel), which makes it easier to reason about programs in isolation (e.g., the meaning of \((1 + 1) + (1 + 1)\)) and for compilers to optimize your code.

Basic Values, Types, and Expressions

Values and Types

Examples?

res1_0: Int = 42
res1_1: Long = 42L
res1_2: Float = 1.618F
res1_3: Double = 1.618
res1_4: Boolean = true
res1_5: Char = 'a'
res1_6: String = "Hello!"

Any value has a type. Most generic definition of a type are the operations that are defined for those values.

Some values can be written down using literals like the above.

Expressions

An expression can be a literal or consist of operations that await to be evaluated. For example, here are some expected expressions:

res3_0: Int = 42
res3_1: Boolean = false
res3_2: Boolean = false
res3_3: Boolean = true
res3_4: Int = 3
res3_5: String = "Hello!"

In the above, we see Scala infers the type of each expression and evaluates each expression to its value. A value is an expression cannot be evaluated any further — the result of evaluating an expression.

Static Type Checking

We can check that an expression has the expected type as follows:

res5_0: Int = 42
res5_1: Long = 42L
res5_2: Float = 1.618F
res5_3: Double = 1.618
res5_4: Boolean = true
res5_5: Char = 'a'
res5_6: String = "Hello!"
res5_7: Int = 42
res5_8: Boolean = false
res5_9: Boolean = false
res5_10: Boolean = true
res5_11: Int = 3
res5_12: String = "Hello!"

Static Type Checking

: 
Compilation Failed

Scala is statically typed. In essence, this statement means that the Scala compiler will perform some validation at compile-time (called type checking) and only translate well-typed expressions.

Static Type Checking

Type checking works by making sure all operations in all sub-expressions have the “expected type”.

(1 + 2) + (3 + 4): Int
- if 1 + 2: Int
  - if 1: Int
  - if 2: Int
- if 3 + 4: Int
  - if 3: Int
  - if 4: Int

res8: Int = 10

Static Type Checking

We state that an expression \(e\) is well-typed with type \(\tau\) using essentially the same notation as Scala, that is, we write \[ e: \tau \quad \text{for expression $e$ has type $\tau$.} \]

Run-Time Errors

java.lang.ArithmeticException: / by zero
  ammonite.$sess.cmd10$Helper.<init>(cmd10.sc:1)
  ammonite.$sess.cmd10$.<clinit>(cmd10.sc:7)

Assertions

Assertions

java.lang.AssertionError: assertion failed
  scala.Predef$.assert(Predef.scala:265)
  ammonite.$sess.cmd14$Helper.<init>(cmd14.sc:1)
  ammonite.$sess.cmd14$.<clinit>(cmd14.sc:7)

Unit

Hello!

Since the unit value () itself is uninteresting and usually associated with side-effecting expression, the printer in the above simply chooses to not print unit values.

Operators and Methods

res18_0: Long = 7L
res18_1: Long = 7L
res18_2: Int = 7
res18_3: String = "3"
res18_4: Int = 7
res18_5: Int = 7
res18_6: Boolean = true
res18_7: Boolean = true

Binary operators like 3 + 4 is just shorthand for a method call 3.+(4). That is, these two syntactically different expressions have the same semantics.

Evaluation Step

\[ e\longrightarrow e' \qquad \text{for expression $e$ \emph{steps to} expression $e'$ in one step.} \]

For example, \[ (1 + 2) + (3 + 4) \longrightarrow 3 + (3 + 4) \]

is the only case assuming left-to-right evaluation order.

0-or-More Steps

\[ e\longrightarrow^{\ast}e' \qquad \text{for expression $e$ \emph{steps to} $e'$ in 0 or more steps,} \]

For example, all of the following hold:

\[ \begin{array}{rcl} (1 + 2) + (3 + 4) & \longrightarrow^{\ast}& (1 + 2) + (3 + 4) \\ (1 + 2) + (3 + 4) & \longrightarrow^{\ast}& 3 + (3 + 4) \\ (1 + 2) + (3 + 4) & \longrightarrow^{\ast}& 3 + 7 \\ (1 + 2) + (3 + 4) & \longrightarrow^{\ast}& 10 \end{array} \]

Evaluation

Sometimes, we only care about the final value of an expression (i.e., its value), so we write \[ e\Downarrow v \qquad \text{for expression $e$ \emph{evaluates to} value $v$.} \]

When we write this particular expression \(e\)

res19: Int = 7

we are asking the interpreter \(\Downarrow\) for its value \(v\), which in this case is 7. That is, we say that for Scala, the following evaluation relation holds:

\[ 3 + 4 \Downarrow 7 \]