Index-based programming или зачем нам все эти if, switch, тернарный оператор?

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

if (typeof a ! == "undefined"
&& typeof b ! == "undefined"
&& typeof c === "string")
{ 
    call_function(a, b, c);
    // ...
}

Задумался над самими условиями: они немного странные, хотя и часто встречаются. Внутри «call_function» будет проверяться тип «a» и тип «b», но не тип «с». С другой стороны, количество поддерживаемых сочетаний типов «a» и «b», поддерживаемых функцией конечно, и, скорее всего, фиксировано, а, значит, было бы полезно эти сочетания увидеть. А этот пост натолкнул на мысль, что можно вообще обойтись без условных операторов. Так и зародилась идея отказаться от условных операторов в пользу индексов. Несмотря на то, подход рассматривается в рамках Javascript, он с успехом может быть применен во многих других языках после учета их синтаксических особенностей.

Не надейтесь увидеть тут картины Рембранта мира программирования. Код в статье — произведение Дали. Впрочем, как и сама статья.

Итак, вот как может выглядеть развернутое условие (напишу в своем стиле и сразу в Совершенной дизъюнктивной нормальной форме(СДНФ)):

if(false
  ||(true
    &&typeof a === "string"
    &&typeof b === "string"
    &&typeof с === "string"
  )||(true
    &&typeof a === "object"
    &&typeof b === "string"
    &&typeof с === "string"
  )||(true
    &&typeof a === "number"
    &&typeof b === "string"
    &&typeof с === "string"
  )||(true
    &&typeof a === "string"
    &&typeof b === "object"
    &&typeof с === "string"
  )||(true
    &&typeof a === "object"
    &&typeof b === "object"
    &&typeof с === "string"
  )||(true
    &&typeof a === "number"
    &&typeof b === "object"
    &&typeof с === "string"
  )||(true
    &&typeof a === "string"
    &&typeof b === "number"
    &&typeof с === "string"
  )||(true
    &&typeof a === "object"
    &&typeof b === "number"
    &&typeof с === "string"
  )||(true
    &&typeof a === "number"
    &&typeof b === "number"
    &&typeof с === "string"
  )
){ 
    call_function(a, b, c);
    // ...
}

Получилось как-то длинно. Видим, что тут больше подходит совершенная конъюнктивная нормальная форма(СКНФ):

if(true
  &&(false
    ||typeof a === "string"
    ||typeof a === "number"
    ||typeof a === "object"
  )&&(false
    ||typeof b === "string"
    ||typeof b === "number"
    ||typeof b === "object"
  )&&(false
    ||typeof c === "string"
  )
){ 
    call_function(a, b, c);
    // ...
}

Но тут возникает вопрос, а что делать когда сочетание типов аргументов другое? Почему бы не охватить сразу все возможные варианты. Ошибки не учета какого-то сочетания множества условий встречаются часто, и их сложно обнаружить.
Пусть «а» может иметь типы 'undefined', 'object', 'boolean', 'number', 'string', 'function', но нам важно поведение только при 'object', 'string', 'number', поведение при других типах аналогично поведению при 'undefined'.
Пусть для «b» все будет аналогично.
Тип «с» — учитываем только 'string' и 'undefined'.
Итого, количество вариантов = 4*4*2, каждый из которых соответствует одной элементарной конъюнкции в СДНФ, но теперь мы можем их различать и менять поведение для каждого конкретного случая.

Аналог условного оператора:

  //тут у нас есть переменные "a", "b", "c"
  //нужно выполнить определенные действия
  //в зависимости от их типов

  var a_type_index = {'undefined':0, 'object':1, 'boolean':0, 'number':2, 'string':3, 'function':0}[typeof a]
  var b_type_index = {'undefined':0, 'object':1, 'boolean':0, 'number':2, 'string':3, 'function':0}[typeof b]
  var c_type_index = {'undefined':0, 'object':0, 'boolean':0, 'number':0, 'string':1, 'function':0}[typeof c]

  var index = a_type_index + b_type_index*4 + c_type_index*4*4

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

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

  //тут у нас есть переменные "a", "b", "c"
  //нужно выполнить определенные действия
  //в зависимости от их типов

  var types = ['undefined', 'object', 'boolean', 'number', 'string', 'function']

  var a_type_index = types.indexOf(typeof a)
  //уменьшаем количество различаемых типов
  a_type_index = +'010230'[a_type_index]

  var b_type_index = types.indexOf(typeof b)
  b_type_index = +'010230'[b_type_index]

  var c_type_index = types.indexOf(typeof c)
  c_type_index = +'000010'[c_type_index]

  var index = a_type_index + b_type_index*4 + c_type_index*4*4

Все, что теперь осталось — выбрать по индексу, что делать:

  ;[
    //c has incorrect type
    //b has incorrect type
    //types a: incorrect, object, number, string
    show_err_all, show_err_bc, show_err_bc, show_err_bc,
    //b has object type
    //types a: incorrect, object, number, string
    show_err_ac, show_err_c, show_err_c, show_err_c,
    //b has number type
    //types a: incorrect, object, number, string
    show_err_ac, show_err_c, show_err_c, show_err_c,
    //b has string type
    //types a: incorrect, object, number, string
    show_err_ac, show_err_c, show_err_c, show_err_c,
    //c has string type
    //b has incorrect type
    //types a: incorrect, object, number, string
    show_err_ab, show_err_b, show_err_b, show_err_b,
    //b has object type
    //types a: incorrect, object, number, string
    show_err_a, process, process, process, process,
    //b has number type
    //types a: incorrect, object, number, string
    show_err_a, process, process, process, process,
    //b has string type
    //types a: incorrect, object, number, string
    show_err_a, process, process, process, process
  ][index](a, b, c)

