Logic Programming Languages

January 13rd, 2018

In this last and final session of the semester, we re going to discuss about Logic Programming Languages.

so what is  Logic Programming Languages.

Logic programming is a type of programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, Answer set programming (ASP) and Datalog.

Proposition

A logical statement that may or may not be true

–Consists of objects and relationships of objects to each other

Symbolic Logic

Logic which can be used for the basic needs of formal logic:

–Express propositions

–Express relationships between propositions

–Describe how new propositions can be inferred from other propositions

Particular form of symbolic logic used for logic programming called predicate calculus

Object Representation

• Objects in propositions are represented by simple terms: either constants or variables
• Constant: a symbol that represents an object
• Variable: a symbol that can represent different objects at different times

–Different from variables in imperative languages

Compound Terms

• Atomic propositions consist of compound terms
• Compound term: one element of a mathematical relation, written like a mathematical function

–Mathematical function is a mapping

–Can be written as a table

Parts of a Compound Term

Compound term composed of two parts

–Functor: function symbol that names the relationship

–Ordered list of parameters (tuple)

Examples:

student(jon)

like(seth, OSX)

like(nick, windows)

like(jim, linux)

Forms of a Proposition

Propositions can be stated in two forms:

–Fact: proposition is assumed to be true

–Query: truth of proposition is to be determined

Compound proposition:

–Have two or more atomic propositions

–Propositions are connected by operators

Logical Operators

Quantifiers

Overview of Logic Programming

Declarative semantics

–There is a simple way to determine the meaning of each statement

–Simpler than the semantics of imperative languages

Programming is nonprocedural

–Programs do not state now a result is to be computed, but rather the form of the result

Terms

• This book uses the Edinburgh syntax of Prolog
• Term: a constant, variable, or structure
• Constant: an atom or an integer
• Atom: symbolic value of Prolog
• Atom consists of either:
  1. a string of letters, digits, and underscores beginning with a lowercase letter
  2. a string of printable ASCII characters delimited by apostrophes

Terms: Variables and Structures

• Variable: any string of letters, digits, and underscores beginning with an uppercase letter
• Instantiation: binding of a variable to a value
  1. Lasts only as long as it takes to satisfy one complete goal
• Structure: represents atomic proposition
  functor(parameter list)

Fact Statements

• Used for the hypotheses
• Headless Horn clauses

  female(shelley).
  male(bill).
  father(bill, jake).

Rule Statements

• Used for the hypotheses
• Headed Horn clause
• Right side: antecedent (if part)
  • May be single term or conjunction
• Left side: consequent (then part)
  • Must be single term
• Conjunction: multiple terms separated by logical AND operations (implied)

Goal Statements

• For theorem proving, theorem is in form of proposition that we want system to prove or disprove – goal statement
• Same format as headless Horn
  man(fred)

• Conjunctive propositions and propositions with variables also legal goals
  father(X, mike)

Inferencing Process of Prolog

• Queries are called goals
• If a goal is a compound proposition, each of the facts is a subgoal
• To prove a goal is true, must find a chain of inference rules and/or facts. For goal Q:

P2 :- P1

P3 :- P2

…

Q :- Pn

• Process of proving a subgoal called matching, satisfying, or resolution

Approaches

• Matching is the process of proving a proposition
• Proving a subgoal is called satisfying the subgoal
• Bottom-up resolution, forward chaining
• Top-down resolution, backward chaining
• Prolog implementations use backward chaining

Subgoal Strategies

• When goal has more than one subgoal, can use either
  • Depth-first search:  find a complete proof for the first subgoal before working on others
  • Breadth-first search: work on all subgoals in parallel
• Prolog uses depth-first search
  • Can be done with fewer computer resources

Backtracking

• With a goal with multiple subgoals, if fail to show truth of one of subgoals, reconsider previous subgoal to find an alternative solution: backtracking
• Begin search where previous search left off
• Can take lots of time and space because may find all possible proofs to every subgoal

Simple Arithmetic

• Prolog supports integer variables and integer arithmetic
• is operator: takes an arithmetic expression as right operand and variable as left operand

A is B / 17 + C

• Not the same as an assignment statement!
  • The following is illegal:

Sum is Sum + Number.

Trace

• Built-in structure that displays instantiations at each step
• Tracing model of execution – four events:
  • Call (beginning of attempt to satisfy goal)
  • Exit (when a goal has been satisfied)
  • Redo (when backtrack occurs)
  • Fail (when goal fails)

List Structures

