CS302: Paradigms of Programming

“Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.”

- Greenspun's tenth rule of programming 

Offering: Feb-Jun 2021 (Online)

Class strength: 90

Slack: cs302spring21.slack.com (use your @students.iitmandi.ac.in ID)

About the course

Why do we have so many programming languages? Can I even try to get acquainted with a good enough subset? What are the relative advantages of each different paradigm of programming?

This course tries to provide the answers to such questions and more, by studying the fundamental paradigms (imperative, functional, object-oriented, logic) using which a large number of programming languages have been designed. The goal is to focus on the underlying concepts and principles, rather than mastering several languages from each paradigm. By the end of the course, students should be able to appreciate the differences among thinking in each paradigm, while also getting a glimpse of the design and practical issues associated therein. A latent aim of the course is to also motivate the students in studying advanced nuances in the design of languages and their runtimes, and arguing about their mathematical nature.

Which language(s) would we learn?

We would be using Scheme (a variant of a legendary homoiconic language called Lisp) for learning all the paradigms, with short case studies from Java, Prolog and Haskell for various subparts.

Why Lisp (and not my favorite popular language)?

Favorite language varies across people; popular language varies across time; but Lisp remains eternal – across paradigms and generations. More technically, Lispy languages such as Scheme consist of rarely found features not present in any single language out there, and have brought features in almost all languages out there. Still confused? Have patience! There is a reason your seniors have been finding such a fundamental course so refreshing (aka PoPping) even after going through five semesters of computer science.

Textbooks:

1. Harold Abelson, Gerald Jay Sussman and Julie Sussman. “Structure and Interpretation of Computer Programs”, Second Edition, Universities Press, 2005 (for most of the concepts and for Scheme).
2. Ravi Sethi. “Programming Languages: Concepts and Constructs”, Second Edition, Pearson Education, 2006 (for Lambda Calculus and Prolog).
3. Miran Lipovańća. “Learn You a Haskell for Great Good!”, Freely Available Online Edition, 2011 (for, you guessed right, Haskell).

Reference:

  • Michael L. Scott. “Programming Language Pragmatics”, Fourth Edition, Morgan Kaufmann, 2015.

Course structure

  • Credits: 3-0-2-4

  • Audience: No escape for CSE 6th sem; elective for EE 6th and 8th sem

  • Instructor: Manas Thakur

  • TAs:

    • Class: Aditya Anand (s20007); Meetesh Mehta (s20012)

    • Lab: Aman Saxena (b17034); Saurabh Bansal (b17059); Anvay Shah (b17078); Manvi Gupta (b17092); Namrata Malkani (b17096); Varun Singh (b17110); Rishi Sharma (b17138)

  • Slots:

    • Class: C (Mon 10am; Wed 11am; Thu 2pm)

    • Lab: L2 (Tue 2pm)

Schedule

Content Material Remarks
Week 1 Feb 17, 18:
  • Introduction and logistics

  • Bindings and environment

Slides:
  • C1 (due Feb 21): John Backus’ Turing Award Lecture

  • Installation: DrRacket

  • OneNote link (whole course)

Week 2 Feb 22, 24, 25:
  • Orders of evaluation, substitution model

  • Recursion, iteration, tail-call optimization

Feb 23:
  • Lab 1: Functional programming with numbers

Notes:
  • Institute foundation day on 24

Week 3 Mar 1, 3, 4:
  • Higher order functions

  • Closures, lambdas, let bindings

  • Constructing pairs and lists

  • PA1 released (due March 14)

Week 4 Mar 8, 9, 10:
  • List applications

  • Lambda calculus

  • Higher order list functions

Mar 9:
  • Lab 2: Church numerals

Code:
  • First lab hour on 9 is for teaching

Week 5 Mar 15, 17, 18:
  • S-expressions and quotation

  • Purity and referential transparency

  • Quiz 1 discussion

  • Quiz 1 on 17

  • C2 (due Mar 21): Russ Olsen's “Functional Programming in 40 Minutes”

Week 6 Mar 22, 23, 24:
  • Overview of OO

  • Tagging and message passing

  • Imperative programming

Slides:
Week 7 Mar 30, 31:
  • Environment model

  • OO case study

Mar 30:
  • Lab 3: States and mutation

Slides:
Week 8 Apr 5, 6, 7:
  • Sequences as conventional interfaces

  • Streams as delayed lists

  • Infinite streams

Code:
  • PA2 released (due April 23)

Week 9 Apr 12, 13:
  • Iterations as stream processes

  • New syntax using macros

Apr 13:
  • Lab 4: Stream processing

Code:
Week 10 Apr 19, 21:
  • DFA simulation in Scheme

  • Continuations

Code:
  • C3 (due Apr 20): Lambda the Ultimate

Week 11 Apr 27, 28, 29:
  • Intro to logic programming

  • Unification and resolution

Code:
  • Quiz 2 on 27

Week 12 May 3, 4, 5:
  • Cuts, negation and puzzles

  • Scalability of Prolog

  • Intro to evaluators

May 4:
  • Lab 5: Logic paradigm

Slides: Code:
  • Guest lecture by Rishi Sharma on May 4

  • Classes suspended (Covid curfew) from May 6

Week 13 Date-less:
Metacircular evaluator
  • The eval/apply interpreter

  • Interpretation example

  • Variable number of arguments

  • Dynamic scoping

  • Lazy evaluation

Slides:
  • Lecture videos posted on May 13

  • PA3 released (due May 28)

Week 14 May 17, 19:
  • Discussion on PA3 and Lectures 30-31

  • Discussion on Lectures 32-34

Code:
  • Classes resume from May 17

  • C4 (due May 22): John Hughes’ “Why Functional Programming Matters”

Week 15 May 24, 29:
  • Functional programming with Haskell

  • Lists in Haskell

Slides:
Week 16 May 31; Jun 2:
  • ADTs and typeclasses

  • Effectful programs

Jun 1:
  • Lab 6: Programming in Haskell

Slides:
  • Last day of teaching on Jun 2

Evaluation

  • Exams: 60

  • Take-home assignments: 30

  • Labs and comprehension: 10