Сообщений 17    Оценка 970 [+1/-0]         Оценить

Язык Nemerle

Часть 2

Автор: Чистяков Владислав Юрьевич

Опубликовано: 30.06.2010
Исправлено: 10.12.2016
Версия текста: 1.1

Переменные

Переменные предназначены для хранения промежуточных результатов вычислений.

Например, программа, переводящая градусы Цельсия в градусы Фаренгейта из предыдущего раздела:

      using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def loop(fahrenheit)
{
  WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", 
    fahrenheit, fahrenheitToCelsius(fahrenheit));

  match (fahrenheit >= 0 && fahrenheit < 300)
  {
    | true  => loop(fahrenheit + 20);
    | false => ()
  }
}

loop(0);

может быть переписана с использованием переменной:

      using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

mutable fahrenheit = 0;

def loop()
{
  match (fahrenheit >= 0 && fahrenheit < 300)
  {
    | true  => 
      WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", 
        fahrenheit, fahrenheitToCelsius(fahrenheit));

      fahrenheit = fahrenheit + 20;
      loop();
      
    | false => ()
  }
}

loop();

В примере выше «fahrenheit» – это изменяемая переменная.

В строке:

      mutable fahrenheit = 0;

дается объявление (definition) изменяемой переменной. С этого места и ниже переменная может быть использована в программе. Модификатор mutable указывает на то, что это изменяемая переменная, т.е. переменная значение которой можно многократно изменять.

При объявлении переменной можно указать ее тип (выделено в коде):

      mutable fahrenheit : int = 0;

Если тип не указан, то, как и в случае параметров локальных функций, он выводится из инициализации или использования. Так как переменной сразу же присваивается значение «0», то переменная автоматически получает тип «int».

Объявление изменяемой переменной может совмещаться с инициализацией переменной (« = 0», в нашем случае). Но изменяемая переменная может и не инициализироваться при объявлении:

      mutable fahrenheit;

В этом случае переменная автоматически инициализируется значением, принятым по умолчанию для типа, который будет выведен для нее компилятором из ее использования (в нашем случае это будет тип «int»). Для всех числовых типов значением по умолчанию является «0».

Явное задание типа переменной никак не зависит от наличия инициализации и наоборот. Так что возможны любые их сочетания.

В строке:

fahrenheit = fahrenheit + 20;

происходит изменение значения переменной – переменная получает значение, равное значению выражения, идущего справа от знака «=». Причем если переменная встречается в правой части выражения, то она заменяется текущим значением (полученным до присвоения ей нового значения). Таким образом, если в переменной fahrenheit в данный момент времени содержится значение «0», то после выполнения этого выражения в нее будет помещено значение «20», а если в ней находится значение «20», то она получит значение «40», и так далее.

Результатом операции присвоения (а именно так называется эта операция) является тип «void». Это означает, что в Nemerle нельзя делать множественные присвоения, как это можно делать в других C-подобных языках (C, C++, C#, ...). Так, если попытаться скомпилировать следующий код:

      mutable x : int;
x = fahrenheit = fahrenheit + 20;

то компилятор выдаст сообщение об ошибке:

Error: expected int, got void in assigned value: void is not a subtype of int

Это происходит именно потому, что выражение «fahrenheit = fahrenheit + 20» имеет тип void.

Область видимости переменных

Переменная видна внутри блока (где она объявлена) с того места, где она объявлена, и ниже, до конца блока (напомню, что блок выделяется в коде фигурными скобками). Ниже приведен псевдокод (т.е. не реальный код, а его подобие), демонстрирующий видимость переменной «x»:

«x» НЕ видна!
{
  «x» НЕ видна!

  mutable x = 0;

  {
    «x» видна

    def func()
    {
      «x» видна
    }
  }
  
  «x» видна
}

«x» НЕ видна!

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

Циклы

Макрос «while»

В большинстве популярных языков программирования для перебора используется не рекурсия (как в наших примерах), а специальные конструкции, называемые циклами. В C-подобных языках наиболее общей и одновременно простой конструкцией цикла является «while». Его синтаксис и семантика очень просты:

        while (условие)
  тело_цикла

Здесь «условие» – это булево выражение (т.е. выражение, тип которого – bool), а «тело_цикла» – это некоторое выражение языка, которое повторяется до тех пор, пока условие истинно (т.е. при вычислении условия возвращает значение true). В качестве тела цикла может выступать блок, что позволяет помещать в тело несколько выражений.

В Nemerle выражение «тело_цикла» обязано быть типа «void», так как цикл не может возвратить значение.

Как я уже говорил, в Nemerle нет циклов, но их, как и многое другое, можно выразить через макросы. Давайте же проделаем это.

Переписав пример перевода градусов Цельсия в градусы Фаренгейта с использованием переменной, мы превратили функцию «loop» в полный аналог цикла. Так что теперь мы можем легко выделить код, отвечающий за организацию цикла, и поместить его в макрос.

Откройте файл MyMacroses.n (который вы создали, выполняя примеры из предыдущей части) и поместите в него следующий код:

        public
        macro While(condition, body)
syntax ("while", "(", condition, ")", body)
{
  <[ 
    def loop() : void
    {
      match ($condition)
      {
        | true => 
          $body;
          loop();
          
        | false => ()
      }
    }
    
    loop();
  ]>
}

Код в квази-цитате очень похож на код из предыдущего примера, в котором условие оператора match заменено «$condition : bool», а код, выводящий значение переменной fahrenheit на экран и изменяющий ее значение, заменен на «$body». Значения «condition» и «body» – это параметры макроса «While». Как говорилось в предыдущем разделе, находящиеся в них выражения подставляются в квази-цитату в тех местах, где на них имеются ссылки (выделено красным).

В общем, все почти как в примере с оператором «&&», за одним небольшим исключением.

Дело в том, что макрос While вводит новый синтаксис! Сейчас я поясню, что это такое.

Как я говорил в предыдущем разделе, применение макроса внутри кода может выглядеть как обращение к функции или как обращение к оператору. Последнее нам совершенно не нужно (цикл не похож на оператор). Так что нам придется использовать макрос как функцию. Если переписать пример, используя макрос While напрямую, без синтаксического расширения, то получится не совсем то, что хотелось получить:

        using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

mutable fahrenheit = 0;

While(fahrenheit >= 0 && fahrenheit < 300,
{
  WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", 
    fahrenheit, fahrenheitToCelsius(fahrenheit));

  fahrenheit = fahrenheit + 20;
});

Хотелось бы в точности воспроизвести синтаксис while из C.

Чтобы это стало возможно, к коду макроса добавлена декларация синтаксиса:

        syntax ("while", "(", condition, ")", body)

Декларация состоит из ключевого слова «syntax» и идущего за ним (в скобках) описания синтаксиса. В описании синтаксиса могут участвовать как статические элементы («while» и скобки в данном случае), так и параметры макроса. При этом параметры макросов рассматриваются как подвыражения. Строковые идентификаторы (вроде приведенного в примере «while») использованные при описании синтаксиса макроса становятся ключевыми словами. Это означает, что в области видимости, где виден макрос, будет нельзя создать переменную или функцию с таким же именем.

Таким образом, описание:

        syntax ("while", "(", condition, ")", body)

аналогично тому, что я приводил ранее:

        while (условие)
  тело_цикла

Использование макроса «while»

После размещения кода макроса в файле MyMacroses.n, его компиляции и подключения полученной сборки (MyMacroses.dll) к основной программе, можно воспользоваться новым синтаксисом и переписать код примера, переводящего градуса Цельсия в градусы Фаренгейта следующим образом:

        using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

mutable fahrenheit = 0;

while (fahrenheit >= 0 && fahrenheit < 300)
{
  WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", 
    fahrenheit, fahrenheitToCelsius(fahrenheit));

  fahrenheit = fahrenheit + 20;
}

Этот пример по-прежнему раскрывается в рекурсивную функцию, но с точки зрения программиста он использует цикл, ничем не отличающийся от цикла «while» из C или C++.