• Other basic data structure (besides atomic propositions we have already seen): list
• List is a sequence of any number of elements
• Elements can be atoms, atomic propositions, or other terms (including other lists)

  [apple, prune, grape, kumquat]

[]   (empty list)

  [X | Y]   (head X and tail Y)

Deficiencies of Prolog

• Resolution order control
  • In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently

• The closed-world assumption
  • The only knowledge is what is in the database

• The negation problem
  • Anything not stated in the database is assumed to be false

• Intrinsic limitations
  • It is easy to state a sort process in logic, but difficult to actually do—it doesn’t know how to sort

Applications of Logic Programming

• Relational database management systems
• Expert systems
• Natural language processing

Functional Programming Language

January 6th, 2018

So, What is Functional Programming Language ?

functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

• The design of the imperative languages is based directly on the von Neumann architecture
• The design of the functional languages is based on mathematical functions

Mathematical Functions

• A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set
• A lambda expression specifies the parameter(s) and the mapping of a function in the following form

l(x) x * x * x

for the function  cube(x) = x * x * x

Lambda Expressions

• Lambda expressions describe nameless functions
• Lambda expressions are applied to parameter(s) by placing the parameter(s) after the expression

e.g.,   (l(x) x * x * x)(2)

which evaluates to 8

Functional Forms

• A higher-order function, or functional form, is one that either takes functions as parameters or yields a function as its result, or both

Function Composition

A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second

Form: h º f ° g

which means h (x) º f ( g ( x))

For f (x) º x + 2  and  g (x) º 3 * x,

h º f ° g yields (3 * x)+ 2

Apply-to-all

A functional form that takes a single function as a parameter and yields a list of values obtained by applying the given function to each element of a list of parameters

Form: a

For h(x) º x * x

a(h, (2, 3, 4))  yields  (4, 9, 16)

LISP Data Types and Structures

• Data object types: originally only atoms and lists
• List form: parenthesized collections of sublists and/or atoms

e.g., (A B (C D) E)

• Originally, LISP was a typeless language
• LISP lists are stored internally as single-linked lists

LISP Interpretation

• Lambda notation is used to specify functions and function definitions. Function applications and data have the same form.
• The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation

Primitive Functions & LAMBDA Expressions

• Primitive Arithmetic Functions: +, -, *, /, ABS, SQRT, REMAINDER, MIN, MAX

e.g., (+ 5 2) yields 7

• Lambda Expressions

–Form is based on l notation

