2 of 37

CSE 341 : Programming Languages� �Lecture 1��Hello ML!

Zach Tatlock

Spring 2015

3 of 37

Hello! My name is…

Zach Tatlock

ztatlock@cs

CSE 546

4 of 37

I really like studying programming languages.

Super stoked to explore PL with all of you.

5 of 37

We shape our tools and thereafter

our tools shape us.

I discover that I think in words. The more words I know, the more things I can think about...

Reading was illegal because if you limit someone's vocab, you limit their thoughts. They can't even think of freedom because they don't have the language to.

Marshall McLuhan

M. K. Asante

6 of 37

I really like studying programming languages.

Why?

Super stoked to explore PL with all of you.

PL helps us break free to think thoughts, ask questions, and solve problems that would otherwise be inaccessible.

7 of 37

Welcome!

We have 10 short weeks to learn the fundamental concepts of PL.

Curiosity and persistence will get you everywhere.

We’ll become better programmers:

Even in languages we won’t use
Learn the core ideas around which every language is built, despite countless surface-level differences and variations

Today’s class:

Administrivia
Dive into ML: HW 1 due Wed next week

8 of 37

Concise to-do list

In the next 24-48 hours:

Read course web page:
Read all course policies (posted soon)
Check out Piazza

Set up ML

Installation/configuration/use instructions on web page
Essential; non-intellectual
No reason to delay!

http://www.cs.washington.edu/education/courses/cse341/15sp/

9 of 37

Our Incredible Guides

Max

super ultra helpful, extraordinarily smart, stellar smiles

Gur

Riley

Stuart

10 of 37

Our Guide in Spirit

Dan Grossman

Creator of this flavor of 341.

(spiritual guide?)

11 of 37

Staying in touch

Piazza! Piazza! Piazza!

https://piazza.com/washington/spring2014/cse341/home
For all discussions
We’ll be there!
You can ask anonymous (to classmates) questions!

Cookies with the Professor (that’s me!)

5 minute chat, 5% of grade

12 of 37

Lecture:

Slides, code, and reading notes / videos posted

May be revised after class
Take notes: materials may not describe everything
The more ways we engage, the better we learn

Ask questions, focus on key ideas

Engage actively

We’ll start pretty much on time (beginning matters most!)
Write down ideas and code as we go
We’ll make lectures interactive, fun, and valuable

13 of 37

Section

Required: will usually cover new material

Sometimes more language or environment details

Sometimes main ideas needed for homework

Will meet this week: using editors and ML

Material often also covered in reading notes / videos

14 of 37

Reading Notes and Videos

Posted for each “course unit:” reading notes and videos that go over most (all?) of the material (and some extra stuff?)

So why come to class?

Videos can make class-time much more valuable (and fun)

Answer your questions without rushing
Can point to occasional optional topics/videos
Can try different things in class, not just recite material

Interact with peers and yours truly!
(probably) see me trip over stuff

15 of 37

Textbooks, or lack thereof

Will treat the “textbooks” as optional, possibly useful references

Look up details you want/need to know, but often in free online resources too

Can provide second explanations, but (because!) they often take a fairly different approach

If the “341 view” confuses you, lecture, reading notes, and video might all confuse you

Some topics aren’t in the texts

Don’t be surprised when we essentially ignore the texts

List on web page what sections are most relevant

Most but maybe not all of you will do fine without the texts

16 of 37

Office hours

Regular hours and locations on course web

Changes as necessary announced on Piazza

Use them

Please visit me
Ideally not just for homework questions (but that’s good too)

17 of 37

Homework

Seven total

To be done individually

Doing the homework involves:

Understanding the concepts being addressed
Writing code demonstrating understanding of the concepts
Testing your code to ensure you have correct programs
“Playing around” with variations, incorrect answers, etc.

Only (2) is graded, but focusing on (2) makes homework harder

Challenge problems: Low points/difficulty ratio

18 of 37

HEADS UP: Homeworks are terse!

Homeworks tend to be worded very precisely and concisely

Technical issues deserve precise technical writing
Conciseness values your time as a reader
You should try to be precise too

Skimming or not understanding why a word or phrase was chosen can make the homework harder

By all means ask if a problem is confusing

Being confused is normal and understandable
I make a mistakes too

20 of 37

Academic Integrity

Read the course policy carefully (posted this afternoon)

Clearly explains how you can and cannot get/provide help on homework and projects

Always explain any unconventional action

Academic integrity is the foundation of the university system

Great trust with little sympathy for violations
Honest work is the most important feature of a university

When in doubt, ask!

21 of 37

Exams

Midterm: … week 5-ish

Final: Late in finals week (probably June 11)