Конечно, писать столь часто используемые конструкции, как операторы «&&», «||», while и т.п. - занятие неблагодарное. Поэтому разработчики Nemerle создали такие реализации и поместили в стандартную библиотеку макросов Nemerle.Macros.dll (которая идет в поставке компилятора). Их исходные коды можно найти здесь.

Макросы из стандартной библиотеки более функциональны. Например, они допускают использование операторов break и continue (как в C). Но о них мы поговорим, когда дойдем до конструкции Nemerle, на которой они реализованы (break и continue также реализуются как макросы).

Списки

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

Например, мы можем сформировать список значений градусов Фаренгейта и написать функцию, преобразующую этот список в список градусов Цельсия. Ну а далее полученный список вывести на консоль или обработать каким-то другим способом. Попробуем решить эту задачу.

Nemerle не имеет встроенных типов данных для работы со списками. Но он позволяет использовать специальные «пользовательские» типы данных для их обработки. Некоторые из этих типов – массивы – предоставляются системой (.Net или Mono), некоторые находятся в стандартных библиотеках системы (такие как динамический массив), а некоторые входят в стандартную библиотеку Nemerle (Nemerle.dll). Мы начнем изучение с типа list[T], реализованного в стандартной библиотеке Nemerle, так как его очень удобно использовать в Nemerle.

Ниже приведен пример реализации все того же примера пересчета градусов Цельсия в градусы Фаренгейта, но оперирующий списками:

      using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def convertFsToCs(fahrenheits)
{
  match (fahrenheits)
  {
    | headFahrenheit :: tailFahrenheits => fahrenheitToCelsius(headFahrenheit) :: convertFsToCs(tailFahrenheits)
    | _                                 => []
  } 
}

def fahrenheits = [0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 
200, 220, 240, 260, 280, 300];
def celsiuses = convertFsToCs(fahrenheits);

WriteLine(celsiuses);

Эта программа выводит на консоль только полученные значения градусов Фаренгейта:

[-17,7777777777778, -6,66666666666667, 4,44444444444444, 15,5555555555556, 
  26,6666666666667, 37,7777777777778, 48,8888888888889, 60, 71,1111111111111,
  82,2222222222222, 93,3333333333333, 104,444444444444, 115,555555555556,
  126,666666666667,  137,777777777778, 148,888888888889]

Консольный вывод у этого варианта не очень красивый, но позже мы и его улучшим.

Пока что давайте разберем код этого примера.

Функция fahrenheitToCelsius не изменилась, так что ее опускаем.

Функция convertFsToCs занимается преобразованием списка целых, содержащего градусы Фаренгейта, в список вещественных чисел (типа double), содержащий градусы Цельсия. Рассмотрение её реализации мы ненадолго отложим и перейдем сразу к использованию этой функции.

Неизменяемая переменная

Строка:

        def fahrenheits = [0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 
200, 220, 240, 260, 280, 300];

задает неизменяемую переменную, ссылающуюся на список градусов Фаренгейта.

Ключевое слово def перед именем (fahrenheits) переменной означает, что переменная является неизменяемой. Можно думать о таких переменных как об имени, сопоставляемом со значением некоторого выражения (в данным случае со списком).

Неизменяемая переменная получает свое значение при инициализации и не меняет его до конца своего срока жизни. Следует понимать, что вы обеспечиваете неизменяемость именно переменной, а не объекта, на который ссылается эта переменная. Если объект допускает изменение, то его можно будет изменить, даже если ссылка на него находится в неизменяемой переменной.

При объявлении неизменяемой переменной можно указать ее тип. Например, следующая строка объявляет и инициализирует неизменяемую переменную «y» типа «double»:

        def y : double = 10;

Ей присваивается значение 10. Литерал «10» имеет тип «int», но так как он присваивается переменной типа «double», то его значение неявно приводится к типу «double». Преобразования производятся во время компиляции. Это означает, что оно не отнимает времени во время исполнения и компилятор контролирует его корректность (в случае ошибки сообщение о ней вам будет выдано во время компиляции).

Имена переменных, функций и макросов

На имена переменных в Nemerle накладывается ряд ограничений.

1.  Имена составляются из букв, цифр или символа подчеркивания «_». Первый символ должен быть буквой или символом подчеркивания.

2. Прописные и строчные буквы различаются. Это означает, что имена «test» , «Test» , «TeSt» , «teSt» – это разные имена. Традиционным для Nemerle является использование стиля кэмэл – «testName» (когда все слова, кроме первого, выделяются большой буквой), для обозначения имен переменных и локальных функций, и стиля паскаль – «TestName» (когда все слова, включая первое, выделяются большими буквами), для обозначения имен типов и их членов, макросов и других публичных названий. Ключевые слова (как встроенные в язык, так и вводимые макросами) принято обозначать строчными буквами, даже если они состоят из двух слов (например, «foreach»).

3. Имена переменных не должны совпадать с ключевыми словами (т.е. со словами, которые зарезервированы.

4. Имена могут начинаться со знака «@». Данный знак указывает комплятору, что это имя, а не ключевое слово. Таким образом, префикс «@» позволяет использовать в качестве имен любые имена, даже если они являются ключевыми словами, причем компилятор Nemerle не учитывает знак «@». Например, «false» – недопустимое имя, но «@false» – допустимое. Таким образом, знак «@» позволяет обходить ограничение, описанное в пункте 3 данного перечисления. Конечно, в программах Nemerle вы будете обязаны всегда добавлять знак «@» перед таким именем, но если это имя будет доступно из другого языка, где оно не является ключевым словом, то к нему моно будет обращаться без «@». Еще одним местом где «@» не будет учитываться являются метаданные, но о них я расскажу только ближе к концу.

Конструирование списка

Конструкция «[ список значении разделенных запятой ]» называется списковым литералом. Списковый литерал позволяет описать статически заданный список (т.е. список значения которого известны в момент написания программы). Элементы списка задаются последовательно слева направо и имеют четкий порядок. Таким образом, «[0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300]» задает список, состоящий из чисел «0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300». Ссылка на этот список помещается в переменную fahrenheits.

Список может быть сконструирован следующими способами:

1. С помощью спискового литерала (именно этот способ использован в примере).
2. С помощью операторов конкатенации списков «::». Его еще называют конструктором списка.
3. С помощью макроса-оператора «::=» который реализован через оператор «::» (из п. 2.).
4. С помощью list comprehensions. List comprehensions так же реализован в виде макроса, так что, по сути, внутри он использует все тот же оператор «::» (из п. 2.).

Конструктор списка позволяет присоединить (конкатенировать) один элемент в начало имеющегося списка. Конструктор списка возвращает список, что позволяет использовать его многократно в одном выражении.

Например, список, состоящий из трех элементов (числе 1, 2 и 3), можно создать, объявив его через строковый литерал:

[1, 2, 3]

Или с помощью конструктора списка:

1 :: 2 :: 3 :: []

Последняя конструкция «[]» – это литерал, описывающий пустой список. Пустой список может быть выражен только через литерал списка или явное создание объекта list[T].Nil(). Но о втором способе мы поговорим чуть позже, когда дойдем до знакомства с объектами.

Конструктор списка правоассоциативен. Это означает, что приведенный выше пример рассматривается как:

1 :: (2 :: (3 :: []))

а не как:

((1 :: 2) :: 3) :: []

Это важно, так как сам список реализован в виде однонаправленного связанного списка, в котором каждый элемент ссылается на следующий элемент списка. Последний элемент ссылается на специальный элемент, обозначаемый литералом «[]».

Следующая строчка:

        def celsiuses = convertFsToCs(fahrenheits);

объявляет еще одну неизменяемую переменную «celsiuses», в которую помещается список градусов по шкале Цельсия, полученный путем последовательного применения функции fahrenheitToCelsius ко всем элементам списка «fahrenheits», переданного ей в качестве параметра.

Строка:

WriteLine(celsiuses);

выводит значение списка на консоль. Эта функция нам уже известна, так что мы не будем заострять на ней внимания.

Описание функции convertFsToCs

Теперь перейдем к самому сложному и самому интересному в данном примере – к рассмотрению функции «convertFsToCs»:

        def convertFsToCs(fahrenheits)
{
  match (fahrenheits)
  {
    | headFahrenheit :: tailFahrenheits => fahrenheitToCelsius(headFahrenheit) :: convertFsToCs(tailFahrenheits)
    | _                                 => []
  } 
}

Эта функция использует уже знакомый нам оператор match, но в несколько более сложном (и необычном для многих) виде.

В данном случае в паттерне используется конструктор списка «::». Образец:

| headFahrenheit :: tailFahrenheits =>

означает, что в данном случае мы рассматриваем список как состоящий хотя бы из одного элемента «headFahrenheit» являющегося головой (head) списка, и хвоста (tail, конца) списка «tailFahrenheits». Конец списка может быть любым допустимым значением списка, то есть пустым списком «[]» или списком любой длины.

Паттерн связывает значения головы и хвоста списка с переменными «headFahrenheit» и «tailFahrenheits», соответственно.

Таким образом, данный паттерн распознает список, состоящий хотя бы из одного элемента и некоторого хвоста списка, и ассоциирует головной элемент с переменной «headFahrenheit», а хвост списка – с переменной «tailFahrenheits».

Можно сказать, что данный паттерн производит декомпозицию списка (разбирает список на составляющие).

Заметьте, что паттерн декомпозиции списка аналогичен конструктору списка. Так что если применить конструктор списка к связанным переменным:

| headFahrenheit :: tailFahrenheits => headFahrenheit :: tailFahrenheits

то в результате мы получим исходный список.

Таким образом, в двух словах, паттерн:

| headFahrenheit :: tailFahrenheits => 

сопоставляется со списком ненулевой длины и помещает его первый элемент в переменную headFahrenheit, а остаток – в переменную tailFahrenheits. Это позволяет применить функцию преобразования градусов «fahrenheitToCelsius» к головному элементу и рекурсивно вызвать «convertFsToCs» для остатка списка.

fahrenheitToCelsius(headFahrenheit) :: convertFsToCs(tailFahrenheits)

В результате на следующем шаге рекурсии в переменную fahrenheits будет помещен остаток списка, для которого еще раз будет произведено сопоставление с образцом. Так будет продолжаться до тех пор, пока список не станет пуст. В этом случае паттерн «headFahrenheit :: tailFahrenheits» не сопоставится и будет произведена попытка сопоставить пустой список с паттерном:

| _ =>

Как вы уже знаете, с этим паттерном сопоставляется любое выражение, так что он обязательно выполнится и вернет пустой список «[]».

Таким образом, функция «fahrenheitToCelsius» будет последовательно применена к каждому элементу исходного списка, а ее результат будет присоединен в начало списка, получаемого в результате применения функции «convertFsToCs» к остатку списка «fahrenheits». В результате мы получим список, длина которого соответствует исходному списку, и который содержит результаты преобразования, т.е. градусы Цельсия, соответствующие градусам Фаренгейта из исходного списка.

И еще раз выразительность…

Генераторы списков

Код примера невелик, но все же его можно улучшить. Во-первых, можно изменить описание списка:

          def fahrenheits = [0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300];

на:

          def fahrenheit = $[0, 20 .. 300];

Конструкция «$[0, 20 .. 300]» является одной из разновидностей list comprehensions. List comprehensions – это макрос, позволяющий упростить генерацию списков и их обработку. В данном случае используется вариант list comprehensions, который генерирует последовательность по заданному образцу. Эта разновидность работает только со списками числовых типов. Первое число задает значение первого элемента списка. Второе число задаёт второй элемент списка, и по разнице между первым и вторым числом вычисляется «приращение», которое будет получать каждый последующий элемент, а число, идущее после «..», задает конечное значение, которое не должен превышать последний элемент. Так, следующий пример:

$[1, 3 .. 10]

породит список:

[1, 3, 5, 7, 9]

а такой:

$[1, 3 .. 11]

породит список:

[1, 3, 5, 7, 9, 11]

Если нужен список с шагом «1», то второй элемент можно не указывать. Следующий пример:

$[1 .. 5]

породит список:

[1, 2, 3, 4, 5]

Если нужно задать список убывающих значений, то второй элемент (задающий приращение) должен быть меньше первого, а последний – меньше второго. Следующий пример:

$[5, 4 .. -5]

породит список:

[5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5]

Это практически то же самое, что вы писали в своих тетрадях на уроках математики в школах.

Типы в функции convertFsToCs

Чтобы лучше понимать картину происходящего, имеет смысл явно описать типы функции «convertFsToCs»:

        def convertFsToCs(fahrenheits : list[int]) : list[double]
{
  match (fahrenheits)
  {
    | headFahrenheit : int :: tailFahrenheits : list[int] => 
      fahrenheitToCelsius(headFahrenheit) : double :: convertFsToCs(tailFahrenheits) : list[double]
      
    | [] => [] : list[double]
  } 
}

Чтобы было более понятно, к чему относятся уточнения типов, я возьму некоторые из них в скобки:

        def convertFsToCs(fahrenheits : list[int]) : list[double]
{
  match (fahrenheits)
  {
    | (headFahrenheit : int) :: (tailFahrenheits : list[int]) => 
      (fahrenheitToCelsius(headFahrenheit) : double) :: (convertFsToCs(tailFahrenheits) : list[double])
      
    | [] => [] : list[double]
  } 
}

Первое что может вас смутить – это запись «list[int]» и «list[double]».

Первое имя – это имя типа («list»). Имя в скобках – это параметр типа. Список «list» имеет один параметр типа, который задает тип хранимых элементов.

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

Параметры типов тоже являются типами.

У типа может быть несколько параметров. Nemerle в большинстве случаев умеет автоматически выводить типы параметров типов. В исходном примере в функции convertFsToCs не было указано ни одного типа, но компилятор сам вывел все типы.

Кстати, Nemerle позволяет задавать типы локальных функций и переменных частично. Вместо типа можно использовать уже знакомый нам подстановочный символ «_». Например, можно описать тип, опустив указание конкретного типа в параметре типа:

выражение : list[_]

Это удобно в тех случаях, когда вы не можете указать конкретный тип, но вам важно указать компилятору, что в данном месте ожидается тип с одним параметром типа. Или три параметра типов, как указано в следующем примере:

выражение : X[_, _, _]

Компилятор выведет типы для всех мест, где использован подстановочный символ, но выдаст ошибку, если структура выводимого типа (т.е. количество параметров типа) не совпадает со структурой, указанной программистом. Кроме того, такой способ позволяет, не указывая явно параметры типа, помочь компилятору отличить одноименные типы, имеющие разное количество параметров типов.

Применение «match» внутри тела функции

Если тело функции содержит в себе единственное выражение, состоящее из одного оператора «match», и все параметры такой функции передаются в оператор «match», то оператор «match» можно опустить. Это значит, что исходную реализацию функции «convertFsToCs»:

        def convertFsToCs(fahrenheits)
{
  match (fahrenheits)
  {
    | headFahrenheit :: tailFahrenheits => 
      fahrenheitToCelsius(headFahrenheit) :: convertFsToCs(tailFahrenheits)
      
    | _ => []
  } 
}

можно упростить до:

        def convertFsToCs(fahrenheits)
{
  | headFahrenheit :: tailFahrenheits => 
    fahrenheitToCelsius(headFahrenheit) :: convertFsToCs(tailFahrenheits)
    
  | _ => []
}

Компилятор распознает такую ситуацию и автоматически подставит оператор «match». Таким образом, две приведенные реализации «convertFsToCs» эквивалентны, но вторая содержит меньше «синтаксического шума».

Декомпозиция функций

Функция «convertFsToCs» не универсальна, так как использует функцию «fahrenheitToCelsius» (объявленную выше), но по сути «convertFsToCs» выполняет очень часто встречаемую задачу – преобразование одного списка в другой с помощью применения ко всем элементам первого списка некоторой функции.

Давайте создадим аналог функции «convertFsToCs», который был бы более универсальным. Это можно сделать, если передавать функцию конвертации (отображения) в качестве параметра (как список в оригинальной версии функции «convertFsToCs»). Вот что из этого получится:

      def convertFsToCs(fahrenheits, elementConverter)
{
  match (fahrenheits)
  {
    | headFahrenheit :: tailFahrenheits => 
      elementConverter(headFahrenheit) :: convertFsToCs(tailFahrenheits, elementConverter)
    
    | _ => []
  }
}

Так как данный вариант функции стал универсален, то следует сделать более общими ее название и названия всех ее параметров и переменных:

      def convert(sourceList, elementConverter)
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

Вот как будет выглядеть применение этого варианта функции в исходном примере:

      using System.Console;

def convert(sourceList, elementConverter)
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses   = convert(fahrenheits, fahrenheitToCelsius);

WriteLine(celsiuses);

Обратите внимание на второй аргумент (выделен в коде) функции «convert». В нем передается ссылка на функцию «fahrenheitToCelsius».

Теперь функция «convert» может использоваться для преобразования любых списков в другие списки с применением любой подходящей функции. О таких функциях говорят, что они универсальны.

Однако если попробовать использовать эту функцию для обратного преобразования:

      def fahrenheits = $[0, 20 .. 300];
def celsiuses   = convert(fahrenheits, fahrenheitToCelsius);

def celsiusToFahrenheit(celsius)
{
  celsius * 9.0 / 5 + 32
}
def fahrenheits2 = convert(celsiuses, celsiusToFahrenheit);

то компилятор сообщит об ошибке, говорящей, что функция convert требует чтобы первый параметр был типа list[int], а ей передали параметр типа list[double].

Чтобы понять, в чем проблема, опишем типы (выведенные компилятором) функции «convert» явно:

      def convert(sourceList : list[int], elementConverter : int -> double) : list[double]
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

Первое, на что следует обратить внимание – это на запись «int -> double». Она описывает тип функции. До стрелочки идет описание типов параметров, а после стрелочки идет описание возвращаемого типа. Это означает, что в параметр elementConverter можно подставить только функцию, принимающую целое, а возвращающую число с плавающей точкой.

Проблема в том, что тип списка градусов Цельсия был list[int] (то есть список, хранящий элементы целочисленного типа), а список, который мы получили в результате преобразования, имеет тип list[double] (то есть хранящий элементы типа числа с плавающей точкой). Мы не можем передать функции «convert» в качестве первого параметра список типа list[double], а в качестве второго – функцию типа «double -> double» или «double -> int».

Так что же, несмотря на то, что мы можем передавать в качестве параметра функцию, нам все же придется писать по отдельной версии функции «convert» для каждого сочетания типов списков?

К счастью, этого делать не придется, так как Nemerle поддерживает обобщенное программирование. При описании функции (или типа) можно абстрагироваться от конкретных типов, введя для функции (или типа) параметр типа.

Вот как будет выглядеть обобщенная версия функции «convert»:

      def convert[TInputElem, TOututElem](
  sourceList       : list[TInputElem], 
  elementConverter : TInputElem -> TOututElem
) : list[TOututElem]
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

Поясню происходящее. В квадратных скобках, идущих непосредственно за именем функции, идет описание двух параметров типов, «TInputElem» и «TOututElem». Это абстрактные имена типов, которые могут использоваться вместо реальных имен типов внутри определения функции. Вместо одного параметра типов можно подставить один конкретный тип. Имена параметров типов не имеют никакого значения. Главное, чтобы они были уникальны (не пересекались с другими именами, видимыми в месте их декларации).

Использование обобщенной функции ничем не отличается от использования обычной функции:

      using System.Console;

def convert[TInputElem, TOututElem](
  sourceList       : list[TInputElem], 
  elementConverter : TInputElem -> TOututElem
) : list[TOututElem]
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses = convert(fahrenheits, fahrenheitToCelsius);

WriteLine(celsiuses);

Nemerle точно так же автоматически выведет типы для параметров типов во всех местах, где используется функция «convert».

Следующий пример демонстрирует, что обобщенный вариант функции «convert» можно использовать со списками любых типов. Это тот же пример, что приведен выше, но дополненный обратным преобразованием (из градусов Цельсия в градусы Фаренгейта) :

      using System.Console;

def convert[TInputElem, TOututElem](
  sourceList       : list[TInputElem], 
  elementConverter : TInputElem -> TOututElem
) : list[TOututElem]
{
  match (sourceList)
  {
    | head :: tail => elementConverter(head) :: convert(tail, elementConverter)
    | _            => []
  }
}

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses = convert(fahrenheits, fahrenheitToCelsius);

WriteLine(celsiuses);

// Ниже идет добавленный код преобразующий список градусов Цельсия // в список градусов Фаренгейта.def celsiusToFahrenheit(celsius)
{
  celsius * 9.0 / 5 + 32
}

def fahrenheits2 = convert(celsiuses, celsiusToFahrenheit);

WriteLine(fahrenheits2); // Выводим преобразованный список
WriteLine(fahrenheits);  // Выводим исходный список (для сравнения)

Эта программа выводит на консоль:

[-17,7777777777778, -6,66666666666667, 4,44444444444444, 15,5555555555556, 
 26,6666666666667, 37,7777777777778, 48,8888888888889, 60, 71,1111111111111,
 82,2222222222222, 93,3333333333333, 104,444444444444, 115,555555555556,
 126,666666666667, 137,777777777778, 148,888888888889]
[0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300]
[0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300]

Типы списков fahrenheits и celsiuses различаются. Список fahrenheits имеет тип list[int], а celsiuses имеет тип list[double]. Несмотря на это, код компилируется и работает.

Модуль NList (Nemerle.Collections.NList)

Функции, аналогичные функции «convert», используются при программировании на Nemerle весьма часто. Чтобы не писать их реализацию в каждой программе, логично было бы поместить ее в библиотеку. Именно так и поступили создатели Nemerle.

Функция, аналогичная нашей функции «convert», в библиотеке Nemerle называется «Map» (в переводе «Отображение»). Она находится в библиотеке Nemerle.dll (которая по умолчанию подключается ко всем Nemerle-программам).

Функция «Map» является глобальной функцией. Она реализована в модуле NList, который находится в пространстве имен Nemerle.Collections.

Перепишем наш пример с использованием этой функции:

        using System.Console;
usingNemerle.Collections;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses = NList.Map(fahrenheits, fahrenheitToCelsius);

WriteLine(celsiuses);

Методы списка «list[T]»

В модуле NList находится множество функций, упрощающих работу со списками. Большая часть этих функций доступна как в виде глобальных функций, так и в виде методов (а некоторые – только в виде методов).

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

        using System.Console;

def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32)
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses = fahrenheits.Map(fahrenheitToCelsius);

WriteLine(celsiuses);

Отображаемый список передается методу в виде неявного (невидимого) параметра.

Принято говорить, что некоторый объект обладает методом. Так, объект типа список обладает методом «Map» (и некоторыми другими).

Восстанавливаем качество выводимой информации

С тех пор как мы перевели наш пример на использование списков, качество выводимой на экран информации сильно ухудшилось. Давайте восстановим качество вывода информации на консоль, при этом не отказываясь от работы со списками.

Для решения этой задачи нужно объединить список градусов Цельсия со списком градусов Фаренгейта в новый список, затем перебрать элементы нового списка и вывести их на консоль так, как мы делали это в прошлой части.

Вот код, делающий это:

        def fahrenheitToCelsius(fahrenheit)
{
  5.0 / 9 * (fahrenheit - 32) 
}

def fahrenheits = $[0, 20 .. 300];
def celsiuses = fahrenheits.Map(fahrenheitToCelsius);

foreach ((fahrenheit, celsius) in fahrenheits.Zip(celsiuses))
  WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", fahrenheit, celsius);

Несмотря на то, что код очень похож на предыдущий его вариант, он содержит много нового!

Первое – метод «Zip» (выделен). Этот метод принимает второй список в качестве параметра и объединяет элементы первого списка с элементами второго списка, формируя третий список, каждый элемент которого содержит кортеж (tuple) двух элементов.

Второе – формируемый с помощью метода «Zip» список состоит из нового для вас типа данных «кортеж». Кортеж – это неизменяемый тип данных, позволяющий хранить 2 или более разнотипных объектов. В отличие от списка, кортеж не может изменять свою длину. Кортеж рассматривается как единое значение. Вы не можете изменить его элементы или их типы. Кортеж аналогичен списку параметров функции.

