CSE 341 - Programming Languages - Autumn 2012

Course Topic Summary (and final exam study checklist)

Big Ideas

• types
• scope
• static vs. dynamic analysis
• major programming language families
• interaction of different programming languages with good style for that language
• objects and encapsulation
• purely functional languages vs. state

General Concepts

• types:
  • static vs. dynamic typing
  • type safety
  • type inference
  • terms with no generally-agreed on definition ("strongly typed language")
  • polymorphism
• functional vs. imperative languages; functional subset of language
• higher-order functions
• parameter passing:
  • call by value (including call by value with pointer semantics)
  • lazy evaluation; thunks
  (Previous final exams also may have had questions on call by value-result, call by result, and call by reference; we didn't get to those topics this time.)
• overloaded functions, operators, and methods
• coercion
• closures
• equality vs. identity (and when it matters)
• compile time vs. run time
• recursion; tail recursion

• aliasing -- this just means two names that refer to the same object. It can make it confusing to reason about a program's behavior however.
• dynamic scoping -- this is an alternative to lexical scoping for looking up non-local variable names. With dynamic scoping, you look up the calling stack to see if you can find the variable, rather than in the lexically enclosing scope. It's almost never used any more -- except for finding an exception handler.

Haskell and Pure Functional Languages

• functions, including higher-order functions, currying, and anonymous functions
• lexical scoping
• types: polymorphic types; type inference, declarations; user-defined types, including recursive types; type classes; inheritance
• referential transparency
• lazy evaluation; infinite data structures
• pattern matching
• list comprehensions
• monads; I/O in Haskell
• correct Haskell vocabulary (For example, "do" in Haskell defines a block. Haskell does not have loops, assignments, or statements.)
• applicative vs. normal order evaluation for pure functional languages

Racket

• constructing and navigating list structures
• scoping issues (lexical scoping, global variables, parameters, let, let*, environments)
• function definition; anonymous functions; special forms
• eval and apply
• programs as data
• side effects in Racket
• delay
• Racket macros (including hygenic macros and what problems they solve)
• functions with variable number of arguments; improper lists; quasi-quoting
• the MUPL interpreter

Prolog

• logic variables
• rules, facts, and goals
• Prolog execution; derivation trees; backtracking; infinite derivations
• Prolog programming techniques: controlling search (including the infamous "cut" operator); difference lists. (You should know what are valid representations of difference lists, and how to write out a search tree for rules involving difference lists. You won't be responsible for writing new rules with difference lists. See the mini-exercises on difference lists for examples of what to study.)
• The clpr constraint library, using it to put constraints on real-values variables; interaction between clpr constraints and ordinary Prolog

Ruby

• pure object-oriented languages
• classes, instances; inheritance
• messages and methods
• duck typing
• self and super
• blocks, procs, and iterators
• mixins
• instance-specific methods; singleton classes
• reflection

Java

• subtype relation
• covariant vs. contravariant vs. invariant (also known as equivariant) argument types
• covariant vs. invariant return types
• method overloading
• Java generics: wildcards, bounded wildcards, type parameters, generic classes, generic methods
• Java arrays and the covariant typing rule (and why it may require a runtime check)
• nested and inner classes; scoping issues

Cross-Cutting Object-Oriented Programming Language Topics

• pure vs. hybrid object-oriented languages
• multiple inheritance (for classes) vs. multiple inheritance (for interfaces) vs. mixins