Нередко в RIDE нет примитивов цикла / for / goto. Этот факт постоянно расстраивает разработчиков, которым необходимо просмотреть коллекцию, вычислить сумму массива, отфильтровать список элементов, соответствующих массиву подписей, по массиву открытых ключей. Однако это ограничение не связано с недосмотром или нежеланием обеспечить надлежащий опыт разработчика: это вопрос ограничения среды: механизм выполнения (а не язык программирования) должен оставаться не-полностью по Тьюрингу.

Но сначала немного истории.

Полнота по Тьюрингу

Определение термина связано с загадочной машиной Тьюринга, которая манипулирует символами на полосе ленты в соответствии с таблицей правил. Но что это на 2019 год? Проще говоря, полнота языка по тьюрингу означает способность кодировать любой алгоритм в рамках языковых примитивов. Любые средства любые - включая грубый взлом сигнатуры эллиптической кривой или даже бесконечную сигнатуру, которая никогда не даст результата, например:

while(true) {
  i = 0
}

Блокчейн, RIDE

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

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

В Waves мы применяем другую модель: RIDE явно не является завершенным по Тьюрингу, в языке нет циклов и циклов, в его байт-коде нет оператора, аналогичного обратному GOTO. Это позволяет нам заранее рассчитать вычислительные затраты и отказаться даже не от выполнения, а от развертывания самого dApp.

Проблема с «foreach»

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

let arr = getString(this,"key").extract().split("|")
arr.foreach(a => a + "A") # imaginary code

В этом примере компилятор попадает в последнюю строку и не знает, что такое arr, и поэтому не может оценить стоимость выполнения строки, как и вы, кстати.

Если вы поместите обход списка внутрь обхода списка, все станет уродливо полиномиально быстрее. Давайте также проведем интенсивные вычисления в map

let arr = getString(this,"key").extract().split("|")
arr.map { a =>
   arr.map { b => 
      arr.map { c =>
         sigVerify(foo,bar,baz)
      }
   }
}

Это N³ проверок подписи, при этом N неизвестно. Вы можете сказать что-то вроде Просто не разрешайте циклы в циклах! или Просто не разрешайте sigVerify в цикле!, но если хорошо подумать , вы увидите, насколько это плохое решение. Несмотря на то, что он не решает никаких проблем, не позволяет правильно оценить стоимость, он делает язык неконтекстным, что делает его очень плохим дизайнерским решением.

Петли

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

let arr = ...
arr.map(10, { a => a + 1 })

Что делать, если массив больше 10? Тогда давайте сгенерируем исключение.
Но если параметр имеет тип Integer, это тоже неизвестно:

let arr = ...
let steps = arr.size()
arr.map(steps, { a => a + 1 })

Макросы

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

Семейство функций складывания

Одна функция высшего порядка, существующая во множестве языков, - это семейство fold, foldLeft и foldRight. Один из Scala выглядит так так:

def fold[A](col: List[A], z: A, op: (A, A) ⇒ A): A
def foldLeft[B](col: List[A], z: B, op: (B, A) ⇒ B): B
def foldRight[B](col: List[A], z: B, op: (A, B) ⇒ B): B

где z - это значение, с которого мы начинаем сворачивать, а затем «модифицируем» его с помощью функции op и следующего элемента в коллекции.

Эти функции чрезвычайно мощны: с их помощью можно определить sum, filter, zip, exists - почти все, что угодно. Нет необходимости в foreach.

FOLD ‹N› Макросы для RIDE

Кулак, немного интуиции, как его использовать:

func sum(a:Int, b:Int) = a + b
let arr = [1,2,3,4,5]
let sum = FOLD<5>(arr, 0, sum) # result: 15

Это гласит: выполнить до 5 шагов, на каждом шаге получить результат накопления, следующий элемент, применить функцию sum к паре, вернуть результат накопления.

Функция filter:

func filterStep(a: Int, accumulated: List[Int]) = 
   if (a % 2 == 0) then a :: acumulated else accumulated
let arr = [1,2,3,4,5]
let evens = FOLD<5>(arr, 0, filterStep) # result: [2,4]*

* Фактически вы получите [4,2], но это решаемо

При компиляции компилятор просто разворачивает:

let result = FOLD<5>(arr, acc0, function)

примерно так:

let restult = {
   let size = arr.size()
   if(size == 0) then acc0 else {
      let acc1 = function(acc0, arr[0])
      if(size == 1) then acc1 else {
         let acc2 = function(acc1, arr[1])
         if(size == 2) then acc2 else {
            let acc3 = function(acc2, arr[2])
            if(size == 3) then acc3 else {
               let acc4 = function(acc3, arr[3])
               if(size == 4) then acc4 else {
                  let acc5 = function(acc4, arr[4])
                  if(size == 5) 
                     then acc5 
                     else 
                       throw("Too big array, max 5 elements")
}}}}}}

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

Компромиссы

Плюсы:

  • sum, mult, filter, contains, exists, average - все, что можно выразить с помощью fold
  • Не нужно менять оценщик или оценщик - все происходит во время предварительной компиляции
  • По этой причине для новой функциональности не нужны хардфорки.

Минусы:

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

Multisig

По неизвестной причине один из главных вопросов в нашем примере с несколькими подписями: Как сделать требование для позиций подписей в массиве доказательств нестрогим, чтобы можно было выгружать подписи к транзакции по мере их поступления? Во всяком случае, вот как (4 из 5):

{-# STDLIB_VERSION 3 #-}
{-# CONTENT_TYPE EXPRESSION #-}
{-# SCRIPT_TYPE ACCOUNT #-}
# array of 5 public keys
let pks = [base58'', base58'', base58'', base58'', base58'']
# inner fold step for each signature
func signedBy(pk:ByteVector) = {
   # is signed by the public key or not
   func f(acc: Boolean, sig: ByteVector)
      = acc || sigVerify(tx.bodyBytes, sig, pk)
   FOLD<5>(tx.proofs, false, f)
}
# outer fold step for each public key
func signedFoldStep(acc:Int, pk:ByteVector)
   = acc + (if(signedBy(pk)) then 1 else 0)
# comparing total number of correct signatures
# to required number of correct signatures
FOLD<5>(pks, 0, signedFoldStep) == 4

Немного загадочно и слишком кратко, чтобы понять с первого взгляда, но это работает.

Ну и что, теперь полная версия Тьюринга?

Почти отсутствует FOLD<INFINITY>. Но в dApps этого никогда не должно происходить. Допустим, это Достаточно полного Тьюринга.

TL; DR. Циклы моделируются с помощью макросов FOLD ‹N›, что требует максимального количества итераций во время компиляции с последующим преобразованием в базовые примитивы.