• ES Español
• EN English

2.5. Foundations of Programming Languages (FPL)

The foundations of programming languages are rooted in discrete mathematics, logic, and formal languages, and provide a basis for the understanding of complex modern programming languages. Although programming languages vary according to the language paradigm and the problem domain and evolve in response to both societal needs and technological advancement, they share an underlying abstract model of computation and program development. This remains true even as processor hardware and their interface with programming tools become increasingly intertwined and progressively more complex. An understanding of the common abstractions and programming paradigms enables faster learning of programming languages.

The Foundations of Programming Languages knowledge area is concerned with articulating the underlying concepts and principles of programming languages, the formal specification of a programming language and the behavior of a program, explaining how programming languages are implemented, comparing the strengths and weaknesses of various programming paradigms, and describing how programming languages interface with entities such as operating systems and hardware. The concepts covered here are applicable to several languages and an understanding of these principles assists a learner to move readily from one language to another, as well as select a programming paradigm and language that best suits the problem at hand.

Programming languages are the medium through which programmers precisely describe concepts, formulate algorithms, and reason about solutions. Over the course of a career, a computer scientist will learn and work with many different languages, separately or together. Software developers must understand different programming models, programming features and constructs, and underlying concepts to make informed design choices among languages that support multiple complementary approaches. It would be useful to know how programming language features are defined, composed, and implemented to improve execution efficiency and long-term maintenance of developed software. Also useful is a basic knowledge of language translation, program analysis, run-time behavior, memory management and interplay of concurrent processes communicating with each other through message-passing, shared memory, and synchronization. Finally, some developers and researchers will need to design new languages, an exercise which requires greater familiarity with basic principles.

Knowledge Area (KA)	CS Core	KA Core
2.5.1 Object-Oriented Programming Fundamentals	2	1
2.5.2 Object-Oriented Programming: Encapsulation, Subtyping, and Reflection	2	1
2.5.3 Functional Programming	4	3
2.5.4 Logic Programming		2
2.5.5 Shell Scripting	2
2.5.6 Event-Driven and Reactive Programming	2	2
2.5.7 Parallel and Distributed Computing	2	2
2.5.8 Aspect-Oriented Programming	Elective
2.5.9 Type Systems Fundamentals	2	2
2.5.10 Type Systems: Polymorphism and Complementary Typing	1	1
2.5.11 Advanced Type Theory	2	2
2.5.12 Systems Execution and Memory Model	2
2.5.13 Memory Management	1
2.5.14 Language Translation and Execution	2	3
2.5.15 Program Abstraction and Representation		3
2.5.16 Syntax Analysis	Elective
2.5.17 Compiler Semantic Analysis	Elective
2.5.18 Program Analysis and Analyzers	Elective
2.5.19 Code Generation	Elective
2.5.20 Run-time Behavior and Systems	Elective
2.5.21 Advanced Programming Constructs	Elective
2.5.22 Language Pragmatics	Elective
2.5.23 Formal Semantics	Elective
2.5.24 Formal Development Methodologies	Elective
2.5.25 Design Principles of Programming Languages	Elective
2.5.26 Society, Ethics, and the Profession	Elective

