HUNTING

Obj Lens

Algebraic specification

In the algebraic specification technique an object class or type is specified in terms of relationships existing between the operations defined on that type. It was first brought into prominence by Guttag [1980, 1985] in specification of abstract data types. Various notations of algebraic specifications have evolved, including those based on OBJ and Larch languages.

Representation of algebraic specification

Essentially, algebraic specifications define a system as a heterogeneous algebra. A heterogeneous algebra is a collection of different sets on which several operations are defined. Traditional algebras are homogeneous. A homogeneous algebra consists of a single set and several operations; {I, +, -, *, /}. In contrast, alphabetic strings together with operations of concatenation and length {A, I, con, len}, is not a homogeneous algebra, since the range of the length operation is the set of integers.

Each set of symbols in the algebra, in turn, is called a sort of the algebra. To define a heterogeneous algebra, we first need to specify its signature, the involved operations, and their domains and ranges. Using algebraic specification, we define the meaning of a set of interface procedure by using equations. An algebraic specification is usually presented in four sections.

Types section:-

In this section, the sorts (or the data types) being used is specified.

Exceptions section:-

This section gives the names of the exceptional conditions that might occur when different operations are carried out. These exception conditions are used in the later sections of an algebraic specification. For example, in a queue, possible exceptions are novalue (empty queue), underflow (removal from an empty queue), etc.

Syntax section:-

This section defines the signatures of the interface procedures. The collection of sets that form input domain of an operator and the sort where the output is produced are called the signature of the operator. For example, the append operation takes a queue and an element and returns a new queue. This is represented as:

append : queue x element → queue

Equations section:-

This section gives a set of rewrite rules (or equations) defining the meaning of the interface procedures in terms of each other. In general, this section is allowed to contain conditional expressions. For example, a rewrite rule to identify an empty queue may be written as:

isempty(create()) = true

By convention each equation is implicitly universally quantified over all possible values of the variables. Names not mentioned in the syntax section such as ‘r' or ‘e' are variables. The first step in defining an algebraic specification is to identify the set of required operations. After having identified the required operators, it is helpful to classify them as either basic constructor operators, extra constructor operators, basic inspector operators, or extra inspection operators. The definition of these categories of operators is as follows:

1.      Basic construction operators. These operators are used to create or modify entities of a type. The basic construction operators are essential to generate all possible element of the type being specified. For example, ‘create' and ‘append' are basic construction operators for a FIFO queue.

2.      Extra construction operators. These are the construction operators other than the basic construction operators. For example, the operator ‘remove' is an extra construction operator for a FIFO queue because even without using ‘remove', it is possible to generate all values of the type being specified.

3.      Basic inspection operators. These operators evaluate attributes of a type without modifying them, e.g., eval, get, etc. Let S be the set of operators whose range is not the data type being specified. The set of the basic operators S1 is a subset of S, such that each operator from S-S1 can be expressed in terms of the operators from S1. For example, ‘isempty' is a basic inspection operator because it does not modify the FIFO queue type.

4.      Extra inspection operators. These are the inspection operators that are not basic inspectors.

A good rule of thumb while writing an algebraic specification, is to first establish which are the constructor (basic and extra) and inspection operators (basic and extra). Then write down an axiom for composition of each basic construction operator over each basic inspection operator and extra constructor operator. Also, write down an axiom for each of the extra inspector in terms of any of the basic inspectors. Thus, if there are m1 basic constructors, m2 extra constructors, n1 basic inspectors, and n2 extra inspectors, we should have m1 × (m2+n1) + n2 axioms are the minimum required and many more axioms may be needed to make the specification complete. Using a complete set of rewrite rules, it is possible to simplify an arbitrary sequence of operations on the interface procedures.

Develop algebraic specification of simple problems

The first step in defining an algebraic specification is to identify the set of required operations. After having identified the required operators, it is helpful to classify them into different catgories.

A simple way to determine whether an operator is a constructor (basic or extra) or an inspector (basic or extra) is to check the syntax expression for the operator. If the type being specified appears on the right hand side of the expression then it is a constructor, otherwise it is an inspection operator. For example, in a FIFO queue, ‘create' is a constructor because the data type specified ‘queue' appears on the right hand side of the expression. But, ‘first' and ‘isempty' are inspection operators since they do not modify the queue data type.

Example:-

Let us specify a FIFO queue supporting the operations create, append, remove, first, and isempty where the operations have their usual meaning.

Types:

defines queue

uses boolean, integer

Exceptions:

underflow, novalue

Syntax:

1. create : φ → queue

2. append : queue x element → queue

3. remove : queue → queue + {underflow}

4. first : queue → element + {novalue}

5. isempty : queue → boolean

Equations:

1. isempty(create()) = true

2. isempty((append(q,e)) = false

3. first(create()) = novalue

4. first(append(q,e)) = is isempty(q) then e else first(q)

5. remove(create()) = underflow

6. remove(append(q,e)) = if isempty(q) then create() else append(remove(q),e)

In this example, there are two basic constructors (create and append), one extra construction operator (remove) and two basic inspectors (first and empty). Therefore, there are 2 x (1+2) + 0 = 6 equations.

Properties of algebraic specifications

Three important properties that every algebraic specification should possess are:

Completeness: This property ensures that using the equations, it should be possible to reduce any arbitrary sequence of operations on the interface procedures. There is no simple procedure to ensure that an algebraic specification is complete.

Finite termination property: This property essentially addresses the following question: Do applications of the rewrite rules to arbitrary expressions involving the interface procedures always terminate? For arbitrary algebraic equations, convergence (finite termination) is undecidable. But, if the right hand side of each rewrite rule has fewer terms than the left, then the rewrite process must terminate.

Unique termination property: This property indicates whether application of rewrite rules in different orders always result in the same answer. Essentially, to determine this property, the answer to the following question needs to be checked: Can all possible sequence of choices in application of the rewrite rules to an arbitrary expression involving the interface procedures always give the same number? Checking the unique termination property is a very difficult problem.

Advantages and disadvantages of algebraic specifications

Algebraic specifications have a strong mathematical basis and can be viewed as heterogeneous algebra. Therefore, they are unambiguous and precise. Using an algebraic specification, the effect of any arbitrary sequence of operations involving the interface procedures can automatically be studied. A major shortcoming of algebraic specifications is that they cannot deal with side effects. Therefore, algebraic specifications are difficult to interchange with typical programming languages. Also, algebraic specifications are hard to understand.

About the Author

Itech troubleshooter is an advanced web development, high skilled professional software Solution Company located in New Delhi founded by, PRABHAKAR MISHRA in the year 2008.The company provides vast range of services to each and every customer in reaching their respective targeted spectators and their valuable information in fix and on steady affordable price. Today, you can easily get a lot of quality services by this company on just dialing a call to the company which includes services like website designing , web application development , Application development , Maintenance , Re-engineering , Flash development , SEO , SEO Services ,  Computer Networking , Wireless Networking , Data Recovery , ERP Solution .

I've built telescope, but cant see Jupiter, Saturn rings,all stars and planets appear oval shape!?

i've 45mm dia Obj. and 9mm Dia Eyep. with FL 1000mm & 25mm,what could be the problem? as I roll my tel, these ovals also rotate!!! is this a problem of Focusing or lens? Since i use meniscus Objective??? Plz Help!!! Thanx for previous help

You are out of focus - could be the objective, could be the focus. Could be similar to the Hubble Telescope's original problem - the lens was built wrong.

Canon ixus 860 obj, ‪so baut man ein neues objektiv (Lens) ein (camera repair)‬