Welcome!

Who Are We?

Melissa O'Neill (“Prof. Melissa”)

• Office: Olin 1262
• Email: oneill@cs.hmc.edu (but use Piazza)
• Interested in systems areas, including
  • Programming languages
  • Operating systems
  • Parallel computing

Ben Wiedermann (“Prof. Ben”)

• Office: Olin Olin B161C
• Email: benw@cs.hmc.edu (but use Piazza)
• Interested in language design, including
  • Social consequences of language design
  • Whose needs have been ignored
  • Design vs Analysability

CS 131 one of our favorite classes to teach. Prof. Melissa is interested in all systems aspects of CS, every situation where people gleefully exclaim “It ran my program!”. Prof. Ben is excited about making programming languages and tools available to populations that are currently ill-served by our current ones. Profs. Melissa and Ben will also both happily chat about any of the topics in or related to the class, at length.:

Optimizing Our Time

We won't go over syllabus today, but it is REALLY IMPORTANT. The Read the syllabus! It has lots of important information, including:

• Course goals
• Attendance policies
• Late homework submission policy
• Early homework submission bonus
• How to get help

There are some useful rules for the course in the syllabus. But you can't take advantage of them unless you know they exist. Reading the sylabus will be part of the warmup assignment.

Survey Results

The background survey lets us see the big picture...

Self Presentation

(from "Quiet" to "Loud")

Attitude to Mistakes/Errors

(from "Hate mistakes" to "Like mistakes")

Feedback preference

(from "Be blunt" to "Be inquisitive")

Programming in Python

(from "Know nothing" to "Know lots")

Programming in Java

(from "Know nothing" to "Know lots")

Programming in C

(from "Know nothing" to "Know lots")

Programming in C++

(from "Know nothing" to "Know lots")

Programming in Standard ML

(from "Know nothing" to "Know lots")

Programming in Haskell

(from "Know nothing" to "Know lots")

Programming in Prolog

(from "Know nothing" to "Know lots")

Programming in Scheme / Racket / Lisp

(from "Know nothing" to "Know lots")

Programming in Lua

(from "Know nothing" to "Know lots")

Programming in Go

(from "Know nothing" to "Know lots")

Programming in D

(from "Know nothing" to "Know lots")

Using Unix from the command line

(from "Know nothing" to "Know lots")

Version control with Subversion

(from "Know nothing" to "Know lots")

Version control with Git

(from "Know nothing" to "Know lots")

Proof by Induction

(from "Know nothing" to "Know lots")

Formal Logic

(from "Know nothing" to "Know lots")

Lambda Calculus

(from "Know nothing" to "Know lots")

Working in Pairs

(from "Know nothing" to "Know lots")

I'm really excited about taking CS 131

Hopefully we'll have everyone feel excited!

I'm expecting to learn a lot in this class

• It's ok if you don't know all the languages. That's what is expected!
• There is no correlation betweeen grades and connections on the similarity graph.

Who You're “Most Similar” to...(?)

Wiki Extra: What are Programming Languages?

• Communication with a computer
• Use of an abstraction
• Description of a computation that we want a machine to perform

We Want This Class To Be Useful to Everyone

CS 131 is aiming at the big circle, not just people whose goal in life is to design or implement programming languages.

This picture vastly exaggerates the number of programmers who have gone on to invent successful general-purpose programming languages --- it's probably just a few dozen in the last 50 years.

Not our plan. But why not?

Week	Language
1	Haskell
2	C#
3	F#
4	Ruby
5	JavaScript
6	TypeScript
7	Clojure
8	Rust
9	Idris
10	Scala
11	Swift
12	Elixir
13	Go
14	D

Specific technologies come and go, but general principles can last your whole life. New programming languages arise all the time; you'll probably need many in your career that haven't even been invented yet.

Also, every time you start talking about a new programming language you have to spend a long time introducing all the little irritating details of syntax: where do the semicolons go, do you need curly braces or not, what are the keywords, can you have primes or question marks as part of variable names, etc.

Syntax details are absolutely crucial if you want to write code in a language, but these details aren't "interesting" or "deep," and are unlikely to help much when switching to other languages.

A Similar List from 1980...

Week	Language
1	Fortran
2	Lisp
3	Cobol
4	Algol
5	Snobol
6	BASIC
7	APL
8	PL/I
9	Mumps
10	Pascal
11	C
12	Modula-2
13	Ada
14	C with Classes

Folks who took a PLs class in 1980 probably aren't retired yet. But at best two of these languages are still in use today (and C++ is very different from its predecessor C-with-classes).

What do you think this sort of list would look like 40 year from now?

C. J. Date on Principles

What are we going to study?

