Hello, world!

Who am I?

Nadia Polikarpova

Nadia Polikarpova

  • Assistant professor at CSE since Sept 2017
  • PhD at ETH Zurich
  • Postdoc at MIT

My Research

  • Software Verification: how to prove software is doing the right thing?
  • Software Synthesis: how to generate software that does the right thing?

The Crew

Teaching assistants:


  • Shivani Doshi
  • Daniel Wang
  • Jiaxiao (Joe) Zhou

What is CSE 130 about?

Bad news:

  • lots of work

Good news:

  • lots of programming!
  • (and we’re here to help)

What is CSE 130 not about?


  • JavaScript in September
  • Haskell in October
  • C++ in November
  • etc.

New languages come (and go …)

There was no

  • Java 25 years ago
  • C# 20 years ago
  • Rust 10 years ago
  • WebAssembly 2 years ago

What is CSE 130 about?

  • Concepts in programming languages
  • Programming paradigms
  • Language design and implementation

A Programming Language

Two Variables

  • x, y

Three Operations

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

Example Program

(What does it do?)

L1: x++
    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?

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 and computation are expressed

Course Goals

Morpheus, The Matrix

Morpheus, The Matrix

Free Your Mind.

Goal: Learn the Anatomy of PL



  • What makes a programming language?
  • Which features are fundamental and which are syntactic sugar?

Goal: Learn New Languages / Constructs

Musical Score

Musical Score

New ways to describe and organize computation, to create programs that are:

  • Correct
  • Readable
  • Extendable
  • Reusable

Goal: How to Design new Languages

New hot lanuages being designed in industry as we speak:

  • Flow, React @ Facebook
  • Rust @ Mozilla,
  • TypeScript @ Microsoft
  • Swift @ Apple
  • WebAsssembly @ Google + Mozilla + Microsoft

Buried in every large system is a (domain-specific) language

  • DB: SQL
  • Word, Excel: Formulas, Macros, VBScript
  • Emacs: LISP
  • Latex, shell scripts, makefiles, …

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?!


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

Course Syllabus

  • Lambda calculus (2 weeks)
  • Haskell (8 weeks)
    • learn Haskell
    • implement a toy language in Haksell

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)
    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
    ls      = [ l | l <- xs, l <= x ]
    rs      = [ r | r <- xs, x <  r ]

(not a wholly fair comparison…)

Course Logistics

  • webpage
    • calendar, lecture notes, programming assignments, …
  • piazza
    • to-go place if you have a question or need help
    • email is futile


  • 30% Assignments
  • 30% Midterm
  • 35% Final
  • 05% Class participation (clickers)
  • 05% Piazza Extra Credit
    • To top 20 best participants


  • 6 programming assignments
  • Released online, at least a week before due date
  • Due on Wednesday at 11:59pm
    • no assignment this and next Wednesday
  • Four late days, used as whole unit
    • 5 mins late = 1 late day
  • Submission instructions in the assignment
  • Solve in groups of at most two
    • register your group here
    • submit individually


  • Midterm: in-class on Nov 1
    • subject to change but unlikely
  • Final: Dec 12
  • 2-sided “cheat sheet”
  • The final is cumulative
  • Midterm grade is calculated as midterm > 0 ? max(final, midterm) : 0
    • you get a second chance if you don’t do well on the midterm
    • you must show up to both the midterm and the final


Make class interactive

  • Help you and me understand what’s tricky

Clickers Are Not Optional

  • Cheap ones are fine
  • Respond to 75% questions

Register your clicker here


If you work on a 130 assignment with a partner…

A. only one of the partners must turn in the solution

B. both partners must turn in (potentially the same) solution

C. working in pairs is not allowed

Quiz Protocol

  1. Solo Vote
    • Think for yourself, select answer
  2. Discuss
    • Analyze Problem in Groups
    • Reach consensus
    • Have questions, raise your hand!
  3. Group Vote
    • Everyone in group votes
    • Hopefully the same way but not enforced
    • You don’t have to answer correctly to get points!
  4. Class Discuss
    • What was easy or tricky?

Your Resources

  • Discussion section: Mon 5pm, CENTR 115
  • Office hours
    • every day, check calendar
    • I expect you to come to my office hours at least once this quarter
  • Piazza
    • we answer during work hours
  • No text
    • online lecture notes and links

Academic Integrity

Programming assignments: do not copy from classmates or from previous years

Exams done alone

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

Students with Disabilites

Students requesting accommodations for this course due to a disability or current functional limitation must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) which is located in University Center 202 behind Center Hall.

Students are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the CSE OSD Liaison in advance so that accommodations may be arranged.

Diversity and Inclusion

Our goal is to create a diverse and inclusive learning environment where all students feel comfortable and can thrive. If there is a way we can make you feel more included please let one of the course staff know, either in person, via email/discussion board, or even in a note under the door. Our learning about diverse perspectives and identities is an ongoing process, and we welcome your perspectives and input.

We also expect that you, as a student in this course, will honor and respect your classmates, abiding by the UCSD Principles of Community. Please understand that others’ backgrounds, perspectives and experiences may be different than your own, and help us to build an environment where everyone is respected and feels comfortable.

If you experience any sort of harassment or discrimination, please contact the Office of Prevention of Harassment and Discrimination. Students may receive confidential assistance at the Sexual Assault Resource Center at (858) 534-5793 or Counseling and Psychological Services (CAPS) at (858) 534-3755.

Basic Needs

  • Are you eating properly?
  • Do you have adequate access to nutritious food?
  • Do you have stable housing?
  • Are you homeless or couch surfing?

If you or someone you know has food and/or housing insecurity, be aware of Basic Needs

  • The Triton Food Pantry (in the old Student Center), is free and anonymous, and includes produce.
  • Financial aid resources, the possibility of emergency grant funding, and off-campus housing referral resources are available.
  • CAPS and college deans can connect students to the above resources, as well as other community resources and support.