alistofbs

Doanyoftheanswerssurpriseyou?

) It is considered a topic that you should know in order to be “well-cultured”in computer science.b) A good craftsman should know his tools, and compilers are important toolsfor programmers and computer scientists.c) The techniques used for constructing a compiler are useful for other purposesas well.d) There is a good chance that a programmer or computer scientist will need towrite a compiler or interpreter for a domain-specific language

s another way of implementing a programming language. Interpre-tation shares many aspects with compiling. Lexing, parsing and type-checking arein an interpreter done just as in a compiler. But instead of generating code fromthe syntax tree, the syntax tree is processed directly to evaluate expressions andexecute statements, and so on. An interpreter may need to process the same pieceof the syntax tree (for example, the body of a loop) many times and, hence, inter-pretation is typically slower than executing a compiled program. But writing aninterpreter is often simpler than writing a compiler and the interpreter is easier tomove to a different machine (see chapter 13), so for applications wher

The compiler may produce intermediate-level code which is then inter-preted rather than compiled to machine code. In some systems, there may even beparts of a program that are compiled to machine code, some parts that are compiledto intermediate code, which is interpreted at runtime while other parts may be keptas a syntax tree and interpreted directly. Each choice is a compromise betweenspeed and space: Compiled code tends to be bigger than intermediate code, whichtend to be bigger than syntax, but each step of translation improves running speed.Using an interpreter is also useful during program development, where

the other hand, programs that are written in a high-level language and auto-matically translated to machine language may run somewhat slower than programsthat are hand-coded in machine language. Hence, some time-critical programs arestill written partly in machine language. A good compiler will, however, be ableto get very close to the speed of hand-written machine code when translating well-structured

ming language that is suitable for human programmers into the low-level machinelanguage that is required by computers. During this process, the compiler will alsoattempt to spot and report obvious programmer mistakes.Using a high-level language for programming has a large impact on how fastprograms can be developed. The main reasons for this are:Compared to machine language, the notation used by programming lan-guages is closer to the way humans think about problems.The compiler can spot some obvious programming mistakes.Programs written in a high-level language tend to be shorter than equivalentprograms written in machine language.Another advantage of using a high-level level language is that the same program

nearly allof these are made to execute relatively simple commands (but do so very quickly).A program for a computer must be built by combining these very simple commandsinto a program in what is calledmachine language. Since this is a tedious and error-prone process most programming is, instead, done using a high-levelprogramminglanguage. This language can be very different from the machine language that thecomputer can execute, so some means of bridging the gap is required.

stract syntax) that is easily manipulated by a computer, can be used to read andmanipulate any kind of structured text such as XML documents,

