Skip to main content Link Search Menu Expand Document (external link)

Lecture 01

2022-09-26 | Week 1 | by Matt Wang

Heya! Matt here. This lecture note covers the entire intro slide deck). If you have feedback on how this is done, please let me know!

(he’s also almost done, but not quite!)

Table of Contents

Logistics

tl;dr: please read the syllabus and check out the core resources, including:

Unfortunately, no extra enrollment (PTEs, waitlists) can be accomodated at this time. It’s okay! CS 131 is taught in Winter and Spring, and Carey plans on teaching it again in the Spring!

The slides also have shoutouts for many people who helped out!

from left-to-right, top-to-bottom: Alan Kay, Angelina Lue, Devan Dutta, James Wu, Kevin Tan, Maggie Li, Matthew Wang, Paul Eggert, Timothy Gu, Todd Millstein

What is CS 131?

The goal of 131 is not to teach you every programming language! Instead, we want to understand the core paradigms and building blocks that go into languages, and the tradeoffs that languages make. Then, you can pick up new languages super quickly!

Some examples of paradigms and building blocks:

  • functional programming
  • object-oriented programming
  • type systems
  • memory management
  • and many, many, many, more!

Practically, we’ll be learning Python, Haskell, and Prolog - the former two quite in-depth!

Along the way, we’ll learn tiny tidbits of these paradigms and building blocks in other languages - like Rust, Go, Scala, and of course, C and C++!

To test your knowledge, we’ll have:

  • a project where you build your own interpreter for a custom language!
  • 8 homeworks, which are graded on effort
  • a midterm and a final exam!

There is no textbook for the class (the slides + notes will be that resource). Be careful with using online resources - terminology differences mean that sites like StackOverflow can be incorrect! Carey recommends some resources:

Programming Languages

What is a programming language? Carey’s definition:

A programming language is a structured system of communication designed to express computations in an abstract manner.

There are many other definitions, but we like this one! Our focus is going to be on “high-level” programming languages, which are generally human-readable and implement most languages we care about :)

There’s some wonderful history about programming languages - including Grace Hopper’s pioneering work in creating the first compilers and the first human-readable language (COBOL) - I would recommend reading more about Grace Hopper (or coming to my discussion!).

Why Variety?

As you’re probably aware, there are many, many programming languages. At the end of the quarter, we’ll make an interpreter for our very own!

But, why? Well, different languages tend to be good at different things. Some programming languages are better suited towards solving different problems.

In class, we went through taking on a creating a spell checker.

spec for smart spellchecker

Even though this sounds complicated, we can implement a simple solution in Python:

import re

def spell_check(s, d):
 return {w for w in [w for ln in essay for w in re.split(r'[. ,!;"]',ln)]
                 if w.lower() not in d and w != ''}

This is pretty concise for a seemingly-hard problem! Part of this comes from Python’s design decisions - a powerful standard library and functional features like list comprehensions!

(in other languages, like Java, the solution is probably more verbose!)


The Tiobe Top Ten is one metric for looking at the most popular languages - though there are many!

Paradigms

We are going to explore four key paradigms in programming languages.

Imperative languages are all about statements. Programs are one statement after another; you can use loops to control statements, change variable values, etc. You have used many imperative languages!

Here’s a loop in C that exhibits imperative properties:

int a = 0;
while (a++ < 100)
  cout << a << endl;

Object-oriented languages are all about objects. Programs are organized into classes and objects which send messages (i.e. method calls) to each other. You’ve used several of these too!

Modern OOP syntax derives heavily from Smalltalk:

class Dog { ... };

Functional languages are all about functions. Programs are just compositions of functions (expressions!). Importantly, there are no statements or iteration - the bread and butter of functional programming is recursion!

We’ll learn Haskell this quarter:

f(n) = if n > 0 then n * f(n - 1) else 1

Logic languages are all about facts. You can define rules about facts, and query your existing facts. Logic languages are uncommon, but a whole new approach to problem solving!

Here’s a Prolog example:

like(dogs, meat), category(beef, meat)
likes(A,C): if like(A,B) and category(C, B)
likes(dogs, beef)?

Many languages mix paradigms!

  • C++ is imperative and object-oriented (with … some functional elements)
  • Scala is object-oriented and functional

You might ask - I haven’t used Functional or Logic languages. Why are we learning these?

  • functional programming is common in almost every modern language - from JS and Python to C++ and Java!
  • while you won’t use logic programming in your job (probably?), it teaches you a whole new way of thinking :)
  • and, Matt says, lots of problems are best solved with multiple paradigms - the more tools in your toolkit, the better!

Building Blocks and Dimensions

Beyond these paradigms, there are many other dimensions that separate programming languages.

Several we’ll look at in this class are:

  • type systems: static versus dynamic
  • parameter passing: by value, reference, pointer, object reference, name
  • scoping: lexical versus dynamic
  • memory management: manual versus automatic
  • and more!

Each language - like C++ or Python - makes (different) decisions in what to do. In turn, this affects the behaviour of the language, and what kinds of problems they solve!

There are some dimensions with bite-sized scopes and pro-cons.

Variable assignment: can you declare before assignment?

  • axis: how verbose do you want your code to be?
  • axis: when do you want to detect errors (runtime versus compile time)

Implicit type conversions: should the programming language convert types for you?

  • axis: how simple do you want your code to be?
  • axis: what bugs are you okay with?

Array bounds checks: should the language check if an array index is in-bounds?

  • axis: performance!
  • axis: nasty memory bugs :(

Exercise: Classify that Language

(this is one of Matt’s favourite parts of this class!!)

Let’s sketch out our approach to learning more about languages. Let’s look at this language that we’ve totally never seen before:

class Student:
 ...  # details hidden

# student goes through life changes
def life_changes(s: Student):
 s.change_major("Econ")
 # hates life choices, so starts from scratch
 s = Student("Carence", "Music")

# main program
student1 = Student("Carey", "CompSci")
life_changes(student1)
student1.print_my_details();

When we run the program, it prints Carey's major is Econ..

The big question: How does this language pass parameters?

  • By value?
  • By reference?
  • By pointer?

Let’s do some sleuthing!!

  • It printed Econ. So, s.change_major does actually change the s value. In particular, it’s not passing by value - that creates a copy!
  • It printed Carey. So, the last assignment in life_changes - s = Student(...) - didn’t change the origianl object! In particular, that means s is a pointer, not a reference!
  • So, it’s passing by pointer! (okay, in Python - the language, this is called passing by object reference, but we were pretty close)

We’ll do more of these every week! And, by the end of the quarter, you’ll be able to do this on your own - every time you see a new language!

Language Tooling

Matt here - this part is coming soon, but it’s not the priority of this lecture. You won’t be tested on this material!