IDS 401Algorithm: A logical sequence of discrete steps that describes a complete solution to a given problem computable in a finite amount of time and space.
A good program achieves the following goals:
Requirements: A statement of what is to be provided by the computer system or software product.
Software specification: A detailed description of the function, inputs, processing, outputs, and special requirements of a software product. It provides the information needed to design and implement the program.
Abstraction: A model of a complex system that includes only the details essential to the perspective of the viewer of the system.
Abstractions are the fundamental way that we manage complexity. Different viewers use different abstractions of a particular system. The programs we write are abstractions; for example, a spreadsheet program used by an accountant models an accounting ledger. In programming, we should always strive to use abstractions to manage the complexity of developing software.
Information Hiding: The practice of hiding the details of a module with the goal of controlling access to the details from the rest of the system.
A module (a cohesive system subunit, like a class) is an abstraction tool. Modules provide services to each other through a carefully defined interface (such as the public methods of a class in Java) thereby managing the complexity of a system since a programmer can concentrate on one module at a time. Changes within a module should not necessitate changes in modules that use it (this independent quality of modules is known as loose coupling).
Stepwise Refinement has many variations such as:
Top-down: details are deferred as long as possible as we move from a general to a specific solution,
Bottom-up: details are delineated first, and are then brought together into increasingly higher-level components,
Functional decomposition: programs are written in logical units, called functions; the main module of the design is the main function. Functional decomposition is based on this hierarchy of tasks, with the main function controlling the processing. This approach is a top-down stepwise refinement with an emphasis on functionality.
Round-trip gestalt design:
This approach is a top-down stepwise refinement with an emphasis on objects and data.
Unified Modeling Language (UML)
The UML is used to specify, visualize, construct, and document the components of a software system.
UML diagrams (another forms of abstraction) hide implementation details and allow us to concentrate only on the major design components.
Class, Responsibility, and Collaboration (CRC)
While UML class diagrams model our design after we have developed them, CRC cards help us determine our designs in the first place. A CRC card contains room for identifying the following:
The object-oriented paradigm is founded on three interrelated constructs: classes, objects, and inheritance. Objects are the basic run-time entities in an object-oriented system. An object is an instantiation of a class; or alternatively, a class defines the structure of its objects
Classes
A class defines the structure of an object or a set of objects. A class definition includes variables (data) and methods (actions) that determine the behavior of the object.
public class Date
{
protected int year;
protected int month;
protected int day;
protected static final int MINYEAR = 1583;
public Date(int newMonth, int newDay, int newYear)
// initializes this Date with the parameter values
{
month = newMonth;
day = newDay;
year = newYear;
}
public int yearIs()
// returns the year value of this Date
{
return year;
}
public int monthIs()
// returns the month value of this Date
{
return month;
}
public int dayIs()
// returns the day value of this date
{
return day;
}
}
The Date class demonstrates two kinds of variables: instance variables and class variables. The instance variables of this class are year, month, and day. Their values vary for each different instance of an object of the class. Instance variables represent the attributes of an object. MINYEAR is a class variable because it is defined to be static. It is associated directly with the Date class, instead of with objects of the class. A single copy of a static variable is maintained for all the objects of the class.
The final modifier states that a variable is in its final form and cannot be modified; thus MINYEAR is a constant. By convention, we use only capital letters when naming constants. Further, it is standard procedure to declare constants as static variables.
The methods of the class are Date, yearIs, monthIs, and dayIs. Note that the Date method has the same name as the class, and recall that this means that it is a special type of method--a class constructor.
Constructors are used to create new instances of a class--to instantiate objects of a class.
The other three methods are classified as observer (or "assessor") methods since they "observe" and return instance variable values.
Observer: A method that returns an observation on the state of an object.
Objects
Objects are created from classes at run-time. They can contain and manipulate data. We could view an object-oriented system as a set of objects, working together by sending each other messages to solve a problem. To create an object in Java we use the new operator, along with the class constructor:
Date myDate = new Date(6, 24, 1951); Date yourDate = new Date(10, 11, 1953); Date ourDate = new Date(6, 15, 1985);
We say the variables myDate, yourDate, and ourDate reference "objects of the class Date" or simply "[are?] objects of the type Date." We could also refer to them as "Date objects."
The myDate, yourDate, and ourDate variables are not objects, but actually hold references to the objects. In reality, references are memory addresses. The memory address of the instantiated object is stored in the memory location assigned to the variable. If no object has been instantiated for a particular variable, then its memory location holds a null reference.
Object methods are invoked through the object upon which they act. For example, to assign the value of the year variable of ourDate to the integer variable theYear, we would code:
theYear = ourDate.yearIs();
Inheritance
Inheritance: A reuse tool that allows programmers to create a new class that is a specialization of an existing class. In this case, the new class is called a subclass of the existing class, which in turn is the superclass of the new class.
A subclass inherits features from a superclass. It adds new features, as needed, related to its specialization. It can also redefine inherited features as necessary: a subclass usually has more variables and methods than its superclass.
Suppose we are interested in creating an application to manipulate the Date objects. Suppose also that in the application, we want to "increment" a Date variable. The question here (aside from those arising from the sheer complexity of the proposed application) is that of where to implement the algorithm. There are several options:
We call the inheritance relationship an is relationship. Here, we say that an object of the class IncCase is also a Date object: InDate is a special case (or specialization) of Date. To create IncDate in Java we would code:
public class IncDate extends Date
{
public IncDate(int newMonth, int newDay, int newYear)
// Initializes this IncDate with the parameter values
{
super(newMonth, newDay, newYear);
}
public void increment()
// Increments this IncDate to represent the next day
{
// Increment algorithm here
}
}
Inheritance is indicated by the keyword extends, which shows that IncDate inherits from Date. It is not possible to inherit constructors in Java, so IncDate takes the month, day, and year parameters and passes them to the constructor of its superclass; it passes them to the Date class constructor using the super reserved word.
The other portion of the IncDate class is the new increment method which is classified as a transformer method, because it changes the internal state of the object. The increment transformer is invokes through the object is is to transform. E.g. the statement:
ourDate.increment();
transforms the ourDate object.
Transformer: A method that changes the internal state of an object.
...more discussion on inheritance...
The object-oriented design (OOD) methodology originated with the development of programs to simulate physical objects and processes in the real world...
Identifying Classes
Identifying classes, the key task in designing OO systems, draws upon the various tools previously discussed:
A standard technique for identifying classes and their methods is to look for objects and operations in the problem statement. Objects are usually nouns and operations are usually verbs. It is a good idea circle the nouns and underline the verbs on a printer copy of the requirements.
Recall too that a good way to validate the cohesiveness of an identified class is to try to describe its main responsibility in a single coherent phrase. If one cannot do this, one should reconsider one's design.
Other Design Issues
To summarize the CRC card process, we brainstorm the objects in a problem and abstract them into classes. Then we filter the list of classes to eliminate duplicates. For each class, we create a CRC card and list any obvious responsibilities that it should support. We then walk through a common scenario, recording responsibilities and collaborations as they are discovered. After that, we walk through additional scenarios, moving from common cases to special and exceptional cases. When it appears that we have all of the scenarios covered, we brainstorm additional scenarios that may need more responsibilities and collaborations. When our ideas for scenarios are exhausted, and all the scenarios are covered by the existing CRC cards, the design is done.
Testing: The process of executing a program with data set designed to discover errors.
Debugging: The process of removing known errors.
Acceptance tests: The process of testing the system in its real environment with real data.
Regression testing: Re-execution of program tests after modifications have been made in order to ensure that the program still works correctly.
Program verification: The process of determining the degree to which a software product fulfills its specifications. "Are we doing the job right?"
Program validation: The process of determining the degree to which software fulfills its intended purpose. "Are we doing the right job?"
The following are some types of software errors that show up at various points in program development and testing.
Some run-time errors stop execution of the program; we say the program "crashed" or "abnormally terminated." Run-time errors often occur when the programmer makes too many assumptions (such as that a divisor will never be zero) or because of unanticipated user errors (such as a user entering the wrong data type in response to a prompt, or supplying an invalid filename to a routine). Well written programs should not crash. They should catch such errors and stay in control until the user is ready to quit.
Robustness: The ability of a program to recover following an error; the ability of a program to continue to operate within its environment.
Preconditions: Assumptions that must be true on entry into an operation or method for the postconditions to be guaranteed. For example, the precondition in the IncDate class would be typified by the requirement that the year cannot be less than the class variable MINYEAR.
Using preconditions is like a contract between the programmer who creates the methods and the programmers who use the methods. The contract says that the programmer who creates the method is not going to try to catch the error conditions described by the preconditions, but as long as the preconditions are met, the method works correctly. It is up to the programmers you use the method to ensure that the method is never called without meeting the preconditions. This approach is called "programming by contract."
Postconditions: Statements that describe what results are to be expected at the exit of an operation or method, assuming that the preconditions are true.
By making explicit statements about what is expected at the interfaces between modules, we can avoid making logical errors based on misunderstandings.
Deskchecking: Tracing an execution of a design or program on paper. There are two extensions of deskchecking:
Walk-through: A verification method in which a team performs a manual simulation of the program or design.
Inspection: A verification method in which one member of a team reads the program or design line by line and the others point out errors.
Exception: Associated with an unusual, often unpredictable event, detectable by software or hardware, that requires special processing. The even may or may not be erroneous. All exception mechanisms have three parts: (1) Defining the exception, (2) generating--raising--the exception, and (3) handling the exception. This issue is explored in Ch2.
Within each test case, we perform a series of component tasks:
Unit testing: Test a class or method by itself.
Data Coverage
In those limited cases where the set of valid inputs, or the functional domain, is extremely small, we can verify a program unit by testing it against every possible input element. This approach, known as exhaustive testing, can prove conclusively that the software meets its specifications.
Functional domain: The set of valid input for a program or method.
It is often not practical to test a program or method by running it with every possible data input. In cases like these, we pick some other measurement as out testing goal: we could cover general classes of data and test one example of each category of inputs, as well as boundary and other special cases.
Blackbox testing: Testing a program or method based on the possible input values, treating the code as a "black box".
Code Coverage
Clear (white) box testing: Testing a program or method based on covering all of the branches or paths of the code.
Branch: A code segment that is not always executed; e.g. a switch state has as many branches as there are case labels.
Path: A combination of branches that might be traversed when a program or method is executed.
Path testing: A testing technique whereby the tester tries to execute all possible paths in a program or method.
Test Plan: A document showing the test cases planned for a program or module, their purposes, inputs, expected outputs, and criteria for success.
...
Discussion on Testing Java Data Structures.
Charles E. Oyibo
IDS :: CBA
:: UIC