Theory of Programming Languages

Spring 2025

Documents

• Syllabus and Schedule - revised February 13, 2025
• History and Advice
• About Laptops and Phones in Class
• Course Policies
• General Academic Calendar
• Academic Honesty
• School of Computer Science and Mathematics Department of Computing Technology Goals
• Writing Center
• Counseling Services
• Title IX at Marist
• Title IX Student Bill of Rights and IX Reporting Options
• Academic Learning Center for tutoring and more

Projects

• Be scholarly and write your labs with LaTeX. Overleaf is probably the easiest way to do this. I have developed a template you can use. There are more LaTeX resources below.
• Programming In The Past
• Fun with Lambda Calculus
• Functional Programming
• Language Design Project - See the Hall of Fame for inspiration. Here's an Ms-Word version. ETH's Oberon 2019 Language Report is an excellent example to follow. Finally, here's a fun video about how NOT to design a language.

Resources

• Programming Tools
• OnlineGDB - A multi-language online IDE
• ideone - Another multi-language online IDE
• Code Pad - Yet another multi-language online IDE
• JDoodle - Still another multi-language online IDE
• OverAPI - Programming Language Reference Cards and Cheat Sheets
• Programming Language Database - a rich resource. Dig in!
• LaTeX
• Comprehensive TEX Archive Network
• Overleaf (formerly ShareLaTeX)
• LaTeX Tutorial from Overleaf
• TeX Stack Exchange
• TikZ package tutorial (for drawing DFAs and NFAs)
• Lambda Calculus
• The Lambda Calculus from The Stanford Encyclopedia of Philosophy
• Lambda Calculi - from the Internet Encyclopedia of Philosophy
• λ-Calculus: Then and Now by Dana S. Scott
• Lambda Calculus for Dummies
• Lambda Lessons Interactive Fun
• Combinatris - Like Tetris, but with Lambda Calculus Combinators Awesome! (Watch out for YY)
• Lambda Calculus: What? How? ...Why? from Yana the Contrarian
• Whiteboard problems in pure Lambda Calculus
• Lambda Calculus, Scheme, and more
• Lists out of Lambda LISP-like functional programming in JavaScript
• Lambda Alligators
• Blog post about Lambda Calculus - pretty good
• The Y Combinator (Slight Return)
• History of Lambda-calculus and Combinatory Logic
• Combinatory Logic from The Stanford Encyclopedia of Philosophy
• Lambda Screen As Alan says, from factorial to Fortnite, all computing is Lambda Calculus
• Lambda Calculators
• Git
• GitHub Desktop
• A Gentle Introduction to Git and GitHub from Alan
• Git from the Bottom up by John Wiegley
• Git Basics
• Try Github
• GitHub Guides
• Advanced: Git From the Inside Out
• Visualizing Git Concepts
• How to Write a Git Commit Message - pretty good advice
• The Issues Feature on GitHub
• Dangers of GitHub and Amazon

Notes

• Chapter One
• Chapter Two
• Chapters Three and Four
  • Context-Free Grammars, Derivations, and Parse Trees
  • Ambiguous Grammars
  • Lex and Parse
  • Axiomatic Semantics
  • C.A.R. Hoare's original 1969 paper on Axiomatic Semantics PDF
• Lambda Calculus
  • Alan Turing's original 1936 paper "On Computable Numbers" PDF
• Scope and Type
  • Chapter Five
  • Chapter Six - Data Types
• Chapter Nine and a little bit of Chapter 10
• Chapter Thirteen
• Chapter Fifteen
• Chapter Sixteen

Languages

