Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

Declarative Scala

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

Давайте я сейчас быстро напишу пример, а дальше всё само понятно:
val (a: Double, b: Double) = solve {

    a + b == 3

    a - b == 1

}

// Now a = 2, b = 1.


Ещё пример из http://infoscience.epfl.ch/record/161283/files/KuncakETAL10Comfusy.pdf, в переводе на наш синтаксис:
val (hours: Int, minutes: Int, seconds: Int) = solve {

  0 <= seconds; seconds < 60

  0 <= minutes; minutes < 60

  hours * 3600 + minutes * 60 + seconds == totalSeconds

}

Это их xeno_by (главный специалист по Скальным макросам) в комментах к этому посту показал.

Идея
Предлагается ввести в язык две конструкции, одну для случая когда у уравнения/системы уравнений ожидается одно решение, одну для случая когда несколько:
val (x: A,.. y: B) = solve {equations}

// Throws exception if there is no unique solution



find(x: A,.. y: B) {equations}

// Throws exception if the solution space is infinite,

// otherwise returns Set of solutions of the anonymous type

// case class Record(x: A,.. y: B)


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

О солверах
Кроме численных и алгебраических солверов, которые решают линейные, алгебраические, дифференциальные, диофантовы, рекуррентные и другие уравнения в числах и функциях, существует ещё один невероятно важный для программироания класс солверов.

Это экзистенциально-логические солверы, такие которые позволяют найти решения задачек про n ферзей или дедушку дяди. Их придумали создатели языка пролог, а метод был значительно развит в языке Карри, являющемся обобщением в сторону логического программирования (старого варианта) языка Хаскелл. Кстати говоря, SQLный select это частный случай работы солвера такого типа. Приведу пример, как выглядит решение задачи про ферзей с солверами.

Пример
Итак, существует известная задачка: как расставить n ферзей на шахматном поле n×n так, чтобы они друг друга не били. Есть несколько упрощающих соображений:
– Если ферзи стоят на одной вертикали, они друг друга бьют, следовательно ферзи должны стоять на разных вертикалях.
– Т.к. ферзей n и горизонталей n, на кажной вертикали будет стоять ровно по одному ферзю. Т.е. результат можно записать как последовательность n чисел: «горизонтальная кордината ферзя с первой вертикали», «горизонтальная кордината ферзя cо второй вертикали» и так далее.
– Ферзи также должны стоять на разных горизонталях, так что числа в этой последовательности повторяться не должны.
– .. но встречаться должны все n. Последовательность n неповторяющихся чисел от 0 до (n-1)
называют перестановкой размера n.

А теперь собственно код:
QueensProblem(boardSize: Int) {

  type QueensPosition = Permutation(boardSize)



  // Search for queens sharing a diagonal:

  def diagQueens(y: QueensPosition) = find(x1: Int, x2: Int) {

    x1 < x2

    x2 - x1 == abs(y(x2) - y(x1))

  }



  def solutions = find(p: QueensPosition) diagQueens(p).isEmpty()

}


Сравните этот простой и понятный код с решениями этой же задачи обычными средствами: http://rosettacode.org/wiki/N-queens_problem

Постскриптум
Лет 30 назад бытовало пове(т)рие, что декларативность это офигенно круто и вообще в будущем все будут писать так. Увы, очень часто проще описать что надо делать, чем сформулировать цель настолько чётко, чтобы из постановки цели можно было вывести верное решение. Так что декларативное программирование следует рассматривать не как базисную парадигму, а как приятное дополнение к обычным методам. Однако дополнение невероятно мощное!
Tags: scala
Subscribe

  • (без темы)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 43 comments

  • (без темы)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…