The book "Theory and practice of programming languages. Textbook for universities. 2nd ed. Standard 3rd generation "

The textbook is devoted to the systematic presentation of the theory and practice of programming languages. It reflects the classical content of the discipline in programming languages. All complex questions are illustrated with complete examples. In addition, it offers a full range of tasks and exercises on key issues. The textbook covers the basic sections of the following disciplines: the theory of formal languages, the theory of automata and formal languages, programming languages, programming, object-oriented programming, logical and functional programming, the theory of computational processes.

The new edition discusses the characteristics, as well as the latest trends in the development of high-level universal programming languages ​​such as Scala, Go and Swift; explains the main features of the latest standards of classical languages ​​C ++, Java, and C #: lambda expressions in all these languages, the reference type rvalue and the semantics of displacement in C ++ 11, the covariance and countervariance of generic patterns in C #; significantly expanded the presentation of the scripting language Ruby, considered its blocks, the mechanisms of single inheritance and mixing, as well as duck typing; added description of the event system and event-based programming; shows the use of functional programming style in scripting and object-oriented languages ​​of Python, Ruby, C #, Java, C ++, Scala, Go and Swift.

Excerpt from a book. Scala language

The language was created at the Swiss Polytechnic School of Lausanne (2004, the main author is Martin Oderski). It was the result of research aimed at developing improved language support for component software. Two ideas were taken as a basis:

• A language for programming component software must be scalable (it must be possible to describe both small and large fragments of programs using the same concepts). Therefore, attention was focused on the mechanisms of abstraction, composition and decomposition, and not on the introduction of a large number of structures that can be useful only at any one level of scaling.
')
• Scalable component support is provided by a language that combines both object-oriented and functional programming. Some of Scala's core innovations are concepts that are a blend of these programming paradigms. In statically typed languages, to which Scala belongs, these paradigms have so far been completely separated.

Scala was released for use on the JVM platform in January 2004 and on the .NET platform in June 2004. In addition, a number of Scala compilers are being actively developed.

Thus, Scala is a multi-paradigm language with strong typing, which supports functional, object-oriented and parallel programming. Designed to be implemented on top of the Java virtual machine and partly motivated by the well known flaws of the Java language. Provides the most aggressive integration of functional characteristics into an imperative language. It has first class and higher order functions, a local type inference mechanism, delayed (lazy) calculations, pattern matching, carrization, tail recursion, developed generic tools (with covariance and countervariance), message-based parallelism, trait-based inheritance (which is the average between classes and interfaces). Vigorously used in industry and in science. The development is funded by the European Research Council.

Scala uses a pure object-oriented model similar to that used in Smalltalk: each value is an object (and the numbers and results of functions), and each operation is sending a message, calling an object's method. For example, the addition of 2 + 3 is interpreted as 2. + (3), that is, as a call in the receiver "2" of the method "+" with an argument of "3". Here, the number 3 is considered as the source object. This differs from Java because Java has primitive types (for example, boolean or int) and reference types, and there is no possibility to work with functions as with values.

Of course, Java programmers will be very surprised that functions in Scala are also objects. However, you can pass a function as an argument to Scala, save it as a variable, or return it from another function. Such an opportunity to manipulate functions as ordinary variables is the cornerstone of functional programming, the essence of which is the work of functions with immutable variables.

Before defining a function, the keyword def is set. Class definitions begin with the reserved word class. A class can prevent further subclassing by using the reserved word final. Like object-oriented languages ​​like C ++, Java, C #, an instance of a class can refer to itself using the word this. Scala allows overloaded methods. As in Java, the extend keyword declares that a class is a subclass of another class. Scala does not support multiple inheritance. Instead, the language applies trait-based mixed inheritance, which includes the inclusion of common attributes and methods in several subclasses. Traits can extend classes or other traits. A subclass in Scala can inherit methods from both the parent class and the traits. Traits can also have relationships with the parent class and subclass. A trait declaration begins with the trait keyword. The body of a treyt is executed when an instance of the class that uses this treyt is created. The default parent for a class or trait is the AnyRef class, a direct descendant of the Any class.

