WIXLIB

Table of Contents12.2. Flavor of object-oriented approach 622Abstract data types 622Type system 623Dynamic properties 623Object-oriented problem solving 62312.3. The correctness specification language 625Eiffel and first-order predicate Logic 625Stack as an example 632Partial and total functions 634Precondition 635Postcondition 635Pre- and postconditions in Eiffel 636Design aspects 639Class invariant 639Check construct 642Loops 643Assertions and inheritance 64712.4. Program-correctness in Eiffel 652Hoare-formulas 653Correctness of attributes 654Loop correctness 654Check correctness 656Exception correctness 656Class consistency 658Class correctness 660Note on method correctness 660Program correctness 66112.5. Program correctness issues 662Dependencies 662Void-safety 663Type safety 666Concurrency 66912.6. Correctness specification language 669Practical limits 669Model classes: an interim solution? 671Theoretical limits 67312.7. Languages and tools supporting Design by ContractD language 673Cobra language 675Oxygene language 676Correctness in .NET 678Java language and additional tools 682Ada 2012 language 689 673 xvii

xviii Table of Contents12.8.12.9.12.10.12.11.12.12.Summary 689Example source codeExercises 693Useful tips 697Solutions 69813. Con urren y 690704Richard O. Legendi, Ákos Balaskó, Máté Tejfel, Viktória Zsók13.1. Reasons for concurrency 70813.2. An abstract example 70813.3. Fallacies of concurrent computing 71413.4. Possible number of execution paths 716Amdahl’s law 71913.5. Taxonomy of concurrent architectures 72113.6. Communication and synchronization models 72213.7. Mutual exclusion and synchronization 723Deadlocks 723Starvation 725Techniques for synchronization 725Solutions for managing critical sections 72613.8. Taxonomy of languages supporting concurrency 729Processes, tasks, threads: Concurrent execution units 732Monitors 739Alternative approaches 74013.9. Common execution models 743Producers-consumers problem 743Readers-writers problem 744Dining philosophers problem 74413.10. Ada 746Tasks 746Entry, entry calls, accept statement 753Selective handling of incoming messages 756Exception handling 761Examples 76113.11. CSP 76813.12. Occam 77113.13. MPI 775Case study: Matrix multiplication 78013.14. Java 78113.15. C#/.NET 795Comparison of .Net with Java 795

Table of Contents13.16. Scala 798Comparison with concurrent processes 800Parallel collections 80513.17. General tips for creating concurrent softwareSingle responsibility principle 809Restrict access to shared resources 809Independency 809Do not reinvent the wheel! 810Know the library support 811Write thread-safe modules 811Testing 81113.18. Summary 81213.19. Exercises 81213.20. Useful tips 81413.21. Solutions 814 809828Attila Kispitye, Péter Csontos14. Program libraries 14.1. Requirements against program libraries 830Skills of a good program library developer 830Basic quality requirements 831Special requirements for program libraries 834Conditions for fulfillment of the requirements 83714.2. Object-oriented program library design 837Class hierarchy 838Size of the classes 841Size of services 844Types of classes 84614.3. New paradigms 85014.4. Standard program libraries 850Data structures 851I/O 851Memory management 85214.5. Lifecycle of program libraries 852Design phase 853Implementation phase 853Maintenance phase 85414.6. Summary 854 xix

xx Table of Contents856Zoltán Horváth, Gábor Páli, coauthors in Section 15.10: Viktória Zsók, MátéTejfel15. Elements of fun tional programming languages 15.1. Introduction 857The functional programming style 858Structure and evaluation of functional programs 859Features of modern functional languages 861Brief overview of functional languages 86515.2. Simple functional programs 867Definition of simple functions 867Guards 867Pattern matching 86815.3. Function types, higher-order functions 869Simple type constructions 871Local declarations 877An interesting example: queens on the chessboard 87715.4. Types and classes 881Polymorphism, type classes 881Algebraic data types 884Type synonyms 887Derived types 887Type constructor classes 88915.5. Modules 889Abstract algebraic data types 89015.6. Uniqueness, monads, side effects 893Unique variables 893Monads 895Mutable variables 89715.7. Interactive functional programs 89815.8. Error handling 90115.9. Dynamic types 90215.10. Concurrent, parallel and distributed programs 903Parallel and distributed programming in Concurrent Clean 904Distributed, parallel and concurrent programming in Haskell 907Parallel and distributed language constructs of JoCaml 91915.11. Summary 92215.12. Exercises 92215.13. Useful tips 92315.14. Solutions 924

