www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [Challenge] implementing the ambiguous operator in D

reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
Hey, this question on SO makes for a good challenge:

http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d

The amb operator does this:

amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"])
amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"])
amb(["hello", "very long string"]).length = amb([5, 16])


(I find the guy examples much more comprehensible that the articles he links
to)

Are people interested in trying this?

Peter, can we discuss your solution here?


Philippe
Sep 01 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 1/09/10 9:08 PM, Philippe Sigaud wrote:
 Peter, can we discuss your solution here?
Sure, I'd be interested to hear any improvements. Like I said in my answer, I'm still learning D so I'm sure there's many issues. For example, I made no attempt for const-correctness or anything like that (mostly for simplicity). In particular, I'd be interested in knowing if there's a better way to write opDispatch i.e. a way that doesn't use that ugly mixin.
Sep 01 2010
parent reply Pelle <pelle.mansson gmail.com> writes:
On 09/01/2010 11:49 PM, Peter Alexander wrote:
 On 1/09/10 9:08 PM, Philippe Sigaud wrote:
 Peter, can we discuss your solution here?
Sure, I'd be interested to hear any improvements. Like I said in my answer, I'm still learning D so I'm sure there's many issues. For example, I made no attempt for const-correctness or anything like that (mostly for simplicity). In particular, I'd be interested in knowing if there's a better way to write opDispatch i.e. a way that doesn't use that ugly mixin.
It needs opEquals :-) something like this auto opEquals(E e) { auto cmp = (E a) { return a == e; }; return map!cmp(r); } ... writeln(5 == amb([1,2,3,4,5])); [false, false, false, false, true]
Sep 01 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 2/09/10 7:34 AM, Pelle wrote:
 It needs opEquals :-)
Yeah, it needs a lot of things :) You could easily add unary operators as well (e.g. so that -amb([1, 2]) == [-1, -2]. I didn't bother adding more than I did because it would make the post too large, and wouldn't really add anything (I thought that the binary ops + dispatch covered most of the interesting cases). Also, I think it would supposed to return amb(map!...) instead of just returning map!... (otherwise you couldn't chain them), but that's a simple fix.
Sep 02 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Thu, Sep 2, 2010 at 09:06, Peter Alexander
<peter.alexander.au gmail.com>wrote:

 On 2/09/10 7:34 AM, Pelle wrote:

 It needs opEquals :-)
Yeah, it needs a lot of things :) You could easily add unary operators as well (e.g. so that -amb([1, 2]) == [-1, -2]. I didn't bother adding more than I did because it would make the post too large, and wouldn't really add anything (I thought that the binary ops + dispatch covered most of the interesting cases). Also, I think it would supposed to return amb(map!...) instead of just returning map!... (otherwise you couldn't chain them), but that's a simple fix.
Yes, like Haskell monads: get into, transform, return a wrapped result. Does your code compile for you? I tried it when you posted it on SO and the .length, .replace("a","u") didn't work. I had to change opDispatch from auto opDispatch(string f)() { mixin("return map!((E e) { return e."~f~"; })(r);"); } to: auto opDispatch(string f)() { return map!(unaryFun!("a."~f))(r); } I tried to do the same for the dispatch with arguments, but got very strange errors. DMD told me it couldn't get the args at CT. Oh, but you changed your code on SO. It can know do the first example too. That's good, and was in fact my main subject of interest. Amb seems to be like the product of two ranges (with an operator), which is then flattened. What I don't get is the link with the ruby article and its use of if. Philippe
Sep 02 2010
prev sibling next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Philippe Sigaud" <philippe.sigaud gmail.com> wrote in message 
news:mailman.42.1283371696.858.digitalmars-d puremagic.com...
 Hey, this question on SO makes for a good challenge:

 http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d

 The amb operator does this:

 amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
 amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", 
 "worldqwerty"])
 amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"])
 amb(["hello", "very long string"]).length = amb([5, 16])
Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having "for each element" versions of the operators? Also, "ambiguous" seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an "elementwise" or something. Certainly useful, I had reason to make a similar function once: /// ctfe_subMapJoin("Hi WHO. ", "WHO", ["Joey", "Q", "Sue"]) /// --> "Hi Joey. Hi Q. Hi Sue. " T ctfe_subMapJoin(T)(T str, T match, T[] replacements) if(isSomeString!T) { T value = ""; foreach(T replace; replacements) value ~= ctfe_substitute(str, match, replace); return value; } Though I'll grant that's a questionable name for it. I wasn't sure what else to call it though.
Sep 02 2010
next sibling parent "Nick Sabalausky" <a a.a> writes:
"Nick Sabalausky" <a a.a> wrote in message 
news:i5p68t$2pth$1 digitalmars.com...
 "Philippe Sigaud" <philippe.sigaud gmail.com> wrote in message 
 news:mailman.42.1283371696.858.digitalmars-d puremagic.com...
 Hey, this question on SO makes for a good challenge:

 http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d

 The amb operator does this:

 amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
 amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", 
 "worldqwerty"])
 amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"])
 amb(["hello", "very long string"]).length = amb([5, 16])
Interesting thing, but devil's advocate: What would be the uses/benefits of that versus just having "for each element" versions of the operators? Also, "ambiguous" seems like a rather odd name for what it does. I don't see how ambiguity has anything to do with it. That disconnect made it difficult at first for me to understand what it was. It's more like an "elementwise" or something.
I've been starting at the Ruby page, and I think I'm starting to understand it a little more: Suppose you have two "mostly" unknown values: x and y. Neither you, nor the computer at runtime, know what either of their values actually are. But, you *do* know a finite set of values that they *might* be: auto x = amb([1, 2]); // x is either 1 or 2, but I don't know which auto y = amb([3, 4, 5]); // y is either 3, 4 or 5, but I don't know which assert(x != 2); // Not guaranteed to be == 2 at this point assert(y != 4); // x*y must be one of these values, but I don't know which, it could be any of them: assert(x*y == amb([3, 4, 5, 6, 8, 10]); // Here's the *real* magic (psuedo-syntax): // For some bizarre reason, this means // that x*y must be == 8 (despite the !=) amb(if x*y != 8); // Since x*y has been determined to be 8, // the real values of x and y are now known and // completely unambiguous: assert(x == 2); assert(y == 4);
Sep 02 2010
prev sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Nick Sabalausky (a a.a)'s article
 Interesting thing, but devil's advocate: What would be the
uses/benefits of
 that versus just having "for each element" versions of the
