Communication Complexity tries to model one aspect of distributed computing.

See Communication Complexity

Let us consider two parties—Alice and Bob. They want to compute some function:

\begin{equation} f: \qty{0,1}^{*} \times \qty{0,1}^{ *} \to \qty{0,1} \end{equation}

against two inputs held by Alice and Bob respectively, \(x \in \qty{0,1}^{*}\) and \(y \in \qty{0,1}^{ *}\), where \(|x| = |y| = n\), where \(n\) is very large (i.e. just sending all of \(x\) over to the other party and compute \(f\) on one end isn’t good).

commutativity means that the same operation can be ran in any order.

That is:

\begin{equation} ABC = ACB \end{equation}

1. return < 0 if first value should come before second value
2. return > 0 if first value should come AFTEr second value
3. 0 if the first and second value are equivalent

A compiler complies code!

parts of compilers

lexical analysis

make stuff tokens — “identifying words”

an example!

if x == y then z = 1; else z = 2;

• if: keyword
• " “: white space
• x: identifier
• ==: relation

… and so on

parsing

abstract syntax treeifying the tokens — “identifying sentences”.

See parser.

semantic analysis

semantic analysis

optimization

make the IR faster — “editing”.

goals

• run faster
• use less memory
• generally, conserve resources

tricky tricky!

Can this be optimized to x=0?

cs143.stanford.edu

Lectures

• SU-CS143 APR012025
• SU-CS143 APR032025
• SU-CS143 APR152025
• SU-CS143 APR172025
• SU-CS143 APR242025
• SU-CS143 APR292025
• SU-CS143 MAY062025

Lexing

• What to do: SU-CS143 APR082025
• How to implement it: SU-CS143 APR102025

Logistics

• programming assignments: myth
• psets: gradescope
• labs: myth.stanford.edu
  • /afs/ir/class/cs143
• finals and midterms

Textbook: the purple dragonbook

Structure

• written assignments (2.5*4 = 10%)
• programming assignments (10+10+15+15 = 50%); 4 of them
  • lexer
  • parser
  • semantic analysis parse
  • code generator
• midterm (15%)
• final (25%)

Compiler we will Build

• lexer: strings -> tokens
  • built with Flex FSTs
  • smallest part of the code
• parser: tokens -> AST
  • built with Bison CFGs
  • linear time parsing!
• semantic analysis: AST
  • C++
  • check types + properties
  • fill in types for expressions in the tree
• [PA5: optimization - TBD]
• code generation: AST -> MIPS
  • C++
  • write MIPS
  • yay!

Emphasis: correctness over performance.