I know, bummer city
Yeah, you have to be here
Unfortunately, probably not much I can do about it

Same concepts, but different format from homework

More conceptual (but write code too)
Will post old exams
Closed book/notes, but you bring one sheet with whatever you want on it

22 of 37

Coursera Doppelgänger

Dan taught this course to thousands of people around the world

You are not allowed to participate in that class!

Please do not search for related homework problems!

This should have little impact on you

Two courses are separate
341 is a great (the greatest?) class
We are committed to this offering being the best ever

Big win for us:

We can use videos and other materials
More time to interact in class and build things

23 of 37

Questions?

Anything I forgot about course mechanics before we discuss, you know, programming languages?

24 of 37

What this course is about

Many essential concepts relevant in any programming language

And how these pieces fit together

Use ML, Racket, and Ruby:

They let various important concepts “shine”
Using multiple languages shows how the same concept just can “look different” or actually be slightly different
In many ways simpler than Java

Big focus on functional programming

Not using mutation (assignment statements) (!)
Using first-class functions (can’t explain that yet)
But many other topics too

25 of 37

Why learn this?

To free our minds from the shackles of imperative programming.

26 of 37

A strange environment

Next 4-5 weeks will use

ML language
Various editors
Read-eval-print-loop (REPL) for evaluating programs

Get things installed and configured ASAP!

Either in the department labs or your own machine
We’ve written thorough instructions (questions welcome)

Only then can you focus on the content of Homework 1

Working in strange environments is a CSE life skill

27 of 37

Mindset

“Let go” of all programming languages you already know

For now, treat ML as a “totally new thing”

Time later to compare/contrast to what you know
For now, “oh that seems kind of like this thing in [Java]” will confuse you, slow you down, and you will learn less

Start from a blank file…

28 of 37

A very simple ML program

[The same program we just wrote in Vim; here for review]

(* My first ML program *)

val x = 34;

val y = 17;

val z = (x + y) + (y + 2);

val q = z + 1;

val abs_of_z = if z < 0 then 0 – z else z;

val abs_of_z_simpler = abs z

29 of 37

A variable binding

Syntax:

Keyword val and punctuation = and ;
Variable x
Expression e

Many forms of these, most containing subexpressions

val z = (x + y) + (y + 2); (* comment *)

More generally:

val x = e;

30 of 37

The semantics

Syntax is just how you write something

Semantics is what that something means

Type-checking (before program runs)
Evaluation (as program runs)

For variable bindings:

Type-check expression and extend static environment
Evaluate expression and extend dynamic environment

So what is the precise syntax, type-checking rules, and evaluation rules for various expressions? Good question!

31 of 37

ML, carefully, so far

A program is a sequence of bindings

Type-check each binding in order using the static environment produced by the previous bindings

Evaluate each binding in order using the dynamic environment produced by the previous bindings

Dynamic environment holds values, the results of evaluating expressions

So far, the only kind of binding is a variable binding

More soon

32 of 37

Expressions

We have seen many kinds of expressions:

34 true false x e1+e2 e1<e2

if e1 then e2 else e3

Can get arbitrarily large since any subexpression can contain subsubexpressions, etc.

Every kind of expression has

Syntax
Type-checking rules

Produces a type or fails (with a bad error message ☹)
Types so far: int bool unit

Evaluation rules (used only on things that type-check)

Produces a value (or exception or infinite-loop)

33 of 37

Variables

Syntax:

sequence of letters, digits, _, not starting with digit

Type-checking:

Look up type in current static environment

If not there fail

Evaluation:

Look up value in current dynamic environment

34 of 37

Addition

Syntax:

e1 + e2 where e1 and e2 are expressions

Type-checking:

If e1 and e2 have type int,

then e1 + e2 has type int

Evaluation:

If e1 evaluates to v1 and e2 evaluates to v2,

then e1 + e2 evaluates to sum of v1 and v2

35 of 37

Values

All values are expressions

Not all expressions are values

A value “evaluates to itself” in “zero steps”

Examples:

34, 17, 42 have type int
true, false have type bool
() has type unit

36 of 37

Slightly tougher ones

What are the syntax, typing rules, and evaluation rules for conditional expressions?

What are the syntax, typing rules, and evaluation rules for

less-than expressions?

37 of 37

The foundation we need

We have many more types, expression forms, and binding forms to learn before we can write “anything interesting”

Syntax, typing rules, evaluation rules will guide us the whole way!

HW 1: functions, pairs, conditionals, lists, options, local bindings

Earlier problems require less

Will not add (or need):

Mutation (a.k.a. assignment): use new bindings instead
Statements: everything is an expression
Loops: use recursion instead

1 of 37