Dec
16
2016

Programming Language Concept

Java

Java is a general-purpose computer programming language that is concurrent, class-based, object-oriented, and specifically designed to have as few implementation dependencies as possible. It is intended to let application developers “write once, run anywhere” (WORA), meaning that compiled Java code can run on all platforms that support Java without the need for recompilation. Java applications are typically compiled to bytecode that can run on any Java virtual machine (JVM) regardless of computer architecture. As of 2016, Java is one of the most popular programming languages in use, particularly for client-server web applications, with a reported 9 million developers. Java was originally developed by James Gosling at Sun Microsystems (which has since been acquired by Oracle Corporation) and released in 1995 as a core component of Sun Microsystems’ Java platform. The language derives much of its syntax from C and C++, but it has fewer low-level facilities than either of them.

The original and reference implementation Java compilers, virtual machines, and class libraries were originally released by Sun under proprietary licence. As of May 2007, in compliance with the specifications of the Java Community Process, Sun relicensed most of its Java technologies under the GNU General Public License. Others have also developed alternative implementations of these Sun technologies, such as the GNU Compiler for Java (bytecode compiler), GNU Classpath (standard libraries), and IcedTea-Web (browser plugin for applets).

The latest version is Java 8, which is the only version currently supported for free by Oracle, although earlier versions are supported both by Oracle and other companies on a commercial basis.

 

 

History

James Gosling, Mike Sheridan, and Patrick Naughton initiated the Java language project in June 1991. Java was originally designed for interactive television, but it was too advanced for the digital cable television industry at the time. The language was initially called Oak after an oak tree that stood outside Gosling’s office. Later the project went by the name Green and was finally renamed Java, from Java coffee.Gosling designed Java with a C/C++-style syntax that system and application programmers would find familiar.

Sun Microsystems released the first public implementation as Java 1.0 in 1995.It promised “Write Once, Run Anywhere” (WORA), providing no-cost run-times on popular platforms. Fairly secure and featuring configurable security, it allowed network- and file-access restrictions. Major web browsers soon incorporated the ability to run Java applets within web pages, and Java quickly became popular, while mostly outside of browsers, that wasn’t the original plan. In January 2016, Oracle announced that Java runtime environments based on JDK 9 will discontinue the browser plugin. The Java 1.0 compiler was re-written in Java by Arthur van Hoff to comply strictly with the Java 1.0 language specification. With the advent of Java 2 (released initially as J2SE 1.2 in December 1998 – 1999), new versions had multiple configurations built for different types of platforms. J2EE included technologies and APIs for enterprise applications typically run in server environments, while J2ME featured APIs optimized for mobile applications. The desktop version was renamed J2SE. In 2006, for marketing purposes, Sun renamed new J2 versions as Java EE, Java ME, and Java SE, respectively.

In 1997, Sun Microsystems approached the ISO/IEC JTC 1 standards body and later the Ecma International to formalize Java, but it soon withdrew from the process.Java remains a de facto standard, controlled through the Java Community Process. At one time, Sun made most of its Java implementations available without charge, despite their proprietary software status. Sun generated revenue from Java through the selling of licenses for specialized products such as the Java Enterprise System.

On November 13, 2006, Sun released much of its Java virtual machine (JVM) as free and open-source software, (FOSS), under the terms of the GNU General Public License (GPL). On May 8, 2007, Sun finished the process, making all of its JVM’s core code available under free software/open-source distribution terms, aside from a small portion of code to which Sun did not hold the copyright.

Sun’s vice-president Rich Green said that Sun’s ideal role with regard to Java was as an “evangelist”. Following Oracle Corporation‘s acquisition of Sun Microsystems in 2009–10, Oracle has described itself as the “steward of Java technology with a relentless commitment to fostering a community of participation and transparency”.This did not prevent Oracle from filing a lawsuit against Google shortly after that for using Java inside the Android SDK (see Google section below). Java software runs on everything from laptops to data centers, game consoles to scientific supercomputers. On April 2, 2010, James Gosling resigned from Oracle.

Principles

There were five primary goals in the creation of the Java language:[16]

  1. It must be “simple, object-oriented, and familiar”.
  2. It must be “robust and secure”.
  3. It must be “architecture-neutral and portable”.
  4. It must execute with “high performance”.
  5. It must be “interpreted, threaded, and dynamic”.

 

