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