Programming Language History & Theory

Distinguish between expressions and statements, using examples from early imperative languages (e.g., C) and functional languages (e.g., Lisp).

Apply referential transparency to reason about code equivalence, referencing its mathematical origins and role in early functional languages.

Write pure functions that avoid side effects, tracing this concept from Lisp through modern functional languages.

Analyze design trade-offs of immutable data structures, comparing implementations in Clojure's persistent structures, Haskell's default immutability, and functional-style Python.

Trace the historical development of first-class and higher-order functions from Lisp through modern languages.

Explain the benefits and trade-offs of functional programming using specific language examples (e.g., Haskell's type safety vs. Python's flexibility).

Write recursive functions for list processing, comparing Lisp's original approach with modern functional languages.

Apply structural recursion to process recursive data types (e.g., lists, trees), recognizing it as the natural approach pioneered by the ML language family.

Identify tail-recursive functions and explain how compilers for languages like Scheme and Haskell perform tail-call optimization.

Transform non-tail-recursive functions into tail-recursive form using the accumulator-passing style.

Compare recursion-first (e.g., Haskell) and iteration-first (e.g., Python) design philosophies for solving problems.

Compose functions to build complex operations, comparing explicit composition in Python (e.g., `lambda x: f(g(x))`) with Haskell's `(.)` operator.

Apply currying to transform multi-argument functions, referencing its origins in logic and central role in ML and Haskell.

Use partial application to create specialized functions, comparing explicit approaches in Python's `functools` with implicit currying in Haskell.

Generalize list processing by implementing `fold` (reduce), analyzing its power as a universal combinator inherited from Lisp.

Evaluate point-free style and its trade-offs for code clarity, with examples from Haskell and its historical context in combinator calculus.

Analyze pipeline-style function chaining, comparing functional approaches (F#'s `|>` operator) with object-oriented method chaining.

Distinguish static typing from dynamic typing, referencing their historical origins in the Fortran/ALGOL vs. Lisp traditions.

Contrast compile-time type checking (e.g., ML, Haskell) with run-time type checking (e.g., Lisp, Python).

Describe type safety and its importance, using examples from the ML family versus C's weaker guarantees.

Explain the Hindley-Milner type inference algorithm at a conceptual level, with reference to its origins in ML.

Compare strong typing (Python, Haskell) with weak typing (C, JavaScript) using concrete examples of their design philosophies.

Analyze trade-offs between typing disciplines by comparing influential languages (e.g., C's performance vs. ML's safety).

Apply parametric polymorphism to write generic functions, explaining its implementation via type variables as pioneered by the ML language family.

Describe ad-hoc polymorphism as a mechanism for providing type-specific implementations of a common interface.

Compare two approaches to ad-hoc polymorphism: function overloading (e.g., C++) and type classes/traits (e.g., Haskell/Rust).

Describe subtype polymorphism and its relationship to inheritance in object-oriented languages like Java or Python.

Analyze the trade-offs between parametric, ad-hoc, and subtype polymorphism by comparing their use cases and implementations across language families.

Define product types using records or tuples, tracing their formalization from the ML language family.

Define sum types using variants or tagged unions, from their origins in ML through modern implementations in Rust and Swift.

Use pattern matching for control flow and data extraction, comparing ML-style matching with Python's recent structural pattern matching.

Model a type-safe expression evaluator using algebraic data types, demonstrating a central design pattern of functional languages.

Explain how sum types (e.g., Option/Maybe) improve type safety by eliminating null reference errors.

Compare algebraic data types with class hierarchies for modeling data, introducing the Expression Problem as a key design challenge.

Contrast call-by-value and call-by-name evaluation, citing historical examples like Algol 60 and their influence on modern languages.

Distinguish eager evaluation from lazy evaluation, comparing default strategies in languages like Python versus Haskell.

Analyze how evaluation strategies affect program behavior, termination, and side effects using comparative examples from Scheme and Haskell.

Implement and process infinite data structures (streams) using lazy evaluation, comparing Haskell's native support with Python's generators.

Explain how call-by-need evaluation (in Haskell) provides implicit memoization, and contrast this with explicit memoization techniques in eager languages.

Identify performance trade-offs of evaluation strategies, such as space leaks in lazy languages and redundant computation in eager ones.

Compare imperative and declarative paradigms, tracing their historical origins in von Neumann architecture versus lambda calculus.

Contrast approaches to the Expression Problem in object-oriented versus functional languages, synthesizing prior concepts on data modeling and polymorphism.

Analyze the influence of logic programming (Prolog) on modern language features like pattern matching and unification-based type inference.

Evaluate paradigm choices for data transformation, comparing the functional pipeline model (e.g., Haskell) with imperative/OO approaches (e.g., loops and iterators in Python/Java).

Evaluate paradigm choices for concurrency, contrasting functional approaches (e.g., actors in Erlang, immutability in Clojure) with traditional imperative models (e.g., threads and locks).

Analyze how Rust integrates functional, imperative, and systems programming concepts through its ownership model, trait-based polymorphism, and sum types.