Re: How would you solve this 'interview' question in D?
On Wednesday, 26 June 2013 at 22:43:05 UTC, David wrote:
Am 26.06.2013 22:51, schrieb Gary Willoughby:
Just for a bit of fun, I saw this question posted on reddit
the other
day and wondered how *you* would solve this in D?
http://stackoverflow.com/questions/731832/interview-question-ffn-n
I solved it ;)
http://dpaste.dzfl.pl/5cd56e9d
Let's keep it simple:
int f(uint n) { return n; }
uint f(int n) { return -n; }
Re: Passing Appender by value
On Saturday, 22 June 2013 at 13:48:53 UTC, Andrej Mitrovic wrote:
On 6/22/13, Andrej Mitrovic wrote:
Appender!(int[]) buffer;
call(buffer);
writeln(buffer.data); // writes [], it's empty
Apparently it's the same thing as the old AA problem.
Essentially the
buffer would have to be initialized first by appending:
-
import std.array;
import std.stdio;
void call(Appender!(int[]) buffer)
{
buffer.put(1);
}
void main()
{
Appender!(int[]) buffer;
call(buffer);
assert(buffer.data.empty); // passes
call(buffer);
assert(buffer.data.empty); // still passes
buffer.put(2);
call(buffer);
assert(buffer.data == [2, 1]); // now it finally went
through
}
-
It has something to do with null-initialization. I remember the
discussion about this problem with hashes, I just can't
remember if
there was a bug report about it to link to.
The problem occurs whenever the internal array is resized because
what actually happens is that a new array is allocated and the
contents copied over - the original Appender still references the
original array (or in this case null). The last example only
works because when you call "put(2)" it actually allocates an
array large enough to hold at least another item as well.
As usual it can be solved by introducing an extra layer of
indirection, either by passing by ref or by making Appender store
a pointer to a range.
Re: randomShuffle
On Thursday, 20 June 2013 at 21:48:49 UTC, Joseph Rushton Wakeling wrote: On 06/04/2013 01:03 PM, Diggory wrote: Still a few places to optimise, and I think the compiler optimisation should be able to give a decent speed up as well. Would be interested to see how it compares in your benchmark! VERY belated apologies for not getting back to you here. I was preparing an email on the nice features of RandomSample -- e.g. that you can use it to sample lines from a file -- when I realized that actually there was a bug that stopped you from doing that: http://d.puremagic.com/issues/show_bug.cgi?id=10265 So I stopped to prepare a fix, and then I got distracted with a bunch of things I realized could be done to improve std.random ... :-P Anyway, I _will_ do the benchmark. Just might be a little while. Haha, no problem!
Re: Is the -property compiler flag broken/bad idea?
On Thursday, 6 June 2013 at 10:38:27 UTC, Martin Primer wrote:
What would be good is:
@property int foo {
get() {
_val = value;
}
set() {
value = _val;
}
}
usage:
foo = 12;
int bar = foo;
my 2 cents.
That's both much more limited and longer than the current syntax.
It also turns properties from a simple rewrite rule into a full
language feature, and it doesn't seem to give any benefits?
Re: Is the -property compiler flag broken/bad idea?
On Thursday, 6 June 2013 at 00:56:22 UTC, Adam D. Ruppe wrote: On Thursday, 6 June 2013 at 00:08:31 UTC, Jonathan M Davis wrote: Which is essentially the position of weak property enforcement. Yes, though I wish we would stop calling it 'enforcement' because nothing actually needs to be especially enforced if we do it right! @property int foo(); foo(); // error, type int is not callable @property void delegate() foo(); foo(); // works, calls the returned delegate. This isn't a syntax case in the parser looking at syntax, it is a natural consequence of the @property function call being substituted for its return value. Similarly btw: &foo; // error, foo is not an lvalue because foo here is a returned int or whatever. This isn't directly substitutable for a plain "int foo", but that's ok because one benefit of properties is we get to do things regular members can't, like restrict read or write access like this. @property ref int foo(); static assert(is(typeof(foo) == int)); static assert(is(typeof(&foo) == int*)); foo = 10; // ok that works now because ref int is an lvalue. An @property returning a reference is one case were we should be able to get (almost*) 100% substitution between it and a regular member variable. * __traits(propertyImplementation, foo) or something like that might still show something different, but if you're using that kind of thing, it is clear that you want special access anyway. I've tried to implement this in the compiler before. It seems like it would be a simple case of a semantic rewrite of "foo" into "foo()" iff foo is @property as soon as you see it. But the implementation is hard because of things like setters. foo = 10 should be rewritten into foo(10), but that's easier said than done - it either has to undo the foo->foo() rewrite on the left hand side, then look for the matching setter, or the rewrite has to be moved and moving it means duplicating it in all the bazillion places it can be referenced. So my attempt got 90% to where I wanted pretty easily, but that last 10% is a hell of a bump in the road and I haven't figured it out yet. A working pull request would surely be a big step toward closing this discussion once and for all, I wish I had more free time, I have so much D I want to hack on! That would be good - some breakage could be avoided by checking if the return type of the property implements the function call operator, if it doesn't you could accept the "getter()" syntax with only a warning/deprecation message.
Re: randomShuffle
Here's the fixed one:
uint[] randomSample(uint N, uint M) {
uint[] result = new uint[N];
struct hashPair {
uint key;
uint index;
}
size_t tableSize = N*4;
if (tableSize > M)
tableSize = M;
hashPair[] table = new hashPair[tableSize];
for (uint i = 0; i < N; ++i) {
uint v = (rndGen.front % (M-i))+i;
uint newv = v, newi = i;
rndGen.popFront();
uint ihash = i%tableSize;
while (table[ihash].index) {
if (table[ihash].key == i) {
newi = table[ihash].index-1;
break;
}
}
uint vhash = v%tableSize;
while (table[vhash].index) {
if (table[vhash].key == v) {
newv = table[vhash].index-1;
table[vhash].index = newi+1;
goto done;
}
vhash = (vhash+1)%tableSize;
}
table[vhash].key = v;
table[vhash].index = newi+1;
done:
result[i] = newv;
}
return result;
}
Still a few places to optimise, and I think the compiler
optimisation should be able to give a decent speed up as well.
Would be interested to see how it compares in your benchmark!
Re: randomShuffle
On Tuesday, 4 June 2013 at 08:30:58 UTC, Diggory wrote:
On Monday, 3 June 2013 at 21:24:50 UTC, Joseph Rushton Wakeling
wrote:
On 06/03/2013 08:28 PM, Diggory wrote:
I'd guess that the heavy use of floating point arithmetic to
calculate the step
sizes means that algorithm has a fairly large constant
overhead even though the
complexity is smaller.
Yes, I agree. There might be some optimizations that could be
done there.
Well I've come up with this new algorithm:
uint[] randomSample(uint N, uint M) {
uint[] result = new uint[N];
struct hashPair {
uint key;
uint index;
}
size_t tableSize = N*4;
if (tableSize > M)
tableSize = M;
hashPair[] table = new hashPair[tableSize];
for (uint i = 0; i < N; ++i) {
uint v = (rndGen.front % (M-i))+i;
uint newv = v;
rndGen.popFront();
uint vhash = v%tableSize;
while (table[vhash].index) {
if (table[vhash].key == v) {
newv = table[vhash].index-1;
table[vhash].index = i+1;
goto done;
}
vhash = (vhash+1)%tableSize;
}
table[vhash].key = v;
table[vhash].index = i+1;
done:
result[i] = newv;
}
return result;
}
It's O(N) rather than O(N²). Conceptually it works by randomly
shuffling the first N items in an array of size M which takes
O(N) time but requires an array of size O(M), so to avoid this
it uses a simple hash table to store just the items which have
been swapped. Since only O(N) items are being shuffled there
can only be O(N) swaps and so the hash table can be O(N) in
size while still offering constant time look-up.
OK, posted too soon! There's a small bug in this one where it
could potentially return the same value twice, it can be fixed by
looking up "i" in the hash table as well as "v".
Re: randomShuffle
On Monday, 3 June 2013 at 21:24:50 UTC, Joseph Rushton Wakeling
wrote:
On 06/03/2013 08:28 PM, Diggory wrote:
I'd guess that the heavy use of floating point arithmetic to
calculate the step
sizes means that algorithm has a fairly large constant
overhead even though the
complexity is smaller.
Yes, I agree. There might be some optimizations that could be
done there.
Well I've come up with this new algorithm:
uint[] randomSample(uint N, uint M) {
uint[] result = new uint[N];
struct hashPair {
uint key;
uint index;
}
size_t tableSize = N*4;
if (tableSize > M)
tableSize = M;
hashPair[] table = new hashPair[tableSize];
for (uint i = 0; i < N; ++i) {
uint v = (rndGen.front % (M-i))+i;
uint newv = v;
rndGen.popFront();
uint vhash = v%tableSize;
while (table[vhash].index) {
if (table[vhash].key == v) {
newv = table[vhash].index-1;
table[vhash].index = i+1;
goto done;
}
vhash = (vhash+1)%tableSize;
}
table[vhash].key = v;
table[vhash].index = i+1;
done:
result[i] = newv;
}
return result;
}
It's O(N) rather than O(N²). Conceptually it works by randomly
shuffling the first N items in an array of size M which takes
O(N) time but requires an array of size O(M), so to avoid this it
uses a simple hash table to store just the items which have been
swapped. Since only O(N) items are being shuffled there can only
be O(N) swaps and so the hash table can be O(N) in size while
still offering constant time look-up.
Re: randomShuffle
On Monday, 3 June 2013 at 17:35:22 UTC, Joseph Rushton Wakeling wrote: On 06/03/2013 07:00 PM, Diggory wrote: Thanks for testing before dismissing completely :P The way it returns results can be improved a lot by pre-allocating a range of the necessary size/using a range passed in. Surely. :-) The complexity is O(N²) where N is the number of samples out of M. The algorithm is something I just thought of although I've possibly used it before and I'm sure someone else has thought of it too. It's quite simple, it effectively says "pick a value from the range except for this value" recursively but instead of dividing the range in two, it shifts the top part down first to make a contiguous range and then shifts the results which are past the split up one afterward. It's an interesting little piece of invention. I'll have to look around and see if there's anything similar documented. I've not seen anything in the literature which has this particular property of O(N) random variates plus O(N^2) calculation. The fact that it's not sequential might have been a bit of an issue historically, which maybe explains why I haven't come across something like it. I expect the phobos implementation to be something like O(M) in which case my method would be faster whenever N < sqrt(M) (with the optimisations) No, the Phobos implementation is O(N) -- I wrote it :-) See: http://braingam.es/2012/07/sampling-d/ The API is Andrei's -- the original implementation used what Knuth refers to as Algorithm S [which is really simple and easy to implement and check, but is indeed O(M)], I updated it to use Algorithm D (which is complicated:-). So, since randomSample takes kN time where k is constant, your algorithm will probably win where N < k. I found that the sampling time was about equal with N = 50 and your algorithm as it's currently written. I'd guess that the heavy use of floating point arithmetic to calculate the step sizes means that algorithm has a fairly large constant overhead even though the complexity is smaller.
Re: randomShuffle
On Monday, 3 June 2013 at 13:18:30 UTC, Joseph Rushton Wakeling
wrote:
On 06/03/2013 02:30 PM, Joseph Rushton Wakeling wrote:
On 06/03/2013 01:29 PM, Diggory wrote:
For small samples from very large ranges an efficient
algorithm would be:
int[] randomGen(int N, int M) {
if (N == 0)
return [];
int[] result = randomGen(N-1, M-1);
int num = rand(M);
foreach (ref int i; result)
if (i >= num)
++i;
result ~= num;
return result;
}
Are you sure about the efficiency of that algorithm? Looks
like it's be O(M) to me.
Apologies, I misread the algorithm slightly. Your qualifier is
quite correct --
when the number of sample points is very small (e.g. 5 out of
some arbitrary
very large number), that algorithm is very quick indeed (I ran
some tests as I
was curious:-), and can outperform D's randomSample.
It doesn't scale with the size of the input (your value M), but
with the number
of sample points n, but that scaling is very bad -- so as the
sample size grows
it becomes _much_ worse than randomSample.
Do you have a reference for the algorithm? Off the top of my
head I don't
recognize it from any of the texts I've read.
Thanks for testing before dismissing completely :P The way it
returns results can be improved a lot by pre-allocating a range
of the necessary size/using a range passed in.
The complexity is O(N²) where N is the number of samples out of
M. The algorithm is something I just thought of although I've
possibly used it before and I'm sure someone else has thought of
it too. It's quite simple, it effectively says "pick a value from
the range except for this value" recursively but instead of
dividing the range in two, it shifts the top part down first to
make a contiguous range and then shifts the results which are
past the split up one afterward.
I expect the phobos implementation to be something like O(M) in
which case my method would be faster whenever N < sqrt(M) (with
the optimisations)
Re: Structs should not contain pointers to internal data
On Monday, 3 June 2013 at 16:00:58 UTC, Ali Çehreli wrote:
On 06/03/2013 05:26 AM, Saurabh Das wrote:
> Thank you @Ali and @Jonothan!
>
> So essentially since I will be storing a pointer,
Telemetry!(T) is NOT safe
> to use only with structs in general.
>
> If I have something like:
>
> struct UsefulStruct2
> {
> this(this) @disable;
> this(UsefulStruct2) @disable;
>this(ref const(UsefulStruct2)) @disable;
>ref UsefulStruct2 opAssign(UsefulStruct2) @disable;
>ref UsefulStruct2 opAssign(ref const(UsefulStruct2))
@disable;
>
> int importantValue;
> auto tel1 = Telemetry!int(importantValue);
> }
>
> Does that ensure that UsefulStruct2 is not relocateable and
thus I can
> safely store a pointer to importantValue?
No. The compiler can still move a struct by blit (bit level
transfer). Blit is based on good old memcpy. For a "copy",
post-blit is for making corrections after the fact. On the
other hand, the programmer cannot interfere if it is a "move".
For example, rvalues are moved, e.g. to an array element as in
the following example:
import std.stdio;
import std.array;
struct UsefulStruct2
{
this(this) @disable;
this(UsefulStruct2) @disable;
this(ref const(UsefulStruct2)) @disable;
ref UsefulStruct2 opAssign(UsefulStruct2) @disable;
ref UsefulStruct2 opAssign(ref const(UsefulStruct2))
@disable;
int importantValue;
int * p;
}
UsefulStruct2 makeObject(int i)
{
UsefulStruct2 u;
u.importantValue = i;
u.p = &u.importantValue; // <-- self-referencing
return u;
}
void main()
{
auto arr = [ makeObject(1) ];
assert(arr.front.p != &arr.front.importantValue); //
PASSES!
}
> If not, what constraints do I need to add to my classes to
ensure that I
> don't run into subtle bugs when structs relocate?
As you see, @disable is cripling and not a solution for this.
As far as I know, the only option is to observe this rule.
I agree with you that a struct may become self-referencing,
unknowingly and indirectly through members of other types.
Ali
You can get around this limitation by making a wrapper struct
which uses special values to represent pointers which point
within the containing struct, and does the conversion
automatically when you dereference it.
Re: randomShuffle
On Monday, 3 June 2013 at 10:10:15 UTC, Yann wrote:
Thanks a lot for the suggestions!
Cheers,
Yann
On Monday, 3 June 2013 at 10:06:30 UTC, bearophile wrote:
Yann:
Is there a better way to accomplish this? Naively, I would
expect something like
"return iota(1, 1000).randomShuffle.take(10).sort;"
Two ways, the first gives items in random order, the second
ordered as you seem to desire:
import std.stdio, std.random, std.range, std.array;
void main() {
iota(1, 1001).randomCover(rndGen).take(10).writeln;
iota(1, 1001).randomSample(10).writeln;
}
But be careful with randomCover, because maybe it takes the
rnd generator by value.
Bye,
bearophile
For small samples from very large ranges an efficient algorithm
would be:
int[] randomGen(int N, int M) {
if (N == 0)
return [];
int[] result = randomGen(N-1, M-1);
int num = rand(M);
foreach (ref int i; result)
if (i >= num)
++i;
result ~= num;
return result;
}
Re: Are heap objects never moved by the garbage collector?
On Saturday, 1 June 2013 at 08:11:05 UTC, sclytrack wrote: On Friday, 31 May 2013 at 16:31:39 UTC, Carl Sturtivant wrote: "The D Programming Language" (TDPL) p.178 asserts the following. "The objects themselves stay put, that is their locations in memory never change after creation." I take this to mean that the D garbage collector doesn't move live objects and adjust all references to them the way that some garbage collectors do. That is to say, the addresses of objects are not changed by the garbage collector. Does D guarantee this? No. Quoted from the D website: http://dlang.org/garbage.html "Although D does not currently use a moving garbage collector, by following the rules listed above one can be implemented. No special action is required to pin objects. A moving collector will only move objects for which there are no ambiguous references, and for which it can update those references. All other objects will be automatically pinned. " I'll assume you can not move immutable pointers. Immutable pointers are not mentioned on that page. (except in the index left :) Actually that's wrong - a moving GC would break everything in D since the GC cannot know if there are any ambiguous references. As soon as you pass a pointer to an external function there's no way for the GC to know if that pointer or any pointers accessible from it will ever be safe to move again. Pinning has to be explicit or it doesn't work, and currently all of phobos and druntime is implemented without it.
Re: Are heap objects never moved by the garbage collector?
On Friday, 31 May 2013 at 17:14:52 UTC, Jonathan M Davis wrote: On Friday, May 31, 2013 18:31:38 Carl Sturtivant wrote: "The D Programming Language" (TDPL) p.178 asserts the following. "The objects themselves stay put, that is their locations in memory never change after creation." I take this to mean that the D garbage collector doesn't move live objects and adjust all references to them the way that some garbage collectors do. That is to say, the addresses of objects are not changed by the garbage collector. Does D guarantee this? I don't believe that there is any such guarantee in the language. Structs on the heap get moved around all the time, so having objects with references to themselves is effectively disallowed. The GC does not currently ever move any objects, but I don't believe that the language itself guarantees that it never will. It may be that in the future it would, though it's unlikely given some of the technical difficulties caused by having unmanaged pointers and void* and whatnot. Languages which run in a VM and are restricted to managed pointers are able to make many more assumptions than D is, making it much easier for them to do moveable garbage collectors. - Jonathan M Davis I assume you mean structs on the stack rather than on the heap - structs on the heap are never moved currently.
Re: double vs real
On Thursday, 30 May 2013 at 16:18:44 UTC, Shriramana Sharma wrote: Hello. I like that D exposes to me the real type to maximally utilize the machine's numerical precision. Since I am writing a program (currently in C++ but I am thinking of moving to D) that has to handle lots of fractional numbers (calculating offset curves and such) I am wondering whether/when I should real instead of double or even any arguments in favour of staying with double (compatibility with C/C++?). Any pointers appreciated please? I checked the FAQ but it doesn't seem to mention this. Thanks! Since D does all operations at highest possible precision anyway (even for double or float) it only makes a difference when the value is being stored to memory and then read back again. I would recommend aliasing double or real to a custom name and then using that. Then when you're done you can easily switch between them and see how it affects precision in your particular case and decide what's best.
Re: regex with literal (ie automatically replace '(' with '\(', etc) )
Your suggestion does not work; try for yourself by replacing
the $$ by \$
in my code. Is that a bug in std.regex' doc?
eg:
replace("",regex(``),`\$`);
=> invalid format string in regex replace
However everything works fine with $$, see my code above.
Either the doc or the code should probably be changed then so
they are consistent.
Re: regex with literal (ie automatically replace '(' with '\(', etc) )
On Thursday, 30 May 2013 at 06:50:06 UTC, Timothee Cour wrote: ok, here it is: https://github.com/timotheecour/dtools/blob/master/dtools/util/util.d#L78 simplified implementation and added missing escape symbols. Any symbol missing? I was basing myself based on http://dlang.org/phobos/std_regex.html, table entry '\c where c is one of', but that was incomplete. I'm also noting that table entry 'any character except' is also incomplete. Technically any working "escapeRegex" would also function as a valid "escapeRegexReplace", although it might be slightly faster to have a specialised one. not sure, because they escape differently (\$ vs $$). According to this: http://dlang.org/phobos/std_regex.html#.replace you can use the same escape sequences for both (\c -> c in the replacement string).
Re: Consume an entire range
On Thursday, 30 May 2013 at 04:18:14 UTC, Jonathan M Davis wrote: On Thursday, May 30, 2013 06:12:51 Diggory wrote: On Thursday, 30 May 2013 at 03:53:06 UTC, Brad Anderson wrote: > On Thursday, 30 May 2013 at 03:50:52 UTC, Brad Anderson > wrote: >> Is there a simple way to consume a range apart from >> std.array.array? I don't need to result of the range stored >> in an array, I just need a lazy map to evaluate completely. > > Obviously I could just popFront. To be more clear, I want > something like eat() or consume() or exhaust() that I can > tack > on the end of my chained algorithm calls. There's "walkLength"? Ah, I should have thought of that, though that won't work if the range defines length. Of course, if it defines length, you can always use popFrontN with length. - Jonathan M Davis Do you think it would be worth adding a "consume" method to std.range or std.algorithm?
Re: Consume an entire range
On Thursday, 30 May 2013 at 03:53:06 UTC, Brad Anderson wrote: On Thursday, 30 May 2013 at 03:50:52 UTC, Brad Anderson wrote: Is there a simple way to consume a range apart from std.array.array? I don't need to result of the range stored in an array, I just need a lazy map to evaluate completely. Obviously I could just popFront. To be more clear, I want something like eat() or consume() or exhaust() that I can tack on the end of my chained algorithm calls. There's "walkLength"?
Re: regex with literal (ie automatically replace '(' with '\(', etc) )
On Wednesday, 29 May 2013 at 23:33:30 UTC, timotheecour wrote:
something like this, which we should have in std.regex:
string escapeRegex(string a){
import std.string;
enum transTable = ['[' : `\[`, '|' : `\|`, '*': `\*`, '+':
`\+`, '?': `\?`, '(': `\(`, ')': `\)`];
return translate(a, transTable);
}
string escapeRegexReplace(string a){
import std.string;
// enum transTable = ['$' : `$$`, '\\' : `\\`];
enum transTable = ['$' : `$$`];
return translate(a, transTable);
}
unittest{
string a=`asdf(def[ghi]+*|)`;
assert(match(a,regex(escapeRegex(a))).hit==a);
string b=`$aa\/$ $$#@$\0$1#$@%#@%=+_`;
auto s=replace(a,regex(escapeRegex(a)),escapeRegexReplace(b));
assert(s==b);
}
That would be good (although you missed a few :P)
Technically any working "escapeRegex" would also function as a
valid "escapeRegexReplace", although it might be slightly faster
to have a specialised one.
Re: iteration over a string
Most algorithms for strings need the offset rather than the
character index, so:
foreach (i; dchar c; str)
Gives the offset into the string for "i"
If you really need the character index just count it:
int charIndex = 0;
foreach (dchar c; str) {
// ...
++charIndex;
}
If strings were treated specially so that they looked like arrays
of dchars but used UTF-8 internally it would hide all sorts of
performance costs. Random access into a UTF-8 string by the
character index is O(n) whereas index by the offset is O(1).
If you are using random access by character index heavily you
should therefore convert to a dstring first and then you can get
the O(1) random access time.
Re: Immutability vs reference types
On Tuesday, 28 May 2013 at 00:24:32 UTC, Francois Chabot wrote:
Hello, I'm trying to get back into D again. This time around,
I'm
playing mostly with concurency and parallism, all the while
trying to get my code writen in "the D way" as much as possible.
I've run into a rather major road block that seems rather
nonsensical at face value, so I'm not sure if i'm
misinterpreting
the nature of immutability...
Here's kinda what I WANT to do:
class DataChunk { }
struct DepPassResult {
immutable( DataChunk ) target_chunk ;
immutable( string ) [] foundDeps ;
}
immutable( DataChunk )[ string ] chunk_db ;
void doWork( const string[] chunks , int workers_count ) {
auto workers = new TaskPool( workers_count ) ;
foreach( chunk ; chunks ) {
_workers.put( task!doDepPass( chunk_db[ chunk ] ,
thisTid )
)
;
}
bool all_done = false ;
while( !all_done )
{
receive(
( DepPassResult r ) { ... } ,
...
) ;
}
workers.stop() ;
}
void doDepPass( immutable( DataChunk ) data , Tid main_thread )
{
...
main_thread.send( DepPassResult( data , [ "whatever" ] )
) ;
}
Obviously, there's a lot more to it, but that's enough to
illustrate my problem.
DepPassResult is being rejected as a valid Variant type (only at
run time might I add) because it's not re-assignable. Fair
enough.
I have a few easy options at my disposal, but all of them seem
pretty bad to me:
1. DepPassResult.target_chunk could be made a string, but that
would require DataChunk to be aware of the index value it has in
chunks_db.
2. DepPassResult.target_chunk could be made a pointer, which
just
screams workaround.
3. DepPassResult.target_chunk could be made a slice that by
convention will only ever point to an array of 1 DataChunk
It's the fact that #3 works that kills me.
If with immutable(Type)[], I can have a re-assignable reference
to arrays of immutable data, I really should be able to have
some
form of syntactical equivalent for single instances. But there
just doesn't seem to be one. Immutability for reference types
seem to always apply both to the referenced data as well as the
reference itself no matter what.
Considering how critical immutability is to concurency and
paralellism in D, that seems like a pretty big missing piece of
the puzzle. I've got to be overseeing something here. Please
help.
It looks like Michel Fortin did some work on this years ago
(though for completely unrelated reasons):
http://forum.dlang.org/thread/bug-532...@http.d.puremagic.com/issues/
Did this ever pan out? or has some form of equivalent or
standard
work-around been established?
This is still a known problem with no nice solution. One other
possibility is making DataChunk a struct and then make two
classes, MutableDataChunk and ImmutableDataChunk which contain
mutable and immutable versions of that struct respectively. You
can use "alias this" on each class to automatically forward calls
to the inner struct.
I haven't tried this out myself so there may be other problems
doing it this way but it's something to consider at least.
Re: lookup fields struct
On Sunday, 26 May 2013 at 23:37:01 UTC, mimi wrote: Wow! thanks! "offsetof" will automatically distribute over the arguments so to get the offsets of a tuple you can just do: auto tmp = TP.offsetof; And "tmp" will be a tuple of the offsets.
Re: Mixin Templates Over-restricted?
On Saturday, 25 May 2013 at 18:05:01 UTC, yaz wrote:
Is there a reason for restricting mixin templates to only
include declarations?
For example, the following code doesn't work.
(http://dpaste.dzfl.pl/1582a25e)
Looking at the language specification
(http://dlang.org/template-mixin.html) this doesn't seem to be
an implementation limitation.
import std.stdio;
mixin template Test() {
writeln("Hello D People!");
}
void main() {
mixin Test;
}
I would have posted to the main newsgroup but I thought that
maybe I'm missing something.
Thanks.
I think you can do it using a string mixin instead:
enum Test = `writeln("Hello D People!")`
void main() {
mixin(Test);
}
The answer to your question is probably that D has to know the
context for a template mixing at the point where it is declared
rather than where it is used.
If non-declarations were allowed the semantic meaning of the
template mixin would depend on the way it was used, and that's
not allowed.
I could also be completely wrong of course :P
Re: WindowProc in a class - function and pointer problem
On Wednesday, 22 May 2013 at 20:25:40 UTC, Simen Kjaeraas wrote: On 2013-05-22, 21:30, D-sturbed wrote: Hello, is there a way to wrap a WindowProc (so "LRESULT WindowProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam) nothrow") in a class and to link it to a WindowClass without puting it as "static" ? Because defacto every datum used in the WindowProc must also be static. The problem technically is that if "static" is not specified, the compiler won't allow this: "MyWinClass.lpfnWndProc = &TheWindowProcInMyClass". I've also tried this: "MyWinClass.lpfnWndProc = (&TheWindowProcInMyClass).funcptr" but, while it compiles, it drastically fails at the run-time... Not possible, no. What you *can* do is have some way to translate from hwnd to class instance, and fetch the right instance inside the static wndProc to call a member function on that. If you are only going to have one window you can store the "this" pointer in a global variable. If you want to have multiple windows each with messages going to an instance of a class, you need to do the following: - Specify the "this" pointer as the lpParam argument to CreateWindow - Hook up a static WndProc function - Have the static function handle a WM_NCCREATE message as follows: - Cast the "lParam" parameter to a CREATESTRUCT* and retrieve the "this" pointer from the "lpCreateParams" member. - Use "SetWindowLongPtr" to set the GWLP_USERDATA property of the window "hwnd" to the "this" pointer - Have the static function handle all messages as follows: - Use "GetWindowLongPtr" to get the GWLP_USERDATA property of the window "hwnd" to get the "this" pointer - Pass the message on to a non-static WndProc in the class using the discovered "this" pointer You also need to make sure that there is a separate reference to the class instance for as long as the window exists, because the garbage collector will not scan the window properties and so may think the object is garbage otherwise.
Re: static analysis: how to test code reachability at compile time
On Tuesday, 21 May 2013 at 21:15:58 UTC, Timothee Cour wrote:
I'd like to have the following tools to help with static
analysis & code
coverage:
1) test whether code is reachable or not.
Of course it only works for executables and may have some
caveats (eg:
goto), but its still useful diagnostic tool.
__traits(isReachable): true when the current context can be
reached via at
least one code path starting from main():
void fun1(){
//__traits(isReachable) would be false here because even though
fun1 is
called by fun2, it can never be called starting from main().
}
void fun2(){fun1;}
void fun3(){} // would also be false, because of static
if(temp); with temp
being known to be 0 at compile time.
void fun4(){
return;
//__traits(isReachable) would be false here because all code
paths return
above this point.
}
void main(){enum temp=0; static if(temp) fun3; fun4;}
When a pointer to a function is taken, we may want to assume by
convention
that __traits(isReachable) is true.
This would enable for example to make sure a given code is
never called.
Note, static assert(0) is not the same.
2)
static code call graph: know caller/calling functions for a
given function.
3) static code coverage
this would allow us to tell at compile time the code coverage
of a module;
it is larger than runtime coverage, but still useful to find
dead code.
It would be very easy to introduce paradoxes if this were
possible, simply use a static if to call something only if it is
unreachable.
Re: Enum of types
On Tuesday, 21 May 2013 at 05:48:31 UTC, Ali Çehreli wrote:
On 05/20/2013 09:58 PM, Diggory wrote:
> On Tuesday, 21 May 2013 at 04:36:57 UTC, Ali Çehreli wrote:
>> Sounds like std.variant.Algebraic:
>>
>> http://dlang.org/phobos/std_variant.html#.Algebraic
>>
>> Ali
>
> I don't see how I could use that. Algebraic is for storing a
value, I'm
> trying to store just a type.
But you did say you needed to store data: "... an object that
stores some typed data ... the user should be able to tell it
what type of data it will hold."
With my current limited understanding, I still think Algebraic
would be a solution.
Ali
The data is stored elsewhere in a black-box completely outside
D's jurisdiction. Also the type of the data is supplied first,
and the data itself is supplied at a later time.
I gave up on the mixin idea but have come up with this:
import std.typetuple;
struct TypeEnum(T...) {
private int index;
private this(int index) {
this.index = index;
}
template from(U) {
static assert(staticIndexOf!(U, T) != -1, "Type is not in the
list of possible types for this TypeEnum");
public enum from = TypeEnum!T(staticIndexOf!(U, T));
}
}
Example usage:
alias TypeEnum!(
ubyte,
ushort,
float
) gpElementType;
gpElementType test = gpElementType.from!float;
Might make a nice addition to std.variant, no?
Re: Enum of types
On Tuesday, 21 May 2013 at 04:36:57 UTC, Ali Çehreli wrote: Sounds like std.variant.Algebraic: http://dlang.org/phobos/std_variant.html#.Algebraic Ali I don't see how I could use that. Algebraic is for storing a value, I'm trying to store just a type.
Enum of types
I want to create an enum of some number of types, eg. { ubyte,
ushort, uint, float }
It should be straightforward to get a member of the enum from the
type itself. Basically I have an object that stores some typed
data, but the type may not be known at compile time, only the set
of possible types. When constructing the object the user should
be able to tell it what type of data it will hold. Also the
underlying type of the enum should be efficient to store and
compare.
So far the best I can come up with is using a mixin and CTFE to
generate the code for an enum plus a template function to convert
from a type to a member of the enum, but it seems like there
might be a better way?
Re: Cross product template
On Wednesday, 15 May 2013 at 01:31:43 UTC, Diggory wrote:
I have a vector struct, Vector(T, uint N) templated on the type
T and number of components, N. I'm trying to write a function
"cross" which will calculate the cross product of a number of
vectors.
For a given number of components, N, the cross function should
take N-1 arguments, each one a Vector!(?, N) and will return a
vector perpendicular to the vectors passed in. The ? means the
type is free to be anything.
The problem is that however I try to write it, the template
argument deduction isn't powerful enough to work out which
instantiation to use.
I thought something like this would work to deduce the
parameters and then I could use constraints to enforce the
other rules, but no:
auto cross(T, N, U...)(Vector!(T, N) a, U b) { return 0; }
Well, after much trial and error I ended up with this, which
seems to work:
template VectorN(T : Vector!(T, N), uint N) {
enum VectorN = N;
}
template isVectorN(uint N) {
template isVectorN(T) {
enum isVectorN = VectorN!(T) == N;
}
}
auto cross(T...)(T args) if (allSatisfy!(isVectorN!(T.length+1),
T) && T.length) {
return 0;
}
Cross product template
I have a vector struct, Vector(T, uint N) templated on the type T
and number of components, N. I'm trying to write a function
"cross" which will calculate the cross product of a number of
vectors.
For a given number of components, N, the cross function should
take N-1 arguments, each one a Vector!(?, N) and will return a
vector perpendicular to the vectors passed in. The ? means the
type is free to be anything.
The problem is that however I try to write it, the template
argument deduction isn't powerful enough to work out which
instantiation to use.
I thought something like this would work to deduce the parameters
and then I could use constraints to enforce the other rules, but
no:
auto cross(T, N, U...)(Vector!(T, N) a, U b) { return 0; }
Re: Interface vs pure abstract class - speed.
On Sunday, 12 May 2013 at 17:31:22 UTC, SundayMorningRunner wrote: Hello, let's say I have the choice between using an abstract class or an interface to declare a "plan", a "template" for the descendants. From the dmd compiler point of view, should I use the abstract class version (so I guess that for each method call, there will be a few MOV, in order to extract the relative address from the vmt before a CALL) or the interface version (are the CALL directly performed in this case). Are interface faster ? (to get the address used by the CALL). Thx. I would expect abstract classes to be slightly faster (certainly they shouldn't be slower), but the difference to be insignificant compared to other factors. Deriving from an abstract base class is a much stronger relationship than implementing an interface, so it depends on your situation. If your class is a "provider" (eg. it provides some functionality such as being able to receive some event) then an interface makes more sense. If your class is a type of something (eg. a button is a type of gui control) then inheritance makes more sense.
Re: How to reserve memory for a slice in a struct
You could allocate space inside a class itself with something
like this:
class Base {
int[] slice;
}
template Derived(size_t N) {
class Derived : Base {
int[N] array;
this() {
slice = array;
}
}
}
Base b = new Derived!32();
A bit pointless though...
Re: C Memory
On Sunday, 5 May 2013 at 07:23:25 UTC, Namespace wrote: On Sunday, 5 May 2013 at 06:43:17 UTC, Diggory wrote: On Sunday, 5 May 2013 at 06:35:38 UTC, Namespace wrote: Quick question: I have a SDL_Surface in one of my classes and the SDL_Surface contains (obviously) memory to the pixel data. Since I cannot free this memory with the DTor: what will happen? AFAIK this cannot be freed by the GC because it was not allocated by it. So AFAIK this creates a memory leak. Am I right? Why can't you free the memory from the destructor? Every time I tried this, I got this: core.exception.InvalidMemoryOperationError I do not know if I get that, because the GC has already cleaned this store or because of something else. Sounds like a bug - if the pointer is not into GC memory then the GC shouldn't touch it.
Re: C Memory
On Sunday, 5 May 2013 at 06:35:38 UTC, Namespace wrote: Quick question: I have a SDL_Surface in one of my classes and the SDL_Surface contains (obviously) memory to the pixel data. Since I cannot free this memory with the DTor: what will happen? AFAIK this cannot be freed by the GC because it was not allocated by it. So AFAIK this creates a memory leak. Am I right? Why can't you free the memory from the destructor?
Re: Check if tuple contains value at compile time
On Sunday, 5 May 2013 at 01:44:19 UTC, bearophile wrote:
Diggory:
The documentation seems too say that "[mytuple]" will make an
array,
Nope. You have to extract the inherent typetuple first. And
this is what the [] syntax does (tested):
import std.stdio, std.typecons, std.algorithm;
void main() {
auto t = tuple("foo", "bar", "spam");
assert([t[]].canFind("bar"));
}
Bye,
bearophile
Is the behaviour of the empty [] when applied to tuples
documented anywhere?
The problem is that this doesn't work if the tuple is empty:
Error: template std.algorithm.canFind does not match any function
template declaration.
And unfortunately in the situation I need it for an empty tuple
is one of the most likely scenarios.
Re: Check if tuple contains value at compile time
On Sunday, 5 May 2013 at 00:33:34 UTC, bearophile wrote: Diggory: It's not a TypeTuple, it's a tuple of strings. Then one simple way to do it is to convert it into an array of strings, and then use canFind: [mytuple[]].canFind(needle) Bye, bearophile OK, that makes sense but I'm not sure I understand that syntax. The documentation seems too say that "[mytuple]" will make an array, or that "mytuple[]" will make a slice from a tuple (presumably with no arguments it will slice the entire tuple?), so how does "[mytuple[]]" work?
Re: Check if tuple contains value at compile time
On Sunday, 5 May 2013 at 00:10:27 UTC, Simen Kjaeraas wrote: On 2013-05-05, 01:42, Diggory wrote: I'm trying to test using a "static if" statement if a tuple of strings contains a particular string. What's the easiest/best way to do this? http://dlang.org/phobos/std_typetuple#.staticIndexOf It's not a TypeTuple, it's a tuple of strings.
Check if tuple contains value at compile time
I'm trying to test using a "static if" statement if a tuple of strings contains a particular string. What's the easiest/best way to do this?
Re: D is totally useless
The wgl*** functions and "SwapBuffers" ARE part of the windows api even though they are implemented in opengl32.dll (they are declared in wingdi.h IIRC)
Re: Win32 + OpenGL bindings
you are doing it wrong. first you will need mingw32-make from mingw default setup, second fix win32 bindings makefile around line 25 so it will looks like this(supported file don't have uuid.di outdated interface file included) Yeah I realise what I was doing wrong now. It only coincidentally worked because the win32 libraries were linked in by default, although of course the functions implemented in D gave errors. I've switched to just adding missing functions as I need them to "windows.d" and recompiling the druntime. Yes, pragma(lib, ...); but it won't work for .di files. http://d.puremagic.com/issues/show_bug.cgi?id=2776 OK, I had seen that but earlier in this thread evilrat said it didn't work in GDC so I assumed it was a DMD only feature. also i would suggest you read all documents in language reference, how-tos, and sections, they are not so big but it will give answer to most begginers questions. also start reading library reference, you will save much time later. I have read all the language reference pages, but there is very little on linking and related things. Specifically, there could be a more obvious link to "deimos" so that those bindings can be found as that seems to be the most official place for such things as well as more information on how to build the .d files. (For example, the opengl project gives just a single .d file with no information about how to use it) As it turns out, the opengl project needs a .lib file to import opengl32.dll which can only be generated by getting "coffimplib.exe" (wow finding that was hard!) and running it on the platform sdk import library for opengl. Since wgl*** functions are declared in "windows.h" but are defined in "opengl32.dll" this is technically part of the platform SDK. It should really not be this hard to call a function supposedly built into the operating system. An up to date opengl32 import library should exist in "dmd2/windows/lib/". I realise D is still fairly young so it's unreasonable to expect everything to already exist, but at least enough information should be given to be able to correctly add things that don't.
Re: Win32 + OpenGL bindings
OK, thanks I think I've got the hang of the way linking works now - I was confused about how some things didn't seem to require libs to work, but now I see it's because those things were compiled into "druntime.lib" which was compiled into "phobos.lib". So is this correct, assuming I'm only talking about non-COFF libs: - D code can link directly to normal C libs - .libs generated by DMD are a superset of normal C .libs, they can contain normal C functions but DMD also has some way of representing more complicated D constructs inside the .lib file (but not templates). - druntime.lib is linked into phobos.lib so only phobos.lib needs to be linked and the compiler does this automatically (how does this work, is just hard-coded in?) Is there a compiler independent way to tell the linker to automatically link in a specific library from within a .d file? (preferable this hint should still exist in the .di file generated from that .d file, and be transitive so dependencies automatically get linked in just by "import"ing the required stuff) If not can I suggest this as a feature? I've switched to using the "head" revision in the repo and building from source which was surprisingly easy (thanks whoever set that up!) so now I can just add missing functions to windows.d as I need and rebuild and no more linker errors! Am I correct in thinking there is no specific order in the contents of windows.d? I've rearranged mine so that functions are ordered by module then header file so I can more easily see if a function already exists, and if not where to add it. Would these changes be of any use?
Re: Win32 + OpenGL bindings
On Saturday, 20 April 2013 at 10:09:37 UTC, Jacob Carlborg wrote:
On 2013-04-20 05:26, Diggory wrote:
- derelict.opengl.gl:
Has all of opengl plus wgl* functions needed for windows, but
has more
dependencies than an ideal opengl binding would have.
Dependencies, like what?
Well the opengl module depends on the util module. The util
module declares a load of stuff duplicated by the windows module
so importing them both without aliasing is impossible. All I want
is to import the raw opengl and win32 functions.
I've got my program partially working using the old win32.windows
module with an opengl module I got from elsewhere which included
"opengl32.lib", but doesn't define glViewport...
I would like to use the opengl module from deimos if possible -
it doesn't need to be particularly up to date - but I don't know
how to get/generate the .lib file for it.
Are the .lib files used with D just C/C++ .lib files? If so what
are the requirements of them - .lib files from the windows SDK
don't seem to be compatible? Do I need to generate them instead
from the .d files?
Also the program I'm compiling is bringing up a console window
when it runs, even though I'm setting the subsystem to "Windows"
and using "WinMain" exactly as the documentation describes.
Finally I seem to have discovered a bug with "final switch":
This correctly does nothing when passed "36" (neither WM_SIZE and
WM_DESTROY equal 36):
switch (message) {
case WM_SIZE:
glViewport(0, 0, LOWORD(lParam), HIWORD(lParam));
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
default:
break;
}
While this runs the "WM_DESTROY" case statement when passed 36.
final switch (message) {
case WM_SIZE:
glViewport(0, 0, LOWORD(lParam), HIWORD(lParam));
break;
case WM_DESTROY:
PostQuitMessage(0);
break;
}
Win32 + OpenGL bindings
I've been trying to write a win32 app using opengl in D, but none of the bindings I've found have been sufficient: - core.sys.windows.windows: Missing large parts of wingdi.h, including PFD_* constants, ChoosePixelFormat(), SwapBuffers(), wgl*() functions. - win32.windows: Apparantly out of date and gives linker errors, although it does declare all the functions needed. - derelict.util.wintypes: Declares a small number of useful windows functions, many of which conflict with those declared in "core.sys.windows.windows" (such as PIXELFORMATDESCRIPTOR). However, "SetPixelFormat" is not declared. - derelict.opengl.gl: Has all of opengl plus wgl* functions needed for windows, but has more dependencies than an ideal opengl binding would have. Why isn't there a simple relationship between C/C++ header files and D modules, instead of this weird mix where some things are duplicated and others not declared at all? All of the windows specific functions including wgl* are supposed to be in "windows.h", and opengl functions in "gl/gl.h" It's a shame because I really like the ideas behind D - in fact the reason I found it is that I'd come up with a whole bunch of ideas I wanted in an ideal language and it turned out D already implemented them all...
