| 1 |
/* |
| 2 |
* lazy.c - lazy evaluation constructs |
| 3 |
* |
| 4 |
* Copyright (c) 2000-2024 Shiro Kawai <[email protected]> |
| 5 |
* |
| 6 |
* Redistribution and use in source and binary forms, with or without |
| 7 |
* modification, are permitted provided that the following conditions |
| 8 |
* are met: |
| 9 |
* |
| 10 |
* 1. Redistributions of source code must retain the above copyright |
| 11 |
* notice, this list of conditions and the following disclaimer. |
| 12 |
* |
| 13 |
* 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
* notice, this list of conditions and the following disclaimer in the |
| 15 |
* documentation and/or other materials provided with the distribution. |
| 16 |
* |
| 17 |
* 3. Neither the name of the authors nor the names of its contributors |
| 18 |
* may be used to endorse or promote products derived from this |
| 19 |
* software without specific prior written permission. |
| 20 |
* |
| 21 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
*/ |
| 33 |
|
| 34 |
#define LIBGAUCHE_BODY |
| 35 |
#include "gauche.h" |
| 36 |
#include "gauche/priv/configP.h" |
| 37 |
#include "gauche/priv/atomicP.h" |
| 38 |
#include "gauche/priv/pairP.h" |
| 39 |
#include "gauche/priv/parameterP.h" |
| 40 |
#include "gauche/priv/promiseP.h" |
| 41 |
|
| 42 |
/*================================================================== |
| 43 |
* Promise |
| 44 |
*/ |
| 45 |
|
| 46 |
/* NB: We adopted the semantics described in srfi-45. |
| 47 |
* http://srfi.schemers.org/srfi-45/srfi-45.html |
| 48 |
* |
| 49 |
* The 'forced' flag indicates one of two state of a promise. |
| 50 |
* |
| 51 |
* forced == TRUE: the promise is in 'eager' state. code has a value. |
| 52 |
* forced == FALSE: the promise is in 'lazy' state. code has a thunk. |
| 53 |
* |
| 54 |
* [syntax] lazy expr : Promise a -> Promise a |
| 55 |
* Creates a lazy promise, delaying evaluation of expr. |
| 56 |
* [procedure] eager expr : a -> Promise a |
| 57 |
* Creates a eager promise, encapsulating the result of evaluation of expr. |
| 58 |
* [syntax] delay expr : a -> Promise a |
| 59 |
* (lazy (eager expr)) |
| 60 |
* [procedure] force expr : Promise a -> a |
| 61 |
* |
| 62 |
* One might want to create a subtype of promise; for example, srfi-40 |
| 63 |
* requires the stream type to be distinct from other types, although |
| 64 |
* it is essentially a promise with a specific usage pattern. To realize |
| 65 |
* that portably, one need effectively reimplement force/delay mechanism |
| 66 |
* (since 'eager' operation is required to return Stream instread of Promise), |
| 67 |
* which is kind of shame. |
| 68 |
* |
| 69 |
* Gauche experimentally tries to address this problem by allowing the |
| 70 |
* program to add a specific KIND object to a promise instance. |
| 71 |
* |
| 72 |
* Thread safety: It is safe that more than one thread force a promise |
| 73 |
* simultaneously. Only one thread does calculation. |
| 74 |
*/ |
| 75 |
|
| 76 |
/* |
| 77 |
* The body of promise |
| 78 |
*/ |
| 79 |
typedef struct ScmPromiseContentRec { |
| 80 |
ScmPromiseState state; |
| 81 |
ScmObj code; /* thunk or value */ |
| 82 |
ScmObj parameterization; /* parameterization of delay form */ |
| 83 |
ScmInternalMutex mutex; |
| 84 |
} ScmPromiseContent; |
| 85 |
|
| 86 |
/* |
| 87 |
* class stuff |
| 88 |
*/ |
| 89 |
|
| 90 |
static void promise_print(ScmObj obj, ScmPort *port, |
| 91 |
ScmWriteContext *ctx SCM_UNUSED) |
| 92 |
{ |
| 93 |
ScmPromise *p = (ScmPromise*)obj; |
| 94 |
const char *forced = ""; |
| 95 |
switch (p->content->state) { |
| 96 |
case SCM_PROMISE_FORCED: |
| 97 |
forced = " (forced)"; |
| 98 |
break; |
| 99 |
case SCM_PROMISE_EXCEPTION: |
| 100 |
forced = " (exception)"; |
| 101 |
break; |
| 102 |
case SCM_PROMISE_UNFORCED: |
| 103 |
break; |
| 104 |
} |
| 105 |
if (SCM_FALSEP(p->kind)) { |
| 106 |
Scm_Printf(port, "#<promise %p%s>", p, forced); |
| 107 |
} else { |
| 108 |
Scm_Printf(port, "#<promise(%S) %p%s>", p->kind, p, forced); |
| 109 |
} |
| 110 |
} |
| 111 |
|
| 112 |
SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_PromiseClass, promise_print); |
| 113 |
|
| 114 |
/* |
| 115 |
* promise object |
| 116 |
*/ |
| 117 |
|
| 118 |
/* Promise can be initialized in one of UNFORCED, FORCED or EXCEPTION state. |
| 119 |
* UNFORCED can change to FORCED or EXCEPTION. Once it becomes FORCED |
| 120 |
* or EXCEPTION, the state never changes. |
| 121 |
* The value of ScmPromise->content->code depends on the state. |
| 122 |
*/ |
| 123 |
|
| 124 |
ScmObj Scm_MakePromise(ScmPromiseState state, ScmObj obj) |
| 125 |
{ |
| 126 |
ScmPromise *p = SCM_NEW(ScmPromise); |
| 127 |
ScmPromiseContent *c = SCM_NEW(ScmPromiseContent); |
| 128 |
SCM_SET_CLASS(p, SCM_CLASS_PROMISE); |
| 129 |
SCM_INTERNAL_MUTEX_INIT(c->mutex); |
| 130 |
c->parameterization = SCM_FALSE; |
| 131 |
c->state = state; |
| 132 |
|
| 133 |
switch (state) { |
| 134 |
case SCM_PROMISE_UNFORCED: |
| 135 |
c->code = obj; /* obj is a thunk */ |
| 136 |
c->parameterization = Scm_CurrentParameterization(); |
| 137 |
break; |
| 138 |
case SCM_PROMISE_FORCED: |
| 139 |
if (!SCM_LISTP(obj)) SCM_TYPE_ERROR(obj, "list"); |
| 140 |
c->code = obj; /* obj is a list of values */ |
| 141 |
break; |
| 142 |
case SCM_PROMISE_EXCEPTION: |
| 143 |
c->code = obj; /* obj is a condition */ |
| 144 |
break; |
| 145 |
} |
| 146 |
p->content = c; |
| 147 |
p->kind = SCM_FALSE; |
| 148 |
return SCM_OBJ(p); |
| 149 |
} |
| 150 |
|
| 151 |
/* |
| 152 |
* force |
| 153 |
*/ |
| 154 |
|
| 155 |
static ScmObj force_exc_handler(ScmObj *argv, int argc, void *data) |
| 156 |
{ |
| 157 |
SCM_ASSERT(argc == 1); |
| 158 |
SCM_ASSERT(SCM_PAIRP(SCM_OBJ(data))); |
| 159 |
ScmPromise *p = (ScmPromise*)SCM_CAR(SCM_OBJ(data)); |
| 160 |
ScmObj prev_handler = SCM_CDR(SCM_OBJ(data)); |
| 161 |
|
| 162 |
ScmPromiseContent *c = p->content; |
| 163 |
|
| 164 |
SCM_INTERNAL_MUTEX_LOCK(c->mutex); |
| 165 |
if (c->state == SCM_PROMISE_UNFORCED) { |
| 166 |
c->code = argv[0]; /* condition object */ |
| 167 |
Scm_AtomicThreadFence(); |
| 168 |
c->state = SCM_PROMISE_EXCEPTION; |
| 169 |
} |
| 170 |
SCM_INTERNAL_MUTEX_UNLOCK(c->mutex); |
| 171 |
|
| 172 |
Scm_VMPushExceptionHandler(prev_handler); |
| 173 |
SCM_RETURN(Scm_Raise(c->code, SCM_RAISE_NON_CONTINUABLE)); |
| 174 |
} |
| 175 |
|
| 176 |
static ScmObj force_cc(ScmObj result, void **data) |
| 177 |
{ |
| 178 |
ScmPromise *p = (ScmPromise*)data[0]; |
| 179 |
ScmPromiseContent *c = p->content; |
| 180 |
ScmObj handlers = (ScmObj)data[1]; |
| 181 |
|
| 182 |
SCM_INTERNAL_MUTEX_LOCK(c->mutex); |
| 183 |
if (c->state == SCM_PROMISE_UNFORCED) { |
| 184 |
/* It is critical to set code first, then state. The reader will |
| 185 |
check state first; if it's eitehr FORCED or EXCEPTION, it's sure |
| 186 |
that c->code holds results/exception. |
| 187 |
*/ |
| 188 |
if (SCM_PROMISEP(result)) { |
| 189 |
/* Deal with a recursive promise introduced by lazy operation. |
| 190 |
See srfi-45 for the details. */ |
| 191 |
ScmPromiseContent *cc = SCM_PROMISE(result)->content; |
| 192 |
c->code = cc->code; |
| 193 |
Scm_AtomicThreadFence(); |
| 194 |
c->state = cc->state; |
| 195 |
SCM_PROMISE(result)->content = c; |
| 196 |
} else { |
| 197 |
/* This isn't supposed to happen if 'lazy' is used properly |
| 198 |
on the promise-yielding procedure, but we can't prevent |
| 199 |
one from writing (lazy 3). So play safe. */ |
| 200 |
SCM_ASSERT(SCM_LISTP(result)); |
| 201 |
c->code = result; |
| 202 |
Scm_AtomicThreadFence(); |
| 203 |
c->state = SCM_PROMISE_FORCED; |
| 204 |
} |
| 205 |
} |
| 206 |
SCM_INTERNAL_MUTEX_UNLOCK(c->mutex); |
| 207 |
Scm_VMSetDynamicHandlers(handlers); |
| 208 |
/* We recursively call force to deliver the result. */ |
| 209 |
SCM_RETURN(Scm_VMForce(SCM_OBJ(p))); |
| 210 |
} |
| 211 |
|
| 212 |
ScmObj Scm_VMForce(ScmObj obj) |
| 213 |
{ |
| 214 |
if (!SCM_PROMISEP(obj)) SCM_RETURN(obj); |
| 215 |
|
| 216 |
ScmPromiseContent *c = SCM_PROMISE(obj)->content; |
| 217 |
ScmVM *vm = Scm_VM(); |
| 218 |
|
| 219 |
retry: |
| 220 |
switch (c->state) { |
| 221 |
case SCM_PROMISE_FORCED: |
| 222 |
/* already forced. c->code has values. */ |
| 223 |
return Scm_Values(c->code); |
| 224 |
case SCM_PROMISE_EXCEPTION: |
| 225 |
/* evaluation of promise ended up exception. */ |
| 226 |
return Scm_VMThrowException(vm, c->code, 0); |
| 227 |
case SCM_PROMISE_UNFORCED: |
| 228 |
{ |
| 229 |
/* State and code may be changed by another thread, so we |
| 230 |
take the snapshot. */ |
| 231 |
ScmPromiseState state; |
| 232 |
ScmObj code; |
| 233 |
SCM_INTERNAL_MUTEX_LOCK(c->mutex); |
| 234 |
state = c->state; |
| 235 |
code = c->code; |
| 236 |
SCM_INTERNAL_MUTEX_UNLOCK(c->mutex); |
| 237 |
if (state != SCM_PROMISE_UNFORCED) { |
| 238 |
/* another thread already forced. */ |
| 239 |
goto retry; |
| 240 |
} |
| 241 |
/* From now on, it is ok that another thread changes the promise's |
| 242 |
state. We go on to evaluate thunk anyway, and we'll check |
| 243 |
the promise's state at the moment we try to set the result. |
| 244 |
*/ |
| 245 |
void *data[2]; |
| 246 |
data[0] = obj; |
| 247 |
data[1] = Scm_VMGetDynamicHandlers(); |
| 248 |
Scm_VMPushCC(force_cc, data, 2); |
| 249 |
|
| 250 |
if (SCM_PARAMETERIZATIONP(c->parameterization)) { |
| 251 |
Scm_InstallParameterization(SCM_PARAMETERIZATION(c->parameterization)); |
| 252 |
} |
| 253 |
ScmObj exc_handler = |
| 254 |
Scm_MakeSubr(force_exc_handler, |
| 255 |
Scm_Cons(obj, Scm_VMCurrentExceptionHandler()), |
| 256 |
1, 0, |
| 257 |
SCM_INTERN("force-exc-handler")); |
| 258 |
Scm_VMPushExceptionHandler(exc_handler); |
| 259 |
SCM_RETURN(Scm_VMApply0(code)); |
| 260 |
} |
| 261 |
} |
| 262 |
return SCM_UNDEFINED; /* dummy */ |
| 263 |
} |
| 264 |
|
| 265 |
/* TODO: The caller assumes only one result, but we extended force to |
| 266 |
* return multiple values. Need the way to update API. |
| 267 |
*/ |
| 268 |
|
| 269 |
ScmObj Scm_Force(ScmObj obj) |
| 270 |
{ |
| 271 |
if (!SCM_PROMISEP(obj)) { |
| 272 |
SCM_RETURN(obj); |
| 273 |
} else { |
| 274 |
ScmPromiseContent *c = SCM_PROMISE(obj)->content; |
| 275 |
if (c->state == SCM_PROMISE_FORCED) { |
| 276 |
SCM_ASSERT(SCM_PAIRP(c->code)); |
| 277 |
return SCM_CAR(c->code); |
| 278 |
} |
| 279 |
|
| 280 |
static ScmObj force = SCM_UNDEFINED; |
| 281 |
SCM_BIND_PROC(force, "force", Scm_SchemeModule()); |
| 282 |
return Scm_ApplyRec1(force, obj); |
| 283 |
} |
| 284 |
} |
| 285 |
|
| 286 |
/*================================================================= |
| 287 |
* Lazy pairs |
| 288 |
* |
| 289 |
* Lazy pair is a lazy structure that can turn into a normal pair. |
| 290 |
* If you check whether the object is pair or not by SCM_PAIRP, |
| 291 |
* it is 'forced' to become a pair. The forcing is |
| 292 |
* identity-preserving; that is, once a lazy pair is forced, the pointer |
| 293 |
* now becomes a pair (actually, an extended pair). It is a critical |
| 294 |
* attribute to make the forcing implicit---we can't do it for general |
| 295 |
* values. Since the forcing is implicit, majority of the code won't see |
| 296 |
* ScmLazyPair. |
| 297 |
* |
| 298 |
* The identity-preserving property requires us to generate |
| 299 |
* one item ahead from the generator, for we can't replace lazypair |
| 300 |
* to (), which is an immediate value. |
| 301 |
*/ |
| 302 |
|
| 303 |
/* |
| 304 |
|
| 305 |
(0) Initial state |
| 306 |
A lazypair is allocated on 4-word boundary, but we return a pointer to |
| 307 |
the second word. That makes the object look like odd-word boundary |
| 308 |
aligned, a marker of Extended Pair (see priv/pairP.h). The 'hidden' |
| 309 |
first word will be used for synchronization. |
| 310 |
NB: An extended pair must have preceding hidden word with 111 in the lower |
| 311 |
bits for extra check (when !SCM_PAIR_ALWAYS_ALIGNED_EVEN_WORDS). That |
| 312 |
check is done after SCM_PAIRP, however, so it won't see (AO_t)0. |
| 313 |
|
| 314 |
+---------------+ |
| 315 |
| (AO_t)0 | |
| 316 |
ScmObj > +---------------+ |
| 317 |
| LazyPair tag | |
| 318 |
+---------------+ |
| 319 |
| ScmObj item | |
| 320 |
+---------------+ |
| 321 |
| ScmObj | ----> generator |
| 322 |
+---------------+ |
| 323 |
|
| 324 |
(1) The first thread (owner) grabs the packet, then evaluates the generator. |
| 325 |
The grabbing is done by CAS to make it atomic. |
| 326 |
|
| 327 |
+---------------+ |
| 328 |
| (AO_t)owner | |
| 329 |
ScmObj > +---------------+ |
| 330 |
| LazyPair tag | |
| 331 |
+---------------+ |
| 332 |
| ScmObj item | |
| 333 |
+---------------+ |
| 334 |
| ScmObj | ----> generator |
| 335 |
+---------------+ |
| 336 |
|
| 337 |
|
| 338 |
(2) If generator yields a non-EOF value, owner first creates a |
| 339 |
new LazyPair... |
| 340 |
|
| 341 |
+---------------+ |
| 342 |
| (AO_t)owner | |
| 343 |
ScmObj > +---------------+ |
| 344 |
| LazyPair tag | |
| 345 |
+---------------+ |
| 346 |
| ScmObj item | |
| 347 |
+---------------+ |
| 348 |
| ScmObj | --------------+-> generator |
| 349 |
+---------------+ | |
| 350 |
| |
| 351 |
| |
| 352 |
| |
| 353 |
+---------------+ | |
| 354 |
| (AO_t)0 | | |
| 355 |
+---------------+ | |
| 356 |
| LazyPair tag | | |
| 357 |
+---------------+ | |
| 358 |
| ScmObj newitem| | |
| 359 |
+---------------+ | |
| 360 |
| ScmObj | -/ |
| 361 |
+---------------+ |
| 362 |
|
| 363 |
(3) then it replaces the cdr pointer with the new LazyPair, and clear |
| 364 |
the last slot. |
| 365 |
|
| 366 |
+---------------+ |
| 367 |
| (AO_t)owner | |
| 368 |
ScmObj > +---------------+ |
| 369 |
| LazyPair tag | |
| 370 |
+---------------+ |
| 371 |
| ScmObj | -\ |
| 372 |
+---------------+ | |
| 373 |
| NIL | | |
| 374 |
+---------------+ | |
| 375 |
| |
| 376 |
| +---------------+ |
| 377 |
| | (AO_t)0 | |
| 378 |
| +---------------+ |
| 379 |
\-> | LazyPair tag | |
| 380 |
+---------------+ |
| 381 |
| ScmObj newitem| |
| 382 |
+---------------+ |
| 383 |
| ScmObj | ---> generator |
| 384 |
+---------------+ |
| 385 |
|
| 386 |
(4) replaces the hidden word with the extended pair descriptor. |
| 387 |
At this moment, it still look like a lazy pair and someone working on |
| 388 |
it, from the thread other than the owner. |
| 389 |
|
| 390 |
+---------------+ |
| 391 |
| desc + 7 | ---> ScmExtendedPairDescriptor |
| 392 |
ScmObj > +---------------+ |
| 393 |
| LazyPair tag | |
| 394 |
+---------------+ |
| 395 |
| ScmObj | -\ |
| 396 |
+---------------+ | |
| 397 |
| NIL | | |
| 398 |
+---------------+ | |
| 399 |
| |
| 400 |
| +---------------+ |
| 401 |
| | (AO_t)0 | |
| 402 |
| +---------------+ |
| 403 |
\-> | LazyPair tag | |
| 404 |
+---------------+ |
| 405 |
| ScmObj newitem| |
| 406 |
+---------------+ |
| 407 |
| ScmObj | ---> generator |
| 408 |
+---------------+ |
| 409 |
|
| 410 |
(5) finally we set the car field with the precomputed item value. |
| 411 |
Now it looks like just an extended pair. |
| 412 |
|
| 413 |
+---------------+ |
| 414 |
| desc + 7 | ---> ScmExtendedPairDescriptor |
| 415 |
ScmObj > +---------------+ |
| 416 |
| ScmObj item | |
| 417 |
+---------------+ |
| 418 |
| ScmObj | -\ |
| 419 |
+---------------+ | |
| 420 |
| NIL | | |
| 421 |
+---------------+ | |
| 422 |
| |
| 423 |
| +---------------+ |
| 424 |
| | (AO_t)0 | |
| 425 |
| +---------------+ |
| 426 |
\-> | LazyPair tag | |
| 427 |
+---------------+ |
| 428 |
| ScmObj newitem| |
| 429 |
+---------------+ |
| 430 |
| ScmObj | ---> generator |
| 431 |
+---------------+ |
| 432 |
|
| 433 |
|
| 434 |
(2') If generator yields EOF, we don't create a new lazy pair. |
| 435 |
We first replace the second and third slot by NIL, |
| 436 |
|
| 437 |
+---------------+ |
| 438 |
| (AO_t)owner | |
| 439 |
ScmObj > +---------------+ |
| 440 |
| LazyPair tag | |
| 441 |
+---------------+ |
| 442 |
| NIL | |
| 443 |
+---------------+ |
| 444 |
| NIL | |
| 445 |
+---------------+ |
| 446 |
|
| 447 |
(3') then replace the car part by the cached value, which turns |
| 448 |
the object to an (extended) pair, |
| 449 |
|
| 450 |
+---------------+ |
| 451 |
| desc + 7 | ---> ScmExtendedPairDescriptor |
| 452 |
ScmObj > +---------------+ |
| 453 |
| LazyPair tag | |
| 454 |
+---------------+ |
| 455 |
| NIL | |
| 456 |
+---------------+ |
| 457 |
| NIL | |
| 458 |
+---------------+ |
| 459 |
|
| 460 |
|
| 461 |
(4') then set the car field with the cached value, which turns |
| 462 |
the object to an (extended) pair, with its cdr being NIL. |
| 463 |
|
| 464 |
+---------------+ |
| 465 |
| desc + 7 | ---> ScmExtendedPairDescriptor |
| 466 |
ScmObj > +---------------+ |
| 467 |
| item | |
| 468 |
+---------------+ |
| 469 |
| NIL | |
| 470 |
+---------------+ |
| 471 |
| NIL | |
| 472 |
+---------------+ |
| 473 |
|
| 474 |
Each step of the state transitions (0)->(1)->(2)->(3)->(4)->(5) and |
| 475 |
(0)->(1)->(2')->(3')->(4') are atomic, so the observer see either |
| 476 |
one of those states. |
| 477 |
|
| 478 |
[Extended protocol] |
| 479 |
|
| 480 |
Experimentally, the generator can return more than just the next item. |
| 481 |
|
| 482 |
- It can return the second value as pair attribute alist, to be attached |
| 483 |
to the pair containing the generated item. |
| 484 |
|
| 485 |
- It can return a (lazy) pair or (), instead of just an item. This is |
| 486 |
useful to implement lcons. We need a special marker to distinguish |
| 487 |
such generator from the ordinary one that returns a pair as an element. |
| 488 |
So such lazy pair should be constructed with Scm_LazyCons, instead of |
| 489 |
Scm_MakeLazyPair. |
| 490 |
*/ |
| 491 |
|
| 492 |
|
| 493 |
SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_LazyPairClass, NULL); |
| 494 |
|
| 495 |
/* This is what everyone see */ |
| 496 |
struct ScmLazyPairRec { |
| 497 |
SCM_HEADER; |
| 498 |
ScmObj item; |
| 499 |
ScmObj generator; |
| 500 |
}; |
| 501 |
|
| 502 |
/* And this is the real thing */ |
| 503 |
typedef struct ScmRealLazyPairRec { |
| 504 |
ScmAtomicVar owner; |
| 505 |
ScmLazyPair data; |
| 506 |
} ScmRealLazyPair; |
| 507 |
|
| 508 |
/* Clean up pair attribute list given from outside. |
| 509 |
(1) We need to copy it so that future mutation won't interfere |
| 510 |
(2) If the given obj contains bad items, we simply ignore it, |
| 511 |
for raising error lazily isn't useful. |
| 512 |
*/ |
| 513 |
static ScmObj copy_attrs(ScmObj attrs) |
| 514 |
{ |
| 515 |
ScmObj h = SCM_NIL, t = SCM_NIL, cp; |
| 516 |
SCM_FOR_EACH(cp, attrs) { |
| 517 |
if (SCM_PAIRP(SCM_CAR(cp))) { |
| 518 |
SCM_APPEND1(h, t, Scm_Cons(SCM_CAAR(cp), SCM_CDAR(cp))); |
| 519 |
} |
| 520 |
} |
| 521 |
return h; |
| 522 |
} |
| 523 |
|
| 524 |
static ScmObj make_lazy_pair(ScmObj item, ScmObj generator, ScmObj attrs) |
| 525 |
{ |
| 526 |
ScmRealLazyPair *z = SCM_NEW(ScmRealLazyPair); |
| 527 |
z->owner = (ScmAtomicWord)0; |
| 528 |
ScmLazyPair *r = &z->data; |
| 529 |
SCM_SET_CLASS(r, SCM_CLASS_LAZY_PAIR); |
| 530 |
r->generator = generator; |
| 531 |
if (!SCM_NULLP(attrs) || SCM_MVBOXP(item)) { |
| 532 |
ScmMVBox *b = Scm_MakeMVBox(2, SCM_UNDEFINED); |
| 533 |
SCM_MVBOX_SET(b, 0, item); |
| 534 |
SCM_MVBOX_SET(b, 1, copy_attrs(attrs)); |
| 535 |
r->item = SCM_OBJ(b); |
| 536 |
} else { |
| 537 |
r->item = item; |
| 538 |
} |
| 539 |
return SCM_OBJ(r); |
| 540 |
} |
| 541 |
|
| 542 |
ScmObj Scm_MakeLazyPair(ScmObj item, ScmObj generator, ScmObj attrs) |
| 543 |
{ |
| 544 |
/* A check to eliminate the caller accidentally create a 'marked' lazy |
| 545 |
pair. Using cons as a generator to mark it is just a provisional |
| 546 |
solution, so do not count on it. */ |
| 547 |
if (SCM_PAIRP(generator)) { |
| 548 |
Scm_Error("generator must be a procedure, but got: %S", generator); |
| 549 |
} |
| 550 |
return make_lazy_pair(item, generator, attrs); |
| 551 |
} |
| 552 |
|
| 553 |
ScmObj Scm_LazyCons(ScmObj item, ScmObj thunk, ScmObj attrs) |
| 554 |
{ |
| 555 |
/* A 'marked' lazy pair, where thunk returns the next pair instead of |
| 556 |
next item. Provisionally, we insert extra indirection in generator |
| 557 |
slot to mark it. It may change in future, so external code shouldn't |
| 558 |
count on it. */ |
| 559 |
return make_lazy_pair(item, SCM_LIST1(thunk), attrs); |
| 560 |
} |
| 561 |
|
| 562 |
/* This can return () */ |
| 563 |
static ScmObj generator_to_lazy_pair(ScmObj generator) |
| 564 |
{ |
| 565 |
ScmVM *vm = Scm_VM(); |
| 566 |
int lazy_cons = FALSE; |
| 567 |
|
| 568 |
if (SCM_PAIRP(generator)) { |
| 569 |
/* 'marked' */ |
| 570 |
generator = SCM_CAR(generator); |
| 571 |
lazy_cons = TRUE; |
| 572 |
} |
| 573 |
|
| 574 |
/* This may be called with incomplete VM stack, so we protect it. */ |
| 575 |
int extra_frame_pushed = Scm__VMProtectStack(vm); |
| 576 |
|
| 577 |
ScmObj val = Scm_ApplyRec0(generator); |
| 578 |
ScmObj r = SCM_NIL; |
| 579 |
|
| 580 |
if (!lazy_cons) { |
| 581 |
/* standard lazy pair. val is the next item. */ |
| 582 |
if (SCM_EOFP(val)) { |
| 583 |
r = SCM_NIL; |
| 584 |
} else { |
| 585 |
ScmObj attrs = ((vm->numVals > 1) |
| 586 |
? vm->vals[0] /* second value */ |
| 587 |
: SCM_NIL); |
| 588 |
r = Scm_MakeLazyPair(val, generator, attrs); |
| 589 |
} |
| 590 |
} else { |
| 591 |
/* Generator returns lazy pair diretly. |
| 592 |
Check LAZY_PAIR_P first to avoid forcing it */ |
| 593 |
if (SCM_LAZY_PAIR_P(val) || SCM_LISTP(val)) { |
| 594 |
r = val; |
| 595 |
} |
| 596 |
/* If lcons's second argument doesn't yield a () or a pair, |
| 597 |
we just treat it as if () is returned. Since it is delayed |
| 598 |
evaluation, raising error won't help. */ |
| 599 |
} |
| 600 |
vm->numVals = 1; /* make sure the extra vals won't leak out */ |
| 601 |
if (extra_frame_pushed) Scm__VMUnprotectStack(vm); |
| 602 |
return r; |
| 603 |
} |
| 604 |
|
| 605 |
ScmObj Scm_GeneratorToLazyPair(ScmObj generator) |
| 606 |
{ |
| 607 |
/* A check to eliminate the caller accidentally create a 'marked' lazy |
| 608 |
pair. Using cons as a generator to mark it is just a provisional |
| 609 |
solution, so do not count on it. */ |
| 610 |
if (SCM_PAIRP(generator)) { |
| 611 |
Scm_Error("generator must be a procedure, but got: %S", generator); |
| 612 |
} |
| 613 |
return generator_to_lazy_pair(generator); |
| 614 |
} |
| 615 |
|
| 616 |
#define REAL_LAZY_PAIR(obj) \ |
| 617 |
(ScmRealLazyPair*)((char*)(obj) - offsetof(ScmRealLazyPair, data)) |
| 618 |
#define XPAIR_DESC() \ |
| 619 |
(ScmAtomicWord)SCM_CLASS2TAG(Scm__GetDefaultExtendedPairDesctiptor()) |
| 620 |
|
| 621 |
/* Force a lazy pair. |
| 622 |
NB: When an error occurs during forcing, we release the lock of the |
| 623 |
pair, so that the pair can be forced again. However, the generator |
| 624 |
has already caused some side-effect before the error, so the next |
| 625 |
forcing may not yield a correct next value. Another plausible option |
| 626 |
is to mark the pair 'unforcible' permanently, by lp->owner == (AO_t)2, |
| 627 |
and let subsequent attempt of forcing the pair fail. |
| 628 |
*/ |
| 629 |
ScmObj Scm_ForceLazyPair(volatile ScmLazyPair *obj) |
| 630 |
{ |
| 631 |
volatile ScmRealLazyPair * volatile lp = REAL_LAZY_PAIR(obj); |
| 632 |
static const ScmTimeSpec req = {0, 1000000}; |
| 633 |
ScmTimeSpec rem; |
| 634 |
ScmVM *vm = Scm_VM(); |
| 635 |
|
| 636 |
do { |
| 637 |
ScmAtomicWord zero = 0; |
| 638 |
if (Scm_AtomicCompareExchange(&lp->owner, &zero, SCM_WORD(vm))) { |
| 639 |
/* Here we own the lazy pair. */ |
| 640 |
volatile ScmObj item = lp->data.item; |
| 641 |
volatile ScmObj attrs = SCM_NIL; |
| 642 |
if (SCM_MVBOXP(item)) { |
| 643 |
attrs = SCM_MVBOX_VALUES(item)[1]; |
| 644 |
item = SCM_MVBOX_VALUES(item)[0]; |
| 645 |
} |
| 646 |
|
| 647 |
SCM_UNWIND_PROTECT { |
| 648 |
lp->data.item = generator_to_lazy_pair(lp->data.generator); |
| 649 |
lp->data.generator = attrs; |
| 650 |
lp->owner = XPAIR_DESC(); |
| 651 |
Scm_AtomicThreadFence(); |
| 652 |
SCM_SET_CAR_UNCHECKED(obj, item); /* Overwrite LazyPair tag */ |
| 653 |
} SCM_WHEN_ERROR { |
| 654 |
lp->owner = (ScmAtomicWord)0; /*NB: See above about error handling*/ |
| 655 |
SCM_NEXT_HANDLER; |
| 656 |
} SCM_END_PROTECT; |
| 657 |
return SCM_OBJ(&lp->data); /* lp is now an (extended) pair */ |
| 658 |
} |
| 659 |
/* Check if we're already working on forcing this pair. Unlike |
| 660 |
force/delay, We don't allow recursive forcing of lazy pair. |
| 661 |
Since generators are supposed to be called every time to yield |
| 662 |
a new value, so it is ambiguous what value should be returned |
| 663 |
if a generator calls itself recursively. */ |
| 664 |
if (SCM_WORD(lp->owner) == SCM_WORD(vm)) { |
| 665 |
/* NB: lp->owner will be reset by the original caller of |
| 666 |
the generator. */ |
| 667 |
Scm_Error("Attempt to recursively force a lazy pair."); |
| 668 |
} |
| 669 |
/* Somebody's already working on forcing. Let's wait for it |
| 670 |
to finish, or to abort. */ |
| 671 |
while (SCM_HTAG(obj) == 7 && lp->owner != 0) { |
| 672 |
Scm_NanoSleep(&req, &rem); |
| 673 |
} |
| 674 |
} while (lp->owner == 0); /* we retry if the previous owner abandoned. */ |
| 675 |
return SCM_OBJ(lp); |
| 676 |
} |
| 677 |
|
| 678 |
int Scm_PairP(ScmObj x) |
| 679 |
{ |
| 680 |
if (SCM_LAZY_PAIR_P(x)) { |
| 681 |
Scm_ForceLazyPair(SCM_LAZY_PAIR(x)); |
| 682 |
return TRUE; |
| 683 |
} else { |
| 684 |
return FALSE; |
| 685 |
} |
| 686 |
} |