• Fortran
• Fortran PLDB Entry
• Software Preservation Group: Fortran
• G95 Fortran
• SilverFrost Fortran
• GNU Fortran
• Tiny GNU Fortran code example
• Photran - a Fortran IDE (Seriously!.. It's Eclipse-based, so think twice.)
• Microsoft Manuals - Fortran
• John Backus interviewed by Grady Booch
• The Fortran I Compiler PDF
• Five Reasons Why Fortran is Still Used
• COBOL (not Kobol)
• COBOL PLDB Entry
• 16-bit COBOLv3 (download link)
• TinyCOBOL
• IBM System/360 COBOL manuals
• Microsoft Manuals - COBOL
• COBOL's Youth Culture (!)
• Learning COBOL - A Journey for the Modern Programmer
• BASIC
• BASIC PLDB Entry
• History of BASIC
• Fifty Years of BASIC - from TIME
• Microsoft Manuals - BASIC
• Free BASIC
• Chipmunk BASIC
• VICE: the Versatile Commodore Emulator - Emulate a PET and write BASIC
• WWW BASIC - Embed BASIC in your web pages
• QB64
• Pascal, Modula, Oberon

• Pascal PLDB Entry
• 50 Years of Pascal by Niklaus Wirth
• Wirth's original Pascal paper
• History of Pascal
• 1985 Interview with Niklaus Wirth and Don Knuth
• The School of Wirth
• Free Pascal
• Lazarus - a Delphi compatible cross-platform IDE for Free Pascal
• GNU Pascal
• Software Preservation Group: ALGOL (a parent of Pascal)
• Modula-2 and Oberon (descendants of Pascal)
• ONBC - an Oberon compiler
• Apple's Lisa Source Code - Understanding Clascal
• LISP
• A Road to Common LISP
• LISP PLDB Entry
• Play with LISP in a browser (Limited LISP) (code)
• Steel Bank Common Lisp (SBCL)
• Clozure Common Lisp (CCL)
• The History of LISP by John McCarthy - as a transcript and as a paper
• The Evolution of LISP
• The History of Franz and Lisp
• Lisp as the Maxwell’s equations of software
• A Road to Common Lisp - Learning LISP
• Software Preservation Group: LISP and Early LISPs
• A List of LISPs
• Ufasoft LISP Studio - a Common LISP IDE
• newLISP- a newer dialect of Lisp
• Arc - a recent-ish dialect of Lisp with documentation and examples
• CLiki - a Common LISP Wiki
• Common LISP Cookbook
• LISP in 200 lines of C
• xkcd LISP joke referencing 2001: A Space Odyssey
• xkcd LISP joke referencing Star Wars
• How Lisp Became God's Own Programming Language
• A brief interview with Common Lisp creator Dr. Scott Fahlman
• John McCarthy's Miscellaneous Numerical Facts for use in LISP programs
• LISP and Prolog
• LISP, Logic Programming, and Prolog
• Prolog
• Prolog PLDB Entry
• SWI Prolog
• SWISH - SWI Prolog in a browser (code)
• GNU Prolog
• XGP - A GNU Prolog Mac OS X IDE
• Logic Programming with Prolog
• The Power of Prolog - Contains great examples
• Prolog Under the Hood
• Why Learn Prolog today?
• Turbo Prolog Manual from 1983 - Nostalgic!
• The Birth of Prolog
• A 50th Anniversary Prolog Documentary It's in French but there are English subtitles.
• Prolog-like ML
• Mercury
• ML
• ML PLDB Entry
• Standard ML of New Jersey from Bell Labs
• zip: ML Code Examples from Alan
• ML cheatsheet from Cornell
• ML tutorial from Princeton
• Four Lectures on ML from Tufts
• SML Help
• SML Family - Docs and history
• Early Evolution of ML
• The History of Standard ML
• Cake ML - a functional programming language with a proven-correct compiler and runtime system
• Millet - A Visual Studio Code language server extension

• ML-flavoured Erlang
• Alpaca - Yes, it's really called Alpaca.
• ML-flavored TypeScript
• Bosque
• Prolog, Erlang, Elixir
• ... a side-by-side reference sheet
• Erlang
• Erlang PLDB Entry
• History of Erlang
• All About Erlang
• Joe Armstrong's blog
• The Zen of Erlang by Fred Hebert
• Learn You Some Erlang for Great Good! by Fred Hebert
• A Big List of Erlang Resources
• Haskell
• Haskell PLDB Entry
• Try Haskell in a browser
• Functional Programming in Verse - From Simon Peyton Jones and others
• F#
• F# PLDB Entry
• F# from Microsoft Research
• F# Software Foundation
• The Early History of F# by designer Don Syme
• F# IDE
• APL
• APL PLDB Entry
• Software Preservation Group: APL
• Fear and Loathing in APL
• APL Overview and History by A Kaleberg
• Try APL online
• A Personal History of APL by Michael S. Montalbano
• A History of APL in 50 Functions by Roger K.W. Hui
• Smalltalk
• Smalltalk PLDB Entry
• Smalltalk History at CHM
• Smalltalk's Influence on Modern Programming - by Matt Savona, 2008
• Design Principles Behind Smalltalk
• Simula
• Simula PLDB Entry
• Simula - paper by Joe Casey, 2008
• Simula - presentation by Joe Casey, 2008
• C
• C PLDB Entry
• History of C PDF or HTML
• Origins of C from Ars Techhnica
• A Short History of Objective C from the Computer History Museum
• C++
• C++ PLDB Entry
• GCC
• CLion
• Qt
• g++ cheatsheet from USC
• makefile cheatsheet from USC
• Boost Libraries
• Abseil - C++ docs and libraries from Google
• Super helpful resource on Templates in C++
• Ada
• Ada PLDB Entry
• Ada: a C Developer's Perspective
• Ada for the C++ or Java Developer
• What's new in Ada 2022

Articles

• Thoughts and Quotes about Various Programming Languages
• A mostly wrong (un)history of Programming Languages
• Interview with Dana Scott (2022) - His life is a tour through the topics of our class.
• The Evolution Of Programming Languages
• If PHP were British
• Interview with James Gosling (2021) - creator of Java
• Edsger W. Dijkstra - A Commemoration (2021)
• Dijkstra on Recursive Programming from 1960
• A walk through building an interpreter
• F* Verification Language
• Z3 Theorem Prover from Microsoft Research
• Using the Z3 Theorem Prover to verify firewall configurations
• On the Expressive Power of Programming Languages - Here's Matthias Felleisen's paper.
• Critiquing SQL by Elvis Pranskevichus
• Nulls, Three-Valued Logic, and Ambiguity in SQL: Critiquing Date’s Critique by Claude Rubinson
• A Large-Scale Study of Programming Languages and Code Quality see also PDF
• 10 Most(ly dead) Influential Programming Languages by Hillel Wayne
• John Carmack on Static Code Analysis
• GUI Gallery
• Compiler Explorer from Matt Godbolt
• Formal Verification: The Gap Between Perfect Code and Reality
• So You Want to Write a Type Checker
• From FORTRAN to Swift The world's most important programming languages according to Computing.co.uk
• Thoughts about Type Safety from the Programming Language Enthusiast blog
• Type Inference tricks
• Ada, C, C++, and Java vs. The Steelman
• Boeing Flies on Ada
• Subtle Bugs - Sometimes correctness proofs are not enough.
• PHP: A Fractal of Bad Design - Required Reading
• PHP quirks and flat-out stupidity - Read at risk of your sanity
• Attempting high quality PHP - You've got to admire the attempt.
• C# 7.0 Design Notes
• C# 5.0 Language Spec from Microsoft
• What are Fortran and COBOL used for today? - closed on Stackoverflow
• A-to-Z of Programming Languages
• The Go Language Spec from Google
• Computer History Timeline
• Programming Language Influence Graphs
• OMeta attribute grammar example
• Microsoft's Parallel Computing Developer Center
• Why C++ is not "back"
• Why We Need New Languages
• Parallel computing support in the next version of Visual Studio
• Erlang for Concurrent Programming
• Real-world Concurrency
• Examples of Many Languages
• Advanced Topics in Programming Languages
• COBOL Turns 50 Years Old
• Dynamic Programming Futures
• Graph of Programming Languages connected by Compilers
• Software Engineering Radio
  The podcast for professional developers
  I really like these folks. Highly recommended. Here are a few episodes to get you started:
  • Bruce Momjian on the Postgres Query Planner
  • Eric Brewer: The CAP Theorem, Then and Now
  • Michael Stonebraker on database systems today
  • Graph Databases
  • Moshe Vardi on P versus NP
  • Dynamic Languages for Static Minds
  • Type Systems
  • Monica Beckwith on Java Garbage Collection
  • Introduction to Aspect-oriented Programming (AOP)
  • Aspect-oriented Programming with Aspect J and Spring AOP
  • Leslie Lamport on Distributed Systems
  • Kyle Kingsbury on Consensus in Distributed Systems
  • Concurrency Part One
  • Concurrency Part Two
  • Concurrency Part Three
  • More about Concurrency
  • Dick Gabriel on the origins of LISP
  • Phillip Carter on F#
  • Joe Armstrong on Erlang
  • Martin Odersky on Scala
  • Martin Ordersky on Scala Update
  • Simon Peyton Jones on Functional Programming and Haskell
  • Interview with Anders Hejlsberg - Turbo Pascal, Delphi, C#
  • Morgan Wilde on LLVM
  • The Singularity Research OS
  • Garbage Collection and Transactional Memory

Other Items of Interest

• Here's a fun video about how NOT to design a language.
• Examples of Programs in Many Languages
• Microsoft .NET CLR -- Shared Source Common Language Infrastructure
• Historical Encyclopedia of Programming Languages
• Y Not - Adventures in Functional Programming - Explore the Y-Combinator
• Tutorials in Functional Programming
• From 1959: Theory of Programming for the SAGE AN/FSQ-7 from BitSavers' Software Archive
• An Actual Turing Machine (kinda)
• Programmers' Last Words
• Write in C (Apologies to John, Paul, George, and Ringo.)
• C Recursion - by Kernighan, Ritchie, and Lovecraft
• Comments on Comments
• Computational Complexity: A Modern Approach a free (draft) textbook from by Sanjeev Arora and Boaz Barak

Final Project Hall of Fame

• Bruciato - by Sorin Macaluso, 2024
• liteRoast - by Andrew Hatch, 2024
• Lambda+ - by Nick Fiore, 2023
• Classic Rock Script - by Marcus DiMarco, 2023
• Qsort - by Alex Lizzo, 2023
• PastPHP - by Caleb Rogers, 2022
• Cappy - by Calista Phippen, 2022
• Geova - by Anthony Sasso, 2022
• Pipes - by Kyle DePace, 2022
• SpellVoid - by Antonio Lopez, 2022
• Hogwarts - by Roxanne Lai, 2021
• Actual Hell - by Marinel Tinnirello, 2021
• Allium - by Dan Yost, 2021
• Concerto - by Shannon Brady, 2021
• Scaling - by Oliver Fountain, 2019
• Wheatley - by Michael Durso, 2019
• SANTA - by Jenna Ficula, 2018
• SOAPScript - by Bob Nisco, 2013
• ˆ (caret) - by Brian Gormanly, 2013
• COBOL 13 - by Bryan Silvia, 2013
• IOE - In One Ear - by Scott Arcuri, 2013
• HAL - by Caitlin Cellier, 2011
• not(FUN) - by Michael Cohoon, 2011
• MaRVN - by John Dunham, 2011
• JFun - by Greg Guida, 2010
• JavaSCAR - by Joey Carmello, 2010
• GLaDOS-script - by Ryan Sullivan, 2010
• Steve# - by Steven Abbagnaro, 2010
• C'thulu - by Shane Steinert, 2010
• Shingle - by Skyler Dodge, 2009
• GLaDOS - by Neal Tanner, 2009