На главную

Сборник занимательных задач по языку программирования C
Часть II

Малоизвестные особенности C и C++.

Кодогенерация

Задача

В давние времена для того, чтобы повторить одну и ту же операцию разработчики языков придумали цикл и рекурсию. А можно ли в C и C++ вывести на экран 100 (1000, 1000000, …) строк "Hello, world!\n", не используя цикл и рекурсию?

Обсуждение

Первое решение задачи связано с использованием макроопределений:

#define DO_10_TIMES(x) { x; x; x; x; x; x; x; x; x; x; }
#define DO_100_TIMES(x) DO_10_TIMES(DO_10_TIMES(x))

void main(void)
{
  DO_100_TIMES(std::cout << "Hello, world!\n");
}

Таким образом можно организовать генерацию повторяющегося кода.

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

class Foo
{
public:
  Foo() { std::cout << "Hello, world!\n"; }
};

void main(void)
{
  Foo foos[100];
}

Поскольку для объектов класса вызывается не только конструктор, но и деструктор, мы можем уменьшить размер массива вдвое:

class Foo
{
public:
  Foo() { std::cout << "Hello, world!\n"; }
  ~Foo() { std::cout << "Hello, world!\n"; }
};

void main(void)
{
  Foo foos[50];
}

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

Примеры с повторяющимся кодом не так интересны. Ниже приведён код, в котором с помощью шаблонов осуществляется кодогенерация для вычисления чисел Фибоначчи:

template<int N>
class Fibonacci
{
public:
  inline static int getValue(void) {
    return Fibonacci<N - 1>::getValue() + Fibonacci<N - 2>::getValue();
  }
};

template<> 
class Fibonacci<1>
{
public:
  inline static int getValue(void) {
    return 1;
  }
};

template<>
class Fibonacci<2>
{
public:
  inline static int getValue(void) {
    return 1;
  }
};

. . .

int fibonacci10 = Fibonaccy<10>::getValue();

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

Исходная задача с помощью специализации шаблонов может быть решена так:

template<int N>
inline void printHelloWorld()
{
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
  printHelloWorld<N/10>();
}

template<>
inline void printHelloWorld<1>()
{
  std::cout << "Hello, World!\n";
}

. . .

printHelloWorld<1000>();

Макроопределения

Задача

В языке Pascal существует строгое, но сложное правило расстановки точки с запятой (её нельзя ставить перед else и можно не ставить перед end). В языке C с этим несколько проще, поскольку точку с запятой нужно ставить всегда, кроме составных операторов, заключённых в фигурные скобки.

Да?

Обсуждение

/* Переменные a и b обмениваются значениями. */
#define swap(a,b) { a = a - b; b = a + b; a = b - a; }

if (a > b)
  swap(a, b);
else
  a++, b++;

Этот кусок, кода не будет даже компилироваться, так как после обработки препроцессором приобретает следующий вид:

if (a > b)
  { a = a - b; b = a + b; a = b - a; };
else
  a++, b++;

Если вы заметили, после закрывающей фигурной скобки стоит точка с запятой. Это означает, что между if и else находится два оператора: один — составной, ограниченный фигурными скобками, а другой — пустой, завершающийся точкой с запятой. Такое использование if не соответствует синтаксису языка C и компилятор считает этот код ошибочным.

Мы не должны ставить точку с запятой после swap, но код без разделителя выглядит неправильно:

if(a > b)
  swap(a, b)
else
  a++, b++;

Можно было бы в очередной раз посетовать на препроцессор, однако, существует способ обойти эту проблему. Определение swap может быть записано так:

/* Переменные a и b обмениваются значениями. */
#define swap(a,b) do { a = a - b; b = a + b; a = b - a; } while(false)

if (a > b)
  swap(a, b);
else
  a++, b++;

Тело цикла do/while будет выполнено только один раз, при этом цикл является отдельным оператором, который требует точки с запятой.

Программа, которая печатает свой исходный код

Задача

Первым эту задачу предложил Уозерелл. Затем она упоминалась в журнале «Наука и Жизнь» где утверждали, что её можно решить на любом языке «достаточно высокого уровня».