ADVANTAGES

  1. Java is Simple: Java was designed to be easy to use and is therefore easy to write, compile, debug, and learn than other programming languages.
  2. Java is Object-Oriented: Java is object-oriented because programming in Java is centered on creating objects, manipulating objects, and making objects work together. This allows you to create modular programs and reusable code.
  3. Java is Platform-Independent: One of the most significant advantages of Java is its ability to move easily from one computer system to another.
  4. Java is Distributed: Distributed computing involves several computers on a network working together.
  5. Java is Interpreted: An interpreter is needed in order to run Java programs. The programs are compiled into Java Virtual Machine code called bytecode. The bytecode is machine independent and is able to run on any machine that has a Java interpreter.
  6. Java is Secure: Java is one of the first programming languages to consider security as part of its design.
  7. Java is Multithreaded: Multithreaded is the capability for a program to perform several tasks simultaneously within a program.

 

DISADVANTAGES

  1. Performance: Java can be perceived as significantly slower and more memory-consuming than natively compiled languages such as C or C++.
  2. Look and feel: The default look and feel of GUI applications written in Java using the Swing toolkit is very different from native applications.
  3. Single-paradigm language: Java is predominantly a single-paradigm language. However, with the addition of static imports in Java 5.0 the procedural paradigm is better accommodated than in earlier versions of Java.

 

Syntax & Semantics

Syntax is about the structure or the grammar of the language. It answers the question: how do I construct a valid sentence? All languages, even English and other human (aka “natural”) languages have grammars, that is, rules that define whether or not the sentence is properly constructed.

Here are some C language syntax rules:

  • separate statements with a semi-colon
  • enclose the conditional expression of an IF statement inside parentheses
  • group multiple statements into a single statement by enclosing in curly braces
  • data types and variables must be declared before the first executable statement (this feature has been dropped in C99. C99 and latter allow mixed type declarations.)

Semantics is about the meaning of the sentence. It answers the questions: is this sentence valid? If so, what does the sentence mean? For example:

x++; // increment foo(xyz, –b, &qrs); // call foo

are syntactically valid C statements. But what do they mean? Is it even valid to attempt to transform these statements into an executable sequence of instructions? These questions are at the heart of semantics.

Consider the ++ operator in the first statement. First of all, is it even valid to attempt this?

  • If x is a float data type, this statement has no meaning (according to the C language rules) and thus it is an error even though the statement is syntactically correct.
  • If x is a pointer to some data type, the meaning of the statement is to “add sizeof(some data type) to the value at address x and store the result into the location at address x”.
  • If x is a scalar, the meaning of the statement is “add one to the value at address x and store the result into the location at address x”.

 

In summary, syntax is the concept that concerns itself only whether or not the sentence is valid for the grammar of the language . Semantics is about whether or not the sentence has a valid meaning.

 

Java Syntax

A Java file can contain the following elements:

  • Package declaration
  • Import statements
  • Type declaration
    • Fields
    • Class initializers
    • Constructors
    • Methods

A Java file can also contain comments and annotations, but I will cover these in later texts.

Below is an example .java file that contains all of the above elements, so you can see the basic syntax of a .java file:

package javacore;

import java.util.HashMap;

public class MyClass {

protected final String name = “John”;

{
//class initializer
}

public MyClass() {
}

public String getName() {
return this.name;
}

public static void main(String[] args) {
}
}
This example contain several elements from the Java syntax. Each will be covered in the following subsections.

 

 

Package Declaration

The first line in the code example shown earlier is the package declaration. This part, to be more specific:

package javacore;
The package declaration consists of the word package, a space, and then the name of the package the type is to be located in. The .java file should be located in a directory structure that matches the package name. Packages and package declarations are covered in more detail in the text on Java packages.

Import Statements

The second line in the code example above is an import statement. To be more specific, this part:

import java.util.HashMap;
This example only has a single import statement, but multiple import statements can be used, each on its own line.

An import statement tells the Java compiler which other Java files this Java file is using. A Java file only needs to import Java files which are not located in the same Java package as the Java file .

Type Declaration

The third line in the code example above is the type declaration. In Java a type is either a class, an abstract class an interface, an enum or an annotation.

In this example it type declared is a class. The type declaration is delimited by a { and a }. As you can see, the beginning { is listed on the same line as the type declaration. The finishing } is on the last line of the example.

