CS 329 Principles of Programming Languages
Instructor: rkj

Slot 6, Room A2

    Post-diwali extra slots: Nov 7-Mon 8:30 pm (A2),
                        Quiz: nov 8-Tue  8:30 pm (A1, A2).
                        Nov. 11: 8:30 pm, A2.

Evaluation Scheme
    Quiz 1: 10% August 29th
    Midterm: 30%  - Friday Sept 23, 9:30-11:30 AM in rooms A1, A2.
    Quiz 2: 10%
    End-semester: 50%

Lecture Notes for your Reference

• The Machine and its language abstractions tower:
  
  • how it works- the big picture
  •   lab1 was designed to give you an idea about this big picture
  • bonus points to those who implemented both parts a & b
    

• High level languages- compilers and interpreters
• Shell: the command interpreter
• OS: The resource manager: system call interpreter
• Processor: The Machine Language (opcodes) interpreter
• control and data abstractions of the machine language


• Overview of the Course
• Values and types
• Types as sets
• Type construction by value enumeration
• Composite Types
• lab 2 was on construction of types and their composites as sets; we did not worry about instance creation!
  
• Cartesian Product types
• Disjoint Union Types
• Function types (mappings)
• Powersets
• Recursive Types
• Modeling Array and String types
• What is a Segmentation fault?
• The notion of type-safety
• Typchecking: Static vs. Dynamic checking
• Variables: typed and untyped- Static Vs. Dynamic typing
• statically and dynamically checked languages
• statically and dynamically typed languages
• Variables and values: lvalue and rvalue
• Operators as function types, and overloading of operators
• Implementation of overloading
• one implementation for each overloaded operation
  
• A combination of a fewer overloaded implementations and coercion
• One implementation for all overloaded operations, use coercion
  
• Overloading as apparent or syntactic polymorphism
• polymorphism is resolved during compile time
  
• An example in a hypothetical language in which polymorphism cannot be resolved at compile time
• Subtyping 'A <: B' relation and subsumption/safe substitution
  
• Simple enumerations
• Record subtypes
• Depth subtyping rule
  
• Width subtyping rule
  
• The combined rule
  
• Function subtypes
• covariance and contravariance
• lab 3 was on subtyping of simple enumerations, function & record types
• bonus points to those who implemented the record permutation rule
  
• Relating subtyping to polymorphism
• types polymorphic in terms of their subtypes
• Type Equivalence
  
• Structural
  
• Nominal (name equivalence)
• The record permutation rule
• subtyping as a reflexive and transitive relation

• Subsumption in OOPLs & its implementation
  
• Subtyping induced by subclassing
• Static vs. dynamic type of an instance
• Embedded vs. shared implementation of member functions
• The this pointer
• Dispatch table of method bindings associated with static type
  
• Visibility control through dynamic type
  
• Using the above dispatch table as a dynamic dispatch mechanism
• The case of single inheritance
•  Lab 4: implementation of dynamic binding in C
• single inheritance
• use void pointers, function pointers, pointers to function pointers

• Implementing subsumption: The case of Multiple inheritance
• Memory layout: aligning subobjects
• Correct computation of the self (this) pointer
• organization of dispatch table - order of entries
• how many dispatch tables?
• sharing of dispatch tables
  
• implementation of typecasting operation
  
•  Lab 6: An implementation of dynamic binding & typecasting over multiple inheritance
• Subsumption in OOPLs as a reuse mechanism 
• Type-safe Narrowing
• connection with reuse
• when is narrowing typesafe
  
• dynamic typechecking in narrowing operation & exceptions

• Inheritance as a private matter
• non-subtyping view
  
• Diamond Inheritance
  
• multiple & repeated inheritance
• multiple & shared inheritance
• Ambiguities in member function binding
• Solutions of C++ and Java

• Classes as objects & Metaclasses
  
• classes of classes-Metaclasses
• Top Object type & Top Class type
• Class attributes and class members (receiver as a class)
• Smalltalk's metaclasses
• C++ and Java's model of meta-level members
  
• Classless OOPLS
  
• prototype-based languages
  
• function-data-parent slots
• cloning as a primitive operation

• Names & bindings
• Static  Binding
• Dynamic binding
• Block-structured binding

• type binding
• storage binding
•  lab 7 used a flat binding table

