Lecture 10

--- 
Administrative





---

Control flow (2)

> Expressions 

  ...

  - Assignment
  ...
     o Initialization

       1. for staticlly allocated variables, compiler can put intial values into
          memory, to save cost at run time incurred to assignment statements 
                          ^^^^
                           ?

       2. to avoid errors caused by using a variable whose value is yet available.

     o implementation

       1. some languages may specify a default value. In C, integers, floating-points
           numbers are defaulted to zero if no initial values are provided.         
       2. a language can choose to define the use of an uninitialized variable as 
          a dynamic semantic error, oftentimes helpful in identifying program bugs.
       
   - Short-Circuit evaluation
       For boolean expressions,

       1. save time. For example,
         if(very_unlikely_condition && very_expensive_function()) ...  

       2. avoid errors. For example,
         if (d <> 0 && n/d > threshold) ...
         division by zero is avoided by short-circuit

       3. may not be desirable if the side effect is seeked 
          for the short-circuited subexpressions. 

       4. some languages provide both regular and short-circuit 
           boolean operators. In Ada, for example, and/or versus cand/cor.


> Sequencing (essential to imperative programming)

e.g.,  

in Pascal        

begin 
  s1;
  s2;
  s3
end

the semicolons are separator

in C

{
  s1;
  s2;
  s3;
}

the last semicolon is terminator

> Selection (if/else)
  - grammatical ambiguity: dangling else
  - code improvements
    o short-circuited conditions
    o case/switch statements

> Iteration

Note: with sequencing, selection, and iteration the language is already 
Turing complete.

> procedural abstraction
  (the next 3 lectures)

> recursion

  - recursion requires no special syntax;
  - any iterative algorithm can be rewritten automatically as a
    recursive algorithm, and vice versa.
  - recursion requires memory management using stacks

   procedure  P() {
           int x;
             .
             .
             .
   }

Note: each call of P will have its own storage for x if P can call 
itself recursively.  Otherwise, if no recursion, only one place is 
needed for storing because a procedure can be invoked one copy at 
every time; no two copies run simultaneously.


Tail recursion

 - fun fact n =
          if n = 0 then 1
          else n * fact (n-1)  (* multiplication can not be done *)
                               (* until fact is evaluated and returned *)

 - fun ifact n =
          let fun f p n =      (* this copy of p and n can be override *)
                               (* once this cycle is donw *)
               if n = 0 then p
               else f (n * p) (n-1)   (* multiplication can be done first *)
          in
              f 1 n
          end


> concurrency

> nondeterminacy
 - semantically aesthetic

   if a >= b -> max := a
   [] b >= a -> max := b
   fi

   a nondeterministic choice is made among the conditions that valuate to true.

 - concurrent programs require nondeterminacy
    
   server:
    loop
       if read request available
          ...
       elsif write request available
          ...
       else wait until some request is available