public class MyClass {

Field Declarations

The fourth line in the example above is a field declaration. The field declaration ends with a semicolon ;. Fields are covered in more detail in the text on Java fields. A type (class / interface / enum) can have more than one field. This example just has one field:

protected final String name = “John”;

 

 

Class Initializers

The fifth line (or block of lines) is a class initializer block. It begins with a { and ends with a }. Inside this block you can put initialization code that is to be executed a instance of the class is created. In this example the block is empty. The text inside the block is just a comment. The Java compiler ignores it.

{
//class initializer
}
Class initializers can also be static. Then they are executed already when the class is loaded, and only once because the class is only loaded in the Java Virtual Machine once. Here is an example of a static initializer block:

static {
//static class initializer
}
Notice the keyword static before the block. This makes the class initializer block static.

Constructors

The sixth block is a constructor. Constructors are similar to class initializers, except they can take parameters. Constructors are covered in more detail in the text on Java constructors. A class can have more than one constructor, although this example just shows one.

Public MyClass() {
}

Methods

The seventh element (or block) is a method. When you create an instance of a class (an object) the object can have methods you can execute. These are also sometimes called “instance methods” because they require an instance of the object before you can call the method. Methods are covered in more detail in the text on Java methods . Here is the method declaration from the example above:

public String getName() {
return this.name;
}
The eigth block is a static method. A static method belongs to the class, not objects of the class. That means that you can call a static method without having an object of the class the static method belongs to.

public static void main(String[] args) {
}

Type Declaration End

The final line in the example is the end of the type declaration, as mentioned earlier.

}
This means that there will come no more Java code which are part of the declared type

A name is a mnemonic character string representing something else:

  • x, sin, f, prog1, null? are names
  • 1, 2, 3, “test” are not names
  • +, <=, . . . may be names if they are not built-in operators

 

A binding is an association between two entities:

  • Name and memory location (for variables)
  • Name and function Typically a binding is between a name and the object it refers to. A referencing environment is a complete set of bindings active at a certain point in a program.

The scope of a binding is the region of a program or time interval(s) in the program’s execution during which the binding is active.

 

A scope is a maximal region of the program where no bindings are destroyed (e.g., body of a procedure).

 

BINDING TIMES

Compile time

  • Map high-level language constructs to machine code
  • Layout static data in memory

Link time

  • Resolve references between separately compiled modules

Load time

  • Assign machine addresses to static data

Run time

  • Bind values to variables
  • Allocate dynamic data and assign to variables
  • Allocate local variables of procedures on the stack

 

IMPORTANCE OF BINDING TIME

Early binding

  • Faster code
  • Typical in compiled languages

Late binding

  • Greater flexibility
  • Typical in interpreted languages

 

Expressions

An expression is a construct made up of variables, operators, and method invocations, which are constructed according to the syntax of the language, that evaluates to a single value. You’ve already seen examples of expressions, illustrated in bold below:

int cadence = 0;
anArray[0] = 100;
System.out.println(“Element 1 at index 0: ” + anArray[0]);

int result = 1 + 2; // result is now 3
if (value1 == value2)
System.out.println(“value1 == value2”);
The data type of the value returned by an expression depends on the elements used in the expression. The expression cadence = 0 returns an int because the assignment operator returns a value of the same data type as its left-hand operand; in this case, cadence is an int. As you can see from the other expressions, an expression can return other types of values as well, such as boolean or String.

The Java programming language allows you to construct compound expressions from various smaller expressions as long as the data type required by one part of the expression matches the data type of the other. Here’s an example of a compound expression:
1 * 2 * 3
In this particular example, the order in which the expression is evaluated is unimportant because the result of multiplication is independent of order; the outcome is always the same, no matter in which order you apply the multiplications. However, this is not true of all expressions. For example, the following expression gives different results, depending on whether you perform the addition or the division operation first:

x + y / 100    // ambiguous
You can specify exactly how an expression will be evaluated using balanced parenthesis: ( and ). For example, to make the previous expression unambiguous, you could write the following:
(x + y) / 100  // unambiguous, recommended

If you don’t explicitly indicate the order for the operations to be performed, the order is determined by the precedence assigned to the operators in use within the expression. Operators that have a higher precedence get evaluated first. For example, the division operator has a higher precedence than does the addition operator. Therefore, the following two statements are equivalent:

x + y / 100

x + (y / 100) // unambiguous, recommended
When writing compound expressions, be explicit and indicate with parentheses which operators should be evaluated first. This practice makes code easier to read and to maintain.

 

Statements

Statements are roughly equivalent to sentences in natural languages. A statement forms a complete unit of execution. The following types of expressions can be made into a statement by terminating the expression with a semicolon (;).

  • Assignment expressions
  • Any use of ++ or —
  • Method invocations
  • Object creation expressions

Such statements are called expression statements. Here are some examples of expression statements.

// assignment statement
aValue = 8933.234;
// increment statement
aValue++;
// method invocation statement
System.out.println(“Hello World!”);
// object creation statement
Bicycle myBike = new Bicycle();
In addition to expression statements, there are two other kinds of statements: declaration statements and control flow statements. A declaration statement declares a variable. You’ve seen many examples of declaration statements already:

// declaration statement
double aValue = 8933.234;
Finally, control flow statements regulate the order in which statements get executed. You’ll learn about control flow statements in the next section, Control Flow Statements

 

Blocks

A block is a group of zero or more statements between balanced braces and can be used anywhere a single statement is allowed. The following example, BlockDemo, illustrates the use of blocks:

class BlockDemo {
public static void main(String[] args) {
boolean condition = true;
if (condition) { // begin block 1
System.out.println(“Condition is true.”);
} // end block one
else { // begin block 2
System.out.println(“Condition is false.”);
} // end block 2
}
}
 

JAVA CONTROL STRUCTURE STATEMENTS

Java Control statements control the order of execution in a java program, based on data values and conditional logic. There are three main categories of control flow statements;

Selection statements: if, if-else and switch.

Loop statements: while, do-while and for.

Transfer statements: break, continue, return, try-catch-finally and assert.

We use control statements when we want to change the default sequential order of execution

SELECTION STATEMENTS

The If Statement

The if statement executes a block of code only if the specified expression is true. If the value is false, then the if block is skipped and execution continues with the rest of the program. You can either have a single statement or a block of code within an if statement. Note that the conditional expression must be a Boolean expression.

The simple if statement has the following syntax:

   if (<conditional expression>)

       <statement action>

Below is an example that demonstrates conditional execution based on if statement condition.

 

public class IfStatementDemo {

public static void main(String[] args) {
int a = 10, b = 20;
if (a > b)
System.out.println(“a > b”);
if (a < b)
System.out.println(“b < a”);
}
}

Output

b > a

 

The If-else Statement

The if/else statement is an extension of the if statement. If the statements in the if statement fails, the statements in the else block are executed. You can either have a single statement or a block of code within if-else blocks. Note that the conditional expression must be a Boolean expression.

The if-else statement has the following syntax:

if (<conditional expression>)

<statement action>

else

<statement action>

Below is an example that demonstrates conditional execution based on if else statement condition.

public class IfElseStatementDemo {

public static void main(String[] args) {
int a = 10, b = 20;
if (a > b) {
System.out.println(“a > b”);
} else {
System.out.println(“b < a”);
}
}
}
Switch Case Statement

The switch case statement, also called a case statement is a multi-way branch with several choices. A switch is easier to implement than a series of if/else statements. The switch statement begins with a keyword, followed by an expression that equates to a no long integral value. Following the controlling expression is a code block that contains zero or more labeled cases. Each label must equate to an integer constant and each must be unique. When the switch statement executes, it compares the value of the controlling expression to the values of each case label. The program will select the value of the case label that equals the value of the controlling expression and branch down that path to the end of the code block. If none of the case label values match, then none of the codes within the switch statement code block will be executed. Java includes a default label to use in cases where there are no matches. We can have a nested switch within a case block of an outer switch. Its general form is as follows:

  switch (<non-long integral expression>) {

     case label1: <statement1>

     case label2: <statement2>

        …

    case labeln: <statementn>

    default: <statement>

    } // end switch

When executing a switch statement, the program falls through to the next case. Therefore, if you want to exit in the middle of the switch statement code block, you must insert a break statement, which causes the program to continue executing after the current code block.

Below is a java example that demonstrates conditional execution based on nested if else statement condition to find the greatest of 3 numbers.

public class SwitchCaseStatementDemo {

public static void main(String[] args) {
int a = 10, b = 20, c = 30;
int status = -1;
if (a > b && a > c) {
status = 1;
} else if (b > c) {
status = 2;
} else {
status = 3;
}
switch (status) {
case 1:
System.out.println(“a is the greatest”);
break;
case 2:
System.out.println(“b is the greatest”);
break;
case 3:
System.out.println(“c is the greatest”);
break;
default:
System.out.println(“Cannot be determined”);
}
}
}

Output

Control statements control the order of execution in a java program, based on data values and conditional logic.

There are three main categories of control flow statements;

Selection statements: if, if-else and switch.

Loop statements: while, do-while and for.

Transfer statements: break, continue, return, try-catch-finally and assert.

