[Programming Language week 4] Sequence Control, Subprogram Control, Calling procedure, Parameter passing, Scoping, Heap memory

Sequence control

Sequence Conrol Structures

• Structures used in expressions
  : Precedence rules and parenthesis
• Structures used between group of statement
  : conditional and iteration statements
• Structures used between subprograms
  : subprogram calls
• Implicit control vs. Explicit control
  -- Implicit control
  : defined by the language and not modified until user redefine it
  -- Explicit control
  : programmer uses to redefine implicit control sequence (parenthesis)

Sequencing with arithmetic expressions

Prefix Notation

• Operators, then the operands
• No ambiguity and no parenthesis needed
• Number of arguments for an operator must be known a priori
• Relatively easy to decode using stack mechanism
• EX) (a+b)*(c-a) -> * + a b - c a

Postfix notation

• An operator follows its operands
• No ambiguity and no parenthesis needed
• Relatively easy to decode using stack mechanism
• EX) (a+b)*(c-a) -> a b + c a - *

Infix notation

• Only suitable for binary operations
• For more than one infix operator, it is inherently ambiguous
• EX) a + b * c : (a+b)*c or a+(b*c)
• Parenthesis is used to explicitly annotate the order
• EX) (a+b)*(c-a)

Implicit Control rules

• Implicit control rules
  : Hierarchy of operations (precedence) in C language
  ++,- : postfix/prefix increment/decrement
  *,/,% : multiplicative operators
  +,- : additive operators
  <, >, <=, >= : relational
  ==, != : equality
  &, ^, | : bitwise and xor, or
  &&, || : logical and, or
  = : assignment
  Associative
  1) left-right associativity (+, -, others)
  2) right-left associativity (exponential)
  

Issues is evaluating expressions

• Uniform Evaluation rules (eager and lazy)
  -- Eager: evaluate the operands as soon as they appear(Parallel processing)
  -- Lazy: Delay evaluation of operands as late as possible(LISP)

• Side effects
  -- Assume that a = 1; foo(x) generates 3
  x is changed to x+1 after foo()

• Error condition : No solution other than exceptional statements
  

• Short-circuit expression : Use the characteristics of "and" or "or" operation
  

Sequence Control Between Statements

• Basic statements
  : Statements that apply operations to data objects
  : Considered as a unit of step
  : e.g.) assignment operations, subprogram calls, input/output statements

• Statement Level Sequence Control
  : Composition
  -- Statements may be placed in a textual sequence and be executed in order
  : Alternation
  -- Two sequences may form alternatives and either one is executed
  : Iteration
  -- A sequence of statements are executed repeatedly, zero or more times
  

• Explicit Sequence Control
  : Goto statement
  -- Unconditional goto : Transfers control to the labeled statement
  -- Conditional goto : Transfers control to the labeled statement only if the specified condition holds
  : Break Statement
  -- Control to move forward to an explicit point at the end of given control structure, that is, immediately exit enclosing while, for, or switch statement
  : Continue statement
  -- Control to move forward to an explicit point at the end of given control structure, that is , continue from the beginning of while or for statement
  

• Conditional statement for more than one options
  -- Alternation of two or more statements, or optional execution of a single statement : IF statement or CASE statement
  -- IF statements are implemented using the usual hardware supported branch and jump instruction using Jump table
  

• Iteration statement
  -- Simple repetition
  : Repeat a fixed number of times
  : EX) perform BODY K times(COBOL)
  -- Repetition while condition holds
  : Reevalutate the condition each time after BODY
  : EX) While test do BODY vs. do BODY while test
  
  -- Repetition while incrementing a counter
  : Initial value, final value, and the increment
  : EX) for I :=1 step 2 until 30 do BODY
  -- Indefinite repetition
  : Used when the exit condition is complex and hard to express or exit condition dynamically determined
  -- In C, all 4 forms can be written by for statement
  -- Structure Sequence Control
  : Proper program = formal model of control structure, as a flow chart which,
  has a single entry arc
  has a single exit arc
  has a path from the entry arc to each node and from each node to the exit arc
  -- Prime program
  : A proper program that cannot be subdivided into smaller proper programs
  -- Composite program
  : A program that is not a prime
  -- The structure theorem
  : Any prime program could be converted into one using only while and if statements called a well-structured program

Sequencing with Non-arithmetic expressions

Pattern Matching
-- Pattern Matching operation
: An operation matches and assigns a set of variables to a predefined template

-- Term rewriting
: A restricted form of pattern match

-- Unification and substitution
: Prolog consists of facts and rules, and query
: Substitution = replacement of a string to another one
: Unification = A pattern match to determine if the query has a valid substitution consistent with the rules and facts in the database

-- Backtracking
: Backup to the previous sub-goal that matched and try another possible goal for it to match when current sub-goal is failed

Subprogram Control

Call-Return subprogram

• Simple Call-Return Subprograms
  : A request by a program/script to execute and return a pre-defined subprogram
  1) Function call : Subprogram that returns values directly
  2) Subroutine call (procedure) : Subprograms that operate only through the side effects
  : Function Definition is executed by function activation
  : Sequence control and data control involved
  

• The activation is implemented with two parts
  1) Code segments
  : Containing the executable code and constants (invariant)
  2) Activation records on the call stack
  : Containing local data, parameters and others
  : Allocated when code is called and deallocated when finished

• Calling procedure
  1) Transmit the parameters
  2) Save the return address
  3) Setup the access link
  4) Start the execution of the new procedure
  5) Set the return address back
  

Scoping Rule

• Scope
  : A region that a variable x is effective is called the scope of x
  : Local variable vs. non-local variable
• Lexical scoping rule
  : A variable is effective in the same subprogram and effective in the nested subprograms except the one which has another definition of the same variable - Called hole of x if x is redefined
• Static scope : Based on program context
• Dynamic scope : Based on program execution ( by dynamic chain )

Fun_A -> Fun_B -> Fun_D -> Fun_C

Parameters Passing

• Position correspondence vs. name correspondence

• Call-by-value (C)
  : R-value is passed
  : Mathematically clean
  : SWAP does not work
  : C uses this implementation alone to clean pointers

• Call-by-reference (Fortran)
  : Pass the lvalue of each actual parameter
  : Issues
  1) aliasing problem
  2) Mid-fault problem : Program halt in the middle of function
  

• Call-by-name
  : Procedure can be replaced by its body with actuals
  : parameters are passed unevaluated
  : Name conflict should be resolved by changing one of the variable name to unused one

• Copy-in Copy-out (Call by value result)
  : Divided into three phases
  1) Copy-in phase
  = lvalue, rvalue of actuals are computed
  = lvalue of actuals are saved
  2) Computing phase
  = rvalue are copied into formals and computed
  3) Copy-out phase
  = The results are copied into lvalues of the actuals
  : Clean when error occurs in the middle of function compared to the call by reference

  Heap memory management

  1) Fixed size Element

• Simple management by maintaining free storage list

• Easy to maintain

• Recovery methods
  -- Explicit return by programmer and system
  -- Maintaining reference count
  -- Garbage collection by "mark and sweep"

• Internal fragmentation
  : Unusable memory is contained withing an allocated region
  
  2) Variable Size Elements

• Allocation methods
  : First fit method vs. Next fit method
  : Best fit method vs. Worst fit method
  
  -- Maintain "length indicator" as well as "garbage collection bit"
  -- Compaction for memory recovery
  1) Partial compaction : only adjacent blocks are merged
  2) Full compaction : active blocks are also shifted