Final Test

a view of an entity (either a process or data entity) that includes only the most significant attributes.

subprograms used from the early days of programming. called "functions" in C or C++.

Any representation of data in which the implementation details are hidden (abstracted). Abstract data types and objects are the two primary forms of data abstraction.

packaging of data with their associated operations, and information hiding.

allow an abstract data type that can store elements of any data-type.

organizing programs into collections of logically related code and data, each of which can be compiled without recompilation of the rest of the program.

large programs need a means to organize groups of subprograms, and to provide partial compilation.

dividing global names into groupings to avoid name collisions.

abstract data types, inheritance, and dynamic binding of method calls.

an abstract data type

an instance of a class (a particular variable)

a class that inherits from another class. a.k.a. SUB-CLASS

the class from which the derived class inherits

a subprogram that defines an operation on objects

a call to a method

the entire collection of methods of an object

one variable per class (in C++ declared static)

one variable per object (in C++ not static)

accept messages to the class (in C++ called with no instance)

accept messages to an object

class inherits from more than 1 parent

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

a method that does not include a definition (it only defines a protocol)

if two parents both define a method C, how does it reference one or the other version? also called "DIAMOND inheritance"

if objects are stack dynamic, there is a problem with assigning subtypes to each other

static binding is faster

if none are dynamic, you lose the advantages of dynamic binding

• the first OOP language
• everything was an object

• private -- visible only in the class and friends. Disallows subclasses from being subtypes
• public -- visible in subclasses and clients (users)
• protected --- visible in the class and in subclasses, but not clients

a method can be defined to be virtual, which means that it can be called through polymorphic variables (pointers) and dynamically bound to messages. otherwise it is statically bound.

• all messages are dynamically bound to methods, unless the method is final (i.e., it cannot be overriden, therefore dynamic binding serves no purpose).
• static binding is also used if the method is static or private, both of which disallow overriding.

• includes only method declarations and named constants.
• a class that implements a particular interface must supply the method(s) specified in the interface.
• a class implementing an interface can then call certain method(s) that require the interface.
• provides some of the things multple inheritance is used for.

• stores the state of an object
• content is static (known at compile time)
• allocated memory at run-time when objects (instances of a class) come into existence
• if a class has a parent, the subclass instance variables are added to the parent CIR
• access to all instance variables is done as it is in records
• efficient at run-time.

• Calls to dynamically bound methods are connected to the corresponding code through a vtable
• all instances of a given class are bound to the same methods, so we need only one vtable per class at run-time
• we store a pointer to the correct vtable in each object's CIR when the object is created at run-time
• method calls can be represented as offsets from the beginning of the vtable

multiple independent processors.

the appearance of physical concurrency by time-sharing one processor.

the sequence of program points reached as the program executes.

a program unit that that can be in concurrent execution with other program units.

when two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race).

a characteristic of a task that it will eventually complete its execution.

occurs when all tasks in a concurrent environment lose their liveness. can occur when each task "owns" a recource and each task is waiting on the other task's resource in order to continue.

each executes in it's own address space, for protection against other tasks.

all execute in the same address space for efficiency.

one task must wait for another task to complete some activity before it can proceed. called producer-consumer problem.

two or more tasks must use some resource that cannot be simultaneously used.

• a task synchronization data structure consisting of a counter and a queue for storing task descriptors.
• simplest, but have a disadvantage.
• semaphores can be used to implement guards on the code that accesses shared data structures.
• has a counter and queue of tasks.
• WAIT method suspends task until a resource unit is available.
• RELEASE makes another unit of a resource available (gives back a resource).
• semaphores can be used to implement monitors.
• monitors can be used to implement semaphores.
• disadvantage is there is no way to check statically (i.e. in the compiler) for the correctness of their use.

• an abstract data type for shared data.
• put the shared data and its operations in the monitor rather than in the client tasks.
• the monitor implementation guarantees synchronized access by allowing only one access to the shared data at a time (mutually exclusive access).
• calls to monitor procedures are implicitly queued if the monitor is busy at the time of the call.
• a better way to provide competition synchronization than semaphores, because monitor can guarantee synchronized access to the shared data no matter how it is used.
• semaphores can be used to implement monitors.
• monitors can be used to implement semaphores.
• support for cooperation synchronization is very similar as with semaphores, so it has the same problems.

• a general model for concurrency.
• messages can model both semaphores and monitors.
• messages are not just for competition synchronization.
• think of seeing a doctor. most of the time she waits for you or you wait for her, but when you are both ready, you get together, or rendezvous.
• to support concurrent tasks with message passing, a language needs:
• a mechanism to allow a task to indicate when it is willing to accept messages.
• a way to remember who is waiting to have its message accepted and some "fair" way of choosing the next message (a message queue).
• when a sender task's message is accepted by a receiver task, the actual message transmission is called a RENDEZVOUS.

• an uninterruptable operation.
• the wait and release semaphore operations must be un-interruptable.
• once "wait" or "release" starts, the task running it cannot be suspended.

no way to check statically for the correctness of their use.

• when used to implement competition synchronization the monitor can guarantee synchronized access to the shared data no matter how the client tasks used the monitor.
• monitors don't help cooperation synchronization more than semaphores.

• RUN method -- the thread method that executes when the START method is called to start a thread running.
• JOIN method -- allows task synchronization. Forces a task to delay until the run method of another task has completed (or until it times out).

any unusual event, either erroneous or not.

the code unit that processes an exception.

• sometimes a subprogram needs to complete some computation regardless of how the subprogram terminates (due to an exception or not).
• finalization is the ability for the programm to specify such a computation.

• where does execution continue, if at all, after an exception handler completes its execution?
• two alternatives:
• termination -- terminate the program.
• resumption -- resume the program somewhere.

allows a high level of reuse of exception handling code.

• writing code to check for error returns from subprograms is tedious and clutters the program.
• encourages programmers to consider many different errors.
• exception propagation allows a high level of reuse of exception handling code.

event isn't necessarily unexpected.

• one in which various parts of the program are executed at unpredictable times, triggered by user interactions (events).
• litttle or no code executed in an order determined by the program itself.

specifies the characteristics of results, not a procedure for producing results.

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

• consequence :- antecedent
• parent(X,Y) :- mother(X,Y)
• parent(X,Y) :- father(X,Y)
• grandparent(X,Z) :- father(X,Y), parent(Y,Z) 

• man(fred)
• father(X,mike)

• the order of attempted matches is nondeterministic and all matches should be attempted concurrently (but aren't).
• CLOSED-WORLD assumption: the only knowledge is what is in the database.
• NEGATION problem: anything not stated in the database is assumed to be false