Следующий пример формирует кортеж из двух значений, целочисленного и строки:

(123, "Строка")

А этот пример формирует кортеж из трех значений:

(1, 1, 2.2)

Тип кортежа описывается как декартово произведение типов его параметров. Так, тип приведенного выше кортежа описывается как:

        int * int * double

А того, что приведен перед ним:

        int * string

Функция «Zip» формирует по одному кортежу типа:

        int * double

для каждой пары элементов списков fahrenheits / celsiuses и помещает сформированный кортеж в новый список.

Третье (новшество) – новый вид цикла, «foreach». Как и все остальные типы циклов в Nemerle «foreach» – это макрос. Мы не будем писать собственную версию этого цикла, так как реализация, доступная в стандартной библиотеке макросов Nemerle, очень гибка, и мы пока что не сможем реализовать ее столь же качественно. Упрощенная реализация будет мало отличаться от цикла «while», а это вы и так уже умеете делать. Так что просто разберем, как работает этот вид цикла.

Синтаксис foreach таков:

        foreach (текущий_элемент in коллекция)
  тело_цикла

«коллекция» – это любой объект Nemerle (и соответственно .Net), поддерживающий перебор элементов. В нашем случае в качестве коллекции выступает список кортежей.

«текущий_элемент» – это имя переменной или паттерн (шаблон), с которым производится сопоставление каждого элемента «коллекции». В нашем случае вместо «текущего_элемента» располагается паттерн «(fahrenheit, celsius)». Это тоже новая конструкция – «паттерн кортеж». С его помощью можно произвести декомпозицию кортежа (состоящего из двух элементов) на составляющие его элементы и связать с первым элементом имя fahrenheit, а со вторым – celsius.

Слово «паттерн» (образец) использовано мной не случайно. Дело в том, что перед нами еще один вариант сопоставления с образцом. «Но где же здесь оператор match?» – спросите вы... В явном виде его нет. Но так как foreach – это макрос, то он волен интерпретировать выражения, передаваемые ему в качестве параметров, как угодно. В том числе foreach может сгенерировать код оператора match и подставить в него образец, полученный в качестве одного из параметров. Именно так и поступает foreach.

В качестве «тело_цикла» может выступать любое выражение Nemerle, в том числе и блок (заключенный в фигурные скобки). Внутри этого выражения можно обращаться к «текущий_элемент». «тело_цикла» выполняется для каждого элемента перебираемой коллекции.

Таким образом, строки:

        foreach ((fahrenheit, celsius) in fahrenheits.Zip(celsiuses))
  WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", fahrenheit, celsius);

выполняют выражение:

WriteLine("Fahrenheit: {0, 4} Celsius: {1, 5:##0.0}", fahrenheit, celsius);

по одному разу для каждого элемента списка, формируемого выражением «fahrenheits.Zip(celsiuses)» поочередно помещая значения элементов этого списка в переменные fahrenheit и celsius. В переменную fahrenheit помещается первый элемент кортежа, а в переменную celsius второй.

Калькулятор

Пример, переводящий градусы, исчерпал себя. Для дальнейшего движения вперед нам нужен более сложный пример. Таким примером я выбрал строчный калькулятор.

Строчный калькулятор – это программа, принимающая (тем или иным образом) строку, содержащую арифметическое выражение, разбирающая эту строку, производящая вычисление разобранного выражения и выводящая результат вычисления выражения или сообщение об ошибке. Например, если этой программе задать выражение:

5 + 6 - 1

то она выдаст результат:

10

а если задать:

10   2

то она выдаст сообщение, говорящее, что вместо двойки ожидается оператор.

Разработка калькулятора будет разбита на несколько этапов, на каждом из которых мы познакомимся с новыми конструкциями языка или его стандартной библиотеки макросов.

Первая версия нашего калькулятора будет работать в командной строке. Так что начнем мы с примера, принимающего пользовательский ввод.

Ввод данных с консоли

Следующий пример ожидает ввод пользователя и выводит введенный текст обратно на консоль:

        using System.Console;

def readInput()
{
  def result = ReadLine();
  
  unless (result == "")
  {
    WriteLine("Вы ввели:");
    WriteLine(result);
    readInput();
  }
}

readInput();

Данная программа содержит всего два новых элемента:

1. Функцию ReadLine, объявленную в модуле System.Console. Она ожидает ввод пользователя (в консоль) и, после нажатия пользователем клавиши Enter, возвращает результат в виде строки.
2. Оператор «unless». Данный оператор реализован в виде макроса и располагается в стандартной библиотеке макросов. Он проверяет значение, передаваемое ему в круглых скобках (в нашем случае это «result == ""») и, если оно ложно (то есть равно false), выполняет выражение, идущее непосредственно за круглыми скобками (в нашем случае это блок кода, заключенный в фигурные скобки).

Вот реализация макроса unless:

        macro @unless(cond, body)
syntax ("unless", "(", cond, ")", body) 
{
  <[ match ($cond) { | false => $body : void | _ => () } ]>
}

Как видите, ничего нового. Обращение к макросу снова переписывается в использование оператора «match».

Таким образом, данная программа вызывает функцию «readInput», которая читает ввод пользователя в виде строки, помещает его в переменную «result», проверяет, не является ли значение этой переменой пустой строкой «""», и если не является, выводит на консоль строку «Вы ввели:» и (с новой строки) введенное пользователем значение, и в заключение рекурсивно вызывает саму себя, тем самым зацикливая свое выполнение. Если пользователь ввел пустую строку (то есть просто нажал Enter, не вводя ни одного символа), то функция «readInput» ничего не делает, и ее выполнение на этом завершается.

Если скомпилировать эту программу, запустить ее на выполнение и ввести, скажем:

1 + 1

и нажать Enter, функция выведет на консоль:

Вы ввели:
1 + 1

Ввод можно повторять многократно. Чтобы программа завершила свою работу, нужно нажать Enter, не вводя ничего в консоль.

Лексический разбор

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

У нас есть два пути:

1. Разбирать строку и сразу же производить необходимые вычисления.
2. Преобразовать строку в промежуточное представление и произвести разбор и вычисление, оперируя этим промежуточным вычислением.

Стоящая перед нами задача не очень сложна (по сравнению с разбором кода программы, например), и ее можно без особых трудов обработать первым способом. Но мы все же выберем второй, так как он нагляднее, и демонстрирует очень важный подход, который позволяет решать сложные задачи – разбиение задачи на последовательные этапы, каждый из которых решается несравнимо проще.

В нашем случае такими этапами будут:

1. Разбор строки на числа и операторы с одновременным отбрасыванием пробелов и табуляций (незначащих символов). На этом этапе также будет выявляться некорректный ввод, например, ввод неподдерживаемых операторов или букв. Этот этап называется «лексический разбор» (lexical analysis), поэтому функцию, выполняющую его, назовем «lexer».
2. Синтаксический разбор (parsing) и вычисление значений (evaluation).

Первый этап, лексический разбор, будет заключаться в чтении строки, введенной пользователем, и преобразованием ее в список, состоящий из операторов и значений. На этом же этапе мы будем отсекать ошибки ввода. Такими ошибками будет ввод текста, отличного от чисел и поддерживаемых операторов. Пока что будем поддерживать операторы «+», «-», «*» и «/».

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

Остается только попытаться заложить в один список значения разных типов. Это можно сделать, воспользовавшись специальным пользовательским типом данных variant.

Тип данных «variant»

Тип данных «variant» – это так называемый пользовательский тип данных. «Пользовательский» – означает, что это тип данных, который программист (пользователь) вводит для собственных целей. Для решения нашей задачи потребуется ввести вариантный тип «Token» (можно перевести как «символ»):

        variant Token
{
  | Number   { value : int; }
  | Operator { name  : string; }
  | Error
}

Значение типа «Token» может хранить значения одного из трех подтипов:

• Number
• Operator
• Error

