Threads, Mutexes, Asyncs and Dynamic Roots
******************************************

[FIXME: This is pasted in from Tom Lord's original guile.texi chapter plus the Cygnus programmer's manual; it should be *very* carefully reviewed and largely reorganized.]

Arbiters
========

Arbiters are synchronization objects.  They are created with make-arbiter.  Two or more threads can synchronize on an arbiter by trying to lock it using try-arbiter.  This call will succeed if no other thread has called try-arbiter on the arbiter yet, otherwise it will fail and return #f.  Once an arbiter is successfully locked, it cannot be locked by another thread until the thread holding the arbiter calls release-arbiter to unlock it.

 -- Scheme Procedure: make-arbiter name
 -- C Function: scm_make_arbiter (name)
     Return an object of type arbiter and name NAME. Its state is initially unlocked.  Arbiters are a way to achieve process synchronization.

 -- Scheme Procedure: try-arbiter arb
 -- C Function: scm_try_arbiter (arb)
     Return #t and lock the arbiter ARB if the arbiter was unlocked. Otherwise, return #f.

 -- Scheme Procedure: release-arbiter arb
 -- C Function: scm_release_arbiter (arb)
     Return #t and unlock the arbiter ARB if the arbiter was locked. Otherwise, return #f.

Asyncs
======

Asyncs are a means of deferring the excution of Scheme code until it is safe to do so.

Guile provides two kinds of asyncs that share the basic concept but are otherwise quite different: system asyncs and user asyncs.  System asyncs are integrated into the core of Guile and are executed automatically when the system is in a state to allow the execution of Scheme code. For example, it is not possible to execute Scheme code in a POSIX signal handler, but such a signal handler can queue a system async to be executed in the near future, when it is safe to do so.

System asyncs can also be queued for threads other than the current one. This way, you can cause threads to asynchronously execute arbitrary code.

User asyncs offer a convenient means of queueing procedures for future execution and triggering this execution.  They will not be executed automatically.

System asyncs
-------------

To cause the future asynchronous execution of a procedure in a given thread, use system-async-mark.

Automatic invocation of system asyncs can be temporarily disabled by calling call-with-blocked-asyncs.  This function works by temporarily increasing the async blocking level of the current thread while a given procedure is running.  The blocking level starts out at zero, and whenever a safe point is reached, a blocking level greater than zero will prevent the execution of queued asyncs.

Analogously, the procedure call-with-unblocked-asyncs will temporarily decrease the blocking level of the current thread.  You can use it when you want to disable asyncs by default and only allow them temporarily.

In addition to the C versions of call-with-blocked-asyncs and call-with-unblocked-asyncs, C code can use scm_with_blocked_asyncs and scm_with_unblocked_asyncs inside a frame (see Frames) to block or unblock system asyncs temporarily.

 -- Scheme Procedure: system-async-mark proc [thread]
 -- C Function: scm_system_async_mark (proc)
 -- C Function: scm_system_async_mark_for_thread (proc, thread)
     Mark PROC (a procedure with zero arguments) for future execution in THREAD.  When PROC has already been marked for THREAD but has not been executed yet, this call has no effect. When THREAD is omitted, the thread that called system-async-mark is used.

     This procedure is not safe to be called from signal handlers.  Use scm_sigaction or scm_sigaction_for_thread to install signal handlers.

 -- Scheme Procedure: call-with-blocked-asyncs proc
 -- C Function: scm_call_with_blocked_asyncs (proc)
 -- C Function: void *scm_c_call_with_blocked_asyncs (void * (*proc) (void *data), void *data)
     Call PROC and block the execution of system asyncs by one level for the current thread while it is running.  Return the value returned by PROC.  For the first two variants, call PROC with no arguments; for the third, call it with DATA.

 -- Scheme Procedure: call-with-unblocked-asyncs proc
 -- C Function: scm_call_with_unblocked_asyncs (proc)
 -- C Function: void *scm_c_call_with_unblocked_asyncs (void *(*p) (void *d), void *d)
     Call PROC and unblock the execution of system asyncs by one level for the current thread while it is running.  Return the value returned by PROC.  For the first two variants, call PROC with no arguments; for the third, call it with DATA.

 -- C Function: void scm_frame_block_asyncs ()
     This function must be used inside a pair of calls to scm_frame_begin and scm_frame_end (see Frames). During the dynamic extent of the frame, asyncs are blocked by one level.

 -- C Function: void scm_frame_unblock_asyncs ()
     This function must be used inside a pair of calls to scm_frame_begin and scm_frame_end (see Frames). During the dynamic extent of the frame, asyncs are unblocked by one level.

