Pull to refresh

Maximum overload — приключения в JavaScript в мире С++

Reading time 12 min
Views 12K
Как правильно расширить возможности языка программирования используя перегрузку операторов.

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

«А зачем, ведь то, что вы предлагаете, можно сделать имеющимися средствами языка».

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

Хотя физикам и математикам эта возможность пришлась по душе, программистам, в том числе создалелям С++ перегрузка операторов никогда особо не нравилась. Слишком сложное дело, много неявностей, поэтому за перегрузкой операторов закрепилось мнение чего-то вредного и применяемого в редких случаях.

Сегодня я попробую показать почему это так сложно и как правильно использовать перегрузку на примере создания одного нового типа под названием var поведение которого будет максимально приближено к аналогичному типу в JavaScript.

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

Для начала объявим сам класс:

struct var {
};


(Почему struct а не class? Разница между ними лишь в том, что в struct по-умолчанию все члены public. Для упрощения читаемости кода будет struct.)

Попробуем поместить в var числовое значение и строковое:

struct var {
	char *str;
	double num;
};



Теперь надо написать конструкторы. Они вызываются когда вы пишете:

var i = 100;
var s = "hello";

struct var {
	char *str;
	double num;
	var (double initial) {
		num = initial;
	}
	var (char *initial) {
		str = initial;
	}
}


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

var i = 100, s = "hello";
log(i);
log(s);


Как этого добиться?

void log(var x) {
	....
	а тут то что написать?
}


Как нам узнать, какое из двух содержимых используется в данном экземпляре var?

Ясно, что надо добавить внутренний тип. Но как это сделать? Логично использовать enum:

enum varType { varNum, varStr };


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

struct var {
	varType type;
	char *str;
	double num;
	var (double initial); 
	var (char *initial);
};


Теперь в конструкторах надо присвоить тип:

var::var (double initial) {
	type = varNum;
	num = initial;
}
var::var (char *initial) {
	type = varStr;
	str = initial;
}


Ну что же, теперь можно вернуться к log():

void log(var x) {
	if (x.type == varNum) printf("%f\n", x.num);
	if (x.type == varStr) printf("%s\n", x.str);
}


И вот теперь-то нам и надо перекрыть оператор присваивания:

void var::operator = (double initial) {
	type = varNum;
	num = initial;
}

void var::operator = (char *initial) {
	type = varStr;
	str = initial;
}


Теперь можно писать:

var a = 10, b = "hello";


Интересно, что оператор присвоения получился полная копия конструктора. Может быть стоит повторно использовать? Так и сделаем. Везде в «конструкторе присвоения» можно просто вызывать «оператор присвоения».

На данный момент вот наш полный рабочий код:

#include <stdio.h>

enum varType { varNum, varStr };

struct var {
	varType type;
	char *str;
	double num;
	var (double initial); 
	var (char *initial);
	void operator = (double initial);
	void operator = (char *initial);
};

var::var (double initial) {
	(*this) = initial;
}
var::var (char *initial) {
	(*this) = initial;
}

void var::operator = (double initial) {
	type = varNum;
	num = initial;
}

void var::operator = (char *initial) {
	type = varStr;
	str = initial;
}

void log(var x) {
	if (x.type == varNum) printf("%f\n", x.num);
	if (x.type == varStr) printf("%s\n", x.str);
}

int main() {
	var x = 100, s = "hello";
	log(x);
	log(s);
}


А что если мы просто напишем:

int main() {
	var y;
}


Нас обругает компилятор! Мы не можем объявлять переменную не инициализировав её. Непорядок, в чём же дело? А в том, что все наши конструкторы требуют начального значения.

Нам нужен «пустой» конструктор, он же — конструктор по умолчанию, default constructor. Но чему будет равна переменная если она ещё ничему не равна? Ещё неизвестно будет ли она числом или строкой, или чем-то ещё.

Для этого вводится понятие «пустое значение», известное как null или undefined.

enum varType { varNull, varNum, varStr };

var::var() {
	type = varNull;
}


Теперь можно просто объявлять переменные, не думая о типе.

var a, b, c;


И уже в коде присваивать значения:

a = 1; b = "foo";


Но мы ещё не можем написать:

a = b;


Нам нужен оператор присвоения var=var:

void var::operator= (var src) {
	type = src.type;
	num = src.num;
	str = src.str;
}


При присвоении изменится тип! И «а» станет строкой.

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

Сначала нам нужен новый тип в enum:

enum varType { varNull, varNum, varStr, varArr };


Теперь указатель на буффер элементов, и размер:

struct var {
	...
	int size;
	var *arr;
	...
}


Теперь перегрузим оператор доступа к элементу:

struct var {
	...
	var operator [](int i);
	...
}


Такой оператор называется «subscript operator» или оператор индекса.

Наша цель: хранить в массиве элементы типа var. То есть речь идёт о рекурсии.

Кстати, таким же оператором, нам придётся обращаться к отдельным символам в строке, и к свойствам объекта. Но в случае объекта на входе будет строка. Ведь ключ это строковое значение:

var operator [](char *key);


Нет, так не годится. Нам нужен не указатель на буфер символов, а именно строка, сделаем так:

struct var {
	...
	var operator [](var key);
	...
}


Тогда, когда всё заработает, мы сможем писать:

x[1]


или

x["foo"]


Компилятор преобразует в var! Почему? Ведь у нас уже есть конструкторы из литералов числа и строки.

Можно будет и так писать:

y = "foo";
x[y];


Кстати, литерал, (literal) это «буквальное значение», то есть то значение, которое вы набрали прямо в коде. Например присвоение «int a = b;» это присвоение по имени, а «int a = 123;» это literal assignment, присвоение буквальное, «по литералу» 123.

Одно не понятно, как var становится массивом? Предположим создадим переменную «а», и как сказать, что это массив?

var a ???;


В JavaScript используется несколько способов:

var a = new Array;
var a = [];


Попробуем оба:

var newArray() {
	var R;
	R.type = varArr;
	R.size = 0;
	R.arr = new var [10];
	return R;
}


Пока, для того, чтобы сосредоточится на более существенных вещах, мы сделаем вид, что 10 элементов, это всё, что нам надо.

Теперь интересный момент, попробовать сделать нечто вроде:

var a = [];


Использовать [] в С++ нельзя, но можно использовать любой идентификатор, то есть имя. Например Array.

var a = Array;


Как это сделать? Для этого применим «синтаксический тип», вот так:

enum varSyntax { Array };


Везде где мы упомянем слово «Array», компилятор сообразит, что нужен тип «varSyntax». А ведь менно по типу компилятор выбирает, какую функцию, конструктор или оператор использовать.

struct var {
	...
	var (varSyntax initial) {
		if (initial == Array) {
			type = varArr;
			size = 0;
			arr = new var[10];
		}
	}
	...
}

var a = Array;


Конечно, где конструктор, там и присвоение, сразу вспомним мы, и напишем оператор присвоения по типу varSyntax.

void var::operator=(varSyntax initial) {
	...
}


В нижеследующем коде, сначала «a» инициализируется конструктором var(varSyntax), а затем «b» инициализируется пустым конструктором и присваевается оператором «var operator=(varSyntax)».

var a = Array, b;
b = Array;


Поскольку конструктор и присвоение через "=" всегда ходят парою, логично применить тот же трюк, и в конструкторе повторно использовать код из присвоения.

struct var {
	...
	var (varSyntax initial) {
		(*this) = initial;
	}
	operator= (var Syntax);
	...
};

void var::operator= (varSyntax initial) {
	if (initial == Array) {
		type = varArr;
		size = 0;
		arr = new var*[10];
	}
//	else if (initial == Object) {
//		...
//	}
}


Где-то, там-же, мы сможем создавать пустые объекты. Но это позже.

Ну что, пора попробовать:

int main() {
	var a = Array;
	a[0] = 100;
	log(a[0]);
}


error: conversion from 'int' to 'var' is ambiguous
	a[0] = 100.0;


Ого, ведь вот какая штука, мы объявили operator[] от var. Компилятор почему-то ожидает int. Если поменять var[0] на var[1] то всё скомпилируется. Что такое?

int main() {
	var a = Array;
	a[1] = 100;
	log(a[1]);
}


Так, с единичкой, компилируется…

Только этот код ничего пока не сделает, потому-что мы ещё не написали operator[].

Надо написать! Наверное как-то так:

var var::operator [](var key) {
	return arr[key];
}