The constructor in Scala is placed in the body of the class definition. When an instance of a class is created, each field corresponding to a parameter in the parameter list is initialized by a parameter automatically. In general, an explicit constructor is not needed. A constructor in a derived class must call one of the constructors of the parent class. Traits use only primary constructors with no arguments. Traits cannot pass arguments to the constructor of the parent class.

Scala's visibility rules are similar to Java with some variations. Unlike C ++, Scala sets the default public visibility. Visibility is governed by the keywords protected and private. Visibility is indicated at the beginning of declarations of functions, variables or traits. Using private [this] closes the declaration for a specific instance inside the class.

Method definitions are considered normal functions, starting with the keyword def, followed by optional argument lists, the colon character ":", and the return type of the method. Abstract is the method that has no body. Methods can be invested in each other.

For illustration, let’s represent an abstract class for a complex number:

class Complex_number (first: Double, second: Double) { val re = first val im = second override def toString = re + " + " im + "i" def add(that: Complex_number): Complex_number = new Complex_number (this.re + that.re, this.im + that.im) def subtract(that: Complex_number): Complex_number = new Complex(this.re - that.re, this.im - that.im) } 

The class definition includes only two attributes: re (real part) and im (imaginary part). Using the override property, the toString operation is overridden. This is done to make printing easier. Two abstract operations are specified: addition and subtraction. Abstract operations are written in the form of two methods. Each method creates a new complex number that is automatically printed to the console using the overridden toString method.

After downloading this fragment to the Scala interpreter, you can run the following commands:

 val c1 = new Complex_number(3, 4) //   3.0 + 4.0 i val c2 = new Complex_number(4, 5) //    4.0 + 5.0 i c1 add c2 //    7.0 + 9.0 i c1 subtract c2 //    -1.0 + – 1.0 

The semicolon is used much less frequently in the language: it is not put at the end of the statement if it is written alone in a line. If the line contains more than one operator, the semicolon is required. Scala supports both mutable and immutable data structures. The language provides polymorphism, and if the variable type is not specified, it is derived based on the value specified for the variable.

Scala implements an extensive set of data types: arrays, associative arrays, lists, tuples, and sets. Arrays are mutable objects, and lists are immutable objects. Lists are used in functional programming, and arrays are used in imperative programming. Sets and associative arrays can be created both mutable and immutable with the help of traits. Recall that traits are abstract interfaces that extend the content of objects. For example, if there is a class "vehicle" and the treyt "four-wheel", expanding vehicles, then the car corresponds to the class "vehicle" with the addition of the trait "four-wheel". In the case of sets and associative arrays, the binding of “changeable” and “unchangeable” traits to the class set or associative array provides, ultimately, their mutability or immutability.

The integer array is declared as Array [Int] (4). This means that the object is an array containing four integers. Variable indices are written inside a pair of parentheses. Since each data structure is an object, an array is created using the new constructor. For example, the declaration val: studentNames = new array [String] (20) will create an array object containing 20 lines. Its strings can be accessed with studentNames (i), where i is an integer index variable.

Lists can be declared in the form of a List (1, 2, 3) or as several elements connected by the symbol "::". For example, List (1, 2, 3) can be written as 1 :: 2 :: 3 :: Nil. Two lists xl and yl are connected with the symbol ":::". For example, List (1, 2) ::: List (3, 4, 5) creates a List (1, 2, 3, 4, 5).

The Scala language supports if-then-else expressions, case classes, while-loop statements, do-while-loop statements, the foreachloop iterator, defines forloop iteration, and recursive function calls. By passing a function as a parameter to another function, you can model the composition. In addition, Scala supports updating in indexed variables, which allows you to develop programs based on normal iterations.