and convert it into a form suitable for computer manipulation. This processis made in two stages: A lexical analysis stage that basically divides the input textinto a list of “words”. This is followed by a syntax analysis (orparsing) stagethat analyses the way these words form structures and converts the text into a datastructure that reflects the textual structure. Lexical analysis is covered in chapter 2and syntactical analysis in chapter 3.The second part of the book (chapters 4 – 10) covers the middle part and back-end of interpreters and compilers. Chapter 4 covers how definitions and uses ofnames (identifiers) are connected throughsymbol tables. Chapter 5 shows how youcan implement a simple programming language by writing an interpreter and notesthat this gives a considerable overhead that can be reduced by doing more things be-fore executing the program, which leads to the following chapters about static typechecking (chapter 6) and compilation (chapters 7 – 10. In chapter 7, it is shownhow expressions and statements can be compiled into anintermediate language,a language that is close to machine language but hides machine-specific details.In chapter 8, it is discussed how the intermediate language can be converted into“real” machine code. Doing this well requires that the registers in the processorare used to store the values of variables, which is achieved by aregister allocationprocess, as described in chapter 9. Up to this point, a “program” has been whatcorresponds to the body of a single procedure. Procedure calls and nested proce-dure declarations add some issues, which are discussed in chapter 10. Chapter 11deals with analysis and optimisation and chapter 12 is about allocating and freeingmemory. Finally, chapter 13 will discuss the process ofbootstrappinga compiler,i.e., using a compiler to compile itself.The book uses standard set notation and equations over sets. Appendix A con-tains a short summary of these, which may be helpful to those that need

his book was written for use in the introductory compiler course at DIKU, thedepartment of computer science at the University of Copenhagen, Denmar

Originally designed by an international team for general and scientific applications, it never achievedwidespread popularity compared to Fortran because of the support that Fortran received from mostcomputer manufacturers. The first version of Algol was published in 1958; the revised version Al-gol 60 was extensively used in computer science research and implemented on many computers,especially in Europe. A third version of the language, Algol 68, has been influential among lan-guage theorists, though it was never widely implemented.Two important languages that were derived from Algol are Jovial, used by the US Air Force forreal-time systems, and Simula, one of the first simulation languages. But perhaps the most famousdescendent of Algol is Pascal, developed in the late 1960’s by Niklaus Wirth. The motivation forPascal was to create a language that could be used to demonstrate ideas about type declarationsand type checking. In later chapters, we will argue that these ideas are among the most significantconcepts ever proposed in language design

Pascal compiler was itself written in Pascal,2and thus could easily be ported to any computer.The language spread quickly, especially to the mini- and micro-computers that were then beingconstructed. Unfortunately, the Pascal language is too small. The standard language has no facili-ties whatsoever for dividing a program into modules on separate files, and thus cannot be used forprograms larger than several thousand lines. Practical compilers for Pascal support decompositioninto modules, but there is no standard method so large programs are not portable.Wirth immediately recognized that modules were an essential part of any practical language anddeveloped the Modula language. Modula (now in version 3 which supports object-oriented pro-gramming) is a popular alternative to non-standard Pascal dialects

the details of assembly language programming by offering structured control statements and datastructures (arrays and records), while at the same time it retains all the flexibility of low-levelprogramming in assembly language (pointers and bit-level operations).Since UNIX was readily available to universities, and since it is written in a portable languagerather than in raw assembly language, it quickly became the system of choice in academic andresearch institutions. When new computers and applications moved from these institutions to thecommercial marketplace, they took UNIX and C with them.C is designed to be close to assembly language so it is extremely flexible; the problem is that thisflexibility makes it extremely easy to write programs with obscure bugs because unsafe constructsare not checked by the compiler as they would be in Pascal. C is a sharp tool when used expertlyon small programs, but can cause serious trouble when used on large software systems developedby teams of varying ability. We will point out many of the dangers of constructs in C and showhow to avoid major pitfalls.The C language was standardized in 1989 by the American National Standards Institute (ANSI);essentially the same standard was adopted by the International Standards Organization (ISO) a

guage, extending C to include support for object-oriented programming similar to that provided bythe Simula language. In addition, C++fixes many mistakes in C and should be used in preferenceto C, even on small programs where the object-oriented features may not be needed. C++is thenatural language to use when upgrading a system written in C.Note that C++is an evolving language and your reference manual or compiler may not be fullyup-to-date. The discussion in this book followsThe Annotated C++Reference Manualby Elli

mistakes of the original teams were included in the standard. Ada was subjected to intensereview and criticism before standardization.Most languages were initially implemented on a single computer and were heavily influ-enced by the quirks of that computer. Ada was designed to support writing portable pro-grams.Ada extends the scope of programming languages by supporting error handling and concur-rent programming which are traditionally left to (non-standard) operating system functions.Despite technical excellence and advantages of early standardization, Ada has not achieved wide-spread popularity outside of military and other large-scale projects (such as commercial aviationand rail transportation). Ada has received a reputation as a difficult language. This is becausethe language supports many aspects of programming (concurrency, exception handling, portablenumerics) that other languages (like C and Pascal) leave to the operating system, so there is simplymore to learn. Also, good and inexpensive development environments for education were notinitially available. Now with free compilers and good introductory textbooks available, Ada isincreasingly used in the academic curriculum, even as a

Lisp’s basic data structure is the linked list

The ba-sic data structures are vectors and matrice

match, the string can be decomposed into substrings. In Icon, the basic operation is expressionevaluation, where expressions include complex string operations.An important predefined function in Icon isnd(s1, s2)which searches for occurrences of thestrings1in the strings2. Unlike similar functions in C,ndgeneratesa list of all positions ins2in whichs1occurs:line := 0 # Initialize line counterwhile s := read( )f# Read until end of leevery col := nd("the", s) do# Generate column positionswrite(line, " ", col) # Write (line,col) of "the"line := line + 1gThis program will write the line and column numbers of all occurrences of the string “the” in a file.Ifnddoes not find an occurrence, it willfailand the evaluation of the expression is terminated.The keywordeveryforces the repeated evaluation of the function as long as it is successful.Icon expressions are not limited to strings which are sequences of characters; they are also definedoncsets, which are sets of characters. Thus:vowels := 'aeiou'gives the variablevowela value that is the set of characters shown. This can be used in functionslikeupto(vowels,s)which generates the sequence of locations of vowels ins, andmany(vowels,s)which returns the longest initial sequence of vowels ins.A more complex function isbalwhich is likeuptoexcept that it generates sequences of locationswhich are balanced with respect to bracketing characters:bal('+ { * /', '( [', ') ]', s)This expression could be used in a compiler to generate balanced arithmetic sub-strings. Giventhe string"x + (y[u/v] { 1)*z", the above expression will generate the indices corresponding tothe sub-strings:xx + (y[u/v] { 1)The first sub-string is balanced because it is terminated by “+” and there are no bracketing char-acters; the second is balanced because it is terminated by “*” and has square brackets correctlynested within parentheses

all other mathematical structures are defined, SETL can be used to create generalizedprograms that are very abstract and thus very concise. The programs resemble logic programs(Chapter 17) in that mathematical descriptions can be directly executed. The notation used is thatof set theory:fxjp(x)gmeaning the set of allxsuch that the logical formulap(x)is true. Forexample, a mathematical specification of the set of prime numbers can be written:fnj:9m[(2mn1)^(nmodm=0)]gThis formula is read: the set of numbers such that there does not exist a numbermbetween 2 andn1 that dividesnwithout a remainder.To print all primes in the range 2 to 100, we just translate the definition into a one-line SETLprogram:print(fn inf2..100g| not exists m inf2..n { 1g| (n mod m) = 0g);What all these languages have in common is that they approach language design from a mathe-matical viewpoint—how can a well-understood theory be implemented, rather than from an en-gineering viewpoint—how can instructions be issued to the CPU and memory. In practice, theseadvanced languages are very useful for difficult programming tasks where it is important to con-centrate on the problem and not on low-level details.Data-oriented languages are somewhat less popular than they once were, partly because by us-ing object-oriented techniques it is possible to embed such data-oriented operations into ordinarylanguages like C++and Ada, but also because of competition from newer language con

orld or other objects, and then writing modules each of which contains all the data and exe-cutable statements needed to represent oneclassof objects. Within such a module, there is a cleardistinction between the abstract properties of the class which are exported for use by other objects,and the implementation which is hidden so that it can be modified without affecting the rest of thesystem.The first object-oriented programming language, Simula, was created in the 1960’s by K. Ny-gaard and O.-J. Dahl for system simulation: each subsystem taking part in the simulation wasprogrammed as an object. Since there can be more than one instance of each subsystem, a classcan be written to describe each subsystem and objects of this class can then be allocated.The Xerox Palo Alto Research Center popularized OOP with the Smalltalk6language. The sameresearch also led to the windowing systems so popular today, and in fact, an important advantageof Smalltalk is that it is not just a language, but a complete programming environment. Thetechnical achievement of Smalltalk was to show that a language can be defined in which classesand objects are theonlystructuring constructs, so there is no need to introduce these concepts intoan “ordinary” language.There is a technical aspect of these pioneering object-oriented languages that prevented wideracceptance of OOP: allocation, operation dispatching and type checking are dynamic (run-time)as opposed to static (compile-time). Without going into detail here (see the appropriate materialin Chapters 8 and 14), the result is that there is a time and memory overhead to programs in theselanguages which can be prohibitive in many types of systems. In addition, static type checking(see Chapter 4) is now considered essential for developing reliable software. For these reasons,Ada 83 only implemented a subset of the language support required for OOP.C++showed that it was possible to implement the entire machinery of OOP in a manner that isconsistent withstaticallocation and type-checking, and with fixed overhead for dispatching; thedynamic requirements of OOP are used only as needed. Ada 95 based its support for OOP onideas similar to those found in C++.However, it is not necessary to graft support for OOP onto existing languages to obtain theseadvantages. The Eiffel language is similar to Smalltalk in that the only structuring method is thatof classes and objects, and it is similar to C++and Ada 95 in that it is statically type-checked andthe implementation of objects can be static or dynamic as needed. The simplicity of the languag

ment statement which commands the computer to move data from one place to another. This isactually a relatively low level of abstraction compared to the level of the problems we want tosolve with computers. Newer languages prefer to describe a problem and let the computer figureout how to solve it, rather than specifying in great detail how to move data around.Modern software packages are really highly abstract programming languages. An application gen-erator lets youdescribea series of screen and database structures, and then automatically createsthe low-level commands needed to implement the program. Similarly, spreadsheets, desktop pub-lishing software, simulation packages and so on have extensive facilities for abstract programming.The disadvantage of this type of software is that they are usually limited in the type of applicationthat can be easily programmed. It seems appropriate to called themparameterized programs, inthe sense that by supplying descriptions as parameters, the package will configure itself to executethe program you need.Another approach to abstract programming is to describe a computation using equations, func-tions, logical implications, or some similar formalism. Since mathematical formalisms are used,languages defined this way are true general-purpose programming languages, not limited to anyparticular application domain. The compiler does not really translate the program into machinecode; rather it attempts to solve the mathematical problem, whose solution is considered to be theoutput of the program. Since indices, pointers, loops, etc. are abstracted away, these programscan be an order of magnitude shorter than ordinary programs. The main problem with descrip-tive programming is that computational tasks like I/O to a screen or disk do not fit in well withthe concept, and the languages must be extended with ordinary programming constructs for thesepurposes.We will discuss two non-imperative language formalisms: (1) functional programming (Chap-ter 16), which is based on the mathematical concept of pure functions, likesinandlogthat do notmodify their environments, unlike so-called functions in an ordinary language like C which canhave side-effects; (2) logic programming (Chapter 17), in which programs are expressed as for-mulas in mathematical logic, and the “compiler” attempts to infer logical consequences of theseformulas in order to solve problems

ompilers adhere to the standard, programs can be ported from one computer to another. If you arewriting a software package that is to run on a wide range of computers, you should strictly adhereto a standard. Otherwise your maintenance task will be extremely complicated because you mustkeep track of dozens or hundreds of machine-specific items.Standards exist (or are in preparation) for most languages discussed here. Unfortunately, thestandards were proposed years after the languages became popular and must preserve machine-specific quirks of early implementations. The Ada language is an exception in that the standards(1983 and 1995) were created and evaluated at the same time as the language design and initialimplementation. Furthermore, the standard is enforced so that compilers can be compared basedon performance and cost, rather than on adherence to the standard. Compilers for other languagesmay have a mode that will warn you if you are using a non-standard construct. If such construct

bus

specializing the interface and by avoiding bottlenecks). From the point of view ofthe software, the only difference that need be considered is the rate at which data can be transferredbetween components.The CPU contains a set ofregisterswhich are special memory locations in which computation isbe done. The CPU can execute any one of a set ofinstructionswhich are stored in memory; theCPU maintains aninstruction pointerwhich points to the location of the next instruction to beexecuted. Instructions are divided into the following classes:Memory access:Loadthe contents of a memory word into a register, andStorethe contentsof a register into a memory word.Arithmetic instructions such as add and subtract. These operations are performed on thecontents of two registers (or sometimes between the content of a register and the content ofa memory word). The result is left in a register. For example:add R1,Nadds the contents of the memory wordNto the contents of the registerR1and leaves theresult in the register.Compare and jump. The CPU can compare two values such as the contents of two registers;depending on the result (equal, greater than, etc.), the instruction pointer is changed to pointto another instruction. For example:jumpeq R1,L1. . .L1: . . .causes the computation to continue with the instruction labeledL1if the contents ofR1arezero; otherwise, the computation continues with the next instruction.Many computers, calledReduced Instruction Set Computers(RISC), limit themselves to theseelementary instructions; the rationale is that a CPU that only needs to execute a few simple in-structions can be very fast. Other computers define more Complex Instructions (CISC) to simplifyboth assembly language programming and compiler construction. The debate between these twoapproaches is beyond the scope of this book; they have enough in common that the choice doesnot materially affect our discussion.Memory is a set of locations that can be used to store data. Each memory location, called amemoryword, has anaddress, and each word consists of a fixed number of bits, typically 16, 32,or 64 bits. The computer may be able to load and store 8 bitbytes, or double words of 64 bits.It is important to know what kind of addressing modes can be used in an instruction. The simplestmode is immediate addressing which means that the operand is part of the instruction. The valu

efined quickly became the most widespread language in its field (as Fortran has in science), andfor a similar reason: the language provides a natural means of expressing computations that aretypical in its field. Business data processing is characterized by the need to do relatively simplecalculations on vast numbers of complex data records, and Cobol’s data structuring capabilitiesfar surpass those of algorithmic languages like Fortran or C.IBM later created the language PL/I as a universal language having all the features of Fortran,Cobol and Algol. PL/I has replaced Fortran and Cobol on many IBM computers, but this verylarge language was never widely supported outside of IBM, espe

Fortran was the first programming language that significantly rose above the level of assemblylanguage. It was developed in the 1950’s by an IBM team led by John Backus, and was intendedto provide an abstract way of specifying scientific computations. The opposition to Fortran wasstrong for reasons similar to those advanced against all subsequent proposals for higher-level ab-stractions, namely, most programmers believed that a compiler could not produce optimal coderelative to hand-coded assembly language.Like most first efforts in programming languages, Fortran was seriously flawed, both in details ofthe language design and more importantly in the lack of support for modern concepts of data andmodule structuring. As Backus himself said in retrospect:As far as we were aware, we simply made up the language as we went along. We didnot regard language design as a difficult problem, merely a simple prelude to the realproblem: designing a compiler which could produce efficient programs.1Nevertheless, the advantages of the abstraction quickly won over most programmers: quicker andmore reliable development, and less machine dependence since register and machine instructionsare abstracted away. Because most early computing was on scientific problems, Fortran becamethe standard language in science and engineering, and is only now being replaced by other lan-guages. Fortran has undergone extensive modernization (1966, 1977, 1990) to adapt it to therequirements of modern software development.

f you write a program in C, you lose the ability you had in assembly language to specify registerallocation; if you write in Prolog, you lose the ability you had in C to specify arbitrary linkedstructures using pointers. There is a natural tension between striving for the concise, clear andreliable expression of a computation in a high-level abstraction, and wanting the flexibility

computer is technically easy but practically inconvenient, since each instruction has to be writtenas binary digits (bits) that can be represented mechanically or electronically. One of the firstsoftware tools was thesymbolic assembler. An assembler takes a program written inassemblylanguage, which represents each instruction as a symbol, and translates the symbols into a binaryrepresentation suitable for execution on the computer. For example, the instruction:load R3,54meaning “load register 3 with the data in memory location 54”, is much more readable than theequivalent string of bits. Believe it or not, the termautomatic programmingoriginally referredto assemblers since they automatically selected the right bit sequence for each symbol. Familiarprogramming languages like C and Pascal are more sophisticated than assemblers because they“automatically” choose addresses and registers, and even “automatically” choose instruction se-quences to specify loops and arithmetical expression

easily as the data used in the computation. Thestored-program computerthus becomes a general-purpose calculating machine and we can change the program just by changing a plugboard ofwires, feeding a punched card, inserting a diskette, or connecting to a telephone line

1.1 The wrong questionWhen one first encounters a new programming language, the first question is usually:What can this language “do”?Implicitly we are comparing the new language with other languages. The answer is very simple:all languages can “do” exactly the same computations! Section 1.8 outlines the justification forthis answer. If they can all do the same computations, surely there must be other reasons for theexistence of hundreds of programming languages.Let us start with some definitions:Aprogramis a sequence of symbols that specifies a computation. Aprogramminglanguageis a set of rules that specify which sequences of symbols constitute a pro-gram, and what computation the program describes.You may find it interesting that the definition does not mention the word computer! Programsand languages can be defined as purely formal mathematical objects. However, more people areinterested in programs than in other mathematical objects such as groups, precisely because it ispossible to use the program—the sequence of symbols—to control the execution of a computer.While we highly recommend the study of the theory of programming, this text will generally limititself to the study of programsas they are executedon a computer.

e of the hardest problems confronting computer architects is matching the performance of theCPU to the performance of the memory. CPU processing speeds are so fast compared with mem-ory access times, that the memory cannot supply data fast enough for the CPU to be kept contin-uously working. There are two reasons for this: (1) there are only a few CPU’s (usually one) ina computer, and the fastest, most expensive technology can be used, but memory is installed inever increasing amounts and must use less-expensive technology; (2) the speeds are so fast thata limiting factor is the speed at which electricity flows in the wires between the CPU and thememory.The solution is to use a hierarchy of memories as shown in Figure 1.2. The idea is to store unlim-RegistersCacheMainMemoryDisk---Figure 1.2: Cache and virtual memoryited amounts of program instructions and data in relatively slow (and inexpensive) memory, andto load relevant portions of the instructions and data into smaller amounts of fast (and expensive)memory. When the slow memory is disk and the fast memory is ordinary RAM (Random Ac-cess Memory), the concept is calledvirtual memoryorpaged memory. When the slow memoryis RAM and the fast memory is RAM implemented in a faster technology, the concept is

if-statement::=if (expression)statement[elsestatement]

ording to the Church-Turing Thesis, any computation that you can effectively describe can beprogrammed on this primitive machine. The evidence for the Thesis rests on two foundations:Researchers have proposed dozens of models of computation and all of them have beenproven to be equivalent to Turing machines.No one has ever described a computation that cannot be computed by a Turing machine.Since a Turing machine can easily be simulated in any programming language, all programminglanguages “do” the same thin

ny languages are case-insensitive, that is,COUNTandcountrepresent the same name.C is case-sensitive, so that the strings represent two distinct identifiers. In case-sensitivelanguages, a project should establish clear conventions on the use of case so that acciden-tal typing mistakes do not cause errors. For example, one convention in C requires thateverything be in lower-case, except defined constant names which are all in upp

For example, executing:a := 25will change the statesto a new states0that is exactly likesexcept that the memory locationassigned toacontains 25.

hile the syntax of languages is very well understood, semantics is much more difficult

Of course, the proof of correctness is only relative to the input and output assertions: it does youno good to prove that a program computes a square root if you need a program to compute a cuberoot! Nevertheless, program verification is a powerful method that has been used in systems thatmust be highly reliable. More importantly, studying verification will improve your ability to writecorrect programs, because you will learn to think in terms of the requirements for correctness.

In Chapters 4 and 9 we will explain whyintand oatare not mathematical, but rather physical representations of memory

ValueA value is an undefined primitive concept.LiteralA specific value is denoted in a program by a literal, which is a sequence of symbols, forexample:154,45.6,FALSE,'x',"Hello world".RepresentationA value is represented within a computer by a specific string of bits. For example,the character value denoted by'x'may be represented by the string of eight bits 0111 1000.VariableA variable is a name given to the memory cell or cells that can hold the representation ofa value of a specific type. The value may be changed during the execution of the program.ConstantA constant is a name given to the memory cell or cells that can hold the representationof a value of a specific type. The value maynotbe changed during the execution of theprogram

sophisticated word processors usually have a facility that enables you to “capture” a sequence ofkey-presses and store them as amacroso that you can execute the entire sequence by pressing asingle key. This is certainly a program because the sequence of key-presses specifies a computationand the software manual will clearly specify the macro language: how to initiate, terminate andname a macro definition.To answer the question in the title of the chapter, we first go back to early digital computers, whichwere very much like the simple calculators used today by your grocer in that the computation thatsuch computers perform is “wired-in” and cannot be changed

he lowly assignment statement is actually quite complex, executing three separate tasks:1. Compute the value of the expression on the right-hand side of the statement.2. Compute the expression on the left-hand side of the statement; the expression must evaluateto the address of a memory cell.3. Copy the value obtained in step (1) to memory cells starting with the address obtained instep (2).Thus the assignment statement:a(i+1) = b + c;despite its superficial resemblance to an equation specifies a complex computatio

Type checkingis a check that the type of the expression is compatible with the typeof the target variable during assignment. This includes the assignment of an actualparameter to a formal parameter when a procedure is called.Possible approaches to type checking are:Do nothing; it is the programmer’s responsibility to ensure that the assignment is meaning-ful.Implicitly convert the value of the expression to the type required by the left-hand side.Strongtype checking: refuse to execute the assignment if the types are not the same.There is a clear trade-off between flexibility and reliability: the more type checking that is donethe more reliable a program will be, but it will require more programming effort to define anappropriate set of types. In addition, provision must be made to bypass type checking if needed.Conversely, if little type checking is done it is easy to write a program, but it then become

Strong type checking can eliminate obscure bugs which are usually caused by such errors or mis-understandings. It is especially important in large software projects which are developed by teamsof programmers; breakdowns in communications, personnel turnovers, etc. make it difficult tointegrate such software without the constant checking done by strong type checking. In effect,strong type checking attempts to transform run-time errors into compile-time errors. Run-timeerrors can be extremely difficult to find, dangerous to the users of the software and expensive forthe developer of the software in terms of delayed delivery and damaged reputation. The cost of acompile-time error is trivial; in fact, you probably don’t even have to tell your boss that you madea compile-time

Structured programmingis the name given to the programming style which restricts the use of con-trol statements to those which yield well-structured programs that are easy to read and understand.There are two classes of well-structured control statements:Choice statements that select one alternative from two or more possible execution sequences:if-statements andcase- orswitch-statements.Loop statements that repeatedly execute a sequence of statements:for-statements andwhile-statements.A good understanding of loop statements is particularly important for two reasons: (1) most of theexecution time will (obviously) be spent within loop statements, and (2) many bugs are caused byincorrect coding at the beginning or end of a

When a subprogram is called, it is passed a sequence of values calledparameters. Parameters areused to modify each execution of the subprogram, to send data to the subprogram, and to receivethe results of a computation. Parameter passing mechanisms differ widely from one language toanoth

Asubprogramis a segment of a program that can be invoked from elsewhere within the program.Subprograms are used for various reasons

ModulesThe elements of the language discussed thus far are sufficient for writingprograms; they are notsufficient for writing asoftware system: a very large program or set of programs developed byteams of programmers. Students often extrapolate from their talent at writing (small) programs,and conclude that writing a software system is no different, but bitter experience has shown thatwriting a large system requires additional methods and tools beyond mere programming. Thetermsoftware engineeringis used to denote the methods and tools for designing, managing andconstructing software systems. In this text we limit ourselves to discussing support for largesystems that can be given by programming languages.You may have been told that a single subprogram should be limited to 40 or 50 lines, because aprogrammer cannot easily read and comprehend larger segments of code. By the same measure,it should be easy to understand the interactions of 40 or 50 subprograms. The obvious conclusionis that any program larger than 1600-2500 lines is hard to understand! Since useful programs canhave tens of thousands of lines, and systems of hundreds of thousands of lines are not uncommon,it is clear that additional structures are needed to construct large systems.If older programming languages are used, the only recourse is to “bureaucracy”: sets of rules andconventions that prescribe to the team members how programs are to be written. Modern pro-gramming languages contain an additional structuring method forencapsulating3data and sub-programs within larger entities calledmodules. The advantage of modules over bureaucracy isthat the interfaces between modules can be checked during compilation to prevent errors and mis-understandings. Furthermore, the actual executable statements, and most (or all) of the data of amodule, can be hidden so that they cannot be modified or used except as specified by the interface.The are two potential difficulties with the practical use of modules:A powerful program development environment is needed to keep track of the modules andto check the interfaces.Modularization encourages the use of many small subprograms with the corresponding run-time overhead of the subprogram call.Neither of these is now a problem: the average personal computer is more than adequate to runan environment for C++or Ada, and modern computer architectures and compilation techniquesminimize the overhead of

he fact that a language has support for modules does not help us to decide what to put in amodule. In other words, how do we decompose a software system into modules? Since the qualityof the system is directly dependent on the quality of the decomposition, the competence of asoftware engineer should be judged on his/her ability to analyze a project’s requirements and tocreate the best software structure to implement the project. It requires much experience to developthis ability; perhaps the best way is to study existing software systems

In 1949, a few years after Von Neumann’s work, the language Short Code appeared (www.byte.com). It was the first computer language for electronic devices and it required the programmer to change its statements into 0’s and 1’s by hand. Still, it was the first step towards the complex languages of today. In 1951, Grace Hopper wrote the first compiler, A-0 (www.byte.com). A compiler is a program that turns the language’s statements into 0’s and 1’s for the computer to understand. This lead to faster programming, as the programmer no longer had to do the work by hand. In 1957, the first of the major languages appeared in the form of FORTRAN. Its name stands for FORmula TRANslating system. The language was designed at IBM for scientific computing. The components were very simple, and provided the programmer with low-level access to the computers innards. Today, this language would be considered restrictive as it only included IF, DO, and GOTO statements, but at the time, these commands were a big step forward. The basic types of data in use today got their start in FORTRAN, these included logical variables (TRUE or FALSE), and integer, real, and double-precision numbers.

Though Java has very lofty goals and is a text-book example of a good language, it may be the “language that wasn’t.” It has serious optimization problems, meaning that programs written in it run very slowly. And Sun has hurt Java’s acceptance by engaging in political battles over it with Microsoft. But Java may wind up as the instructional language of tomorrow as it is truly object-oriented and implements advanced techniques such as true portability of code and garbage collection. Visual Basic is often taught as a first programming language today as it is based on the BASIC language developed in 1964 by John Kemeny and Thomas Kurtz. BASIC is a very limited language and was designed for non-computer science people. Statements are chiefly run sequentially, but program control can change based on IF..THEN, and GOSUB statements which execute a certain block of code and then return to the original point in the program’s flow. Microsoft has extended BASIC in its Visual Basic (VB) product. The heart of VB is the form, or blank window on which you drag and drop components such as menus, pictures, and slider bars. These items are known as “widgets.” Widgets have properties (such as its color) and events (such as clicks and double-clicks) and are central to building any user interface today in any language. VB is most often used today to create quick and simple interfaces to other Microsoft products such as Excel and Access without needing a lot of code, though it is possible to create full applications with it. Perl has often been described as the “duct tape of the Internet,” because it is most often used as the engine for a web interface or in scripts that modify configuration files. It has very strong text matching functions which make it ideal for these tasks. Perl was developed by Larry Wall in 1987 because the Unix sed and awk tools (used for text manipulation) were no longer strong enough to support his needs. Depending on whom you ask, Perl stands for Practical Extraction and Reporting Language or Pathologically Eclectic Rubbish Lister. Programming languages have been under development for years and will remain so for many years to come. They got their start with a list of steps to wire a computer to perform a task. These steps eventually found their way into software and began to acquire newer and better features. The first major languages were characterized by the simple fact that they were intended for one purpose and one purpose only, while the languages of today are differentiated by the way they are programmed in, as they can be used for almost any purpose. And perhaps the languages of tomorrow will be more natural with the invention of quantum and biological computers.

C was developed in 1972 by Dennis Ritchie while working at Bell Labs in New Jersey. The transition in usage from the first major languages to the major languages of today occurred with the transition between Pascal and C. Its direct ancestors are B and BCPL, but its similarities to Pascal are quite obvious. All of the features of Pascal, including the new ones such as the CASE statement are available in C. C uses pointers extensively and was built to be fast and powerful at the expense of being hard to read. But because it fixed most of the mistakes Pascal had, it won over former-Pascal users quite rapidly. Ritchie developed C for the new Unix system being created at the same time. Because of this, C and Unix go hand in hand. Unix gives C such advanced features as dynamic variables, multitasking, interrupt handling, forking, and strong, low-level, input-output. Because of this, C is very commonly used to program operating systems such as Unix, Windows, the MacOS, and Linux. In the late 1970’s and early 1980’s, a new programing method was being developed. It was known as Object Oriented Programming, or OOP. Objects are pieces of data that can be packaged and manipulated by the programmer. Bjarne Stroustroup liked this method and developed extensions to C known as “C With Classes.” This set of extensions developed into the full-featured language C++, which was released in 1983. C++ was designed to organize the raw power of C using OOP, but maintain the speed of C and be able to run on many different types of computers. C++ is most often used in simulations, such as games. C++ provides an elegant way to track and manipulate hundreds of instances of people in elevators, or armies filled with different types of soldiers. It is the language of choice in today’s AP Computer Science courses. In the early 1990’s, interactive TV was the technology of the future. Sun Microsystems decided that interactive TV needed a special, portable (can run on many types of machines), language. This language eventually became Java. In 1994, the Java project team changed their focus to the web, which was becoming “the cool thing” after interactive TV failed. The next year, Netscape licensed Java for use in their internet browser, Navigator. At this point, Java became the language of the future and several companies announced applications which would be written in Java, none of which came into use.

The Algol language was created by a committee for scientific use in 1958. It’s major contribution is being the root of the tree that has led to such languages as Pascal, C, C++, and Java. It was also the first language with a formal grammar, known as Backus-Naar Form or BNF (McGraw-Hill Encyclopedia of Science and Technology, 454). Though Algol implemented some novel concepts, such as recursive calling of functions, the next version of the language, Algol 68, became bloated and difficult to use (www.byte.com). This lead to the adoption of smaller and more compact languages, such as Pascal. Pascal was begun in 1968 by Niklaus Wirth. Its development was mainly out of necessity for a good teaching tool. In the beginning, the language designers had no hopes for it to enjoy widespread adoption. Instead, they concentrated on developing good tools for teaching such as a debugger and editing system and support for common early microprocessor machines which were in use in teaching institutions. Pascal was designed in a very orderly approach, it combined many of the best features of the languages in use at the time, COBOL, FORTRAN, and ALGOL. While doing so, many of the irregularities and oddball statements of these languages were cleaned up, which helped it gain users (Bergin, 100-101). The combination of features, input/output and solid mathematical features, made it a highly successful language. Pascal also improved the “pointer” data type, a very powerful feature of any language that implements it. It also added a CASE statement, that allowed instructions to to branch like a tree in such a manner: CASE expression OF possible-expression-value-1: statements to execute... possible-expression-value-2: statements to execute... END Pascal also helped the development of dynamic variables, which could be created while a program was being run, through the NEW and DISPOSE commands. However, Pascal did not implement dynamic arrays, or groups of variables, which proved to be needed and led to its downfall (Bergin, 101-102). Wirth later created a successor to Pascal, Modula-2, but by the time it appeared, C was gaining popularity and users at a rapid pace.

(Updated Aug 11 2004) In 1958, John McCarthy of MIT created the LISt Processing (or LISP) language. It was designed for Artificial Intelligence (AI) research. Because it was designed for a specialized field, the original release of LISP had a unique syntax: essentially none. Programmers wrote code in parse trees, which are usually a compiler-generated intermediary between higher syntax (such as in C or Java) and lower-level code. Another obvious difference between this language (in original form) and other languages is that the basic and only type of data is the list; in the mid-1960’s, LISP acquired other data types. A LISP list is denoted by a sequence of items enclosed by parentheses. LISP programs themselves are written as a set of lists, so that LISP has the unique ability to modify itself, and hence grow on its own. The LISP syntax was known as “Cambridge Polish,” as it was very different from standard Boolean logic (Wexelblat, 177): x V y - Cambridge Polish, what was used to describe the LISP program OR(x,y) - parenthesized prefix notation, what was used in the LISP program x OR y - standard Boolean logic LISP remains in use today because its highly specialized and abstract nature.

Though FORTAN was good at handling numbers, it was not so good at handling input and output, which mattered most to business computing. Business computing started to take off in 1959, and because of this, COBOL was developed. It was designed from the ground up as the language for businessmen. Its only data types were numbers and strings of text. It also allowed for these to be grouped into arrays and records, so that data could be tracked and organized better. It is interesting to note that a COBOL program is built in a way similar to an essay, with four or five major sections that build into an elegant whole. COBOL statements also have a very English-like grammar, making it quite easy to learn. All of these features were designed to make it easier for the average business to learn and adopt it.

In 1945, John Von Neumann was working at the Institute for Advanced Study. He developed two important concepts that directly affected the path of computer programming languages. The first was known as “shared-program technique” (www.softlord.com). This technique stated that the actual computer hardware should be simple and not need to be hand-wired for each program. Instead, complex instructions should be used to control the simple hardware, allowing it to be reprogrammed much faster. The second concept was also extremely important to the development of programming languages. Von Neumann called it “conditional control transfer” (www.softlord.com). This idea gave rise to the notion of subroutines, or small blocks of code that could be jumped to in any order, instead of a single set of chronologically ordered steps for the computer to take. The second part of the idea stated that computer code should be able to branch based on logical statements such as IF (expression) THEN, and looped such as with a FOR statement. “Conditional control transfer” gave rise to the idea of “libraries,” which are blocks of code that can be reused over and over. (Updated Aug 1 2004: Around this time, Konrad Zuse, a German, was inventing his own computing systems independently and developed many of the same concepts, both in his machines and in the Plankalkul programming language. Alas, his work did not become widely known until much later. For more information, see this website: http://www.epemag.com/zuse/, or the entries on Wikipedia: Konrad Zuse and Plankalkul.)

Ever since the invention of Charles Babbage’s difference engine in 1822, computers have required a means of instructing them to perform a specific task. This means is known as a programming language. Computer languages were first composed of a series of steps to wire a particular program; these morphed into a series of steps keyed into the computer and then executed; later these languages acquired advanced features such as logical branching and object orientation. The computer languages of the last fifty years have come in two stages, the first major languages and the second major languages, which are in use today. In the beginning, Charles Babbage’s difference engine could only be made to execute tasks by changing the gears which executed the calculations. Thus, the earliest form of a computer language was physical motion. Eventually, physical motion was replaced by electrical signals when the US Government built the ENIAC in 1942. It followed many of the same principles of Babbage’s engine and hence, could only be “programmed” by presetting switches and rewiring the entire system for each new “program” or calculation. This process proved to be very tedious.