Immutable interpreter in C++

Question

I am writing an immutable interpreter in C++ for fun. Originally standard vectors and dequeues were used to create a double ended queue data type, but it was very slow, because each operation require a whole new copy of the original container to be created.

So it was redone using a custom immutable single linked node lists which only requires a single node to be recreated during each operation on list like data types. And a double ended queue was implemented using two of these single linked lists.

While it doesn't require the whole data type and each element to be copied during each operation. It does require a limited recreation of the data type during dequeue operations to rebalance the two lists, which is expensive.

Is there a more efficient, and less copy expensive method, that could have been used to implement the double ended queue? Which does not require rebalancing the lists, and the original data still remains immutable during each operation.

(Per comments below is the minimum code needed to get it to compile.)

int main() {
 let l = list();
 for (int i = 5; i <= 10; ++i) {
 l = l.place_last(number(i));
 }
 l = l.place_lead(l);
 for (int i = 4; i >= 0; --i) {
 l = l.place_lead(number(i));
 }
 l = l.reverse();
 print("list l = " + str(l));
 while (l.is()) {
 print("lead element of l = " + str(l.lead()));
 l = l.shift_lead();
 print("l lead shifted = " + str(l));
 }
 return 0;
}

class list {
 let _lead;
 let _last;
 int_t _size;
 public:
 list();
 list(const list& exp);
 list(let exp);
 virtual ~list();
 friend str_t __type__(const list& self);
 friend bool_t __is__(const list& self);
 friend real_t __comp__(const list& self, const let& other);
 friend void __str__(stream_t& out, const list& self);
 friend void __repr__(stream_t& out, const list& self);
 friend int_t __len__(const list& self);
 friend let __lead__(const list& self);
 friend let __last__(const list& self);
 friend let __place_lead__(const list& self, const let& other);
 friend let __shift_lead__(const list& self);
 friend let __place_last__(const list& self, const let& other);
 friend let __shift_last__(const list& self);
 friend let __reverse__(const list& self);
 private:
 void balance();
 };
 list::list() : _lead(__node__()), _last(__node__()), _size(0) {
 }
 list::list(const list& exp) : _lead(exp._lead), _last(exp._last), _size(exp._size) {
 }
 list::list(let exp) : _lead(__node__()), _last(__node__()), _size(0) {
 _lead = _lead.place_lead(exp);
 }
 list::~list() {
 }
 std::string __type__(const list& self) {
 return "list";
 }
 bool_t __is__(const list& self) {
 if (self._lead.is() || self._last.is()) {
 return true;
 }
 return false;
 }
 real_t __comp__(const list& self, const let& other) {
 const list* e = other.cast<list>();
 if (e) {
 if ((self._lead == e->_lead) && (self._last == e->_last)) {
 return 0.0;
 }
 }
 return NOT_A_NUMBER;
 }
 void __str__(stream_t& out, const list& self) {
 if (!__is__(self)) {
 out << "[]";
 return;
 }
 out << "[";
 out << str(self._lead);
 if (self._last.is()) {
 if (self._lead.is()) {
 out << " ";
 }
 out << str(self._last.reverse());
 }
 out << "]";
 }
 void __repr__(stream_t& out, const list& self) {
 if (!__is__(self)) {
 out << "[]";
 return;
 }
 out << "[";
 out << repr(self._lead);
 if (self._last.is()) {
 if (self._lead.is()) {
 out << " ";
 }
 out << repr(self._last.reverse());
 }
 out << "]";
 }
 int_t __len__(const list& self) {
 return self._size;
 }
 let __lead__(const list& self) {
 if (!self._lead.is()) {
 return self._last.lead();
 }
 return self._lead.lead();
 }
 let __last__(const list& self) {
 if (!self._last.is()) {
 return self._lead.lead();
 }
 return self._last.lead();
 }
 let __place_lead__(const list& self, const let& other) {
 if (other.is_nothing()) {
 return self;
 }
 list e = self;
 e._lead = e._lead.place_lead(other);
 e._size += 1;
 if (!e._last.is()) {
 e.balance();
 }
 return e;
 }
 let __shift_lead__(const list& self) {
 if (__len__(self) == 0) {
 return self;
 }
 list e = self;
 if (!e._lead.is()) {
 if (e._last.shift_lead().is()) {
 // Balance if _last has more than one element.
 e.balance();
 }
 else {
 e._last = e._last.shift_lead();
 return e;
 }
 }
 e._lead = e._lead.shift_lead();
 if (!e._lead.is()) {
 if (e._last.shift_lead().is()) {
 e.balance();
 }
 }
 return e;
 }
 let __place_last__(const list& self, const let& other) {
 if (other.is_nothing()) {
 return self;
 }
 list e = self;
 e._last = e._last.place_lead(other);
 e._size += 1;
 if (!e._lead.is()) {
 e.balance();
 }
 return e;
 }
 let __shift_last__(const list& self) {
 if (__len__(self) == 0) {
 return self;
 }
 list e = self;
 if (!e._last.is()) {
 if (e._lead.shift_lead().is()) {
 // Balance if _last has more than one element.
 e.balance();
 }
 else {
 e._lead = e._lead.shift_lead();
 return e;
 }
 }
 e._last = e._last.shift_lead();
 if (!e._last.is()) {
 if (e._lead.shift_lead().is()) {
 e.balance();
 }
 }
 return e;
 }
 let __reverse__(const list& self) {
 if (__len__(self) < 2) {
 return self;
 }
 list e;
 e._lead = self._last;
 e._last = self._lead;
 e._size = self._size;
 return e;
 }
 void list::balance() {
 // print("lead = " + str(_lead) + " : last = " + str(_last));
 bool_t flip = _last.is() && !_lead.is();
 if (flip) {
 std::swap(_lead, _last);
 }
 int_t i = _size < 2 ? 1 : _size / 2;
 _lead = _lead.reverse();
 _last = _last.reverse();
 while (i-- > 0) {
 _last = _last.place_lead(_lead.lead());
 _lead = _lead.shift_lead();
 }
 _lead = _lead.reverse();
 _last = _last.reverse();
 if (flip) {
 std::swap(_lead, _last);
 }
 // print("lead = " + str(_lead) + " : last = " + str(_last));
 }