operators? Well the obvious benefit is that you don't have to create all those extra version -- you get them all for free.
 Also, "ambiguous" seems like a rather odd name for what it does.
I don't see
 how ambiguity has anything to do with it. That disconnect made
it difficult
 at first for me to understand what it was. It's more like
an "elementwise"
 or something.
I agree, it's a pretty bad name. I'd call it "all" or something.
Sep 03 2010
prev sibling next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 Hey, this question on SO makes for a good challenge:

 http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d

 The amb operator does this:

 amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
 amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty",  
 "worldqwerty"])
 amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"])
 amb(["hello", "very long string"]).length = amb([5, 16])


 (I find the guy examples much more comprehensible that the articles he  
 links
 to)

 Are people interested in trying this?
Yes, very much so. However, Peter Alexander has misunderstood the ambiguous operator. The idea of amb is to return the combinatorial product of N ranges. if this sounds familiar, it is because it has been discussed at length here earlier, with me and Andrei being the prime contributors (see Combining infinite ranges and Huffman coding comparison). The solution has eluded me for a while, and I have shelved my efforts while doing other things. Perhaps now is the time to revisit it. Peter Alexander seems to have conflated the two concepts of the ambiguous operator and its require()-function. Basically, Amb should be a range of tuples, and you then filter it to retrieve the interesting parts. -- Simen
Sep 03 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article
 Yes, very much so. However, Peter Alexander has misunderstood the
 ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Sep 03 2010
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Sep 3, 2010 at 19:51, Peter Alexander
<peter.alexander.au gmail.com>wrote:

 == Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article
 Yes, very much so. However, Peter Alexander has misunderstood the
 ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Yes, I agree with Peter there. As I said, I personally prefer the examples in the SO OP than the Haskell/Ruby code, if only because the example are easily understood and I find this range combinator useful in some circumstances. What we have here in D is a bit like the List monad in Haskell: a way to represent a bunch of possible values for a computation. If a can 2 or 4 or 6, and b can be 0 or 1 or 2, it makes sense for a*b to among 0,2,4,6,8,12. So thanks, Peter. But does the code compile for you? As I said, here with 2.048, it doesn't. Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does like the Haskell implementation linked in SO does: backtracking on the results to avoid some condition. If someone is up to the challenge of implementing it in D, great! Maybe with closures? I never really thought about it. I guess the D syntax would be auto x = amb([1,2,3]); auto y =amb([4,5,6]); x*y == 8; // forces desambiguation => the ambs explore the possibilities. assert(x == amb([2])); assert(y == amb([4])); There is only one value left, no more ambiguity. Maybe in this case an 'alias possibilities[0] this' could do the trick: assert(x == 2); assert(y == 4); Can we do alias someArray[0] this; ? Philippe Philippe
