Книга «Теория и практика языков программирования. Учебник для вузов. 2-е изд. Стандарт 3-го поколения»

    image Учебник посвящен систематическому изложению теории и практики языков программирования. Он отражает классическое содержание учебной дисциплины по языкам программирования. Все сложные вопросы поясняются законченными примерами. Кроме того, здесь предлагается полный комплекс задач и упражнений по узловым вопросам. Учебник охватывает базисные разделы следующих дисциплин: теория формальных языков, теория автоматов и формальных языков, языки программирования, программирование, объектно-ориентированное программирование, логическое и функциональное программирование, теория вычислительных процессов.

    В новом издании обсуждаются характеристики, а также последние тенденции развития универсальных языков программирования высокого уровня, таких как Scala, Go и Swift; поясняются главные особенности последних стандартов классических языков C++, Java и C#: лямбда-выражения во всех этих языках, cсылочный тип rvalue и семантика перемещения в языке C++ 11, ковариантность и контрвариантность родовых шаблонов в C#; существенно расширено представление скриптового языка Ruby, рассматриваются его блоки, механизмы единичного наследования и подмешивания, а также утиной типизации; добавлено описание аппарата событий и программирования на основе событий; показано применение стиля функционального программирования в скриптовых и объектно-ориентированных языках Python, Ruby, C#, Java, C++, Scala, Go и Swift.

    Отрывок из книги. Язык Scala


    Язык был создан в Швейцарской политехнической школе Лозанны (2004 год, главный автор — Мартин Одерски). Он стал результатом исследований, направленных на разработку улучшенной языковой поддержки компонентного ПО. За основу были взяты две идеи:

    • Язык для программирования компонентного ПО должен быть масштабируемым (должна обеспечиваться возможность с помощью одних и тех же концепций описывать как малые, так и большие фрагменты программ). Поэтому внимание было сконцентрировано на механизмах абстракции, композиции и декомпозиции, а не на введении большого количества конструкций, которые могут быть полезными только на каком-то одном уровне масштабирования.

    • Масштабируемая поддержка компонентов обеспечивается языком, объединяющим как объектно-ориентированное, так и функциональное программирование. Некоторые из базовых новшеств Scala представляют собой концепции, являющиеся сплавом этих парадигм программирования. В статически типизированных языках, к которым относится Scala, данные парадигмы до сих пор были полностью разделены.

    Scala была выпущена для использования на платформе JVM в январе 2004 года и на платформе .NET в июне 2004 года. Кроме того, в настоящее время активно разрабатывается целый ряд Scala-компиляторов.

    Таким образом, Scala — это мультипарадигменный язык со строгой типизацией, который поддерживает функциональное, объектно-ориентированное и параллельное программирование. Предназначен для реализации на вершине виртуальной машины Java и частично мотивирован известными недостатками языка Java. Обеспечивает наиболее агрессивную интеграцию функциональных характеристик в императивный язык. Имеет функции первого класса и высшего порядка, механизм логического вывода локального типа, отложенные (ленивые) вычисления, сопоставление с образцом, карризацию, хвостовую рекурсию, развитые родовые средства (с ковариантностью и контрвариантностью), параллелизм на основе сообщений, наследование на основе трейтов (что-то среднее между классами и интерфейсами). Энергично используется как в промышленности, так и в науке. Развитие финансируется Европейским исследовательским советом.

    В Scala используется чистая объектно-ориентированная модель, похожая на применяемую в Smalltalk: каждое значение является объектом (и числа, и результаты функций), а каждая операция — это отправка сообщения, вызов метода объекта. Например, сложение 2 + 3 интерпретируется как 2.+(3), то есть как вызов в объектеприемнике «2» метода «+» с аргументом «3». Здесь в качестве объекта-источника рассматривается число 3. Этим Scala отличается от Java, поскольку в Java разделены примитивные типы (например, boolean или int) и ссылочные типы, а также нет возможности работать с функциями как со значениями.

    Конечно, Java-программисты сильно удивятся тому, что в Scala функции также являются объектами. Тем не менее в Scala функцию можно передавать как аргумент, сохранять в качестве переменной или возвращать из другой функции. Такая возможность манипулировать функциями как обычными переменными является краеугольным камнем функционального программирования, суть которого состоит в работе функций с неизменяемыми переменными.

    Перед определением функции ставится ключевое слово def. Определения классов начинаются с зарезервированного слова class. Класс может предотвратить дальнейшее создание подклассов, употребляя зарезервированное слово final. Подобно объектно-ориентированным языкам C++, Java, C#, экземпляр класса может ссылаться на себя, используя слово this. Scala допускает перегруженные методы. Как и в Java, ключевое слово extend объявляет, что класс является подклассом другого класса. Scala не поддерживает множественное наследование. Вместо этого язык применяет смешанное наследование на базе трейтов, обеспечивающих включения общих атрибутов и методов в несколько подклассов. Трейты могут расширять классы или другие трейты. Подкласс в Scala может наследовать методы как от родительского класса, так и от трейтов. Трейты могут также иметь отношения с родительским классом и подклассом. Объявление трейта начинается с ключевого слова trait. Тело трейта выполняется, когда создается экземпляр класса, задействующего этот трейт. Родительским по умолчанию для класса или трейта является класс AnyRef, прямой потомок класса Any.

    Конструктор в Scala размещается в теле определения класса. Когда создается экземпляр класса, каждое поле, соответствующее параметру в списке параметров, инициализируется параметром автоматически. В общем случае явный конструктор не нужен. Конструктор в производном классе должен вызывать один из конструкторов родительского класса. Трейты используют только первичные конструкторы без аргументов. Трейты не могут передавать аргументы конструктору родительского класса.

    Правила видимости в Scala похожи на Java с некоторыми вариациями. В отличие от C++, по умолчанию в Scala задается «публичная» видимость. Видимость регулируется с помощью ключевых слов protected и private. Видимость указывается в начале объявлений функций, переменных или трейтов. Применение private [this] закрывает объявление для конкретного экземпляра внутри класса.

    Определения методов считаются обычными функциями, начинаются с ключевого слова def, за которым следуют необязательные списки аргументов, символ двоеточия «:» и тип возвращаемого значения метода. Абстрактным является метод, у которого отсутствует тело. Методы могут вкладываться друг в друга.

    Для иллюстрации представим абстрактный класс для комплексного числа:

    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)
    }

    Определение класса включает только два атрибута: re (действительная часть) и im (мнимая часть). С помощью свойства override операция toString переопределена. Это сделано для облегчения печати результата. Заданы две абстрактные операции: сложение и вычитание. Абстрактные операции записываются в виде двух методов. Каждый метод создает новое комплексное число, которое автоматически печатается на консоли с помощью переопределенного метода toString.

    После загрузки этого фрагмента в интерпретатор Scala можно выполнить следующие команды:

    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

    Точка с запятой используется в языке значительно реже: она не ставится в конце оператора, если он записан один в строке. Если строка содержит более одного оператора, точка с запятой обязательна. Scala поддерживает как изменяемые, так и неизменяемые структуры данных Язык обеспечивает полиморфизм, и если тип переменной не указан, то он выводится на основе значения, заданного для переменной.

    Scala реализует обширный набор типов данных: массивы, ассоциативные массивы, списки, кортежи и множества. Массивы являются изменяемыми объектами, а списки — неизменяемыми объектами. Списки используются при функциональном программировании, а массивы — при императивном программировании. Множества и ассоциативные массивы могут создаваться как изменяемыми, так и неизменными с помощью трейтов. Напомним, что трейты — это абстрактные интерфейсы, которые расширяют содержание объектов. Например, если имеется класс «транспортное средство» и трейт «четырехколесный», расширяющий транспортные средства, то автомобиль соответствует классу «транспортное средство» с добавлением трейта «четырехколесный». В случае множеств и ассоциативных массивов связывание «изменяемого» и «неизменяемого» трейтов с классом множество или ассоциативный массив обеспечивает, в конечном счете, их изменяемость или неизменность.

    Целочисленный массив объявляется как Array [Int] (4). Это означает, что объект является массивом, содержащим четыре целых числа. Индексы переменных записываются внутри пары круглых скобок. Поскольку каждая структура данных является объектом, массив создается с использованием конструктора new. Например, объявление val: studentNames = new array [String] (20) создаст объект массива, содержащий 20 строк. К его строкам можно получить доступ с помощью studentNames(i), где i — индексная переменная типа integer.

    Списки могут быть объявлены в форме List (1, 2, 3) или как несколько элементов, соединенных символом «::». Например, List (1, 2, 3) можно записать как 1 :: 2 :: 3 :: Nil. Два списка xl и yl соединяются с помощью символа «:::». Например, List (1, 2) ::: List (3, 4, 5) создают List (1, 2, 3, 4, 5).

    Язык Scala поддерживает выражения if-then-else, классы case, операторы while-loop, do-while-loop, итератор foreachloop, определяет итерацию forloop и рекурсивные вызовы функций. Передавая функцию в качестве параметра в другую функцию, можно смоделировать композицию. Кроме того, Scala поддерживает обновление в индексированных переменных, что позволяет разрабатывать программы на основе обычных итераций.

    Рассмотрим еще один пример объявления функции:

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

    Здесь функция описывает факториал и объявляет тип аргумента и тип результата как целочисленный. Предусмотрен рекурсивный вызов функции.

    Scala является блочно-структурированным языком, где функции могут вкладываться внутрь других функций. Локальные переменные имеют область действия внутри блоков, где они были объявлены. Внутри вложенного блока переменные, объявленные во внешних блоках, могут быть перекрыты. Scala поддерживает концепцию модуля с использованием пакетов Java и может импортировать методы по предложению import. По умолчанию Scala импортирует все библиотеки классов Java и любую предопределенную библиотеку в Scala перед выполнением программы. Для передачи параметров Scala использует передачу по значению, а также передачу по имени. Синтаксис передачи по имени: : ‘=>’ , тогда как синтаксис передачи по значению имеет вид : . Scala использует возможности обработки исключений Java.

    Примеры программного кода на Scala


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

    Функция add7 добавляет 7 к входному параметру n и возвращает значение. Обратите внимание, что тип параметра и тип результата функции объявлены явно. Тело функции является блоком и заключено в фигурные скобки.

    def int_square(x: Int): Int = {x * x} // возведение в квадрат целых
    def square_add(x: Int): Int = int_square(add7(x)) // композиция

    Функция square_add показывает композицию двух функций: square и add7. Сначала функция add7 применяется для генерации числа, которое на 7 больше входного параметра, а затем сгенерированное значение возводится в квадрат. Например, square_add (5) эквивалентно 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 и рекурсия

    Функция power_rec иллюстрирует использование выражения if-then-else и рекурсии в Scala. Обратите внимание, что предикат заключен в круглые скобки и нет никакой мутации (изменения значений переменных).

    def power_iter(x : Int, n: Int): Int = //итерационная версия power
    {                var a = n; var b = 1;
                      while(a > 0 ) {b = x * b; a = a - 1}// обновление переменных
    }

    Напротив, функция power_iter использует локальные изменяемые переменные a и b для вычисления значения функции xn. Значение накапливается в аккумуляторе b и, наконец, возвращается после завершения цикла while.

    def sum_list(xl:List[Int]): Int = // рекурсия над списками
    {                if (xs.isEmpty) 0
                       else xl.head + sum_list(xs.tail)
    }

    Функция sum_list добавляет все целые числа в список, используя рекурсивный вызов в остальной части списка. Встроенный метод isEmpty используется для проверки пустого списка, метод head применяется для доступа к первому элементу списка, а метод tail обеспечивает доступ к остальным элементам списка.

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

    Scala использует встроенную функцию отображения map, которая обеспечивает возможность применения функциональной формы apply_all. Здесь в теле функции сначала записывается параметр (xl), затем функция отображения высшего порядка (map), а затем имя функции (my_func). В этом случае apply_all (int_square, List (1, 2, 3)) будет генерировать список List (1, 4, 9). Следует отметить способ объявления типа для функции my_func. Тип функции объявлен как Int => Int, что означает, что он принимает входной аргумент типа integer и генерирует выходное значение типа 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)
    }

    Наконец, функция construct берет последовательность функций, применяемых к одному и тому же аргументу, и генерирует последовательность выходных значений. Например, construct (List (add7, int_square), 5) будет генерировать список List (12, 25). Программа с функцией construct возвращает нулевой список, если список функций пуст. В противном случае она вызывает рекурсивно из списка остальные функции и объединяет результат применения первой функции с остальной частью выходной последовательности, полученной путем применения остальных функций к этому же аргументу.

    Рецензенты:


    Соколов Б. В., д. т. н., профессор, руководитель лаборатории информационных технологий
    в системном анализе и моделировании Санкт-Петербургского института информатики
    и автоматизации РАН;

    Пасмуров А. Я., д. т. н., доцент, senior member of IEEE, руководитель учебного центра ФГУП
    «ЗащитаИнфоТранс» Министерства транспорта РФ, Санкт-Петербургский филиал.

    » Более подробно с книгой можно ознакомиться на сайте издательства
    » Оглавление
    » Отрывок

    Для Хаброжителей скидка 20% по купону — Орлов

    Comments 4

      +2
      Больше книг по функциональному программированию это отлично, но имеется пустота по продвинутой теории: скажем, по дискретной математике книг достаточно, а вот по теории категорий вообще ничего! Рассмотрите пожалуйста возможность переиздать «Категории для работающего математика» Маклейна, полагаю, будут благодарны как математики, так и программисты, изучающие Haskell, Scala и т.п.
        +1
        В книге, посвященной языкам программирования в общем виде, не упомянуть Haskell. Тем более ни слова свежие тенденции — про зависимые типы, хотя бы path depended types в Scala могли бы упомянуть. Хорошо хоть ML вспомнили.
          0
          Цена электронной книги кусается.
            0
            Напомнило «Concepts, Techniques, and Models of Computer Programming», думал это перевод. Только авторы вместо рассмотрения разных языков реализуют один мульти-парадигменный Oz. Я думаю, это лучшая книга на эту тему.

            Only users with full accounts can post comments. Log in, please.