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!"
Meeting 02 - Expressions
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?
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 \]