Consider another example of a function declaration:

 def factorial(n: Int): Int = { if (n == 0) 1 else n * factorial(n – 1) } 

Here the function describes the factorial and declares the type of the argument and the type of the result as integer. A recursive function call is provided.

Scala is a block-structured language where functions can be embedded inside other functions. Local variables have scope within the blocks where they were declared. Inside a nested block, variables declared in external blocks can be overridden. Scala supports the concept of a module using Java packages and can import methods using the import clause. By default, Scala imports all Java class libraries and any predefined library into Scala before executing the program. To pass parameters, Scala uses pass by value as well as pass by name. The syntax of the transfer by name is:: '=>', whereas the syntax of transfer by value is:. Scala uses Java exception handling.

Scala code samples

 def add7(n: Int): Int = {n + 7} //   7   

The add7 function adds 7 to the input parameter n and returns the value. Please note that the parameter type and the result type of the function are declared explicitly. The body of the function is a block and is enclosed in braces.

 def int_square(x: Int): Int = {x * x} //     def square_add(x: Int): Int = int_square(add7(x)) //  

The square_add function shows the composition of two functions: square and add7. First, the function add7 is used to generate a number that is 7 more than the input parameter, and then the generated value is squared. For example, square_add (5) is equivalent to square (5 + 7) = 144.

 def power_rec(x: Double, n:Int): Double = {if (n == 0) 1 else x * power_rec(x, n-1)} // if-then-else   

The power_rec function illustrates the use of an if-then-else expression and recursion in Scala. Note that the predicate is enclosed in parentheses and there is no mutation (change in the values ​​of variables).

 def power_iter(x : Int, n: Int): Int = //  power { var a = n; var b = 1; while(a > 0 ) {b = x * b; a = a - 1}//   } 

In contrast, the power_iter function uses local variable variables a and b to calculate the value of the function xn. The value accumulates in battery b and finally returns after the end of the while loop.

 def sum_list(xl:List[Int]): Int = //    { if (xs.isEmpty) 0 else xl.head + sum_list(xs.tail) } 

The sum_list function adds all integers to the list using a recursive call in the rest of the list. The built-in isEmpty method is used to check the empty list, the head method is used to access the first list item, and the tail method provides access to the rest of the list items.

 def apply_all(my_func:Int => Int, xl:List[Int]): List[Int] = {xl map my_func} 

Scala uses the built-in map display function, which allows the use of the apply_all functional form. Here, in the body of the function, the parameter (xl) is first written, then the display function of the highest order (map), and then the name of the function (my_func). In this case, apply_all (int_square, List (1, 2, 3)) will generate a List (1, 4, 9). Note the type declaration method for the my_func function. The type of the function is declared as Int => Int, which means that it takes an input argument of type integer and generates an output value of type integer.

 def construct(my_funcs:List[Int => Int], n:Int): List[Int] = //  { if (my_funcs.isEmpty) Nil else my_funcs.head(n)::construct(my_funcs.tail, n) } 

Finally, the construct function takes a sequence of functions applied to the same argument and generates a sequence of output values. For example, construct (List (add7, int_square), 5) will generate a List (12, 25). A program with the construct function returns a null list if the list of functions is empty. Otherwise, it calls the remaining functions recursively from the list and combines the result of applying the first function with the rest of the output sequence obtained by applying the remaining functions to the same argument.

Reviewers:

B. Sokolov, Ph.D., Professor, Head of the Laboratory of Information Technologies
in systems analysis and modeling of the St. Petersburg Institute of Informatics
and automation RAS;

Pasmurov A. Ya., Ph.D., associate professor, senior member of IEEE, head of the FSUE training center
ZaschitaInfoTrans, Ministry of Transport of the Russian Federation, St. Petersburg branch.

»More information about the book can be found on the publisher's website.
» Table of Contents
» Excerpt

For Habrozhiteley a 20% discount on the coupon - Orlov