• Not the tiny details from many specific programming languages since they may be obsolete in 20 years
• Higher level principles that stick around like binding variables, making trees, object oriented programming, anonymous functions...
• Processing symbolic data

The fuller quote is:

The point about principles is this: they endure. By contrast, products and technologies (and the SQL language, come to that) change all the time—but principles don't.... For example, suppose you know Oracle; in fact, suppose you're an expert on Oracle. But if Oracle is all you know, then your knowledge is not necessarily transferable to, say, a DB2 or SQL Server environment ... But if you know the underlying principles then you have knowledge and skills that will be transferable: knowledge and skills that you'll be able to apply in every environment and that will never be obsolete.

... The following quote—which is attributed to Leonardo da Vinci (1452-1519) and is thus some 500 years old—sums up the situation admirably: Those who are enamored of practice without theory are like a pilot who goes into a ship without rudder or compass and never has any certainty where he is going. Practice should always be based on a sound knowledge of theory.

Superficial differences, deeper similarities

\(x \,\mapsto\, x{+}1\)	math
\(\lambda x.\, x{+}1\)	logic
lambda x: x+1	Python
(lambda (x) (+ x 1))	Scheme/Racket
\x -> x+1	Haskell
[](int x) { return x+1; }	C++11
x => x+1	C#
(x) => x+1	Dart, JavaScript 6
{ x in x+1 }	Swift
fn x => x+1	SML
function x -> x+1	OCaml
function(x) { return x+1; }	JavaScript 5
Function[x,x+1]	Mathematica

It's interesting and deep that all of these languages have a way of representing anonymous functions (specifically the anonymous function that takes an integer and returns the next bigger integer). If you're comfortable with the idea of anonymous functions and functions-as data, then you can apply that understanding to any of these languages. It's just a simple matter of figuring out the exact sequence of characters expected by that language.

Conceptually, it's not "deep" why different languages use different sequences of characters to mean the same thing.

At best, there's "historical interest." Python and Racket use the keyword "lambda" because of the use of the actual greek letter \(\lambda\) by logicians starting in the 1930's and 40's. Haskell uses a backslash, which is 2/3 of the lambda character --- as close as we can get solely using ASCII art.

Tentative Order of Topics (subject to change)

Week	Topic
1	Introduction
2	Lambda Calculus
3	Functional Programming
4	Abstract Syntax and Interpreters
5	Closures and Scope
6	Parsing
7	Side-Effects
8	Types and Subtypes
9	Dispatch
10	Objects (with and without Classes)
11	Control Flow
12-13	Concurrency and Parallelism
14	Memory and Garbage Collection
15	Wrap up

Shouldn't real PLs show up somewhere, though?

Nearly all of the homeworks ask you to write Haskell code

We'll also encounter examples of

• Domain-specific languages (PostScript, pic, ...)
• Object-oriented languages (Java, C++, JavaScript, ...)
• Parallel languages (D, Go, ...)
• And more!

But why Haskell?

The Problem With Strings

If we want to process symbolic data (e.g., mathematical expressions), strings are a painful representation.

     "3.0 + x"
     "3.0 * y + 2 * exp(exp(x) + 7.0)"
     "3.0 * y + exp(2) * exp(x + 7.0)"
     "3.0 * x + exp (x * x + y)"

Why are strings a painful representation for processing symbolic data?

• Parsing characters one at a time means that you can't see the structure
• Symbols are characters and are not representative of the actual values

Better: Trees

A better way to represent symbolic data is with a tree!

Challenge: Using one of {Python, Racket, Java, C++, C}, write the code required to represent any such tree as data. How would you build trees for "2" or "2+x"?

Too easy? Add code that, given one of these trees, computes the derivative with respect to a variable (returning a new expression tree)

In class we came up with solutions like defining separate classes for the nodes of the tree, making a generic node with an assumed left and right node but all of these solutions were like trying to hammer in a screw.

Probably the simplest approach is to use Python or Racket and represent trees with nested lists,where we use numbers or strings for the base case of Num or Var nodes, and lists otherwise (with the first element of the list giving the label of the node, and the remainder of the list being the 1 or 2 subtrees)

For example, "2" would be represented as the python value 2 and "2+x" would be represented as the Python value ["Plus", 2, "x"]

and the last tree "3.0*x+exp(x*x+y)" would be

["Plus", ["Times", 3.0, "x"], ["Exp", ["Plus", ["Times", "x", "x"], 2.0]]]

Then if you weanted to "traverse" such a tree, you first check if the tree is a python number, python string, or python list; if it's a list, you can check the first string element to know the node label, and then recurse on the remaining list elements (subtrees).

---

