"The removal of much of the accidental complexity of programming means that the intrinsic complexity of the application is what's left."

- Security Engineering, Ross J. Anderson (2001)

"If you want people to do something the right way, you must make the right way the easy way."

- Traditional saying

- This section describes two additional computation models (which are related to each other).
- We did not cover all the computation models, and new models will be created in the future.

- A procedure in declarative model uses its input arguments to calculate the values of its output arguments.
- For a given set of input argument values, there is only one set of output argument values.

- A relational procedure is more flexible in two ways:
- there can be any number of results to a call - either zero (no results), one, or more
- which arguments are inputs and which are outputs can be different for each call

- Relational programming is well-suited for databases, parsers, and for enumerating solutions to complex combinatoric problems.
- Relational programming extends declarative programming with a new kind of statement called "choice".
- The choice is implemented with search, which enumerates the possible answers.

- Relational programming is practical:
- when the search space is small
- as an exploratory tool

- To use search in other cases (when brute force exploration is not possible in real space/time), more sophisticated techniques are needed (e.g., constraint-solving algorithms, optimizations based on the problem structure, and search heuristics).

- Constraint programming consists of a set of techniques for solving constraint satisfaction problems.
- A constraint satisfaction problem (CSP) consists of a set of constraints on a set of variables.
- "X is less than Y" or "X is a multiple of 3"

- A constraint satisfaction problem (CSP) consists of a set of constraints on a set of variables.
- Constraint programming is close to the ideal of declarative programming: to say
*what*we want without saying*how*to achive it. - Propagate-and-search (a general approach for tackling CSPs) is based on three important ideas:
- Keep partial information -> During the calculation, we might have partial information about a solution (e.g., "in any solution, X is grater than 100").
- Use local deduction -> Each of the constraints uses the partial information to deduce more information. For example, combining the constraint "X < Y" and the partial information "X > 100", we can deduce that "Y > 101" (assuming Y and X are integers).
- Do controlled search -> When no more local deductions can be done, then we have to search. The idea is to search as little as possible: we will do just a small search step and then try to do local deduction again.

- Constraint programming is a type of logic programming.

- There exist many computation models that differ in how expressive they are and how hard it is to reason about programs written in them.
- The declarative model is one of the simplest, however, it has serious limitations for some applications.
- There are more expressive models that overcome these limitations, at the price of sometimes making reasoning more complicated.
**Rule of least expressiveness**: When programming a component, the right computation model for the component is the least expressive model that results in a natural program.

**Declarative sequential model**-> This model encompasses strict functional programming and deterministic logic programming. It extends the former with partial values (dataflow variables) and the latter with higher-order procedures.**Declarative concurrent model**-> This is the declarative model extended with explicit threads and by-need computation (lazy evaluation). It includes lazy functional programming and deterministic concurrent logic programming.**Message-passing concurrent model**-> This is the declarative model extended with communication channels (ports). This removes the limitation of the declarative concurrent model that it cannot implement programs with some nondeterminism.**Stateful model**-> This is the declarative model extended with explicit state (mutable variables). This model can express sequential object-oriented programming. In this model components have history.**Shared-state concurrent model**-> This is the declarative model extended with both explicit state and threads. This model contains concurrent object-oriented programming. Reasoning with this model is the most complex since there can be multiple histories interacting in unpredictable ways.**Relational model**-> This is the declarative model extended with search. It encompasses nondeterministic logic programming. This model is a precursor to constraint programming.