what is an abstraction?
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.
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.
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)
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
- 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
multiple independent processors.
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.
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.
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).
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.
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
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