Sep 03 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 Now, the 'real'/intriguing/mind-bending amb operator (from the 60's) does
 like the Haskell implementation linked in SO does: backtracking on the
 results to avoid some condition. If someone is up to the challenge of
 implementing it in D, great! Maybe with closures? I never really thought
 about it.

 I guess the D syntax would be
 auto x = amb([1,2,3]);
 auto y =amb([4,5,6]);
 x*y == 8; // forces desambiguation => the ambs explore the possibilities.
I believe this will only work with arrays as input. Either that, or I need a way to make this work: struct Foo( R ) if ( isForwardRange!R ) { bool delegate( ElementType!R ) bar; Filter!( bar, R ) range; } Or, well, something like it. I need a static type for a Filter that delegates to a struct member, in this case bar.
 assert(x == amb([2]));
 assert(y == amb([4]));

 There is only one value left, no more ambiguity. Maybe in this case an
 'alias possibilities[0] this' could do the trick:

 assert(x == 2);
 assert(y == 4);

 Can we do alias someArray[0] this; ?
For a simple assert like that, overloading opEquals ought to do the trick, no? -- Simen
Sep 03 2010
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Simen kjaeraas <simen.kjaras gmail.com> wrote:

 I believe this will only work with arrays as input. Either that, or I  
 need
 a way to make this work:

 struct Foo( R ) if ( isForwardRange!R ) {
      bool delegate( ElementType!R ) bar;
      Filter!( bar, R ) range;
 }

 Or, well, something like it. I need a static type for a Filter that
 delegates to a struct member, in this case bar.
I would have thought this'd work, but apparently I'm wrong: module foo; import std.stdio; import std.algorithm; import std.range; struct Foo( R ) if ( isForwardRange!R ) { R range; void delegate( ) _popFront; bool delegate( ) _empty; ElementType!R delegate( ) _front; this( R rng ) { range = rng; _popFront = { range.popFront( ); }; _empty = { return range.empty; }; _front = { return range.front; }; } void attempt( bool delegate( ElementType!R ) dg ) { auto rng = filter!dg( range ); _popFront = { rng.popFront( ); }; _empty = { return rng.empty; }; _front = { return rng.front; }; } void popFront( ) { _popFront( ); } property bool empty( ) { return _empty( ); } property ElementType!R front( ) { return _front( ); } } Foo!R bar( R )( R rng ) if ( isForwardRange!R ) { return Foo!R( rng ); } void main() { auto b = bar( [1,2,3] ); foreach ( e; b ) { writeln( e ); } } Output: 1 object.Error: Access Violation -- Simen
Sep 03 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, Sep 4, 2010 at 01:40, Simen kjaeraas <simen.kjaras gmail.com> wrote:

 Simen kjaeraas <simen.kjaras gmail.com> wrote:

  I believe this will only work with arrays as input. Either that, or I need
 a way to make this work:

 struct Foo( R ) if ( isForwardRange!R ) {
     bool delegate( ElementType!R ) bar;
     Filter!( bar, R ) range;
 }

 Or, well, something like it. I need a static type for a Filter that
 delegates to a struct member, in this case bar.
Maybe with a dynamic filter? struct DynamicFilter(R) if (isInputRange!R) { R range; bool delegate(ElementType!R) predicate; bool set; this(R _range) { range = _range; } this(R _range, bool delegate(ElementType!R) _predicate) { range = _range; predicate = _predicate; set = true; popFront(); } void setPredicate(bool delegate(ElementType!R) _predicate) { predicate = _predicate; set = true; popFront();} ElementType!R front() { if (set) { return range.front();} else { throw new Exception("Calling DynamicFilter with an unset predicate.");};} bool empty() { if (set) {return range.empty;} else { throw new Exception("Calling DynamicFilter with an unset predicate.");};} void popFront() { if (set) { while( !range.empty && !predicate(range.front)) { range.popFront(); } } else { throw new Exception("Calling DynamicFilter with an unset predicate."); } } } //DynamicFilter!(R) dynamicFilter(R)(R range) //{ // return DynamicFilter!R(range); //} DynamicFilter!(R) dynamicFilter(R,E)(R range, bool delegate(E) pred = null) if ((isInputRange!R) && is(ElementType!R == E)) { if (pred is null) return DynamicFilter!(R)(range); else return DynamicFilter!R(range, pred); } void main() { auto f = dynamicFilter([0,1,2,3], (int i) { return i%2 == 0;}); writeln(f.front); // 0 f.setPredicate((int i) { return i%2 == 1;}); writeln(f.front); // 1 } Note that in this version, the filtered range always advances. When you change filter, it continues to consume elements from the current point. For backtracking, maybe you need a forward range input, a saved version of this input, and have setPredicate rewind the inner range to the saved version. Philippe
Sep 03 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 I guess the D syntax would be
 auto x = amb([1,2,3]);
 auto y =amb([4,5,6]);
 x*y == 8; // forces desambiguation => the ambs explore the possibilities.
 assert(x == amb([2]));
 assert(y == amb([4]));

 There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left? That's one of the reasons I feel that doing the combination, then filtering it, is more correct. There is also the fact that the above syntax does not let you call arbitrary functions in the requirements, something filter does.
 Maybe in this case an
 'alias possibilities[0] this' could do the trick:

 assert(x == 2);
 assert(y == 4);

 Can we do alias someArray[0] this; ?
Well, we can do this: struct foo( R ) { R range; ref ElementType!R getFront( ) { return range.front; } alias getFront this; } -- Simen
Sep 05 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas <simen.kjaras gmail.com> wrote:

 Philippe Sigaud <philippe.sigaud gmail.com> wrote:

  I guess the D syntax would be
 auto x = amb([1,2,3]);
 auto y =amb([4,5,6]);
 x*y == 8; // forces desambiguation => the ambs explore the possibilities.
 assert(x == amb([2]));
 assert(y == amb([4]));

 There is only one value left, no more ambiguity.
But what happens in the case where there is more than one value left?
If I understand correctly the linked Ruby and Haskell versions, the search stops as soon as you find a possibility. But then, I'm no pro on this.
 That's one of the reasons I feel that doing the combination, then
 filtering it, is more correct. There is also the fact that the above
 syntax does not let you call arbitrary functions in the requirements,
 something filter does.
The combining and filtering is interesting (in this case, it'd be like doing a list comprehension). But the real challenge in the SO question is the 'going back in time' part, which I have trouble to understand : how can you modify x and y through a multiplication and a comparison? I did a range comprehension maybe one year ago, which would be partially equivalent to the problem: auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]); solution is a range, in this case a one element range, containing only [2,4]. Philippe
  Maybe in this case an
 'alias possibilities[0] this' could do the trick:

 assert(x == 2);
 assert(y == 4);

 Can we do alias someArray[0] this; ?
Well, we can do this: struct foo( R ) { R range; ref ElementType!R getFront( ) { return range.front; } alias getFront this; } -- Simen
Sep 05 2010
next sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:

 But the real challenge in the SO question is the 'going back in time'  
 part,
 which I have trouble to understand : how can you modify x and y through a
 multiplication and a comparison?
It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html
Sep 05 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
2010/9/5 Denis Koroskin <2korden gmail.com>

 On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud <
 philippe.sigaud gmail.com> wrote:

  But the real challenge in the SO question is the 'going back in time'
 part,
 which I have trouble to understand : how can you modify x and y through a
 multiplication and a comparison?
It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html
How can we access setjmp/longjmp in D? Anyway, I'm a bit nervous with using such a raw statement. An oh-so-slightly wrapped equivalent for D would be better. Philippe
Sep 05 2010
parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 05 Sep 2010 18:24:43 +0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:

 2010/9/5 Denis Koroskin <2korden gmail.com>

 On Sun, 05 Sep 2010 16:59:31 +0400, Philippe Sigaud <
 philippe.sigaud gmail.com> wrote:

  But the real challenge in the SO question is the 'going back in time'
 part,
 which I have trouble to understand : how can you modify x and y  
 through a
 multiplication and a comparison?
It can be done using setjmp/longjmp, see C implementation for an example: http://homepage.mac.com/sigfpe/Computing/continuations.html
How can we access setjmp/longjmp in D? Anyway, I'm a bit nervous with using such a raw statement. An oh-so-slightly wrapped equivalent for D would be better. Philippe
It is available after the following import: import core.sys.posix.setjmp; It is not defined on Windows, but I believe you can use the following declaration with dmd (works for ddmd): version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } Some documentation: http://en.wikipedia.org/wiki/Setjmp.h Use the following struct (or make it a class) if you prefer OOP style: struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } import std.stdio; void main() { State state; int result = state.save(); if (result == 0) { // first time here writeln("state saved"); state.restore(1); } else { assert(result == 1); writeln("state restored"); } } The code above should print: state saved state restored (not tested)
Sep 05 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Denis Koroskin:
 The code above should print:
 state saved
 state restored
 
 (not tested)
On Windows, dmd 2.048, this code: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } void main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } } Gives an Access Violation after printing state saved. Bye, bearophile
Sep 05 2010
parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 05 Sep 2010 19:17:55 +0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 Denis Koroskin:
 The code above should print:
 state saved
 state restored

 (not tested)
On Windows, dmd 2.048, this code: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } void main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } } Gives an Access Violation after printing state saved. Bye, bearophile
Turn main into an "extern(C) int main()" and it works. Surround the code with try/catch block and it fails again. Looks like longjmp fails if you run the function inside a try/catch block for some reason.
Sep 05 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Denis Koroskin:
 Turn main into an "extern(C) int main()" and it works.
This version: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } extern(C) int main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } return 0; } Gives link errors: test.obj(test) Error 42: Symbol Undefined __d_assertm test.obj(test) Error 42: Symbol Undefined __d_assert_msg Bye, bearophile
Sep 05 2010
parent "Denis Koroskin" <2korden gmail.com> writes:
On Sun, 05 Sep 2010 20:18:13 +0400, bearophile <bearophileHUGS lycos.com>  
wrote:

 Denis Koroskin:
 Turn main into an "extern(C) int main()" and it works.