error: no viable overloaded operator[] for type 'var *'
        return arr[i];
               ~~~^~


О, компилятор, что ещё не так?

Оказывается индексный доступ к указателю требует int, а как превратить var в int компилятор пока не знает.

Ну можно определить оператор int, есть и такое в C++! Но лучше, где можно не создавать нового оператора, его не создавать (долгая история), поэтому сделаем так:

struct var {
	...
	int toInt() {
		return num;
	}
	...
}

var var::operator[] (var i) {
	return arr[i.toInt()];
}


Компилируется, но ничего не выводит после запуска, в чём же дело?

А как, вообще, оно может работать? Как можно и читать и писать содержимое элемента через один и тот же оператор?

Ведь должны работать обе строчки:

a[1] = 100;
log(a[1]);


В одной запись, в другой чтение. Оказывается, operator= должен возвращать ссылку на элемент. Обратите внимание на символ &, в нём в данном случае дело:

var& var::operator[] (var i) {
	return arr[i.toInt()];
}


Но, хотя, «a[1]» заработало, «a[0]» продолжает ругаться. Почему же всё-таки?

Дело в том, что 0 может считаться и числом и указателем, а у нас var имеет два конструктора, один для числа (double), другой для указателя (char*). Из за этого вроде бы совершенно нормальный код, при использовании 0 в качестве литерала вдруг выдаёт ошибки компиляции. Это одна из особо изощрённых пыток С++ и серии ambiguous call.

Ну а вообще, компилятор в первую очередь считает ноль целым, то есть int.

К счастью, достаточно научить наш var инициализироваться из int. Как обычно сразу пишем конструктор и operator=.

var::var (int initial) {
	(*this) = (double) initial;
}

void var::operator = (int initial) {
	(*this) = (double) initial;
}


Тут, чтобы повторно использовать код, просто перенаправляются оба вызова в operator=(double).

Итак, что получилось на данный момент:

#include <stdio.h>

enum varType { varNull, varNum, varStr, varArr };
enum varSyntax { Array };

struct var {
	varType type;
	char *str;
	double num;
	var ();
	var (double initial); 
	var (int initial); 
	var (char *initial);
	void operator = (double initial);
	void operator = (int initial);
	void operator = (char *initial);

	var *arr;
	int size;
	var &operator [](var i);
	var (varSyntax initial) {
		(*this) = initial;
	}
	void operator= (varSyntax initial);
	void operator= (var src) {
		type = src.type;
		num = src.num;
		str = src.str;
		arr = src.arr;
	}
	int toInt() {
		return num;
	}
};

var::var() {
	type = varNull;	
}
var::var (double initial) {
	(*this) = initial;
}
var::var (int initial) {
	(*this) = (double)initial;
}
var::var (char *initial) {
	(*this) = initial;
}

void var::operator = (double initial) {
	type = varNum;
	num = initial;
}

void var::operator = (int initial) {
	(*this) = (double) initial;
}

void var::operator = (char *initial) {
	type = varStr;
	str = initial;
}

void log(var x) {
	if (x.type == varNum) printf("%f\n", x.num);
	if (x.type == varStr) printf("%s\n", x.str);
}

void var::operator= (varSyntax initial) {
	if (initial == Array) {
		type = varArr;
		size = 0;
		arr = new var[10];
	}
}

var &var::operator[] (var i) {
	return arr[i.toInt()];
}

int main() {
	var x = 100, s = "hello";
	var a = Array;
	a[0] = 200;
	log(a[0]);
	log(x);
	log(s);
}


Кстати, а что если мы захотим вывести массив на экран?

void log(var x) {
	if (x.type == varNum) printf("%f\n", x.num);
	if (x.type == varStr) printf("%s\n", x.str);
	if (x.type == varArr) printf("[Array]\n");
}


Пока только так.

Но хочется же большего.

Во-первых надо сделать самонастраивающуюся длину массива:

var &var::operator[] (var i) {
	int pos = i.toInt();
	if (pos >= size) size = pos+1;
	return arr[pos];
}


И надо сделать push() — добавление одного элемента в конец:

var var::push(var item) {
	if (type != varArr) {
		var nil;
		return nil;
	}
	(*this)[size] = item;
	size++;
	return item;
}


