Introduction

• Programs in logic languages are expressed in a form of symbolic logic
• Use a logical inferencing process to produce results
• Declarative rather that procedural:

–Only specification of results are stated (not detailed procedures for producing them)

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

• 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)

Logical Operators

Name	Symbol	Example	Meaning
negation	Ø	Ø a	not a
conjunction	Ç	a Ç b	a and b
disjunction	È	a È b	a or b
equivalence	º	a º b	a is equivalent to b
implication	É Ì	a É b a Ì b	a implies b b implies a

Quantifiers

Name	Example	Meaning
universal	“X.P	For all X, P is true
existential	$X.P	There exists a value of X such that P is true

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:

–a string of letters, digits, and underscores beginning with a lowercase letter

–a string of printable ASCII characters delimited by apostrophes

• Variable: any string of letters, digits, and underscores beginning with an uppercase letter
• Instantiation: binding of a variable to a value

–Lasts only as long as it takes to satisfy one complete goal

• Structure: represents atomic proposition

functor(parameter list)

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

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)

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

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

Introduction

• 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 Expression

• 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

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

 

LISP Data Type 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.

e.g., If the list (A B C) is interpreted as data it is

a simple list of three atoms, A, B, and C

If it is interpreted as a function application,

it means that the function named A is

applied to the two parameters, B and C

• The first LISP interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation

Special Form Function: 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.

Output Function

• Usually not needed, because the interpreter always displays the result of a function evaluated at the top level (not nested)
• Scheme has PRINTF, which is similar to the printf function of C
• Note: explicit input and output are not part of the pure functional programming model, because input operations change the state of the program and output operations are side effects

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))

• LIST is a function for building a list from any number of parameters

(LIST ′apple ′orange ′grape) returns

(apple orange grape)

Predicate Functions

• 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

• 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)

• 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

Functional Form

• Composition

–If h is the composition of f and g, h(x) = f(g(x))

(DEFINE (g x) (* 3 x))

(DEFINE (f x) (+ 2 x))

(DEFINE h x) (+ 2 (* 3 x)))  (The composition)

–In Scheme, the functional composition function compose can be written:

(DEFINE (compose f g) (LAMBDA (x) (f (g x))))

((compose CAR CDR) ‘((a b) c d)) yields c

(DEFINE (third a_list)

((compose CAR (compose CDR CDR)) a_list))

is equivalent to CADDR

Comparing Functional and Imperative Language

• 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

Introduction

Exception Handling

• 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

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

Comparison of Exception Handling in C++ and Java

Both languages use try, catch and throw keywords for exception handling, and meaning of try, catch and free blocks is also same in both languages. Following are the differences between Java and C++ exception handling.

1) In C++, all types (including primitive and pointer) can be thrown as exception. But in Java only throwable objects (Throwable objects are instances of any subclass of the Throwable class) can be thrown as exception. For example, following type of code works in C++, but similar code doesn’t work in Java.

Output:
Exception occurred: thrown value is -1

2) In C++, there is a special catch called “catch all” that can catch all kind of exceptions.

Output:
Exception occurred: exiting

In Java, for all practical purposes, we can catch Exception object to catch all kind of exceptions. Because, normally we do not catch Throwable(s) other than Exception(s) (which are Errors)

Output:
Got the error
Inside finally block

4) In C++, all exceptions are unchecked. In Java, there are two types of exceptions – checked and unchecked. See this for more details on checked vs Unchecked exceptions.

5) In Java, a new keyword throws is used to list exceptions that can be thrown by a function. In C++, there is no throws keyword, the same keyword throw is used for this purpose also.

Event Handling

Java:

• 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

C#:

• An application subclasses the Form predefined class (defined in System.Windows.Forms)
• Label objects are used to place text in the window
• Radio buttons are objects of the RadioButton class
• 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);

• Machine instruction level
• High-level language statement level
• Unit level
• Program level

• Heavyweight tasks execute in their own address space
• Lightweight tasks all run in the same address space – more efficient

• 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

• 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

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

• Semaphores
• Monitors
• Message Passing

• A third semaphore, named access, is used to control access (competition synchronization)

• Note that wait and release must be atomic!

• Shared data is resident in the monitor (rather than in the client units)
• All access resident in the monitor

Introduction

• 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 (Chapter VIII)

–Inheritance

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

–Polymorphism

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
• 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

  –The new one overrides the inherited one

  –The method in the parent is overriden

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

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

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 Concept

• 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

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

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

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.

Concept of Abstraction

• An abstraction is a view or representation of an entity that includes only the most significant attributes
• The concept of abstraction is fundamental in programming (and computer science)
• Nearly all programming languages support process abstraction with subprograms
• Nearly all programming languages designed since 1980 support data abstraction

Encapsulation Construct

• Large programs have two special needs:

–Some means of organization, other than simply division into subprograms

–Some means of partial compilation (compilation units that are smaller than the whole program)

• Obvious solution: a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units)
• Such collections are called encapsulation

Nested Subprograms

• Organizing programs by nesting subprogram definitions inside the logically larger subprograms that use them
• Nested subprograms are supported in Ada, Fortran 95+, Python, JavaScript, and Ruby

Encapsulation in C

• Files containing one or more subprograms can be independently compiled
• The interface is placed in a header file
• Problem: the linker does not check types between a header and associated implementation
• #include preprocessor specification – used to include header files in applications

Encapsulation in C++

• Can define header and code files, similar to those of C
• Or, classes can be used for encapsulation

–The class is used as the interface (prototypes)

–The member definitions are defined in a separate file

• Friends provide a way to grant access to private members of a class

The danger of C’s approach to encapsulation:
There are two problems with this approach. First, the documentation of the dependence of the client program on the library (and its header file) is lost. Second, the author of the library could change the header file and the implementation file, but the client could attempt to use the new implementation file (not realizing it had changed) but with the old header file, which the user had copied into his or her client program.

Naming Encapsulation

• Large programs define many global names; need a way to divide into logical groupings
• A naming encapsulation is used to create a new scope for names
• C++ Namespaces

–Can place each library in its own namespace and qualify names used outside with the namespace

–C# also includes namespaces

• Java Packages

–Packages can contain more than one class definition; classes in a package are partial friends

–Clients of a package can use fully qualified name or use the import declaration

Similarities between Java Packages dan C++ Namespace:

1) Java Packages are namespaces system while C++ also has namespace
2) Both are abstract containers for classes
3) Java Packages and namespaces provide breakup for class names
4) both make the code cleaner and less redundant, by enabling some
parts of the code.
Difference between Java Packages and C++ Namespace:
1) Java packages are about modules meanwhile, in C++ namespaces are just about partitioning the available names.
2) In Java language, namespaces are intended to avoid conflicts between names in different parts of class libraries.
3) C++ namespaces have an extra way to encapsulate stuff within an already existing system.

• Ruby classes are name encapsulations, but Ruby also has modules
• Typically encapsulate collections of constants and methods
• Modules cannot be instantiated or subclassed, and they cannot define variables
• Methods defined in a module must include the module’s name

Access to the contents of a module is requested with the require method.