PoPL 2006

Programming Languages = Fun::Conceptual Structures-->Insights
and Fun() uses Labs::Insights-->Conceptual Structures!

Midsem exam: Tuesday 12 sept, 2:30-4:30 A1/A2.
Endsem exam: Wed 22 nov. 2:30-4:30 A1/A2.

Coverage

Types:
        -- types as sets
        -- primitive types
                -- sets of primitive elements
        -- composite types
                -- product types
                -- power types
                -- mappings types
                -- recursive types (lists)
        -- subtyping
                -- for primitive types (set/subset)
                -- for record types
                        -- width rule
                        -- depth rule
                        -- permutation rule
                -- for function types --} the notion of covariance and
                -- for object types   --} contravariance
        -- the notion of top and bottom types
        -- polymorphism
                -- adhoc/syntactic
                -- universal polymorphism
                -- interpretations of + operator through adhoc polymorphism
        -- why is segmentation fault a typing error

Core ideas from Object Oriented Programming Languages

        -- shared vs. embedded method implementation
        -- significance of the this/self reference
                        -- why is it needed?
        -- inheritance
                -- single and multiple
                -- method search
                -- difference between the type of a variable
                        and object which is refers to
                -- polymorphism: dynamic binding of a method name to an
                        implementation
                        -- dispatch table implementation
                -- super references and binding rules
        -- diamond inheritance problem
                        -- multiple copies of variables
                        -- ambiguous function implementations
        -- class-less languages
                -- method slots
                -- parent pointer and delegation
                -- creation by definition and creation by cloning
        -- class Object
        -- metaclasses
               -- significance of the idea of metaclasses
                -- instance-of relation
                -- classes as objects
                -- class Class
                -- brief look at meta-class hierarchy in smalltalk
        -- what are static members in C++/Java


 Storage Bindings and Scoping rules

        variables and location bindings
        type binding and storage binding
        pointer types and some tricky examples from C.
        assignment statement
        lvalues and rvalues
        table of bindings as implementation of 'environment'(i.e. set of
        all bindings)
        implementing scoping rules to identify which binding to be used
                static scoping
                dynamic scoping
               dynamic scoping


Parameter Passing
   
       call by value
       call by constant value
       call by result
       call by value result
       call by reference
       call by name
       lazy and eager evaluation of parameters

  Activation records

  Imperative style control constructs
        early ideas in structured programming
        primitive structured programming constructs
        their structured representations in terms of flow charts
        goto -- is harmful
        alternatives to goto -- java's way
                -- break
                -- labeled break
                -- continue
                -- labeled continue
       object oriented control constructs
             conditional
             conditional repeat
             n timesRepeat
                
            implementations through Block, Boolean and Integer classes

  Escape procedures and Continuations

  Concurrency and Nondeterminism

       guarded commands
       guarded regions
       implementing synchronization through guarded commands and
           guarded regions: semaphores and monitors
       concurrency and synchronization: threads and monitors

   Lambda calculus

        lambda abstractions, application
        syntactic conventions
        beta reduction
        applicative style: computation as reduction of application
        free and bound variables     
        alpha renaming
        eta reduction
        closed terms or combinators
        higher order functions
        functions with multiple parameters and currying
        Church Booleans
         logical operators
         conditional statement
       Pairs
       Church numerals
       successor
       addition, multiplication, subtraction
       Evaluation order:
          normal order reduction
          call by name reduction
          call by value reduction
          full beta reduction
       Recursion
             fix point operator
             y combinator

  Logic Programming

       declarative style
       introduction to prolog
       computing with objects and relations: facts, rules and goal  queries
       horn clauses
       backtracking
       infinite recursion problems in prolog
       some uses of cuts  
 
 + problem solving sessions: problems from last year's question sets

Reading material: