Prabhakar Ragde's flâneries
This page collects some recent longform pedagogical writing that I
hope will be of interest. The word "flânerie" simply means "stroll",
but I use it to evoke the German cultural critic Walter Benjamin
(18921940), who elevated wandering through sophisticated urban
environments to an art form. Freed from the pressures of the credit
system, course material can become a voluntary pleasure, a guided
walk through an interesting quarter. The works below are shorter and
more informal than a textbook, but longer and more polished than a
typical blog post. I'm happy to take suggestions for improvement.
Currently available:
Scroll down for brief descriptions, or click through for full materials.
Wishful thinking: Functional Lexing And Parsing. Not even a
description on this one.
An introduction to CS for those who have never programmed before, or
who have done some programming in imperative languages, based on my
offerings of the courses CS 145, CS 146, and Math 642. These
courses were originally designed for students with mathematical
aptitude and enthusiasm for the subject. Programming examples and
exercises use the Racket teaching languages, as well as full Racket.
The lost preludes of FICS
I used to start CS 145 (an "advanced" first course in CS,
last taught by me in 2014) with a lecture using Haskell as
functional pseudocode. In 2020 I reimagined that lecture using
Agda. This material is not properly part of FICS,
but you may find it amusing.
Contents:
 Part I: The Functional Paradigm (draft completed)
 Introduction to the Racket teaching languages.
 Syntax and semantics.
 Structures: natural numbers, lists.
 Functional abstraction.
 Efficient representations of numbers.
 Trees.
 Generative recursion.
 Interpreters.

Part II: The Imperative Paradigm (draft completed)
 Introduction to full Racket.
 Impurity.
 High level: the SIMP language.
 Intermediate level: the PRIMP language.
 Low level: the FIST language.
 Implementing functional languages.
 Control.
 Continuations.
A rapid introduction to the basics of programming in full Racket,
intended for mature programmers.
Contents:
 Basics: getting started; programs, expressions, values;
definitions; style; conditional expressions; recursion; compound
data; modules; testing.
 Pure Functional Programming: lambda; higherorder functions;
local variables; pattern matching.
 Impure Functional Programming: input and output; mutation.
 Advanced Racket (to be written): iterations and
comprehensions; regular expressions; exceptions; prompts and
continuations; concurrency; macros; Typed Racket.
An introduction to C from a Racket perspective,
based on optional material from my course CS 146.
Not as passionate or inventive as other material here,
but I tried to do a decent job.
Somewhat shorter than TYR.
Contents:
 Getting started: C compilers, commandline environments,
editors, optional textbooks.
 Introduction: basic statements, types, separate
compilation, loops, running time analysis, testing.
 Pointers: structures, pointers, NULL, heap allocation,
queues, arrays.
 Intermediate C: pointer arithmetic, strings,
reading Sexpressions, tree representations, mergesort,
binary search, enforcing abstraction.
A modern reimagining of data structures focussing on
immutability and persistence, based on my offerings of
the course CS 240E, and aimed at those who have done some programming
in imperative or functional languages (such as covered in TYR or
FICS). Programming examples and exercises use the OCaml language.
Contents:
 Preliminaries: tools of algorithm analysis, introduction to OCaml.
 Sequences: lists, arrays, Braun trees.
 Simple queues: one list, two lists, streams (amortized analysis).
 Priority queues: Braun heaps, arraybased heaps, maxiphobic heaps.
 Sets and maps: a unifying framework covering treaps, AVL trees,
weightbalanced trees, and redblack trees; binary tries.
 Text processing: simple exact matching; suffix trees; suffix
arrays.
 Hashing: chaining; open addressing; cuckoo hashing; perfect
hashing.
An introduction to logic and program verification for computer
scientists via intuitionistic type theory, based on my offerings of
the course CS 245E. The reader will write the majority of the code
for a very small proof assistant, Proust, before we move to
introductions to the much more fullfeatured Agda and Coq software
systems. Required background: some experience in programming in
imperative or functional languages (such as covered in TYR or
FICS). Programming examples and exercises use full Racket.
There are also some exercises in Agda and Coq.
Contents:
 Propositional logic.
 Formulas.
 The Boolean interpretation.
 Proof for the implicational fragment.
 Proofs as programs.
 Proust for implication.
 Adding the other logical connectives.
 Intuitionistic vs classical logic.
 Predicate logic.
 An overview of firstorder logic.
 The advantages of higherorder logic.
 Universal quantification and dependent types.
 Equality.
 Booleans.
 Natural numbers and arithmetic.
 Existential quantification.
 Proof assistants.
 Common features.
 Agda: from nothing, logic, ordering, equality, numbers,
sorting, data structures.
 Coq: Booleans, logic, numbers, inductivelydefined
propositions, sorting.
Functional Lexing And Parsing (FLAP)
A planned collection of ideas I've scattered into various courses
over the years, along the lines of the works above,
and including material from my offering of CS 842 in fall 2012.
Unlike the above technical works on computer science,
this is about Eurorack synthesizer modules
used for the creation of music and interesting sounds.
Though the subject matter is different from the works above,
this is very much in the same spirit,
in that it is aimed at the relative beginner,
and focusses on a small but rich universe.
After a brief introduction,
the second chapter looks at a single module,
introducing concepts through an explanation of its parts
and what can be done with it through selfpatching.
The third chapter brings in more ideas
through an examination of modules currently resident in my rack.
This short flanerie explores the mathematics behind some
techniques in audio synthesis, using free software
that simulates Eurorack.
It is aimed at university students in their first year of study.
Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario,
Canada N2L 3G1
plragde at uwaterloo.ca