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

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

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

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

Вообще говоря, шаблоны вошли в состав языка С++ совсем с другими целями, и их реальные возможности исследователи открыли почти что случайно. Одной из первых метапрограмм такого рода принято считать программу для определения простоты числа за авторством Эрвина Анруха из компании Siemens, написанную в 1994 году. Примечательно, что для вывода результата в процессе компиляции программы тогда использовались сообщения об ошибках. Весьма символично.

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

 

Template Temple

Итак, нам предстоит реализовать множество логических операций времени компиляции с помощью шаблонов. Компилятором был выбран (вернее, оказался) GCC, с опцией -std=c++17 для расширенной поддержки метапрограммирования. Не так давно Комитет по стандартизации языка принял в Праге новую версию С++20, но ожидать, что все производители компиляторов ее поддержат, наверное, пока рановато.

И последнее замечание, прежде чем мы перейдем непосредственно к коду, для тех, кто мало знаком с шаблонами С++. Нужно понимать, что программирование на шаблонах представляет собой работу с типами, а не с переменными, как обычно. Взаимоотношения между шаблоном, типом, классом и объектом класса (переменной) мы обсудим чуть ниже, ну а пока заведем парочку структур для представления нуля и единицы в нашей будущей библиотеке логических элементов.

#include <iostream>
#include <type_traits>
#include <tuple>

using std::cout;
using std::endl;

struct I {
  /* HIGH, TRUE, ONE */
};

struct O {
  /*LOW, FALSE, ZERO */
};

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

Пойдем дальше и создадим пару байтов с помощью встроенных в язык кортежей (они появились в С++11). Для этого используем директиву using, которая по сути представляет собой продвинутый вариант typedef из языка С. Опять же важно заметить: с их помощью мы не создаем новой переменной, а только лишь объявляем некоторый новый тип.

using op1 = std::tuple< O, O, O, O, I, O, I, I >;
using op2 = std::tuple< O, I, O, O, O, O, I, O >;

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

template<typename T>
void _print();

template<>
void _print<O>() {
  cout << "O " << endl;
}

template<>
void _print<I>() {
  cout << "I " << endl;
}

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

template<typename A, typename B>
struct NAND {
  using result = std::conditional_t<(std::is_same<A, B>::value &&
    std::is_same<A, I>::value), O, I>;
};

В целом не самый сложный кусочек кода, но на всякий случай разберем его подробнее, чтобы в дальнейшем не возвращаться к очевидным вещам. Тут мы объявляем шаблон структуры с двумя шаблонными параметрами. В составе этой структуры единственное «поле» — директива using, которая выводит тип результата как возвращаемое значение шаблона std::conditional_t.

Этот шаблон имеет вид std::conditional_t<условие, тип1, тип2> и по сути является аналогом тернарного оператора ? : из стандартного С++. Если условие (первый параметр) принимает значение true, то возвращается тип1 (второй параметр), иначе — тип2 (третий параметр).

По аналогии с тернарным оператором инструкции std::conditional_t можно вкладывать друг в друга, формируя тем самым выбор сразу из нескольких доступных вариантов. Более того, можно совмещать последовательности std::conditional с тернарными операторами в качестве выражения для выведения первого параметра. Таким образом, у нас есть полноценная возможность программировать нетривиальную логику элементов. Хотя, конечно, монструозный вид подобных конструкций несколько настораживает (спойлер: то ли еще будет!).

Шаблон std::is_same гораздо тривиальнее в применении и банально сравнивает типы в своих угловых скобках. Значение результата (логический ноль или единица) можно забрать из его поля value.

Тут возникает первая возможность «грязного» хака. Формально ничто не мешает нам не сравнивать типы наших шаблонных параметров напрямую. Мы вполне можем определить шаблон функции, которая бы сводила наши пользовательские типы к стандартному типу bool, и, таким образом, строить логику и внутреннее представление элемента на его основе.

template<typename T>
bool state();

template<>
bool state<O>() {
  return false;
}

template<>
bool state<I>() {
  return true;
}

template<typename A, typename B>
struct NAND {
  using result = std::conditional_t<(state<A>() == state<B>()) &&
    (state<A>() == true), O, I>;
};

Но я так делать, конечно, не буду. Это все равно что играть в видеоигры на легком уровне сложности — никакой радости от достижения результата.

Код для всех остальных базовых блоков выводится уже с помощью нашей структуры NAND.

template<typename A, typename B = A>
struct NOT {
  using result = typename NAND<A,A>::result;
};

template<typename A, typename B>
struct AND {
  using result = typename NOT<typename NAND<A, B>::result>::result;
};

template<typename A, typename B>
struct OR {
  using result = typename NAND<typename NOT<A>::result,
    typename NOT<B>::result>::result;
};

template<typename A, typename B>
struct NOR {
  using result = typename NOT<typename OR<A, B>::result>::result;
};

template<typename A, typename B>
struct XOR {
  using result = typename NAND<typename NAND<typename NAND<A, B>::result, A>::result, typename NAND<typename NAND<A, B>::result, B>::result>::result;
};

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

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

template<typename A, typename B>
struct HALFADDER {
  using sum   = typename XOR<A, B>::result;
  using carry = typename  AND<A, B>::result;
};

template<typename A, typename B, typename C = O>
struct FULLADDER {
  using sum = typename HALFADDER<typename HALFADDER<A, B>::sum, C>::sum;
  using carry = typename OR<HALFADDER<A, B>::carry, HALFADDER<A, B>::sum, C>::carry>::value;
};

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

Действительно, стандартно функция отрицания НЕ (NOT) принимает на вход только один параметр. Но в целях стандартизации мы унифицируем ее список шаблонных параметров с остальными вентилями, добавляя второй «вход В», чтобы иметь возможность применять ее даже в тех местах, где требуются два входа. Аналогично и с шаблоном сумматора.

 

В ушах — бит, в классе — тип

Прежде чем мы перейдем к рассмотрению вложенных шаблонов структур (классов) и шаблонов в качестве параметров шаблонов (в том числе использованию шаблона контейнера std::tuple), предлагаю сделать небольшое лирическое отступление и более детально рассмотреть взаимоотношения между нашими абстрактными категориями.

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

Тип переменной, напротив, в программу никак явно не попал. В методологии ООП, которой стараются придерживаться в С++, класс представляет собой тип, а конкретный объект класса — переменную, сконструированную по некоторому шаблону. Сколько полей имеет объект, какие права доступа к ним — все это содержится в определении класса.

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

Сам по себе шаблон структуры NAND не имеет смысла далее в нашей программе, за исключением применения в каком-либо списке параметров в качестве шаблонного параметра шаблона. Что именно интересует компилятор после его определения, так это конкретизация шаблонной структуры NAND с помощью существующих типов. В нашем случае это O и I. Только тогда появляется новый тип (при условии, что определение шаблонной структуры допускает такое использование).

Резюмируя: в метапрограммировании С++ шаблон — это тип, а тип — это переменная. В сущности, не так уж и сложно.

Продолжение доступно только участникам

Вариант 1. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», увеличит личную накопительную скидку и позволит накапливать профессиональный рейтинг Xakep Score! Подробнее

Вариант 2. Открой один материал

Заинтересовала статья, но нет возможности стать членом клуба «Xakep.ru»? Тогда этот вариант для тебя! Обрати внимание: этот способ подходит только для статей, опубликованных более двух месяцев назад.


1 комментарий

  1. Аватар

    le

    14.05.2020 в 13:11

    Креативно. Спасибо.

Оставить мнение