При этом подтип Number может хранить в себе целочисленное значение. Мы будем использовать его для хранения разобранных целочисленных значений. Подтип Operator мы будем использовать для хранения разобранных операторов. Подтип Operator позволяет хранить строковое значение, которое и будет отражать реальный оператор ("+" для оператора «+», "-" для оператора «-» и т.д.). Подтип Error не позволяет хранить значений. Он будет использоваться если во входной строке встретится ошибка.

Такой подтип (т.е. Number, Operator, Error) называется вхождением варианта (variant option).

Строка:

  | Number   { value : int; }

описывает вхождение варианта «Number». Оно имеет одно неизменяемое поле «value» типа «int». Поле – это переменная, размещаемая внутри объекта некоторого типа. Поля требуют обязательного объявления типов.

Аналогично, строка:

  | Operator { name  : string; }

описывает вхождение варианта «Operator», имеющее одно поле «name» типа «string», а строка:

  | Error

вхождение варианта «Error», не имеющее полей.

Описание вхождения варианта начинается с вертикальной черты – «|», за которой идет его имя.

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

Ниже приведен код функции «lexer», производящей лексический разбор строки, формирующий список токенов «list[Token]»:

        def lexer(text : string) : list[Token]
{
  mutable index = 0;
  
  def peek() : char
  {
    if (index >= text.Length) '\0' else text[index]
  }

  def read() : char
  {
    def ch = peek();
    when (index < text.Length)
      index++;
    ch
  }

  def isDigit(ch) { ch >= '0' && ch <= '9' }

  def loop(resultTokens : list[Token]) : list[Token]
  {
    def number(ch : char, accumulator : int = 0) : int
    {
      def highOrderValue    = accumulator * 10;
      def currentOrderValue = ch - '0' : int;def currentValue      = highOrderValue + currentOrderValue;
  
      if (isDigit(peek()))
        number(read(), currentValue);
      else
        currentValue
    }

    def error()
    {
      WriteLine(string(' ', index - 1) + "^");
      WriteLine("ожидается число или оператор");
      (Token.Error() :: resultTokens).Reverse()
    }
    
    def ch = read();

    match (ch)
    {
      | ' ' | '\t'            => loop(resultTokens) // игнорируем пробелы
      | '+' | '-' | '*' | '/' => loop(Token.Operator(ch.ToString()) :: resultTokens)
      | '\0'                  => resultTokens.Reverse()
      | _ when isDigit(ch)    => loop(Token.Number(number(ch)) :: resultTokens)
      | _                     => error()
    }
  }
  
  loop([])
}

Давайте последовательно разберем, что она делает.

В начале функции «lexer» описывается изменяемая переменная «index» и две функции, «peek» и «read»:

        mutable index = 0;
  
  def peek() : char
  {
    if (index >= text.Length) '\0' else text[index]
  }
  def read() : char
  {
    def ch = peek();
    when (index < text.Length)
      index++;
    ch
  }

Переменная «index» хранит индекс текущего символа строки. Этот индекс увеличивается по мере разбора строки.

Функция «peek» предназначена для заглядывания вперед на один символ. Первое, на что стоит обратить внимание, – на то, что локальная функция «peek» объявлена внутри другой локальной функции «lexer». Это позволяет из «peek» обращаться к параметрам внешней функции и к переменным, объявленным в ней (до объявления вложенной функции).

Так, «text» – это строковый параметр, захваченный из внешней функции. Он содержит текст разбираемой строки.

Символы строки

Строка в Nemerle состоит из символов. Каждый символ строки представляется типом «char». Тип char позволяет хранить числовое представление символа в формате Unicode 16. Упрощенно можно сказать, что каждому символу соответствует некоторое число – код. Большая часть символов может быть выражена визуально, но есть ряд непечатных символов, которые представляются escape-последовательностями.

Символы в строке идут последовательно. В строке может быть ноль и более символов. Строка, в которой нет ни одного символа, называется пустой строкой.

Выражение «text.Length» возвращает количество символов, содержащихся в строке «text». Мы пока не будем обсуждать, что такое «Length».

Макрос «if»

«if» – это еще один макрос, основанный на операторе «match». Вот его определение:

        macro @if (cond, e1, e2)
syntax ("if", "(", cond, ")", e1, Optional (";"), "else", e2) 
{
  <[ 
    match ($cond : bool)
    { 
      | true => $e1 
      | _    => $e2
    } 
  ]>
}

Как видите, если выражение «cond» (задаваемое в круглых скобках) истинно (равно true), выполняется выражение e1 (идущее непосредственно за закрывающей круглой скобкой), а в обратном случае (когда выражение «cond» ложно) выполняется выражение e2 (идущее за «else»).

Таким образом, выражение:

        if (index >= text.Length) '\0'else text[index]

Выполняет выражение «'\0'», если index больше или равен длине строки (т.е. выражение «index >= text.Length» истинно) и «text[index]» в противном случае.

Символьные литералы

Конструкция '\0' – это символьный литерал. Символьный литерал описывает один символ и имеет тип «char».

Как и в строковом литерале, в символьном литерале можно использовать escape-последовательности. Escape-последовательность «\0» означает символ с кодом «0» (не путать с символом «ноль», обозначаемым литералом «'0'» и имеющем код «48»). Его также называют «нулевым символом». То же значение можно было бы получить, используя уточнение типа:

0 : char

Ниже приведен простой пример, демонстрирующий разницу между символом «0» и нулевым символом:

        using System.Console;

WriteLine('0'  : int);
WriteLine('\0' : int);

Этот пример выведет на консоль:

48
0

Доступ к символам строки

Как уже было сказано выше, символы в строке расположены последовательно. Это позволяет получать символы по индексу. Индекс – это значение отступа символа от начала строки, т.е. его позиция. Первый символ строки имеет индекс «0».

Выражение:

text[индекс]

возвращает символ, находящийся по индексу «индекс» в строке, на которую ссылается параметр «text».

Следующий пример:

text[0]

возвращает первый символ строки (символ с нулевым смещением от начала строки), а этот возвращает четвертый символ:

text[3]

Таким образом, следующее выражение означает получение символа по индексу, значение которого находится в переменной «index»:

text[index]

Так как функция «peek» не изменяет значения «index», то ее можно использовать неограниченное количество раз, и она не влияет на состояние функции.

Итак, мы разобрали все составные части выражения:

        if (index >= text.Length) '\0'else text[index]

и теперь можем объяснить, что же оно делает с точки зрения нашей программы.

Это выражение возвращает следующий символ, подлежащий разбору, или символ с кодом «0». Если не делать проверки выхода индекса за границы строки, то рано или поздно (когда значение переменной «index» сравняется с длиной строки), индекс выйдет за границы строки (т.е. перестанет означать допустимый индекс символа в строке), и попытка выполнения выражения «text[index]» приведет к исключительной ситуации, которая без специальной обработки приведет к аварийному завершению программы.

В нашем случае локальные функции «peek» и «read» инкапсулируют процесс перебора символов в строке. Если в процессе разбора строки индекс (значение переменной «index») выходит за границу допустимых индексов для строки «text», то функции «peek» и «read» начинают возвращать нулевой символ, сигнализирующий, что достигнут конец строки. Это позволяет в основном алгоритме вообще не думать об индексе, и даже о том, как организовано чтение символов из строки. Достаточно знать, что функция «peek» позволяет узнать, какой символ подлежит разбору, а функция «read» читает следующий символ, сдвигая текущую позицию разбора на один символ вперед.

Настало время разобрать как же реализована функция «read»:

        def read() : char
{
  def ch = peek();

  when (index < text.Length)
    index++;

  ch
}

Для начала она, с помощью функции «peek», считывает значение следующего символа и помещает в неизменяемую переменную «ch». Переменная нужна для того, чтобы вернуть считанное значение в конце функции «read» (как результат ее работы).

Нетрудно догадаться, что «when» – это еще один макрос из стандартной библиотеки макросов, созданный на основе оператора «match». Он позволяет выполнить некоторое выражение (в примере выше это выражение «index++»), если истинно выражение в круглых скобках (в примере выше это выражение «index < text.Length»).

«++» – это еще один макрос из стандартных макросов. Он вводит оператор, увеличивающий значение переменной на единицу (инкремент). Код:

index++

аналогичен коду:

index = index + 1

Таким образом, выражение:

        when (index < text.Length)
    index++;

увеличивает значение переменной «index» на единицу, если текущее значение этой переменной меньше длины строки, на которую ссылается параметр «text». Таким образом, если значение index выходит за границы строки, то оно больше не увеличивается.

Так как для получения значения текущего символа строки в функции «read» используется функция «peek», то при достижении индексом конца строки функция «read» (как и «peek») начнет возвращать нулевой символ «’\0’», символизирующий достижения конца строки.

Функция «isDigit»

Чтобы проверить, является ли символ числом, можно воспользоваться следующим выражением:

ch >= '0' && ch <= '9'

Здесь ch – это переменная (или параметр) типа «char», а '0' и '9' – значения символьных литералов, соответствующие символам «0» и «9».

Данный код использует тот факт, что цифровые символы в кодировке Unicode (используемой в .Net для представления символов) идут последовательно (имеют последовательно идущие значения).

В принципе, в программах можно использовать приведенное выше выражение во всех местах, где требуется узнать, является ли символ числом. Но это, с одной стороны, неудобно, а с другой (что намного более важно) – заставляет тех, кто будет читать код, каждый раз разбираться, что же делает данное выражение. Поэтому правильнее будет вынести данное выражение в отдельную функцию:

        def isDigit(ch) { ch >= '0' && ch <= '9' }

Теперь в любом месте программы, где используется эта функция, будет сразу ясно, что программист хочет узнать, является ли символ числом, а не чем-то другим.

Функция «loop»

Функция «loop» – это функция, выполняющая основную работу по лексическому разбору. Для начала опустим описание двух ее вложенных функций и посмотрим на ее тело:

        def loop(resultTokens : list[Token]) : list[Token]
{
  def number(ch : char, accumulator : int = 0) : int { ... }
  def error() { ... }
  
  def ch = read();

  match (ch)
  {
    | ' ' | '\t'            => loop(resultTokens) // игнорируем пробелы
    | '+' | '-' | '*' | '/' => loop(Token.Operator(ch.ToString()) :: resultTokens)
    | '\0'                  => resultTokens.Reverse()
    | _ when isDigit(ch)    => loop(Token.Number(number(ch)) :: resultTokens)
    | _                     => error()
  }
}

Это рекурсивная функция, которая на каждом шаге рекурсии читает и анализирует один (текущий) символ из обрабатываемой строки.

Ее параметр «resultTokens» предназначен для накопления результата. Он содержит список токенов, разобранных на данный момент времени. При вызове этой функции из функции «lexer» в качестве начального значения для параметра «resultTokens» задается пустой список. По мере продвижения по разбираемой строке к нему присоединяются новые токены.

В следующей строке происходит считывание текущего символа из входной строки:

        def ch = read();

Далее это значение передается в оператор «match», который осуществляет анализ этого символа. Если текущий символ – это пробел или табуляция, выполняется:

    | ' ' | '\t'            => loop(resultTokens) // игнорируем пробелы

Так как пробелы и символы табуляции не имеют значения для нашего калькулятора, они просто отбрасываются. В терминах лексического анализа «отбрасывается» означает, что символы не порождают лексем. Так что мы просто рекурсивно вызываем функцию «loop», передавая ей тот же список лексем, что был получен в качестве параметра на текущей итерации.

Если текущим символом оказался символ сложения «+», вычитания «-», умножения «*» или деления «/», выполняется вхождение:

    | '+' | '-' | '*' | '/' => loop(Token.Operator(ch.ToString()) :: resultTokens)

В нем происходит следующее:

Текущий считанный символ преобразуется в строку с помощью метода «ToString»:

ch.ToString()

Метод «ToString» имеется у всех без исключения .Net-объектов. Он преобразует значение объекта в строку. Для символа он формирует строку, содержащую ровно один символ, значение которого соответствует преобразуемому символу. Таким образом, если вызвать метод «ToString», скажем, для символа «+»:

        '+'.ToString()

то он вернет строку:

        "+"
      

Полученная таким образом строка передается конструктору вхождения «Operator» варианта «Token»:

Token.Operator(ch.ToString())

Что это за параметр и откуда он взялся? Для ответа на этот вопрос нужно вспомнить, как описывалось вхождение варианта «Operator»:

  | Operator { name  : string; }

Для каждого поля вхождения варианта создается один параметр. Таким образом, строка:

Token.Operator("+")

создает экземпляр вхождения варианта «Operator» со значением поля «name» равным строке «+».

Созданный экземпляр присоединяется к голове списка-аккумулятора «resultTokens»:

Token.Operator(...) :: resultTokens

и полученный таким образом список передается в рекурсивный вызов функции «loop»:

loop(Token.Operator(...) :: resultTokens)

Чтобы было более понятно происходящее, я перепишу выражение:

loop(Token.Operator(ch.ToString()) :: resultTokens)

в аналогичное, но с использованием ряда промежуточных переменных, и укажу их типы:

        def operatorStr   : string         = ch.ToString();
def operatorToken : Token.Operator = Token.Operator(operatorStr);
def token         : Token          = operatorToken;
def newRes        : list[Token]    = token  :: resultTokens;
loop(newRes)

Думаю, что практически все шаги вам должны быть уже понятны, кроме шага:

        def token : Token = operatorToken;

На этом шаге не выполняется никаких действий кроме неявного преобразования значения типа вхождения варианта «Token.Operator» в значение типа «Token», т.е. в вариант.

Дело в том, что вхождения варианта совместимы с вариантным типом, в котором они объявлены. Эта особенность позволяет хранить в списке типа list[Token] элементы типа Token.Operator. Более того, в одном списке можно хранить значения и других типов вхождений (т.е. Token.Number и Token.Error).

Если текущим символом является «\0» (нулевой символ), выполняется вхождение оператора «match»:

    | '\0'                  => resultTokens.Reverse()

Символ «\0»означает, что достигнут конец разбираемой строки. Так как токены добавлялись в начало списка-аккумулятора «resultTokens», в нем получился «перевернутый» (т.е. развернутый в обратном порядке) список токенов. Метод «Reverse» списка «разворачивает» список, т.е. формирует новый список, содержащий те же элементы, что в исходном, но в обратном порядке. Полученный список возвращается как результат работы функции «loop».

Обратите внимание на то, что при этом не производится рекурсивного вызова. Таким образом, нулевой символ является признаком остановки рекурсии.

Если текущим символом является цифра, то срабатывает вхождение:

    | _ when isDigit(ch)    => loop(Token.Number(number(ch)) :: resultTokens)

В нем происходит вызов функции «number» (объявленной прямо внутри функции «loop»), которая производит распознавание числа. Распознанное значение передается в конструктор вхождения варианта «Token.Number» который, как и в случае распознавания оператора, добавляется к началу списка-аккумулятора и передается в качестве параметра рекурсивного вызова функции «loop».

Данное вхождение оператора «match» похоже на то, в котором обрабатывались операторы, но в нем есть две особенности. Во-первых, здесь используется еще незнакомая вам конструкция «защитник» (guard) образца: «when ...», а во-вторых, функцию «number» стоит разобрать отдельно. Начнем с защитника.

Защитник (guard) образца оператора «match»

Рассмотрим еще раз следующее вхождение оператора «match»:

 | _ when isDigit(ch) => ...

Как уже говорилось выше, символ подчеркивания «_» задает образец, который сопоставляется с любым значением. Но за этим образцом следует конструкция:

        when isDigit(ch)

Данная конструкция называется «защитником» образца (pattern guard). Она обязательно начинается с ключевого слова «when» и одного выражения.

Защитник может добавляться к любому образцу (не только к «_») и выполняет дополнительную проверку.

Вхождение варианта сопоставляется с образцом при условии, что с образцом сопоставляется сам образец, и при условии, что выражение защитника (если оно есть) истинно (возвращает true). В нашем случае выражением защитника является выражение:

isDigit(ch)

то есть функция, проверяющая, является ли значение переменной «ch» цифрой.

