wc на D: 712 символов без единого ветвления

После прочтения "Побиваем С программой в 80 строк на Хаскеле", которую я нашел на ХакерНьюс, я решил, что D может и лучше. И я написал wc на D.

Прим.пер. Я предложил вышеупомянутую статью перевести 0xd34df00d, но он предпочел сделать по мотивам свою «Побеждая C двадцатью строками Haskell: пишем свой wc». И теперь статьи множатся как перепевы «чеканной монетой».

Программа

Состоит из одного файла — 34 строки и 712 символов.

import std.stdio : writefln, File;
import std.algorithm : map, fold, splitter;
import std.range : walkLength;
import std.typecons : Yes;
import std.uni : byCodePoint;

struct Line {
	size_t chars;
	size_t words;
}

struct Output {
	size_t lines;
	size_t words;
	size_t chars;
}

Output combine(Output a, Line b) pure nothrow {
	return Output(a.lines + 1, a.words + b.words, a.chars + b.chars);
}

Line toLine(char[] l) pure {
	return Line(l.byCodePoint.walkLength, l.splitter.walkLength);
}

void main(string[] args) {
	auto f = File(args[1]);
	Output o = f
		.byLine(Yes.keepTerminator)
		.map!(l => toLine(l))
		.fold!(combine)(Output(0, 0, 0));

	writefln!"%u %u %u %s"(o.lines, o.words, o.chars, args[1]);
}

Разумеется, он использует Фобос, стандартную библиотеку D, но почему бы и нет? Фобос прекрасен, и поставляется с каждым компилятором D. Сама программа не содержит ни одного оператора if. А в реализации wc на Haskell используется несколько if. Программа на D, кроме основной, содержит еще три крошечные функции. Я мог бы легко поместить всю функциональность в одну range-цепочку, но тогда она, вероятно, превысила бы 80 символов в строке. Это основной принцип стиля кода.

Производительность

А wc на D быстрее, чем coreutils wc? Нет, но мне понадобилось 15 минут, чтобы написать свою версию (пришлось поискать walkLength, потому что я забыл название функции).

Память:

wc на Haskell быстрее? Для больших файлов, безусловно, но он использует многопоточность. Для маленьких файлов GNU coreutils все еще выигрывает. На данном этапе моя версия, скорее всего, ограничена IO, и в любом случае она достаточно быстра.

Я не буду утверждать, что один язык быстрее другого. Если вы потратите время на оптимизацию микро-бенчмарка, то, скорее всего, выиграете. Но не в реальной жизни. Но я буду утверждать, что функциональное программирование в D почти догоняет ФП в Хаскелле.

Немного о range в D

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

void popFront();

и двух членов либо свойств

T front;
bool empty;

Т — это обобщенный тип элементов, которые range итерирует.

В D range являются специфическими типами. Когда range попадает в оператор foreach, компилятор выполняет небольшую модификацию.

foreach (e; range) { ... }

превращается в

for (auto __r = range; !__r.empty; __r.popFront()) {
    auto e = __r.front;
    ...
}

auto e = вычисляет тип и эквивалентен T e =.
Поняв это, легко создать range, который может быть использован foreach.

struct Iota {
	int front;
	int end;

	@property bool empty() const {
		return this.front == this.end;
	}

	void popFront() {
		++this.front;
	}
}

unittest {
	import std.stdio;
	foreach(it; Iota(0, 10)) {
		writeln(it);
	}
}

Iоta — это очень простой пример range. Она функционирует как генератор, не имея нижележащей коллекции. Она выполняет итерацию целых чисел от начала до конца с шагом в один. Этот фрагмент раскрывает немного синтаксис D.

