CS 470 Programming Languages
Contents
Catalog Description
The purpose of the course is to develop an understanding of the organization of programming languages and introduce the formal study of programming language specification and analysis. Topics covered usually include: language definition structure, data types and structures, control structures and data flow, run-time consideration, interpretative languages, lexical analysis, and parsing. Prerequisite - C or better in CS 202.
Prerequisites
Student must have knowledge of Programming and Elementary Data Structures
Standard Content
Course Outline
The course begins with a history of programming languages, and the various programming paradigms are introduced. The Logic Programming paradigm is covered using Prolog as the example. Backtracking, unification, recursion, the cut , depth first search are covered. Stack overflows, occurs check , and floundering problems are covered. Applications covered are list processing, state space problem solving, constraint processing, expert systems, natural language processing and parsing. The Functional Programming paradigm is illustrated using Haskell. Covered are list processing and the conversion to tail recursion using the method of accumulating parameters, fixed point computation, square root computation and sorting, testing of perfect numbers, and implementing the Sieve or Eratosthenes using Lazy Evaluation, available in Haskell. Proofs of list properties using structural induction are covered, and the implementation of data structures using Haskell is covered. The Object Oriented Programming paradigm is covered using Smalltalk: introduced are the elements of the GUI: browsers, Workspaces, and Transcripts, Defining classes, and objects, inheritance and aggregation hierarchies are introduced. Avoidance of conditional code through polymorphism, polymorphism within and across inheritance hierarchies is considered, and the model –view – controller pattern through the use of the dependency mechanism are described. The issue of aggregation vs. inheritance is discussed via a concrete example. The Concurrent Programming paradigm is introduced. Three synchronization problems are considered: Serialization, Mutual Exclusion and the Rendezvous. Semaphores are introduced and the use of Semaphores in solving the synchronization problems are discussed. Implementations of the solutions are given in Smalltalk, using the Process and Semaphore implementations available in Smalltalk. Finally aspects of the syntax and semantics of programming languages are covered.
Learning Outcomes
Functional, Logic, Object-Oriented and Concurrent programming paradigms, syntax and semantics of programming languages.
Important Assignments and/or Exam Questions
In each of the programming paradigms, short assignments, and a larger assignment are given.
Standard resources
- [1] Learn Prolog Now http://www.learnprolognow.org/
- [2] Learn You a Haskell for Great Good http://learnyouahaskell.com/
- [3] Squeak Smalltalk https://squeak.org/
- [4] The Little Book of Semaphores http://greenteapress.com/semaphores/LittleBookOfSemaphores.pdf
- [5] Syntax and Semantics of Programming Languages http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/