Table of Contents16. Logiprogramming and Prolog 932Tibor Ásványi16.1. Introduction 93316.2. Logic programs 934Facts 935Rules 936Computing the answer 938Search trees 940Recursive rules 94216.3. Introduction to the Prolog programming language16.4. The data structures of a logic program 94616.5. List handling with recursive logic programs 948Recursive search 950Step-by-step approximation of the output 951Accumulator pairs 953The method of generalization 95416.6. The Prolog machine 954Executing pure Prolog programs 955Pattern matching 956NSTO programs 958First argument indexing 960Last call optimization 96116.7. Modifying the default control in Prolog 962Disjunctions 963Conditional goals and local cuts 963Negation and meta-goals 967The ordinary cut 96916.8. The meta-logical predicates of Prolog 972Arithmetic 972Type and comparison of terms 974Term manipulation 97516.9. Operator symbols in Prolog 97716.10. Extra-logical predicates of Prolog 980Loading Prolog programfiles 980Input and output 981Dynamic predicates 98216.11. Collecting solutions of queries 98516.12. Exception handling in Prolog 98716.13. Prolog modules 988Flat, predicate-based module system 988Module prefixing 990Modules and meta-predicates 991 944 xxi

xxii Table of Contents16.14. Conclusion 993Some classical literature 993Extensions of Prolog 993Problems with Prolog 994Fifth generation computers and their programsNewer trends 99516.15. Summary 99616.16. Exercises 99716.17. Useful tips 99916.18. Solutions 1003 9951012Péter Csontos, Tamás Kozsik, Attila Kispitye17. Aspe t-oriented programming 17.1. Overview of AOP 1014Aspects and components 1015Aspect description languages 1015Aspect weavers 101617.2. Introduction to AspectJ 1017Elements and main features of AspectJ 1017A short AspectJ example 1018Development tools and related languages 101817.3. Paradigms related to AOP and their implementations 1019Multi-dimensional separation of concerns (MDSC) 1019Adaptive programming (AP) 1020Composition filters (CF) 1021Generative programming (GP) 1021Intentional programming (IP) 1022Further promising initiatives 102317.4. Summary 10241026Péter Csontos, Attila Kispitye et al.18. Appendix 18.1. Short descriptions of programming languagesAda 1027ALGOL 60 1028ALGOL 68 1029BASIC 1029BETA 1029C 1029C 1030C# 1031Clean 1031 1027

Table of ContentsCLU 1031COBOL 1032Delphi 1032Eiffel 1033FORTRAN 1033Haskell 1034Java 1034LISP 1035Maple 1035Modula-2 1036Modula-3 1036Objective-C 1036Pascal 1037Perl 1037PHP 1038PL/I 1038Python 1038Ruby 1038SIMULA 67 1039Smalltalk 1039SML 1040SQL 1040Tcl 104118.2. Codetables 1042The ASCII character table 1042The ISO 8859-1 (Latin-1) printable character tableThe ISO 8859-2 (Latin-2) printable character tableThe IBM Codepage 437 1044The EBCDIC character table 1045Bibliography Index 10691049 10431043 xxiii

Introdu tion

Programming languages are thought by many to provide as a notation formfor program description. This view does not take into account – or does noteven know –, how high level or user-centered languages can aid in managingprogram complexity. Different languages with their possibilities suggest differentprogramming approaches, so the common practice, which is still used nowadaysin many places, is highly dangerous, when programming methodology is taughtthrough particular programming languages, not independently from them – thiscould only lead to narrow concerning all the programming possibilities.The goal of programming is to produce a good quality software product, sothe education of programming must start with the general definition of thetask and its solving program [Fot83]. Then based on this principle, the differentconcrete language tools should be acquainted to the programmers, which supportthe implementation. However, as it is questionable to teach the methodologythrough particular concrete programming languages, it also leads to a dead end,if the used programming language is said to be not important for the sake of themethodology. This is – as described by Bertrand Meyer [Mey00] – like “a birdwithout wings”. The idea is inseparable from the possibilities of formulation. It isnot a coincidence that in programming no single language has become dominant,nor that always newer programming languages are designed, which support evenmore the adaptation of different methodological concepts and requirements intopractice.Designers of programming languages must deal with three problems [Hor94]: The representation provided by the language must fit the hardware andthe software at the same time.The language must provide a good nomenclature for the description ofalgorithms.The language must serve as a tool to manage program complexity.

