Блоки кода и операции управления ходом вычислений

Блоки кода

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

{
    expr1
    expr2; expr3
    ...
    expr_n
}

Оформление может быть почти произвольным:

а)

{ expr1; expr2; ... ; expr_n }

б)

{ expr1
expr2
...
expr_n }

и т.д.

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

Блок кода сам является выражением, его тип и значение соответствует типу и значению последнего выражения в блоке. Пустой блок кода имеет тип void.

Можно использовать блоки кода везде, где ожидается выражение. В этом случае выражение следует заключить в последовательность круглых и фигурных скобок ({ ... }). Многие выражения в Ficus, например, условные выражения, циклы, соответствие с образцом, try-catch и др., ожидают блоки кода как часть конструкции. Их следует писать без круглых скобок:

// Круглые и фигурные скобки здесь обязательны, потому как компилятор
// ожидает одиночное выражение после "if"
// Так писать можно, но не рекомендуется.
if ({ val diff=x - y;
    -10 <= diff && diff < 20 }) {
    // then- и else- ветки являются блоками кода,
    // потому фигурные скобки обязательны.
    print("условие верно"); foo()
}
else
{   // фигурные скобки могут располагаться сразу после  'else'
    // или на отдельной строке
    bar()
}

// Тело функции может быть одиночным выражением, идущим за '=',
// или блоком кода, в этом случае '=' опускается
fun sort3(a: int, b: int, c: int): (int, int, int)
{
    val (a, b) = (min(a, b), max(a, b))
    val (b, c) = (min(b, c), max(b, c))
    val (a, b) = (min(a, b), max(a, b))
    (a, b, c)
}

Как ранее было сказано, тип блока кода определяется типом последнего выражения. Он (тип) может быть void, например:

fun print_in_red(msg: string) {
    print("\33[31;1m")
    print(msg)
    print("\33[0m")
}

или не-void. Чтобы как-то предотвратить случайные программные ошибки, компилятор Ficus сообщает о ситуациях, когда в середине блока кода встречается не-void выражение.

fun dotprod((x1, y1, z1, w1): (float*4),
            (x2, y2, z2, w2): (float*4)) {
    x1*x2 // ошибка: не-void выражение   x1*x2
  + y1*y2 // ошибка: не-void выражение + y1*y2
  + z1*z2 // ошибка: не-void выражение + z1*z2
  + w1*w2 // не ошибка, последнее выражение в блоке
}

Если все же нужно вставить не-void выражение (например, вызвать функцию ради побочных эффектов, но не использовать результат), есть 2 практически эквивалентных способа:

val _ = waitkey() // Код клавиши не нужен,
                  // просто ожидаем нажатие клавиши пользователем.
                  // Поскольку это объявление значения, 
                  // это не может быть последним выражением 
                  // в блоке кода

ignore(waitkey())  // То же самое, игнорируем возвращаемое значение
                   // Может использоваться как последнее выражение
                   // в блоке кода

Здесь ignore() – тривиальная стандартная фукнция, объявленная в Builtins:

fun ignore(_: 't) {}

Про области видимости

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

• Область видимости модуля. Имена, определенные в этой области видимости доступны внутри модули и в других модулях (если только не объявлены @private). Снаружи модуля имена доступны с ипользованием нотации <имя_модуля>.<имя_сущности> сразу после импорта модуля. Смотри раздел Модули.
• Область видимости функции. В этой области определяются Формальные параметры функции.
• Область видимости блока. Каждый блок кода задает свою собственную область видимости.

В областях видимости действуют следующие правила:

1. Во всех областях видимости возможно объявление типов, функций, значений и переменных. В области видимости модуля можно также объявлять исключения и интерфейсы.
2. Имена, объявленные в области видимости функции или блока, доступны только внутри этой области. Имена, объявленные в области видимости модуля, также доступны снаружи, только если они не объявлены как @private.
3. Типы и функции (возможно рекурсивные), определенные в области видимости, доступны во все области, а также во вложенных областях, независимо от порядка объявления. Другими словами, нет необходимости (как и нет способа) делать предварительное объявление типа или функции. Просто определите их где-нибудь в соответствующей области видимости и они будут найдены.
4. Значения могу ссылаться только на значения, объявленные перед ними, в той же области видимости или внешней области видимости. Это сделано для исключения циклической зависимости между значениями.
5. Функции могут ссылаться на значения, обявленные перед ними.
6. Имена из разных областей видимости никогда не конфликтуют друг с другом. Если в области видимости (или вложенных областях) объявлено несколько перегруженных функций, компилятор выберет наиболее подходящую. Объявленные фукнции всегда добавляются в начало списка перегруженных функций, то есть последняя объявленная становится первой пробуемой. Для значений и типов компилятор выбирает последний определенный, т.е. имена из вложенных областей временно переопределяют имена внешних областей. Значения, определенные в некоторой области видимости переопределяют/отменяют все перегруженные функции с тем же именем в точке объявления значения вплоть до конца блока. 7.Типы и значения/функции никогда не конфликтуют:

  type Malkovich = string
  fun Malkovich(Malkovich: Malkovich): Malkovich? = Some(Malkovich)
  println(Malkovich("Malkovich"))

1. Функции в области видимости могут иметь одно имя, но должны иметь разный набор параметров. Классический пример – функция print() из модуля Builtins, определенная для разных типов.
2. Значения в области видимости могут иметь одно имя, следующее определение “переопределяет” предыдущее (не физически, а в терминах разрешения имен). Мы видели подобное поведение в разделе Значения и переменные.

Условные выражения

Наиболее общий вид условного выражения в Ficus представлен следующим образом:

if условие1 {
  выражения1 ...
} /* необязательные ветви else if: */
else if условие2 {
  выражения2 ...
} else if ...
/* необязательная ветвь else */ else {
  else-выражения ...
}

Другими словами, существует обязательная ветвь then (с выражениями выражения1), необязательная ветвь else и ноль или более промежуточных ветвей else if. Все ветви должны иметь одинаковый тип: либо void (классический стиль императивных языков), либо непустые типы. Отсутствие ветви else считается сокращённой записью для else {}. В таком случае остальные ветви обязаны быть типа void. Рассмотрим несколько примеров:

// ошибка: ветвь if имеет тип 'double', ветвь else имеет тип 'void'
val y = if x >= 0. {sqrt(x)}
        else {
           println(f"x={x} отрицательное")
        }
val y = if x >= 0. {sqrt(x)}
        else {
           // нормально, так как 'throw' совместимо с любым типом
           throw Fail(f"x={x} отрицательное")
        }
import File
val y = if x >= 0. {sqrt(x)}
        else {
           // эта форма тоже правильная, мы регистрируем ошибку
           File.println(File.stderr, f"x={x} отрицательное")
           // затем возвращаем некоторое дефолтное значение
           0.
        }
// использование цепочки условий для реализации бизнес-логики
fun days_in_month(month: int, year: int) =
   if month < 1 || month > 12 { throw OutOfRangeError }
   else if month == 1 || month == 3 || month == 5 || month == 7 ||
           month == 8 || month == 10 || month == 12 {31}
   else if month == 4 || month == 6 || month == 9 || month == 11 {30}
   else if year % 4 != 0 ||
        (year % 100 == 0 && year % 400 != 0) {28}
   else {29}

Цикл while

Это классическая конструкция цикла, выполняющаяся до тех пор, пока указанное условие остаётся истинным:

while условие { тело_цикла ... }

Пример использования:

import File
val f = File.open("fiblist.fx", "rt")
var count = 0
// читаем текст из файла, считаем ненулевые строки
while !f.eof() {
   val str = f.readln()
   count += str.strip() != ""
}
println(count)

Тип тела цикла обязательно должен быть void, и весь цикл также имеет тип void.

Цикл for

Ещё одна важная конструкция — это цикл по некоторому интервалу значений, двумерной сетке или коллекции:

// итерация по диапазону
for idx1 <- старт_знач1:конец_знач1[:шаг1]
 for idx2 <- старт_знач2:конец_знач2[:шаг2] ... {
   выражения ...
}

В первом варианте цикла for вводится идентификатор idx1 типа int, принимающий последовательно значения:

старт_знач1, старт_знач1 + шаг1, старт_знач1 + шаг1*2, ...

до достижения границы конец_знач1. Если шаг не указан, принимается значение шага 1. Шаги могут быть отрицательными, тогда цикл выполняется минимум один раз, если старт_знач больше конечного значения. Приведём пример:

// подготовка таблицы для быстрого подсчета расстояния Хэмминга
fun popcount(n: int) =
    if n > 0 {1 + popcount(n & (n - 1))}
    else {0}
val hamming_lut = array(256, 0u8)
for i <- 0:256 { hamming_lut[i] = uint8(popcount(i)) }
println(hamming_lut)

// вывод треугольника Паскаля
val n = 10
val triangle = array((n, n), 0)
for i <- 0:n for j <- 0:i+1 {
    val x = if j == 0 || i == 0 {1}
            else {triangle[i-1, j-1] + triangle[i-1, j]}
    triangle[i, j] = x
    print(f"{x} ")
    if j == i {print("\n")}
}

Заметим, что внутренние циклы могут зависеть от текущих значений внешнего цикла.

Вторая форма цикла for предназначена для перебора коллекций:

// перебор коллекций
for эл1 <- колл1
   [for эл2 <- колл2 ...] {
   выражения
}

Поддерживаемые коллекции включают списки, строки, массивы и векторы:

// гистограмма изображений
val histogram = array(256, 0)
val w = 640, h = 480
val image = array((h, w), 0u8)
val rng = RNG(0x12345u64)
// заполняем изображение случайными значениями
for y <- 0:h
   for x <- 0:w {
      image[y, x] = rng.uniform(0u8, 255u8))
   }

