Des и ondre58 для @opendevcast

Язык программирования Янус (Janus) был предложен Кристофером Лутцем, Говардом Дерби и другими сотрудниками Калифорнийского технологического института в качестве языка реализующего модель обратимых вычислений. Синтаксис языка сильно ограничен, что делает его эзотерическим.

Немного физики

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

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

В 1961-ом году Рольфом Ландауэром был сформулирован принцип Ландауэра (который определенным образом следует из квантовой механики), гласящий что в любой вычислительной системе, при стирании 1 бита выделяется минимум W джоулей:

Принцип Ландауэра

Где k - постоянная Больцмана, а T - температура окружающей среды в градусах Кельвина. При 23 °C заначение W приблизительно равно 7×(10^-21) Дж - для сравнения, для того чтобы нагреть один килограм воды на один градус Цельсия необходимо около 4200 Дж. Можно подумать что W - незначительная величина, однако, современные компьютеры работают на очень высоких частотах и стирают ежесекундно огромное количество информации, что дает существенный вклад в энергопотребление. Учесть надо так же, что данный принцип разработан для идеальных моделей - на начало XXI века компьютеры при потере одного бита рассеивали примерно в миллион раз больше тепла чем W, на начало 2010-х разница снизилась до нескольких тысяч.

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

Однако, квантовая механика обратима - стало быть если верить предсталвениям совремнной физики, мир в целом, кажется всё-таки обратим. Александр Охотин

Логическая обратимость

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

Вентиль NOT является обратимым - ведь зная NOT X всегда можно получить X. А вот вентили OR и AND не являются обратимыми так как из x OR y нельзя получить значения x и y (аналогично с AND). Вместо обычного XOR исользуется CNOT - этот вентиль работает почти как XOR, только на выходе он выдает два бита (еще один - вспомогательный, собственно, для сохранения обратимости - подробнее - по ссылке).

Что касается алгоритмов, в теории алгоритмов было доказано, что если некоторую задачу можно решить детерминированым (т.е.выдающим уникальный и предопредленный результат) алгоритмом с памятью s(n), то задачу можно решить обратимым алгоритмом с паматью s(n) + const.

Для реализации таких алгоритмов и был предложен язык Янус

Синтаксис языка Janus

Один из самых частых необратимых операторов в "классических" языках программирования - оператор присвоения, поэтому в Янусе вместо него используется замена (swap), которая меняет местами значение двух переменных. Чтобы изменить значение переменной, используются операторы '+=', '-=', '*=' и '/=', при чем, для сохранения обратимости, в правой части этого оператора не может использоваться та переменная, которую мы хотим изменить. Стоит отметить, что в Янусе по умолчанию все ячейки памяти имеют значение 0.

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

Заметим, что оператор /= не является полностью обратимым, так как в случае целочисленного деления теряется остаток. Это может исправить (см. ниже)

Условие

Условный оператор имеет следующий вид:

if e then
 s 
else
 t
fi f

Схема работы условного оператора

Обратный этому оператору имеет такой вид:

if f then
 s' 
else
 t'
fi e

где s' и t' - обратные операторы s и t соответственно.

Цикл

Цикл имеет следующий синтаксис:

from e do s
loop t
until f

Схема работы цикла

Обратный же цикл будет таким:

from f do s'
loop t'
until e

где s' и t' - обратные операторы s и t соответственно.

Для примера рассмотрим реализацию целочисленного деления с остатком

0 | x1 x2 div mod i
1 | procedure divMod
2 |    from i = 0
3 |        do i += 1
4 |    until x1 < x2*i
5 |    div += i - 1
6 |    mod += x1 - x2*div
7 |    i -= div + 1
8 |    x1 -= x2*div + mod
9 |
10| procedure main
11|    x1 += 13
12|    x2 += 5
13|    call divMod

В строке 0 мы объявляем переменные (в старой версии языка - все переменные - целочисленные).

Со 2 по 4 строку идет описание цикла, в котором считается целочисленное деление x1 на x2 (переменная i - вспомогательная, чуть ниже можно будет увидеть, как можно избавиться от нее). Как видно из кода, как только x1 становится меньше чем x2 помноженное на i, выполнение цикла прекращается. После чего, зная i можно элементарно вычилсить mod и div. В строках 7 и 8 мы просто избавляемся от ненужной памяти, удаляя значения i и x1. Еще одной отличительной особеностью Janus является тот факт, что в нем нет ввода и вывода в классическом понимании (т.к. это уже в некоторой степнени физические операции) - поэтому вместо этого в main-е прописываются значения переменных.

Инвертированая процедура выглядит следующим образом:

procedure divMod
    x1 += x2 * div + mod
    i += div + 1
    mod -= x1 - x2 * div
    div -= i - 1
    from x1 < x2 * i do
        i -= 1
    until i = 0

Что дальше?

С 2009 по 2012 года в Копенгагенском Университете проводились исследования обратимых вычислений в целом и языка Janus в частности. Ознакомиться с их результатами можно здесь: https://topps.diku.dk/pirc/?id=home Они же разработали классический интерпретатор (здесь) языка и обновленный с собственными расширениями (здесь) - там есть несколько примеров программ.

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

Если у Вас есть заинтересованность в этой теме, можете попробовать реализовать следующие программы:

Вычисление квадратичного корня.
Вычисленние целочисленного логарифма по основанию 2.
Сортировка массива.
Поиск в глубину