User asyncs
-----------

A user async is a pair of a thunk (a parameterless procedure) and a mark.  Setting the mark on a user async will cause the thunk to be executed when the user async is passed to run-asyncs.  Setting the mark more than once is satisfied by one execution of the thunk.

User asyncs are created with async.  They are marked with async-mark.

 -- Scheme Procedure: async thunk
 -- C Function: scm_async (thunk)
     Create a new user async for the procedure THUNK.

 -- Scheme Procedure: async-mark a
 -- C Function: scm_async_mark (a)
     Mark the user async A for future execution.

 -- Scheme Procedure: run-asyncs list_of_a
 -- C Function: scm_run_asyncs (list_of_a)
     Execute all thunks from the marked asyncs of the list LIST_OF_A.

Dynamic Roots
=============

A dynamic root is a root frame of Scheme evaluation. The top-level repl, for example, is an instance of a dynamic root.

Each dynamic root has its own chain of dynamic-wind information.  Each has its own set of continuations, jump-buffers, and pending CATCH statements which are inaccessible from the dynamic scope of any other dynamic root.

In a thread-based system, each thread has its own dynamic root.  Therefore, continuations created by one thread may not be invoked by another.

Even in a single-threaded system, it is sometimes useful to create a new dynamic root.  For example, if you want to apply a procedure, but to not allow that procedure to capture the current continuation, calling the procedure under a new dynamic root will do the job.

 -- Scheme Procedure: call-with-dynamic-root thunk handler
 -- C Function: scm_call_with_dynamic_root (thunk, handler)
     Evaluate (thunk) in a new dynamic context, returning its value.

     If an error occurs during evaluation, apply HANDLER to the arguments to the throw, just as throw would.  If this happens, HANDLER is called outside the scope of the new root -- it is called in the same dynamic context in which call-with-dynamic-root was evaluated.

     If THUNK captures a continuation, the continuation is rooted at the call to THUNK.  In particular, the call to call-with-dynamic-root is not captured.  Therefore, call-with-dynamic-root always returns at most one time.

     Before calling THUNK, the dynamic-wind chain is un-wound back to the root and a new chain started for THUNK.  Therefore, this call may not do what you expect:

          ;; Almost certainly a bug:
          (with-output-to-port
           some-port

           (lambda ()
             (call-with-dynamic-root
              (lambda ()
                (display 'fnord)
                (newline))
              (lambda (errcode) errcode))))

     The problem is, on what port will fnord be displayed?  You might expect that because of the with-output-to-port that it will be displayed on the port bound to some-port.  But it probably won't -- before evaluating the thunk, dynamic winds are unwound, including those created by with-output-to-port. So, the standard output port will have been re-set to its default value before display is evaluated.

     (This function was added to Guile mostly to help calls to functions in C libraries that can not tolerate non-local exits or calls that return multiple times.  If such functions call back to the interpreter, it should be under a new dynamic root.)

 -- Scheme Procedure: dynamic-root
 -- C Function: scm_dynamic_root ()
     Return an object representing the current dynamic root.

     These objects are only useful for comparison using eq?. They are currently represented as numbers, but your code should in no way depend on this.

 -- Scheme Procedure: quit [exit_val]
     Throw back to the error handler of the current dynamic root.

     If integer EXIT_VAL is specified and if Guile is being used stand-alone and if quit is called from the initial dynamic-root, EXIT_VAL becomes the exit status of the Guile process and the process exits.

When Guile is run interactively, errors are caught from within the read-eval-print loop.  An error message will be printed and abort called.  A default set of signal handlers is installed, e.g., to allow user interrupt of the interpreter.

It is possible to switch to a "batch mode", in which the interpreter will terminate after an error and in which all signals cause their default actions.  Switching to batch mode causes any handlers installed from Scheme code to be removed.  An example of where this is useful is after forking a new process intended to run non-interactively.

 -- Scheme Procedure: batch-mode?
     Returns a boolean indicating whether the interpreter is in batch mode.

 -- Scheme Procedure: set-batch-mode?! arg
     If ARG is true, switches the interpreter to batch mode. The #f case has not been implemented.

Threads
=======

Guile threads are implemented using POSIX threads, they run pre-emptively and concurrently through both Scheme code and system calls.  The only exception is for garbage collection, where all threads must rendezvous.

Low level thread primitives
---------------------------

 -- Scheme Procedure: call-with-new-thread thunk error-handler
     Evaluate (thunk) in a new thread, and new dynamic context, returning a new thread object representing the thread.

     If an error occurs during evaluation, call error-handler, passing it an error code.  If this happens, the error-handler is called outside the scope of the new root -- it is called in the same dynamic context in which with-new-thread was evaluated, but not in the caller's thread.

     All the evaluation rules for dynamic roots apply to threads.

 -- Scheme Procedure: join-thread thread
     Suspend execution of the calling thread until the target THREAD terminates, unless the target THREAD has already terminated.

 -- Scheme Procedure: yield
     If one or more threads are waiting to execute, calling yield forces an immediate context switch to one of them. Otherwise, yield has no effect.

 -- Scheme Procedure: make-mutex
     Create a new mutex object.

 -- Scheme Procedure: lock-mutex mutex
     Lock MUTEX. If the mutex is already locked, the calling thread blocks until the mutex becomes available. The function returns when the calling thread owns the lock on MUTEX.  Locking a mutex that a thread already owns will succeed right away and will not block the thread.  That is, Guile's mutexes are recursive.

     When a system async is activated for a thread that is blocked in a call to lock-mutex, the waiting is interrupted and the async is executed.  When the async returns, the waiting is resumed.

 -- Scheme Procedure: try-mutex mutex
     Try to lock MUTEX. If the mutex is already locked by someone else, return #f.  Else lock the mutex and return #t.

 -- Scheme Procedure: unlock-mutex mutex
     Unlocks MUTEX if the calling thread owns the lock on MUTEX.  Calling unlock-mutex on a mutex not owned by the current thread results in undefined behaviour. Once a mutex has been unlocked, one thread blocked on MUTEX is awakened and grabs the mutex lock.  Every call to lock-mutex by this thread must be matched with a call to unlock-mutex.  Only the last call to unlock-mutex will actually unlock the mutex.

 -- Scheme Procedure: make-condition-variable
     Make a new condition variable.

 -- Scheme Procedure: wait-condition-variable cond-var mutex [time]
     Wait until COND-VAR has been signalled.  While waiting, MUTEX is atomically unlocked (as with unlock-mutex) and is locked again when this function returns.  When TIME is given, it specifies a point in time where the waiting should be aborted.  It can be either a integer as returned by current-time or a pair as returned by gettimeofday.  When the waiting is aborted, #f is returned.  When the condition variable has in fact been signalled, #t is returned.  The mutex is re-locked in any case before wait-condition-variable returns.

     When a system async is activated for a thread that is blocked in a call to wait-condition-variable, the waiting is interrupted, the mutex is locked, and the async is executed.  When the async returns, the mutex is unlocked again and the waiting is resumed.

 -- Scheme Procedure: signal-condition-variable cond-var
     Wake up one thread that is waiting for CV.

 -- Scheme Procedure: broadcast-condition-variable cond-var
     Wake up all threads that are waiting for CV.

Higher level thread procedures
------------------------------

Higher level thread procedures are available by loading the (ice-9 threads) module.  These provide standardized thread creation and mutex interaction.

 -- macro: make-thread proc [args...]
     Apply PROC to ARGS in a new thread formed by call-with-new-thread using a default error handler that display the error to the current error port.

 -- macro: begin-thread first [rest...]
     Evaluate forms FIRST and REST in a new thread formed by call-with-new-thread using a default error handler that display the error to the current error port.

 -- macro: with-mutex m [body...]
     Lock mutex M, evaluate BODY, and then unlock M. These sub-operations form the branches of a dynamic-wind.

 -- macro: monitor body...
     Evaluate BODY, with a mutex locked so only one thread can execute that code at any one time.  Each monitor form has its own private mutex and the locking is done as per with-mutex above.  The return value is the return from the last form in BODY.

     The term ``monitor'' comes from operating system theory, where it means a particular bit of code managing access to some resource and which only ever executes on behalf of one process at any one time.

C level thread interface
------------------------

You can create and manage threads, mutexes, and condition variables with the C versions of the primitives above.  For example, you can create a mutex with scm_make_mutex and lock it with scm_lock_mutex.  In addition to these primitives there is also a second set of primitives for threading related things.  These functions and data types are only available from C and can not be mixed with the first set from above.  However, they might be more efficient and can be used in situations where Scheme data types are not allowed or are inconvenient to use.

Furthermore, they are the primitives that Guile relies on for its own higher level threads.  By reimplementing them, you can adapt Guile to different low-level thread implementations.

C code in a thread must call a libguile function periodically.  When one thread finds garbage collection is required, it waits for all threads to rendezvous before doing that GC.  Such a rendezvous is checked within libguile functions.  If C code wants to sleep or block in a thread it should use one of the libguile functions provided.

Only threads created by Guile can use the libguile functions.  Threads created directly with say pthread_create are unknown to Guile and they cannot call libguile.  The stack in such foreign threads is not scanned during GC, so SCM values generally cannot be held there.

 -- C Data Type: scm_t_thread
     This data type represents a thread, to be used with scm_thread_create, etc.

 -- C Function: int scm_thread_create (scm_t_thread *t, void (*proc)(void *), void *data)
     Create a new thread that will start by calling PROC, passing it DATA.  A handle for the new thread is stored in T, which must be non-NULL.  The thread terminated when PROC returns. When the thread has not been detached, its handle remains valid after is has terminated so that it can be used with SCM_THREAD_JOIN, for example.  When it has been detached, the handle becomes invalid as soon as the thread terminates.

 -- C Function: void scm_thread_detach (scm_t_thread t)
     Detach the thread T.  See scm_thread_create.

 -- C Function: void scm_thread_join (scm_t_thread t)
     Wait for thread T to terminate.  The thread must not have been detached at the time that scm_thread_join is called, but it might have been detached by the time it terminates.

 -- C Function: scm_t_thread scm_thread_self ()
     Return the handle of the calling thread.

 -- C Data Type: scm_t_mutex
     This data type represents a mutex, to be used with scm_mutex_init, etc.

 -- C Function: void scm_mutex_init (scm_t_mutex *m)
     Initialize the mutex structure pointed to by M.

 -- C Function: void scm_mutex_destroy (scm_t_mutex *m)
     Deallocate all resources associated with M.

 -- C Function: void scm_mutex_lock (scm_t_mutex *m)
     Lock the mutex M.  When it is already locked by a different thread, wait until it becomes available.  Locking a mutex that is already locked by the current threads is not allowd and results in undefined behavior.  The mutices are not guaranteed to be fair.  That is, a thread that attempts a lock after yourself might be granted it before you.

 -- C Function: int scm_mutex_trylock (scm_t_mutex *m)
     Lock M as with scm_mutex_lock but don't wait when this does succeed immediately.  Returns non-zero when the mutex could in fact be locked , and zero when it is already locked by some other thread.

 -- C Function: void scm_mutex_unlock (scm_t_mutex *m)
     Unlock the mutex M.  The mutex must have been locked by the current thread, else the behavior is undefined.

 -- C Data Type: scm_t_cond
     This data type represents a condition variable, to be used with scm_cond_init, etc.

 -- C Function: void scm_cond_init (scm_t_cond *c)
     Initialize the mutex structure pointed to by C.

 -- C Function: void scm_cond_destroy (scm_t_cond *c)
     Deallocate all resources associated with C.

 -- C Function: void scm_cond_wait (scm_t_cond *c, scm_t_mutex *m)
     Wait for C to be signalled.  While waiting M is unlocked and locked again before scm_cond_wait returns.

 -- C Function: void scm_cond_timedwait (scm_t_cond *c, scm_t_mutex *m, timespec *abstime)
     Wait for C to be signalled as with scm_cond_wait but don't wait longer than the point in time specified by ABSTIME. when the waiting is aborted, zero is returned; non-zero else.

 -- C Function: void scm_cond_signal (scm_t_cond *c)
     Signal the condition variable C.  When one or more threads are waiting for it to be signalled, select one arbitrarily and let its wait succeed.

 -- C Function: void scm_cond_broadcast (scm_t_cond *c)
     Signal the condition variable C.  When there are threads waiting for it to be signalled, wake them all up and make all their waits succeed.

 -- C Type: scm_t_key
     This type represents a key for a thread-specific value.

 -- C Function: void scm_key_create (scm_t_key *keyp)
     Create a new key for a thread-specific value.  Each thread has its own value associated to such a handle.  The new handle is stored into KEYP, which must be non-NULL.

 -- C Function: void scm_key_delete (scm_t_key key)
     This function makes KEY invalid as a key for thread-specific data.

 -- C Function: void scm_key_setspecific (scm_t_key key, const void *value)
     Associate VALUE with KEY in the calling thread.

 -- C Function: int scm_key_getspecific (scm_t_key key)
     Return the value currently associated with KEY in the calling thread.  When scm_key_setspecific has not yet been called in this thread with this key, NULL is returned.

 -- C Function: int scm_thread_select (...)
     This function does the same thing as the system's select function, but in a way that is friendly to the thread implementation. You should call it in preference to the system select.

Fluids
======

Fluids are objects to store values in.  They have a few properties which make them useful in certain situations: Fluids can have one value per dynamic root (see Dynamic Roots), so that changes to the value in a fluid are only visible in the same dynamic root.  Since threads are executed in separate dynamic roots, fluids can be used for thread local storage (see Threads).

Fluids can be used to simulate the desirable effects of dynamically scoped variables.  Dynamically scoped variables are useful when you want to set a variable to a value during some dynamic extent in the execution of your program and have them revert to their original value when the control flow is outside of this dynamic extent.  See the description of with-fluids below for details.

New fluids are created with make-fluid and fluid? is used for testing whether an object is actually a fluid.  The values stored in a fluid can be accessed with fluid-ref and fluid-set!.

 -- Scheme Procedure: make-fluid
 -- C Function: scm_make_fluid ()
     Return a newly created fluid. Fluids are objects of a certain type (a smob) that can hold one SCM value per dynamic root.  That is, modifications to this value are only visible to code that executes within the same dynamic root as the modifying code.  When a new dynamic root is constructed, it inherits the values from its parent.  Because each thread executes in its own dynamic root, you can use fluids for thread local storage.

 -- Scheme Procedure: fluid? obj
 -- C Function: scm_fluid_p (obj)
     Return #t iff OBJ is a fluid; otherwise, return #f.

 -- Scheme Procedure: fluid-ref fluid
 -- C Function: scm_fluid_ref (fluid)
     Return the value associated with FLUID in the current dynamic root.  If FLUID has not been set, then return #f.

 -- Scheme Procedure: fluid-set! fluid value
 -- C Function: scm_fluid_set_x (fluid, value)
     Set the value associated with FLUID in the current dynamic root.

with-fluids* temporarily changes the values of one or more fluids, so that the given procedure and each procedure called by it access the given values.  After the procedure returns, the old values are restored.

 -- Scheme Procedure: with-fluids* fluids values thunk
 -- C Function: scm_with_fluids (fluids, values, thunk)
     Set FLUIDS to VALUES temporary, and call THUNK. FLUIDS must be a list of fluids and VALUES must be the same number of their values to be applied.  Each substitution is done in the order given.  THUNK must be a procedure with no argument. it is called inside a dynamic-wind and the fluids are set/restored when control enter or leaves the established dynamic extent.

 -- Scheme Macro: with-fluids ((fluid value) ...) body...
     Execute BODY... while each FLUID is set to the corresponding VALUE.  Both FLUID and VALUE are evaluated and FLUID must yield a fluid.  BODY... is executed inside a dynamic-wind and the fluids are set/restored when control enter or leaves the established dynamic extent.

 -- C Function: SCM scm_c_with_fluids (SCM fluids, SCM vals, SCM (*cproc)(void *), void *data)
 -- C Function: SCM scm_c_with_fluid (SCM fluid, SCM val, SCM (*cproc)(void *), void *data)
     The function scm_c_with_fluids is like scm_with_fluids except that it takes a C function to call instead of a Scheme thunk.

     The function scm_c_with_fluid is similar but only allows one fluid to be set instead of a list.

 -- C Function: void scm_frame_fluid (SCM fluid, SCM val)
     This function must be used inside a pair of calls to scm_frame_begin and scm_frame_end (see Frames). During the dynamic extent of the frame, the fluid FLUID is set to VAL.

     More precisely, the value of the fluid is swapped with a `backup' value whenever the frame is entered or left.  The backup value is initialized with the VAL argument.

Futures
=======

Futures are a convenient way to run a calculation in a new thread, and only wait for the result when it's actually needed.

Futures are similar to promises (see Delayed Evaluation), in that they allow mainline code to continue immediately.  But delay doesn't evaluate at all until forced, whereas future starts immediately in a new thread.

 -- syntax: future expr
     Begin evaluating EXPR in a new thread, and return a ``future'' object representing the calculation.

 -- Scheme Procedure: make-future thunk
 -- C Function: scm_make_future (thunk)
     Begin evaluating the call (THUNK) in a new thread, and return a ``future'' object representing the calculation.

 -- Scheme Procedure: future-ref f
 -- C Function: scm_future_ref (f)
     Return the value computed by the future F.  If F has not yet finished executing then wait for it to do so.

Parallel forms
==============

The functions described in this section are available from

     (use-modules (ice-9 threads))

 -- syntax: parallel expr1 ... exprN
     Evaluate each EXPR expression in parallel, each in a new thread. Return the results as a set of N multiple values (see Multiple Values).

 -- syntax: letpar ((var1 expr1) ... (varN exprN)) body...
     Evaluate each EXPR in parallel, each in a new thread, then bind the results to the corresponding VAR variables and evaluate BODY.

     letpar is like let (see Local Bindings), but all the expressions for the bindings are evaluated in parallel.

 -- Scheme Procedure: par-map proc lst1 ... lstN
 -- Scheme Procedure: par-for-each proc lst1 ... lstN
     Call PROC on the elements of the given lists.  par-map returns a list comprising the return values from PROC. par-for-each returns an unspecified value, but waits for all calls to complete.

     The PROC calls are (PROC ELEM1 ... ELEMN), where each ELEM is from the corresponding LST.  Each LST must be the same length.  The calls are made in parallel, each in a new thread.

     These functions are like map and for-each (see List Mapping), but make their PROC calls in parallel.

 -- Scheme Procedure: n-par-map n proc lst1 ... lstN
 -- Scheme Procedure: n-par-for-each n proc lst1 ... lstN
     Call PROC on the elements of the given lists, in the same way as par-map and par-for-each above, but use no more than N new threads at any one time.  The order in which calls are initiated within that threads limit is unspecified.

     These functions are good for controlling resource consumption if PROC calls might be costly, or if there are many to be made.  On a dual-CPU system for instance N=4 might be enough to keep the CPUs utilized, and not consume too much memory.

 -- Scheme Procedure: n-for-each-par-map n sproc pproc lst1 ... lstN
     Apply PPROC to the elements of the given lists, and apply SPROC to each result returned by PPROC.  The final return value is unspecified, but all calls will have been completed before returning.

     The calls made are (SPROC (PPROC ELEM1 ... ELEMN)), where each ELEM is from the corresponding LST.  Each LST must have the same number of elements.

     The PPROC calls are made in parallel, in new threads.  No more than N new threads are used at any one time.  The order in which PPROC calls are initiated within that limit is unspecified.

     The SPROC calls are made serially, in list element order, one at a time.  PPROC calls on later elements may execute in parallel with the SPROC calls.  Exactly which thread makes each SPROC call is unspecified.

     This function is designed for individual calculations that can be done in parallel, but with results needing to be handled serially, for instance to write them to a file.  The N limit on threads controls system resource usage when there are many calculations or when they might be costly.

     It will be seen that n-for-each-par-map is like a combination of n-par-map and for-each,

          (for-each sproc (n-par-map pproc lst1 ... lstN))

     But the actual implementation is more efficient since each SPROC call, in turn, can be initiated once the relevant PPROC call has completed, it doesn't need to wait for all to finish.