@property bool empty() const {

Атрибут @ property позволяет использовать функцию empty так же, как и переменную-член (вызов функции без скобок). Атрибут const в конце означает, что мы не модифицируем данные экземпляра, для которого мы вызываем empty. Встроенный юнит-тест печатает числа от 0 до 10.
Еще одна небольшая особенность — отсутствие явного конструктора. Структура Iota имеет две переменных-члена типа int. В операторе foreach в тесте мы создаем экземпляр Iota так, как будто у него есть конструктор, который принимает два int. Это структурный литерал. Когда компилятор D это видит, а у структуры нет соответствующего конструктора, то в соответствии с порядком объявления переменных — членов структуры будут присваиваться int.
Отношения между тремя членами просты. Если empty — ложь, front гарантированно вернет новый элемент, следующий в итерации, после вызова popFront. После вызова popFront значение empty могло измениться. Если это верно, то это означает, что больше нет элементов для итерации и дальнейшие вызовы front недействительны. Согласно документации по InputRange:

• front может быть корректно вычислен, если и только если empty вернула или вернула бы false.
• front может быть вычислен несколько раз без вызова popFront или иного мутирования range или нижележащих данных, и он дает один и тот же результат для каждого вычисления.

Использовать foreach-выражения, или циклы, не очень функционально. Допустим, мы хотим отфильтровать все нечетные числа для Iota. Мы могли бы поместить if внутри блока foreach, но это только сделает хуже. Было бы лучше, если бы у нас был range, который принимает range и предикат, который решает, подходит ли элемент или нет.

struct Filter {
	Iota input;
	bool function(int) predicate;

	this(Iota input, bool function(int) predicate) {
		this.input = input;
		this.predicate = predicate;
		this.testAndIterate();
	}

	void testAndIterate() {
		while(!this.input.empty
				&& !this.predicate(this.input.front))
		{
			this.input.popFront();
		}
	}

	void popFront() {
		this.input.popFront();
		this.testAndIterate();
	}

	@property int front() {
		return this.input.front;
	}

	@property bool empty() const {
		return this.input.empty;
	}
}

bool isEven(int a) {
	return a % 2 == 0;
}

unittest {
	foreach(it; Filter(Iota(0,10), &isEven)) {
		writeln(it);
	}
}

Filter опять-таки очень прост: нужны Iota и указатель на функцию. При построении Filter мы вызываем testAndIterate, который берет элементы из Iota до тех пор, пока она не окажется пустой, либо предикат не вернет false. Идея в том, что предикат решает, что отфильтровать, а что оставить. Свойства front и empty просто транслируются к Iota. Единственное, что на самом деле выполняет работу — это popFront. Он выдает текущий элемент и вызывает testAndIterate. Вот и все. Это реализация фильтра.
Конечно, в testAndIterate есть цикл while, но переписывать его с помощью рекурсии, на мой взгляд, просто глупо. Что делает D замечательным, так это то, что вы можете использовать подходящий способ для каждой задачи. Функциональное программирование — это хорошо, и часто щеголяет, но иногда это не так. Если немного инлайн-ассемблера будет необходимо или более приятным, используйте.
Вызов Filter все еще выглядит не очень хорошо. Предполагая, что вы привыкли читать слева направо, Filter появляется до Iota, даже если он выполняется после Iota. D не предусматривает pipe-оператора, но использует унифицированный синтаксис вызова функций (UFCS). Если выражение может быть неявно преобразовано в первый параметр функции, то функция может быть вызвана так же, как если бы она являлась функцией-членом этого выражения. Это довольно сложно, я понимаю. Поможет пример:

string foo(string a) {
	return a ~ "World";
}

unittest {
	string a = foo("Hello ");
	string b = "Hello ".foo();
	assert(a == b);
}

В приведенном выше примере показаны два вызова функции foo. Как следует из assert, оба вызова эквивалентны. Что это значит для нашего примера Iota Filter? UFCS позволяет нам переписать юнит-тест так:

unittest {
	foreach(it; Iota(1,10).Filter(&isEven)) {
		writeln(it);
	}
}

Реализация map/transform для range теперь должна быть доступна каждому читателю. Конечно, фильтр можно сделать более абстрактным, используя шаблоны, но это просто детали, ничего концептуально нового.
Конечно, есть разные типы range, например, двунаправленные. Угадай, какие возможности это тебе дает. Небольшой совет: в двунаправленном диапазоне есть два новых примитива, называемых back и popBack. Есть и другие типы range, но после того, как вы поймете input range, показанный выше дважды, вы практически все их узнали.
P.S. Просто для ясности, не реализуйте свой собственный filter, map или fold; в D стандартной библиотеке Phobos есть все, что вам нужно. Загляните в std.algorithm и std.range.

Об авторе

Роберт Шадек получил степень магистра информатики в Университете Ольденбурга. Его магистерская диссертация называлась " DMCD — распределенный многопоточный компилятор D с кэшированием", где он работал над созданием D-компилятора с нуля. Он был аспирантом по информатике в 2012-2018 гг. в университете г. Ольденбурга. Его докторская диссертация посвящена системам кворумов в сочетании с графами. С 2018 года он с удовольствием использует D в своей повседневной работе, работая в компании Symmetry Investments.

О Symmetry Investments

Symmetry Investments — глобальная инвестиционная компания с офисами в Гонконге, Сингапуре и Лондоне. Мы ведем бизнес с 2014 года после успешного отделения от крупного нью-йоркского хедж-фонда.
В компании Symmetry мы стремимся к разумному принятию на себя рисков для создания ценности для наших клиентов, партнеров и сотрудников. Мы извлекаем выгоду из нашей способности генерировать беспроигрышные контракты — в самом широком смысле этого слова. Win-Win — это наш фундаментальный этический и стратегический принцип. Генерируя беспроигрышные варианты, мы можем создавать уникальные решения, сочетающие в себе перспективы, которые обычно воспринимаются как несовместимые или противоположные, и охватывающие все лучшее, что может предложить каждая из сторон. Мы по-новому интегрируем арбитраж с фиксированным доходом с глобальными макростратегиями. Мы изобретаем и развиваем технологию, которая фокусируется на потенциале интеграции человека и машины. Мы создаем системы, в которых машины делают то, что они делают лучше всего, поддерживая людей в том, чтобы они делали то, что они делают лучше всего. Мы создаем меритократию, основанную на сотрудничестве: культуру, в которой индивидуальный вклад служит как личным, так и коллективным целям — и вознаграждается соответствующим образом. Мы ценим как чувство собственности, так и командный дух сотрудничества, самореализацию и общность.
Люди из компании Symmetry Investments являются активными участниками сообщества D с 2014 года. Мы спонсировали разработку excel-d, dpp, autowrap, libmir и другие проекты. Мы запустили Symmetry Autumn of Code в 2018 году и провели DConf 2019 в Лондоне.

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

Автор: Siemargl

Источник