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 (1892-1940), 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:

• A Functional Introduction to Computer Science (FICS), Part I and Part II, as well as its lost preludes),
• Teach Yourself Racket (TYR),
• If You Must Learn C (IYMLC),
• Functional Data Structures (FDS),
• Logic And Computation Intertwined (LACI),
• A Functional Introduction to Modular Synthesis (FIMS).
• The Sound of Math (TSOM)

Wishful thinking: Functional Lexing And Parsing. Not even a description on this one.

A Functional Introduction to Computer Science (FICS)

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

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.

Teach Yourself Racket (TYR)

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; higher-order 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.

If You Must Learn C (IYMLC)

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, command-line 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 S-expressions, tree representations, mergesort, binary search, enforcing abstraction.

Functional Data Structures (FDS)

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, array-based heaps, maxiphobic heaps.
• Sets and maps: a unifying framework covering treaps, AVL trees, weight-balanced trees, and red-black trees; binary tries.
• Text processing: simple exact matching; suffix trees; suffix arrays.
• Hashing: chaining; open addressing; cuckoo hashing; perfect hashing.

Logic And Computation Intertwined (LACI)

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 full-featured 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 first-order logic.
  • The advantages of higher-order 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, inductively-defined 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.

A Functional Introduction to Modular Synthesis (FIMS)

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 self-patching. The third chapter brings in more ideas through an examination of modules currently resident in my rack.

The Sound of Math (TSOM)