class number {
 typedef std::complex<real_t> num_t;
 public:
 number();
 number(const number& obj);
 number(const int_t& value);
 virtual ~number();
 friend str_t __type__(const number& self);
 friend bool_t __is__(const number& self);
 friend real_t __comp__(const number& self, const let& other);
 friend void __str__(stream_t& out, const number& self);
 friend void __repr__(stream_t& out, const number& self);
 private:
 num_t _value;
 };
 number::number() : _value(0.0, 0.0) {
 }
 number::number(const number& obj) : _value(obj._value) {
 }
 number::number(const int_t& value) : _value(value, 0.0) {
 }
 number::~number() {
 }
 str_t __type__(const number& self) {
 return "number";
 }
 bool_t __is__(const number& self) {
 if (__nan__(self)) {
 return false;
 }
 return (self._value.real() || self._value.imag() ? true : false);
 }
 real_t __comp__(const number& self, const let& other) {
 const number* n = other.cast<number>();
 if (n) {
 if (__nan__(self) || __nan__(*n) || __complex__(self) || __complex__(*n)) {
 return NOT_A_NUMBER;
 }
 real_t x = self._value.real();
 real_t y = n->_value.real();
 if (x > y) {
 return 1.0;
 }
 if (x < y) {
 return -1.0;
 }
 return 0.0;
 }
 return NOT_A_NUMBER;
 }
 void __str__(stream_t& out, const number& self) {
 real_t real = self._value.real();
 real_t imag = self._value.imag();
 if (imag && !real) {
 out << imag << "j";
 return;
 }
 if (!imag && real) {
 out << real;
 return;
 }
 if (!real && !imag) {
 out << 0.0;
 return;
 }
 out << "(" << real << ",";
 out.setf(std::ios::showpos);
 out << imag << "j)";
 out.unsetf(std::ios::showpos);
 }
 void __repr__(stream_t& out, const number& self) {
 out << "\'";
 __str__(out, self);
 out << "\'";
 }