This version: import std.c.stdio: puts; version (Windows) { alias int[16] jmp_buf; extern (C) extern { int setjmp(ref jmp_buf env); void longjmp(ref jmp_buf env, int value); } } struct State { int save() { return setjmp(buf); } void restore(int status) { assert(status != 0); longjmp(buf, status); } private jmp_buf buf; } extern(C) int main() { State state; int result = state.save(); if (result == 0) { // first time here puts("state saved"); state.restore(1); } else { assert(result == 1); puts("state restored"); } return 0; } Gives link errors: test.obj(test) Error 42: Symbol Undefined __d_assertm test.obj(test) Error 42: Symbol Undefined __d_assert_msg Bye, bearophile
Try linking with phobos explicitly:
Sep 05 2010
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/05/2010 07:59 AM, Philippe Sigaud wrote:
 On Sun, Sep 5, 2010 at 12:00, Simen kjaeraas <simen.kjaras gmail.com
 <mailto:simen.kjaras gmail.com>> wrote:

     Philippe Sigaud <philippe.sigaud gmail.com
     <mailto:philippe.sigaud gmail.com>> wrote:

         I guess the D syntax would be
         auto x = amb([1,2,3]);
         auto y =amb([4,5,6]);
         x*y == 8; // forces desambiguation => the ambs explore the
         possibilities.
         assert(x == amb([2]));
         assert(y == amb([4]));

         There is only one value left, no more ambiguity.


     But what happens in the case where there is more than one value left?


 If I understand correctly the linked Ruby and Haskell versions, the
 search stops as soon as you find a possibility. But then, I'm no pro on
 this.


     That's one of the reasons I feel that doing the combination, then
     filtering it, is more correct. There is also the fact that the above
     syntax does not let you call arbitrary functions in the requirements,
     something filter does.


 The combining and filtering is interesting (in this case, it'd be like
 doing a  list comprehension).
 But the real challenge in the SO question is the 'going back in time'
 part, which I have trouble to understand : how can you modify x and y
 through a multiplication and a comparison?

 I did a range comprehension maybe one year ago, which would be partially
 equivalent to the problem:

 auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]);

 solution is a range, in this case a one element range, containing only
 [2,4].
Here we need to have a crossProduct range, as we discussed in the thread "Combining infinite ranges". Then it's easy to combine it with filter: auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6])); Andrei
Sep 05 2010
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 equivalent to the problem:
 auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]);

 solution is a range, in this case a one element range, containing only
 [2,4].
I did a range comprehension maybe one year ago, which would be partially Here we need to have a crossProduct range, as we discussed in the thread "Combining infinite ranges". Then it's easy to combine it with filter: auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6]));
Not exactly: crossProduct is a range, and the only element type that makes sense is Tuple!(A,B). Unless of course you're interested in adding binary predicates to filter, which would be understood as automatically opening tuples (and of course, would statically check the length of the tuple and the arity of the passed function). I can add this to Phobos. What you call crossProduct can be seen as zipWith!tuple(range, range2), which If there is interest in this, I also suggest having a n-range version of map that takes a n-ary function and maps them in parallel. auto m = map!"a < b ? a : c"(range1, range2, range3); OK, I definitely need to take some time to assemble all this and propose it for a formal Phobos review. I'll bump it up higher in my TODO list. Philippe Philippe
Sep 05 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/05/2010 09:30 AM, Philippe Sigaud wrote:
 On Sun, Sep 5, 2010 at 15:56, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>>
 wrote:


         equivalent to the problem:

         auto solution = comp!("[a,b]", "a*b == 8")([1,2,3], [4,5,6]);

         solution is a range, in this case a one element range,
         containing only
         [2,4].

     I did a range comprehension maybe one year ago, which would be partially

     Here we need to have a crossProduct range, as we discussed in the
     thread "Combining infinite ranges". Then it's easy to combine it
     with filter:

     auto solutions = filter!"a*b == 8"(crossProduct([1,2,3], [4,5,6]));


 Not exactly: crossProduct is a range, and the only element type that
 makes sense is Tuple!(A,B).
 Unless of course you're interested in adding binary predicates to
 filter, which would be understood as automatically opening tuples (and
 of course, would statically check the length of the tuple and the arity
 of the passed function). I can add this to Phobos.
Oh indeed. I think it's not onerous to require the client to write: auto solutions = filter!"a._0*a._0 == 8"(crossProduct([1,2,3], [4,5,6]));
 What you call crossProduct can be seen as zipWith!tuple(range, range2),
 which
Yah, per your follow-up post, it's a different problem. It's also a much more difficult one. I convinced myself crossProduct is impossible to implement if one input range and one infinite forward range are simultaneously present. It works with any number of infinite forward ranges, and also with other combinations. I couldn't formalize the exact requirements yet.
 If there is interest in this, I also suggest having a n-range version of
 map that takes a n-ary function and maps them in parallel.

 auto m = map!"a < b ? a : c"(range1, range2, range3);

 OK, I definitely need to take some time to assemble all this and propose
 it for a formal Phobos review. I'll bump it up higher in my TODO list.

 Philippe
Yah, definitely. Note that I have a functioning Zip in my upcoming commit to std.range. Andrei
Sep 05 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Andrei Alexandrescu
 Yah, per your follow-up post, it's a different problem. It's
also a much
 more difficult one. I convinced myself crossProduct is
impossible to
 implement if one input range and one infinite forward range are
 simultaneously present. It works with any number of infinite
forward
 ranges, and also with other combinations. I couldn't formalize
the exact
 requirements yet.
I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Sep 06 2010
next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Peter Alexander <peter.alexander.au gmail.com> wrote:

 I must be missing something, because I don't understand how you
 could possibly take the cross product of any number of infinite
 ranges (other than to just return the range of (a[0], b[i]) for
 all (infinitely many) i in b).

 Note that I'm assuming you mean cartesian product, rather than
 cross product; I've never heard cross product used in the context
 of sets.
Quite simple - the result is also an infinte range (infinitely infinite, if you will :p ), that is lazily calculated. And yes, Cartesian product is exactly what we're talking about. -- Simen
Sep 06 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/06/2010 06:51 AM, Peter Alexander wrote:
 == Quote from Andrei Alexandrescu
 Yah, per your follow-up post, it's a different problem. It's
also a much
 more difficult one. I convinced myself crossProduct is
impossible to
 implement if one input range and one infinite forward range are
 simultaneously present. It works with any number of infinite
forward
 ranges, and also with other combinations. I couldn't formalize
the exact
 requirements yet.
