Exam Syllabus

Related Courses

  • CS 320 Programming Languages: Procedural Languages
  • CS 520 Programming Languages: Alternative Designs

References

  • C++ Primer, 2’nd Edition, by Stanley Lippman, Addison-Wesley, 1991.
  • The SR Programming Language: Concurrency in Practice, by Andrews and Olsson, Benjamin/Cummings, 1993
  • An Introduction to Object-Oriented Programming, by Timothy Budd, Addison-Wesley, 1991
  • Programming in Prolog by Clocksin and Mellish
  • Goldberg, A. and Robson, D. Smalltalk-80: The Language. Addison Wesley, Menlo Park, CA, 1989

Topics

For non-ANS languages, the term ‘working knowledge’ is used, and implies the ability to read, and write with reasonable accuracy, code from these languages which involves commonly used features.

CS 320 level

1. Languages covered

Candidates should have reading and writing knowledge of JAVA, FORTRAN 77, and C, and working knowledge of Lisp (or other applicative language like ML or Haskell).

2. Classification of languages

  • Imperative vs. applicative languages
  • High-level vs. low-level languages
  • Static vs. block-structured languages
  • General-purpose vs. simulation languages
  • Sequential vs. concurrent languages
  • Basic historical facts in language evaluation
  • Basic facts about language processors (translators, compilers, assemblers, cross-compilers, interpreters, simulators)

3. Formal means for defining language syntax

  • BNF
  • Extended BNF
  • Syntax diagrams
  • Cobol notation

4. Constants

  • Constant types
  • Constant expressions
  • Symbolic constant names

5. Variables and types

  • Concept of variables and binding
  • Basic data types
  • Complex type in FORTRAN
  • Aggregates (arrays, records)
  • Representation of arrays (column-major vs. row-major ordering)
  • Unions and discriminated unions
  • Data initialization
  • Data retention
  • Pointers, indirect addressing, pointer arithmetic, dangling pointer problem
  • Typing
  • Static vs. dynamic typing
  • Strong typing vs. weak typing
  • User-defined types and type names

6. Expressions, operators, and assignments

    • Operator hierarchy (logical, relational, arithmetic and string operators and expressions)
    • Operator precedence and associativeness
    • Operator overloading
    • Parsing expressions using BNF and EBNF
    • Lazy evaluation
    • Type of expressions, coercions
    • Exotic operators in C
      • Auto-increment/decrement operator
      • Assignment operators
      • Comma operator
      • Bitwise operators

 

  • Conditional semantics
  • Semantics of assignment statement
  • Multiple assignments (examples from PL/I, Algol 60, and C)
  • Assignments by I/O
  • Aggregate statements
  • Intrinsic functions
  • Statement functions (FORTRAN)

7. Control structures

  • Unconditional and conditional branching
  • Dangling else problem and its solution (including Algol 60)
  • Multiway branching
  • Iteration
  • Pretest and posttest loops
  • Forced loop exit
  • Variable vs. constant iteration parameters

8. Procedural abstractions

  • Procedure declaration and procedure call
  • Nested declarations
  • Recursion
  • Actual vs. formal parameters
  • Parameter passing (call by value, call by reference, call by name, call by value-result)
  • Jensens device
  • Array parameters and assumed size arrays
  • Procedure parameters
  • Side-effects and pure functions
  • Multiple entry and multiple exit procedures in FORTRAN 77 and their use in building data abstractions
  • Function/procedure prototypes

9. Scope of names

  • Blocks
  • Local and global variables
  • Storage types (automatic, static, external, dynamic)
  • Scope rules
  • Lexical vs. dynamic scoping
  • Aliasing
  • Extent

10. Implementation issues

  • Execution environment in static and block-structured languages (static data area, program area, run-time stack, environment pointer, argument pointer, instruction pointer)
  • Representation of local and global variables
  • Representation of formal parameters
  • Activation records
  • Static and dynamic links in Pascal
  • Implementation of blocks in C
  • Dynamic storage allocation and garbage collection
CS 520 level

1. Languages covered

Students should have a working knowledge of C++, SR and Prolog . Some concepts may require a reading knowledge of the corresponding notation from Ada or Smalltalk.

2. Logic programming

  • Facts
  • Questions
  • Rules
  • Variables
  • Instantiation of variables
  • Matching
  • Structures
  • Backtracking
  • Unification
  • Operators
  • Dynamically modifying facts
  • Lists
  • Head and tail of lists
  • Accumulators
  • Cut operator

3. Object-oriented programming

    • Abstract data types, information hiding, data encapsulation
    • Concept of class and object
    • Realization of class and objects in C++
      • Data and function class members
      • Static members
      • Levels of information hiding
      • Friends
      • Virtual

 

    • Functions, constructors, destructors, this, class templates
    • Realization of class and objects in Smalltalk
      • Methods
      • Instance methods
      • Class variables
      • Class methods
      • super
      • self
      • Metaclasses

 

  • Difference between messages and function calls
  • Static and dynamic binding of objects and methods
  • Creation and initialization of objects: stack verses heap
  • Constructors and class methods
  • Statically typed verses dynamically bound languages
  • Inheritance
  • Name ambiguity in multiple inheritance
  • C++ public, protected, private, and virtual base classes
  • Overloading functions versus inheritance of functions
  • SR’s interface inheritance. Subtypes versus subclasses
  • Assignment of objects: copy semantics verses pointer semantics
  • Meaning of equals
  • Polymorphism. Polymorphic objects in C++ and Smalltalk
  • Benefits and cost of polymorphism

4. Advanced features of high-level languages

  • Exceptions: Scope of exceptions, raising exception, exception handlers
  • Examples from C++, Ada
  • Procedures: default parameters, overloading, generic or template functions

5. Concurrent programming

  • Coroutines, multitasking
  • Process communication and synchronization
    • Semaphores( binary and general)
    • Monitors
    • Asynchronous message passing
    • Message queues
    • Remote procedure calls
    • Rendezvous
  • Procedure calls vs. message passing
  • Implementation of semaphores and monitors via message queues
  • Deadlock, livelock, concurrency verses parallelism
  • Impact of parallelism on procedure parameters
  • Guarded command: SR if statements, loops
  • Examples from SR