The let class and support classes / functions.

#if _WIN32 || _WIN64
#if _WIN64
 using int_t = long int;
#else
 using int_t = int;
#endif
#endif
#if __GNUC__
#if __x86_64__ || __ppc64__
 using int_t = long int;
#else
 using int_t = int;
#endif
#endif
 typedef bool bool_t;
 typedef long double real_t;
 typedef std::string str_t;
 typedef std::stringstream stream_t;
 static const real_t NOT_A_NUMBER = std::numeric_limits<real_t>::quiet_NaN();
 static const std::hash<str_t> DEFAULT_HASH_FUNCTION;
 /********************************************************************************************/
 //
 // 'let' Class Definition
 //
 // The 'let' class represents an immutable object wrapper. It will accept 
 // any object assigned to by the assignment operator '='.
 // Example: let a = 42;
 //
 // The fundamental structure of the 'let' data type was inspired and extended 
 // from a presentation entitled:
 // Title: Value Semantics and Concept-based Polymorphism
 // By - Sean Parent
 // (http://sean-parent.stlab.cc/papers-and-presentations)
 //
 /********************************************************************************************/
 class let {
 public:
 let();
 template <typename T> let(T x);
 template <typename T> let(T* x);
 template <typename T> const T* cast() const; // Cast the object as an instance of the specified type.
 str_t id() const; // Return the typeid of the object.
 bool_t is_type(const let& other) const; // Compair two objects by typeid. 
 std::size_t hash() const; // Get the hash of an object.
 str_t type() const; // The class generated type name.
 bool_t is() const; // Is or is not the object defined.
 void str(stream_t& out) const; // String representation of the object.
 void repr(stream_t& out) const;
 real_t comp(const let& other) const; // Compare two objects. 0 = equality, > 0 = grater than, < 0 = less than.
 bool_t eq(const let& other) const; // Equal to.
 bool_t ne(const let& other) const; // Not equal to.
 bool_t ge(const let& other) const; // Greater than equal to.
 bool_t le(const let& other) const; // Less than equal to.
 bool_t gt(const let& other) const; // Greater than.
 bool_t lt(const let& other) const; // Less than.
 int_t len() const; // Length of an object.
 let lead() const; // Lead element of an object.
 let last() const; // Last element of an object.
 let place_lead(const let& other) const; // Place an object as the lead element.
 let shift_lead() const; // Remove the lead element from an object.
 let place_last(const let& other) const; // Place an object as the last element.
 let shift_last() const; // Remove the last element from an object.
 let reverse() const; // Reverse the order of an object's elements.
 bool_t is_nothing() const;
 bool_t nan() const;
 bool_t complex() const;
 // General object operator overloads. 
 bool_t operator==(const let& other) const;
 bool_t operator!=(const let& other) const;
 bool_t operator>=(const let& other) const;
 bool_t operator> (const let& other) const;
 bool_t operator<=(const let& other) const;
 bool_t operator< (const let& other) const;
 private:
 struct interface_t {
 /********************************************************************************************/
 //
 // 'interface_t' Class Definition
 //
 // A simple interface description allowing redirection of the 'let' data type.
 //
 /********************************************************************************************/
 virtual ~interface_t() = default;
 virtual operator bool() const = 0;
 virtual void* __as() = 0;
 virtual str_t __id() const = 0;
 virtual std::size_t __hash() const = 0;
 virtual str_t __type() const = 0;
 virtual bool_t __is() const = 0;
 virtual void __str(stream_t& out) const = 0;
 virtual void __repr(stream_t& out) const = 0;
 virtual real_t __comp(const let& other) const = 0;
 virtual int_t __len() const = 0;
 virtual let __lead() const = 0;
 virtual let __last() const = 0;
 virtual let __place_lead(const let& other) const = 0;
 virtual let __shift_lead() const = 0;
 virtual let __place_last(const let& other) const = 0;
 virtual let __shift_last() const = 0;
 virtual let __reverse() const = 0;
 virtual bool_t __is_nothing() const = 0;
 virtual bool_t __nan() const = 0;
 virtual bool_t __complex() const = 0;
 };
 template <typename T>
 struct data_t : interface_t {
 /******************************************************************************************/
 //
 // 'data_t' Class Definition
 //
 // The int_terface implementation of the 'interface_t' data type. 
 // Defining a shared const point_ter of the data type passed to it.
 //
 /******************************************************************************************/
 data_t(T val);
 operator bool() const;
 void* __as();
 str_t __id() const;
 std::size_t __hash() const;
 str_t __type() const;
 bool_t __is() const;
 void __str(stream_t& out) const;
 void __repr(stream_t& out) const;
 real_t __comp(const let& other) const;
 int_t __len() const;
 let __lead() const;
 let __last() const;
 let __place_lead(const let& other) const;
 let __shift_lead() const;
 let __place_last(const let& other) const;
 let __shift_last() const;
 let __reverse() const;
 bool_t __is_nothing() const;
 bool_t __nan() const;
 bool_t __complex() const;
 T _data;
 };
 std::shared_ptr<const interface_t> _self;
 };
 /********************************************************************************************/
 //
 // 'nothing' Class Definition
 //
 // A basic class definition of the value of nothing. This is used within
 // 'let' class implementation to return a result of nothing for results
 // which have either conflicting types, or in some cases as the default to
 // return unless overridden.
 //
 // This class also demonstrates the basic function methods that should be
 // over written for proper object behavior. 
 //
 /********************************************************************************************/
 class nothing {
 public:
 nothing();
 nothing(const nothing& obj);
 virtual ~nothing();
 friend str_t __type__(const nothing& self);
 friend bool_t __is__(const nothing& self);
 friend real_t __comp__(const nothing& self, const let& other);
 friend void __str__(stream_t& out, const nothing& self);
 friend void __repr__(stream_t& out, const nothing& self);
 friend bool_t __is_nothing__(const nothing& self);
 };
 /********************************************************************************************/
 //
 // '__node__' Class Definition
 //
 // The __node__ class is implimented using Lisp inspired data nodes. It
 // is used to define the data lists as in Lisp. 
 //
 /********************************************************************************************/
 class __node__ {
 let _data;
 let _next;
 public:
 __node__();
 __node__(const __node__& exp);
 __node__(let obj);
 virtual ~__node__();
 friend str_t __type__(const __node__& self);
 friend bool_t __is__(const __node__& self);
 friend real_t __comp__(const __node__& self, const let& other);
 friend void __str__(stream_t& out, const __node__& self);
 friend void __repr__(stream_t& out, const __node__& self);
 friend int_t __len__(const __node__& self);
 friend let __lead__(const __node__& self);
 friend let __last__(const __node__& self);
 friend let __place_lead__(const __node__& self, const let& other);
 friend let __shift_lead__(const __node__& self);
 friend let __reverse__(const __node__& self);
 };
 /********************************************************************************************/
 //
 // Basic Primitive Declarations
 //
 // These definitions add a few useful and some necessary support functions.
 //
 /********************************************************************************************/
 inline void print(); // Simply print a new line.
 inline void print(const str_t& str); // Accept any single string and print it with a std::endl.
 inline void print(const let& a); // Accept any single 'let' and print it with a std::endl.
 str_t str(const let& a); // Convert any 'let' to a str_t.
 
 /********************************************************************************************/
 //
 // 'let' Class Function Default Template API.
 //
 // The following function templates define the over-ridable functions which
 // may be used to tailor the behavior of any object held within a 'let'.
 //
 // Each function defined here defines the default behavior of each function
 // which is invoked if a function is not overwritten for a defined class.
 //
 /********************************************************************************************/
 template<typename T> /**** Hash Value ****/
 std::size_t __hash__(const T& self);
 template<typename T>
 std::size_t __hash__(const T& self) {
 return DEFAULT_HASH_FUNCTION(repr(self));
 }
 template<typename T> /**** Type Name ****/
 str_t __type__(const T& self);
 template<typename T>
 str_t __type__(const T& self) {
 return typeid(self).name();
 }
 template<typename T> /**** Boolean Conversion ****/
 bool_t __is__(const T& self);
 template<typename T>
 bool_t __is__(const T& self) {
 return false;
 }
 template<typename T> /**** String Conversion ****/
 void __str__(stream_t& out, const T& self);
 template<typename T>
 void __str__(stream_t& out, const T& self) {
 out << "object<" << &self << "," << __type__(self) << ">";
 }
 template<typename T> /**** String Representation ****/
 void __repr__(stream_t& out, const T& self);
 template<typename T>
 void __repr__(stream_t& out, const T& self) {
 out << str(nothing());
 }
 template<typename T> /**** Comparison Between Variables ****/
 real_t __comp__(const T& self, const let& other);
 template<typename T>
 real_t __comp__(const T& self, const let& other) {
 return NOT_A_NUMBER;
 }
 template<typename T> /**** Length Of ****/
 int_t __len__(const T& self);
 template<typename T>
 int_t __len__(const T& self) {
 return 0;
 }
 template<typename T> /**** Lead Element Of ****/
 let __lead__(const T& self);
 template<typename T>
 let __lead__(const T& self) {
 return nothing();
 }
 template<typename T> /**** Last Element Of ****/
 let __last__(const T& self);
 template<typename T>
 let __last__(const T& self) {
 return nothing();
 }
 template<typename T> /**** Perpend Lead Element Of ****/
 let __place_lead__(const T& self, const let& other);
 template<typename T>
 let __place_lead__(const T& self, const let& other) {
 return nothing();
 }
 template<typename T> /**** Left Shift Remove ****/
 let __shift_lead__(const T& self);
 template<typename T>
 let __shift_lead__(const T& self) {
 return nothing();
 }
 template<typename T> /**** Postpend Last Element Of ****/
 let __place_last__(const T& self, const let& other);
 template<typename T>
 let __place_last__(const T& self, const let& other) {
 return nothing();
 }
 template<typename T> /**** Right Shift Remove ****/
 let __shift_last__(const T& self);
 template<typename T>
 let __shift_last__(const T& self) {
 return nothing();
 }
 template<typename T> /**** Reverse The Elements Of ****/
 let __reverse__(const T& self);
 template<typename T>
 let __reverse__(const T& self) {
 return nothing();
 }
 template<typename T> /**** Is Nothing Type ****/
 bool_t __is_nothing__(const T& self);
 template<typename T>
 bool_t __is_nothing__(const T& self) {
 return false;
 }
 template<typename T> /**** Is Not A Number ****/
 bool_t __nan__(const T& self);
 template<typename T>
 bool_t __nan__(const T& self) {
 return false;
 }
 template<typename T> /**** Is A Complex Number ****/
 bool_t __complex__(const T& self);
 template<typename T>
 bool_t __complex__(const T& self) {
 return false;
 }
 /********************************************************************************************/
 //
 // 'nothing' Class Implimentation
 //
 /********************************************************************************************/
 nothing::nothing() {
 }
 nothing::nothing(const nothing& obj) {
 }
 nothing::~nothing() {
 }
 str_t __type__(const nothing& self) {
 return "nothing";
 }
 bool_t __is__(const nothing& self) {
 return false;
 }
 real_t __comp__(const nothing& self, const let& other) {
 return other.is_nothing() ? 0.0 : NOT_A_NUMBER;
 }
 void __str__(stream_t& out, const nothing& self) {
 out << "nothing";
 }
 void __repr__(stream_t& out, const nothing& self) {
 __str__(out, self);
 }
 bool_t __is_nothing__(const nothing& self) {
 return true;
 }
 /********************************************************************************************/
 //
 // '__node__' Class Implimentation
 //
 /********************************************************************************************/
 __node__::__node__() : _data(), _next() {
 }
 __node__::__node__(const __node__& exp) : _data(exp._data), _next(exp._next) {
 }
 __node__::__node__(let object) : _data(object), _next() {
 }
 __node__::~__node__() {
 }
 std::string __type__(const __node__& self) {
 return "__node__";
 }
 bool_t __is__(const __node__& self) {
 if (self._data.is_nothing()) {
 return false;
 }
 return true;
 }
 real_t __comp__(const __node__& self, const let& other) {
 const __node__* p = other.cast<__node__>();
 if (p) {
 let a = self;
 let b = *p;
 while (a.is() && b.is()) {
 if (a.lead() != b.lead()) {
 return NOT_A_NUMBER;
 }
 a = a.shift_lead();
 b = b.shift_lead();
 }
 if (!a.is() && !b.is()) {
 return 0.0;
 }
 }
 return NOT_A_NUMBER;
 }
 void __str__(stream_t& out, const __node__& self) {
 if (!__is__(self)) {
 return;
 }
 let e = self;
 bool_t next = false;
 do {
 out << str(e.lead());
 e = e.shift_lead();
 next = e.is();
 if (next) {
 out << " ";
 }
 } while (next);
 }
 void __repr__(stream_t& out, const __node__& self) {
 if (!__is__(self)) {
 return;
 }
 let e = self;
 bool_t next = false;
 do {
 out << repr(e.lead());
 e = e.shift_lead();
 next = e.is();
 if (next) {
 out << " ";
 }
 } while (next);
 }
 int_t __len__(const __node__& self) {
 if (!__is__(self)) {
 return 0;
 }
 int_t size = 1;
 let next = self._next;
 while (next.is()) {
 size += 1;
 next = next.shift_lead();
 }
 return size;
 }
 let __lead__(const __node__& self) {
 return self._data;
 }
 let __last__(const __node__& self) {
 if (self._next.is_nothing()) {
 return self;
 }
 let next = self;
 while (next.shift_lead().is()) {
 next = next.shift_lead();
 }
 return next;
 }
 let __place_lead__(const __node__& self, const let& other) {
 if (other.is_nothing()) {
 return self;
 }
 __node__ a(other);
 if (__is__(self)) {
 a._next = self;
 }
 return a;
 }
 let __shift_lead__(const __node__& self) {
 if (self._next.is_nothing()) {
 return __node__();
 }
 return self._next;
 }
 let __reverse__(const __node__& self) {
 if (self._next.is_nothing()) {
 return self;
 }
 let a = __node__();
 let next = self;
 while (next.is()) {
 a = a.place_lead(next.lead());
 next = next.shift_lead();
 }
 return a;
 }
 /********************************************************************************************/
 //
 // 'let' Class Implementation
 //
 /********************************************************************************************/
 let::let() : _self(std::make_shared<data_t<Olly::nothing>>(Olly::nothing())) {
 }
 template <typename T>
 let::let(T x) : _self(std::make_shared<data_t<T>>(std::move(x))) {
 }
 template <typename T>
 let::let(T* x) : _self(std::make_shared<data_t<T>>(x)) {
 }
 template <typename T> const T* let::cast() const {
 const T* p = static_cast<T*>(const_cast<interface_t*>(_self.get())->__as());
 if (p) {
 return p;
 }
 return nullptr;
 }
 str_t let::id() const {
 return _self->__id();
 }
 bool_t let::is_type(const let& other) const {
 return _self->__id() == other._self->__id();
 }
 std::size_t let::hash() const {
 return _self->__hash();
 }
 str_t let::type() const {
 return _self->__type();
 }
 bool_t let::is() const {
 return const_cast<interface_t*>(_self.get())->__is();
 }
 void let::str(stream_t& out) const {
 _self->__str(out);
 }
 void let::repr(stream_t& out) const {
 _self->__repr(out);
 }
 real_t let::comp(const let& other) const {
 return _self->__comp(other);
 }
 bool_t let::eq(const let& other) const {
 return (comp(other) == 0 ? true : false);
 }
 bool_t let::ne(const let& other) const {
 return (comp(other) != 0 ? true : false);
 }
 bool_t let::ge(const let& other) const {
 return (comp(other) >= 0 ? true : false);
 }
 bool_t let::le(const let& other) const {
 return (comp(other) <= 0 ? true : false);
 }
 bool_t let::gt(const let& other) const {
 return (comp(other) > 0 ? true : false);
 }
 bool_t let::lt(const let& other) const {
 return (comp(other) < 0 ? true : false);
 }
 int_t let::len() const {
 return _self->__len();
 }
 let let::lead() const {
 return _self->__lead();
 }
 let let::last() const {
 return _self->__last();
 }
 let let::place_lead(const let& other) const {
 return _self->__place_lead(other);
 }
 let let::shift_lead() const {
 return _self->__shift_lead();
 }
 let let::place_last(const let& other) const {
 return _self->__place_last(other);
 }
 let let::shift_last() const {
 return _self->__shift_last();
 }
 let let::reverse() const {
 return _self->__reverse();
 }
 bool_t let::is_nothing() const {
 return _self->__is_nothing();
 }
 bool_t let::nan() const {
 return _self->__nan();
 }
 bool_t let::complex() const {
 return _self->__complex();
 }
 bool_t let::operator==(const let& other) const {
 return eq(other);
 }
 bool_t let::operator!=(const let& other) const {
 return ne(other);
 }
 bool_t let::operator>=(const let& other) const {
 return ge(other);
 }
 bool_t let::operator> (const let& other) const {
 return gt(other);
 }
 bool_t let::operator<=(const let& other) const {
 return le(other);
 }
 bool_t let::operator< (const let& other) const {
 return lt(other);
 }
 /********************************************************************************************/
 //
 // 'data_t' Class Implementation
 //
 /********************************************************************************************/
 template <typename T>
 let::data_t<T>::data_t(T val) : _data(std::move(val)) {
 }
 template <typename T>
 let::data_t<T>::operator bool() const {
 return __is();
 }
 template <typename T>
 void* let::data_t<T>::__as() {
 return &_data;
 }
 template <typename T>
 str_t let::data_t<T>::__id() const {
 return typeid(_data).name();
 }
 template <typename T>
 std::size_t let::data_t<T>::__hash() const {
 return __hash__(_data);
 }
 template <typename T>
 str_t let::data_t<T>::__type() const {
 return __type__(_data);
 }
 template <typename T>
 bool_t let::data_t<T>::__is() const {
 return __is__(_data);
 }
 template <typename T>
 void let::data_t<T>::__str(stream_t& out) const {
 __str__(out, _data);
 }
 template <typename T>
 void let::data_t<T>::__repr(stream_t& out) const {
 __repr__(out, _data);
 }
 template <typename T>
 real_t let::data_t<T>::__comp(const let& other) const {
 return __comp__(_data, other);
 }
 template <typename T>
 int_t let::data_t<T>::__len() const {
 return __len__(_data);
 }
 template <typename T>
 let let::data_t<T>::__lead() const {
 return __lead__(_data);
 }
 template <typename T>
 let let::data_t<T>::__last() const {
 return __last__(_data);
 }
 template <typename T>
 let let::data_t<T>::__place_lead(const let& other) const {
 return __place_lead__(_data, other);
 }
 template <typename T>
 let let::data_t<T>::__shift_lead() const {
 return __shift_lead__(_data);
 }
 template <typename T>
 let let::data_t<T>::__place_last(const let& other) const {
 return __place_last__(_data, other);
 }
 template <typename T>
 let let::data_t<T>::__shift_last() const {
 return __shift_last__(_data);
 }
 template <typename T>
 let let::data_t<T>::__reverse() const {
 return __reverse__(_data);
 }
 template <typename T>
 bool_t let::data_t<T>::__is_nothing() const {
 return __is_nothing__(_data);
 }
 template <typename T>
 bool_t let::data_t<T>::__nan() const {
 return __nan__(_data);
 }
 template <typename T>
 bool_t let::data_t<T>::__complex() const {
 return __complex__(_data);
 }
 /********************************************************************************************/
 //
 // Basic Primitive Implementations
 //
 /********************************************************************************************/
 void print() {
 std::cout << std::endl;
 }
 void print(const str_t& str) {
 std::cout << str << std::endl;
 }
 void print(const let& a) {
 print(str(a));
 }
 str_t str(const let& a) {
 /*
 Convert a 'let' to its string representation.
 */
 stream_t stream;
 stream << std::boolalpha;
 if (a.type() == "format") {
 /*
 The 'format' data type must be printed using
 its string representation, else it would only
 impart its formating to the stream instead of
 being printed to it.
 */
 a.repr(stream);
 }
 else {
 a.str(stream);
 }
 return stream.str();
 }
