On 09/24/2016 03:34 AM, Jonathan M Davis via Digitalmars-d wrote:
> On Friday, September 23, 2016 23:50:03 Nick Sabalausky via Digitalmars-d
> wrote:
>>
>> And then that leads too, to the question of whether such third-party
>> asserts are a good idea for the doc unittests I like so much... :/
>
> I'd say not. If you're writing a library for general consumption, I don't
> think that anyone else who is not actually helping to develop it should have
> to know or care what unit testing facilities you're using. assert is
> universal and clear, whereas other stuff is not universal and may or may not
> be clear to those not familiar with it.
>

Yea, honestly, that's my thought as well. :(  And it's a big part of why I was (and still am) so disappointed that assertPred didn't become official even if it is technically usable as third-party. We could've already been using that for years by now, standard, if it weren't for D's habit of letting perfect be the enemy of progress.

> Also, my take on it is that ddoc-ed unittest blocks are really there to just
> give examples for the documentation, not to test your code. You want the
> examples tested so that you know that they work - which is why ddoc-ed
> unittest blocks are such a great feature - but it's not their purpose to
> test your library. It would be wholly unreasonable to have thorough tests in
> the documentation, and what makes a good example doesn't necessarily make
> for a very good test (or vice versa).
>

I think there's a balance (albeit a difficult one). I agree that being pedantic with the examples can make them overly cluttered, so that should be avoided. But all major side-cases should still be documented, and examples help with that as they do with anything else.

For example, std.path.buildNormalizedPath: It should not only document typical cases like `buildNormalizedPath("foo","bar")`, but it's very important for its docs to also be clear about various other significant cases:

- How does it handle empty strings as arguments?
- What does it return for buildNormalizedPath("foo",".."). It used to return empty string which turned out very problematic. Now it returns "." which is much better.
- What happens when I do buildNormalizedPath(relativePath,absolutePath)?

These are all very important cases that still need to be documented. And examples work excellently as documentation here. (And IIRC, buildNormalizedPath docs are doing a good job of this.)

So a good set of examples *do* still test a significant amount of a function, even if it isn't exhaustive.

So because of that, and heck, even if your examples *are* overly sparse, sometimes you will get a failure in one. Which, of course, is the whole point of actually testing them. And when you do, it's a big help for the diagnostic output to actually be, well, helpful:

The whole cycle of:

- Search the stack trace for the relevant file/line number.

- Find it:
assert(x.foo(blah...) == y);

- Insert scaffolding:
import std.stdio;
writeln("x.foo(blah...): ", x.foo(blah...));
writeln("y: ", y);

- Recompile/re-run tests (and maybe go back again and fix any stupid typos in the scaffolding).

- Finally view key information that COULD'VE been shown right from the start.

Gets very tiresome very quickly, even if it's only in the example tests.

On 09/24/2016 04:03 AM, Martin Nowak wrote:
>
> assertPred!"=="(a, b);
> assertPred!"!"(a);
> assertPred!(std.range.equal)(a, b);
>
> Seems to do most of what DIP83 does w/ expensive feature design, and
> compiler implementation work.
> Also http://code.dlang.org/packages/unit-threaded comes with a couple of
> test comparators, though it follows ruby rspec's bad idea of giving
> every comparator a name (which has to be learnt and documented).

Yea, incidentally, I just started using unit-threaded for the first time this week, and so far, for the most part, I really quite like it a lot. But those comparator functions give me bad flashbacks of old-school Java.

Hmm, I wonder if Atila would be amenable to a more assertPred-like function in unit-threaded. Maybe a `should!"=="(leftSide, rightSide)` would fit in well. Or better yet, also adding in something like that that trick used in Andre's really nice recently proposed "dump" function (or whatever the name of it was), where it also prints out the actual argument provided in addition to the argument's value.

On 2016-09-24 15:12, Nick Sabalausky wrote:

> +1.
>
> Although I haven't given it too much thought, I'd bet that could also be
> used to provide, in library, my #1 most wanted missing D feature: Input
> ranges (maybe even forward, too) written as stackless coroutines
> (C#-style, heck, even C can do it in lib). So we could write input
> ranges without turning the whole freaking algorithm completely
> inside-out, or requiring the overhead of a full fiber.

Yeah, I've been thinking of that as well. It should be fairly easy to implement something like Protothreads [1]. Not sure about stackless coroutines though, if they need to save the state of the function on suspension and restore the state when the function resumes.

[1] http://dunkels.com/adam/pt/

-- 
/Jacob Carlborg

On 09/24/2016 10:20 AM, Jacob Carlborg wrote:
> On 2016-09-24 15:12, Nick Sabalausky wrote:
>
>> +1.
>>
>> Although I haven't given it too much thought, I'd bet that could also be
>> used to provide, in library, my #1 most wanted missing D feature: Input
>> ranges (maybe even forward, too) written as stackless coroutines
>> (C#-style, heck, even C can do it in lib). So we could write input
>> ranges without turning the whole freaking algorithm completely
>> inside-out, or requiring the overhead of a full fiber.
>
> Yeah, I've been thinking of that as well. It should be fairly easy to
> implement something like Protothreads [1]. Not sure about stackless
> coroutines though, if they need to save the state of the function on
> suspension and restore the state when the function resumes.
>
> [1] http://dunkels.com/adam/pt/
>

"Protothreads"! I've been trying to remember the name of that lib and couldn't find it. I used that the last time I was working on a C/C++ thing, and it was very helpful.

AIUI though, that IS stackless coroutines, same thing AFAIK. The Protothreads lib refers to itself as "extremely lightweight stackless threads". And the way it's used is definitely what I'd consider a coroutine.

Protothreads solves the problem of saving/restoring state by doing two things:

1. You put all your locals (at least, any that need preserved across save/restore) in a struct, together with the appropriate jump label to be jumped to upon resume. Then when yielding, this struct gets passed out, and when resuming you pass it back in.

2. Yielding can ONLY be done by a coroutine, itself, NOT by any functions it calls (unless those are also coroutines and return some flag signaling the first coroutine to also yield). This is the one big key that makes stackless fibers/coroutines/etc possible in the first place.

My understanding is that C#'s coroutines, under the hood, work the same way as C's Protothreads library:

First, only C#'s coroutines can yield, not regular functions called by a coroutine. Then, the C# compiler "lowers" the coroutine function into a big switch statement, with the current state (values of the locals and the hidden "case" target to jump to) passed in and out as a hidden argument.

Since the compiler does the conversion, it can safely deal with saving/restoring the locals, and crossing scope boundaries and such (which C is just plain not concerned with at all).

So really, C#'s coroutines (AIUI) are just like C's Protothreads, but with nicer sugar.

But about implementing it in D:

I'm not so sure that's realistic right now. I mean, I think something like it is *technically* possible, and I would have done so myself long ago, except that I see two major problems:

1. You'd have to write the entire coroutine as a string, which would really mess with IDE/editor features and the compiler's error reporting. And I'm not sure I see any way to do this in D without writing the coroutine as a string (or, you know, using AST macros ;) ).

2. Compared to C, D has much stricter rules about where a switch's "case" labels can do. Ie, they can't really cross scope boundaries. So *all* the coroutine's "yield" statements would have to be within the same scope *and* at the same nesting-level (or at the very least, there'd be some big annoying restrictions). Otherwise, when it gets converted to a "case:", the resulting code would be invalid.

We could use "goto" instead of case, but that has many of the same issues, plus (IIRC) the issue of goto-ing past a variable declaration (which IIRC is disallowed, or maybe had some other problem).

I'm not sure how you could get around problem #1 without AST macros or just implementing the whole feature in the compiler, like C#.

Even if you solved that, the only way I see to get around #2 would require very careful manual adjustments to the coroutine via a CTFE D AST, which (for right now) would be all kinds of bother, and at that point you may as well just add the feature built-into the compiler (like C#) because it would be more efficient than CTFE, AND it would solve problem #1.

On Sat, 24 Sep 2016 11:49:24 -0400, Nick Sabalausky wrote:
> My understanding is that C#'s coroutines, under the hood, work the same way as C's Protothreads library:

You mean async/await, which is a compiler-provided CPS transformation on top of the Task API.

There was a coroutine library for Mono, based on Mono.Tasklets, but I haven't been able to get Mono.Tasklets to work without segfaulting the last couple times I tried.

> First, only C#'s coroutines can yield, not regular functions called by a coroutine.

Because it's the continuation passing style, not a full thread of execution. That makes it moderately painful to use under normal circumstances and entirely unsuitable in other cases.

For instance, I've got a project that involves simulating a large number of actors (several thousand at a minimum) within a world. If I used CPS, it would be a bit painful. I'd have to keep remembering which functions are asynchronous and which are synchronous. If I needed to turn a function asynchronous, it changes how I call it, and that effect can ripple up.

And that's a maintenance problem, but at least I have a type system to help out.

I also need a scripting system, which will no doubt be weakly typed (ECMAScript, perhaps), and coordinating those changes there would be a much higher cost.

I also want to support people writing scripts who are not cautious about writing those scripts, who don't appreciate the technical innards that I implemented, and who will write scripts that occasionally misbehave. I want to make a pit of success for them and hopefully ensure that their scripts won't typically misbehave too badly.

So the CPS transformation model is a nonstarter for me, manual or partially automated.

> But about implementing it in D:
> 
> I'm not so sure that's realistic right now.

Look at Node.js and Vert.x. It's not a barrier to the market to force programmers to manually execute the CPS transformation.

Fibers are more convenient. They also have a large, upfront cost, but they have the advantage of treating the stack like a stack. It breaks fewer assumptions about performance.

Go's multitasking is a middle ground -- it has stacks that can shrink and grow, but the cost is a check for the stack bottom at every function call.

On 09/24/2016 09:14 PM, Chris Wright wrote:
> On Sat, 24 Sep 2016 11:49:24 -0400, Nick Sabalausky wrote:
>> My understanding is that C#'s coroutines, under the hood, work the same
>> way as C's Protothreads library:
>
> You mean async/await, which is a compiler-provided CPS transformation on
> top of the Task API.
>

No, I mean "yield". My C# work was all before async/await.

>> First, only C#'s coroutines can yield, not regular functions called by a
>> coroutine.
>
> Because it's the continuation passing style, not a full thread of
> execution. That makes it moderately painful to use under normal
> circumstances and entirely unsuitable in other cases.
>

If I understand correctly what you mean by "continuation passing style", then yes, it sort of is, but only behind-the-scenes. The only recognizable effect of that is that yield can only break out of one level of the call stack at a time (just like how return only ever returns from the current function, no further - unless you use Ruby, but well, let's not go there...).

The "turning functions inside-out" effect of continuation passing is exactly what input ranges suffer from[1] - and is exactly what stackless coroutines *avoid*.

>
> Look at Node.js and Vert.x. It's not a barrier to the market to force
> programmers to manually execute the CPS transformation.

Speaking as a long-time web developer, most (not all) web developers are fully-acclimated to eating shit sandwiches and convincing themselves they like it. Hence their tolerance for what Node.js does to their code (among other issues with it, like...using JS...on the server...).

Obviously I'm being colorfully figurative there, but I'm sure you knew that ;)

>
> Fibers are more convenient. They also have a large, upfront cost, but
> they have the advantage of treating the stack like a stack. It breaks
> fewer assumptions about performance.
>

You may want to give C's protobuf or C#'s yield-based generator functions a try. Yes, true, they're not as convenient as actual fibers, but there's a LOT they let you do painlessly (far more painlessly than writing input ranges[1]) without the fiber overhead - think opApply but without the complete and total incompatibility with functions that operate on ranges.

[1] Note I mean actually writing an input range itself. *Using* an input range is wonderfully pleasant. But writing them turns all my logic inside out, somewhat like Node.js-style callback hell (or ActionScript2 back in my day).

On 2016-09-24 17:49, Nick Sabalausky wrote:

> "Protothreads"! I've been trying to remember the name of that lib and
> couldn't find it. I used that the last time I was working on a C/C++
> thing, and it was very helpful.
>
> AIUI though, that IS stackless coroutines, same thing AFAIK. The
> Protothreads lib refers to itself as "extremely lightweight stackless
> threads". And the way it's used is definitely what I'd consider a
> coroutine.

I find it quite difficult to find correct definitions with many of these terms like: coroutine, fiber, stackless thread, resumeable function. Because many languages use the same name of different things and they use different names for the same things.

> Protothreads solves the problem of saving/restoring state by doing two
> things:
>
> 1. You put all your locals (at least, any that need preserved across
> save/restore) in a struct, together with the appropriate jump label to
> be jumped to upon resume. Then when yielding, this struct gets passed
> out, and when resuming you pass it back in.

Ah, right. Previously when I looked at this I only saw examples which stored the jump label. That might be possible to automatically rewrite in a AST macro.

Would it be possible to store the state in a TLS variable inside the function to avoid having to pass in the state?

> 2. Compared to C, D has much stricter rules about where a switch's
> "case" labels can do. Ie, they can't really cross scope boundaries. So
> *all* the coroutine's "yield" statements would have to be within the
> same scope *and* at the same nesting-level (or at the very least,
> there'd be some big annoying restrictions). Otherwise, when it gets
> converted to a "case:", the resulting code would be invalid.

Do you have any examples?

-- 
/Jacob Carlborg

On Sun, 25 Sep 2016 01:36:57 -0400, Nick Sabalausky wrote:

> On 09/24/2016 09:14 PM, Chris Wright wrote:
>> On Sat, 24 Sep 2016 11:49:24 -0400, Nick Sabalausky wrote:
>>> My understanding is that C#'s coroutines, under the hood, work the same way as C's Protothreads library:
>>
>> You mean async/await, which is a compiler-provided CPS transformation on top of the Task API.
>>
>>
> No, I mean "yield". My C# work was all before async/await.

Ah, I'd heard about people doing that.

That's a different transformation. Method to method object, add a state variable to mimic the program counter, and munge things about enough to match the IEnumerator interface.

Surprisingly similar despite the differences in implementation, though.

> The "turning functions inside-out" effect of continuation passing is exactly what input ranges suffer from[1] - and is exactly what stackless coroutines *avoid*.

The compiler inverts them for you.

>> Fibers are more convenient. They also have a large, upfront cost, but they have the advantage of treating the stack like a stack. It breaks fewer assumptions about performance.
>>
>>
> You may want to give C's protobuf or C#'s yield-based generator functions a try. Yes, true, they're not as convenient as actual fibers, but there's a LOT they let you do painlessly (far more painlessly than writing input ranges[1]) without the fiber overhead - think opApply but without the complete and total incompatibility with functions that operate on ranges.

Yeah, I really want something transparent.

> [1] Note I mean actually writing an input range itself. *Using* an input range is wonderfully pleasant. But writing them turns all my logic inside out, somewhat like Node.js-style callback hell (or ActionScript2 back in my day).

Agreed. It's relatively easy to compose ranges, which is nice, but whenever I have to write one from scratch, I get a little sad.

On Sun, 25 Sep 2016 12:39:21 +0200, Jacob Carlborg wrote:
> On 2016-09-24 17:49, Nick Sabalausky wrote:
>> 2. Compared to C, D has much stricter rules about where a switch's "case" labels can do. Ie, they can't really cross scope boundaries. So *all* the coroutine's "yield" statements would have to be within the same scope *and* at the same nesting-level (or at the very least, there'd be some big annoying restrictions). Otherwise, when it gets converted to a "case:", the resulting code would be invalid.
> 
> Do you have any examples?

Duff's device works, so case labels can cross scope boundaries.

On 09/25/2016 06:39 AM, Jacob Carlborg wrote:
>
> I find it quite difficult to find correct definitions with many of these
> terms like: coroutine, fiber, stackless thread, resumeable function.
> Because many languages use the same name of different things and they
> use different names for the same things.
>

FWIW, and this is at least the way I see it:
(BTW, any domain experts please chime in if I'm wrong. I'm thinking it may be worth reposting this as a blog entry, as long as I'm not too far off-base.)

Fiber:
------
Like a thread, but lighter-weight. Multiple fibers can run within one thread.

Like a thread, a fiber has it's own stack, and upon suspend/resume various state is saved/restored (I assume that "state" means "CPU registers").

Unlike a thread, a fiber's multitasking is sequential and cooperative, NOT simultaneous and preemptive: Ie, One fiber must willfully relinquish control (by calling a "yield" function) before another fiber in the same thread can resume. I'm assuming this sequential/cooperative what allows it to be lighter-weight than a true thread, but I'm not 100% certain.

Coroutine:
----------
A function that can "yield" (ie, it can choose to temporarily exit so that it can be resumed from the same place later on). Often a return value is emitted upon yielding, so these are usually used as generators, because they're a convenient way to generate a series of values in an easy procedural style.

Coroutines are commonly implemented as fibers, so it is often said that fibers and coroutines are the same thing. That's partially accurate, except for two things:

1. "Coroutine" refers to a specific function, whereas "fiber" refers to the overall sequence of execution.

2. This is probably a debatable matter of semantics, but coroutines don't have to be implemented using fibers. For example, opApply is essentially a coroutine (it yields by calling the delegate that was passed in).

Stackless Thread/Fiber:
-----------------------
Not a true thread or fiber. It's called a "stackless thread" or "stackless fiber" simply because it's *like* a thread or fiber (closer to a fiber, really), but without a separate stack for each, umm..."fiber". Protothreads is an example of a stackless thread/fiber.

A stackless thread/fiber is much more lightweight than even a fiber. But it comes with a limitation:

With a true fiber, any function in the callstack can yield. When it yields, it suspends the fiber's entire callstack. So inside a fiber, your coroutine can call a function and have *that* function yield your fiber. That feature requires a separate callstack for each fiber, so you cannot do that with the stackless versions.

Instead, in a stackless thread/fiber, yielding will ONLY suspend the current function, not a full callstack (since it doesnt have a callstack of its own to suspend).

In other words, yielding a stackless thread/fiber works much like a normal "return" statement:

-------------------
void foo() {
    bar();
}
void bar() {
    return; // ONLY return from bar

    return from BOTH bar AND foo; // IMPOSSIBLE!!!
}
-------------------

A stackless thread/fiber works the same (psuedocode):

-------------------
void coroutineFoo() {
    coroutineBar();
}
void coroutineBar() {

    // Stackless fiber: ONLY suspends coroutineBar.
    // Regular fiber: Suspends ENTIRE callstack.
    yield;

    yield from BOTH bar AND foo;// IMPOSSIBLE with stackless

    // More code here....
}
-------------------

Luckily, you can work around it, just like you can with normal returning (psuedocode):

-------------------
void coroutineFoo() {
    bool shouldYield = coroutineBar();
    if(shouldYield)
        yield;

    // More code here....
}
// Yielded value: Should the caller yield?
bool coroutineBar() {
    yield true; // Yield both bar and foo
    // More code here....
}
-------------------

I'd argue opApply's approach technically qualifies as a stackless thread/fiber, since it yields (by calling the delegate it received) and does not involve any extra callstack. Plus, like any other stackless thread/fiber, it cannot suspend any further up the callstack than just itself.

However, from what I've seen, a stackless thread/fiber is typically implemented the way Protothreads works:

When the "stackless coroutine" function is called, the first thing done inside the function is jump to wherever the function last left off.

Then, every "yield" is constructed as an *actual* "return" followed by a jump label. When a function yields, it returns three things:

1. An optional value being yielded (like a normal return value).

2. Which jump label to jump to next time the function is resumed.

3. Any local variables that need to be preserved upon resume (or just all local variables).

With a really nice stackless thread/fiber system, like C#'s, this is all handled behind-the-scenes.

Stackless Coroutine:
--------------------
A coroutine that uses a stackless thread/fiber instead of a normal fiber.

Resumable Function:
-------------------
This sounds like a vague general term to me. I would think it casually refers to any function that can be suspended/resumed: A Fiber-based coroutine, a stackless coroutine, or whatever else may or may not exist.


> Ah, right. Previously when I looked at this I only saw examples which
> stored the jump label. That might be possible to automatically rewrite
> in a AST macro.
>
> Would it be possible to store the state in a TLS variable inside the
> function to avoid having to pass in the state?
>

I don't see why not, but there would be one notable drawback: You could only have one instance existing at a time (per thread).

Ex: If you pass the state through params and return values instead of a static function variable, you can do this:

----------------------
// A manual stackless coroutine in D
// Would be much simpler with built-in support

struct YieldInfo {
    State state;
    int yieldedValue;
}

struct State {
    int jumpLabel = 1;
    // Any additional locals here
}

// Generate three multiples of 'multiplier', repeating forever
YieldInfo generateMultiples(
    State state, int multiplier
) {
    switch(state.jumpLabel) {
    case 1:
        // Yield first multiple
        return YieldInfo(State(2), 1 * multiplier);

    case 2:
        // Yield second multiple
        return YieldInfo(State(3), 2 * multiplier);

    case 3:
        // Yield third multiple
        return YieldInfo(State(1), 3 * multiplier);
    }
}

void main()
{
    // One instance of generateMultiples
    YieldInfo a;

    a = generateMultiples(a, 2); assert(a.yieldedValue == 2);
    a = generateMultiples(a, 2); assert(a.yieldedValue == 4);
    a = generateMultiples(a, 2); assert(a.yieldedValue == 6);
    a = generateMultiples(a, 2); assert(a.yieldedValue == 2);

    // Do another instance at the same time:
    YieldInfo b;

    b = generateMultiples(b, 5); assert(b.yieldedValue == 5);
    a = generateMultiples(a, 2); assert(a.yieldedValue == 4);
    b = generateMultiples(b, 5); assert(b.yieldedValue == 10);
    a = generateMultiples(a, 2); assert(a.yieldedValue == 6);
    b = generateMultiples(b, 5); assert(b.yieldedValue == 15);
}
----------------------

Actual stackless coroutine support would make that much simpler of course:

----------------------
CoroutineInputRange!int generateMultiples(int multiple) {
    while(true) {
        foreach(i; 1...4)
            yield i * multiple;

    }
}
void main()
{
    auto a = generateMultiples(2);

    assert(a.front == 2);
    a.popfront(); assert(a.front == 4);
    a.popfront(); assert(a.front == 6);
    a.popfront(); assert(a.front == 2);

    auto b = generateMultiples(5);

    assert(b.front == 5);
    a.popfront(); assert(a.front == 4);
    b.popfront(); assert(b.front == 10);
    a.popfront(); assert(a.front == 6);
    b.popfront(); assert(b.front == 15);
}
----------------------

Naturally, if the state was stored as the function's static locals, you woudn't be able to do that. Instance "b" would clobber instance "a".

>> 2. Compared to C, D has much stricter rules about where a switch's
>> "case" labels can do. Ie, they can't really cross scope boundaries. So
>> *all* the coroutine's "yield" statements would have to be within the
>> same scope *and* at the same nesting-level (or at the very least,
>> there'd be some big annoying restrictions). Otherwise, when it gets
>> converted to a "case:", the resulting code would be invalid.
>
> Do you have any examples?
>

I'd have to look it up and refresh my memory. I just remember D has more restrictions regarding jumping to labels than C has. Something like:

------------------
State myCoroutine(State s) {
    yield "hello";

    if(foo) {
        yield " world";
    }

    yield "!";
}
------------------

A Protothreads-like preprocessing approach that used switch/case would turn that into:

------------------
State myCoroutine(State s) {
switch(s.jumpLabel){
    case 0:
    // Start converted code: //////////////

    //yield "hello"; -> return+case:
    return State(1, "hello");
    case 1:

    if(int foo = getFoo()) {
        //yield " world"; ->
        return State(2, " world"); return+case:
        case 2:
    }

    //yield "!"; -> return+case:
    return State(3, "!");
    case 3:

    // End converted code //////////////
    break;
}
}
------------------

That "if" really messed things up. AIUI, I don't think D will allow things like that.

C doesn't have so much of a problem with any of this, it famously just permits pretty much anything, which is why Protothreads works there.