CS374 Course Overview

CS374: Principles of Programming Languages

Bill Mongan

Welcome to CS374!

About Me

Born in Delaware County, PA
Married in Carmel, CA in 2015

About Me

Upper Darby High School Class of 2000
Drexel University Class of 2005
Completed my PhD at Drexel in 2018

About Me

I am a private pilot who loves to travel

About Me

We love animals and have two cats
… plus some occasional visitors!

About Me (cont.)

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

What do you think this does?

What this Course is About

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

How about this? What’s different about this version?

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

What this Course is About (cont.)

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!

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.

Welcome: Why Study Programming Languages? (cont.)

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.

Welcome: Why Study Programming Languages? (cont.)

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.

Learning Goals

By the end of this activity, you will be able to:

Identify the three parties involved in every programming language (author, machine, and reader) and explain the role each plays
Compare at least three distinct programming languages by describing the specific design choices that differentiate their syntax and semantics

Learning Goals (cont.)

Trace the pipeline from source text to program behavior, naming each stage and its input/output
Explain the trade-offs a language designer faces among expressiveness, safety, and machine efficiency
Classify a given code snippet by the paradigm it primarily represents and justify that classification

Learning Goals (cont.)

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.

Learning Goals (cont.)

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 — arguments in, return value out

Read a simple regular expression like \d+ and say what it matches

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.

Directions and Group Roles (cont.)

Presenter: reports the team’s findings to the class.
Reflector: notes what helped or hindered the team, and shares one observation at the end.

Directions and Group Roles (cont.)

Consider each model below and answer the questions provided. First reflect on the questions on your own briefly, before discussing and comparing your thoughts with your group. Report out on areas of disagreement or items for which your group identified alternative approaches. 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).

1. Languages All the Way Down (cont.)

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, so that the next language you meet (or invent) is a configuration of familiar choices rather than a new world.

1. Languages All the Way Down (cont.)

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

1. Languages All the Way Down (cont.)

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 below do the same arithmetic, but each reveals a different programming paradigm — a different mental model for organizing computation.

Model 1: One Idea, Four Notations (cont.)

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

Model 1: One Idea, Four Notations (cont.)

Python (imperative/functional blend):

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
total = sum(x*x for x in nums if x % 2 == 0)
print(total)  # 220

Model 1: One Idea, Four Notations (cont.)

Python OO style:

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

class VowelCounter:  # reusing class structure for illustration
    def __init__(self, data): self.data = data
    def sum_even_squares(self):
        return sum(x*x for x in self.data if x % 2 == 0)

vc = VowelCounter(nums)
print(vc.sum_even_squares())  # 220

Model 1: One Idea, Four Notations (cont.)

Scheme-style functional (Python simulation):

from functools import reduce

nums = list(range(1, 11))
even = list(filter(lambda x: x % 2 == 0, nums))
squared = list(map(lambda x: x * x, even))
total = reduce(lambda a, b: a + b, squared, 0)
print(total)  # 220

Model 1: One Idea, Four Notations (cont.)

All four approaches — same answer, different mental models:

nums = list(range(1, 11))

# Imperative: explicit state
total_imp = 0
for x in nums:
    if x % 2 == 0:
        total_imp += x * x

Model 1: One Idea, Four Notations (cont.)

# Functional: composition
from functools import reduce
total_func = reduce(lambda a,b: a+b, map(lambda x: x*x, filter(lambda x: x%2==0, nums)), 0)

# Comprehension: declarative
total_comp = sum(x*x for x in nums if x % 2 == 0)

Model 1: One Idea, Four Notations (cont.)

print(f"Imperative: {total_imp}")
print(f"Functional: {total_func}")
print(f"Comprehension: {total_comp}")
print(f"All equal? {total_imp == total_func == total_comp}")

Critical Thinking Questions

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

Critical Thinking Questions (cont.)

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

Critical Thinking Questions (cont.)

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

Critical Thinking Questions (cont.)

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:

\[\text{characters} \xrightarrow{\text{lexer}} \text{tokens} \xrightarrow{\text{parser}} \text{syntax tree} \xrightarrow{\text{interpreter}} \text{value}\]

2. From Text to Behavior: The Pipeline (cont.)

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 (cont.)

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.

2. From Text to Behavior: The Pipeline (cont.)

What flows through this pipeline is built from each language’s primitives — the small set of atoms the language treats as given rather than defined:

2. From Text to Behavior: The Pipeline (cont.)

its primitive values (numbers, strings, booleans), the operators that combine them (+, <, and), and the forms that structure behavior (assignment, selection, iteration, function application).

2. From Text to Behavior: The Pipeline (cont.)

Every language in this course — and the one your team designs — is some choice of primitives plus rules for composing them; the Type Systems and Control Flow and Statement Semantics activities are where those choices get made precise, one primitive at a time.

2. From Text to Behavior: The Pipeline (cont.)

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

2. From Text to Behavior: The Pipeline (cont.)

The interpreter
The operating system

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 (cont.)

A minimal Python tokenizer — watch the pipeline live:

import re

source = "total = 3 + price * 2"

# A simple token spec: (type, pattern)

Model 2: Be the Pipeline (cont.)

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

Model 2: Be the Pipeline (cont.)

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()))

Model 2: Be the Pipeline (cont.)

for tok in tokens:
    print(tok)

Model 2: Be the Pipeline (cont.)

Critical Thinking Questions

As a team, list the tokens the lexer produced. How many are there? Did anyone’s count differ?
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.

Model 2: Be the Pipeline (cont.)

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 (cont.)

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. In this model you’ll open the lid and watch Python process its own source code step by step, the same way a mechanic puts a car on a lift to show you what’s happening beneath the hood. Seeing Python’s actual tokens, AST, and bytecode demystifies the interpreter and previews exactly what you’ll build in your own project.

Model 3: Python’s Own Pipeline (cont.)

Python itself uses the same pipeline. You can inspect every stage:

import ast, dis, tokenize, io

source = "total = 3 + 2 * 5"

# Stage 1: Tokens
print("=== 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}")

Model 3: Python’s Own Pipeline (cont.)

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

Model 3: Python’s Own Pipeline (cont.)

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

Model 3: Python’s Own Pipeline (cont.)

Critical Thinking Questions

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

Model 3: Python’s Own Pipeline (cont.)

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

Model 3: Python’s Own Pipeline (cont.)

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

Model 3: Python’s Own Pipeline (cont.)

Watch out! Python is both compiled and interpreted: it compiles your source to bytecode (the .pyc files), 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 — not CPython’s bytecode VM. Both are interpreters in spirit; just be clear which level you’re describing.

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.

3. How This Course Works (cont.)

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.

4. Exercises

Language autobiography. List every programming language and notation (count spreadsheets and regex!) you have used. For each, one sentence: what was it good at?
Notation hunt. Find one notation in daily life that has a syntax and a semantics but is not usually called a programming language (music notation, knitting patterns, chess notation). The Presenter shares the team’s best example.

4. Exercises (cont.)

Tokenizer extension. Extend the minimal tokenizer above to also recognize (, ), -, /, and floating-point numbers like 3.14. Test it on result = (a - 3.14) / b. How many tokens does it produce?
Pipeline trace. Manually trace the three stages of the pipeline for the expression 2 * (x + 1): list tokens, draw the parse tree, and show the evaluation order.

4. Exercises (cont.)

Team charter. Draft your team’s working agreement: role rotation, communication, preparation norms, and disagreement resolution. The Recorder posts it.

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?

5. 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.

5. Further Reading (cont.)

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.

5. Further Reading (cont.)

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