Поскольку мы работаем с указателем, тут не лишне проверить тип. В процессе подготовки этой статьи, как раз на этом программа падала. Ну размер мы пока не проверяем, заняты глобальным проектированием, но мы ещё вернёмся к этому вопросу.

Теперь можно переписать функцию log(), чтобы она выводила массив целиком:

void log(var x) {
	if (x.type == varNum) printf("%f ", x.num);
	if (x.type == varStr) printf("%s ", x.str);
	if (x.type == varArr) {
		printf("[");
		for (int i = 0; i < x.size; i++) log(x[i]);
		printf("]");
	}
}


Какой минимум работы понадобился, что рекурсия животворящая делает!

int main() {
	var a = Array;
	a[0]=100;
	a.push(200);
	log(a[0]);
	log(a[1]);
	log(a);
}


Вывод данных после запуска:

100.000000 200.000000 [100.000000 200.000000]


Ну вот, замечательно, какие-то основы полиморфизма у нас есть.

Можно даже уже помещать массив в массиве, причём вперемешку со строками и числами.

int main() {
	var a = Array;
	a.push(100);
	a.push("foo");
	a[2] = Array;
	a[2][0] = 200;
	a[2][1] = "bar";
	log(a);
}


[100.000000 foo [200.000000 bar ]]


Интересно, что будет если мы попробуем написать так:

var a = Array;
var b = a.push(Array);
b.push(200);
b.push("foo");
log(a);


А вот что:

[[]]


Почему же так получилось?

Проверим таким простым способом:

printf("%\n", a.arr[0].size);
printf("%\n", b.size);


По-логике, мы должны увидеть одно и то же число: 2.

Но на самом деле a.arr[0].size == 0!

Всё дело в том, что a[0] и b это две РАЗНЫЕ переменные, два разных экземпляра. В момент, когда произошло присвоение внутри функции a.push() через return, их поля совпали, то есть size, arr были идентичными, но после b.push() произошло увеличение b.size, и не произошло увеличение a[0].size.

Это мозголомная проблема, которую даже трудно описать словами, и возможно читатель совсем запутался пока читал последние строки, называется «передача по ссылке» (pass by reference).

В С++, обычно, передачей по ссылке называется когда перед аргументом стоит &, но это частный случай. Вообще, это значит, что изменение копии изменяет оригинал.

Посмотрим, как решать такую задачу. Сначала, всё что было связано с массивом, вынесем в отдельный класс, так исторически сложилось, что я его назвал lst. Особо не вдавайтесь в его устройство, так, схватите общую суть:

class lst {
	typedef var** P;
	P p;
	int capacity, size;
	void zeroInit();
	
public:
	lst();
	~lst();
	int length();
	void resize(int newsize);
	var pop();
	void push(const var &a);
	var& operator [](int i);
	void delIns(int pos, int delCount, var *item, int insCount);
};


Поясню, что это маленький класс для хранения списка указателей с возможностью динамически изменять размер, и дополнительными коммандами push/pop/delIns.

Это всё что нам понадобится, для того, чтобы наши массивы близко соответствовали JavaScript Array.

Теперь забудем как был устроен «var» раньше, и попробуем вписать «lst» в него правильно:

struct Ref {
	int uses;
	void *data;
	Ref () {
		uses = 1;
	}
};

struct var {
	varType type;
	union {
		double num;
		Ref* ref;
	};
...
};


Во-первых, мы совместили num и ref, потому-что всё равно одновременно нам эти свойства не нужны. Память экономим.

Во-вторых, вместо прямого значения всего, что связано с массивом, у нас будет ссылка со счётчиком внутри. Это называется подсчёт ссылок или reference counting.

В такой-же ссылке будем потом хранить Object.

Заметим, что счётчик сразу устанавливается в 1.

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

В первом делается «ref=src.ref, ref->uses++», обычно он называется copy, link, attach, или, собственно, reference.

void var::copy(const var &a) {
	// к этому месту экземпляр должен быть пуст.
	type = a.type;
	if (type == varNum || type == varBool) num = a.num;
	else {
		if (a.type == varNull) { return; }
		ref = a.ref;
		if (ref) ref->uses++;
	}
}


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

Обычно он называется unlink, unreference, detach. Я привык его называть unref().

