heterogeneous lists in C++

Discussion in 'C++' started by Willi, Mar 18, 2013.

  1. Willi

    Willi Guest

    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
     
    Willi, Mar 18, 2013
    #1
    1. Advertising

  2. On 3/18/2013 4:38 PM, Willi wrote:
    > 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
    --
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Mar 18, 2013
    #2
    1. Advertising

  3. Willi

    Stefan Ram Guest

    Willi <> writes:
    >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.
     
    Stefan Ram, Mar 18, 2013
    #3
  4. Willi

    Nobody Guest

    On Mon, 18 Mar 2013 13:38:10 -0700, Willi wrote:

    > 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.
     
    Nobody, Mar 18, 2013
    #4
  5. Willi

    Jeff Flinn Guest

    On 3/18/2013 4:38 PM, Willi wrote:
    > 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
     
    Jeff Flinn, Mar 19, 2013
    #5
  6. Willi

    Öö Tiib Guest

    On Monday, 18 March 2013 22:38:10 UTC+2, Willi wrote:
    > 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'.
     
    Öö Tiib, Mar 19, 2013
    #6
  7. Willi

    Stefan Ram Guest

    Öö Tiib <> writes:
    >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>
    ....

    ?
     
    Stefan Ram, Mar 19, 2013
    #7
  8. Willi

    Öö Tiib Guest

    On Tuesday, 19 March 2013 16:48:34 UTC+2, Stefan Ram wrote:
    > Öö Tiib <> writes:
    > >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>
    > ...
    >
    > ?


    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. ;)
     
    Öö Tiib, Mar 19, 2013
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. kj
    Replies:
    1
    Views:
    381
    Ashmodai
    Apr 15, 2004
  2. Mike
    Replies:
    3
    Views:
    491
  3. Jason
    Replies:
    0
    Views:
    414
    Jason
    Aug 21, 2003
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    451
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. Bruno Desthuilliers

    Heterogeneous lists

    Bruno Desthuilliers, Aug 6, 2007, in forum: Python
    Replies:
    5
    Views:
    308
    Hendrik van Rooyen
    Aug 8, 2007
Loading...

Share This Page