SEN2001 · Programlama Dilleri

Programming Languages

Syntax and semantics, binding and scope, data types, subprograms, functional and logic programming.

Textbook: Robert W. Sebesta, Concepts of Programming Languages, 8e, Pearson Education, Addison Wesley, 2008, ISBN 978-0-321-50968-0

Week 1
Introduction
- Introduction: language evaluation criteria and influences on language designWhy we study programming languages, application domains, the readability/writability/reliability/cost criteria, orthogonality, design trade-offs, the influence of the von Neumann architecture and language categories.
- Implementation methods and the evolution of languagesCompilation, pure interpretation and hybrid implementation; compiler phases, linker and preprocessor, JIT; programming environments and the milestones in the evolution of languages from Fortran to Java that are asked on exams.
Week 2
Describing Syntax and Semantics I
- Syntax: BNF, derivation, parse tree and ambiguityWriting language rules with BNF and EBNF, producing leftmost derivations, drawing parse trees, proving ambiguity and reading precedence/associativity from a grammar. The part of the midterm that brings the most points.
Week 3
Describing Syntax and Semantics II
- Semantics: attribute grammar and weakest preconditionAttribute grammars for static semantics (synthesized, inherited, intrinsic), the three methods of dynamic semantics, and computing weakest preconditions with axiomatic semantics.
- Lexical and syntax analysis: lexer, recursive descent, LL and LRThe lexer producing lexemes/tokens, state diagrams, tracing a recursive-descent parser, removing left recursion, the pairwise disjointness test and the idea of bottom-up (shift-reduce) parsing.
Week 4
Names, Bindings, Type Checking and Scopes
- Names, binding, lifetime and scope (static vs dynamic)The six attributes of a variable, the binding time table, the four storage categories, the difference between scope and lifetime, and tracing program output under static/dynamic scope.
Week 5
Data Types
- Data types I: primitive, string, enum and array addressingPrimitive types, string design, enumeration, array categories, row-major and column-major address formulas, and associative arrays. Address computation is guaranteed points on the midterm.
- Data types II: record, union, pointer and type equivalenceRecords and tuples, free and discriminated unions, pointers/references, dangling pointers and memory leaks, heap management, type checking, strong typing and name/structure type equivalence.
Week 6
Expressions and Assignment Statements
- Expressions and assignment: precedence, side effects, short-circuit, coercionOperator precedence and associativity, operand evaluation order and functional side effects, short-circuit evaluation, mixed-mode expressions and type conversions, forms of assignment. The source of the “What is printed?” questions on the exam.
Week 7
Control Structures
- Control structures: selection, loops and guarded commandsTwo-way and multiple-way selection (switch fall-through), counter-controlled and logically-controlled loops, break/continue, iterator loops, goto and Dijkstra's guarded commands. The output-tracing questions are here.
Week 8
Subprograms I
- Subprograms I: parameter passing methodsFormal/actual parameters, the in/out/inout models and five implementations: pass-by-value, result, value-result, reference, name. Tracing what the same program prints under each method; also Java's rule, closures and default parameters.
Week 9
Subprograms II
- Subprograms II: activation records, static and dynamic chainsWhat happens at call and return, the structure of an activation record, the run-time stack, recursion, nonlocal access through the static chain in nested subprograms (chain_offset, local_offset), blocks and the deep/shallow access implementation of dynamic scope.
Week 10
Abstract Data Types
- Abstract data types (ADT) and encapsulationThe concept of abstraction, the two conditions of an ADT, information hiding, Ada packages, C++ and Java classes, parameterized ADTs (generics) and encapsulation constructs for large programs (namespace, package).
Week 11
Object-oriented Programming
- Object-oriented programming: inheritance, dynamic binding and vtablesThe three features of OOP, inheritance and subtypes, finding which method runs with dynamic binding, the difference between override/overload/hiding, multiple inheritance and the implementation of dynamic binding with a vtable.
Week 12
Exception Handling and Event Handling
- Exception handling and event handlingThe concept of exceptions and design questions, binding to a handler and propagation, the try/catch/finally flow in Java, checked/unchecked exceptions, a C++ and Ada comparison; event-driven programming, the listener model and the JavaScript event loop.
Week 13
Functional Programming
- Functional programming: Scheme, lambda, map and recursionThe idea of a mathematical function, LISP data structures (atom, list, cons cell), car/cdr/cons in Scheme, define and lambda, if/cond/let, recursive list functions, higher-order functions (map, filter, compose) and tail recursion.
Week 14
Logic Programming
- Logic programming: Prolog, unification and resolutionFrom propositional logic to Prolog: fact, rule and query, unification and instantiation, depth-first search with resolution and backtracking, lists, arithmetic (is), cut and the closed-world assumption. Finding the answers to queries and their order.