CSci 450-01: Organization of Programming Languages
CSci 503-01: Fundamental Concepts in Languages
Fall 2014

Lecture Notes and Web Resources

Sections

Reference Materials

1. Free online programming language textbooks and tutorials
2. Functional programming using Haskell:
   Primary Haskell lecture notes and tutorials for course
   
   1. H. Conrad Cunningham. Notes on Functional Programming with Haskell
      This document is under revision during Fall 2014 and may change frequently. Reload the page or clear the browser cache to ensure that you see the latest version.
   2. Miron Lipovaca. Learn You a Haskell for Great Good: A Beginner's Guide, online tutorial
      This book is also available in print, published by No Starch Press April 2011.
   
   Other Haskell books
   
   3. Kees Doets and Jan van Eijck. The Haskell Road to Logic, Math and Programming, March 2004
      This book is also available in print, published by College Publications, 2004.
   4. Paul Hudak. The Haskell School of Music: From Signals to Symphonies, Version 2.6, January 2014
      This book is a recent rewrite of Hudak's The Haskell School of Expression: Learning Functional Programming through Multimedia, Cambridge University Press, 2000: [source code for SOE]
   5. Simon Marlowe. Parallel and Concurrent Programming in Haskell: Techniques for Multicore and Multithreaded Programming, 2013
      This book is also available in print, published by O'Reilly Media 2013.
   6. Bryan O'Sullivan, Don Stewart, and John Goerzen. Real World Haskell: [HTML book]
      This book is also available in print, published by O'Reilly Media November 2008.
   7. (book not online) Simon Thompson. Haskell: The Craft of Functional Programming, Third Edition, Addison Wesley, 2011:
      [source code] [local copy of source code]
   
   Other Haskell resources
   
   8. Haskel project web site
      • Haskell Platform 2014.2.0.0 software available free from http://www.haskell.org/platform for Windows, Mac, and Linux--bundles Glasgow Haskell Compiler (GHC) 7.8.3 and common libraries
      • Haskell 2010 Language Report
      • GHCi User's Guide
      • Haskell Cheat Sheet
      • Standard Prelude functions
      • School of Haskell online tutorials
3. Lua:
   1. (Textbook not available online) Roberto Ierusalimshcy. Programming in Lua( PiL), Third Edition, Lua.org, Rio de Janiero, 2013 (covers Lua 5.2)
   2. Course notes by Fabio Mascarenhas for a course based on Programming in Lua
   3. Official Lua language site: [download ] [documentation]
   4. Lua users site: [wiki]
   5. Lua Tutorial
   6. Love 2D game framework
4. Prolog:
   1. Patrick Blackburn, Johan Bos, and Kristina Striegnitz. Learn Prolog Now, online tutorial
   2. SWI Prolog, stable release 6.6.6, available from http://www.swi-prolog.org/ or various other repositories.
5. William R. Cook. Anatomy of Programming Languages, online draft
6. Kathleen Fisher's lectures on programming languages: [local]
7. (SICP) Harold Abelson and Gerald J. Sussman with Julie Sussman. Structure and Interpretation of Computer Programs, Second Edition, MIT Press, 1996:
   [book site at MIT Press] [HTML book] [SICP ebook site] [local copy of source code]
8. Shiram Krishnamurthi. Programming Languages: Application and Interpretation, Second Edition:
   [HTML] [PDF] [Fall 2012 course] [Fall 2013 course]



Schedule, Lecture Notes, and Examples

9. (25 Sep) Examine syllabus and discuss class organization. Separate CSci 503 students into new meeting time (10:00 MWF, Weir 106).
10. Discuss the changes in computer systems over past 70 years and their implications for programming and programming language design.
    1. (27 Sep) Effect of Computing Hardware Evolution on Programming Languages, instructor's lecture notes
    2. (for reference) Nathan Ensmegner's Early History of Computing, The Franklin Institute
    3. (for reference) Wikipedia article on History of Computing Hardware
    4. (for reference) Wikipedia article on the Timeline of Computing