Докажите, что C — язык «достаточно высокого уровня», напишите программу, честно распечатывающую саму себя. Под «честностью» понимаются следующие условия:

  1. нельзя вызывать функции чтения;
  2. нельзя пользоваться особенностями операционной системы, компилятора и т.д.

Несмотря на простоту формулировки, такую программу не всегда удаётся написать с первого раза.

Обсуждение

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

Проблема в том, что строковые константы должны содержать символы экранирования, а код программы — нет. В коде мы пишем printf(" \"%s\",\n");, а строковая константа будет равна "printf(\" \\\\"%s\\\",\\n\");".

Я решил эту проблему, создав функцию, которая печатает строку в кавычках, экранируя содержимое:

void put_escaped_str(const char* s)
{
  putchar('"');

  while (*s) {
    if (*s == '\\' || *s == '"')
      putchar('\\');

    putchar(*s++);
  }

  putchar('"');
}

Функцию можно упростить, вынеся условие внутри цикла в отдельную функцию. Этот вид рефакторинга называется extract method, то есть извлечение метода. С 1999 года в C можно создавать встраиваемые (inline) функции, что спасает нас от странных ошибок макроопределений.

inline void put_escaped_char(c)
{
  if (c == '\\' || c == '"')
    putchar('\\');

  putchar(c);
}

inline void put_escaped_string(const char* s)
{
  while (*s)
    put_escaped_char(*s++);
}

Будь put_escaped_char макроопределением, вызов put_escpaed_char(*s++) приводил бы к ошибке, поскольку в макроопределениях параметр не копируется, а подставляется. Мы бы получили:

if (*s++ == '\\' || *s++ == '"')
  putchar('\\');

putchar(*s++);

Оператор *s++ содержит побочный эффект — переход к следующему символу строки, и функция в таком виде съедала бы часть символов. Подобные ошибки сложно обнаружить.

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

void put_line(const char* s)
{
  putchar(' ');
  putchar(' ');
  putchar('"');

  put_escaped_string(s);

  putchar('"');
  putchar(',');
  putchar('\n');
}

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

inline void put_prefix()
{
  putchar(' ');
  putchar(' ');
  putchar('"');
}

inline void put_suffix()
{
  putchar('"');
  putchar(',');
  putchar('\n');
}

void put_line(const char* s)
{
  put_prefix();
  put_escaped_string(s);
  put_suffix();
}

Без единого комментария, опираясь только на названия функций, мы подсказыли читателю назначение вызовов putchar. Программа стала понятнее.

На этот этапе уже ясно, как будет выглядеть программа:

#include <stdio.h>

const char* lines[] =
{
  "#include <stdio.h>",
  "",
  "const char* lines[] =",
  "{",
  . . .
};

inline void put_escaped_char(c)
{
  if (c == '\\' || c == '"')
    putchar('\\');

  putchar(c);
}

inline void put_escaped_string(const char* s)
{
  while (*s)
    put_escaped_char(*s++);
}

inline void put_prefix()
{
  putchar(' ');
  putchar(' ');
  putchar('"');
}

inline void put_suffix()
{
  putchar('"');
  putchar(',');
  putchar('\n');
}

void put_line(const char* s)
{
  put_prefix();
  put_escaped_string(s);
  put_suffix();
}

void main()
{
  . . .
}

Очевидно, мы должны напечатать первые четыре строки массива как код, а именно:

#include <stdio.h>

