Hello, world!







A Programming Language

Two Variables

  • x, y

Three Operations

  • x++
  • x--
  • x = 0 ? L1 : L2







Example Program

(What does it do?)

L1: x++
    y--
    y = 0 ? L2 : L1
L2: ...







The above language is “equivalent to” every PL!

  • But good luck writing QuickSort …
  • … or Plants v. Zombies
  • … or Spotify!







So Why Study Programming Languages?

Federico Fellini

Federico Fellini

A different language is a different vision of life.







So Why Study Programming Languages?

Spoiler Alert

Spoiler Alert







So Why Study Programming Languages?

The principle of linguistic relativity holds that the structure of a language affects its speakers world view or cognition.

Or more simply:

Programming Language shapes Programming Thought.

Language affects how:

  • Ideas are expressed
  • Computation is expressed







Course Goals

Morpheus, The Matrix

Morpheus, The Matrix

Free Your Mind.







Goal: Learn New Languages / Constructs

Musical Score

Musical Score

New ways to describe and organize computation,

To create programs that are:

  • Readable
  • Correct
  • Extendable
  • Modifiable
  • Reusable







New languages come (and go …)

There was no

  • Java 20 years ago,
  • C# 15 years ago,
  • Rust 10 years ago,
  • Go 5 years ago…







Goal: Learn to Learn

Anatomy

Anatomy

In 130 you will learn the anatomy of a PL

  • Fundamental building blocks
  • Different guises in different PLs

Understand the PLs you already “know”.







Goal: How to Design new Languages

Buried in every extensible system is a PL

  • Emacs, Android: LISP
  • Word, Powerpoint: Macros, VBScript
  • Firefox, Chrome, Safari: JavaScript
  • SQL, Renderman, Latex, XML …

If you work on a large system, you will design a new PL!







Goal: Enable You To Choose Right PL

But isn’t that decided by

  • Libraries
  • Standards
  • Hiring
  • Your Boss?!

Yes.

My goal: Educate tomorrow’s leaders so you’ll make informed choices.







Speaking of Right and Wrong

x = x + 1

x = x + 1







Imperative Programming is Wrong (default)

Gears of War

Gears of War

Tim Sweeney (Epic, Creator of the UNREAL Gaming Engine)

In a concurrent world, imperative is the wrong default.







Imperative Programming is Wrong (default)

John Carmack, creator of FPS (Doom, Quake, …)

Carmack discourages variable mutation

Carmack discourages variable mutation







Functional Programming

  • No assignment
  • No mutation
  • No loops







OMG! Who uses FP?!

  • Google (MapReduce, …)
  • Microsoft (LinQ, F#, …)
  • Facebook (Erlang, Reason,…)
  • Twitter (Scala, …)
  • Wall St. (Haskell, Ocaml, …)

and, most importantly ….

  • CSE 130

Course Mechanics: Web Page

All information lives online:







Course Mechanics: Clickers

Make class interactive

  • Help you and me understand whats tricky

Clickers Are Not Optional

  • Cheap ones are fine
  • Respond to 75% questions
  • Worth 5% of your grade

Laptops are welcome in lecture (but optional)







Course Mechanics: In Class Exercises

  1. Solo Vote
  • Think for yourself, select answer
  1. Discuss
  • Analyze Problem in Groups
  • Reach consensus
  • Have questions, raise your hand!
  1. Group Vote
  • Everyone in group votes
  • Must have same vote to get points
  1. Class Discuss
  • What was easy or tricky?







Course Mechanics: Grading

(30%) Assignments

  • 6-7 assignments
  • All programming

(30%) Midterm

  • In-class (TBA)
  • 2-sided printed “cheat sheet”

(35%) Final

  • 2-sided printed cheat sheet

(05%) Clickers

  • Attempting to answer > 75% questions

(05%) Piazza Extra Credit

  • To top 20 best participants







Course Mechanics: Grading

CSE 130 is graded on a curve

  • Lots of work
  • Don’t worry (too much) about grade







Course Mechanics: No Text

  • Online lecture notes and links

  • Pay attention to lecture

  • Do Assignments Yourself







Programming Assignments

  • About 6-7 over the quarter

  • Accessed via github

  • Schedule up on webpage (due Fridays 5 PM)







Programming Assignments

Don’t complain

Don’t complain







Programming Assignments

Unfamiliar Languages and Environments Forget

  • Java, C, C++ …
  • … and other 20th century languages

Don’t Complain

  • That X-language is hard
  • That X-language is @!%$#$

Do

  • Start early
  • Ask lots of questions!







Programming Assignments

No Deadline Extension

  • Four late days, used as whole unit
  • 5 mins late = 1 late day
  • Plan ahead no other extensions







A Word from Our Sponsor

Programming Assignments done alone

  • Zero Tolerance
  • Offenders punished ruthlessly
  • Please see academic integrity statement

We use plagiarism detection software

  • I am an expert
  • Have code from all previous classes
  • MOSS is fantastic, plagiarize at your own risk







Plan

FP

  • Haskell
  • 5 weeks

OO

  • Scala
  • 3 weeks

Logic

  • Prolog
  • 2 weeks







QuickSort in C

void sort(int arr[], int beg, int end){
  if (end > beg + 1){
    int piv = arr[beg];
    int l = beg + 1;
    int r = end;
    while (l != r-1)
       if(arr[l] <= piv) l++;
       else swap(&arr[l], &arr[r--]);
    if(arr[l]<=piv && arr[r]<=piv)
       l=r+1;
    else if(arr[l]<=piv && arr[r]>piv)
       {l++; r--;}
    else if (arr[l]>piv && arr[r]<=piv)
       swap(&arr[l++], &arr[r--]);
    else r=l-1;
    swap(&arr[r--], &arr[beg]);
    sort(arr, beg, r);
    sort(arr, l, end);
  }
}







QuickSort in Haskell

sort []     = []
sort (x:xs) = sort ls ++ [x] ++ sort rs
  where
    ls      = [ l | l <- xs, l <= x ]
    rs      = [ r | r <- xs, x <  r ]

(not a wholly fair comparison…)







Readability Matters …







QuickSort in J

sort =: (($:@(<#[),(=#[),$:@(>#[))({~ ?@#))^: (1:<#)







Plan for next 5 weeks

  • Tiny core language (Lambda Calculus)

  • Fast forward intro to Haskell

  • Rewind and go over anatomy individually