The book "Theory and practice of programming languages. Textbook for high schools. 2nd ed. 3rd generation standard "

    imageThe textbook is devoted to a systematic presentation of the theory and practice of programming languages. It reflects the classical content of the discipline in programming languages. All difficult questions are illustrated by 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: theory of formal languages, theory of automata and formal languages, programming languages, programming, object-oriented programming, logical and functional programming, theory of computational processes.

    The new edition discusses the characteristics, as well as the latest development trends, of high-level universal programming languages ​​such as Scala, Go and Swift; The main features of the latest standards of the classical languages ​​C ++, Java and C # are explained: lambda expressions in all these languages, the reference type rvalue and the semantics of movement in C ++ 11, the covariance and contravariance of generic templates in C #; the Ruby scripting language has been significantly expanded; its blocks, single inheritance and mixing mechanisms, and duck typing are considered; Added description of the event apparatus and event-based programming; The application of the functional programming style in scripting and object-oriented languages ​​of Python, Ruby, C #, Java, C ++, Scala, Go and Swift is shown.

    Excerpt from a book. Scala language

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

    • The language for programming component software should be scalable (it should 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 fuse these programming paradigms. In the statically typed languages ​​Scala refers to, 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 strongly typed multi-paradigm language that supports functional, object-oriented, and parallel programming. Designed to be implemented on top of the Java virtual machine and partially motivated by the known flaws of the Java language. Provides the most aggressive integration of functional characteristics into an imperative language. It has functions of the first class and higher order, a local type inference mechanism, deferred (lazy) calculations, pattern matching, currying, tail recursion, developed generic tools (with covariance and contravariance), message-based parallelism, trait-based inheritance (which something between classes and interfaces). Vigorously used both in industry and in science.

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

    Of course, Java programmers will be greatly surprised that in Scala, functions are also objects. However, in Scala, a function can be passed as an argument, stored as a variable, or returned from another function. This ability to manipulate functions like ordinary variables is the cornerstone of functional programming, the essence of which is to work with immutable variables.

    The function definition is preceded by the def keyword. Class definitions begin with the reserved word class. A class can prevent further subclassing by using the reserved word final. Like the object oriented languages ​​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 uses trait-based mixed inheritance, which provides for 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 traits. Traits can also have relationships with the parent class and subclass. A trait declaration begins with the keyword trait. The body of the trait is executed when an instance of the class that uses this trait 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 located in the body of the class definition. When an instance of the class is created, each field corresponding to a parameter in the parameter list is automatically initialized by the parameter. 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 visibility rules are similar to Java with some variations. Unlike C ++, Scala defaults to “public” visibility. Visibility is controlled by the protected and private keywords. Visibility is indicated at the beginning of declarations of functions, variables or traits. Using private [this] closes the declaration for a specific instance within the class.

    Method definitions are considered ordinary functions, starting with the def keyword, followed by optional argument lists, a colon “:”, and the type of the method return value. Abstract is a method that does not have a body. Methods can be nested together.

    To illustrate, imagine 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 ( +, +
                      def subtract(that: Complex_number): Complex_number =
                           new Complex( -, -

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

    After loading this fragment into 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 in the language much less frequently: it is not put at the end of the statement if it is written alone in a line. If a line contains more than one statement, a semicolon is required. Scala supports both mutable and immutable data structures. The language provides polymorphism, and if the type of a variable is not specified, then it is displayed 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 for functional programming, and arrays are used for imperative programming. Sets and associative arrays can be created both mutable and immutable using traits. Recall that traits are abstract interfaces that extend the content of objects. For example, if there is a “vehicle” class and a “four-wheel” trait that extends vehicles, then the car corresponds to the “vehicle” class with the addition of a “four-wheel” trait. In the case of sets and associative arrays, associating “mutable” and “immutable” traits with a class, a set or associative array provides

    An 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, declaring val: studentNames = new array [String] (20) will create an array object containing 20 rows. Its strings can be accessed using studentNames (i), where i is an integer index variable.

    Lists can be declared in the form of 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. The two lists xl and yl are connected using the ":::" symbol. For example, List (1, 2) ::: List (3, 4, 5) creates List (1, 2, 3, 4, 5).

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

    Consider another example 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 an integer. A recursive function call is provided.

    Scala is a block-structured language where functions can be nested inside other functions. Local variables have a 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 at the suggestion import. By default, Scala imports all Java class libraries and any predefined library in Scala before running the program. To pass parameters, Scala uses pass by value, as well as pass by name. The syntax for passing by name is:: '=>', while the syntax for passing by value is:. Scala uses Java exception handling capabilities.

    Scala code examples

    def add7(n: Int): Int = {n + 7} // функция добавляет 7 к числу

    The add7 function adds 7 to the input parameter n and returns a value. Note that the type of the parameter and the type of the result of the function are explicitly declared. 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 add7 function 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 the 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 the local mutable variables a and b to calculate the value of the function xn. The value accumulates in battery b and finally returns after the while loop completes.

    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 a list using a recursive call in the rest of the list. The built-in isEmpty method is used to check for an empty list, the head method is used to access the first element of the list, and the tail method provides access to the rest of the list.

    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 provides the ability to apply the apply_all functional form. Here, in the body of the function, the parameter (xl) is first written, then the higher-order display function (map), and then the function name (my_func). In this case, apply_all (int_square, List (1, 2, 3)) will generate a list of List (1, 4, 9). Note the type declaration method for the my_func function. The function type 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 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.


    Sokolov B.V., Doctor of Technical Sciences , Professor, Head of the Laboratory of Information Technologies
    in System Analysis and Modeling of the St. Petersburg Institute of Informatics
    and Automation of the Russian Academy of Sciences;

    Pasmurov A. Ya., Doctor of Engineering, Associate Professor, senior member of IEEE, Head of the Training Center of FSUE
    ZashchitaInfoTrans of the Ministry of Transport of the Russian Federation, St. Petersburg Branch.

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

    For Khabrozhiteley 20% discount on the coupon - Orlov

    Also popular now: