Encapsulation in Java. Java provides language support for information hiding. When we declare an instance variable (or method) as private, this means that the client (code written in another module) cannot directly access that instance variable (or method). The client can only access the API through the public methods and constructors. Programmer can modify the implementation of private methods (or use different instance variables) with the comfort that no client will be directly affected.
Program Counter.java implements a counter, e.g., for an electronic voting machine. It encapsulates a single integer to ensure that it can only get incremented by one at at time and to ensure that it never goes negative. The goal of data abstraction is to restrict which operations you can perform. Can ensure that data type value always remains in a consistent state. Can add logging capability to hit(), e.g., to print timestamp of each vote. In the 2000 presidential election, Al Gore received negative 16,022 votes on an electronic voting machine in Volusia County, Florida. The counter variable was not properly encapsulated in the voting machine software!
Access control. Java provides a mechanism for access control to prevent the use of some variable or method in one part of a program from direct access in another. We have been careful to define all of our instance variables with the private access modifier. This means that they cannot be directly accessed from another class, thereby encapsulating the data type. For this reason, we always use private as the access modifier for our instance variables and recommend that you do the same. If you use public then you will greatly limit any opportunity to modify the class over time. Client programs may rely on your public variable in thousands of places, and you will not be able to remove it without breaking dependent code.
Getters and setters. A data type should not have public instance variables. You should obey this rule not just in letter, but also in spirit. Novice programmers are often tempted to include get() and set() methods for each instance variable, to read and write its value.
Complex a = new Complex(1.0, 2.0);
Complex b = new Complex(3.0, 4.0);
// violates spirit of encapsulation
Complex c = new Complex(0.0, 0.0);
c.setRe(a.re() + b.re());
c.setIm(a.im() + b.im());
// better design
Complex a = new Complex(1.0, 2.0);
Complex b = new Complex(3.0, 4.0);
Complex c = a.plus(b);
The purpose of encapsulation is not just to hide the data, but to hide design decisions which are subject to change. In other words, the client should tell an object what to do, rather than asking an object about its state (get()), making a decision, and then telling it how to do it (set()). Usually it's better design to not have the get() and set() methods. When a get() method is warranted, try to avoid including a set() method
Monday, January 11, 2010
Designing APIs
Designing APIs. Often the most important and most challenging step in building software is designing the APIs. In many ways, designing good programs is more challenging that writing the code itself. Takes practice, careful deliberation, and many iterations.
Specification problem. Document the API in English. Clearly articulate behavior for all possible inputs, including side effects. "Write to specification." Difficult problem. Many bugs introduced because programmer didn't correctly understand description of API. See booksite for information on automatic documentation using Javadoc.
Wide interfaces. "API should do one thing and do it well." "APIs should be as small as possible, but no smaller." "When in doubt, leave it out." (It's easy to add methods to an existing API, but you can never remove them without breaking existing clients.) APIs with lots of bloat are known as wide interfaces. Supply all necessary operations, but no more. Try to make methods orthogonal in functionality. No need for a method in Complex that adds three complex numbers since there is a method that adds two. The Math library includes methods for sin(), cos(), and tan(), but not sec().
Java libraries tend to have wide interfaces (some designed by pros, some by committee). Sometimes this seems to be the right thing, e.g., String. Although, sometimes you end up with poorly designed APIs that you have to live with forever.
Deprecated methods. Sometimes you end up with deprecated methods that are no longer fully supported, but you still need to keep them or break backward compatibility. Once Java included a method Character.isSpace(), programmers wrote programs that relied on its behavior. Later, they wanted to change the method to support additional Unicode whitespace characters. Can't change the behavior of isSpace() or that would break many programs. Instead, add a new method Character.isWhiteSpace() and "deprecate" the old method. The API is now more confusing than needed.
Almost all methods in java.util.Date are deprecated in favor of java.util.GregorianCalendar.
Backward compatibility. The need for backward compatibility shapes much of the way things are done today (from operating systems to programming languages to ...). [Insert a story.]
Standards. It is easy to understand why writing to an API is so important by considering other domains. Fax machines, radio, MPEG-4, MP3 files, PDF files, HTML, etc. Simpler to use a common standard. Lack of incompatibilities enables business opportunities that would otherwise be impossible. One of the challenges of writing software is making it portable so that it works on a variety of operating systems including Windows, OS X, and Linux. Java Virtual Machine enables portability of Java across platforms.
Specification problem. Document the API in English. Clearly articulate behavior for all possible inputs, including side effects. "Write to specification." Difficult problem. Many bugs introduced because programmer didn't correctly understand description of API. See booksite for information on automatic documentation using Javadoc.
Wide interfaces. "API should do one thing and do it well." "APIs should be as small as possible, but no smaller." "When in doubt, leave it out." (It's easy to add methods to an existing API, but you can never remove them without breaking existing clients.) APIs with lots of bloat are known as wide interfaces. Supply all necessary operations, but no more. Try to make methods orthogonal in functionality. No need for a method in Complex that adds three complex numbers since there is a method that adds two. The Math library includes methods for sin(), cos(), and tan(), but not sec().
Java libraries tend to have wide interfaces (some designed by pros, some by committee). Sometimes this seems to be the right thing, e.g., String. Although, sometimes you end up with poorly designed APIs that you have to live with forever.
Deprecated methods. Sometimes you end up with deprecated methods that are no longer fully supported, but you still need to keep them or break backward compatibility. Once Java included a method Character.isSpace(), programmers wrote programs that relied on its behavior. Later, they wanted to change the method to support additional Unicode whitespace characters. Can't change the behavior of isSpace() or that would break many programs. Instead, add a new method Character.isWhiteSpace() and "deprecate" the old method. The API is now more confusing than needed.
Almost all methods in java.util.Date are deprecated in favor of java.util.GregorianCalendar.
Backward compatibility. The need for backward compatibility shapes much of the way things are done today (from operating systems to programming languages to ...). [Insert a story.]
Standards. It is easy to understand why writing to an API is so important by considering other domains. Fax machines, radio, MPEG-4, MP3 files, PDF files, HTML, etc. Simpler to use a common standard. Lack of incompatibilities enables business opportunities that would otherwise be impossible. One of the challenges of writing software is making it portable so that it works on a variety of operating systems including Windows, OS X, and Linux. Java Virtual Machine enables portability of Java across platforms.
Sunday, January 10, 2010
String processing.
String processing. The program CommentStripper.java reads in a Java (or C++) program from standard input, removes all comments, and prints the result to standard output. This would be useful as part of a Java compiler. It removes /* */ and // style comments using a 5 state finite state automaton. It is meant to illustrate the power of DFAs, but to properly strip Java comments, you would need a few more states to handle extra cases, e.g., quoted string literals like s = "/***//*". The picture below is courtesy of David Eppstein.
DEFINATION & DESCRIPTION OF Finite state automata.
Finite state automata. A deterministic finite state automaton (DFA) is, perhaps, the simplest type of machine that is still interesting to study. Many of its important properties carry over to more complicated machines. So, before we hope to understand these more complicated machines, we first study DFAs. However, it is an enormously useful practical abstraction because DFAs still retain sufficient flexibility to perform interesting tasks, yet the hardware requirements for building them are relatively minimal. DFAs are widely used in text editors for pattern matching, in compilers for lexical analysis, in web browsers for html parsing, and in operating systems for graphical user interfaces. They also serve as the control unit in many physical systems including: vending machines, elevators, automatic traffic signals, and computer microprocessors. Also network protocol stacks and old VCR clocks. They also play a key role in natural language processing and machine learning.
A DFA captures the basic elements of an abstract machine: it reads in a string, and depending on the input and the way the machine was designed, it outputs true or false. A DFA is always is one of N states, which we name 0 through N-1. Each state is labeled true or false. The DFA begins in a distinguished state called the start state. As the input characters are read in one at a time, the DFA changes from one state to another in a prespecified way. The new state is completely determined by the current state and the character just read in. When the input is exhausted, the DFA outputs true or false according to the label of the state it is currently in.
UPPER PICTURE is an example of a DFA that accepts binary strings that are multiples of 3. For example, the machine rejects 1101 since 1101 in binary is 13 in decimal, which is not divisible by 3. On the other hand, the machine accepts 1100 since it is 12 in decimal.
Abstract machines
Abstract machines. Modern computers are capable of performing a wide variety of computations. An abstract machine reads in an input string, and, depending on the input, outputs true (accept), outputs false (reject), or gets stuck in an infinite loop and outputs nothing. We say that a machine recognizes a particular language, if it outputs true for any input string in the language and false otherwise. The artificial restriction to such decision problems is purely for notational convenience. Virtually all computational problems can be recast as language recognition problems. For example, to determine whether an integer 97 is prime, we can ask whether 97 is in the language consisting of all primes {2, 3, 5, 7, 13, ... } or to determine the decimal expansion of the mathematical constant π we can ask whether 7 is the 100th digit of π and so on.
We would like to be able to formally compare different classes of abstract machines in order to address questions like Is a Mac more powerful than a PC? Can Java do more things than C++? To accomplish this, we define a notion of power. We say that machine A is at least as powerful as machine B if machine A can be "programmed'" to recognize all of the languages that B can. Machine A is more powerful than B, if in addition, it can be programmed to recognize at least one additional language. Two machines are equivalent if they can be programmed to recognize precisely the same set of languages. Using this definition of power, we will classify several fundamental machines. Naturally, we are interested in designing the most powerful computer, i.e., the one that can solve the widest range of language recognition problems. Note that our notion of power does not say anything about how fast a computation can be done. Instead, it reflects a more fundamental notion of whether or not it is even possible to perform some computation in a finite number of steps.
We would like to be able to formally compare different classes of abstract machines in order to address questions like Is a Mac more powerful than a PC? Can Java do more things than C++? To accomplish this, we define a notion of power. We say that machine A is at least as powerful as machine B if machine A can be "programmed'" to recognize all of the languages that B can. Machine A is more powerful than B, if in addition, it can be programmed to recognize at least one additional language. Two machines are equivalent if they can be programmed to recognize precisely the same set of languages. Using this definition of power, we will classify several fundamental machines. Naturally, we are interested in designing the most powerful computer, i.e., the one that can solve the widest range of language recognition problems. Note that our notion of power does not say anything about how fast a computation can be done. Instead, it reflects a more fundamental notion of whether or not it is even possible to perform some computation in a finite number of steps.
DEFNATION OF Turing machines
Turing machines are the most general automata. They consist of a finite set of states and an infinite tape which contains the input and is used to read and write symbols during the computation. Since Turing machines can leave symbols on their tape at the end of the computation, they can be viewed as computing functions: the partial recursive functions. Despite the simplicity of these automata, any algorithm that can be implemented on a computer can be modeled by some Turing machine.
Turing machines are used in the characterization of the complexity of problems. The complexity of a problem is determined by the efficiency of the best algorithm that solves it. Measures of an algorithm's efficiency are the amount of time or space that a Turing machine requires to implement the algorithm. A computation's time is the number of configurations involved in that computation, and its space corresponds to the number of positions on its tape that were used.
Turing machines are used in the characterization of the complexity of problems. The complexity of a problem is determined by the efficiency of the best algorithm that solves it. Measures of an algorithm's efficiency are the amount of time or space that a Turing machine requires to implement the algorithm. A computation's time is the number of configurations involved in that computation, and its space corresponds to the number of positions on its tape that were used.
DEFINATION ABOUT Automata Theory
Automata theory is a further step in abstracting your attention away from any
particular kind of computer or particular programming language. In automata theory
we consider a mathematical model of computing. Such a model strips the computational
machinery—the “programming language”—down to the bare minimum, so that it’s easy
to manipulate these theoretical machines (there are several such models, for different purposes, as you’ll soon see) mathematically to prove things about their capabilities.
For the most part, these mathematical models are not used for practical programming
problems. Real programming languages are much more convenient to use. But the very
flexibility that makes real languages easier to use also makes them harder to talk about in a formal way. The stripped-down theoretical machines are designed to be examined
mathematically.
What’s a mathematical model? You’ll see one shortly, called a “finite-state machine.”
The point of this study is that the mathematical models are, in some important ways,
to real computers and real programming languages. What this means is that
any problem that can be solved on a real computer can be solved using these models,and vice versa. Anything we can prove about the models sheds light on the real problems of computer programming as well.
The questions asked in automata theory include these: Are there any problems that
no computer can solve, no matter how much time and memory it has? Is it possible to
PROVE that a particular computer program will actually solve a particular problem? If a computer can use two different external storage devices (disks or tapes) at the same time,does that extend the range of problems it can solve compared to a machine with only one such device?
There is also a larger question lurking in the background of automata theory: Does
the human mind solve problems in the same way that a computer does? Are people
subject to the same limitations as computers? Automata theory does not actually answer this question, but the insights of automata theory can be helpful in trying to work out an answer. We’ll have more to say about this in the chapter on artificial intelligence
particular kind of computer or particular programming language. In automata theory
we consider a mathematical model of computing. Such a model strips the computational
machinery—the “programming language”—down to the bare minimum, so that it’s easy
to manipulate these theoretical machines (there are several such models, for different purposes, as you’ll soon see) mathematically to prove things about their capabilities.
For the most part, these mathematical models are not used for practical programming
problems. Real programming languages are much more convenient to use. But the very
flexibility that makes real languages easier to use also makes them harder to talk about in a formal way. The stripped-down theoretical machines are designed to be examined
mathematically.
What’s a mathematical model? You’ll see one shortly, called a “finite-state machine.”
The point of this study is that the mathematical models are, in some important ways,
to real computers and real programming languages. What this means is that
any problem that can be solved on a real computer can be solved using these models,and vice versa. Anything we can prove about the models sheds light on the real problems of computer programming as well.
The questions asked in automata theory include these: Are there any problems that
no computer can solve, no matter how much time and memory it has? Is it possible to
PROVE that a particular computer program will actually solve a particular problem? If a computer can use two different external storage devices (disks or tapes) at the same time,does that extend the range of problems it can solve compared to a machine with only one such device?
There is also a larger question lurking in the background of automata theory: Does
the human mind solve problems in the same way that a computer does? Are people
subject to the same limitations as computers? Automata theory does not actually answer this question, but the insights of automata theory can be helpful in trying to work out an answer. We’ll have more to say about this in the chapter on artificial intelligence
Friday, January 8, 2010
DESCRIPTION ABOUT EVENT CLASSES IN JAVA (OBJECT ORIENTED PROG)
EVENT CLASSES
The classes that represent events are the core of java’s event handling mechanism .
thus we begin our study of event handling with a tour of the event classes .As our will see,they provide a consistent ,easy-to-use means of encapsulatating events.
At the root of java event class hierarchy is Eventobject, which is in java .util.It
Is the superclass for all events.its one constructor is show here
EventObject(Object src)
Here , src is the object that generates this event.
EventObject contain two methods: getsource() & toString().The getsource() method return the source of events . its general form show here:
Objectgetsource()
As expected string() return the string equivalent of the event
The class AWTEvent , define with in the java.awt package , is a subclass of EventObject.it is the superclass(either directly or indirectly) of all AWT-based event used by the delegation event model.its getID() method can be used ti determine the type of the event .the signature of this method is show here
Int getID()
At this point , it is important to know only that all of the other classes discusses in this section are subclasses of AWTEvent.
TO SUMMARIZE:
EventObject is a superclass of all event
AWTEvent is a superclass os all AWT event that are handled by the delegation event model.
The package java.awt.event define several types of event that are generated by various user interface elements .the table below enumerates the most important of these event classes & provide a breif description of when they are generated .The most commonly
used constructors,
EVENT ClASS DESCRIPTION
ACTIONEVENT Generated whan a button is presses,a list item
is double-clicked or a menu item is selected .
AdjustmentEvent Generated when a scroll bar is mainuplated.
ComponentEvent Generated when a component is hidden,moved,resizes,
Or become visible.
ContainerEvent Generated when a component is added to removes from a
Container.
FocusEvent Generated when a component gains or loses keyboard focus.
InputEvent Abstract super class for all component input event classes.
The classes that represent events are the core of java’s event handling mechanism .
thus we begin our study of event handling with a tour of the event classes .As our will see,they provide a consistent ,easy-to-use means of encapsulatating events.
At the root of java event class hierarchy is Eventobject, which is in java .util.It
Is the superclass for all events.its one constructor is show here
EventObject(Object src)
Here , src is the object that generates this event.
EventObject contain two methods: getsource() & toString().The getsource() method return the source of events . its general form show here:
Objectgetsource()
As expected string() return the string equivalent of the event
The class AWTEvent , define with in the java.awt package , is a subclass of EventObject.it is the superclass(either directly or indirectly) of all AWT-based event used by the delegation event model.its getID() method can be used ti determine the type of the event .the signature of this method is show here
Int getID()
At this point , it is important to know only that all of the other classes discusses in this section are subclasses of AWTEvent.
TO SUMMARIZE:
EventObject is a superclass of all event
AWTEvent is a superclass os all AWT event that are handled by the delegation event model.
The package java.awt.event define several types of event that are generated by various user interface elements .the table below enumerates the most important of these event classes & provide a breif description of when they are generated .The most commonly
used constructors,
EVENT ClASS DESCRIPTION
ACTIONEVENT Generated whan a button is presses,a list item
is double-clicked or a menu item is selected .
AdjustmentEvent Generated when a scroll bar is mainuplated.
ComponentEvent Generated when a component is hidden,moved,resizes,
Or become visible.
ContainerEvent Generated when a component is added to removes from a
Container.
FocusEvent Generated when a component gains or loses keyboard focus.
InputEvent Abstract super class for all component input event classes.
Subscribe to:
Posts (Atom)