CS374: Principles of Programming Languages

Bill Mongan

Welcome to CS374!

About Me

• Born in Delaware County, PA
• Upper Darby High School Class of 2000
• Drexel University Class of 2005; PhD at Drexel in 2018
• Married in Carmel, CA in 2015

About Me

• I am a private pilot who loves to travel
• We love animals and have two cats … plus some occasional visitors!

About Me

• I use computing (specifically Machine Learning and Signal Processing)…
  • To improve public health
  • To leverage technology to mitigate side-effects and to improve access to care

What this Course is About

int main(void) {
    int y = 5;
    int y2 = y * y;
    printf("%d squared is %d.", y, y2);
}

• What does this program do? How did you know what a “statement” is?

What this Course is About

(define square
  (lambda(n)
    (* n n)
  )
)
      
(square 5)

• How about now?

What this Course is About

movl	$5, -4(%rbp)
movl	-4(%rbp), %eax
imull	%eax, %eax
movl	%eax, -8(%rbp)
movl	$0, %eax

li	$2,5
sw	$2,0($fp)
lw	$2,0($fp)
mul	$2,$2,$2
sw	$2,4($fp)

• Same program, two assembly dialects. What is the same? What is different?

What this Course is About

00100000000010100000000000000101 # li t2 5
10101111110010100000000000000000 # sw
10001111110010100000000000000000 # lw
00000001010010100000000000011000 # mult
00000000000000000101000000010010 # mflo t2
10101111110010100000000000000100 # sw 4(fp)

What this Course is About

• The evolution of programming languages from assembly language to intermediate languages to our favorite high level languages

• The provenance of modern conveniences
  • Conditionals and Loops

• Programming paradigms

• Algorithms that read, translate, and execute code

Class Logistics and Culture

• Class website and syllabus: http://www.billmongan.com/Ursinus-CS374
• Challenging but fun!
• Communicate with me and the TA’s often - we enjoy it.
• If you know stuff, use it for good to help others!

How Today Works (no experience assumed)

You do not need to write any code today. Bring curiosity and a laptop; today is discussion and paper-and-pencil tracing.

• No setup required now. The container, git, and Python toolchain come later — the Development Environment tutorial walks you through it, and the Overview assignment that needs it goes out Thursday.
• You will read notations before you build them. Every topic this semester arrives twice: first as something you can read, then as something you implement.
• Ask the obvious question. If a term is new, say so — the person next to you is wondering too, and naming it is exactly the participation this course grades.

Welcome: Why Study Programming Languages?

Every programmer uses languages, but few understand why they work the way they do — or how to evaluate a new one quickly.

Studying programming language theory is like learning music theory: you can play guitar without it, but understanding harmony, rhythm, and form lets you compose music rather than just repeat what you’ve heard.

This course gives you the composer’s toolkit — you’ll read languages, compare them, and ultimately build one from scratch. The companion reading The Arc of This Course: From Symbols to Languages previews every destination on that map; today we take the first step.

Where This Course Is Going

By December, your team will have built a programming language of your own: a lexer, a parser, and an interpreter, assembled from components you write one assignment at a time. Today we ask why that journey is worth taking. We move from what a language is → why languages differ → the pipeline from text to behavior → how this course works.

Before You Begin: this activity assumes you can write and run a basic Python script (loops, functions, list comprehensions), describe what a function call does at a high level, and read a simple regular expression like \d+. If any of these feel shaky, review them first.

Directions and Group Roles

Throughout this course, we work in POGIL-style teams of three or four with rotating roles:

• Manager: keeps the team on task and watches the time.
• Recorder: writes the team’s answers on the Class Activity Questions discussion board.
• Presenter: reports the team’s findings to the class.
• Reflector: notes what helped or hindered the team, and shares one observation at the end.

Consider each model below and answer the questions provided. First reflect on your own briefly, then discuss and compare with your group. Report out on areas of disagreement. After class, respond to the reflective prompt individually in your notebook.

1. Languages All the Way Down

A programming language is a precise notation for computation. It is an agreement among three parties: the human who writes, the machine that executes, and, most often forgotten, the other humans who read. Every language is a set of design decisions about syntax (what programs look like), semantics (what programs mean), and pragmatics (what programs are easy or hard to express).