I must be missing something, because I don't understand how you could possibly take the cross product of any number of infinite ranges (other than to just return the range of (a[0], b[i]) for all (infinitely many) i in b). Note that I'm assuming you mean cartesian product, rather than cross product; I've never heard cross product used in the context of sets.
Yah, thanks for the correction. But probably ranges could be easier seen as vectors than as sets. We've discussed this before. Crosscartesian product of multiple infinite ranges can be easily done by applying Cantor's trick for proving that rational numbers are just as numerous than natural numbers. Google for "Cantor" with "site:digitalmars.com". Andrei
Sep 06 2010
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 We've discussed this before. Crosscartesian product of multiple infinite
 ranges can be easily done by applying Cantor's trick for proving that
 rational numbers are just as numerous than natural numbers. Google for
 "Cantor" with "site:digitalmars.com".
 Andrei
Thanks. For some reason I had just assumed that we would have wanted to provide the product in lexicographic order, but Cantor's trick does seem like a solution to this problem.
Sep 06 2010
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
Peter:
        I must be missing something, because I don't understand how you
        could possibly take the cross product of any number of infinite
        ranges (other than to just return the range of (a[0], b[i]) for
        all (infinitely many) i in b).


The trick is to iterate diagonally. Me, I'll use tensorial product :p
Say you have: [0,1,2,...] x [0,1,2,...]

