UNI “ae Programming Language Processors CONTENTS > Structure and Operations of Translators 2» Software Simulated Computer GSyntox, > Semantics ~ Structure 8 Virtual Computers @Binding ond Binding Time @®ata Types : Properties of Types and Objects } 2 Elementary Data Types | ] ] ] | > Structured Data Types > Abstraction : Abstract Dato Types > Encapsulation by Subprograms > Type Definition @ Storage Management.Computational Science 2-2 GATE ACADEMY PUBLICATIONS ™ [introduction [ Question 1" Ans. What do mean by programming language? {CSVTU Dec 2014] A programming language is formal constructed language designed communicate instruction to a machine particularly a computer. It is used to create programs to control the behaviour of a machine or to express algorithms. Like natural language, programming languages are also notation with which common man can communicate to the computer, ie, a programming language is a notation used to specify the data/operation or instructions and sequence which is available on a computer as understandable to the computer. Coded language used by programmers to write instructions that a computer can understand to do what the programmer wants, The most basic (called low level) computer language is the machine language that uses binary (‘1’ and ‘0’) code which a computer can execute very fast without using any translator or interpreter program. Each computer is designed to understand machine language. This language does not support the abstractions, thereby making the program development less natural and time consuming. The high level languages support the abstractions and hence the use of high level language natation makes the program development more natural, efficient and easier. Since, the programs written in high level languages are not directly understandable to computer or machine on which we want to get the task done, therefore, the system programs called compiler and interpreter serve the purpose of making the high level language program understandable to computer or machine. A notation of an algorithm and data structures are called a programming language. l Structures and Operations of Translator Question Z_ What is a language processor or language translator? ICSVTU Dec 2014] Ans. A program written in high level programming language (or written in assembly language) is called the source program. The source code cannot be executed directly by the computer. The source program must be converted into machine code to run it on the computer. Every language has its own language translator (or processor). Therefore, Language translator is defined as : The special translator system software that is used to translate the programs written in high-level language (or Assembly language) into machine code is called language processor or language translator. In other words, a translator is a computer program that translates a program written in a given programming language into a functionally equivalent program in a different computer language, without losing a functional or logical structure of the original code. These includes translation between high-level and human-readable computer languages such as C+, java and COBOL, intermediate-level languages such as java byte code, low level language such as assembler and machine code, andGATE ACADEMY PUBLICATIONS ™ 2-3 Programming Language Proc between similar levels of language on different computing platforms. The language translators (or processors) are dividing into 3 types : 1. Compiler. 2. Interpreter. 3. Assembler. Question ¥ Explain different types of translators (or processor). Ans, There are three types of translators : 1, Compiler : A compiler is a computer program that translates code written in a high level language to a lower level language, object/machine code. The most common reason for translating source code is to create an executable program. (Converting from a high level language into machine language). The C and C++ compilers are best examples for compilers. The program translated into object code successfully if it is free of errors. If there are any errors in the source code, the compiler specifies the errors at the end of compilation. The error must be removed before the compiler can successfully compile the source code. The object program can be executed a number of times without translating it again. oo compiler Executable code ‘code Fig, 2.1 Process of compiler 2. Interpreter : An interpreter program executes other programs directly, running through program code and executing it line-by-line. As it analyses every line, an interpreter is slower than running compiled code but it can take less time to interpret program code than to compile and then run it, this is very useful when prototyping and testing code. Interpreters are written for multiple platforms, this means code written once can be run immediately on different system without having to recompile for each. Examples of this include flash based web programs that will run on your PC, MAC, games console and mobile phone. An interpreter also a program that translates high-level (language) source code into executable code. However, the difference between a compiler and an interpreter is that an interpreter translates one at a time and then executes it Interpreter Executable code Get next instruction Fig. 2.2 Process of InterpreterComputati ‘ional Science 2-4 GATE ACADEMY PUBLICATIONS ™ en a ata No object code is produced, and so the program has to be interpreted each time it is to be run. If the program performs a section code 1000 times, then the section is translated into machine code 100 times. Since each line is interpreted and then executed. If there is an error in the statement, the interpreter terminates its translating process at that statement. It also display an error messages. Assembler : The language translator program that translates the program written in assembly language into machine code is called assembler. An assembler forms the translation process in similar way as compiler. But assembler is the translator program for assembly language (a low-level programming language), while a compiler is the translator program for high level programming language assembly language consists of mnemonics for machine opposes so assemblers performs a 1 : 1 translation from mnemonics to a direct instruction. For examples : LDA#4 converts to 0001001000100100 conversely; one instruction in a high level language will translate to one or more instruction at machine level. Executabl ‘Assembly process fi Fig. 2.3 Process of Assembler "interpreter It translates the statements of the source code one by one and execute L immediately. 2. | It creates an object file. | It does not create an object file. | Program execution is very fast. Program execution is slow. Translator program is not required | Translator program is required to | to translate the program each time | translate the program each time you _| you want to run the program. _| want to run the program. Itdoes not make easier to correct _| It makes easier to correct the | the mistakes in the source code. __| mistakes in the source code. | 6. | Most of the high level A few high level programming programming languages have | languages have interpreter program. | compiler program. 7 __ _ | To enable error checking before __| Performs error checking at run time. | run time, programmers have to | provide more information (e.g, | type information )GATE ACADEMY PUBLICATIONS ™ 25 Programming Language Processors [ Compilation self iakes time Good for rapid prototyping of | experimental software. | ; a 1 Write ard explain the structure of translators. ICSVTU Dec 2014] | Ans. Structure and functions of translators are : 1. A translator is a computer program that translates a program written in a given programming language into a functionally equivalent program in a different language. 2, Depending upon the translator, this may changing or simplifying the program flow. | 3. Ifa translator translates a HLL into another HLL, it is called a translator. 4 For e.g., PASCAL to C translator. ] | | FORTRAN to C translator. 4, If a translator translates HLL into an intermediate language, then it is called interpreter. 4 translates a HLL into a LLL then it is called a compiler. i 6. Ifa translator translates target machine code to source language; it is called a De- compiler. For e.g., DCC, REC (Reverse Eng. compiler). 7. lf a translator translates assembly language to machine code, it is called an assembler. For e.g., MASM, FASM. 8. Ifa translator translates machine code into assembly language, it is called a De- assembler for e.g. gdb, IDA pro. 9. Language translators convert program source code into language that the H getaputer processor understands. | Question/é | What are the operations of language translator? ICSVTU Dec 2014] Ans. A language translator is likely to perform many or all of the following operations. ] ‘There are 2 phases in the operation of translator i 1. Analysis phase : () Lexical Analysis or scanner (ii) Pre-processing (iii) Parsing or syntax analysis 2. Synthesis phase: ! ' | (iv) Semantic analysis, (v) Code optimization (vi) Code generation [ Question 7 ‘Explain the operation of translator. Or Draw the phase of compiler and explain it.Computational Science 2-6 GATE ACADEMY PUBLICATIONS ™ Source Program Lexical Analyzer Syntax Analyzer : Semantic Analyzer Tae] intermediate code generator _ Synthesis Phasd, Code Optimizer : (back end) Code generator Error Handling Target Program Fig. 2.4 Phases of compiler or structure of compiler. ‘These six phases of compiler can be grouped into two parts, as follows : 1. Analysis : In this part source program is broken into constituent pieces and creates on intermediate representation. Analysis can be done in three phases : (a) Lexical analysis (b) Syntax analysis (c) Semantic analysis 2. Synthesis : Synthesis constructs the desired target program from intermediate representation. Synthesis can be done in following three phases : (a) Intermediate code generation (b) Code optimization () Code generator Error handler module comes when some error occurs in the program like syntax error. So that, proper diagnostics could be called to locate and warn about the error message and error point, like line number at which error has occurred. Both the symbol table management and error handler co-operate and interacts with each phase of compiler. Front and Back ends of compiler : The front end of a compiler includes all analysis phases and the intermediate code generator while the back end includes code optimization and final code generation phases. The front end analyzes the source program and produces intermediate code while the back end synthesizes the target program from the intermediate code.GATE ACADEMY PUBLICATIONS ™ 2-7 Programming Language Processors It is an advantage to use the same intermediate code representation for several | different source languages and/or several different target languages. One can then | combine any front end with any back end. Modern compilers eliminate the storage 1 problems using syntax directed translation to interleave the actions of phases; the syntax analyzer directs the whole process. The lexical analyzer is a subroutine that produces just one token each time it is called by syntax analyzer and the actions of er and the intermediate code generator are built inside the syntax analyzer. Now we will study these phases of compilation process in detail as follows | semantic anal 1. Lexical Analyzer ; In a ler linear scanning. wilysis is called lexical analysis or For example : The lexical analysis the character in the assignment statement. q initial + rate * 60 Position : Would be grouped into the following tokens : {a) Identifier position. (b) The assignment symbol := | () The identifier initial (@ The + sign ‘ (e) The identifier rate (0 The sign | (g) The number 60. | The blanks separating the character of these tokens would normally be eliminated . Thi 2. Syntax Analysis : Hierarchical analysis is called parsing or syntax analysis, It evolves grouping the token in the source program into grammatical phases that are used by the compiler by synthesize the o/p. This phase is also called parsing during lexical anal during lexical analy phase is also called scanning phase. Usually the grammatical phases of the source program are represented by a parse tree. | unent identifier [epRSIOT] position [expression + [expression] | (identifier Spe expr i ] | ER identifier | [number] i Cee Cw initial + rate * 60. Fig. 2.5 Parse tree for Position:Computational Science 2-8 GATE ACADEMY PUBLICATIONS ™ 3. Semantic Analysis : The semantic analysis phase checks the source program or semantic error and gathers type information for the subsequent code generator phase. It uses the hierarchical structure determined by the syntax analysis phase to. identify the operators and operands of expression and statement. An important part of semantic analysis is type checking. Here the compiler checks that each operator has operands that are permitted by source program specification, 4, Intermediate code generator : After syntax and semantic analysis some compiler generates explicit intermediate representation of the source program. There are many types of intermediate code depending upon the language : (a) Syntax directed translation scheme. (b) Triples | (c) Quadruples } Tree Address code (TAC) (4) Indirect triples | (e) Postfix notations. These intermediate representation should have to important properties : (a) It should be easy to produce and easy to translate into the target program.GATE ACADEMY PUBLICATIONS ™ 2-9 Programming Language Processors Position := init semantic analyzer oN N id3 ito real t 60 Intermediate code generator! 1 temp! = into real (60) temp2= id3*templ temp3 = id2+temp2 idl = temp3 code optimizer templ = id3*60.0 id Code generator y MovF id3, R2 Mul F # 60.0, R1 Mov F id2, RI ADDF R2, Ri Mov F R1, id1 Fig. 2.6 Translation of a statementComputational Science 2-10 GATE ACADEMY PUBLICATIONS ™ 5. Code Optimization ; It tries to improve the intermediate code to achieve faster running mvc code. Design of good optimizer is very important part of compiler development as it decides the speed of the execution of the source program even if it is an optional is, it is not optional for compiler development compiler developer. If intermediate codes do not require optimization it is optional for intermediate code but there are many intermediate codes which required heavy amount of optimization, Let us consider few examples to show the optimization process A:=BHC+D B: = A+B+C+D Ci= BACHDtA This can be optimized as, A:=B+C+D B:= A+A C=B 6. Code Generation : It generates the target code. Memory allocations are done for each of the variable used by the program. Intermediated instructions are then translated into a sequence of m/c instruction. Symbol Table : An important part of any compiler is the construction and maintenance of a table containing all names used in the source program and their associated values. These table is called symbol table, It is searched every time a name is encounter in the source program. It may be modified if new information about an existing name is encountered whenever a new name is encountered in the source program; an insertion is made to the symbol table. Therefore a symbol table mechanism allows the user to add new entries and search exiting entries efficiently. i Error Handler : The error handler is invoked when an error is occurred in a source program. (a) It must warn the programmer by issuing a diagnostic and adjust the information being passed from phase to phase, so that each phase can proceed. (b) It is desirable that compilation error must be removed at least through the syntax analysis phase. (©) Both the table management and error handling routines interact with all phases of compiler. Question 8 What are the compiler construction tools? Explain.4 Programming Language Processors GATE ACADEMY PUBLICATIONS ™ Ans. The following is the list of some useful compiler construction tools: 1. Scanner generator tool : it automatically generates the lexical analyzer module, The lexical rules in the form of regular expressions is given as input to the scanner generated tool. Example : LEX 2. Parser generator tool : The i/p to these tool will be syntactic rule of the program language in the form of context free grammar Example : YACC (Yet another compile compiler) 3, Automatic translator system : Syntax directed definition that are associated with each node of parse tree are given as the i/p to this. It generates semantic analyzer modules. 4. Automatic code generators : It takes a collection of ruies defining the translation of each operation of the intermediate language to the target m/c code. Its maximum use of template matching technique. 5. Data flow engines : These tools automatically generates the code optimizer module. The data flow analysis will be given as i/p to this. Question 9 ‘How compilers produce machine code? Draw the translation stages. ‘Ans. Let us take an example of C++ program which is ready to be compile : # include Void main () { c=atb; Cout << ¢ << endl ; } Now, stages of translating a C++ program. yan <———— Compiler —_————— Linker +————— Loader ay pon a. Fig. 2.7 Stages of translating a C+ program to machine code.' Computational Science 2-12 GATE EMY PUBLICATIONS ™ Program input gt Program.ce ‘Preprocessor Library header | ee files [C+ Compiter eR dena YP data Uno out y result/output Fig. 2.8 An alternative view of the translation stages. Question 10 Ans. Explain the pass structure of a compiler and advantages and disadvantages of both. A pages of compiler is a collection of phases of compiler that collectively reads the source code completely and transforms it into another form depending on total no. of complete scan of the source program, compilers can be divided into two categories 1, Single pass compiler. 2. Multi pass compiler. Many language processors are capable of generating their output with just one read, a single pass, through the source code. In some cases, it is not possible, and a multi-pass process is required. In case of multi-pass compilers, every pass read the source program and o/p of previous pass, makes the transformation specified by its phases and writes o/p into an intermediate file, which may then be read by subsequent pass. Following are the important factors that affect no. of passes of compiler. 1. Structure of source language. 2. Environment in which compiler must operate. Advantages and disadvantages of both single and multi-pass compiler : 1. A single pass compiler is fast, since all the compiler code is loaded in the memory at once, It can process the source text without the overhead of the operating system having to shut-down one process and start another. Also the o/p of each pass of multi-pass compiler is stored on disk and must be read in each time the next pass starts. 2. On the other hand, a single pass compiler tend to impose some restriction upon the program ie, the constants, variables and procedures must be defined beforeGATE ACADEMY PUBLICATIONS ™ 2.13 they are used. A multi-pass compiler does not impose this type of restriction upon the user. Operation that cannot be performed because of the lack of information be differed to the next pass of t compiler when the text been traversed and needed information made available. 3. The components of a, single pass compiler are inter related much component ‘loser than the f a multi-pass compiler, This requires the entire programmer working on the project to have knowledge about the entire project. A multi-pass compiler can be decomposed into passes that can be relatively independent; hence a team of programmers can work on the project with little interaction among them. Each pass of a compiler can be regarded as a minicomputer having an i/p source written in one intermediate language and producing an op written in another intermediate language. Question 17 Write the advantages and disadvantages of compiler. Ans, Advantages of compile! 1, Source code is not included; therefore compiled code is more secure than interpreter code. Tends to produce faster code than interpreting source code. 3. Produces an executable file, and therefore the program can run without need of the source code The object program can be used whenever required without the need to of recompilation 5. Fast in execution. Disadvantages of Compiler : 1. Object code needs to be produced before a final executable file; this can be a slow process. 2, ‘The source code must be 100% correct for the executable file to be produced, 3. Debugging a program is much harder, Therefore not so good at finding errors 4, When an error is found, the whole program has to be recompiled. | Question 12 l Explain the role and functions of lexical analyzer, i Ans. Role of lexical analyzer : The lexical analyzer is the first phase of the compiler, Its main task is to read the i/p character and produce as o/p a sequence of tokens that the parser user for syntax analysis. Whenever we group phases into passes, lexical analyzer module act as a subroutine for syntax analyzer. Parser calls the lexical analyzer whenever it needs a token.Computational Science 2-14 GATE ACADEMY PUBLICATIONS ™ Token ~ Getnext token Fig. 2.9 Interaction of a lexical analyzer with parser. Main functions of lexical analyzer: 1. It removes comments and white spaces form the source program. 2. Keeps track of new line character in the source program. So that the line number can be associated with error message. 3. Macro expansion i.e., pre-processor functions are also included. 4, Reads the characters of source program and grouped them into tokens and written to the parser. Question 13 What are issues in the design of lexical analyzer? Ans. Issues in the design of lexical analyzer are : 1. Compiler efficiency is improved. A separate lexical analyzer allows us to construct a specialized and potentially more efficient procedure for the task. A large amount of time is spent to reading a source program and partitioning into tokens specialized buffering techniques for reading into characters and processing tokens can significantly speed up the performance of the compiler. 2. It will simplify the design of lexical analyser and parser both. 3. Compiler portability is enhanced i/p alphabet, other special characters and devices anamolies can be restricted to the lexical analyzer. 4, Lexical rules are simpler then syntactic rules as regular expression is simpler than CFG. Question 14 Write application of interpreter, Ans. Applications of interpreter : 1. Interpreter are frequently used to execute command languages since each operator executed in command language is usually an invocation of a complex routine such as an editor or compiler. 2. Self-modifying code can easily be implemented in an interpreted language.GATE ACADEMY PUBLICATIONS ™ 2-15 Programming Language Processors 3. Virtualization : machine code intended for one hardware architecture can be run on another using a virtual machine, which is essentially an interpreter. 4, Sandboxing : An interpreter or virtual machine is not compelled to actually execute all the instruction the source code it is processing, In particular, it can Tefuse to execute code that violates any security constraints it is operating under. Question 15 Write advantages and disadvantages of interpreter. Ans. Advantages of using an interpreter : 1. Easier to debug (check errors) than compiler since it stops when it encounters an error. 2. Easier to create multiplatform code; as each different platform would have an interpreter to run the same code. 3. Useful for prototyping software and testing basic program logic. 4, Ifan error is deducted there is no need to retranslate the whole program. Disadvantages of using an interpreter : 1. No object code is produced, so a translation has to be done every time the program is running. 2. Source code is required for the program to be executed and this source code can be read making it insecure. 3. Interpreter are generally slower than compiled programs due to the per-line translation method. 4. For the program to run, the interpreter must be present. Question 16 Explain assembler. How it works? Ans. An assembler is a program that takes basic computer instruction and converts them into a pattern of bits that the computers processors can use to perform its basic operations. These instructions called as assembler language or assembly language. Assembly language is a low-level programming language which is converted into executable machine code by a utility program referred to as an assembler, the conversion process is referred to as assembly or assembling the code. Working : 1. Most computers come with a specified set of very basic instructions that correspond to the basic machine operations that the computer can perform. For example, a Load instruction causes the processor to move a string of bits from a location in the processor's memory to a special holding place called a register. Assuming the processors has at least eight registers, each numbered, the following instruction would move the value (string of bits of a certain length) at memory location 3000 into the holding place called register 8 : L 8, 3000Computational Science 2-16 GATE ACADEMY PUBLICATIONS ™ 2. The programmer can write a program using a sequence of these assen j instructions. s, known as th 3. This sequence of assembler instructi program, is then specified to the assembler program when 0's and 1's of a g The assembler program takes each p generates a corresponding bit stream or pattern (a serie: length). i 5. The output of the assembler program is called the object code or object program relative to the input source program. The sequence of 0's and 1's that constitute the object program is sometimes called machine code. ven 6. The object program can be run (or executed) whenever desi In the earliest computers, programmers actually wrote the programs in machine code, but assembler languages or instruction sets were soon developed to speed up programming. Today, assembler programming is used only where very efficient control over processor operations is needed. A newer idea in program preparation and portability is the concept of a virtual machine. For example : Using the java programing language, language statement are compil yte code that can be run by a ic form of machine language known as into a gene virtual machine, a kind of theoretical m/c that approximates most computer operations, | Question 47 re] Write the applications, advantages and disadvantages of assembler, || Ans. Application : 1. Assemblers can be used to generate blocks of data, with no high level language overhead, from formatted and commented source code, to be used by other code. v ‘Assembly language is valuable in reverse engineering. Relatively low-level languages, such as c, allow the programmer to embed assembly language directly in the source code. 4. Assembly language is typically used in a systems boot code, the low-level code that initializes and tests the system hardware prior to booting the operating system and is often stored in ROM. & Advantages of using an assembler : 1. Very fast in translating assembly language to machine code as 1 to 1 relationship. é 2. Assembly code is often very efficient (and therefore fast) because it is a low-level 3 language. 3, Assembly code is fairly easy to understand due to the use of English-like mnemonics. ee scien2-47 Programming Language Processo ‘ages of using an assembler : sembly language is written for a certain instruction set and/or processor. bl imised for the hardware it’s designed for, meaning often incompatible with different hardware. y code is needed to do relatively simple tasks and complex e lots of progr: ——— = [ Question 18 eS Le Define Lit ‘Ans. Linker: Both compilers and assemblers often rely on a program called linker which collects code separately compiled or assembled in different object files into a file that is tly executable. In this way a distinction can be made between object code- machine code that has not yet been linked and executable machine code. A linker also am to the code for standard library functions and resources nputer such as memory allocators and i/o devic connects an objects prog ied by oper ing system of Question 19 ES Define load Me ees] ang. Loader is rarely used as an actual separate program; it is used in conjunction w the code generated by compiler, assembler or linker is not yet 1 fixed and ready to execute, but their principal memory reference are all made relative to an undetermined starting location that can be anywhere in m/r. such code is said to be relocatable and a loader will resolve all relocatable addresses relative toa given base or starting addresses. linker. General [ Question 20 | [What loaded subprogram? {CSVTU Dec2013]_| Ans. Ano subprogram is a subprogram that has the same (function) name for another subprogram in the same referencing environment. The overloaded subprograms may differ in the number, type or order of its parameters. Java , C++ and C# provides the features of subprogram is called, java or C++ compiler first checks the rloade ubprograms name and then the number and type of parameters are analyzed to decide whi ion of the overloaded subprograms must be chosen for execution. This process is also known as ‘polymorphism’. The return Lype of subprogram has no effect on subprogram overloading where as is used to differentiate between the calls in ADA. Hence, two overloaded functions in ADA can have the same parameter profile with different return values. For example : Following four functions can be overloaded depended on arguments int SUM (int a, int b); I void SUM (int a, float b); a void SUM (inta, intb, into); 0 i void SUM (float x, int y); VvComputational Science 2-18 GATE ACADEMY PUBLICATIONS ™ When four calls are made for SUM function ; SUM (10, 20, 30); calls III* function. SUM 6, 20); calls I* function. SUM (105, 5); calls IV® function. SUM (8, 2.5); calls I function. [Syntax Question 21 Define syntax and explain it. Ans. The syntax of a programming language describes the structure of a program without any considerations of their meaning. In computer science, the syntax of a computer language is the set of rules that defines the combination of symbols that are consided to be correctly structured document or fragment in that language. Levels of syntax: Computer language syntax is generally distinguished into 3 levels, 1, Words : The lexical level, determining how characters form tokens. 2. Phrases : The grammar level, narrowly speaking, determining how tokens form phrases; 3. Context : Determining what objects or variables names refer to, if types are valid, etc. Question 22 Discuss the key criteria concerning syntax. Ans. The key criteria concerning syntax are:- 1. Readability : A program is considered readable if the algorithm and data are apparent by inspection. Write-ability : Ease of writing the program. Verifiability : Ability to prove program correctness (very difficult issue) Translatability : Eases of translating the program into executable form. Lack of ambiguity : the syntax should provide for ease of avoiding ambiguous structures. [Semantics Question 23 ‘What is semantics? Explain its approaches. Or Explain the basic concept of denotational semantics. ‘Ans. Semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages. It does so by evaluating the meaning of syntactically legal strings defined by a specific programming language, showing the computation PPE DPGATE ACADEMY PUBLICATIONS ™ 2-19 ing Language Processors involved. In such a case that the evaluation would be of syntactically illegal strings, the result would be non-computation. Semantics describes the processes a computer follows when executing a program in that specific language. This can be shown by describing the relationship between the input and output of a program, or an explanation of how the program will execute on a certain platform, hence creating a model of computation. There are 5 ways to define the semantics i.e,, operational, axiomatic, denotation, action and behavioural semantics. Approaches : There are 5 approaches to formal semantics, but the three major semantic model are : 1. Denotational Semantics : Denotational semantics is the most rigorous , widely known method for describing the meaning of programs. It is based on recursively function theory. The fundamental concept of denotational semantics is to define for each language entity both a mathematical object and a function that maps instances of that entity onto instances of the mathematical object. Where by each phrase in the language is interpreted as a denotation, ie, a conceptual meaning that can be thought of abstractly. Such denotations are often mathematical objects inhabiting a mathematical space, but it is not a requirement that they should be so. As a practical necessity, denotations are described using some form of mathematical notation, which can in turn be formalized as a denotational Meta language for example, Denotational semantics of functional languages often translate the language in to domain theory. Denotational semantic description can also serve as compositional translations form a programming language into the denotational Meta language and used as a basis for designing compilers. 2. Operational semantics : Where by the execution of the language is described directly (rather than by translation). Operational semantics loosely corresponds to interpretation although again the “implementation language” of the interpreter is generally a mathematical formalism. Operational semantics may define an abstract machine (such as the SECD machine), and give meaning to phrases by describing the transitions they induce on states of the machine. Alternatively, as | with the pure lambda calculus, operational semantics can be defined via syntactic transformations on phrases of the language itself 3. Axiomatic semantics : Where by one gives meaning to phrases by describing logical axioms that apply to them. Axiomatic makes no distinction between a phrases meaning and the logical formulas that describe it, it’s meaning is exactly what can be proven about it in some logic. The canonical example of axiomatic semantics is Hoare logic. The idea in axiomatic semantics is to define meaning in terms of logical specifications that program satisfy. It is based on mathematical logic.Computational Science 2-20 GATE ACADEMY PUBLICATIONS ™ Question 24 Write the major advantages of axiomatic semantics. Ans. The major advantages of axiomatic semantics are as follows : mn 1. It can be used to derive the final condition after the execution of a prog without actually executing it. This property can facilitate, in a limited way, wecking program correctness without executing the program. The idea is to derive the final condition Fé derived using axiomatic semantics and compare it with the intended condition F! using axiomatic semantics, and compare it with intended condition F', If the final derived condition FC C_ Fi, then the program is correct and if the final derived condition F*C_ Fl and F'C Fe, then the program is both complete and correct. While the scheme works for smaller programs, becomes computationally prohibitive for the bigger programs due to (a) the computational cost of matching the equivalent Boolean expressions, (b) the overhead of identifying that a condition expressed by a Boolean expression is subsumed by another Boolean expression, and (c) the overhead of identifying invariant conditions. 2. By knowing the intended final condition F', a program can be constructed stepwise by reasoning in backward manner: Postconditions and the effect of program constructs are used to derive progressively the preconditions that are true. These preconditions become postconditions for the previous statements. By repeating this process of backward heuristic reasoning, a program can be constructed stepwise. Question 25 Write the similarities and difference between the denotational and operational semantics, Or In what fundamental way do operational semantic and denotational semantic differ? _| Ans. The difference between operational semantics and denotational semantics is that operational semantics describes the changes in a computational state as an effect of abstract instructional in an abstract machine, while denotational semantics uses abstract syntax trees and composition of semantics rules expressed as mathematical functions to derive the meaning of a sentence. There is no concepts of computational states and abstract machines in denotational semantics. There are some similarities in denotational semantics and operational semantics : 1. Denotational semantics also uses the environment and store like operational semantics does. 2. Both operational semantics and denotational semantics use abstractions in their definitions.GATE ACADEMY PUBLICATIONS ™ 2-24 Programming Language Processors Question 26 plain what the preconditions and post-conditions of a given statement mean in ICSVTU Dec 2013] antics, b axiomatic sei Axiomatic s ased on mat upor licate calculus first explained by € Boolean expressions to define a computational state at an instant of computation. When axiomatic semantics is used to specify formally the semantics of a statement, the meaning is defined by the statement effect on assertions about the data being processed by the statement. The logical expressions are called predicates, or assertions. An assertion immediately preceding a program statement describes the constraints on the program variables at that point in the program. An assertion immediately following a statement describes the new constraints on those variables (and possibly others) after execution of the statement, These assertions are called the precondition and post-condition, respectively, of the statement. For two adjacent statements, the post-condition of the condition of the second. Developing an axiomatic description or the program have both a \.R. Hoare, us first serves as the pre of of a given program requires that every statement i recondition and a post-condition. In the following, we examine assertions from the point of view that precondition st-condition, although it is possible to for statements are computed from given p e sense. We assume all variables are integer type. As a lowing assignment statement and post-condition: consider these in the oppo: simple example, consider the f SUM = 2* x#1 {SUM>1} Precondition and post condition assertions are presented in braces to distinguish them from program statements. One possible precondition for this statement is (x>10} In axiomatic semantics, the meaning of a specific kind of statement is defined by itatement of that kind, along with its ly the effect of executing the the process of computing a precondition from 2 post condition. In effect, such a process spe: statement, in terms of logic expressions. The execution of the statement alters the computation state by changing the Boolean expression. The meaning of a statement is derived by the difference between post-condition and precondition, A precondition is the Boolean expression immediately before executing a statement, and a post- condition is the Boolean expression that will become true immediately after executing the statement. precis aestion 27 Define syntax and semantics. Ans. Semantics: Semantics are used to explain the meaning of the abstractions to program developers, language designers and compiler developers. There are 5 ways to describe the semantics, but the first 3 are major semantics. ie., operational semantics, axiomatic semantic, Denotation semantics, action semantics and behavioural semantics. ‘r Computational Science 2-22 GATE ACADEMY PUBLICATIONS ™ Syntax : The syntax of a programming language describes the structure of a programs without any considerations of their meaning. The syntax of a computer language is the set of rules that define the combinations of symbols that are considered to be a correctly structured document or fragment in that language. It has 3 level ie. words, phrases and context. Question 23 Define action semantics. Ams. Action semantics integrates the advantages of denotational semantics, axiomatic semantics and operational semantics to explain the meaning of control and data abstractions using rules in natural english language. These rules are called actions. The major advantages of action semantics is that it defines the meanings of realistic programming, Language abstractions in a comprehensible way. Action semantics borrows the ideas of context free grammars to derive abstract syntax tree, and then use semantics equations from denotational semantics. There are 3 major components of action semantics: ie., action, data and yielders. Question 29 What is abstract syntax tree? ‘Ans. A parse tree made out of abstract system rules gives an abstract syntax tree. An abstract syntax tree is free of all the nonterminal symbols in the concrete syntax rules that are not in the abstract syntax rules. The expressions are rooted at the operators. For example, the abstract syntax tree for the expression “x+3"4”is given below. —_ _ Fig. 2.10 Abstract syntax tree for the expression “x+3*4.” Abstract syntax tree are useful in understanding the language constructs in programming languages, as they hide unnecessary details. Abstract syntax trees have also been used in program analysis. [Lvirtual Computers Question 3a What is a virtual computer? Explain. ICSVTU May 2014, Dec 2014] Ans. Virtual computing allows computer users remote access to software applications and processes when they need it. Users gain access via the Internet through a wireless or network server. For a fee, users can boost their computers’ capabilities, size, |GATE ACADEMY PUBLICATIONS 2-23 Programming Language Processors een sng Language Processors performance, processes and/or software applications whenever they need it, Virtual computing makes one computer act and perform like many computers. Through virtual computing providers, users can download and use more than one operating system and perform a multitude of functions at the same time through a single mouse click and receive all the benefits of additional programs and hardware without having to purchase or install them on their own computer. Executives can check their ike classes from home and managers can company e-mail on the road, students can ta keep up with documents stored on internal servers from anywhere in the world. This real-time technology offers : 1. Operating and utility systems 2. Storage 3. Memory 4. Software 5. Allocation and reassignment of input/output and other processes 6. Data backup 7. Automated problem solving and troubleshooting 8. Tools for monitoring and managing systems ~ Users can access software applications for a single computer or an entire network because of the ability to select only what you need when you need it. They also can save or back up data and text documents to a virtual server (thus freeing space on individual computers) and reallocate or assign different processes to the virtual environment. This enables computers to operate at optimal speeds, Virtual computing initially began as a method of borrowing space or storage for computer systems, but it's since grown significantly, offering data and software applications, as well as operating and utility systems. The corporate environment most commonly uses it, where IT system managers run multiple applications on several servers Virtual computing is increasing possibilities and performance in the world of information technology (IT): increased storage space, more software applications, performance and troubleshooting solutions, as well as data backup. Layers of virtual computer : 4 Input data | | Output results ¥ Web Application Computer _(Implemented on HTML web pages) Web Virtual Computer (Browser program implemented in ¢ or java) C Virtual Computer ] (Implemented by runtime library _ loaded with compiled prograi routingGATE ACADEMY PUBLICAT J Computational Science Operating System Virtual Compater | lang. prog? (Implemented by machin executed by ‘Actual Hardware Computer ted by physical devic ual Computers cali Question ay Write the advantages of virtual computing. ICSVTU May 2014, Dec 2014) ‘Ans. Advantages of virtual computing 1. Virtual computing provi processes to a virtual environment, processes and applications. You can achieve faster system speeds due to freeing up the system, memory and 2. It's also flexible. You have the abi having to install, configure and store it 0: increased efficiency addition, techs ne at any time. You have the satw flexibility to chan Automated troubleshooting, diagnosing and « ware and software are available as needed. Virtual computing programs automatically review your computer's speed and efficiency and reallocate processes or repait programs as. needed. 4. Virtual computing users can run more than one operating system on one PC at the same time. For instance, through virtual computing, you can run Windows on a war computer has the capability of becoming m: 2 Mac computer. Effectively, y computers. 5, There's a reduction in cooling and power costs, as well. Virtual computing eliminates the need to operate multiple computers and servers, which saves energy. 6. Virtual files are two small files, mak: Question 32 Write the disadvantages of virtual ‘Ans. Disadvantages of virtual comput 1. While virtual computing does er applications, it can also be time consuming and laborious for some IY staff. Even though the applications are remote, managers must still track and monitor files, applications, data and storage. Virtual computing can increase their workload because now they have more places to track. es can be stored on one or macl copying 2 d fast process, _ rm more tasks and run more ble servers to per |GATE ACADEMY PUBLICATIONS ™ Programming Language Processors 2. Security itor and addressed to prevent the loss or theft of data in a virtual or remote environment. Transfer of information and the n interact remotely must also be monitored continual but for many organizations, virtual nd firewall issues m d for F computing doesn't cut costs or th IT staff. 18 should charge for each use of allows 0 aputer could be runing several software simultaneously. There have been oftware. To address that Other cost issues include what v ion. Be to run 1 computer software se virt the same app of the sam regarding paying ue, providers are exploring a meter process, which would provide users a ge them for any overaj many ar lly for the same s repeated nd c specific amount of uses tures of virtual computer ICSVTU May 20141 Ans, Features: le architecture : Uses the files for configuration and resource files, 1. Basic 2. Networking: Virtual machine control options : options fc as starting, stopping, shutting dow: saving state. 4, Disk features Jo and differen machines and physical machines. orking b/w vi ¢ ‘ontrolling virtual machines, such a » application is infront formed nd are avail | Explain the hierarchies of virtual machin 3 to create ‘Ans, The virtual machine that a programmer us from a hierarchy of virtual computers 1. At the bottorn, there must of course an actual hardware computer. This H/w formed by layers of software (or microprogram) computer is successively .t into a virtual machine that may be radically different. 2. The second level of virtua! computer (or the third if a micro program forms the second level) is usually defi ction of routines known as the operating systems. 3. The operating system provides simulation for a no. of new operations and data structures that are not directly provided by the hardware. For eg,, external file structure. 4, The operating system also deletes certain hardware primitives from the operating system define virtual computer so that they are not accessible to the operating primitives for I/P, O/P multiprogramming and compress coll system users. (For e.g, hardwa multiprocessing). The operating system defined virtual computers is usually that which is available to the implementer of a HLL. The language implementer provides new layer software that runs on the operating system define computer and simulates the n of virtual computer for the HLL. operatiComputational Scienc 2-26 GATE ACADEMY PUBLICATIONS ™ 6. The implementer also provides a translator for translating user programs into the machine language of the language defined virtual computer. 7. C language virtual machine created by the C language compiler, programmer build a program called a web browser using the ‘C’ language. This browser creates the web virtual machine which can process the basic data structure of the www, the hyperlinks (VRLS), to visit the websites, the basic html language for displaying webpages and the ability to run inte! browser. 8. At the highest level in this particular hierarchy is the web applications computer. The web developer uses the features of the thines (HTML, applets, etc.) ive programs for users of that to provide services to users of that web page. [ Binding and Binding Time Question a5 Los Define binding and binding time. ICSVTU May 2014] Binding : A binding in a program is an association of an attribute with a program component such as an identifier or a symbol. For example the data type of the value of a variable is an attribute that is associated with the variable name. Binding Time : The binding time for an attribute is the time at which the binding occurs, for example, in C the binding time for a variable type is when the program is compiled (because the type cannot be changed without changing and recompiling the program), but the value of the variable is not bound until the program executes (that is, the value of the variable can change during execution). Ans. Question 36 Explain the classes of binding time. There is no simple categorization of various types of bindings; a few main binding times may be distinguished if we recall our basic assumptions that the processing of programs, regardless of the language always involves a translations step followed by execution of the translated program, There are 4 types of binding time : 1. Execution time (run time). 2. Translation time (compile time). 3. Language implementation time. 4. Language definition time. 1. Execution time/Runtime : Many bindings are performed during program executions. These includes binding of variables to their values as well as the binding of variable to particular storage location. The important sub categories may distinguished : (i) On entry to a subprogram or block : In most languages, bindings are restricted to occur only at the time of entry to a subprogranf or block during execution. For'e.g., in C and C++, binding of formal to actual parameters and the binding of formal parameters to particular storage locations may occur only on entry to a subprogram.GATE ACADEMY PUBLICATIONS ™ 2-27 Programming Language Processors ena LTOgTamming Language Processors Gi) At arbitrary points during execution : Some binding may occur at any point during executions of a program. The most imp. eg,, is binding of variables to values through assignment. Whereas some languages like LISP (List programming) and ML permits the binding of names to storages location to also occur at arbitrary print in the program. 2, Translation time/compile time : Three different classes of translation time jinding may be distinguished : (Binding chosen by the programmer : In writing a program, the programmer makes many decisions regarding choice of variable names, types, program structures and so on that represents binding during translations. The language translator makes use of these bindings to determine the final form of the object program. (ii) Binding chosen by the translator ; Some bindings are chosen by the language translator without direct programmer specifications. For eg., the relative locations of a data object is the storage allocated for a procedure is generally handled without knowledge or interventions by the programmer. (iii) Binding chosen by the loader : A program usually ¢ of several sub programs that must be merged into a single executable program. The translator typically binds variables, To addresses within the storage designated for each sub program. However, this storage must be allocated actual addresses with in the physical computer that will execute the program. This occurs during load time (also called link time). 3. Language implementation time : Some aspects of a language definition may be the same for all programs that are run using a particular implementations of the language but they may vary between implementations. For e.g., after the details associated with the representation of the numbers and arithmetic operations are determined by the way that arithmetic is done in the under-lined hardware computer. A program written in a language that uses a feature whose definition has been fixed at implementation time will not necessarily run on another implementation of the same language. 4, Language definition time : Most of the structure of program language is fixed at the time the language is defined in the sense of specification of the alternative available to a programmers when writing a program. For eg, the possible alternative statement forms, data structure types, program structure and so on are all often found at language definition time. For e.g,, suppose X = X+10 (i) Set of types for variable x. (ii) Types of variable X. (iii) Set of possible values for variable X. (iv) Value of variable X (v) Representation of the constant. (vi) Properties of the operator (+).Computational Science 2-28 GATE ACADEMY PUBLICATIONS ™ Question 37 ‘| gE What is binding? Explain its types also. Ans. Binding : Binding refers to the linking between an attribute and an entit an operations and symbols. A data object participates in various binding du time. The attributes of a data object is invariant but the binding may change. The time at which binding takes place is known as binding time. The various types of binding are of the forms : 1. Binding between data object and a set of values that data object may take. 2. Binding between storage location in memory and the data object. 3. Binding resulting from an assignment operation. X= X+10; 4. Binding to one or more names by which the object may be referenced during execution. This is set up by declaration and changed by functions 5. Binding of one data object to its components. Data object Data value ing {1001010 Fig, 2.12 Binding of data object and data value. Binding are of two types : 1. Static Binding 2. Dynamic Binding. 1. Static binding : Static binding is done at compile time. Variables are declared of two types an explicit declaration in program that specifies the variable name and its types and an implicit declaration in which variables are declared through default conventions. Both declarations create static binding. Static binding is fixed during the execution of programs. The value of data object declared is fixed during static binding. Alll errors, such as type mismatch, declaration syntax ertors are comes out during compile time. Static binding includes declaration of values to the variables, passing actual values to formal values etc. 2. Dynamic binding : In dynamic binding the binding is done at runtime. Dynamic binding is fixed during program execution. In dynamic binding the type is not specified by a declaration statement. The type is assigned value by an assignment statement and when assignment statement executes then the binding take place. ‘The type of the value, variable or expression is bounded during execution. Question 33 ‘What is early binding and late binding? Ans, 1. Early binding : Early binding always occurs in the polymorphism when we pass the reference of a subclass into the pointer object of base class, then the member function are new to be override when we executes the program, then compiler knows this thing, This is called an early binding and the compiler will execute theGATE ACADEMY PUBLICATIONS ™ 9 Programming Language Processors member functions of base class and this will newer override the body of the sub class member functions. This is known as early binding. 2, Late binding ; In the late binding the compiler knows about the code mean what the code will do all the code is understand at the time of executions. This is called late binding. Late binding is performed by using the virtual functions, virtual means the functions must be override. When the compiler find out the word virtual at the time of the execution then this will override the body of function of base class with the function of subclass. | Software Simulated Computer Question 39 What is software simulated computer? Ans. Software simulation : (Software interpretation) It is possible to write a software simulation, of the equivalent firmware implementation of a language. 1. Therefore the software simulation will directly execute a given program. 2. As these are software implementations, they are almost always slower than translated programs (JVM) In practice, most languages combine these techniques : 1. First a language is translated into a simpler form. 2. Then the simpler form is combined with a number of runtime support routines, before being executed, Simulation may have to interpret each line many times, but the original code may be examined, It tends to be used for languages that are based around more abstract concepts than the physical machine. L Structure Question 40 Define structure. Ans, Structure have defined boundaries with in which : [Data Types” 1. Each element is physically or functionally connected to other elements. 2. The elements themselves and their interrelationships are taken to be either fixed or changing only occasionally or slowly. It defines construction or frame-work of identifiabie elements (components, entities, factors, members, parts, steps, etc.) which gives forms and stability and resists stresses and strains. Question 44 What is data type? [CSVTU May 2014, Dec 2014]30 GATE ACADEMY PUBLICATIONS ™ Computational Science Ans. The data type of a value (or variable in some contexts) is an attributes that tells what kind of data that value can have, data types define particular characteristics of data used in software programs and inform the compilers about the predefined attributes required by specific variables or associated data objects. The most common data types include Boolean, integer, floating point number, character and alphanumeric string. There are other data types in programming languages, each serving a specific function and storing data in a particular way. Question 42 What is a data type? Discuss the classes of data types. [CSVTU Dec 2014] Ans. A data type in a programming language is a set of data with values having predefined characteristics. Example of data types are : 1. Integer 2. Floating point 3. Unit number 4, Character 5. String 6. Pointer Usually, a limited number of such data types come built into a language. The language usually specifies the range of values for a given data type, how the values are processed by the computer, and how they are stored. Most programming languages also allow the programmer to define additional data types, usually by combining multiple elements of other types and defining the valid operations of the new data type. For example, a programmer might create a new data type named complex number that would include real and imaginary parts. A data type also represents a constraint placed upon the interpretation of data in a type system. The type system uses data type information to check correctness of computer programs that access or manipulate the data. Classes of data types 1. Primitive data types: (i) Machine data types (i) Boolean type (ai) Numeric types 2. Composite types : (i) Enumerations (ii) String and text types 3. Other types () Pointers and references (ii) Function types 4. Abstract data types 5. Utility types. Explanation : 1. Primitive data types : (a) Machine data types : Machine data types need to be. exposed or made available in systems or low level programming languages, allowing fine grained control over hardware. In higher level programming, machine data types are often hidden or abstracted as an implementation detail that wouldGATE ACADEMY PUBLICATIONS ™ 4 Prog Language Processors rang Language Processors render code less portable if exposed. For instance, a generic numeric type might be supplied instead of integers of some specific bit-width. (b) Boolean type : The Boolean type represents the value true and false. Although only two values are possible, they are rarely implemented as a single binary digit for efficiency reasons. Many programing languages do not have an explicit Boolean type, instead interpreting (for instance) O(zero) as false and other values as true. (o) Numeric types : Such as, (i) The integer data types, or whole numbers. May be subtyped according to their ability to certain negative values. (e.g., unsigned in C and C+). May also have a small number of predefined subtypes (such as short and long, in C/C++); or allows users to freely define sub-ranges such as 1....12 (eg,, Pascal/Ada) (ii) Floating point data types, sometimes called reals, contain fractional | values. They usually have predefined limits on both their maximum | values and their precision, These are often represented as decimal | numbers. (iii) Fixed point data types are convenient for representing monetary values, They are often implemented as integers, leading to predefined limits. (iv) Big num or arbitrary precision numeric types lack predefined limits. 2, Composite types : Composite types are derived from more than one primitive type. This can be done in a number of ways. The ways they are combined are called data structures. Composing a primitive type into a compound type generally results in a new type e.g., array of integer is a different type to integer. (a) Enumeration : It has values which are different from each other and which can be compared and assigned, but which do not necessarily have any Particular concrete representation in the computer's memory; compiler and interpreters can represent them arbitrarily. Some implementation allows Programmers to assign integer values to the enumeration values. (b) String and text types : characters and string types can have different subtypes according to the required character width. Strings to may be either stretch to fit or of fixed size, even in the same programming language. They may also be subtyped by their maximum size, 3. Other types : Types can be based on, or derived from, the basic types explained above. In some languages, such as C, functions have a type derived from the type of their return value, Pointers and references : Pointers are often stored in a format similar to an integer, however, attempting to dereferences or “lookup” a pointer whose value Was never a valid memory address would cause a program to crash.Computational Science 2-32 GATE ACADEMY PUBLICATIONS ™ 4. Abstract data types : Any type that does not specify an implementation is an abstract data type. Abstract types can be handled by code that does not know or care what underlying types are contained in them. 5. Utility types : For convenience, high-level languages may supply ready-made real world data types, for instance times, dates and monetary values and memory, even where the language allows them to be built from primitive types. Question 43 Explain the role of data type. Ans. Data type of variable determines the range of values the variable can have and the set of operation that are defined for values of the type. For example : Type Integer have a value range of — 32768 to 32767 and arithmetic operations for addition, subtraction, division, multiplication, along with some library functions for operations. Every programming language deals with some commonly known data types like class of arrays, integers or files and operations for manipulating them. 1. Specification of a data type includes : (a) A basic attributes that distinguish one data object to another. (b) The value that the data object of that type contains. (c) The operations that performs on data objects of that type. 2. Implementation of data type includes : (a) The memory representation of the data objects of the data type in the storage during execution. () Algorithms are designed to perform operations on the data objects. By using algorithms or procedure we can implement the data objects. Question 44 What is data object and data value? Ans, Data object is a runtime collection of one or more pieces of data in a digital computer. During execution many data objects of different types are created and after execution they are destroyed. A data object is of two types : 1. System defined data objects : These data objects are created automatically as needed during program execution and programmer have no interfere. 2. Programmer defined data objects ; Programmer defined data objects are created by programmer. Programmer also manipulates through statements in the program. Programmer defined data objects are constant, arrays, variables etc, Data object have many attributes. One of them is data type. The attributes determine the number and type of values that the data object may have and organization of the values. A data value might be a single number, character or a pointer to another data object. A data value is generally represents in the form of bits in the virtual computer storage. A data object is generally represented asGATE ACADEMY PUBLICATIONS ™ 2-33 Programming Language Processors storage in the computer memory. Data object is a place where the data value is stored. Data value is represented by a pattern of Bits. 1000-<-——Address Data value , Data object Variable Fig. 2.13 Simple representation of data object, data value, and address where the data value is stored. || Abstraction : Abstract Data Types ‘What is abstraction? Explain it with suitable example. ICSVTU Dec 2014] Ans. An abstraction is a technique for managing complexity of computer systems. It works by establishing a level of complexity on which a person interacts with the system, suppressing the more complex details below the current level. The programmer works with an idealized interface (usually well defined) and can add additional levels of functionality that would otherwise be too complex to handle. For example, a programmer writing code that in t be the way numbers are represented in the underlying hardware (e.g, whether they are 16 bit or 32 bit integers) and where those details have been suppressed it can be said that they were abstracted away, leaving simply numbers with which the programmer can work. In addition, a task of sending an email message across continents would be extremely complex if you start with a piece of optic cable and basic hardware components. By using layers of complexity that have been created to abstract away the physical cables, network layout and presenting the programmer with a virtual data channel, this task is manageable. For example ; Engineers have to work together in teams to build complex systems, whether software, hardware, cars, planes or bridges. This complexity is a major source of engineering cost and errors. With the wrong engineering approach, every team member can end up needing to understand every other team member's work, which means the total effort requires to build a system of size n is proportional to 11. The solution to complexity is abstraction, also known as information hiding. Abstraction is simply the removal of unnecessary detail. The idea is that to design a part of a | complex system, you must identify what about that part others must know in order to design their parts, and what details you can hide. The part others must know is the abstraction. Example (using Java) : A Car has Engine, wheels and many other parts. When we write all the properties of the Car, Engine, and wheel in a single class, it would look this way :Computational Science 2-34 GATE ACADEMY PUBLICATIONS ™ pul class Car int price; String name; String color; int engineCapacity; int engineHorsePower; String wheelName; int wheelPrice; void move() { //move forward } void rotate() { {Wheels method } void internalCombustion() { J/Engine Method In the above example, the attributes of wheel and engine are added to the Car type. As per the programming, this will not create any kind of issues. But when it comes to maintenance of the application, this becomes more complex. Applying the abstraction with composition, the above example can be modified as given below : fpublic class Car Engine engin Wheel whee! int price; String name; String color; | void move() { /Imove forward }GATE ACADEMY PUBLI' 5 Programming Language Processors jublic class Engine int engineCapacity; int engineHorsePower; void internalCombustion( { 1 [engine Method | po ublic class Wheel String wheeiName; int wheetPrice; void rotate() { {Wheels method } Here, the attributes and methods related to the engine and wheel are moved to the respective classes. Engine and Wheel are referred from the Car type. Whenever an instance of Car is created, both Engine and Wheel will be available for the Car and when there are changes to these Types(Engine and Wheel), changes will only be confined to these classes and will not affect the Car class. Two kinds of abstraction in programming languages are process abstraction and | data abstraction. The concept of process abstraction is one of the oldest. All sub programs are process abstractions because they provide a way for a program to specify that some process is to be done, without providing the details of how it to be done. Process abstraction is a crucial to programming process. All sub-programs including concurrent sub-programs and exception handlers, are process abstraction. ‘An abstract data type or data abstraction is simply an encapsulation that includes only the data representation of one specific data type and the sub-programs that provide the operations for that type. Object-oriented programming is an outgrowth of the use of data abstraction. Question 46 Write the advantages of abstraction. ICSVTU Dec 2014] Ans. Advantages of Abstraction : 1. Abstraction in Object Oriented Programming helps to hide the irrelevant details of an object. 2. By using abstraction, we can separate the things that can be grouped to another type.Computational Science TE ACADEMY PUBLICATIONS ™ 3. Frequently changing properties and methods can be grouped to a separate type so that the main type need not undergo changes. This adds strength to the OOAD (object oriented analysis and design) principle -"Code should be open for Extension but closed for Modification". 4. Applying Abstraction during the design and domain modeling, helps a lot in design the system which is flexible and maintainable. 5. Simplifies the representation of the domain models. 6. It helps to reduce the complexity and also improves the maintainability of the system. 7. When combined with the concepts of the Encapsulation and Polymorphism, Abstraction gives more power to the Object oriented programming languages. Question 47 What is an abstract data types? Write its properties. What is the reason for using ADT'S? ‘An abstract data type is an encapsulation that includes only the data representation of one specific data type and the sub-program that provides the operations for that type. Am instance of an abstract data type is calls object. Through access control, unnecessary details of the type can be hidden from units outside the encapsulation that use the type. Program units that use an abstract data type can declare variables of that type, even though the actual representation is hidden from them. Object oriented programming is an outgrowth of the use of data abstraction in software development and data abstraction is one of its most important components. The goal of data abstraction is to allow programs to define data types. Reason for using ADT’s : One of the main reason for using ADT’s is that it allows the capabilities (operations) that are needed to be separated from any implementation of the ADT data and operations. A programmer who uses ADT’s need not to be concerned about the implementation of an ADT in order to use it, unless there is a choice of implementations and efficiency considerations are an important aspect of the problem solution. Properties of an abstract data types (ADT) : An abstract data type (ADT) is characterized by the following properties : 1. Itexports a type called domain. 2. Itexports a set of operations. This set is called interface. 3. Operations of interface are the one and only access mechanism to the type’s data structure. 4. Axioms and preconditions define the application domain of the type.GATE ACADEMY PUBLICATIONS ™ 2-37 Programming Language Processors een heen PORTEmMINg Language Processors Data types | | Interface : Operations Fig, 2.14 An Abstract Data type (ADT) Explaination of properties : 1. The first property allows the creation of more than one instance of an ADT object. 2. The second property defines the only possible operations on the ADT object. 3. The third property prevents using other operations different from the ones defined in the interface. 4. Finally the application domain is defined by the semantical meaning of provided operations. Axioms and preconditions include statements such as : (a) The denominator of fraction is different from zero. (b) An empty list is a list. (0) Let 1 = (ds, ds; ds....dx) be a list then Lappend (4M) Results in 1 = (ds, ds, (d) The 1* element of a list can only be deleted if the list is not empty. Question 48 Explain the types of Abstract data types. Ans. There are two types of abstract data types i.e. : 1. User-defined abstract data types. 2. Parameterized or Generic abstract data types. 1. User defined abstract data types : {a) The concept of user-defined abstract data type is relatively recent. (b) They should provide a type definition that allows program units to declare | variables of the type but hides the representation of these variables. | (c) An abstract type is a user defined data types that satisfies the following two conditions : (i) The representation or definition, of the type and the operations are contained in a single syntactic unit.’ Computational Science 2-38 GATE ACADEMY PUBLICATIONS ™ (i) ‘The representation of objects of the type is hidden from the program units that use these objects, so the only operations possible are those provided in the type’s definition. (d) A program units that use a specific abstract data type are called clients of that type. 2. Parameterized or Generic abstract data types : (a) A parameterized abstract data type means that the data type is generic. (b) Both Ada and C+ allows for generic or parameterized abstract data type. (©) These generic types are considered templates. (d) ADT’s are used to define a new type from which instances can be created. An e.g., sometimes these instances should operate on other data types ad well. For instance one can think of lists of apples, cars or even lists. The semantical definition of lists is always the same. Only the type of data elements changes according to what type the list should operate on. This additional information could be specified by a generic parameter which is specified at instance creation time. Thus an instance of a generic ADT is actually an instance of a particular variant of the ADT. A list of apples can therefore be declared as follows: List list of apples; ts now enclose the data type for which a variant of the generic The angle bracl ADT list should be created. Question 49 Ans. Write the design issues of an abstract data types. write its advantages also. ICSVTU May 2014] Or What is the language design issue for abstract data types? Design issues of an abstract data types are: 1. A facility for defining abstract data types in a language must provide a syntactic unit that can encapsulate the type definition and subprogram definitions of the abstract operations. Concurrent Pascal, small talk, C++, and java directly support abstract data types. 3. Some design issues beyond encapsulation are whether the kind of types that can be abstract should be restricted. Whether abstract data type can be parameterized and what access controls are provided, and how such controls are specified. Advantages of Abstract data type: 1. Abstract data type binds the data to the functions so only these functions can use the data objects. 2. Functions outsides the class cannot access the data. 3. It provide, facility to hide the information regarding the storage. So less burden on programmer. nNGATE ACADEMY PUBLICATIONS ™ 2-39 Programming Language Processors nn OSTOMENINE Language Processors 4, We can add new data and functions at any time to the abstract data type. 5. Data is not free to move function to function, only function defined in the class uses the data only. Question 50 L Ans. Discuss Abstract data type (ADT) versus object oriented. 1. ADTs allows the creation of instances well defined properties and behavior. In object-orientation ADTs are reffered to as classes. Therefore a class define properties of objects which are the instances in an object-oriented environment. 2. ADTs define functionality by putting main emphasis on the involved data, their structure, operations as well as axioms and preconditions, Consequently, object- oriented programming is programming with ADTs : combining functionality of different ADTs to solve a problem, Therefore instances (objects) of ADTs (classes) are dynamically created, destroyed and used. 3. The main differences are that object-oriented language supports inheritance and polymorphism whereas ADTs do not necessarily include these features. 4, A language that supports ADTs but is not object oriented is sometimes called an object-based language. An object-oriented language by definition supports ADTs. 5. A class in an actual representation of an ADT. It provides implementation details for the data structure used and operations. Oop supports implementation of an ADT using information hiding, Question 54 Explain the abstract data type with respect to following languages: 1. ADTin Ada 2, ADTinCH 3, ADTin Java 4. ADTinC# Ans. 1. Abstract data type in Ada: (a) The encapsulation construct is called a package : (i) Specification package (the interface). (ii) Body package (implementation of the entities named in the specification). (b) Information hiding : (i) The specification package has two parts, public and private (i) The name of abstract data type appears in the public part of the specification package. (iii) The representation of abstract type is appears in the private part. More restricted form with limited private types, Private types has built in operations for assignment and comparison. Limited private types have no built in operations. Reasons for the public/private specification package : (i) The compiler must be able to see the representations after seeing only the specification package. (it cannot see the private part) (ii) Client must see the type name, but not the representation (they also cannot see the private part). ©} Computational Science 2-40 GATE ACADEMY PUBLICATIONS ™ (@) Having part of the implementation details (the representation) in the specification package and part in the body package (the method bodies) is not good. (@) One solution : makes all ADTs pointers. (6 Problem with this : () Difficulties with pointers. (ii) Object comparisons (iii) Control of object allocation is losts. 2. Abstract data type in C++: (a) Based on c struct type and simula 67 classes. (b) The class is the encapsulations device. () All of the class instances of a class share a single copy of the members functions. (d) Each instance of the class has its own copy of the class data members. (e) Instances can be static, stack dynamic or heap dyn (6) Information hiding: (i) Private clause for hidden entities. (i) Public clause for interface entities. (iii) Protected clause for inheritance. (@ Constructors : (i) Function to the object). (ii) Can include parameters to provide parameterization of the objects. (iii) Implicitly called when an instance is created. (iv) Can be explicitly called. (v) Name is the same as the class name. (h) Destructors : (i) Functions to cleanup after an instance is destroyed; usually just to reclaim heap storage (i) Implicitly called when the object life time ends. (iii) Can be explicitly called. (iv) Name is the class name preceded by tilde (~). 3. Abstract data types in Java: Similar to C++, expe (a) All user-defined types are classes. (b) All objects are allocated from the heap and accessed through reference variables. (©) Individual entities in classes have access control modifiers (private or public) rather than clauses. (d) Java has a second scoping mechanism, package scope, which can be used in place of friends. (All entities in all clauses in a package that do not have access control modifiers are visible throughout the package. _ ialize the data members of instances. (they de not create