-
what is an abstraction?
a view of an entity (either a process or data entity) that includes only the most significant attributes.
-
process abstraction
subprograms used from the early days of programming. called "functions" in C or C++.
-
data abstraction
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.
-
two primary features of an abstract data type
packaging of data with their associated operations, and information hiding.
-
the purpose of a parameterized abstract data type
allow an abstract data type that can store elements of any data-type.
-
what is encapsulation?
organizing programs into collections of logically related code and data, each of which can be compiled without recompilation of the rest of the program.
-
why do we need encapsulations?
large programs need a means to organize groups of subprograms, and to provide partial compilation.
-
what is a naming encapsulation?
dividing global names into groupings to avoid name collisions.
-
three major language features needed by OOP
abstract data types, inheritance, and dynamic binding of method calls.
-
CLASS
an abstract data type
-
OBJECT
an instance of a class (a particular variable)
-
DERIVED CLASS
a class that inherits from another class. a.k.a. SUB-CLASS
-
SUPERCLASS
the class from which the derived class inherits
-
METHOD
a subprogram that defines an operation on objects
-
MESSAGE
a call to a method
-
MESSAGE PROTOCOL
the entire collection of methods of an object
-
CLASS VARIABLES
one variable per class (in C++ declared static)
-
INSTANCE VARIABLES
one variable per object (in C++ not static)
-
CLASS METHODS
accept messages to the class (in C++ called with no instance)
-
INSTANCE METHODS
accept messages to an object
-
MULTIPLE INHERITANCE
class inherits from more than 1 parent
-
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
-
ABSTRACT METHOD
a method that does not include a definition (it only defines a protocol)
-
what is the "SHARED inheritance" problem with multiple inheritance?
if two parents both define a method C, how does it reference one or the other version? also called "DIAMOND inheritance"
-
What is OBJECT SLICING and when can it occur?
if objects are stack dynamic, there is a problem with assigning subtypes to each other
-
static binding of method calls
static binding is faster
-
dynamic binding of method calls
if none are dynamic, you lose the advantages of dynamic binding
-
Smalltalk
- the first OOP language
- everything was an object
-
C++'s three access controls
- 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
-
C++ method statically vs dynamically bound
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.
-
Java methods statically vs dynamically 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.
-
what is a Java INTERFACE?
- 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.
-
what is a Class Instance Record (CIR)?
- 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.
-
what is the "vtable" is for?
- 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
-
physical concurrency
multiple independent processors.
-
logical concurrency
the appearance of physical concurrency by time-sharing one processor.
-
thread of control
the sequence of program points reached as the program executes.
-
task (a.k.a. process or thread)
a program unit that that can be in concurrent execution with other program units.
-
race condition
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).
-
liveness
a characteristic of a task that it will eventually complete its execution.
-
deadlock
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.
-
heavyweight task
each executes in it's own address space, for protection against other tasks.
-
lightweight task
all execute in the same address space for efficiency.
-
cooperation synchronization
one task must wait for another task to complete some activity before it can proceed. called producer-consumer problem.
-
competition synchronization
two or more tasks must use some resource that cannot be simultaneously used.
-
semaphore
- 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.
-
monitor
- 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.
-
message-passing
- 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.
-
ATOMIC operation
- 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.
-
what is one problem with using semaphores for task synchronization?
no way to check statically for the correctness of their use.
-
what's one advantage of monitor over semaphore?
- 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.
-
how do the methods in a Java Thread work?
- 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).
-
exception
any unusual event, either erroneous or not.
-
exception handler
the code unit that processes an exception.
-
finalization
- 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.
-
continuation
- 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.
-
exception propagation
allows a high level of reuse of exception handling code.
-
why do we have exceptions in programming languages?
- 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.
-
what's the difference between an event and an exception?
event isn't necessarily unexpected.
-
what's an EVENT DRIVEN program?
- 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.
-
what is a logic programming language?
specifies the characteristics of results, not a procedure for producing results.
-
PROLOG FACT Statements
- female(shelley)
- male(bill)
- father(bill,jake)
-
PROLOG RULE Statements
- consequence :- antecedent
- parent(X,Y) :- mother(X,Y)
- parent(X,Y) :- father(X,Y)
- grandparent(X,Z) :- father(X,Y), parent(Y,Z)
-
-
what are some deficiencies of prolog?
- 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
|
|