CSE 341 - Programming Languages

Course Topic Summary (and final exam study checklist)

Topics that are in the lecture notes, but that we didn't have time to cover in class, are written with strikethrough font, like this. These won't be on the final for this quarter.

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; backtracking; derivation trees; infinite derivations; controlling search (including the infamous "cut" operator)
• difference lists
• 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