imports and a data structure (any critique welcome)

[Timon Gehr]

On 12/27/2013 05:08 PM, Jonathan wrote:
> Let me just check my understanding:  If a function says it returns a
> thing of type T, it really does return something whose outermost shape
> is T; however, if it contains pointers to other things, and these were
> stack allocated, the pointers might be readdressed.
> ...

Well, the it is returned as-is, but the value of something that contains 
indirections is in general only meaningful in the context of a 
corresponding heap, stack and static data segment. Here the stack is 
changed in a way that renders the pointers in the returned value 
meaningless, so type safety does not hold. (Outside of @safe code, type 
safety is conditional on the programmer making sure that code does not 
violate certain invariants.)

> @Bearophile: in your example, why is the array heap allocated?

This is just how the language feature works. The array literal allocates 
an array on the heap and gives you a slice to it. (If you assign such a 
literal to a static variable during compilation, it will actually be 
stored in the static data segment.)

> For arrays do you not need to use new?
> ...

You can also allocate a new array using new:

auto x = new int[](4); // allocate array of 4 elements

> ...
>
> It makes sense that union is not type safe.  If I have a struct like this
> ...
> }
>
> That seems like a bad practice leaving one of the fields
> uninstantiated.  Is this is a sign that I should be using an object
> oriented approach, or is there a way to clean this up.
> ...

The only way to clean it up is to hide it behind a type safe interface. 
(Besides concise syntax, that's all the ADT mixin template is doing 
essentially.)

> I have to admit, I don't understand the mixin/template stuff right now.
> However the mixin ADT thing seems pretty sexy, so it might be a good
> idea to learn enough to understand what is going on there.

It parses the given specification (q{this is a string}), generates D 
code as a string using the built-in D interpreter that the compiler 
comes with. ("Using CTFE".) Then the generated D code is "mixed in" and 
compiled.

> The problem
> I have with this is if it ends up describing a struct in the background,
> will I have to keep a bunch of conventions straight in my head, or are
> there lots of utilities for working with this kind of thing (i.e. can I
> do a case operation, and recurse on subterms)?

Well, it is implemented in D code, so that's up to you. The 
proof-of-concept implementation supports pattern matching.

> Are templates considered a good practice in D?
> ...

Yes, but mixins less so. (They are considered good if there is no other 
way to get what you want.)

> Also, would
>
> mixin ADT!q{ Term: Var char | Op char Term[] | Ptr Term*};
>
> be considered valid.  If so, then it would allow me to create a term t
> get its pointer, p, and then have
>    Op 'g' (Ptr p, Ptr p)
> so that in rewriting g(t,t), I only need to rewrite t once.
> ...

A full-blown ADT implementation probably would not tolerate mutable 
aliasing.

> Suppose a seasoned D programmer were thinking about this problem: would
> (s)he opt for an object oriented approach  or the use of structs.  The
> main point of this data structure is to implement term rewriting.  There
> will probably be a lot of object creation -- especially in building and
> applying substitution lists.  I don't see any real benefit of one of the
> other for this application.
>
> I tend not to worry too much about being performance critical i.e.
> cutting corners to shave off constants at the expense of losing safety
> ... I tend to prefer a simpler approach as long as I can guarantee that
> the big-O is the same -- however, I try to avoid even logarithmic
> "blowups" in comparable approaches ...

You should probably just go with classes then. (It's what I've done for 
a recent toy implementation of the calculus of constructions.)