Sections

• Schedule, Lecture Notes, and Examples
• Reference Materials and Other Resources
  

• (26 Jan) Examine syllabus and discuss class organization.
  
  
• Discuss programming paradigms
  
  
  
  • (26 Jan) A programming paradigm is "a way of conceptualizing what it means to perform computation, of structuring and organizing how tasks are to be carried out on a computer."
    -- from: Timothy A. Budd. Multiparadigm Programming in Leda, Addison-Wesley, 1995, page 3
    
    
  • (26 Jan) Programming Language Paradigms, section 1.3, pages 5-6, from the instructor's Notes on Functional Programming with Haskell
    
    Note: I use the phrase "programming language paradigms" in this document. More correctly, I should only say "programming paradigms" and differentiate among different styles of programming but not among languages. A language typically supports more than one style although some styles may be more directly supported than others.
    
    Concepts: programming language paradigm, imperative language, declarative language, functional language, relational or logic language; program state, implicit versus explicit state; sequencing versus recursion, execution of commands versus evaluation of expressions, "how" versus "what" to compute.
    
    
  • Peter Van Roy's Programming Paradigms Poster website
    
    • (28 Jan) local pdf of poster pdf
    • (for reference) Programming Paradigms for Dummies: What Every Programmer Should Know
      
    
    
  
  
• Motivate the study of functional programming
  
  
  
  • (28 Jan) Excerpt from Backus' 1977 Turing Award Address, section 1.2, pages 2-4, from the instructor's Notes on Functional Programming with Haskell
    From the 1977 Turing Award Address, John Backus. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs, Communications of the ACM 21.8 (1978): 613-641.
    
    Concepts: von Neumann computer, bottleneck; von Neumann language, world of expressions versus world of statements. Functional programming.
    
    
  • (28 Jan) Reasons for Studying Functional Programming, section 1.4, pages 6-10, from the instructor's Notes on Functional Programming with Haskell
    
    Concepts: referential transparency, abstraction, higher-order function, first-class function, eager versus lazy evaluation, separation of data from control
    
    
  • (2 Feb) Objections Raised to Functional Languages, section 1.5, pages 11-12, from the instructor's Notes on Functional Programming with Haskell
    
  
  
• Introduce Scala to Java programmers
  
  
  
  • (2-9 Feb) Notes on Scala for Java Programmers [HTML] [PDF]
    Michel Schniz and Philipp Haller, A Scala Tutorial for Java Programmers
    
    Concepts: basic syntax and semantics of Scala from the perspective of a Java programmer; includes singleton objects, val and var identifiers, type inference, infix method calls, higher-order and first-class functions, anonymous functions, argumentless methods, classes, overriding, case classes, pattern matching, traits, generics, etc.
    
    
  • (4 Feb, for Assignment #1) Arithmetic expression tree program skeletons
    
    
    
    Functional versions
    • Scala Recursive Functions with Case Classes (ExprCase.scala)
    • (for reference) Lua Recursive Functions with Record Representation (exprRecFuncRecord.lua)
    • (for reference) Lua Recursive Functions with List Representation (exprRecFuncList2.lua)
    • (for reference) Lua Evaluation Function Table with List Representation (exprEvalTable2.lua)]
      
      Object-oriented versions
    • Scala Traditional Object-Oriented (ExprObj.scala)
    • (for reference) Lua Prototype Object-Based (exprObjBased.lua)
    • (for reference) Lua Object-Oriented with Inheritance (exprObjInherit.lua)
      
    
    
  • (9 Feb) Scala Class Hierarchy
    
    Concepts: Unification of Java/Scala primitive value types under type AnyVal, Java/Scala reference types under AnyRef, and both under Any.
    
    
  • (for reference) A Tour of Scala
    
    
  • (for reference) Martin Odersky. Scala by Example, June 11, 2014.
    Original at http://www.scala-lang.org (Documentation, Older Documentation, Scala By Example).
    
    
  
  