e.g., (LAMBDA (x) (* x x)

x is called a bound variable

• Lambda expressions can be applied to parameters

e.g., ((LAMBDA (x) (* x x)) 7)

• LAMBDA expressions can have any number of parameters

(LAMBDA (a b x) (+ (* a x x) (* b x)))

Special form functinon : DEFINE

DEFINE – Two forms:

1.To bind a symbol to an expression

e.g., (DEFINE pi 3.141593)

Example use: (DEFINE two_pi (* 2 pi))

These symbols are not variables – they are like the names bound by Java’s final declarations

2.To bind names to lambda expressions (LAMBDA is implicit)

e.g., (DEFINE (square x) (* x x))

Example use: (square 5)

– The evaluation process for DEFINE is different! The first parameter is never evaluated. The second parameter is evaluated and bound to the first parameter.

Numeric Predicate Functions

• #T (or #t) is true and #F (or #f) is false (sometimes () is used for false)
• =, <>, >, <, >=, <=
• EVEN?, ODD?, ZERO?, NEGATIVE?
• The NOT function inverts the logic of a Boolean expression

Control Flow

• Selection- the special form, IF

  (IF predicate then_exp else_exp)

    (IF (<> count 0)

(/ sum count)

)

• Recall from Chapter 8 the COND function:

(DEFINE (leap? year)

(COND

((ZERO? (MODULO year 400)) #T)

((ZERO? (MODULO year 100)) #F)

(ELSE (ZERO? (MODULO year 4)))

))

List Functions

• QUOTE – takes one parameter; returns the parameter without evaluation

–QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function.  QUOTE is used to avoid parameter evaluation when it is not appropriate

–QUOTE can be abbreviated with the apostrophe prefix operator

‘(A B) is equivalent to (QUOTE (A B))

Predicate Function: EQ?

• EQ? takes two expressions as parameters (usually two atoms); it returns #T if both parameters have the same pointer value; otherwise #F

(EQ? ‘A ‘A) yields #T

(EQ? ‘A ‘B) yields #F

(EQ? ‘A ‘(A B)) yields #F

(EQ? ‘(A B) ‘(A B)) yields #T or #F

(EQ? 3.4 (+ 3 0.4))) yields #T or #F

Predicate Function: EQV?

• EQV? is like EQ?, except that it works for both symbolic and numeric atoms; it is a value comparison, not a pointer comparison

(EQV? 3 3) yields #T

(EQV? ‘A 3) yields #F

(EQV 3.4 (+ 3 0.4)) yields #T

(EQV? 3.0 3) yields #F  (floats and integers are different)

Predicate Functions: LIST? and NULL?

• LIST? takes one parameter; it returns #T if the parameter is a list; otherwise #F

(LIST? ‘()) yields #T

• NULL? takes one parameter; it returns #T if the parameter is the empty list; otherwise #F

(NULL? ‘(())) yields #F

Tail Recursion in Scheme

• Definition: A function is tail recursive if its recursive call is the last operation in the function
• A tail recursive function can be automatically converted by a compiler to use iteration, making it faster
• Scheme language definition requires that Scheme language systems convert all tail recursive functions to use iteration

Functions That Build Code

• It is possible in Scheme to define a function that builds Scheme code and requests its interpretation
• This is possible because the interpreter is a user-available function, EVAL

Comparing Functional and Imperative Languages

• Imperative Languages:

–Efficient execution

–Complex semantics

–Complex syntax

–Concurrency is programmer designed

• Functional Languages:

–Simple semantics

–Simple syntax

–Less efficient execution

–Programs can automatically be made concurrent

Concurrency

January 6th, 2018

In this session we will talk about concurrency, so what is concurrency in programming language concept ?

Concurrecy is refers to the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome.

Concurrency can occur at four levels:

–Machine instruction level

–High-level language statement level

–Unit level

–Program level

Introduction to Subprogram-Level Concurrency

A task or process or thread is a program unit that can be in concurrent execution with other program units

Tasks differ from ordinary subprograms in that:

–A task may be implicitly started

–When a program unit starts the execution of a task, it is not necessarily suspended

–When a task’s execution is completed, control may not return to the caller

Tasks usually work together

Two General Categories of Tasks

• Heavyweight tasks execute in their own address space
• Lightweight tasks all run in the same address space – more efficient
• A task is disjoint if it does not communicate with or affect the execution of any other task in the program in any way

Task Synchronization

A mechanism that controls the order in which tasks execute

Two kinds of synchronization

• Cooperation: Task A must wait for task B to complete some specific activity before task A can continue its execution, e.g., the producer-consumer problem
• Competition: Two or more tasks must use some resource that cannot be simultaneously used, e.g., a shared counter

–Competition is usually provided by mutually exclusive access  (approaches are discussed later)

Scheduler

• Providing synchronization requires a mechanism for delaying task execution
• Task execution control is maintained by a program called the scheduler, which maps task execution onto available processors

Task Execution States

• New – created but not yet started
• Ready – ready to run but not currently running (no available processor)
• Running
• Blocked – has been running, but cannot now continue (usually waiting for some event to occur)
• Dead – no longer active in any sense

Liveness and Deadlock

• Liveness is a characteristic that a program unit may or may not have
  – In sequential code, it means the unit will
  eventually complete its execution
• If all tasks in a concurrent environment lose their liveness, it is called deadlock

Design Issues for Concurrency

• Competition and cooperation synchronization*
• Controlling task scheduling
• How can an application influence task scheduling
• How and when tasks start and end execution
• How and when are tasks created

* The most important issue

Methods of Providing Synchronization

• Semaphores
  A semaphore is a data structure consisting of a counter and a queue for storing task descriptors
• Monitor
  A monitor is an abstract data type for shared data
• Message Passing
  Message passing is a general model for concurrency
  –It can model both semaphores and monitors–It is not just for competition synchronization

Multiple Entry Points

–The specification task has an entry clause for each

–The task body has an accept clause for each entry clause, placed in a select clause, which is in a loop

Exception Handling and Event Handling

December 16, 2017

I. Exception Handling

What is Exception Handling in programming language ?

Exception handling is the process of responding to the occurrence, during computation, of exceptions – anomalous or exceptional conditions requiring special processing – often changing the normal flow of program execution. (wikipedia)

• In a language without exception handling

–When an exception occurs, control goes to the operating system, where a message is displayed and the program is terminated

• In a language with exception handling

–Programs are allowed to trap some exceptions, thereby providing the possibility of fixing the problem and continuing

Basic Concepts

• Many languages allow programs to trap input/output errors (including EOF)
• An exception is any unusual event, either erroneous or not, detectable by either hardware or software, that may require special processing
• The special processing that may be required after detection of an exception is called exception handling
• The exception handling code unit is called an exception handler

Exception Handling Alternatives

• An exception is raised when its associated event occurs
• A language that does not have exception handling capabilities can still define, detect, raise, and handle exceptions (user defined, software detected)
• Alternatives:

–Send an auxiliary parameter or use the return value to indicate the return status of a subprogram

–Pass a label parameter to all subprograms (error return is to the passed label)

–Pass an exception handling subprogram to all subprograms

Advantages of Built-in Exception Handling

• Error detection code is tedious to write and it clutters the program
• Exception handling encourages programmers to consider many different possible errors
• Exception propagation allows a high level of reuse of exception handling code

Exception Handling Control Flow

C++ Exception Handlers

• Exception Handlers Form:

  try {

— code that is expected to raise an exception

}

catch (formal parameter) {

— handler code

}

…

catch (formal parameter) {

— handler code

}

The catch Function

• catch is the name of all handlers–it is an overloaded name, so the formal parameter of each must be unique
• The formal parameter need not have a variable

–It can be simply a type name to distinguish the handler it is in from others

• The formal parameter can be used to transfer information to the handler
• The formal parameter can be an ellipsis, in which case it handles all exceptions not yet handled

Throwing Exceptions

• Exceptions are all raised explicitly by the statement:

  throw [expression];

• The brackets are metasymbols
• A throw without an operand can only appear in a handler; when it appears, it simply re-raises the exception, which is then handled elsewhere
• The type of the expression disambiguates the intended handler

Unhandled Exceptions

• An unhandled exception is propagated to the caller of the function in which it is raised
• This propagation continues to the main function
• If no handler is found, the default handler is called

Continuation

• After a handler completes its execution, control flows to the first statement after the last handler in the sequence of handlers of which it is an element
• Other design choices

–All exceptions are user-defined

–Exceptions are neither specified nor declared

–The default handler, unexpected, simply terminates the program; unexpected can be redefined by the user

–Functions can list the exceptions they may raise

–Without a specification, a function can raise any exception (the throw clause)

II. Event Handling

• An event is a notification that something specific has occurred, such as a mouse click on a graphical button
• The event handler is a segment of code that is executed in response to an event

to understand more about event handling, we take an example from Java and C# Programming language.

Java Swing GUI Components

• Text box is an object of class JTextField
• Radio button is an object of class JRadioButton
• Applet’s display is a frame, a multilayered structure
• Content pane is one layer, where applets put output
• GUI components can be placed in a frame
• Layout manager objects are used to control the placement of components

The Java Event Model

• User interactions with GUI components create events that can be caught by event handlers, called event listeners
• An event generator tells a listener of an event by sending a message
• An interface is used to make event-handling methods conform to a standard protocol
• A class that implements a listener must implement an interface for the listener
• One class of events is ItemEvent, which is associated with the event of clicking a checkbox, a radio button, or a list item
• The ItemListener interface prescribes a method, itemStateChanged, which is a handler for ItemEvent events
• The listener is created with addItemListener

Event Handling in C#

• Event handling in C# (and the other .NET languages) is similar to that in Java
• .NET has two approaches, Windows Forms and Windows Presentation Foundation—we cover only the former (which is the original approach)
• An application subclasses the Form predefined class (defined in System.Windows.Forms)
• There is no need to create a frame or panel in which to place the GUI components
• Label objects are used to place text in the window
• Radio buttons are objects of the RadioButton class

• Components are positioned by assigning a new Point object to the Location property of the component

private RadioButton plain = new RadioButton();

plain.Location = new Point(100, 300);

plain.Text = ″Plain″;

controls.Add(plain);

• All C# event handlers have the same protocol, the return type is void and the two parameters are of types object and EventArgs

• An event handler can have any name
• A radio button is tested with the Boolean Checked property of the button

private void rb_CheckedChanged (object o,

EventArgs e) {

if (plain.Checked) …

…

}

• To register an event, a new EventHandler object must be created and added to the predefined delegate for the event

• When a radio button changes from unchecked to checked, the CheckedChanged event is raised
• The associated delegate is referenced by the name of the event
• If the handler was named rb_CheckedChanged, we could register it on the radio button named plain with:

plain.CheckedChanged +=

new EventHandler (rb_CheckedChanged);

Object-Oriented Programming

December 2, 2017

There are many object-oriented programming (OOP) languages

–Some support procedural and data-oriented programming (e.g., Ada 95+ and C++)

–Some support functional program (e.g., CLOS)

–Newer languages do not support other paradigms but use their imperative structures (e.g., Java and C#)

–Some are pure OOP language (e.g., Smalltalk & Ruby)

–Some functional languages support OOP, but they are not discussed in this chapter

Three major language features:

–Abstract data types (Session GSLC 02)

–Inheritance

• Inheritance is the central theme in OOP and languages that support it

–Polymorphism

I.  Inheritance

• Productivity increases can come from reuse

–ADTs are difficult to reuse—always need changes

–All ADTs are independent and at the same level

• Inheritance allows new classes defined in terms of existing ones, i.e., by allowing them to inherit common parts
• Inheritance addresses both of the above concerns–reuse ADTs after minor changes and define classes in a hierarchy

Object-Oriented Concepts

• ADTs are usually called classes
• Class instances are called objects
• A class that inherits is a derived class or a subclass
• The class from which another class inherits is a parent class or superclass
• Subprograms that define operations on objects are called methods
• Calls to methods are called messages
• The entire collection of methods of an object is called its message protocol or message interface
• Messages have two parts–a method name and the destination object
• In the simplest case, a class inherits all of the entities of its parent
• Inheritance can be complicated by access controls to encapsulated entities–A class can hide entities from its subclasses–A class can hide entities from its clients

  –A class can also hide entities for its clients while allowing its subclasses to see them

• Besides inheriting methods as is, a class can modify an inherited method 

  –The new one overrides the inherited one

  –The method in the parent is overriden

• Three ways a class can differ from its parent:
  1. The parent class can define some of its variables or methods to have private access, which means they will not be visible in the subclass
  2. The subclass can add variables and/or methods to those inherited from the parent
  3. The subclass can modify the behavior of one or more of its inherited methods.

• There are two kinds of variables in a class:

–Class variables – one/class

–Instance variables – one/object

• There are two kinds of methods in a class:

–Class methods – accept messages to the class

–Instance methods – accept messages to objects

• Single vs. Multiple Inheritance
• One disadvantage of inheritance for reuse:

–Creates interdependencies among classes that complicate maintenance

Dynamic Binding

• A polymorphic variable can be defined in a class that is able to reference (or point to) objects of the class and objects of any of its descendants
• When a class hierarchy includes classes that override methods and such methods are called through a polymorphic variable, the binding to the correct method will be dynamic
• Allows software systems to be more easily extended during both development and maintenance

Dynamic Binding Concepts

• An abstract method is one that does not include a definition (it only defines a protocol)
• An abstract class is one that includes at least one virtual method
• An abstract class cannot be instantiated

The Exclusivity of Objects

• Everything is an object

–Advantage – elegance and purity

–Disadvantage – slow operations on simple objects

• Add objects to a complete typing system

–Advantage – fast operations on simple objects

–Disadvantage – results in a confusing type system (two kinds of entities)

• Include an imperative-style typing system for primitives but make everything else objects

–Advantage – fast operations on simple objects and a relatively small typing system

–Disadvantage – still some confusion because of the two type systems

Single and Multiple Inheritance

• Multiple inheritance allows a new class to inherit from two or more classes
• Disadvantages of multiple inheritance:

–Language and implementation complexity (in part due to name collisions)

–Potential inefficiency – dynamic binding costs more with multiple inheritance (but not much)

• Advantage:

–Sometimes it is quite convenient and valuable

Allocation and DeAllocation of Objects

• From where are objects allocated?

–If they behave line the ADTs, they can be allocated from anywhere

• Allocated from the run-time stack
• Explicitly create on the heap (via new)

–If they are all heap-dynamic, references can be uniform thru a pointer or reference variable

• Simplifies assignment – dereferencing can be implicit

–If objects are stack dynamic, there is a problem with regard to subtypes – object slicing

• Is deallocation explicit or implicit?

Nested Classes

• If a new class is needed by only one class, there is no reason to define so it can be seen by other classes

–Can the new class be nested inside the class that uses it?

–In some cases, the new class is nested inside  a subprogram rather than directly in another class

• Other issues:

–Which facilities of the nesting class should be visible to the nested class and vice versa

Inheritance Example in C++

class base_class {

private:

int a;

float x;

protected:

int b;

float y;

public:

int c;

float z;

};

class subclass_1 : public base_class { … };

//     In this one, b and y are protected and

//     c and z are public

class subclass_2 : private base_class { … };

//    In this one, b, y, c, and z are private,

//    and no derived class has access to any

//    member of base_class

Implementing OO Constructs

• Two interesting and challenging parts

–Storage structures for instance variables

–Dynamic binding of messages to methods

Dynamic Binding of Methods Calls

• Methods in a class that are statically bound need not be involved in the CIR; methods that will be dynamically bound must have entries in the CIR

–Calls to dynamically bound methods can be connected to the corresponding code thru a pointer in the CIR

–The storage structure is sometimes called virtual method tables  (vtable)

–Method calls can be represented as offsets from the beginning of the vtable

Subprograms

October 27, 2017

Two fundamental abstraction facilities

–Process abstraction

• Emphasized from early days
• Discussed in this chapter

–Data abstraction

• Emphasized in the1980s
• Discussed at length in Chapter 11

Fundamentals of Subprograms

• Each subprogram has a single entry point
• The calling program is suspended during execution of the called subprogram
• Control always returns to the caller when the called subprogram’s execution terminates

Local Referencing Environments

• Local variables can be stack-dynamic

–Advantages

• Support for recursion
• Storage for locals is shared among some subprograms

–Disadvantages

• Allocation/de-allocation, initialization time
• Indirect addressing
• Subprograms cannot be history sensitive
• Local variables can be static

–Advantages and disadvantages are the opposite of those for stack-dynamic local variables

Semantic Models of Parameter Passing

• In mode
• Out mode
• Inout mode

Models of Parameter Passing

Models of Parameter Passing

Pass-by-Value (In Mode)

• The value of the actual parameter is used to initialize the corresponding formal parameter

–Normally implemented by copying

–Can be implemented by transmitting an access path but not recommended (enforcing write protection is not easy)

–Disadvantages (if by physical move): additional storage is required (stored twice) and the actual move can be costly (for large parameters)

–Disadvantages (if by access path method): must write-protect in the called subprogram and accesses cost more (indirect addressing)

Pass-by-Result (Out Mode)

• When a parameter is passed by result, no value is transmitted to the subprogram; the corresponding formal parameter acts as a local variable; its value is transmitted to caller’s actual parameter when control is returned to the caller, by physical move

–Require extra storage location and copy operation

• Potential problems:

– sub(p1, p1); whichever formal parameter is copied back will represent the current value of p1

–sub(list[sub], sub); Compute address of list[sub] at the beginning of the subprogram or end?

Pass-by-Value-Result (inout Mode)

• A combination of pass-by-value and pass-by-result
• Sometimes called pass-by-copy
• Formal parameters have local storage
• Disadvantages:

–Those of pass-by-result

–Those of pass-by-value

Pass-by-Reference (Inout Mode)

• Pass an access path
• Also called pass-by-sharing
• Advantage: Passing process is efficient (no copying and no duplicated storage)
• Disadvantages

–Slower accesses (compared to pass-by-value) to formal parameters

–Potentials for unwanted side effects (collisions)

–Unwanted aliases (access broadened)

fun(total, total);  fun(list[i], list[j];  fun(list[i], i);

Pass-by-Name (Inout Mode)

• By textual substitution
• Formals are bound to an access method at the time of the call, but actual binding to a value or address takes place at the time of a reference or assignment
• Allows flexibility in late binding
• Implementation requires that the referencing environment of the caller is passed with the parameter, so the actual parameter address can be calculated

Implementing Parameter-Passing Methods

Function header:  void sub(int a, int b, int c, int d)

Function call in main: sub(w, x, y, z)

(pass w by value, x by result, y by value-result, z by reference)

Design Considerations for Parameter Passing

• Two important considerations

–Efficiency

–One-way or two-way data transfer

• But the above considerations are in conflict

–Good programming suggest limited access to variables, which means one-way whenever possible

–But pass-by-reference is more efficient to pass structures of significant size

Calling Subprograms Indirectly

• Usually when there are several possible subprograms to be called and the correct one on a particular run of the program is not know until execution (e.g., event handling and GUIs)
• In C and C++, such calls are made through function pointers

Overloaded Subprograms

• An overloaded subprogram is one that has the same name as another subprogram in the same referencing environment

–Every version of an overloaded subprogram has a unique protocol

• C++, Java, C#, and Ada include predefined overloaded subprograms
• In Ada, the return type of an overloaded function can be used to disambiguate calls (thus two overloaded functions can have the same parameters)
• Ada, Java, C++, and C# allow users to write multiple versions of subprograms with the same name

Generic Subprograms

• A generic or polymorphic subprogram takes parameters of different types on different activations
• Overloaded subprograms provide ad hoc polymorphism
• Subtype polymorphism means that a variable of type T can access any object of type T or any type derived from T (OOP languages)
• A subprogram that takes a generic parameter that is used in a type expression that describes the type of the parameters of the subprogram provides parametric polymorphism
  – A cheap compile-time substitute for dynamic binding

User-Defined Overloaded Operators

• Operators can be overloaded in Ada, C++, Python, and Ruby
• A Python example

def __add__ (self, second) :

  return Complex(self.real + second.real,

self.imag + second.imag)

Use: To compute x + y, x.__add__(y)

Closures

• A closure is a subprogram and the referencing environment where it was defined

–The referencing environment is needed if the subprogram can be called from any arbitrary place in the program

–A static-scoped language that does not permit nested subprograms doesn’t need closures

–Closures are only needed if a subprogram can access variables in nesting scopes and it can be called from anywhere

–To support closures, an implementation may need to provide unlimited extent to some variables (because a subprogram may access a nonlocal variable that is normally no longer alive)

Coroutines

• A coroutine is a subprogram that has multiple entries and controls them itself – supported directly in Lua
• Also called symmetric control: caller and called coroutines are on a more equal basis
• A coroutine call is named a resume
• The first resume of a coroutine is to its beginning, but subsequent calls enter at the point just after the last executed statement in the coroutine
• Coroutines repeatedly resume each other, possibly forever
• Coroutines provide quasi-concurrent execution of program units (the coroutines); their execution is interleaved, but not overlapped

Control Structure Statements

October 28, 2017

in this session we going to learn about control structures. so what is control structures ?
A control structure is a control statement and the statements whose execution it control.

control structure consist of 2 statements :

I. Selection Statements
A selection statement provides the means of choosing between two or more paths of execution
Two general categories:

–Two-way selectors

–Multiple-way selectors

1. Two-Way Selection Statements

• General form:

if control_expression

then clause

else clause

• Design Issues:

–What is the form and type of the control expression?

–How are the then and else clauses specified?

–How should the meaning of nested selectors be specified?

The Control Expression

• If the then reserved word or some other syntactic marker is not used to introduce the then clause, the control expression is placed in parentheses
• In C89, C99, Python, and C++, the control expression can be arithmetic
• In most other languages, the control expression must be Boolean

Clause Form

• In many contemporary languages, the then and else clauses can be single statements or compound statements
• In Perl, all clauses must be delimited by braces (they must be compound)
• In Fortran 95, Ada, Python, and Ruby, clauses are statement sequences
• Python uses indentation to define clauses

if x > y :

x = y

print ” x was greater than y”

Nesting Selectors

• Java example

if (sum == 0)

if (count == 0)

result = 0;

else result = 1;

• Which if gets the else?
• Java’s static semantics rule: else matches with the nearest previous if

• To force an alternative semantics, compound statements may be used:

if (sum == 0) {

if (count == 0)

result = 0;

}

else result = 1;

• The above solution is used in C, C++, and C#

2. Multiple-Way Selection Statements

• Allow the selection of one of any number of statements or statement groups
• Design Issues:

What is the form and type of the control expression?

How are the selectable segments specified?

Is execution flow through the structure restricted to include just a single selectable segment?

How are case values specified?

What is done about unrepresented expression values?

• C, C++, Java, and JavaScript

  switch (expression) {

case const_expr1: stmt1;

…

case const_exprn: stmtn;

[default: stmtn+1]

}

• Multiple Selectors can appear as direct extensions to two-way selectors, using else-if clauses, for example in Python:

if count < 10 :

bag1 = True

elif count < 100 :

bag2 = True

elif count < 1000 :

bag3 = True

II. Iterative Statements

• The repeated execution of a statement or compound statement is accomplished either by iteration or recursion
• General design issues for iteration control statements:

1. How is iteration controlled?
2. Where is the control mechanism in the loop?

Counter-Controlled Loops

• A counting iterative statement has a loop variable, and a means of specifying the initial and terminal, and stepsize valuesExample :

1.Ada

  for var in [reverse] discrete_range loop               …

end loop

• Design choices:
• Type of the loop variable is that of the discrete range (A discrete range is a sub-range of an integer or enumeration type).
• Loop variable does not exist outside the loop
• The loop variable cannot be changed in the loop, but the discrete range can; it does not affect loop control
• The discrete range is evaluated just once
• Cannot branch into the loop body

2. C-based languages

for ([expr_1] ; [expr_2] ; [expr_3]) statement

– The expressions can be whole statements, or even statement sequences, with the statements separated by commas

–The value of a multiple-statement expression is the value of the last statement in the expression

–If the second expression is absent, it is an infinite loop

• Design choices:

-There is no explicit loop variable

-Everything can be changed in the loop

-The first expression is evaluated once, but the other two

are evaluated with each iteration

– It is legal to branch into the body of a for loop in C

Logically-Controlled Loops

• Repetition control is based on a Boolean expression
• Design issues:

–Pretest or posttest?

–Should the logically controlled loop be a special case of the counting loop statement  or a separate statement?

Example :

• C and C++ have both pretest and posttest forms, in which the control expression can be arithmetic:

while (control_expr)  do

loop body    loop body

while (control_expr)

– In both C and C++ it is legal to branch into the body

of a logically-controlled loop

• Java is like C and C++, except the control expression must be Boolean (and the body can only be entered at the beginning — Java has no goto

User-Located Loop Control Mechanisms

• Sometimes it is convenient for the programmers to decide a location for loop control (other than top or bottom of the loop)
• Simple design for single loops (e.g., break)
• Design issues for nested loops

Iteration Based on Data Structures

• The number of elements in a data structure controls loop iteration
• Control mechanism is a call to an iterator function that returns the next element in some chosen order, if there is one; else loop is terminate
• C’s for can be used to build a user-defined iterator:

  for (p=root; p==NULL; traverse(p)){

…

}

Expression and Assignment Statements

October 21st, 2017

on session 4, we talk more about Expression and Assignment statement, what is Expression ? and what is Assignment statement in computing ?

Expressions are the fundamental means of specifying computations in a programming language.To understand expression evaluation, need to be familiar with the orders of operator and operand evaluation.Essence of imperative languages is dominant role of assignment statements.

here are types of expression in computing :

I. Arithmetic Expressions
Arithmetic evaluation was one of the motivations for the development of the first programming languages
Arithmetic expressions consist of operators, operands, parentheses, and function calls

• A unary operator has one operand
• A binary operator has two operands
• A ternary operator has three operandsOperator Precedence Rules
  • Typical precedence levels

  – parentheses

  – unary operators

  – ** (if the language supports it)

  – *, /

  – +, –

  Operator Associativity Rule

  • The operator associativity rules for expression evaluation define the order in which adjacent operators with the same precedence level are evaluated
  • Typical associativity rules

  –Left to right, except **, which is right to left

  –Sometimes unary operators associate right to left (e.g., in FORTRAN)

  • APL is different; all operators have equal precedence and all operators associate right to left
  • Precedence and associativity rules can be overriden with parentheses

  
  Operand evaluation order1.Variables: fetch the value from memory

  2.Constants: sometimes a fetch from memory; sometimes the constant is in the machine language instruction

  3.Parenthesized expressions: evaluate all operands and operators first

  4.The most interesting case is when an operand is a function call

   

   

II. Functional Side Effects

Two possible solutions to the problem

1.Write the language definition to disallow functional side effects

• No two-way parameters in functions
• No non-local references in functions
• Advantage: it works!
• Disadvantage: inflexibility of one-way parameters and lack of non-local references

2.Write the language definition to demand that operand evaluation order be fixed

• Disadvantage: limits some compiler optimizations
• Java requires that operands appear to be evaluated in left-to-right order

Overloaded Operators

• Use of an operator for more than one purpose is called operator overloading
• Some are common (e.g., + for int and float)
• Some are potential trouble (e.g., * in C and C++)

–Loss of compiler error detection (omission of an operand should be a detectable error)

–Some loss of readability

• C++, C#, and F# allow user-defined overloaded operators

–When sensibly used, such operators can be an aid to readability (avoid method calls, expressions appear natural)

–Potential problems:

• Users can define nonsense operations
• Readability may suffer, even when the operators make sense

III. Type Conversion

• A narrowing conversion is one that converts an object to a type that cannot include all of the values of the original type e.g., float to int
• A widening conversion is one in which an object is converted to a type that can include at least approximations to all of the values of the original type e.g., int to float

IV. Errors in Expressions

• Causes

–Inherent limitations of arithmetic                         e.g., division by zero

–Limitations of computer arithmetic                     e.g. overflow

• Often ignored by the run-time system

V. Relational and Boolean Expressions

• Relational Expressions

–Use relational operators and operands of various types

–Evaluate to some Boolean representation

–Operator symbols used vary somewhat among languages (!=, /=, ~=, .NE., <>, #)

• Boolean Expressions

–Operands are Boolean and the result is Boolean

–Example operators

Sources: https://binusmaya.binus.ac.id/newStudent/#/class/resources.COMP6060/007420/1710/LEC/15077