```

• Loki Astari: Double underscore in an identifier is a no no - What are the rules about using an underscore in a C++ identifier?
• StormCrow: Thank you for the heads up on the underscore rules! I was not aware of them. I used that pattern to identify visually what level of function overloading I am working on. Since I typically use a single underscore for private variables I choose two underscores to document the overloads. I will come up with another solution for that.

Answer 1

Try to write ideomatic C++

Your code doesn't really look like the typical C++ you will find in many other projects. For example, the name of every member function that is not a constructor or destructor is surrounded by double underscores. Apart from the issues with using underscores already mentioned by Martin York, this is very uncommon. It requires more typing and I am not sure the sheer quantity of underscores in your code is helping with readability.

Furthermore, you are creating typedefs for all the types you are using, but this is not really helping matters. Some issues for example are:

• bool_t is longer to type than bool
• int_t does not tell you what size the integer is, and apparently it can either be a long int or a regular int, but the sizes of those types are not guaranteed to be what you think either.
• In general, you are hiding the underlying type, and while that is sometimes a good thing, as someone who is not familiar with your code, now I'm constantly having to guess whether str_t is the same as a std::string, if stream_t is a std::stringstream or any other kind of stream, like std::ofstream for example.

I recommend you don't typedef anything. It doesn't require that much extra typing, especially not if you use more auto.

Another issue is terminology. It's very uncommon to see the terms "lead" and "last" used, normally it is "head" and "tail" for a list, and the STL uses "front" and "back" for the first and last element of a container.

Use of let

I'm not really sure I like the use of let. It hides the types and introduces a lot of overhead. For example:

let a = 42;

a contains a pointer to an instance of data_t<int>, and the latter inherits from a base class with virtual functions, so it also contains a pointer to a vtable. To do something simple as getting the value of a back, like in:

int value = *a.cast<int>();

The compiler will first dereference the pointer to data_t<int>, then dereference the pointer to the vtable, then look up the pointer to __as in that table, and then call through that pointer, just to get the address to the actual int value, which the caller then still has to dereference. All that for just an int! Apart from that, you lose type safety because the caller now has to know what the actual type was that was stored in the let object, but the compiler will not warn you if you would write a.cast<double>().

So, if you want an immutable int, why not just use const?

const int a = 42;

Making an immutable list using the STL

So you want to be able to create new lists without creating/copying the nodes. But behind the scenes you are using a std::shared_ptr anyway to ensure you can copy let objects. So what you can do instead, is use the standard library to create a list of shared pointers to const ints:

std::list<std::shared_ptr<const int>> my_list = {std::make_shared<int>(42)};
my_list.push_back(std::make_shared<int>(123));

The contents are immutable, for example the following will not compile:

*my_list.front() = 0;

I would use this as a basis to create an immutable list class, for example like so:

template<typename T>
class immutable_list {
 std::list<std::shared_ptr<const T>> data;
public:
 // Constructors
 immutable_list() = default;
 immutable_list(const T &value): data{std::make_shared<T>(value)} {}
 ...
 // Member functions returning modified lists
 immutable_list push_front(const T &value) {
 immutable_list result = *this;
 result.data.emplace_front(std::make_shared<T>(value));
 return result;
 }
 ...
 // Member functions accessing list contents
 std::size_t size() {
 return data.size();
 }
 const T &front() {
 return *data.front();
 }
 ...
};

And then you can use it like so:

auto foo = immutable_list(42);
foo = foo.push_front(123);
std::cout << foo.front() << "\n";

You probably should write wrappers for all the member functions of std::list, including for the iterators, so you can write something like this:

for (auto &value: foo) {
 std::cout << value << "\n";
}

• StormCrow: Thank you for the answer! A point I think needs to clarified. The class let is being used to invoke method overloading on the derived datatypes passed to let, using the interface to data_t to call the friend function of each data type held by the specific instance of let. Including that the list can hold a reference to itself as an element of data. l = [a b c], l.place_lead(l) then results in l = [[a b c] a b c]. That way the interpreter doesn't need to know what data type it is using the let class manages both that and memory management of the data type.