Выражение защитника может использовать все переменные и функции, которые были видны перед оператором «match», а также переменные, введенные (связанные) в образце, к которому принадлежит защитник. Так, вхождение:

 | _ when isDigit(ch) => ...

можно переписать следующим образом:

| x when isDigit(x) => ...

В данном случае образец «x» вводит переменную «x», с которой связывается любое значение, переданное в оператор «match». В нашем случае такое значение уже находится в переменной «ch», так что вводить еще одну переменную смысла нет, но в некоторых случаях это может быть полезно. Например, если бы мы не ввели переменную «ch», а сразу передали бы в оператор «match» значение функции «read»:

        match (read())
  {
    ...
    | chwhen isDigit(ch)    => loop(Token.Number(number(ch)) :: resultTokens)

то мы все же могли бы получить значение, возвращенное функцией read, воспользовавшись образцом «переменная». В сущности, образец «_» является специальным случаем образца «переменная».

В примере, приведенном выше, выделена переменная, введенная в образце, и ее использование.

Но вернемся к защитникам образцов...

Как уже говорилось ранее, так как вхождения оператора «match» сопоставляются по очереди, очень важен порядок, в котором расположены образцы. Но особенно это важно для образцов, содержащих переменные, и защитников. Например, если переставить местами образцы:

    | _ when isDigit(ch)    => loop(Token.Number(number(ch)) :: resultTokens)

и

    | _                     => error()

то переставленный ниже образец не сработает, так как образец «_» будет сопоставляться с любым значением, и до проверки защитника дело попросту не дойдет.

Последним вхождением оператора «match» является:

    | _                     => error()

Оно просто вызывает локальную функцию «error», объявленную прямо в функции «loop».

Функция «error»

        def error()
    {
      WriteLine(string(' ', index - 1) + "^");
      WriteLine("ожидается число или оператр");
      (Token.Error() :: resultTokens).Reverse()
    }

Цель функции «error» – вывести пользователю внятное сообщение об ошибке и указать на то место, где произошла ошибка. Чтобы указать на место, где произошла ошибка, в первой строке данной функции формируется строка вида:

                      ^

где знак «^» указывает на символ предыдущей строки, в котором произошла ошибка (предыдущая строка содержит текст выражения, введенного пользователем). Данная строка состоит из пробелов, количество которых равно позиции, в которой произошла ошибка, минус один. К этой строке конкатенируется («приклеивается») символ «^», и эта строка выводится на консоль. В результате символ «^» указывает на место ошибки (предыдущая строка консоли в этот момент содержит введенную пользователем строку).

Далее на новой строке выводится диагностическое сообщение «ожидается число или оператор».

В конце функции «error» к началу списка-аккумулятора токенов «resultTokens» присоединяется экземпляр токена типа «Token.Error». Он позволит оповестить следующий шаг разбора строк (синтаксический разбор) о том, что при лексическом разборе произошла ошибка.

После этого, как и в случае достижения конца разбираемой строки, полученный список разворачивается в обратную сторону и возвращается как результат работы функции «loop».

Функция «number»

Функция «number» производит разбор участка строки, содержащего целое число:

        def number(ch : char, accumulator : int = 0) : int
{
  def highOrderValue    = accumulator * 10; // значение верхних разрядов  def currentOrderValue = ch - '0' : int; // значение текущего разрядаdef currentValue      = highOrderValue + currentOrderValue;
  
  if (isDigit(peek()))
    number(read(), currentValue);
  else
    currentValue
}

Значения по умолчанию

Первое, на что нужно обратить внимание – это на то, что данная функция имеет параметр «accumulator», которому задано значение по умолчанию. При вызове функции, имеющей значения по умолчанию для параметров, можно не задавать значения этих параметров.

Так, если вызывать функцию «number» следующим образом:

number('1')

то параметр «accumulator» получит значение «0». Если же передать в него некоторое значение:

number('1', 5)

то значение по умолчанию будет проигнорировано, и параметр «accumulator» получит переданное значение («5» в данном случае).

Алгоритм работы функции «number»

Все остальное операторы в функции «number» вам уже знакомы, но, тем не менее, стоит подробнее разобрать, что она делает.

Первые три строки этой функции:

          def highOrderValue    = accumulator * 10;
def currentOrderValue = ch - '0' : int;def currentValue      = highOrderValue + currentOrderValue;

вычисляют текущее значение разбираемого числа. Так как число может состоять из нескольких десятичных разрядов (каждый из которых представляется отдельным символом), то распознавание числа происходит рекурсивно.

Параметр «accumulator» содержит значение числа, рассчитанного на предыдущем шаге рекурсии (или «0», если это вызов из функции «loop»). Умножив его на 10 можно получить значение старших порядков числа:

          def highOrderValue    = accumulator * 10;

Для получения значения текущего разряда из кода текущего символа (находящегося в параметре «ch») вычитается код цифры '0':

            def currentOrderValue = ch - '0' : int;

Как я уже говорил, коды, описывающие десятичные цифры, идут последовательно, и код каждой следующей цифры на единицу больше кода предыдущей цифры. Таким образом, если вычесть из кода любой цифры код цифры '0', то получится соответствующее число. Например, если вычесть '0' из '2':

          '2' - '0' : int

то в результате мы получим число «2».

Уточнение типа здесь требуется, так как оператор вычитания не определен для типа «char». Чтобы обойти это ограничение, значения типа «char» нужно преобразовать к типу «int». Именно это и происходит, когда к одному из операндов применяется операция уточнения типа. При этом компилятор автоматически приводит второй операнд к типу «int», и вычитание производится над приведенными к типу «int» значениями.

На следующем шаге значение старших разрядов числа складывается со значением текущего разряда:

          def currentValue      = highOrderValue + currentOrderValue;

В результате в переменную «currentValue» помещается текущее значение.

Чтобы было понятнее, разберем алгоритм работы функции «number» на примере. Предположим, что происходит разбор числа «12». На первом шаге рекурсии accumulator равен нулю, а в параметре «ch» будет находиться символ '1'. Умножение accumulator на 10 даст ноль (параметр «accumulator» заменен на его текущее значение):

          def highOrderValue = 0 * 10;

Стало быть, в переменную «highOrderValue» помещается значение «0».

В параметре «ch» находится код символа '1'. Вычитание из него кода символа '0':

          def currentOrderValue = '1' - '0' : int;

дает значение «1», которое помещается в переменную «currentOrderValue».

Сложение нуля с единицей дает значение «1», которое помещается в переменную «currentValue»:

          def currentValue      = highOrderValue + currentOrderValue;

Далее производится проверка, является ли следующий символ входной строки цифрой:

          if (isDigit(peek()))

Поскольку следующий символ – это '2', проверка завершается успехом (функция «isDigit» возвращает «true»). Благодаря этому происходит рекурсивный вызов функции «number». При этом в первый параметр (ch) помещается символ '2', а во второй (accumulator) – число «1»:

number('2', 1) // здесь переменные заменены на их значения

Внутри функции снова происходит вычисление:

          def highOrderValue    = accumulator * 10;
def currentOrderValue = ch - '0' : int;def currentValue      = highOrderValue + currentOrderValue;

Так как «accumulator» содержит значение «1», а вычисление «(ch - '0' : int)» дает значение «2», то в результате в переменную «currentValue» помещается значение «12». Так как следующий символ – не цифра, проверка «isDigit(peek())» возвращает «false». Вследствие этого происходит возврат вычисленного значения (находящегося в переменной «currentValue»). На этом работа функции завершается, и вызывающий ее код получает значение «12».

Список литературы

1. http://nemerle.org
2. В.Ю.Чистяков, Язык Nemerle, часть 1 // RSDN Magazine. М.: К-Пресс, 2009 – №2. – стр. 36-49. http://rsdn.ru/article/Nemerle/TheNemerleLanguage.xml
3. В.Ю.Чистяков, Язык Nemerle, часть 3 // RSDN Magazine. М.: К-Пресс, 2010 – №1. – стр. 39-57. http://rsdn.ru/article/Nemerle/TheNemerleLanuage-prt-3.xml

Сообщений 17    Оценка 970 [+1/-0]         Оценить