2.5.1. FPL/Object-Oriented Programming Fundamentals  (CS Core: 2 hrs, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Imperative programming as a subset of object-oriented programming.
• Object-oriented design:
• Decomposition into objects carrying state and having behavior.
• Class-hierarchy design for modeling. enumerate
• Definition of classes: fields, methods, and constructors.
• Subclasses, inheritance (including multiple inheritance), and method overriding.
• Dynamic dispatch: definition of method-call.
• Exception handling.

Learning Outcomes:
Core:

1. Enumerate the differences between imperative and object-oriented programming paradigms [Enumerate]
2. Compose a class through design, implementation, and testing to meet behavioral requirements [Compose]
3. Build a simple class hierarchy utilizing subclassing that allows code to be reused for distinct subclasses [Create]
4. Predict and validate control flow in a program using dynamic dispatch [Evaluate]
5. Compare and contrast how computational solutions to a problem differ in procedural, functional, and object-oriented approaches [Compare]
6. Compare and contrast mechanisms to define and protect data elements within procedural, functional, and object-oriented approaches [Compare]

2.5.2. FPL/Object-Oriented Programming: Encapsulation, Subtyping, and Reflection  (CS Core: 2 hrs, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Object-oriented idioms for encapsulation:
• Privacy, data hiding, and visibility of class members.
• Interfaces revealing only method signatures.
• Abstract base classes, traits and mixins. enumerate
• Dynamic vs static properties.
• Composition vs inheritance.
• Subtyping:
• Subtype polymorphism; implicit upcasts in typed languages.
• Notion of behavioral replacement: subtypes acting like supertype.
• Relationship between subtyping and inheritance. enumerate
• Collection classes, iterators, and other common library components.
• Metaprogramming and reflection.

Learning Outcomes:
Core:

1. Compare and contrast the benefits and costs/impact of using inheritance (subclasses) and composition (specifically, how to base composition on higher order functions) [Compare]
2. Explain the relationship between object-oriented inheritance (code-sharing and overriding) and subtyping (the idea of a subtype being usable in a context that expects the supertype) [Explain]
3. Use object-oriented encapsulation mechanisms such as interfaces and private members [Use]
4. Define and use iterators and other operations on aggregates, including operations that take functions as arguments, in multiple programming languages, selecting the most natural idioms for each language [Define]
5. Use collection classes and iterators effectively to solve a problem [Use]
6. Compare and contrast how computational solutions to a problem differ in procedural, functional, and object-oriented approaches [Compare]
7. Compare and contrast mechanisms to define and protect data elements within procedural, functional, and object-oriented approaches [Compare]

2.5.3. FPL/Functional Programming  (CS Core: 4 hrs, KA Core: 3 hrs) ↑ Back to top

Topics:
Core

• Lambda expressions and evaluation:
• Variable binding and scope rules.
• Parameter-passing.
• Nested lambda expressions and reduction order. enumerate
• Effect-free programming:
• Function calls have no side effects, facilitating compositional reasoning.
• Immutable variables and data copying vs reduction.
• Use of recursion vs loops vs pipelining (map/reduce). enumerate
• Processing structured data (e.g., trees) via functions with cases for each data variant:
• Functions defined over compound data in terms of functions applied to the constituent pieces.
• Persistent data structures. enumerate
• Using higher-order functions (taking, returning, and storing functions).
• Metaprogramming and reflection.
• Function closures (functions using variables in the enclosing lexical environment):
• Basic meaning and definition - creating closures at run-time by capturing the environment.
• Canonical idioms: call-backs, arguments to iterators, reusable code via function arguments.
• Using a closure to encapsulate data in its environment.
• Delayed versus eager evaluation. enumerate

Non Core

• Graph reduction machine and call-by-need.
• Implementing delayed evaluation.
• Integration with logic programming paradigm using concepts such as equational logic, narrowing, residuation and semantic unification.
• Integration with other programming paradigms such as imperative and object-oriented.

Learning Outcomes:
Core:

1. Develop basic algorithms that avoid assigning to mutable states or considering reference equality [Create]
2. Develop useful functions that take and return other functions [Create]
3. Explain a simple example of lambda expression being implemented using a virtual machine, such as a SECD machine, showing storage and reclaim of the environment [Explain]
4. Correctly interpret variables and lexical scope in a program using function closures [Interpret]
5. Use functional encapsulation mechanisms such as closures and modular interfaces [Use]
6. Compare and contrast stateful vs stateless execution [Compare]
7. Define and use iterators and other operations on aggregates, including operations that take functions as arguments, in multiple programming languages, selecting the most natural idioms for each language [Define]

NonCore:

1. Illustrate graph reduction using a \(\lambda\)-expression using a shared subexpression [Apply]
2. Illustrate the execution of a simple nested \(\lambda\)-expression using an abstract machine, such as an ABC machine [Apply]
3. Illustrate narrowing, residuation, and semantic unification using simple illustrative examples [Apply]
4. Illustrate the concurrency constructs using simple programming examples of known concepts such as a buffer being read and written concurrently or sequentially [Apply]

2.5.4. FPL/Logic Programming  (KA Core: 2 hrs) ↑ Back to top

Topics:
Core

• Universal vs existential quantifiers.
• First order predicate logic vs higher order logic.
• Expressing complex relations using logical connectives and simpler relations.
• Definitions of Horn clause, facts, goals and subgoals.
• Unification and unification algorithm; unification vs assertion vs expression evaluation.
• Mixing relations with functions.
• Cuts, backtracking, and non-determinism.
• Closed-world vs open-world assumptions.

Non Core

• Memory overhead of variable copying in handling iterative programs.
• Programming constructs to store partial computation and pruning search trees.
• Mixing functional programming and logic programming using concepts such as equational logic, narrowing, residuation, and semantic unification.
• Higher-order, constraint, and inductive logic programming.
• Integration with other programming paradigms such as object-oriented programming.
• Advance programming constructs such as difference-lists, creating user defined data structures, set of, etc.

Learning Outcomes:
Core:

1. Use a logic language to implement a conventional algorithm [Use]
2. Use a logic language to implement an algorithm employing implicit search using clauses, relations, and cuts [Use]
3. Use a simple illustrative example to show correspondence between First Order Predicate Logic (FOPL) and logic programs using Horn clauses [Use]
4. Use examples to illustrate the unification algorithm and its role of parameter-passing in query reduction [Use]
5. Use simple logic programs interleaving relations, functions, and recursive programming such as factorial and Fibonacci numbers and simple complex relationships between entities and illustrate execution and parameter-passing using unification and backtracking [Use]

NonCore:

1. Illustrate computation of simple programs such as Fibonacci and show overhead of recomputation, and then show how to improve execution overhead [Apply]

2.5.5. FPL/Shell Scripting  (CS Core: 2 hrs) ↑ Back to top

Topics:
Core

• Error/exception handling
• Piping
• System commands:
• Interface with operating systems enumerate
• Environment variables
• File abstraction and operators
• Data structures, such as arrays and lists.
• Regular expressions
• Programs and processes
• Workflow

Learning Outcomes:
Core:

1. Create and execute automated scripts to manage various system tasks [Create]
2. Solve various text processing problems through scripting [Solve]

2.5.6. FPL/Event-Driven and Reactive Programming  (CS Core: 2 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Core

• Procedural programming vs reactive programming: advantages of reactive programming in capturing events.
• Components of reactive programming: event-source, event signals, listeners and dispatchers, event objects, adapters, event-handlers.
• Stateless and state-transition models of event-based programming.
• Canonical uses such as GUIs, mobile devices, robots, servers.
• Using a reactive framework:
• Defining event handlers/listeners
• Parameterization of event senders and event arguments
• Externally generated events and program-generated events enumerate
• Separation of model, view, and controller
• Event-driven and reactive programs as state-transition systems

Learning Outcomes:
Core:

1. Implement event handlers for use in reactive systems, such as GUIs [Implement]
2. Examine why an event-driven programming style is natural in domains where programs react to external events [Examine]
3. Define and use a reactive framework [Define]
4. Describe an interactive system in terms of a model, a view, and a controller [Describe]

2.5.7. FPL/Parallel and Distributed Computing  (CS Core: 2 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Core

• Safety and liveness:
• Race conditions
• Dependencies/preconditions
• Fault models
• Termination enumerate
• Programming models:
• Actor models
• Procedural and reactive models
• Synchronous/asynchronous programming models
• Data parallelism enumerate
• Properties:
• Order-based properties:
• Commutativity
• Independence enumerate
• Consistency-based properties:
• Atomicity
• Consensus enumerate enumerate
• Execution control:
• Async await
• Promises
• Threads enumerate
• Communication and coordination:
• Mutexes
• Message-passing
• Shared memory
• Cobegin-coend
• Monitors
• Channels
• Threads
• Guards enumerate
• Futures
• Language support for data parallelism such as forall, loop unrolling, map/reduce
• Effect of memory-consistency models on language semantics and correct code generation
• Representational State Transfer Application Programming Interfaces (REST APIs)
• Technologies and approaches: cloud computing, high performance computing, quantum computing, ubiquitous computing
• Overheads of message-passing
• Granularity of program for efficient exploitation of concurrency
• Concurrency and other programming paradigms (e.g., functional)

Learning Outcomes:
Core:

1. Explain why programming languages do not guarantee sequential consistency in the presence of data races and what programmers must do as a result [Explain]
2. Implement correct concurrent programs using multiple programming models, such as shared memory, actors, futures, synchronization constructs, and data-parallelism primitives [Implement]
3. Use a message-passing model to analyze a communication protocol [Use]
4. Use synchronization constructions such as monitor/synchronized methods in a simple program [Use]
5. Modeling data dependency using simple programming constructs involving variables, read and write [Implement]
6. Modeling control dependency using simple constructs such as selection and iteration [Implement]
7. Explain how REST API's integrate applications and automate processes [Explain]
8. Explain benefits, constraints and challenges related to distributed and parallel computing [Explain]

2.5.8. FPL/Aspect-Oriented Programming ↑ Back to top

Topics:
Non Core

• Aspects
• Join points
• Advice:
• Before
• After (as finally, returning or throwing)
• Around enumerate
• Point cuts:
• Designators enumerate
• Weaving - static and dynamic
• Alternatives including annotations and IDEs

Learning Outcomes:
NonCore:

1. Describe the core concepts of aspect-oriented programming, including aspects, join points, advice, and point cuts [Describe]
2. Apply static and dynamic weaving strategies to modularize cross-cutting concerns in a program [Apply]
3. Analyze alternatives to aspect-oriented programming, such as annotations and IDE-based approaches, for handling cross-cutting concerns [Analyze]

2.5.9. FPL/Type Systems Fundamentals  (CS Core: 2 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Core

• A type as a set of values together with a set of operations:
• Primitive types (e.g., numbers, Booleans)
• Compound types built from other types (e.g., records/structs, unions, arrays, lists, functions, references using set operations) enumerate
• Association of types to variables, arguments, results, and fields
• Type safety as an aspect of program correctness
• Type safety and errors caused by using values inconsistently given their intended types
• Goals and limitations of static and dynamic typing: detecting and eliminating errors as early as possible.
• Type equivalence: structural vs name equivalence

Learning Outcomes:
Core:

1. Describe, for both a primitive and a compound type, the values that have that type [Describe]
2. Describe, for a language with a static type system, the operations that are forbidden statically, such as passing the wrong type of value to a function or method [Describe]
3. Describe examples of program errors detected by a type system [Describe]
4. Identify program properties, for multiple programming languages, that are checked statically and program properties that are checked dynamically [Analyze]
5. Describe an example program that does not type-check in a particular language and yet would have no error if run [Describe]
6. Use types and type-error messages to write and debug programs [Use]
7. Explain how typing rules define the set of operations that are legal for a type [Explain]
8. List the type rules governing the use of a particular compound type [List]
9. Explain why undecidability requires type systems to conservatively approximate program behavior [Explain]
10. Explain multiple benefits and limitations of static typing in writing, maintaining, and debugging software [Explain]

2.5.10. FPL/Type Systems: Polymorphism and Complementary Typing  (CS Core: 1 hr, KA Core: 1 hr) ↑ Back to top

Topics:
Core

• Generic types (parametric polymorphism):
• Definition and advantages of polymorphism: parametric, subtyping, overloading, and coercion
• Comparison of monomorphic and polymorphic types
• Comparison with ad-hoc polymorphism (overloading) and subtype polymorphism
• Generic parameters and typing
• Use of generic libraries such as collections
• Comparison with ad hoc polymorphism (overloading) and subtype polymorphism
• Prescriptive vs descriptive polymorphism
• Implementation models of polymorphic types
• Subtyping enumerate
• Complementary benefits of static and dynamic typing:
• Errors early vs errors late/avoided
• Enforce invariants during code development and code maintenance vs postpone typing decisions while prototyping and conveniently allow flexible coding patterns such as heterogeneous collections.
• Typing rules for function, product, and sum types
• Avoiding misuse of code vs allowing more code reuse
• Detect incomplete programs vs allow incomplete programs to run
• Relationship to static analysis
• Decidability enumerate

Learning Outcomes:
Core:

1. Define and use program pieces (such as functions, classes, methods) that use generic types, including for collections [Define]
2. Discuss the differences among generics, subtyping, and overloading [Debate]

2.5.11. FPL/Advanced Type Theory  (CS Core: 2 hrs, KA Core: 2 hrs) ↑ Back to top

Topics:
Non Core

• Compositional type constructors, such as product types (for aggregates), sum types (for unions), function types, quantified types, and recursive types
• Type checking
• Subtyping:
• Subtype polymorphism; implicit upcasts in typed languages
• Notion of behavioral replacement: subtypes acting like supertype
• Relationship between subtyping and inheritance enumerate
• Type safety as preservation plus progress
• Type inference
• Static overloading
• Propositions as types (implication as a function, conjunction as a product, disjunction as a sum)
• Dependent types (universal quantification as dependent function, existential quantification as dependent product).

Learning Outcomes:
NonCore:

1. Define a type system precisely and compositionally [Define]
2. For various foundational type constructors, identify the values they describe and the invariants they enforce [Analyze]
3. Precisely describe the invariants preserved by a sound type system [Describe]
4. Prove type safety for a simple language in terms of preservation and progress theorems [Prove]
5. Implement a unification-based type-inference algorithm for a simple language [Implement]
6. Explain how static overloading and associated resolution algorithms influence the dynamic behavior of programs [Explain]

2.5.12. FPL/Systems Execution and Memory Model  (CS Core: 2 hrs) ↑ Back to top

Topics:
Core

• Data structures for translation, execution, translation, and code mobility such as stack, heap, aliasing (sharing using pointers), indexed sequence and string
• Direct, indirect, and indexed access to memory location
• Run-time representation of data abstractions such as variables, arrays, vectors, records, pointer-based data elements such as linked-lists and trees, and objects
• Abstract low-level machine with simple instruction, stack, and heap to explain translation and execution
• Run-time layout of memory: activation record (with various pointers), static data, call-stack, heap:
• Translating selection and iterative constructs to control-flow diagrams
• Translating control-flow diagrams to low level abstract code
• Implementing loops, recursion, and tail calls
• Translating function/procedure calls and return from calls, including different parameter-passing mechanisms using an abstract machine enumerate
• Green computing.

Learning Outcomes:
Core:

1. Explain how a core language construct, such as data abstractions and control abstractions, is executed [Explain]

2.5.13. FPL/Memory Management  (CS Core: 1 hr) ↑ Back to top

Topics:
Core

• Low level allocation and accessing of high-level data structures such as basic data types, n-dimensional array, vector, record, and objects
• Return from procedure as automatic deallocation mechanism for local data elements in the stack
• Manual memory management: allocating, de-allocating, and reusing heap memory
• Automated memory management: garbage collection as an automated technique using the notion of reachability

Learning Outcomes:
Core:

1. Explain how programming language implementations typically organize memory into global data, text, heap, and stack sections and how features such as recursion and memory management map to this memory model [Explain]
2. Explain why memory leaks and dangling pointer problems occur, and what can be done by a programmer to avoid/fix them [Explain]

2.5.14. FPL/Language Translation and Execution  (CS Core: 2 hrs, KA Core: 3 hrs) ↑ Back to top

Topics:
Core

• Execution models for JIT (Just-In-Time), compiler, interpreter
• Use of intermediate code, e.g., bytecode
• Limitations and benefits of JIT, compiler, and interpreter
• Cross compilers/transpilers
• BNF and extended BNF representation of context-free grammar
• Parse tree using a simple sentence such as arithmetic expression or if-then-else statement
• Execution as native code or within a virtual machine
• Language translation pipeline: syntax analysis, parsing, optional type-checking, translation/code generation and optimization, linking, loading, execution
• Run-time representation of core language constructs such as objects (method tables) and functions that can be passed as parameters to and returned from functions (closures)
• Secure compiler development

Learning Outcomes:
Core:

1. Explain and understand the differences between compiled, JIT, and interpreted language implementations, including the benefits and limitations of each [Explain]
2. Differentiate syntax and parsing from semantics and evaluation [Differentiate]
3. Use BNF and extended BNF to specify the syntax of simple constructs such as if-then-else, type declaration and iterative constructs for known languages such as C++ or Python [Use]
4. Illustrate the parse tree using a simple sentence/arithmetic expression [Apply]
5. Illustrate translation of syntax diagrams to BNF/extended BNF for simple constructs such as if-then-else, type declaration, iterative constructs, etc [Apply]
6. Illustrate ambiguity in parsing using nested if-then-else/arithmetic expression and show resolution using precedence order [Apply]
7. Discuss the benefits and limitations of garbage collection, including the notion of reachability [Debate]

2.5.15. FPL/Program Abstraction and Representation  (KA Core: 3 hrs) ↑ Back to top

Topics:
Core

• BNF and regular expressions
• Programs that take (other) programs as input such as interpreters, compilers, type-checkers, documentation generators
• Components of a language:
• Definitions of alphabets, delimiters, sentences, syntax, and semantics
• Syntax vs semantics enumerate
• Program as a set of non-ambiguous meaningful sentences
• Basic programming abstractions: constants, variables, declarations (including nested declarations), command, expression, assignment, selection, definite and indefinite iteration, iterators, function, procedure, modules, exception handling
• Mutable vs immutable variables: advantages and disadvantages of reusing existing memory location vs advantages of copying and keeping old values; storing partial computation vs recomputation
• Types of variables: static, local, nonlocal, global; need and issues with nonlocal and global variables.
• Scope rules: static vs dynamic; visibility of variables; side-effects.
• Side-effects induced by nonlocal variables, global variables and aliased variables.

Non Core

• L-values and R-values: mapping mutable variable-name to L-values; mapping immutable variable-names to R-values
• Environment vs store and their properties
• Data and control abstraction
• Mechanisms for information exchange between program units such as procedures, functions, and modules: nonlocal variables, global variables, parameter-passing, import-export between modules
• Data structures to represent code for execution, translation, or transmission.
• Low level instruction representation such as virtual machine instructions, assembly language, and binary representation
• Lambda calculus, variable binding, and variable renaming.
• Types of semantics: operational, axiomatic, denotational, behavioral; define and use abstract syntax trees; contrast with concrete syntax.

Learning Outcomes:
Core:

1. Illustrate the scope of variables and visibility using simple programs [Apply]
2. Illustrate different types of parameter-passing using simple pseudo programming language [Apply]
3. Explain side-effect using global and nonlocal variables and how to fix such programs [Explain]
4. Explain how programs that process other programs treat the other programs as their input data [Explain]
5. Describe a grammar and an abstract syntax tree for a small language [Describe]
6. Describe the benefits of having program representations other than strings of source code [Describe]
7. Implement a program to process some representation of code for some purpose, such as an interpreter, an expression optimizer, or a documentation generator [Implement]

2.5.16. FPL/Syntax Analysis ↑ Back to top

Topics:
Non Core

• Regular grammars vs context-free grammars
• Scanning and parsing based on language specifications
• Lexical analysis using regular expressions
• Tokens and their use
• Parsing strategies including top-down (e.g., recursive descent, or LL) and bottom-up (e.g., LR or GLR) techniques:
• Lookahead tables and their application to parsing enumerate
• Language theory:
• Chomsky hierarchy
• Left-most/right-most derivation and ambiguity
• Grammar transformation enumerate
• Parser error recovery mechanisms
• Generating scanners and parsers from declarative specifications

Learning Outcomes:
NonCore:

1. Use formal grammars to specify the syntax of languages [Use]
2. Illustrate the role of lookahead tables in parsing [Apply]
3. Use declarative tools to generate parsers and scanners [Use]
4. Recognize key issues in syntax definitions: ambiguity, associativity, precedence [Recognize]

2.5.17. FPL/Compiler Semantic Analysis ↑ Back to top

Topics:
Non Core

• Abstract syntax trees; contrast with concrete syntax
• Defining, traversing, and modifying high-level program representations
• Scope and binding resolution
• Static semantics:
• Type checking.
• Define before use
• Annotation and extended static checking frameworks. enumerate
• L-values/R-values
• Call semantics
• Types of parameter-passing with simple illustrations and comparison: call by value, call by reference, call by value-result, call by name, call by need and their variations
• Declarative specifications such as attribute grammars and their applications in handling limited context-base grammar

Learning Outcomes:
NonCore:

1. Draw the abstract syntax tree for a small language [Diagram]
2. Implement context-sensitive, source-level static analyses such as type-checkers or resolving identifiers to identify their binding occurrences [Implement]
3. Describe semantic analyses using an attribute grammar [Describe]

2.5.18. FPL/Program Analysis and Analyzers ↑ Back to top

Topics:
Non Core

• Relevant program representations, such as basic blocks, control-flow graphs, def-use chains, and static single assignment
• Undecidability and consequences for program analysis
• Flow-insensitive analysis, such as type-checking and scalable pointer and alias analysis
• Flow-sensitive analysis, such as forward and backward dataflow analyses
• Path-sensitive analysis, such as software model checking and software verification
• Tools and frameworks for implementing analyzers
• Role of static analysis in program optimization and data dependency analysis during exploitation of concurrency
• Role of program analysis in (partial) verification and bug-finding
• Parallelization:
• Analysis for auto-parallelization
• Analysis for detecting concurrency bugs enumerate

Learning Outcomes:
NonCore:

1. Explain the difference between dataflow graph and control flow graph [Explain]
2. Explain why non-trivial sound program analyses must be approximate [Explain]
3. Argue why an analysis is correct (sound and terminating) [Argue]
4. Explain why potential aliasing limits sound program analysis and how alias analysis can help [Explain]
5. Use the results of a program analysis for program optimization and/or partial program correctness [Use]

2.5.19. FPL/Code Generation ↑ Back to top

Topics:
Non Core

• Instruction sets
• Control flow
• Memory management
• Procedure calls and method dispatching
• Separate compilation; linking
• Instruction selection
• Instruction scheduling (e.g., pipelining)
• Register allocation
• Code optimization as a form of program analysis
• Program generation through generative AI

Learning Outcomes:
NonCore:

1. Identify all essential steps for automatically converting source code into assembly or other low-level languages [Analyze]
2. Explain the low-level code necessary for calling functions/methods in modern languages [Explain]
3. Discuss why separate compilation requires uniform calling conventions [Debate]
4. Discuss why separate compilation limits optimization because of unknown effects of calls [Debate]
5. Discuss opportunities for optimization introduced by naive translation and approaches for achieving, optimization, such as instruction selection, instruction scheduling, register allocation, and peephole optimization [Debate]

2.5.20. FPL/Run-time Behavior and Systems ↑ Back to top

Topics:
Non Core

• Process models using stacks and heaps to allocate and deallocate activation records and recovering environments using frame pointers and return addresses during a procedure call including parameter-passing examples
• Schematics of code lookup using hash tables for methods in implementations of object-oriented programs
• Data layout for objects and activation records
• Object allocation in heap
• Implementing virtual entities and virtual methods; virtual method tables and their application
• Run-time behavior of object-oriented programs
• Compare and contrast allocation of memory during information exchange using parameter-passing and non-local variables (using chain of static links).
• Dynamic memory management approaches and techniques: malloc/free, garbage collection (mark-sweep, copying, reference counting), regions (also known as arenas or zones)
• Just-in-time compilation and dynamic recompilation
• Interface to operating system (e.g., for program initialization)
• Interoperability between programming languages including parameter-passing mechanisms and data representation:
• Big endian, little endian
• Data layout of composite data types such as arrays enumerate
• Other common features of virtual machines, such as class loading, threads, and security checking
• Sandboxing

Learning Outcomes:
NonCore:

1. Discuss benefits and limitations of automatic memory management [Debate]
2. Explain the use of metadata in run-time representations of objects and activation records, such as class pointers, array lengths, return addresses, and frame pointers [Explain]
3. Compare and contrast static allocation vs stack-based allocation vs heap-based allocation of data elements [Compare]
4. Explain why some data elements cannot be automatically deallocated at the end of a procedure/method call (need for garbage collection) [Explain]
5. Discuss advantages, disadvantages, and difficulties of just-in-time and dynamic recompilation [Debate]
6. Discuss the use of sandboxing in mobile code [Debate]
7. Identify the services provided by modern language run-time systems [Analyze]

2.5.21. FPL/Advanced Programming Constructs ↑ Back to top

Topics:
Non Core

• Encapsulation mechanisms
• Delayed evaluation and infinite streams
• Compare and contrast delayed evaluation vs eager evaluation
• Unification vs assertion vs expression evaluation
• Control abstractions: exception handling, continuations, monads.
• Object-oriented abstractions: multiple inheritance, mixins, traits, multimethods
• Metaprogramming: macros, generative programming, model-based development
• String manipulation via pattern-matching (regular expressions)
• Dynamic code evaluation ("eval")
• Language support for checking assertions, invariants, and pre/post-conditions
• Domain specific languages, such as database languages, data science languages, embedded computing languages, synchronous languages, hardware interface languages
• Massive parallel high performance computing models and languages

Learning Outcomes:
NonCore:

1. Use various advanced programming constructs and idioms correctly [Use]
2. Discuss how various advanced programming constructs aim to improve program structure, software quality, and programmer productivity [Debate]
3. Discuss how various advanced programming constructs interact with the definition and implementation of other language features [Debate]

2.5.22. FPL/Language Pragmatics ↑ Back to top

Topics:
Non Core

• Effect of technology needs and software requirements on programming language development and evolution
• Problem domains and programming paradigm
• Criteria for good programming language design:
• Principles of language design such as orthogonality
• Defining control and iteration constructs
• Modularization of large software enumerate
• Evaluation order, precedence, and associativity
• Eager vs delayed evaluation
• Defining control and iteration constructs
• External calls and system libraries

Learning Outcomes:
NonCore:

1. Discuss the role of concepts such as orthogonality and well-chosen defaults in language design [Debate]
2. Objectively evaluate and justify language-design decisions [Evaluate]
3. Implement an example program whose result can differ under different rules for evaluation order, precedence, or associativity [Implement]
4. Illustrate uses of delayed evaluation, such as user-defined control abstractions [Apply]
5. Discuss the need for allowing calls to external calls and system libraries and the consequences for language implementation [Debate]

2.5.23. FPL/Formal Semantics ↑ Back to top

Topics:
Non Core

• Syntax vs semantics
• Approaches to semantics: axiomatic, operational, denotational, type-based
• Axiomatic semantics of abstract constructs such as assignment, selection, iteration using pre-condition, post-conditions, and loop invariant
• Operational semantics analysis of abstract constructs and sequence of such as assignment, expression evaluation, selection, iteration using environment and store:
• Symbolic execution
• Constraint checkers enumerate
• Denotational semantics:
• Lambda Calculus. enumerate
• Proofs by induction over language semantics
• Formal definitions and proofs for type systems:
• Propositions as types (implication as a function, conjunction as a product, disjunction as a sum)
• Dependent types (universal quantification as dependent function, existential quantification as dependent product)
• Parametricity enumerate

Learning Outcomes:
NonCore:

1. Construct formal semantics for a small language [Create]
2. Write a lambda-calculus program and show its evaluation to a normal form [Write]
3. Discuss the different approaches of operational, denotational, and axiomatic semantics [Debate]
4. Use induction to prove properties of all programs in a language [Use]
5. Use induction to prove properties of all programs in a language that is well-typed according to a formally defined type system [Use]
6. Use parametricity to establish the behavior of code given only its type [Use]

2.5.24. FPL/Formal Development Methodologies ↑ Back to top

Topics:
Non Core

• Formal specification languages and methodologies
• Theorem provers, proof assistants, and logics
• Constraint checkers
• Dependent types (universal quantification as dependent function, existential quantification as dependent product)
• Specification and proof discharge for fully verified software systems using pre/post conditions, refinement types, etc.
• Formal modeling and manual refinement/implementation of software systems.
• Use of symbolic testing and fuzzing in software development.
• Model checking.
• Understanding of situations where formal methods can be effectively applied and how to structure development to maximize their value.

Learning Outcomes:
NonCore:

1. Use formal modeling techniques to develop and validate architectures [Use]
2. Use proof assisted programming languages to develop fully specified and verified software artifacts [Use]
3. Use verifier and specification support in programming languages to formally validate system properties [Use]
4. Integrate symbolic validation tooling into a programming workflow [Integrate]
5. Discuss when and how formal methods can be effectively used in the development process [Debate]

2.5.25. FPL/Design Principles of Programming Languages ↑ Back to top

Topics:
Non Core

• Language design principles:
• Simplicity
• Security
• Fast translation
• Efficient object code
• Orthogonality
• Readability
• Completeness
• Implementation strategies enumerate
• Designing a language to fit a specific domain or problem
• Interoperability between programming languages
• Language portability
• Formal description of a programming language
• Green computing principles

Learning Outcomes:
NonCore:

1. Understand what constitutes good language design and apply that knowledge to evaluate a real programming language [Evaluate]

2.5.26. FPL/Society, Ethics, and the Profession ↑ Back to top

Topics:
Non Core

• Impact of English-centric programming languages
• Enhancing accessibility and inclusivity for people with disabilities - Supporting assistive technologies
• Human factors related to programming languages and usability:
• Impact of syntax on accessibility
• Supporting cultural differences (e.g., currency, decimals, dates)
• Neurodiversity enumerate
• Etymology of terms such as "class," "master," and "slave" in programming languages
• Increasing accessibility by supporting multiple languages within applications (UTF)

Learning Outcomes:
NonCore:

1. Consciously design programming languages to be inclusive and non-offensive [Design]