2 Introdu tionAspe ts of software qualityThe software is a product, and as for every product, it has – as defined by many([Mey00], [Hor94] and [LG96]) – different quality characteristics and requirements. One of the most important goals of the programming methodology isto specify a theoretical approach for creating good quality program products.The design and the evaluation of already existing programming languages aredefinitely influenced by methodological considerations.Next, characteristics of “good” software will be discussed according to thework of Bertrand Meyer [Mey00]. After that, language features will be examinedfor supporting the methodology – through numerous programming languages.Software quality is influenced by many factors. One part of these – suchas reliability, speed, or ease of use – are basically perceived by the user of theprogram. Others – such as how easy it is to reuse some parts of it for a different,but similar problem – affect program developers.Corre tnessCorrectness of the program product means that the program solves exactly theproblem and fits the desired specification. This is the first and most importantcriterion, since if a program is not working like it should, other requirementsdo not really count. The elementary basis for this is the precise and the mostcomplete specification.ReliabilityA program is called reliable if it is correct, and abnormal – not described inthe specification – circumstances do not lead to catastrophe, but are handled insome “reasonable” way.This definition shows, that reliability is by far not as a precise notion ascorrectness. One could say, of course with a more specific specification reliabilitywould mean correctness exactly, but in practice there are always cases which arenot covered by specification explicitly. That is why reliability is of high priorityfor the program product quality.MaintainabilityMaintainability refers to how easy it is to adjust the program product to specification changes.The users often demand further development, modification, adjustment of theprogram product to new external conditions. According to some surveys 70 %of program product costs are spent on maintenance, so it is understandablethat this requirement significantly affects the quality of the program. (This is

Introdu tionrelevant especially if developing big programs and program systems, since forsmall programs usually no change is too complex.)To increase maintainability, design simplicity and decentralization (to haveindependent modules) can be seen as the two most important basic principles.ReusabilityReusability is the feature of the software products, that they can be partly or asa whole reused in new applications.This is different to maintainability, since the same specification was modifiedthere, but now the experience should be utilized, that many elements of softwaresystems follow common patterns, and reimplementing already solved problemsshould be avoided.This question is particularly important, not only when producing individualprogram products, but for a global optimization of software development, asthe more reusable components are available to help problem solving, the moreenergy remains to improve other quality characteristics (at the same costs).CompatibilityCompatibility shows how easy it is to combine the software products with eachother. Programs are not developed isolated, so efficiency can go up by ordersof magnitude, if ready software can be simply connected to other systems.(Communication between programs is based on some standards, such as, forexample, in Unix.)Other hara teristi sFrom the quality characteristics of the program product, portability, efficiency,user friendliness, testability, clarity etc. are also important to pay attention to.Portability regards how easy it is to port the program to another machine,configuration or operating system – usually to have it run in different runtimeenvironments.The efficiency of a program is proportional to the running time and usedmemory size – the faster, or the less memory is used, the more efficient it is.(These requirements often contradict each other, a faster run is often set off bybigger memory requirements, and vice versa.)The user friendliness is very important for the user: this requires data inputto be logical and simple, the output of the results must be clearly formatted.Testability and clarity are important for the developers and maintainers ofthe program, without these the reliability of the program cannot be guaranteed. 3

4 Introdu tionAspe ts of software designSome of these requirements – the improvement of correctness and reliability– require primarily the development of specification tools. The easier it is toverify if a piece of program code is really an implementation according to thespecification, the easier it will be to developed correct and reliable programs.The main role here have programming language features for specification (typeinvariant, pre- and postconditions) descriptions – this is supported for exampleby Eiffel [Mey00], by Ada 2012 [Nyek98] etc.Implementation of another group of requirements – mainly maintainability,reusability and compatibility – can be best supported by designing the programsas independent program units having well defined interconnections. This is thebasis of the so called modular design. (A module here is not a programminglanguage concept, but a unit of the design.) This question will be handled inmore detail in Chapter 9.3.Our goal is to examine the features of different programming languages tosupport professional programmers in developing reliable software of good quality.Study of the tools of programming languagesIt is a natural question, why it is not enough to know one programming language,for what purpose it is good to deal with all the possible features of differentprogramming languages. In the following – primarily based on the work ofRobert W. Sebesta [Seb13] – we will try to summarize the advantages comingfrom this:In rease of the expressive powerOur thinking and even abstraction skills are strongly influenced by the possibilities of the language used. Only that can be expressed, for which there arewords. Likewise during program development and designing the solution, theknowledge of diverse programming language features can help programmers towiden their horizon. This is also true if a particular language must be used, sincegood principles can be applied in any environments.Choosing the appropriate programming languageMany programmers have learnt programming through one or two languages.Others know older languages which are now considered obsolete, and they arenot familiar with the features of modern languages. This could result in notselecting the most appropriate language if there would be more programminglanguages as options to choose from for a new task – since they do not know thepossibilities the other languages could offer. If these programmers would know

Introdu tionthe unique features of the available tools, they could make considerably betterdecisions.Better attainment of new toolsNewer and newer programming languages will appear, thus quality programmingrequires continuous learning. The more the basic elements of the programminglanguages are known, the easier it will be to learn and keep up with progress.In our book most examples are in Ada, C/C or Java language for certainlanguage constructs, there are only a few chapters (except of course those aboutlogical and functional programming) where these languages are not referencedin almost every paragraph.Our book is aimed at facilitating primarily, the studies of unive

1.3. The evolution of programming languages 15 The early years 15 The move to higher-level languages 16 The future of programming languages 19 1.4. Programming language categories 20 Imperative or procedural languages 21 Applicative or functional languages 21 Rule-based or logical languages 22 Object-oriented .