(CS = Computer science)
- The CS is a revolution in the way we think, and in the way in which we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology -- the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects.
Mathematics provides a framework for precisely dealing with notions of "what is".
Computation provides a framework for precisely dealing with notions of "how to."
- When some field is just getting started and you don't really understand it very well, it's very easy to confuse the essence of what you're doing with the tools that you use.
- CS is about "How to do things" or "How to compute things": Process.
- Every powerful language has three mechanisms:
* There are primitive expressions that represent the simplest entities with which the
language is concerned.
* There are means of combination by which compound expressions are built from
simpler ones.
* There are means of abstraction by which compound objects can be named and
manipulated as units (ie: separate use from representation, layered system).
- Building a programming language is a complex job ==> Techniques for controlling this complexity:
1- Black Box abstraction (refers to a procedure): In a programming language you should define primitive procedure/data + means of construction of new procedures/data
2- Conventional interface:
All data are represented in an unified type -Conventional type - (ie: lists), and there is a universal and convenient set of generic operators for this type (ie: map, filter, accumulate ...). It aims to produce a modular design
3- Metalinguistic abstraction : creating new (high level) languages on top of your programming language (maybe popularised recently through DSL).
- Define in Lisp, as the basic mechanism for naming, is our language's simplest means of abstraction. Computational objects may have very complex structures, and it would be extremely inconvenient to have to remember and repeat their details each time we want to use them.
- Substitution model variants:
>> Fully expand and then reduce method is known as normal order evaluation.
>> Evaluate the arguments and then apply method that the interpreter actually uses, which is called applicative order evaluation.
- The contrast between function and procedure is a reflection of the general distinction between describing properties of things and describing how to do things,
- Theorem:
Applied order evaluation terminates ==> Normal order evaluation terminates too
- A procedure definition binds its formal parameters to names. If a parameter is not bound, we say that it is free. The set of expressions for which a binding defines a name is called the scope of that name.
i.e: " sum (x, y){x + y} "; 'x' and 'y' are bound, '+' is free
- A closure is any procedure that is "encapsulated" within an environment. Often, the environment is a lexical scope of an other procedure. By nature, a closure owns free variables (unbound operands).
- A procedure is a pattern for the local evolution of a computational process. It specifies the evolution of a process in the same way that a differential equation describes the evolution of a physical system
- Process types:
>> Recursive = characterized by a chain of deferred operations (to keep track of all partial computations). The process consumes an
amount of memory that grows with the number of procedure calls.
>> Iterative = characterized by a fixed number of variables, called state variables,
together
with a fixed rule that describes how the state variables should be
updated as the process moves from state,to state, and an (optional) end
test that specifies conditions under which the process should terminate.
The process is executed in a constant space (no growth).
- The
time required by a tree-recursive process will be proportional to the
number of nodes in the tree, while the space required will be
proportional to the maximum depth of the tree.
- Order of growth:
>> Let n be the size of a problem (a property of the problem with respect to which it will be desirable to analyse a given process),
>> Let R(n) be the amount of resources the process requires (the number of internal storage registers used, the number of elementary machine operations performed ...)
>> Linear growth: doubling the size will roughly double the amount of resources used.
>> Exponential growth:
each increment in problem size will multiply the resource utilization by a constant factor.
>> Logarithmic growth: doubling the
problem size increases the resource requirement by a constant amount.
No comments:
Post a Comment