The tensorial product produces a range of ranges:
[[(0,0),(0,1),(0,2),(0,3),...
,[(1,0),(1,1),(1,2), ...
,[(2,0),(2,1),...
...
]

The standard cartesian product just iterates in the first line and will try to
explore an infinite row.
The trick is to iterate along the secondary diagonals, like this:

0 1 3 6
2 4 7
5 8
9

Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ..
See the indices: sum of 0, then sum of 1, then sum of 2, ...
You never get stuck in an infinite line since these diagonal slices are finite.


Andrei:
    We've discussed this before. Crosscartesian product of multiple infinite
ranges can be easily done by applying Cantor's trick for proving that rational
numbers are just as numerous than natural numbers. Google for "Cantor" with
"site:digitalmars.com".



Ok, I think I solved this particular problem, if only for infinite ranges.
It's in three parts:

1- A memorize(range) struct that slowly looks ahead in a range, store the result
in an internal array and so slowly transforms an input range into a
random-access
range. I tried this a few months ago, but got stuck in trying to propagate
properties (bidirectional, etc). Now it's just an input range. Much easier. It's
related to Zippers (in functional PL).
2- Generate the indices of sum  = 0, then sum = 1, then sum = 2; etc.
3- Just take the corresponding indices in the input ranges.

example:
a = memorize(cycle([0,1,2,3,4])); // to make it infinite.
auto dp = diagonalProduct(a,a,a);
 // -> (0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,0,2),(0,1,1), ...


entire source code attached (I hope it works). Now, I still have some problems
with finite ranges in the mix. Nothing crucial, but it's getting late.

Philippe
begin 644 infiniteproduct.zip


MR\4$D6LYV=SY.4X46E/0'\;$NE=Y1'>V&CS9("2\! !EJ,\,!`=03^6,.%6X

MKG%A_`W^>VCP`5!+`P04````"`#RNB8]=*T:)9\'``!,10``"0```'!R;V1U

M(K^]M]>9G?7LQ\V<UZY:]6'DN[W=V?G>V=GUDR=/+BJXK&!8P4T%DPK*" KX



M63QDHYL+\B%=CI$6E+\=2[3=PAP3D&DIX!^?KQV>[PTO\.TCC+D)ZX%HL&VD
MN]NZG>8X,0!MLQH(QZ6/S]<SM`]C^D[(8>;*`IX_5-"MX$4%&S _VG*#SB_!



M?O4'M,UL?[+1L7F.V.F>(_L'Y[E \!K7#NM_9"O[N&8Q' 85'$36\WY`IK\S
M'_/Y)![+ +WO&AJ0#JL'\I--EW^`7H+G/8>6&XS#C/=^>#S%2[0/M,^H7Y"=
M/0CF-=]WS&\BMWE$VA(T'CNRF-1MI*<K)Q_I.O3]"-^N,=:R6'2_P`?1/G?X
MF4;LHN?-3_B^-B"031`'RB2SC9MQ(Y0%]E^AO+IF;H7<D(8?XO+VZ8>^WPEE
M[8T7R/H6^H\=W[YRY/-S9IG6\7I)&3[$9"B _6]YD']-,(XI?%XSC\3WMPG\
MO!;7*I8'3*']3IC7VC HV-O%\MH+OK;!;\G:1A:?GP^_=?,Q9DO'!A<;7RZN
M-Y3CLW6YI[1Q25ZHM?/ _.GUG""D$VC[7,&.T"Z]&!!9XS^8?AG6<BE?)QG\

MG<VK:+WNIOR=YP_0YV4%WQBZ%'-KZ+2 D"7Z?G^)>;8`IDH\CTO:^D(NJ8S!
MZXISJ=RJ(X 77GZP AB!-C%A<B $,HKZ=](__?C_UN']%.-6"YU)\]I03C4)

MQEAF(92/-\A^QT`F^4^P+L-JZ6<8,^&]]&K/M/9->+UTC>M94(_"O&NDS+5R
MZW?!#RP?)/^.^<9D^WZ-LD5[VVII;QI9<C RNN.U?[;V%<*]P3)T)'-SFW?Z
MM&T:^67(HZ+VS>=< TW;;\&US\\AAKA'13UB7T$=W5T++Q0U=VE],V==7E*[
M#NI1


M/0G/W8PVMT!/BHYX[*3Q=F]`=O!"8<<I6QA$:#J(Z5:Q%FED\U_3U<L6>M+0
M9^7EUO/Q3%60GS3L<VFLHD8W=NVTX8[+L7.WX#SCOEHJ0QY?9]!^Y.Z]&O 8
M0(VQ!_`5X/T6\'XV<HF.]?L_;YG;:G-ZB7]!;N3+C/S)EUD+VA?.9:Q-4#VJ
M9'6>?HB_->[=I/:UZ)M4"Y Y=!\[O`U='7&^\<P&XXW"KW"?6;2T+0OI6$-G
M2BWXUM"CJ0T\-R"(9X\MUTY)W'T4WNG<!UF=+^3[_GVO$3[CNIN\\^G?'1NR
M^M0G X?=13MML7<91^K8PX6[7C3VV)GO*>81,,\IYGT46^C^'.X=V+GMTR7N

M[J[M\[O62`_IC^ &';R#MBOLJSP;J/?'C(>BQ7EQD"<EW8EZA4\K/?L^'Z,U




M)'*6V+C]'LN!,MZ)SK&F1>E3QK1UKXV%$D;.&>38\9FA&\L%_QO L7\ C-%8
MYSIPQZ_XWD;0%X3Z_:?OIN>P;8E>EKWC6 CN)$EH\.+MFGUCU;Z[BEB?E+W0
M?WL-=S`W5D#G,KHJ!#XOX;GM7=M<,GA<`<YE\Z!"H;=<."T(<I3 WDJ1)RX+
MWKYM1?-JUKB<8Y\;4-1;"H$NI__"O9M&ILE[5TO6A3O\/\N"&G>;.G/3O:S9

M`"````!!<F-H:79E(&-R96%T960 8GD 9G)E92!J6FEP+G5R;%M);G1E<FYE
M=%-H;W)T8W5T70T*55),/6AT='`Z+R]W=W<N:GII<"YC;VTO87)C:&EV95]L

M````````;6%I;BYD4$L!`A0`%````` `\KHF/72M&B6?!P``3$4```D`````
M``````` ````O ```'!R;V1U8W0N9%!+`0(4``H``````(EIB3A&_<=>. ``
M`#H```` ````````````(````(0(``!!<F-H:79E(&-R96%T960 8GD 9G)E

`
end
Sep 06 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/06/2010 04:34 PM, Philippe Sigaud wrote:
 Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ..
 See the indices: sum of 0, then sum of 1, then sum of 2, ...
 You never get stuck in an infinite line since these diagonal slices are finite.
I don't think iteration for constant index sums works with forward ranges - you need bidirectional ranges to go back in one while going forth in another. You need to only move forward in all ranges, or reset them to zero. It helps me a lot to think how I'd lay bricks to fill the first quadrant of an n-dimensional infinite space. If you tried the tensorial product, you'd lay a nice column of bricks, but you'd be busy at it forever because the column would have infinite "height". If you try your solution that has constant sums, then you are filling hypersimplexes of increasing size. That's certainly encouraging because it fills the space quite nicely, but again it requires bidirectional ranges. My solution is to fill hypercubes of increasing size from origin. One hypercube of size k is built by adding a layer of bricks on a hypercube of size k - 1. That can be done with forward iterators, and in fact is not all that difficult.
 Andrei:
      We've discussed this before. Crosscartesian product of multiple infinite
 ranges can be easily done by applying Cantor's trick for proving that rational
 numbers are just as numerous than natural numbers. Google for "Cantor" with
 "site:digitalmars.com".



 Ok, I think I solved this particular problem, if only for infinite ranges.
 It's in three parts:

 1- A memorize(range) struct that slowly looks ahead in a range, store the
result
 in an internal array and so slowly transforms an input range into a
random-access
 range. I tried this a few months ago, but got stuck in trying to propagate
 properties (bidirectional, etc). Now it's just an input range. Much easier.
It's
 related to Zippers (in functional PL).
 2- Generate the indices of sum  = 0, then sum = 1, then sum = 2; etc.
 3- Just take the corresponding indices in the input ranges.
I don't think this is a good solution. Andrei
Sep 06 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
I agree with Andrei here, building hypercubes makes more sense, and feels like
it has more structure. It
also has the nice property that, once you've seen a (n+1)th element of any
range then you have already
explored the entire product of the first n elements of every range, kind of
like how the colex ordering
works.

But which way would you add the successive "shells"?

Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order?

btw, what are some real-world uses of the cartesian product of infinite ranges?
I can't think of any off
the top of my head.
Sep 07 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 09/07/2010 02:43 AM, Peter Alexander wrote:
 I agree with Andrei here, building hypercubes makes more sense, and feels like
it has more structure. It
 also has the nice property that, once you've seen a (n+1)th element of any
range then you have already
 explored the entire product of the first n elements of every range, kind of
like how the colex ordering
 works.

 But which way would you add the successive "shells"?

 Like this?: (00) (01 10 11) (02 12 20 21 22)... i.e. lex order?
The algorithm builds one hyperplane at a time. At level k, there are n hyperplanes to build, each of which keeps exactly one range positioned on the kth element, and all others iterate from their first up to their kth element. Whenever you reached the corner of the hypercube (all ranges are at the kth position), you start building the next hyperplane. When all other hyperplanes are built, you popFront() the first range, reset all others, and start building the next shell.
 btw, what are some real-world uses of the cartesian product of infinite
ranges? I can't think of any off
 the top of my head.
It's great for various solution-searching algorithms, like the example given (lazily generate solutions to the equation x * y = 8). Even for finite ranges of moderate size, exploring two iota()s in the naive order (keep one fixed and exhaust all others) most often takes a long time to find anything interesting. That's why I think finding a solid method to iterate the cartesian product is important even for finite ranges. Andrei
Sep 07 2010
prev sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:
 I convinced myself crossProduct is impossible to implement if one input  
 range and one infinite forward range are simultaneously present. It  
 works with any number of infinite forward ranges, and also with other  
 combinations. I couldn't formalize the exact requirements yet.
This is indeed correct. Now, I have found a working algorithm (it works on paper, I swear!), but I can't seem to get it to work in code. Special cases come for input ranges - I will not consider those. All forward ranges can be treated the same, regardless of infiniteness. We need to keep track of the active ranges, and the initial versions of those (i.e. those passed to the constructor). In addition, we need to keep the position of each range, probably as a ulong (2 ranges should give 2^128 combinations, which will not cover the whole solution space for infinite ranges, but will still be enough for practical purposes). Also, we must maintain a stack of locked ranges. The solution is recursive to the number of ranges, and is given in pseudocode below. Critique is very, VERY welcome! bool movedEnough( lastUnlocked, lockedStack.peek ) { if ( lastUnlocked.empty ) { // If range is empty, don't pop stuff off of it. return true; } else if ( lastUnlocked > lockedStack.peek ) { // If the last unlocked range has a higher index than // the next one the locked stack, check if popping // would bring us past its position. return pos[lastUnlocked] >= pos[lockedStack.peek]; } else { // If the last unlocked range has a lower index than // the next one the locked stack, check if popping // would bring us to its position. return pos[lastUnlocked] >= pos[lockedStack.peek] -1; } } void popFront( ) { if ( !unlockedRanges.empty ) { // If there are unlocked ranges, use the first of them currentRange = unlockedRanges[0]; } else { // No unlocked ranges, so unlock one. currentRange = lastUnlocked = lockedStack.pop; unlock( lastUnlocked ); while ( movedEnough( lastUnlocked, lockedStack.peek ) ) { // We have moved far enough along this range, move the next one up. currentRange = lastUnlocked = lockedStack.pop; unlock( lastUnlocked ); if ( // If there are more unlocked ranges below this one ( lastUnlocked != unlockedRanges[$] ) || // Or there are no more locked ranges ( lockedStack.empty ) ) { // Move to the next range. Note that firstAfter would need to return 0 on being passed $. currentRange = unlockedRanges.firstAfter( lastUnlocked ); // We have found the next range from which to pop. break; } } } // Pop off the found range, the lock it, and reset all unlocked ranges to their saved states. currentRange.popFront(); lock(currentRange); foreach ( unlockedRanges ) { reset(); } } Given cartesian( [1,2], "ab" ), the result should be as follows: tuple( 1, 'a' ); tuple( 2, 'a' ); tuple( 2, 'b' ); tuple( 1, 'b' ); And for cartesian( [1,2,3], "abc" ): tuple( 1, 'a' ); tuple( 2, 'a' ); tuple( 2, 'b' ); tuple( 1, 'b' ); tuple( 3, 'a' ); tuple( 3, 'b' ); tuple( 3, 'c' ); tuple( 1, 'c' ); tuple( 2, 'c' ); -- Simen
Sep 06 2010
next sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Simen kjaeraas <simen.kjaras gmail.com> wrote:

 Special cases come for input ranges - I will not consider those. All
 forward ranges can be treated the same, regardless of infiniteness.
Actually, input ranges make everything a lot easier - the best solution is the brute-force stupid solution. -- Simen
Sep 06 2010
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Attached latest version. It bugs out with an infinite loop, and I'm too
tired to look more at it now.

-- 
Simen
Sep 06 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, Sep 5, 2010 at 16:30, Philippe Sigaud <philippe.sigaud gmail.com>wrote:

 What you call crossProduct can be seen as zipWith!tuple(range, range2),
 which
Scratch that. zipWith *is* mapping on n ranges in parallel.
Sep 05 2010
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Philippe Sigaud <philippe.sigaud gmail.com> wrote:

 But the real challenge in the SO question is the 'going back in time'  
 part,
 which I have trouble to understand : how can you modify x and y through a
 multiplication and a comparison?
I believe this to be possible, though horrible and unpleasant. Basically, binary operations on Amb ranges create a new, temporary type. This type keeps track of which ranges have been involved in the operation thus far, and which operations, and at the end gives each Amb a bool delegate( ElementType!Amb ) that has a heap copy of each other range and evaluates the operations on each. However, this solution may lead to inconsistent state in the combination of ranges. Another solution is for each Amb to keep track of a 'controller', which keeps track of the constraints given. This controller would be a combinatorial product of references to the ranges involved. Any call to popFront on the Amb ranges would delegate to the controller's popFront, which would update the involved ranges. Due to the unknowability of the number and type of ranges involved, this controller would need to be a class. I believe, but cannot prove, that only one constraint (i.e. one set of operations) would be feasible to keep track of in such a system, and thus the following would not work: auto a = amb( [1,2,3] ); auto b = amb( [1,3,6] ); auto c = amb( [3,6,9] ); a * b = 6; a * c = 9; assert( a == 1 ); assert( b == 6 ); assert( c == 9 ); A system based around the combinatorial range as a stand-alone, and using filter(s) could easily do the equivalent, but would be limited in that it would only yield one range unless given reference semantics. In the latter case, it would function much like above, except the controller would be a known type that the programmer him- or herself would need to manage. Another problem of the first system is that it has no support for conditionals. -- Simen
Sep 05 2010
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Peter Alexander <peter.alexander.au gmail.com> wrote:

 == Quote from Simen kjaeraas (simen.kjaras gmail.com)'s article
 Yes, very much so. However, Peter Alexander has misunderstood the
 ambiguous operator.
Hey, I was just going by what the guy posted :) He mentioned nothing of tuples, and his examples certainly didn't show any tuples.
Sorry, yes. Copied the wrong name off of the OP on SO. Should have said chrisdew, not Peter Alexander. -- Simen
Sep 03 2010
prev sibling parent reply Justin Johansson <no spam.com> writes:
On 02/09/10 05:38, Philippe Sigaud wrote:
 Hey, this question on SO makes for a good challenge:

 http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d
It's great to see someone doing the first D discussion topic with the [challenge] annotation. Bearophile, if you are reading this perhaps you might like to repost some of you previous "challenges" which have not received much attention with the [challenge] annotation in the subject line. I hope this idea of annotating ng discussion topics with their genre, say [challenge] or [trick], or perhaps [typesystem] or whatever takes on as much as [OT] threads seem to :-) Cheers Justin Johansson
Sep 03 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Justin Johansson:
 Bearophile, if you are reading this perhaps you might like
 to repost some of you previous "challenges" which have not
 received much attention with the [challenge] annotation in
 the subject line.
See: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=116505 Bye, bearpophile
Sep 03 2010
parent reply Don <nospam nospam.com> writes:
bearophile wrote:
 Justin Johansson:
 Bearophile, if you are reading this perhaps you might like
 to repost some of you previous "challenges" which have not
 received much attention with the [challenge] annotation in
 the subject line.
See: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=116505 Bye, bearpophile
That's not a very useful problem, because the timing depends entirely on BigInt, which is completely unoptimised for small values.
Sep 03 2010
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Don (nospam nospam.com)'s article
 That's not a very useful problem, because the timing depends entirely on
 BigInt, which is completely unoptimised for small values.
True, but it would be nice to get it as concise as Haskell's. In an ideal world, we'd simply write it as: auto H() { return chain([BigInt(1)], setIntersection(map!"2*a"(H()), map!"3*a"(H()), map!"5*a"(H()))); } BigInt hamming(int limit) { return H().at(limit); } But the unfortunately, due to D's type system, you cannot have recursive types (H's type depends on its own type). You should be able to get around this by introducing a "abstract range wrapper". I'll see what I can come up with.
Sep 03 2010
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Don:
 That's not a very useful problem, because the timing depends entirely on 
 BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used. The Haskell version of the program is quite fast, very short, and it's lazy so it uses very low memory. The "Alternate version using "Cyclic Iterators"" Python version invented by the great Raymond Hettinger too is lazy and uses very low memory. On the other hand, that D version, that I have translated from the Java code, is eager so it uses a lot of memory, is slow (mostly because of the bigint implementation, I agree), and its source is many lines long. So D must do better along one or more than one of those axis. This huge thread shows that this is a very interesting problem, and solving it well is important for a language like that D that wants to support lazy iterables a lot in its standard library, and wants to be able to express code at a high level too (this means short programs): http://lambda-the-ultimate.org/node/608 Bye, bearophile
Sep 03 2010
next sibling parent reply Don <nospam nospam.com> writes:
bearophile wrote:
 Don:
 That's not a very useful problem, because the timing depends entirely on 
 BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used.
Well, I would hate for somebody to waste their time trying to optimise that problem either for speed or memory consumption, when both are limited by a fairly simple, short-term library issue. Lines of code, sure.
Sep 03 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Don:
 Well, I would hate for somebody to waste their time trying to optimise 
 that problem either for speed or memory consumption, when both are 
 limited by a fairly simple, short-term library issue.
What is the short-term Phobos issue that limits the memory usage? In the current Phobos2 I have not found any easy-to-use mean to transform that eager D version into a lazy version that uses about 1/10 of the memory it currently uses (s in the second Python version). Bye, bearophile
Sep 03 2010
prev sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Sep 3, 2010 at 21:43, bearophile <bearophileHUGS lycos.com> wrote:

 Don:
 That's not a very useful problem, because the timing depends entirely on
 BigInt, which is completely unoptimised for small values.
You are usually right, but this time what you say is useless. There are other means to judge how good a program is, beside running time: - Total line count of the program; - Max amount of memory used. The Haskell version of the program is quite fast, very short, and it's lazy so it uses very low memory.
It's crystal clear & short (but we should aim for J! :-), but being lazy I don't see how it can use less memory than a strict version of the same algo. Got to store all those thunks somewhere.
 The "Alternate version using "Cyclic Iterators"" Python version invented by
 the great Raymond Hettinger too is lazy and uses very low memory. On the
 other hand, that D version, that I have translated from the Java code, is
 eager so it uses a lot of memory, is slow (mostly because of the bigint
 implementation, I agree), and its source is many lines long. So D must do
 better along one or more than one of those axis.
What did you use to compare them? (out of curiosity, not attack). I used GHCi, and got 8.8s for the millionth Hamming number, using ~450 Mo of RAM, according to GHCi itself (:set +s, :set +t). But I'm no pro in optimizing Haskell compilation. For my own D version, that is quite near the Rosetta Code version, I get 3.7s, 100 Mo of RAM. (-O -release -inline) Using the RC code (your own, translated from Java, right?), I get the same. Same result, same time, same memory consumption. Yeah, my code is not wrong :-) So, at least naively like this for me, D is more than twice as fast as Haskell and uses about 80% less memory. Of course, GHC caches results, so the second time I ask for the millionth Hamming number, I get it almost instantaneously. Nifty, that! Philippe
Sep 04 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:

It's crystal clear & short (but we should aim for J! :-), but being lazy I
don't see how it can use less memory than a strict version of the same algo.
Got to store all those thunks somewhere.<
I have appreciated how the Haskell version allows me to generate a sequence lazily in a recursive way, with a compact syntax and efficiently. But I don't know Haskell, so it's easy for what I say about Haskell programs to be false :-)
 What did you use to compare them? (out of curiosity, not attack).<
 I used GHCi, and got 8.8s for the millionth Hamming number, using ~450 Mo of
 RAM, according to GHCi itself (:set +s, :set +t). But I'm no pro in
 optimizing Haskell compilation.
For the Python and D programs I have used woerking memory & commit on Windows, for the Haskell version I have used Ideone: http://ideone.com/wH1YU It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.
 For my own D version, that is quite near the Rosetta Code version, I get
 3.7s, 100 Mo of RAM. (-O -release -inline)
 Using the RC code (your own, translated from Java, right?), I get the same.
 Same result, same time, same memory consumption. Yeah, my code is not wrong :-)
On my very slow PC using DMD the D version requires about 2.7s and about max 92 MB of memory. The second Python version (the one by Hettinger) takes about 4.95s and less than 4.5 MB of memory. (The third Python version, that uses the eager array and Psyco is faster.) Are you able to write a short D version similar to the second Python version? (I have created one, but it's not as short as the second Python version, and it takes something like 4 seconds or more). Bye, bearophile
Sep 04 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sat, Sep 4, 2010 at 23:55, bearophile <bearophileHUGS lycos.com> wrote:

 It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.
OK, so that may the difference between GHCi and GHC proper. Less than 1s is impressive. I see I have GHC 6.12.3 on my system. I may give this code a try one day. I tend to do most (if not all) of my Haskell 'dips' with GHCi.
 For my own D version, that is quite near the Rosetta Code version, I get
 3.7s, 100 Mo of RAM. (-O -release -inline)
 Using the RC code (your own, translated from Java, right?), I get the
same.
 Same result, same time, same memory consumption. Yeah, my code is not
wrong :-) On my very slow PC using DMD the D version requires about 2.7s and about max 92 MB of memory.
Maybe my PC is even slower :-)
 The second Python version (the one by Hettinger) takes about 4.95s and less
 than 4.5 MB of memory.
 (The third Python version, that uses the eager array and Psyco is faster.)

 Are you able to write a short D version similar to the second Python
 version? (I have created one, but it's not as short as the second Python
 version, and it takes something like 4 seconds or more).
Funnily, this second Python version was the only one I knew. So no, I'm not able to do the deferred output in D. That's were the trick is anyway, to have the solution recurse on a 'younger' version of itself. Maybe with lazy int delegates ? Philippe
Sep 05 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:

Less than 1s is impressive.<
To compare, on the Ideone site the third Python version (Python 2.6.4 + Psyco) takes 1.46s and max 88 MB (this is where what Don has said about D bignums is important): http://ideone.com/5NvzR
Maybe with lazy int delegates ?<
Right, but the devil is in details. Bye, bearophile
Sep 05 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Sep 3, 2010 at 16:30, Justin Johansson <no spam.com> wrote:

 On 02/09/10 05:38, Philippe Sigaud wrote:

 Hey, this question on SO makes for a good challenge:


 http://stackoverflow.com/questions/3608834/is-it-possible-to-generically-implement-the-amb-operator-in-d
It's great to see someone doing the first D discussion topic with the [challenge] annotation.
This was just for fun, because combining ranges is always fun, and in this case, it's a good example of operator overloading. I have a more interesting / less academic challenge in mind: make idmd, an interactive,REPL-like, D "interpreter". Philippe
Sep 03 2010