void var::unref() {
	if (type == varNum || type == varNull || type == varBool) return;
	else if (type == varStr) {
		ref->uses--;
		if (ref->uses == 0) {
			delete (chr*)ref->data, delete ref;
		}
	}
	else if (type == varArr) {
		ref->uses--;
		if (ref->uses == 0) {
			deleteLst();
		}
	}
	else if (type == varObj) {
		ref->uses--;
		if (ref->uses == 0) {
			deleteObj();
		}
	}
	type = varNull;
	ref = 0;
}


data в структуре Ref имеет тип void*, то есть просто указатель, и будет хранить ссылку на собственно экземпляр массива(lst) или объекта(obj). При словe объект, речь о том объекте, в котором мы будет хранить пары ключ/значение в соответствии с JavaScript [Object object].

В сущности подсчёт ссылок, это разновидность сборщика мусора.

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

И, как видите, он не так уж прост, мозг сломать можно на раз.

Просто, чтобы читатель не запутался, повторю всё сначала:

Делаем класс var и в нём инкапуслируем либо double, либо lst (для массива), либо chr(для строк), либо keyval(для объектов).

Вот наш класс для работы со строками:

struct chr {
	int size;
	wchar_t *s;
	chr ();
	~chr();
	void set(double i);
	void set(wchar_t *a, int length = -1);
	void setUtf(char *a, int length = -1);
	void setAscii(char *a, int length = -1);
	char * getAscii();
	char * getUtf();

	wchar_t operator [](int i);

	double toNumber ();
	int intToStr(int i, char *s);
	void dblToStr (double d, char *s);

	int cmp (const chr &other);
	int find (int start, wchar_t *c, int subsize);
	chr substr(int pos, int count = -1);
	int _strcount(const chr &substring);
	void _cpto(int from, const chr &dest, int to, int count);
	chr clone();
	void replace(chr &A, chr &B, chr &dest);
};


И вот класс для объектов:

struct keyval {
	var keys, vals;
	keyval ();
	void set(var key, var val);
	var &get(var key);
};


Тут уже полная рекурсия и полиморфизм, смотрите, keyval использует массивы в виде var. Чтобы самому стать частью var. И это работает!

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

Например:

void f(var t) {
	t += "world";
	log(t);
}

var s = "hello";
f(s);
log(s);


Вывод:

world
world


При передаче s в f() вместо копирвания всех символов строки, только копируется один указатель и увеличивается один счётчик.

Но после изменения строки t так же изменится и строка s. Что нам надо в случае массивов, но не надо в случае строк! Это называется передача по ссылке, pass-by-reference.

Когда нам надо, чтобы переменная переданая через подсчёт ссылок была изменена отдельно от своего исходника, мы должны перед каждым изменением вызывать функцию detach/unref/unlink.

Так работают строки в Delphi, например. Это называется термином copy-on-write.

Считается, что это плохое решение. Но как отказаться от copy-on-write, но сохранить воможность pass-by-reference и copy-pointer-and-increment (подсчёт ссылок)?

Ответ стал стандартом современного программирования: а не надо изменять переменную, сделайте её неизменной! Это называется immutability — неизменяемость.

Согласно принципу неизменяемости строки в JavaScript устанавливаются только один раз, и после этого их изменять нельзя. Все функции работы со строками которые что-то изменяют, вызвращают новые строки. Это сильно облегчает нелёгкий труд по тщательной расстановке всех copy/unref, проверок указателей и прочей работе с памятью.

Тут, внезапно, я вынужден прерваться, ведь статья превысила комфортные для читателя 20К символов. А ведь ещё надо перегрузить около 20 операторов! Даже operator, (запятая). Совместить объекты и массивы, написать JSON.parse, реализовать сравнения строк и булевых значений, написать конструктор для Boolean, придумать и реализовать нотацию для инициализации значений массивов и объектов, решить проблему многоаргументного log(...), придумать что делать с undefined, typeof, правильно реализовать replace/slice и т.д. И всё это без единого шаблона, только перегрузка операторов и функции.

Так что, если вам будет интересно, то скоро продолжим.

Для самых любопытных, ссылка на репозиторий библиотеки:

github.com/exebook/jslike
Tags:
Hubs:
+7
Comments 31
Comments Comments 31

Articles