But if you feel determined to have nodes represented as objects, then that could lead to much more complicated code, e.g.,

public interface Node { ... };

public class Num implementes Node { private double value; };
public class Var implements Node { private String varname; };
public class Plus implements Node { private Node left; 
                                    private Node right;};
public class Times implements Node { private Node left; 
                                     private Node right;};
public class Exp implements Node { private Node exponent; };

plus all the constructors and other code that would let you say

  new Num(2.0)

and

  new Plus(new Num(2.0), new Var("x"))

and

  new Plus(new Times(new Num(3.0), new Var("x")),
           new Exp(new Plus(new Times(new Var("x"), new Var("x")), 
                            new Num(2.0))))

Even this isn't so bad, but the code to implement tree traversal would be even longer...

You could do something in similar in Python, perhaps even simplifying the number of classes because we don't have to worry about types (although that means we don't have any confirmation that our trees are not broken). Doing all this in C would probably be a disaster.

If we wanted to do the bonus part of the question, trying to compute the derivative would be even harder -- accounting for rules like the produce rule would get very complicated.

My Haskell Solution

Luckily, there is a more simple implementation in Haskell that uses pattern matching instead of many classes that makes computing the derivative easy.

Haskell is a means, not an end. CS 131 has all sorts of examples of tree-structured data, and so we want to choose a language (like Haskell or Standard ML or OCaml; we picked Haskell this semester) that lets us create and manipulate trees easily.

It's always a good idea to pick a language based not on fashion, or what you happen to have been using lately, but based on whether it is a good match for the specific problem to be solved.

Nodes

This creates a new type "Expression" of expression trees. There are only five possible labels for nodes in these trees; we just list them.

Children

For each possible node label, we specify what sort of children it has -- one string, one double-precision floating-point value, two Expressions subtrees, or a single Expression subtree.

3.0_x + exp(x_x + y)

We just specify the root, and recursively the values of the children.

Computing Symbolic Derivatives

The nice thing about Haskell is that it is really easy to write functions that do different things for different kinds of trees.

If it's a binary tree with the Plus label at the root, we apply the rule for the derivative of a sum. If it's a binary tree with the Times label at the root, we instead apply the product rule.

If it's a unary tree with the Num label at the root, we know the derivative is zero. Since the result of this function is always supposed to be a symbolic expression (represented as a tree), we represent the symbolic expression zero by the tree that has Num at the root and the floating-point value 0.0 as its child.

Wiki Extra: Back to Programming Language Principles

Mental Chunking

This is hard to remember:

        CIAD HSF BIAT FNSA

Remembering multiple nonsense words (or equivalently, 15 letters in no meaningful order) is hard.

These might be much easier

        CIA DHS FBI ATF NSA

It's much more likely that in a few days or weeks you can remember some of these government agencies, even though it's exactly the same 15 letters as above!

Chunking of Code

   for (int i = 0; i < 10; ++i) {
     x += i;
   }

What does an experienced C/Java programmer see?

A loop that counts up from 0 to 9; adding each index value to an accumulator.

What might a novice student see?

Let's see. There's the "for" keyword; I think that's a loop. It's creating a variable for some reason, and assigning 0 to that variable. Why are there two pluses in a row? Why is there a semicolon on after i < 10 but not after ++i? Oh god, there are parentheses and curly braces here; why the difference? and so on...

Big Idea: Languages Can Be Further Chunked

• Racket (Scheme) is a statically scoped, dynamically typed, higher-order, eager, functional language.

• Emacs Lisp is a dynamically scoped, dynamically typed, higher-order, eager, functional language.

This tells us that Racket and Emacs Lisp are similar in many ways, and when switching back and forth we mainly have to be careful about scoping.

• Standard ML is a statically scoped, statically typed, polymorphic, higher-order, eager, functional language.

So Standard ML is more like Scheme than like Emacs Lisp. Good to know.

• Haskell is a statically scoped, statically typed, polymorphic, higher-order, lazy, purely functional language.

And Haskell and Standard ML are very similar in philosophy, except for eagerness vs. laziness.

• Ruby is a statically scoped, dynamically typed, single-inheritance (with mixins), object-oriented, (mostly) class-based, object-oriented, imperative language.

Ruby has some similarities to the above functional languages, but a lot of differences. But it's single-inheritance, which is more like Java than like C++.

---

In general, by learning the things to look for --- ideas that recur in programming languages, or for which there's a small menu of choices made by each language --- you can look at a new programming language, quickly recognize most of the language (scoping behavior, evaluation behavior, parameter-passing behavior, etc.) and then focus in on learning the "weird" parts of the specific language.

-- MelissaONeill - 26 Jan 2020