• Explore recursion in Scala
  
  
  
  • (11 Feb) Recursion Concepts and Terminology: Scala Version [HTML] [PDF] [Elixir] [Lua]
    
    Concepts: recursion, linear and nonlinear recursion, tree recursion, backward and forward recursion, tail recursion, tail recursion optimization (also know as tail call elimination or proper tail calls), auxiliary functions, accumulating parameter (i.e. accumulator), nested functions, time and space complexity of recursive functions, termination arguments for recursive functions, preconditions and postconditions, Scala function definitions.
    
    
  • (for reference) Tail call (on Wikipedia)
    
    
  
  
• Examine functions adapted from SICP
  
  
  
  • Background reading: Chapter 1 of the classic textbook 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]
    
    
  • (9-11 Feb) First-order functions in Scala
    
    • (9 Feb) Square root (Newton's Method) version 1 with all public functions
      [Scala source] [listing]
    • (9 Feb) Square root (Newton's Method) version 2 with nested function definitions
      [Scala source] [listing]
    • (11 Feb) Factorial -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Fibonacci -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Exponentiation -- discussed in Recursion Concepts notes above
      [Scala source] [listing]
    • (11 Feb) Greatest common divisor
      [Scala source] [listing]
      
    
    Concepts: Reinforces the concepts noted above for the "Notes on Scala for Java Programmers" and the notes on "Recursion Concepts and Terminology." Scala object as module, appropriate use of type inference and explicit typing of public features.
  • (11 Feb) Higher-order functions in Scala
    
    • Summation (takes function arguments)
      [Scala source] [listing]
    • Derivative (returns function result)
      [Scala source] [listing]
      
    
    Definition: A higher-order function is a function that takes other functions as input and/or returns a function as its output value.
    
    Related definition: A first-class function is a function that is a first-class value in the language. It can be stored in a variable or some other data structure, passed to a function, or returned by a function.
    
    Concepts: Higher order functions allow us to capture the common aspects of a computational pattern in the fixed part of a function and pass in the variable aspects as functional arguments.
    
    
  • (for reference) Other versions
    
    • Elixir versions from Spring 2015
      [Square root] [Factorial] [Fibonacci] [Exponentiation] [Greatest common divisor] [Summation] [Derivative]
    • Lua versions from Fall 2013
      [Square root] [Factorial] [Fibonacci] [Exponentiation] [Greatest common divisor] [Summation] [Derivative]
      
  
  
• Study functional data structures
  
  
  
  
  • Background reading: "Functional Data Structures," Chapter 3, Paul Chiusano and Runar Bjarnason, Functional Programming in Scala
    
    
  • (16-18 Feb, 25 Feb, 1-3 Mar) Functional data structures lecture notes to accompany Chapter 3 (primarily on the List data type)
    [source]
    
    Concepts: referential transparency, side effect, immutable; algebraic data type, composite type, sum type (tagged, disjoint union, variant), product type (tuple, record), enumerated type, algebraic data type versus abstract data type, syntax, semantics; list, head, tail, constructor, sealed, case class, case object, distinction between case and regular objects, singleton object; polymorphism, ad hoc polymorphism, overloading, subtyping (subtype or inclusion polymorphism), parametric polymorphism (generics), type class, early versus late binding; variance, covariant, contravariant, invariant (nonvariant), variance annotation; companion object; form of the data guides the form of the algorithm, following types to implementations, pattern matching; associativity, identity element, monoid, zero element; variadic functions, apply method in companion object; data sharing, persistent data structure; when to throw exceptions, when not; backward recursion, tail recursion, accumulating parameter, auxiliary function; higher-order function, anonymous function (function literal), underscore notation in anonymous functions; fold functions, map function, filter function, flatMap function; local mutation; type inference, currying, partial application, upper and lower type bounds, view bounds; insertion sort, merge sort, total order pattern of computation, generalizing function definition; stack overflow error; method chaining, train wreck.
    
    
  • (23 Feb) No class because of instructor illness