We use control statements when we want to change the default sequential order of execution

ITERATION STATEMENTS

While Statement

The while statement is a looping construct control statement that executes a block of code while a condition is true. You can either have a single statement or a block of code within the while loop. The loop will never be executed if the testing expression evaluates to false. The loop condition must be a boolean expression.

The syntax of the while loop is

while (<loop condition>)

<statements>

Below is an example that demonstrates the looping construct namely while loop used to print numbers from 1 to 10.

public class WhileLoopDemo {

public static void main(String[] args) {
int count = 1;
System.out.println(“Printing Numbers from 1 to 10”);
while (count <= 10) {
System.out.println(count++);
}
}
}

Output

Printing Numbers from 1 to 10

1

2

3

4

5

6

7

8

9

10

 

Do-while Loop Statement

The do-while loop is similar to the while loop, except that the test is performed at the end of the loop instead of at the beginning. This ensures that the loop will be executed at least once. A do-while loop begins with the keyword do, followed by the statements that make up the body of the loop. Finally, the keyword while and the test expression completes the do-while loop. When the loop condition becomes false, the loop is terminated and execution continues with the statement immediately following the loop. You can either have a single statement or a block of code within the do-while loop.

The syntax of the do-while loop is

do

<loop body>

while (<loop condition>);

Below is an example that demonstrates the looping construct namely do-while loop used to print numbers from 1 to 10.

public class DoWhileLoopDemo {

public static void main(String[] args) {
int count = 1;
System.out.println(“Printing Numbers from 1 to 10”);
do {
System.out.println(count++);
} while (count <= 10);
}
}

Output

Printing Numbers from 1 to 10

1

2

3

4

5

6

7

8

9

10

Below is an example that creates A Fibonacci sequence controlled by a do-while loop

public class Fibonacci {

public static void main(String args[]) {
System.out.println(“Printing Limited set of Fibonacci Sequence”);
double fib1 = 0;
double fib2 = 1;
double temp = 0;
System.out.println(fib1);
System.out.println(fib2);
do {
temp = fib1 + fib2;
System.out.println(temp);
fib1 = fib2; //Replace 2nd with first number
fib2 = temp; //Replace temp number with 2nd number
} while (fib2 < 5000);
}
}

Output

Printing Limited set of Fibonacci Sequence

0.0

1.0

1.0

2.0

3.0

5.0

8.0

13.0

21.0

34.0

55.0

89.0

144.0

233.0

377.0

610.0

987.0

1597.0

2584.0

4181.0

6765.0

For Loops

The for loop is a looping construct which can execute a set of instructions a specified number of times. It’s a counter controlled loop.

The syntax of the loop is as follows:

for (<initialization>; <loop condition>; <increment expression>)

<loop body>

The first part of a for statement is a starting initialization, which executes once before the loop begins. The <initialization> section can also be a comma-separated list of expression statements. The second part of a for statement is a test expression. As long as the expression is true, the loop will continue. If this expression is evaluated as false the first time, the loop will never be executed. The third part of the for statement is the body of the loop. These are the instructions that are repeated each time the program executes the loop. The final part of the for statement is an increment expression that automatically executes after each repetition of the loop body. Typically, this statement changes the value of the counter, which is then tested to see if the loop should continue.

All the sections in the for-header are optional. Any one of them can be left empty, but the two semicolons are mandatory. In particular, leaving out the <loop condition> signifies that the loop condition is true. The (;;) form of for loop is commonly used to construct an infinite loop.

Below is an example that demonstrates the looping construct namely for loop used to print numbers from 1 to 10.

public class ForLoopDemo {

public static void main(String[] args) {
System.out.println(“Printing Numbers from 1 to 10”);
for (int count = 1; count <= 10; count++) {
System.out.println(count);
}
}
}

Output

Printing Numbers from 1 to 10

1

2

3

4

5

6

7

8

9

10

 

Download ForLoopDemo.java

Control statements control the order of execution in a java program, based on data values and conditional logic. There are three main categories of control flow statements;

Selection statements: if, if-else and switch.

Loop statements: while, do-while and for.

Transfer statements: break, continue, return, try-catch-finally and assert.

We use control statements when we want to change the default sequential order of execution

 

TRANSFER STATEMENTS

Continue Statement

A continue statement stops the iteration of a loop (while, do or for) and causes execution to resume at the top of the nearest enclosing loop. You use a continue statement when you do not want to execute the remaining statements in the loop, but you do not want to exit the loop itself.

The syntax of the continue statement is

