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();
    }
```

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";
}