const char* lines[] =
{

Затем мы напечатаем весь массив, как константы, и снова напечатаем строки, начиная с пятой, как код:

void main()
{
  for (int i = 0; i < 4; i++)
    puts(lines[i]);

  for (int i = 0; i < sizeof(lines)/sizeof(char*); i++)
    put_line(lines[i]);

  for (int i = 4; i < sizeof(lines)/sizeof(char*); i++)
    puts(lines[i]);
}

Вопросы может вызвать конструкция sizeof(lines)/sizeof(char*), поэтому я подробнее остановлюсь на том, как она работает. Мы описали перменную lines как const char* lines[]. По правилам C этот тип читается справа налево, то есть это «массив указателей на неизменяемый символ» Указатель на символ обычно означает просто строку, следовательно, всё вместе представляет собой массив строк. Мы не вписали размер массива в квадратные скобки, а это значит, что компилятор вычислит его самостоятельно, посчитав, сколько строк встретилось в тексте программы на самом деле.

sizeof(lines) равен размеру массива в байтах: если массив содержит 30 указателей, и каждый указатель имеет размер 4 байта, то sizeof(lines) будет равен 120. Мы можем получить количество элементов в массиве, разделив его размер на размер элемента. Таким образом, значение sizeof(lines)/sizeof(char*) равно количеству строк в массиве lines. Поскольку значения sizeof(lines) и sizeof(char*) известны во время компиляции, компилятор вычислит sizeof(lines)/sizeof(char*) и будет использовать это значение как константу.

Если бы мы описали lines как const char** lines, его тип был бы «указателем на указатель на неизменямый символ». В этом случае sizeof(lines) стал бы равен размеру указателя, а выражение sizeof(lines)/sizeof(char*) всегда бы равнялось 1.

В остальных аспектах записи const char* lines[] и const char** lines работают совершенно одинаково, но использование массива позволяет нам переложить подсчёт количества строк на компилятор.

#include <stdio.h>

const char* lines[] =
{
  "#include <stdio.h>",
  "",
  "const char* lines[] =",
  "{",
  "};",
  "",
  "inline void put_escaped_char(c)",
  "{",
  "  if (c == '\\\\' || c == '\"')",
  "    putchar('\\\\');",
  "",
  "  putchar(c);",
  "}",
  "",
  "inline void put_escaped_string(const char* s)",
  "{",
  "  while (*s)",
  "    put_escaped_char(*s++);",
  "}",
  "",
  "inline void put_prefix()",
  "{",
  "  putchar(' ');",
  "  putchar(' ');",
  "  putchar('\"');",
  "}",
  "",
  "inline void put_suffix()",
  "{",
  "  putchar('\"');",
  "  putchar(',');",
  "  putchar('\n');",
  "}",
  "",
  "void put_line(const char* s)",
  "{",
  "  put_prefix();",
  "  put_escaped_string(s);",
  "  put_suffix();",
  "}",
  "",
  "void main()",
  "{",
  "  for (int i = 0; i < 4; i++)",
  "    puts(lines[i]);",
  "",
  "  for (int i = 0; i < sizeof(lines)/sizeof(char*); i++)",
  "    put_line(lines[i]);",
  "",
  "  for (int i = 4; i < sizeof(lines)/sizeof(char*); i++)",
  "    puts(lines[i]);",
  "}",
};

inline void put_escaped_char(c)
{
  if (c == '\\' || c == '"')
    putchar('\\');

  putchar(c);
}

inline void put_escaped_string(const char* s)
{
  while (*s)
    put_escaped_char(*s++);
}

inline void put_prefix()
{
  putchar(' ');
  putchar(' ');
  putchar('"');
}

inline void put_suffix()
{
  putchar('"');
  putchar(',');
  putchar('\n');
}

void put_line(const char* s)
{
  put_prefix();
  put_escaped_string(s);
  put_suffix();
}

void main()
{
  for (int i = 0; i < 4; i++)
    puts(lines[i]);

  for (int i = 0; i < sizeof(lines)/sizeof(char*); i++)
    put_line(lines[i]);

  for (int i = 4; i < sizeof(lines)/sizeof(char*); i++)
    puts(lines[i]);
}

В этой программе использована одна малоизвестная особенность C. В массиве все строки разделены запятыми, но запятая стоит также за последней строкой перед закрывающей фигурной скобкой. И этот код компилируется:

  . . .
  "  for (int i = 4; i < sizeof(lines)/sizeof(char*); i++)",
  "    puts(lines[i]);",
  "}", // <-- вот эта запятая
};
  . . .

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

Авторы языков-наследников C тоже реализовали эту возможность, поэтому вы можете вставлять запятую в C++, Java, C# и так далее. Там это можно делать не только с элементами массивов, но и с перечислениями, которых нет в C:

public enum Color
{
  Red,
  Green,
  Blue, // <-- можно
}