11. (27 Aug) Discuss Backus' Turing Award lecture excerpt in Notes on Functional Programming with Haskell, section 1.2, pages 2-4.
12. (29 Aug) Discuss history of programming languages over past 60 years, calling attention to the emergence of paradigms and major languages. See instructor's notes.
13. Discuss programming paradigms
    1. General programming language concepts: programming language paradigm, imperative language, declarative language, functional language, relational or logic language, state, implicit versus explicit state
    2. (29 Aug) Lecture from Notes on Functional Programming with Haskell, section 1.3, pages 5-6
14. Discuss simple factorial function example to explore Haskell syntax and semantics.
    1. Background reading: Chapter 2 "Starting Out" of Learn You a Haskell for Great Good
    2. (for reference) GHCi User's Guide
    3. (3 Sep) Lecture from Chapter 3 of Notes on Functional Programming with Haskell, pages 17-22
    4. (3 Sep) Demonstrate the GHCi (Glasgow Haskell Compiler interactive interface) using the factorial functions from Chapter 3.
       Note: GHCi is an interactive REPL (Read-Evaluate-Print-Loop) tool for the Haskell language.
15. Discuss reasons for studying functional programming.
    1. General programming language concepts: referential transparency, abstraction, first-class functions, higher-order functions, eager versus lazy evaluation
    2. (5 Sep) Lecture from Section 1.4 of Notes on Functional Programming with Haskell, pages 6-8
16. Discuss basic Haskell functional programming concepts from Chapter 5 of Notes on Functional Programming with Haskell, pages 25-54.
    1. Background reading: Chapters 2, 3, 4, and 5 of Learn You a Haskell for Great Good
    2. General programming language concepts: data types, lists, recursion, pattern matching, recursive programming styles (backward, forward, and tail recursion), accumulating parameter
    3. (for reference) Haskell Cheat Sheet
    4. Haskell modules from Notes Chapter 5
    5. (5-8 Sep) Haskell builtin data types, section 5.1, pages 25-29
    6. (8 Sep) Programming with list patterns, section 5.2, pages 30-34
    7. (10-12 Sep) Infix operators, recursive programming styles, more list operations, and the rational arithmetic package, section 5.3-6, pages 35-47
    8. (15 Sep) Standard Prelude functions
    9. (15 Sep) IO program to test an xor function
    10. (17 Sep) Live coding demonstration using exercises 6 and 8 at the end of Chapter 5
    11. (19 Sep) Example rjustify function
    12. (19 Sep) Exponentiation function examples (backward, tail, and logarthmic)
    13. (for reference) Kathleen Fisher's introductory slides on Haskell

17. Discuss Haskell higher-order functions from Chapter 6 of Notes on Functional Programming with Haskell, pages 55-78.
    1. Background reading: Chapter 6 of Learn You a Haskell for Great Good
    2. General programming language concepts: first-class functions, higher-order functions, maps, filters, folds, strictness of operations, Currying, partial application, combinators, functional composition, anonymous functions (lambda expressions)
    3. Haskell modules from Notes Chapter 6
    4. (12-15 Sep) Capturing computational patterns using higher-order functions: Maps and filters from sections 6.1-2, pages 55-58
    5. (19-22 Sep) Capturing more computational patterns using higher-order functions: folds from section 6.3, pages 58-61
    6. (22 Sep) Example uses of fold functions
    7. (22 Sep) Higher-order function concepts and features: Strictness and currying from sections 6.4-5, pages 61-63
    8. (24-26 Sep) Higher-order function concepts and features: Operator sections, combinators, and functional composition, and lambda expressions from sections 6.6-9, pages 64-69
    9. (26 Sep) Capturing more computational patterns: List-breaking and list-combining functions, sections 6.10-11, pages 69-71
    10. (26 Sep) Case studies: Rational arithmetic package revisited and cosequential processing package, sections 6.12-13, pages 72-74
