Regarding my proposal to add with-unique-continuation-mark and use it for the implementation of parameterize and in SRFI155 where the tail-call-detection mark is set -- this works to satisfy the bounded-space tests.   I tested it thoroughly today.    But as I feared, it has a measurable performance impact on parameterize, even when I push all the heavy lifting into C code.    I threw that code away.

So, in the end, I come back full-circle to the prior solution which involves explicit reduction where (srfi 155)'s code previously calls (current-dynamic-extent).

    1) Where the DELAY macro invokes (current-dynamic-extent), the saved extent needs to be reduced to minimize the storage associated with all parameters and to reduce marks associated with the tail-call-detection key.

    2) Since the forcing-extent is saved in a parameter, the same reduction must be done on that saved extent as well.

Let's assume for the moment that the (srfi 155) is the only client of (srfi 154) that requires this special feature.   The time cost of the reduction is significant, so we don't want every call to (current-dynamic-extent) to incur this workload by default.

So, we need an extra special API function from (srfi 154) or an internals library it depends on:

    (reduced-dynamic-extent extent tail-call-detection-key)

where tail-call-detection-key is the key used inside SRFI155 for tail-call detection in force.  The procedure returns a new extent object with the minimization for parameters and reduction for the tail-call-detection marks.    Since at most one new tail-mark is added per call to force, it is sufficient for reduced-dynamic-extent to remove at most 1 instance of the tail-call mark.   However, since arbitrarily many parameterizations could occur in delayed expressions, the reduction for parameters needs to be to some fixed maximum # of parameter versions per parameter (I use 1 as that maximum).

Since this is for (srfi 155) only -- and I cannot envision anyone else needing it, except perhaps a later variant on (srfi 155), I don't really see any value in adding this to (srfi 154)'s specification.    Already, there's no chance in hell this can be implemented with portable code, so there's little value in forcing the community to add reduced-dynamic-extent to their (srfi 154) implementation -- it's really only of interest to (srfi 155) implementors.

I've edited my (srfi 154) and (srfi 155) code and added it to a fork of the srfi-155 repo at:

https://github.com/jimrees/srfi-155/commit/6e6bf9a3b538ee0de8612d776563f6e09c28d1aa

In summary, I think the best bet is to leave the (srfi 155) _document_ alone (except there's a "their" which should be "there" ;-)).   Accomplishing bounded-space requirements is an implementation detail.

There is ONE suggestion I could make though for the official (srfi 154) api -- a weakness of (current-dynamic-extent) is that it cannot reproduce the tail-call behavior associated with continuation marks, unless it is called in tail context itself, which is rarely useful.    The continuation of the call to current-dynamic-extent will usually be to initialize an argument to another procedure call or to bind/assign a variable.  Either way that's never in tail context, -- in your (srfi 157) parlance, "flag" is always #f.   An alternative is:

    (call-with-current-dynamic-extent f)

where f is procedure which takes one argument.  I could see this as either a replacement or addition to current-dynamic-extent which is trivial to implement in terms of the above.

On Thu, Jun 28, 2018 at 2:21 PM Jim Rees <xxxxxx@gmail.com> wrote:

Hey Marc,

I need to apologize to you.   After that last email, I went back to my code to be sure I could tidy it up exactly the way I had proposed.    I discovered that my approach to parameters was NOT the way I had suggested.    I proposed that parameterize should taken on the burden (performance hit) of using with-unique-continuation-mark.     What my code actually does is defer that filtering operation to (current-dynamic-extent) - so that parameterize is kept fast and simple.

The proposal is still valid with respect to space-complexitiy behavior on the lazy examples, but I don't think it's preferable since it hits parameterize with a lot of extra work which is ONLY needed for lazy code.

I will spend the proper time to come up with a better set of changes this time and give you the paragraph for (srfi 155) you actually asked for.

-jim

On Thu, Jun 28, 2018 at 1:26 PM Jim Rees <xxxxxx@gmail.com> wrote:

Actually, after my last realization about how parameters should be implemented, the minimal necessary tweak is to add an alternative to with-continuation-mark to (srfi 157), and for the implementation of parameters to use it and for (srfi 155) to use it when setting the tail-call-detection mark.    Then no changes to (srfi 154) are needed.

(with-unique-continuation-mark <key> <value> <expression>)

The name may not be ideal.    This will add the given continuation mark, and remove all other marks associated with the same <key>.    (For the purposes of limiting space growth, it MAY be sufficient if this removes at most 1 other mark associated with the key -- that would still pass all the standard lazy streams tests, but I can't for certain say it's the correct approach.   I can't think of why someone would mix the two flavors of with-continuation-mark on the same key -- just looking for trouble, I suppose).

So, then the sample code for parameterize should use this, as well as the sample code for (srfi 155) when setting the tail-call-detection mark.

2) You argue that we can save space by treating, continuations as lists (instead of copying them). However, on several occasions, you are filtering lists of marks. Don't you have to copy the lists for this?

It's not my intent to suggest that Scheme systems with entirely different approaches to continuations cannot get the space-growth issue right.   I just haven't had the time to fully explore these issues in other systems beyond my own.  I *think* the change I have proposed is necessary across all systems, because with-continuation-mark has necessary consequences on the results of other (srfi 157) API which requires growth in storage.

It's true that in my code, I can walk the "list" of continuations, and attached to each continuation is a continuation-marks list (which is lazily constructed only if needed, but never, ever mutated after that).

The proposed new (srfi 157) item does, in general, have to do some copying -- though it's certainly encouraged to share common-tails.   This doesn't create a new source of space growth though -- since as all the old continuations become garbage, their associated marks lists become garbage as well.