// Итерация по пикселям изображения
// вложенный цикл автоматически организуется компилятором
for pix <- image {
    histogram[pix] += 1
}

// проверка, является ли строка числом
val str = "12345"
var isint = true
for c <- str {
   if !('0' <= c <= '9') {
      isint = false
      break // выход раньше окончания цикла
   }
}

Во вложенных циклах можно смешивать проход по диапазону и коллекциям.

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

for val1 <- coll1, val2 <- coll2 ... { выражения ... }

Так, например, легко рассчитать расстояние Хэмминга между двумя векторами:

val a = array(16, 0u8)
val b = array(16, 0u8)
... // инициализация a и b, и подготовка таблицы расстояний Хамминга
var hamming_dist = 0
for x <- a, y <- b { hamming_dist += hamming_lut[x ^ y] }

При попытке параллельно пройти по коллекциям разного размера возникнет исключение SizeMismatchError.

Тело цикла for, как и результат, должно иметь тип void. Если тип тела отличается от void, компилятор выдаёт ошибку.

Получение индекса текущего элемента с помощью @

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

for i <- 0:n { if i > 0 {print ", "}; print(a[i]) }

Однако такая конструкция менее эффективна и сложнее воспринимается визуально. Особенно неудобно это для списков, где a[i] отсутствует вовсе.

Специальная синтаксическая конструкция решает проблему:

for x@i <- mylist { if i > 0 {print ", "}; print(x) }

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

Индексация доступна и для многомерных массивов:

// вычислить рамку вокруг изображения, содержащую все ненулевые пиксели
fun bounding_box(image: uint8 [,])
{
    var minx = 1000000, maxx = -1
    var miny = 1000000, maxy = -1
    for pix@(y, x) <- image {
        if pix != 0 {
            minx = min(minx, x); maxx = max(maxx, x)
            miny = min(miny, y); maxy = max(maxy, y)
        }
    }
    if maxx >= 0 { (minx, miny, maxx-minx+1, maxy-miny+1) }
    else { (0,0,0,0) }
}

Все индексы и сами элементы остаются неизменными на каждой итерации. Попытка изменить индекс приведет к ошибке:

for v@offset <- datastream {
   // ошибка: индекс offset не может быть изменён вручную
   if v == 0 {offset += 10}
}

Свертка (folding)

Ранее мы использовали переменные для обновления координат. Повторяющийся проход по массиву и накопление результатов — распространённая задача обработки данных, называемая операцией “свёртка” (folding) или “редукция” (reduce). В Ficus существует функциональная форма цикла for, позволяющая накапливать итоговый результат без использования переменных:

fold acc1=initval1, acc2=initval2, ...
for x1 <- domain1, x2 <- domain2 ...
[for y1 <- nested_domain1, y2 <- nested_domain2, ...] {
  exprs ...
}

Таким образом, выражение делится на две части. Первая часть объявляет аккумуляторы и их начальные значения. Вторая часть — обычный цикл for, но с важным отличием: тело цикла должно возвращать обновлённую величину аккумулятора (в случае множественных аккумуляторов — кортеж величин). Внутри тела цикла аккумуляторы являются неизменяемыми величинами. Рассмотрим несколько примеров:

val array = [ 1, 2, 3, 4, 5 ]
// Посчитать сумму элементов массива.
// После каждой итерации сумма замещается на "сумма + x"
println(fold sum = 0 for x <- array {sum + x})