You already speak several. Python, probably Java or C, perhaps SQL or regular expressions; each made different choices. Studying principles of programming languages means learning the design space itself.

1. Languages All the Way Down: Three Payoffs

First, you become a better programmer in every language, because you see through syntax to the semantics beneath.

Second, you become able to build languages: configuration formats, query languages, and domain-specific notations are everyday engineering artifacts.

Third, you join an intellectual tradition connecting logic, linguistics, and computing, from the lambda calculus of the 1930s to the languages being designed this year.

Model 1: One Idea, Four Notations

Intuition: Think of the same recipe written in four different styles — a traditional French cookbook, a quick-reference cheat sheet, a flowchart, and a voice command to a smart speaker. The dish comes out the same, but each style reflects different assumptions about who’s cooking and what they already know. The four code snippets that follow do the same arithmetic, but each reveals a different programming paradigm — a different mental model for organizing computation.

Model 1: One Idea, Four Notations

The same computation — summing the squares of the even numbers in a list — in four notations:

Comprehension (declarative):

nums = list(range(1, 11))
total = sum(x*x for x in nums if x % 2 == 0)
print(total)  # 220

Imperative (explicit state):

total = 0
for x in nums:
    if x % 2 == 0:
        total += x * x
print(total)  # 220

Model 1: One Idea, Four Notations

Continuing with the same nums:

Object-oriented:

class EvenSquares:
    def __init__(self, data): self.data = data
    def total(self):
        return sum(x*x for x in self.data if x % 2 == 0)

print(EvenSquares(nums).total())  # 220

Scheme-style functional:

from functools import reduce
even = filter(lambda x: x % 2 == 0, nums)
squared = map(lambda x: x * x, even)
print(reduce(lambda a, b: a + b, squared, 0))  # 220

Critical Thinking Questions

1. For each version, identify what the programmer must keep track of (loop counters, intermediate state, nothing?). Which version says what to compute and which says how?

2. Rank the four for readability by a newcomer, and separately for your own confidence that each is correct. Did the rankings differ? Why might they?

3. The Scheme-style version is built from three reusable pieces (filter, map, reduce). Identify the analogous pieces hiding inside the comprehension.

Critical Thinking Questions

1. Propose one computation that would be awkward to express declaratively but easy imperatively. What does that suggest about general-purpose versus domain-specific languages?

Watch out! “Declarative” does not mean “shorter.” A SQL query can be more verbose than an equivalent Python loop. Declarative means you describe what result you want, not the steps to produce it. Don’t confuse conciseness with paradigm.

2. From Text to Behavior: The Pipeline

Every implementation answers the same question: how does this string of characters become behavior? The classical pipeline, which is also the skeleton of this course and of your project, proceeds in stages:

The lexer (scanner) groups characters into meaningful units called tokens, using the machinery of regular expressions and finite automata. The parser assembles tokens into a tree according to a grammar.

2. From Text to Behavior: The Pipeline

The interpreter walks the tree, computing values within environments that give names their meanings. A compiler shares the front half and differs at the back, emitting code instead of computing values; we focus on interpretation, and the principles transfer.

What flows through the pipeline is built from each language’s primitives: its values (numbers, strings, booleans), the operators that combine them (+, <, and), and the forms that structure behavior (assignment, selection, iteration, function application).

Every language is some choice of primitives plus rules for composing them; the Type Systems and Control Flow activities make those choices precise.

2. Check Your Understanding

In the pipeline above, the component whose job is to decide that the characters c, o, u, n, t form a single identifier token is:

• The lexer
• The parser
• The interpreter
• The operating system

The lexer. Grouping characters into tokens is exactly its job; every later stage sees tokens, never raw characters.

Model 2: Be the Pipeline

Intuition: Imagine a customs officer at an airport breaking your passport down into individual fields — name, date of birth, nationality — before any decision gets made. The lexer does exactly that: it reads a raw stream of characters and groups them into labeled chunks (“this is a number,” “this is a variable name”) so the later stages never have to squint at raw text again. In this model you’ll write a tiny version of that officer.

Consider the source text: total = 3 + price * 2

Model 2: Be the Pipeline

A minimal Python tokenizer — watch the pipeline live:

import re

source = "total = 3 + price * 2"

TOKEN_SPEC = [                      # (type, pattern)
    ("NUMBER",  r"\d+(\.\d*)?"),
    ("IDENT",   r"[A-Za-z_]\w*"),
    ("ASSIGN",  r"="),
    ("PLUS",    r"\+"),
    ("STAR",    r"\*"),
    ("WS",      r"\s+"),
]

master = "|".join(f"(?P<{name}>{pat})" for name, pat in TOKEN_SPEC)
tokens = []
for m in re.finditer(master, source):
    kind = m.lastgroup
    if kind != "WS":
        tokens.append((kind, m.group()))

for tok in tokens:
    print(tok)

Model 2: Critical Thinking Questions

1. As a team, list the tokens the lexer produced. How many are there? Did anyone’s count differ?

2. The interpreter must compute price * 2 before adding 3. Where in the pipeline is that ordering decided: the lexer, the parser, or the interpreter? Defend your answer.

3. Suppose the text were total = 3 + * 2. At which stage should the error be caught, and what should a helpful error message say?

Model 2: Be the Pipeline

Watch out! The lexer cannot catch all errors — it only sees one token at a time and has no memory of what came before. total = 3 + * 2 contains five perfectly valid tokens; the sequence is illegal. Only the parser, which knows the grammar rules about how tokens may be combined, can flag that two operators in a row is a syntax error.

Model 3: Python’s Own Pipeline

Intuition: You’ve been using Python as a black box — type code in, get output out. Here we open the lid and watch Python process its own source code stage by stage, the way a mechanic puts a car on a lift. Python uses the very same pipeline you just traced by hand, and you can inspect every stage of it.

import ast, dis, tokenize, io

source = "total = 3 + 2 * 5"

Model 3: Python’s Own Pipeline

# Stage 1: Tokens
tokens = list(tokenize.generate_tokens(io.StringIO(source).readline))
for tok in tokens:
    if tok.type not in (tokenize.NL, tokenize.NEWLINE, tokenize.ENDMARKER):
        print(f"  {tokenize.tok_name[tok.type]:10} {tok.string!r}")

# Stage 2: AST
tree = ast.parse(source)
print(ast.dump(tree, indent=2))

# Stage 3: Bytecode (compiled)
code = compile(source, "<string>", "exec")
dis.dis(code)

Watch out! Python is both compiled and interpreted: it compiles source to bytecode, then a virtual machine interprets that bytecode. When we say “interpreter” in this course, we mean the tree-walking variety that reads an AST directly.

Model 3: Critical Thinking Questions

1. How many tokens does Python produce for total = 3 + 2 * 5? Which token is the operator precedence information not encoded in (it appears in the AST instead)?

2. The AST shows a BinOp with Mult nested inside Add. How does the tree encode precedence without any explicit precedence rules?

3. The bytecode shows BINARY_OP instructions. These are the output of Python’s compiler. What is the input to an interpreter, by contrast?

3. How This Course Works

The first half of the semester builds your skills bottom-up through scaffolded individual assignments: regular expressions, automata, a lexer, a parser, an interpreter.

In the second half, your team snaps those components together into a language of your own design, developed in sprints with rotating roles, a gallery walk peer review, and a public Demo Day. Along the way we study languages as artifacts (Scheme, the lambda calculus, modern features) so your design choices are informed by sixty years of others’ choices.

Reflection Prompt

In your notebook: describe one moment when a programming language fought you — when the thing you wanted to say was hard to express. Knowing you will design a language this semester, what would you change to make that moment easier? And after seeing Python’s own tokens/AST/bytecode pipeline, does Python feel more or less like magic to you?

Further Reading

• Douglas Thain. Introduction to Compilers and Language Design (2nd ed.), Chapter 1. Our pipeline, named and framed.
• Shriram Krishnamurthi. Programming Languages: Application and Interpretation (online). The interpreter-first philosophy we follow.
• Robert Nystrom. Crafting Interpreters (online), “A Map of the Territory.”
• The ast module docs: help(ast) in Python shows every node type you’ll encounter.

Up next: the Programming Paradigms activity tours the worldviews your language could adopt — and the Overview and Warmup assignments begin the journey.