Итак, первый принцип индекс-ориентированного программирования: охват всех вариантов.

Естественно условия могут быть любыми. Зачем ограничиваться одним условным оператором, когда есть другие ему подобные.

Аналог тернарного оператора:

  var b_status = false

  //с использованием тернарного оператора
  var str_status = b_status? 'ok': 'this is false'

  //с использованием индексов
  var str_status = ['this is false','ok'][+b_status]

Знак "+" конвертирует переменную b_status в числовой тип, поскольку индекс должен быть числом. Обратите внимание, что сначала идет выражение для невыполнения условия.

Аналог оператора множественного выбора:

  var i_state = 1

  //с использованием switch
  switch (i_state) {
    case 1:
      console.log('you select 1')
      break
    case 2:
      console.log('you select 2')
      break
    default:
      console.log('you select another')
  }


  //с использованием индексов
  i_state = 0|[0,1,2][i_state]

  //если нужно получить числовой индекс по строке
  //i_state = 0|{'one':1, 'two':2}[str_state]
  //i_state = ['one', 'two'].indexOf(str_state)+1

  [
    function(){
      //default
      console.log('you select another')
    },function(){
      //i_state == 1
      console.log('you select 1')
    },function(){
      //i_state == 2
      console.log('you select 2')
    }
  ][i_state]

Также как для тернарного оператора первым(нулевым) идет случай для false, для switch-а первым идет случай default, что в общем-то удобно, поскольку он один, его наличие обязательно — это некий аналог нуля.

Второй принцип индекс-ориентированного программирования: наличие особого нулевого варианта.

Однако, идея индекс-ориентированного программирования несколько шире, чем замена условных операторов. Еще пара примеров.

Генерации перестановок из индекса:

function factorial(n){ 
  if(n<=1) return 1; 
  var ret = 1; 
  for(var i=2; i<=n; i++) ret *= i; 
  return ret; 
}

function i_to_insert_order(n, i){
  var arr = []
  var i_tmp = i
  for(var j=0; j<n; j++){
    var a = i_tmp%(j+1)
    arr[j] = a
    i_tmp = ~~(i_tmp/(j+1))
  }
  return arr
}

function correct(arr){
  var n = arr.length;
  for(var i=1; i<n; i++){
//    for(var j=0; j<i; j++){
    for(var j=i-1; j>=0; j--){
      //if(arr[j]>=arr[i]) arr[j]++
      arr[j] += arr[j]>=arr[i]
    }
  }
}

//correct([0,0,0,0,0]) == [4,3,2,1,0]

var n = 5
var arr_perm = []
for(var i=0; i<factorial(n); i++){
  var arr = i_to_insert_order(n, i)
  //arr = 0, 0..1, 0..2, 0..3, 0..4
  correct(arr)
  arr_perm.push(arr)
}
arr_perm.reverse()

//arr_perm.length == factorial(n)
//arr_perm[0] == [0,1,2,3,4]
//arr_perm[-1] == [4,3,2,1,0]

Немного пояснений: "~~(x)" — короткая запись "Math.floor(x)", о которой узнал из видео с livecoding. При использовании короткой записи следует соблюдать ограничение: 0<=x<=2147483647.9999998(подобрано экспериментально). Для сравнения ограничение для "Math.floor": -9007199254740992<=x<9007199254740993. Обращение массива нужно, чтобы получить перестановки в лексикографическом порядке. По индексу получаем(i_to_insert_order) одну из возможных последовательностей вставки элементов. В принципе, ее достаточно, чтобы получить перестановку реальных элементов:

function insert(arr, i, elem){arr.splice(i, 0, elem)}

//исходное множество
var elements = ['word', 'symbol', 'face', 'colors', 'song']
//получаем 35-ю последовательность вставки
var order = i_to_insert_order(5, 35)
var arr = []
for(var i=0; i<order.length; i++) insert(arr, order[i], elements[i])
//arr == ['word', 'song', 'colors', 'symbol', 'face']

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

Третий принцип индекс-ориентированного программирования: нумерация вариантов.

Генерация числа Фибоначчи по номеру:

Воспользуемся сокращенной формулой Бине. Затем, сравним результат с табличным.

  const φ = (1+Math.sqrt(5))/2

  function fib_by_index(i){
    return Math.round(Math.pow(φ, i)/Math.pow(5,0.5))
  }

  fib_by_index(6) == 8
  fib_by_index(50) == 12586269025

И, наконец, четвертый принцип индекс-ориентированного программирования: алгоритмы сложности О(1).

Преимущества:

• быстродействие(при большом числе условий)
• устойчивость к атакам по времени

Недостатки:

• повышенный расход памяти
• нужно вычислять все условия для индекса

объект Number
перестановка
числа Фибоначчи
вычислительная сложность
Steve McConnell. Code Complete, Second Edition. Глава 18: Табличные методы