CSC302 2006S, Class 28: Declarative Programming

Admin:
* Post-mid-semester examination distributed.
* Sick family + spring cleaning + exam writing = no grading.  Sorry.
* One of you argued that Saturday's Harris Party should count for EC.
* Talk tomorrow at 4:30.  EC.  Class at 11:00.  EC.
* The reading for Wednesday will be announced this afternoon.
* Absent: Dimitar

Overview:
* Admin
  * About the examination.
  * About the project.
* Declarative
  * What is a declarative language?
  * Common forms of declarative languages.
  * Why have declarative languages?

Language paradigms
* Imperative - Algorithms are sequences of instructions
* Functional - Algorithms are defined by definition, application, and composition of functions
* Object-Oriented - Algorithms are defined in terms of interacting objects

* Declarative - Algorithms are collections of facts and questions
  * Declarative algorithms specify *what* we want to compute and a context, but as little as possible about *how* to compute it

What are some key declarative languages?
* Regular expressions - Specify *what* to match, but not how to match it.
  ^((a*b)*|(ababc))$
  * Create an NFA
  * Convert it to a DFA
  * Turn the DFA into simple code.
* SQL and other relational database languages
  SELECT name,id from PEOPLE where id < 100;
  * Of course, real SQL programmers consider the efficiency of their code
* Predicate logic languages (Prolog)
  * Make statements in predicate logic and ask questions
    * if X is a man then X is human
    * if X is a human then X will die
    * Sam is a man
    * will Sam die?
    * X is the sorted version of Y if X is a permutation of Y and X is sorted
    * What is the sorted version of [34,1,2,6,2]?
* Pure functional programming (Haskell; Equations)
  * It shouldn't matter which order the functions are evaluated in
  * Church-Rosser Thm: If there is a way to compute a solution, then outermost/lazy evaluation will compute it

Why have these things?
* Rely on language designer to do the work for you
* For certain types of algorithms, more "efficient"