• Static (lexical) and Dynamic scoping
• The difference between scoping and binding
  
• dynamic and static scoping rules
• Pointers to implementation of scoping rules
  
• more in lab after you are back from industrial visit
  
• closures for static scoping
  
• identifier binding- stacks for dynamic scoping
• lab 8: we discussed a simple extension to lab7 implementation
• Tutorial coverage:
• level 0 languages-(classless)
  
• relation between Class Top type and Object Top type
• bindings for variables of pointer types
  
• investigation into dynamic/static binding X dynamic/static scoping possibilities
  
• can classes have rvalues and lvalues? (classes as objects-metaclasses)

• Parameter Passing Mechanisms
• Call by value
• Call by reference
• Call by constant value
• Call by constant reference
  
• Call by result
  
• Call by value-result (copy/restore)
(not equivalent to call by reference)
• Call by name (as in Algol 60)
  
• Lazy vs. eager evaluation
• lab 9 on parameter passing mechanisms in a few languages
  

• Activation Records
• handling of Globals/COMMON
  
• parameters
• return address - why on activation stack?
  
• environment pointer and control links (dynamic link)
  
• communication between activation records as per scoping rules
  
• access links (static link)
• return value communication
• accommodating call by reference and other parameter passing
  
the cases of

• Non-procedural nested blocks
  
• flat subroutines
  
• procedure calls and recursion
  
• nested procedure definitions

• Control Structures (imperative style)
  
• Structured programming
  
• Dijkstra's structure (D-structures): single entry, single exit control structures
• Extended D-structures & their flow-graph representations
  
• primitive statement, sequential composition, conditional statement,
  
• conditional repetition forms (do while, while do, repeat until, for loops),
  
• case statement
  
• GOTO --> unstructured programs
  
• Modern multiple exit non-goto forms
  
• return, exit, exceptions
• unconditional break, labeled break, continue, labeled continue
  
• Pure object oriented formulations of control constructs
  
• if-then-else through a boolean hierarchy and blocks as objects,
  
• while-do through block receivers and block arguments, times-repeat on Integers
  
• Exception Handling Mechanism of Smalltalk
  
• lab 10: experiments on control constructs
  

• Untyped Lambda Calculus
  
• Abstraction and Application
• syntactic conventions to be followed
  
• Multiple arguments & Curried forms
  
• Free and bound Variables
  
• Beta reduction
• Higher order functions
  
• Encoding the booleans: Church Booleans
• Construction of the Conditional (if-then-else)
• Logical operators (and, or, isfalse, istrue, not, xor) as lambda abstractions 
• Lab 11: Scheme programs equivalent to above encodings
  
• Normal form; Evaluation; redexes, order of reduction, termination of reduction
  
• normal order reduction
• call-by-value reduction,
  
• call-by-name reduction
  
• full beta reduction
• Alpha renaming and Eta conversion
• Pairs and accessor functions
  
• Church Numerals
• Successor function
• Addition and Multiplication of numbers
  
• Raising to a power
• Predecessor function -- using pairs
  
• Subtraction
  
• Testing: zero testing, equality testing
• Recursion
• The problem of representing self calls in presence of anonymity
  
• Divergent combinators - the omega combinator
• Fixed points (or fixpoints) and fixed point combinator
• The call by name Y combinator 
  
• Single step and recursive function definition
  
• Example- fact n as Y g n  -- watch the termination


• Concurrency, Synchronization and Non-determinism
  
• Concurrency abstractions- specifying concurrent 'Activities'
• Ability to hold and resume execution of a concurrent thread of execution
• Thread safe sharing of resources/objects/processes
• Example of Java's model of concurrency
  
• OS level concurrency Vs. Programming Language level concurrency
• Introduction to Nondeterminism
• guarded commands
• guarded regions

• Logic Programming
• Programming with relations
• Goal Queries

• Horn clauses
  
• Prolog's Resolution & Unification
• Execution flow & Potential infinite recursion problem
• Backtracking and controlling backtracking with cuts

Reading material:

• David Watt, Programming Language Concepts and Paradigms, Prentice-Hall, 1990
• Fischer & Grodzinsky, The Anatomy of Programming Languages, Prentice Hall, 1993
• Iain Craig, The interpretation of object oriented programming languages, Springer, 2002
• Kenneth Louden, Programming Languages: Principles & Practice, 2003
• Selected Articles.