// Посчитать расстояние Хэмминга с использованием свёртки
fun hamming_dist(a: uint8 [], b: uint8 []) =
    fold dist = 0 for x<-a, y<-b {
        dist + hamming_lut[int(x ^ y)]
    }

// Версия функции bounding_box на основе складывания:
fun bounding_box(image: uint8 [,])
{
    val (minx, maxx, miny, maxy) =
        fold minx = 1000000, maxx = -1, miny = 1000000, maxy = -1
        for pix@(y, x) <- image {
            if pix != 0 {
                (min(minx, x), max(maxx, x), min(miny, y), max(maxy, y))
            } else {
                (minx, maxx, miny, maxy)
            }
        }
    if maxx >= 0 { (minx, miny, maxx-minx+1, maxy-miny+1) }
    else { (0,0,0,0) }
}

Возможно, вы заметили, что в последнем примере переменные minx, maxx, miny, maxy пришлось дважды задать: сначала как аккумуляторы внутри fold, потом как назначаемые величины. Это неудобно и чревато ошибками (при рефакторинге порядок величин может нарушиться), поэтому предусмотрен сокращённый вариант:

...
val fold minx = 1000000, maxx = -1, miny = 1000000, maxy = -1
    for pix@(y, x) <- image {
        if pix != 0 {
            (min(minx, x), max(maxx, x), min(miny, y), max(maxy, y))
        } else {
            (minx, maxx, miny, maxy)
        }
    }
...

То есть можно просто добавить val (или var, если планируется модификация результатов после завершения цикла) перед ключевым словом fold, и Ficus самостоятельно определит одноимённые значения-аккумуляторы и присвоит им результаты складывания.

Специальные формы свёртки

Существуют несколько общих операций, похожих на свёртку, но не вполне вписывающихся в обычную семантику fold. Среди них:

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

Все эти операции можно реализовать через fold, например:

val mylist = [3, 5, 0, 7, 21]
val fold all_odd = true for x <- mylist {
    if x%2 == 0 {false} else {all_odd}
}

Однако проблема заключается в том, что такое решение не позволяет прервать выполнение раньше момента нахождения нужного результата, так как конструкция break недопустима внутри fold (что оправдано, ведь тело fold — это выражение, обновляющее аккумулятор, а не тело классического цикла). Альтернативой может служить реализация с помощью обычного цикла:

val mylist = [3, 5, 0, 7, 21, 42]
var all_odd = true
for x <- mylist { if x%2 == 0 {false; break} }

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

Чтобы решить эти проблемы, в Ficus введены специализированные макроподобные варианты операции fold:

• all(for i1 <- domain1 ... [вложенные for...] {предикат(i1, ...)}) — возвращает истину, если каждый элемент последовательности удовлетворяет заданному условию.
• exists(for i1 <- domain1 ... [вложенные for...] {предикат(i1, ...)}) — возвращает истину, если хотя бы один элемент удовлетворяет заданному условию.
• find(for i1 <- domain1 ... [вложенные for...] {предикат(i1, ...)}) — находит первый элемент, удовлетворяющий условиям. Если подходящего элемента нет, возбуждается исключение NotFoundError.
• find_opt(for i1 <- domain1 ... [вложенные for...] {предикат(i1, ...)}) — возвращает Some(i1) или Some((i1, ...)) для первого найденного элемента, удовлетворяющего критериям. Возвращает None, если подходящий элемент отсутствует.

Примеры:

val mylist = [3, 5, 0, 7, 21, 42]
println(all(for i <- mylist {i % 2 != 0})) // выводит 'false'
println(exists(for i <- mylist {i <= 0})) // выводит 'true'

fun isprime(n: int) =
    if n <= 1 {false} else if n % 2 == 0 {n == 2}
    else {
        all(for d<-3:floor(sqrt(double(n)))+1:2 {n % d != 0})
    }

// Здесь в заголовке цикла единственным элементом итерации 'x'
// является его индекс i, так что результатом будет кортеж Some((x, i))
val res = find_opt(for x@i <- mylist {x > 0 && !isprime(x)})
println(if res.isnone() {"не найдено"}
  else {val (x,i)=res.value(); f"i={i}: x={x}"}) // выводит 'i=4: x=21'

Генерация коллекций (Comprehension)

Мы уже сталкивались с конструкциями подобного рода, например, когда создавались большие векторы и списки из миллиона элементов:

// [1, 2, 3, ..., 1000000]
val big_vector = vector([for i<-0:1000000 {i+1}])
val big_list = [:: for i<-0:1000000 {i+1}]

