heterogeneous lists in C++

[Willi]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.

Any suggestions?!

Willi

 

[Victor Bazarov]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.

Any suggestions?!

http://lmgtfy.com/?q=heterogeneous+list+c++

V

 

[Stefan Ram]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.
Any suggestions?!

A list of void*? Or, defining a common base class T for all
other types and then T*?

The traditional way in LISP (IBM-704-style implementation?)
is, IIRC, to have some bits in the pointer or value reserved
for type information, e.g., for to tell atoms from lists.

When implementing Lisp, you usually need to implement a GC,
that is, a memory management system, anyways.

 

[Nobody]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.

In Lisp, a "list" is either a cons cell or nil. A cons cell is a pair of
pointers to arbitrary Lisp values.

As such, a "list" is closer to a binary tree than to a list; but it's not
necessarily a tree, as there's no prohibition on cyclic references.

 

[Jeff Flinn]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.

Any suggestions?!

For the loosest definition of list, at compile time there's:

- a struct xxx { int, char, [boost|std]::array<int, 3> };

- [boost|std]::tuple<int, char, [boost|std]::array<int, 3> >

If you mean a container with stl list-like semantics:

- boost::fusion::list<int, char, [boost|std]::array<int, 3> >

Jeff

 

[Öö Tiib]

I have a problem, how to represent heterogeneous lists in C++. as
they exist in Lisp where you can have '(1 a (1 2 3)) for instance.
I'm implementing a Lisp compiler in C++ and this has me stuck. Short
of implementing a memory management system from scratch, I have no
idea how to go about doing this.

There are not so lot of types that can be list elements so you can
easily use something like
'std::vector<boost::variant<list of the types>>'

Make sure that you read a bit about boost::variant<> and the
problems with it. It is not entirely fool-proof that's why we do not
have 'std::variant'.

 

[Stefan Ram]

There are not so lot of types that can be list elements so you can
easily use something like
'std::vector<boost::variant<list of the types>>'

Why not

struct variant { ...
struct type0 public : variant { ...
struct type1 public : variant { ...
struct type2 public : variant { ...
....

::std::vector<variant>
....

?

 

[Öö Tiib]

Why not

struct variant { ...
struct type0 public : variant { ...
struct type1 public : variant { ...
struct type2 public : variant { ...
...

::std::vector<variant>
...

?

Because boost::variant<> is quite efficient, well tested and its issues
are known and avoidable. There are support classes to it like
'static_visitor' etc.

I would write 'variant' of my own when boost usage was out of question
for some reason. Since it is lisp compiler and so will be ran either
on desktop or on mainframe it is hard to imagine such reason.

My own 'variant' would become quite similar to 'boost::variant' I
suspect.