continue; // the unlabeled form

continue <label>; // the labeled form

You can also provide a loop with a label and then use the label in your continue statement. The label name is optional, and is usually only used when you wish to return to the outermost loop in a series of nested loops.

Below is a program to demonstrate the use of continue statement to print Odd Numbers between 1 to 10.

public class ContinueExample {

public static void main(String[] args) {
System.out.println(“Odd Numbers”);
for (int i = 1; i <= 10; ++i) {
if (i % 2 == 0)
continue;
// Rest of loop body skipped when i is even
System.out.println(i + “\t”);
}
}
}

Output

Odd Numbers

1

3

5

7

9

Break Statement

The break statement transfers control out of the enclosing loop ( for, while, do or switch statement). You use a break statement when you want to jump immediately to the statement following the enclosing control structure.

The Syntax for break statement is as shown below;

break; // the unlabeled form

break <label>; // the labeled form

Below is a program to demonstrate the use of break statement to print numbers Numbers 1 to 10.

public class BreakExample {

public static void main(String[] args) {
System.out.println(“Numbers 1 – 10”);
for (int i = 1;; ++i) {
if (i == 11)
break;
// Rest of loop body skipped when i is even
System.out.println(i + “\t”);
}
}
}

Output

Numbers 1 – 10

1

2

3

4

5

6

7

8

9

10

 

Abstract Data Type

introduction

In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

 

Formally, an ADT may be defined as a “class of objects whose logical behavior is defined by a set of values and a set of operations”; this is analogous to an algebraic structure in mathematics. What is meant by “behavior” varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model;these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively. Some authors also include the computational complexity (“cost”), both in terms of time (for computing operations) and space (for representing values). In practice many common data types are not ADTs, as the abstraction is not perfect, and users must be aware of issues like arithmetic overflow that are due to the representation. For example, integers are often stored as fixed width values (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.

 

ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages—mainstream computer languages do not directly support formally specified ADTs. However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract. ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language.

Implementation

Implementing an ADT means providing one procedure or function for each abstract operation. The ADT instances are represented by some concrete data structure that is manipulated by those procedures, according to the ADT’s specifications.

Usually there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented by a linked list or by an array.

In order to prevent clients from depending on the implementation, an ADT is often packaged as an opaque data type in one or more modules, whose interface contains only the signature (number and types of the parameters and results) of the operations. The implementation of the module—namely, the bodies of the procedures and the concrete data structure used—can then be hidden from most clients of the module. This makes it possible to change the implementation without affecting the clients. If the implementation is exposed, it is known instead as a transparent data type.

When implementing an ADT, each instance (in imperative-style definitions) or each state (in functional-style definitions) is usually represented by a handle of some sort.[8]

Modern object-oriented languages, such as C++ and Java, support a form of abstract data types. When a class is used as a type, it is an abstract type that refers to a hidden representation. In this model an ADT is typically implemented as a class, and each instance of the ADT is usually an object of that class. The module’s interface typically declares the constructors as ordinary procedures, and most of the other ADT operations as methods of that class. However, such an approach does not easily encapsulate multiple representational variants found in an ADT. It also can undermine the extensibility of object-oriented programs. In a pure object-oriented program that uses interfaces as types, types refer to behaviors not representations.

 

Example: implementation of the abstract stack

As an example, here is an implementation of the abstract stack above in the C programming language.

Imperative-style interface

An imperative-style interface might be:

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty
This interface could be used in the following manner:

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if(stack_empty(s)) { }      // does something if stack is empty
This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether the stack state s continues to exist after a call x ← pop(s).

In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and the array size).

Functional-style interface

Functional-style ADT definitions are more appropriate for functional programming languages, and vice versa. However, one can provide a functional-style interface even in an imperative language like C. For example:

typedef struct stack_Rep stack_Rep;          // type: stack state representation (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

ADT libraries

Many modern programming languages, such as C++ and Java, come with standard libraries that implement several common ADTs, such as those listed above.

Built-in abstract data types

The specification of some programming languages is intentionally vague about the representation of certain built-in data types, defining only the operations that can be done on them. Therefore, those types can be viewed as “built-in ADTs”. Examples are the arrays in many scripting languages, such as Awk, Lua, and Perl, which can be regarded as an implementation of the abstract list.

Written by ivan09 in: Uncategorized |

No Comments »

RSS feed for comments on this post. TrackBack URL


Leave a Reply

Powered by WordPress. Theme: TheBuckmaker. Zinsen, Streaming Audio