CSE 341 - Programming Languages

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)
  • call by reference
  • call by name
  • lazy evaluation; thunks
• overloaded functions, operators, and methods
• coercion
• closures
• equality vs. identity (and when it matters)
• compile time vs. run time
• recursion; tail recursion
• aliasing
• dynamic scoping; lexical vs. dynamic scope

Racket

• constructing and navigating list structures
• scoping issues (lexical scoping, global variables, parameters, let, let*, letrec, 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)
• simulating objects in Racket
• functions with variable number of arguments; improper lists

Haskell and Pure Functional Languages

• functions, including higher-order functions, currying, and anonymous functions
• 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.)

Cross-cutting Haskell/Racket Topics

• lexical scoping
• the Octopus 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 and clpfd constraint satisfaction libraries; using them in Prolog programs

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