По сути, это цикл for, заключённый в квадратные скобки специальной формы Ficus: [for ...] (создание массива), vector([for ...]) или vector(for ...) (создание вектора), [:: for ...] (создание списка). Генерируемая коллекция зависит от типа, указанного в теле цикла. Генерация коллекций позволяет создать коллекцию любого размера с применением формул или преобразований одной коллекции в другую того же или другого типа.

Пример:

val n = 10
// Создать матрицу Гильберта размером 10×10
val hilbert = [for i <- 0:n for j <- 0:n {1./(i + j + 1)}]

val rng = RNG(123u64)
val img = random(rng, (480, 640), 0u8, 255u8)
val (h, w) = size(img)
// Применить размытие изображения фильтром 3×3
val blurred = [for y <- 1:h-1 for x <- 1:w-1 {
      sat_uint8((img[y-1, x-1] + img[y-1, x] + img[y-1, x+1]+
                 img[y, x-1] + img[y, x] + img[y, x+1]+
                 img[y+1, x-1] + img[y+1, x] + img[y+1, x+1])/9.)}]

// Найти разницу между размытым изображением и оригиналом
val diffmap = [for a <- blurred, b <- img[1:h-1, 1:w-1] {abs(a - b)}]

// Умножение матриц (простая неэффективная реализация)
fun matmul(A: double [,], B: double [,]) {
   val (ma, na) = size(A), (mb, nb) = size(B)
   assert(na == mb)
   [
       for i <- 0:ma
         for j <- 0:nb {
            fold s=0. for k <- 0:na {s + A[i,k]*B[k,j]}
         }
   ]
}

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

// Вычислить 'интеграл' для одномерного входного массива:
// S_i = sum_{j < i} (A[j]):
// S = [0, A[0], A[0]+A[1], A[0]+A[1]+A[2], ...]
val A = [1, 2, 3, 4, 5]
var acc = 0
val n = size(A)
val S = [for i<-0:n+1 {
    val prev_acc = acc
    acc = if i < n {acc + A[i]} else {0}
    prev_acc
}]

Фильтрация данных

Ещё один распространённый шаблон обработки данных — пройти по коллекции и оставить только те элементы, которые соответствуют определённым критериям. В функциональных языках часто предоставляется высокоуровневая функция, такая как List.filter, которая доступна и в Ficus. Однако в дополнение к этому Ficus предлагает два дополняющих метода на основе генерации коллекций:

1. Существует необязательное предложение when в заголовке цикла:

for id1 <- domain1, id2 <- domain2, ... [when expr] {...}

Помимо обычных циклов for или fold, её можно применять в списках и векторах (но не в массивах!).

2.Можно использовать оператор continue внутри цикла for и в списке/векторах.

Два эквивалентных варианта компрешения, дающие список простых чисел меньше 100:

fun is_prime(n: int) =
    if n <= 1 {false} else if n % 2 == 0 {n == 2}
    else {
        all(for d<-3:floor(sqrt(double(n)))+1:2 {n % d != 0})
    }

// Используем предложение when
val primes = [for i <- 2:100 when is_prime(i) {i}]

// Используем continue
val primes = [for i <- 2:100 {
                if !is_prime(i) {continue}
                i
              }]

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

Объединение и разделение (Zip & @unzip)

Часто используемые операции генерации коллекций включают объединение (zip) и разделение (unzip) коллекций. Объединение берёт несколько коллекций и создаёт новую, элементами которой становятся кортежи соответствующих элементов. Обратная операция называется unzip.

Объединение коллекций выполняется элементарно:

val a_list = [:: 1, 2, 3, 4, 5]
val b_list = [:: "a", "b", "c", "d", "e"]
// Взять два списка и сформировать вектор пар
val ab_vector = vector(for a <- a_list, b <- b_list {(a, b)})
// Производит вектор([(1, "a), (2, "b"), (3, "c"), (4, "d"), (5, "e")])

Если размеры коллекций различаются, возникает исключение SizeMismatchError.

Разделение (unzip) требует дополнительного синтаксического дополнения:

...
val (a_array, b_array) =
    [@unzip for (a, b) <- ab_vector {(a*10, b.toupper())}]
// Будет создано [10, 20, 30, 40, 50] и
//              ["A", "B", "C", "D", "E"]

Атрибут @unzip перед for сигнализирует компилятору о необходимости формировать на выходе кортеж коллекций, а не единую коллекцию.