18. Discuss Haskell sequences and comprehensions from Chapter 7 of Notes on Functional Programming with Haskell, pages 79-84.
    1. Background reading: Sections "Texas ranges" and "I'm a list comprehension" in Chapter 2 of Learn You a Haskell for Great Good
    2. General programming language concepts: sequences, list comprehensions, solve a more general problem first
    3. Haskell modules from Notes Chapter 7
    4. (15 Sep) Discuss Haskell sequences and comprehensions from Chapter 7 of Notes on Functional Programming with Haskell, pages 79-82.
    5. (19 Sep) Discuss "first occurrence in a list" problem and "solve a harder problem" strategy from section 7.2.6 of Notes on Functional Programming with Haskell, page 83.
19. Examination 1
    1. (29 Sep) Covers everything to this point in the semester (e.g. items 9-18 of this list)
    2. (for reference) 2010 Functional Programming exam: [CSci 555 Exam 1] [partial solution]
    3. (6 Oct) Discuss graded exam: [solution]
20. (1 Oct, for assignment #3) Discuss recognizing regular expressions case study from Simon Thompson. Haskell: The Craft of Functional Programming, Third edition, Addison Wesley, 2011. Assignment #3 requires us to treat functions as data.

21. Discuss Haskell algebraic data types and type classes.
    1. Background reading: Chapter 3 and Chapter 8 of Learn You a Haskell for Great Good
    2. General programming language concepts: types; algebraic data types (enumerated types, tuple types, disjoint union types, recursive types); Haskell type system concepts (type classes, instances, overloading, inheritance) versus related Java/C++ type system concepts (abstract and concrete classes, objects, inheritance, interfaces)
    3. Haskell modules from Notes Chapter 8
    4. (3, 8 Oct) Chapter 8 of Notes on Functional Programming with Haskell, pages 85-94
    5. (8-10 Oct) Overloading and Type Classes
    6. (for reference) Kathleen Fisher's slides on Type Classes
    7. (for reference) Type Inference
    8. (for reference) Kathleen Fisher's slides on Types
22. (10 Oct) Discuss problem-solving techniques from Chapter 10 of Notes on Functional Programming with Haskell, pages 105-108.
23. (13 Oct) 9:00 CSci 450 class meets with ABET/CAC Program Evaluator. 10:00 CSci 503 class does not meet.
24. Discuss languages from Chapter 1 of William Cook's Anatomy of Programming Languages (AoPL).
    1. (used below with AoPL sections) Bruno Oliviera's slides for AoPL
    2. AoPL Chapter 1 concepts: language, syntax, semantics; metaprogram; expressions, statements, side effects
    3. (15 Oct) Introduction to languages (pages 8-9) (Oliveira's lecture 4 slides)
25. Discuss expressions, syntax, and evaluation from Chapter 2 of William Cook's Anatomy of Programming Languages (AoPL).
    1. (used below with AoPL sections) Bruno Oliviera's slides for AoPL
    2. AoPL Chapter 2 concepts: expression, syntax, evaluation; concrete and abstract syntax; literal, token, identifier, grammar, syntactic category, production rule, terminal, nonterminal, precedence, associativity, parser generator, object language, metalanguage
    3. (15 Oct) Simple language of arithmetic--abstract syntax, and recognizing tokens in concrete syntax (pages 19-21) (Oliveira's lecture 6 slides)
    4. (20 Oct) Simple language for arithmetic--concrete syntax, grammars, and evaluation (pages 23-30) (Oliveira's lecture 6 slides)
    5. (for reference) Source code for simple language: [Lexer.hs] [Simple.hs] [Base.hs] [SimpleParse.y] [SimpleTest.hs]
26. Discuss Section 4.1 "Compilers and Syntax" (pages 48-57) of John Mitchell's Concepts in Programming Languages, Cambridge University Press, 2003. This handout discusses general programming language concepts but not explicitly in the context of Haskell or other languages.
    1. (17 Oct) Phases of a simple compiler (described in handout): lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, and code generation
    2. (17 Oct) Other optional phases discussed (but not described in this handout): lexical preprocessing (e.g., as in C) before lexical analysis and assembly, linking, loading (static and dynamic), and just-in-time compilation after code generation
    3. (for reference) Grammar and parse tree concepts: grammars, derivations, parse trees, ambiguity, parsing,and precedence (This handout was not discussed from this section but was discussed with Anatomy of Programming Languages Chapters 2 and 3)
27. (22 Oct) No class because of instructor illness.

28. Discuss variables in the arithmetic expression language from Chapter 3 of William Cook's Anatomy of Programming Languages.
    1. (used below with AoPL sections) Bruno Oliviera's slides for AoPL
    2. AoPL Chapter 3 concepts: variable, binding, mutation, substitution, renaming, environment, local variable, scope, unbound variable, bound variable, free variable, static and dynamic properties
    3. (24, 29 Oct) Adding global and local variables to the arithmetic expression tree (Oliveira's lecture 7, 8, 9 slides).
29. Discuss domain-specific languages in Haskell.
    1. General programming language concepts: domain-specific languages (DSLs); DSLs versus general-urpose programming languages; external versus internal DSLs; shallow versus deep embedding of internal DSLs
    2. (27 Oct) Domain-Specific Languages, instructor's lecture notes
    3. (27-29 Oct) SandwichDSL Case Study, instructor's lecture notes (with significant revisions on 28 October)
    4. (29 Oct) Assignment #4, based on the SandwichDSL case study, requires us to use Haskell algebraic data types to implement a small deeply embedded internal DSL.
30. (29 Oct) Review solutions to Assignments #2 and #3.
31. Examination 2
    1. (3 Nov) Emphasizes topics covered since Exam 1 (e.g., items 20-30 of this list) plus concepts needed for homework assignments 2-4. Of course, the Haskell language and programming concepts needed may include anything from the beginning of the semester
    2. (31 Oct) 2010 Functional Programming exam: [CSci 555 Exam 2] [partial solution]
       Note: This is only a partial model for the exam. The 555 exam does not cover the language processing content. Only problems 1, 2, 5, and 7 are relevant to this course.
    3. (7 Nov) Discuss graded exam: [partial solution]
32. Discuss basic Lua concepts using Fabio Mascarenhas's Lecture Notes, based on the Programming in Lua textbook.
    1. Background reading: Chapters 1-8 of Programming in Lua (PiL), pages 1-82
    2. General programming language concepts: types (static versus dynamic, strong versus weak, duck typing); primitive data types; scope of variables (global versus local, nested scopes, shadowing); control constructs; functions versus procedures, side effects; first-class and higher-order functions; closures; tail recursion optimization
    3. (5-10 Nov) Mascarenhas Notes: Introduction to Lua, Getting Started, Types and Values
    4. (10-12 Nov) Mascarenhas Notes: Control Flow, Functions
    5. (14 Nov) Mascarenhas Notes: Data Structures, More Functions, Iterators, Handling Errors
33. Discuss Lua modules, metatables, and objects using Fabio Mascarenhas's Lecture Notes and other materials
    1. Background reading: Chapters 13, 15, and 16 of Programming in Lua (PiL)
    2. General programming language concepts: modular programming, information hiding, and abstract data types; object-based programming, especially prototype-based; single and multiple inheritance (i.e., object-oriented programming)
    3. (14 Nov) Mascarenhas Notes: Modules, Metatables, Objects
34. (for Assignment #5) Arithmetic expression tree program skeletons (Lua)
    Functional versions
    1. (12 Nov) Recursive Functions with Record Representation (exprRecFuncRecord.lua)
    2. (14 Nov) Recursive Functions with List Representation (exprRecFuncList2.lua)
    3. (14 Nov) Evaluation Function Table with List Representation (exprEvalTable2.lua)]
    4. (for reference) Similar Scala code using case classes
    
    Object-oriented versions
    5. Prototype Object-Based (exprObjBased.lua)
    6. Object-Oriented with Inheritance (exprObjInherit.lua)
    
    Parsers (defer until LPEG discussion)
    7. LPEG parser with captures
    8. LPEG parser with semantic actions
35. (TBD) Data Abstraction, instructor's lecture notes
36. (TBD) Lua list module
    1. Cell-based list module: [module source] [test driver]
       
    2. Closure-and-table-based list module variant: [module source] [test driver]
    3. Function-based cell list module variant: [module source] [test driver]
    4. Lazy list module variant using C preprocessor (cpp -P)
       [module source] [source after cpp] [test driver] [driver after cpp] [sh script]
    5. Lazy list module variant using LuaMacro 2.5
       [macro definitions] [module macro source] [source after luam -o] [macro test driver] [driver after luam -o] [sh script]
37. (TBD) Introduction to Object-Orientation, instructor's lecture notes--through the section titled "An Object Model".

    Note: In CSci 658, along with the discussion of these notes, we examined the object-oriented versions of the Arithmetic Expression Tree, Complex Number, and the Movable and Named Object example.

38. (TBD) Discuss scope, functions, and storage management from Chapter 7 (pages 204-231) of John Mitchell's Concepts in Programming Languages, Cambridge University Press, 2003: [slides]

Other Materials from Fall 2013 CSci 658 (Software Language Engineering)

39. (for reference) Recursion Concepts and Terminology (Using Lua Examples), instructor's lecture notes
    (We covered this recursive styles content from Chapter 5 of the Notes on Functional Programming with Haskell.)
40. Example recursive Lua functions adapted from from the Scheme versions in Chapter 1 of Abelson and Sussman's Structure and Interpretation of Computer Programs
    1. Square root (Newton's Method)
    2. Factorial
    3. Fibonacci
    4. Exponentiation
    5. Greatest common divisor
    6. Summation (takes function arguments)
    7. Derivative (returns function)
41. Natural number package
    1. Natural number package in Lua (nats2.lua)
    2. Older Lua version with less distinct data abstraction layers
    3. Similar programs in other languages: [Java] [Ruby] [Scala (three versions, item 5)]

42. Complex number arithmetic modules in Lua adapted from SICP Section 2.4. (Modules are repeated in each package in which they are used.)
    1. Rectangular coordinates modules
       [arithmetic:] [rectangular representation] [utilities] [test driver]
       
    2. Polar coordinates modules:
       [arithmetic] [polar representation] [utilities] [test driver]
       
    3. Tagged data modules:
       [arithmetic] [data tagging] [utilities] [test driver]
       
    4. Data-directed programming modules:
       [arithmetic] [rectangular representation] [polar representation] [data tagging] [utilities] [test driver]
       
    5. Object-oriented modules:
       [arithmetic] [utilities] [test driver]
       
43. Carrie's Candy Bowl ADT in Lua
    1. Problem description
    2. ADT semantics
    3. Description of bag concept
    4. Hashed version (candybowl_hash.lua). This file has a description of the problem and the formal invariant, precondition, and postcondition assertions.
    5. Unsorted list version (candybowl_list.lua)
    6. Test driver (test_candybowl.lua)
44. Movable and Named Objects example (in Lua but based on a similar Haskell case study given in Section 14.6 of: Simon Thompson. Haskell: The Craft of Functional Programming, Third Edition, Addison Wesley, 2011).
    1. First Lua version: [source (movable.lua)]
    2. Modularized version with improved class support
       [class_support module] [using class-support (movable2.lua)] [test driver (movable2Test.lua)]
    3. Other older versions: [Haskell source ] [Scala source (partial) ]
45. Lua versions similar to Martin Fowler's Lair Configuration domain-specific language (DSL) examples from his book chapter "One Lair and Twenty Ruby DSLs," Chapter 3, The ThoughtWorks Anthology: Essays on Software Technology and Innovation, The Pragmatic Bookshelf, 2008: [book site]
    
    Note: The DSL patterns mentioned are from the DSL patterns catalog from Martin Fowler's book Domain Specific Languages (Addison Wesley, 2010.
    
    Caveat: Some of these DSL programs depend upon features from Lua 5.1 that were changed in Lua 5.2.
    
    Shared modules
    1. Class support module (same as in Movable Objects case study)
       [class support module (class_support.lua)]
    2. Semantic Model
       [model module (model.lua)] [test driver (rules00.lua)]
    
    Internal DSLs
    3. Global Function Sequence
       [builder module (builder08.lua)] [dsl script (rules08.lua)] [test driver (test08.lua)]
    4. Class Method Function Sequence with Method Chaining
       [builder module (builder11.lua)] [dsl script (rules11.lua)] [test driver (test11.lua)]
    5. Expression Builder with Method Chaining
       [builder module (builder14.lua)] [dsl script (rules14.lua)] [test driver (test14.lua)]
    6. Nested Closures
       [builder module (builder03.lua)] [dsl script (rules03.lua)] [test driver (test03.lua)]
    7. Expression Builder with Object Scoping and Method Chaining
       [builder module (builder17.lua)] [dsl script (rules17.lua)] [test driver (test17.lua)]
    8. Literal Collection
       [builder module (builder22.lua)] [dsl script (rules22.lua)] [test driver (test22.lua)]
    
    External DSL
    9. LPEG Parser/Builder (no corresponding example in Fowler paper)
       [builder module (builderLPEG1.lua)] [dsl script (rulesLPEG1.dsl)] [test driver (testLPEG1.lua)]
46. Sandwich DSL in Lua (related but not precisely the same as the Haskell SandwichDSL above)
    1. Semantic model module (sandwich_model.lua)
    2. DSL builder module using function sequence pattern (sandwich_builder.lua)
    3. Test driver (test_sandwichDSL.lua)
47. Lua Parsing Expression Grammar (LPEG) library
    1. Roberto Ierusalimschy's talk LPEG: A New Approach to Pattern Matching [PDF slides] [video]
    2. (For reference) Roberto Ierusalimschy's paper "A Text Pattern-Matching Tool Based on Parsing Expression Grammars," Software: Practice & Experience 39 #3 (2009) 221-258: [PDF]
48. Kamin Interpreters in Lua Toolset (KILT) [Compressed tar file]

    1. Language/Interpreter-independent modules:
       [REPL Module (repl.lua)]
       [Environment Module (environment.lua)]
       [Function Table Module (funtab.lua)]
       [Utilities Module (utilities.lua)]
       [Opcodes Factory Module (opcodes.lua)]
       [Values Factory Module (values.lua) ]
       [Parser Factory Module (parser.lua)]
       [Evaluator Factory Module (evaluator.lua)]
       
    2. Kamin Chapter 1 Core language interpreter:
       [Core Interpreter (Core.lua)]
       [Core Opcodes (opcodes_core.lua)]
       [Core Values Module (values_core.lua)]
       [Core Parser Module (parser_core.lua)]
       [Core Evaluator Module (evaluator_core.lua)
       
    3. Kamin Chapter 2 Lisp language interpreter:
       [Lisp Interpreter (Lisp.lua)]
       [Lisp Opcodes (opcodes_lisp.lua)]
       [Lisp Values Module (values_lisp.lua)]
       [Lisp Parser Module (parser_lisp.lua)]
       [Lisp Evaluator Module (evaluator_lisp.lua)
       [A few Lisp examples]
    4. Kamin Chapter 4 Scheme language interpreter:
       [Scheme Interpreter (Scheme.lua)]
       [Scheme Opcodes (opcodes_scheme.lua)]
       [Scheme Values Module (values_scheme.lua)]
       [Scheme Parser Module (parser_scheme.lua)]
       [Scheme Evaluator Module (evaluator_scheme.lua)
       [A few Scheme examples]

49. (Not discussed directly in CSci 658) Functional Program Evaluation Concepts, instructor's lecture notes

UP to CSci 450/503 root document?