Showing posts with label scheme. Show all posts

2011-03-10

Imagining Iteratee IO in Scheme

Oleg's Iteratee IO is an application of collection traversal to stream processing. He has been interested in coming up with a good technique to traverse general collection. I think Iteratee IO is an excellent and exciting application of collection traversal, but it's implemented in Haskell and it's kind of odd that he didn't come up with a Scheme version considering that he was very involved in Scheme.

So, I just had to try bringing it over to Scheme, at the risk of marring his work.

Here's my first attempt at imagining what the Iteratee examples in his slide would look like in Scheme. There are some repetitions that really should be streamlined or reduced in subsequent attempts.

What missing are: 1. lack of error resumption, and 2. resumption of partial computation through Monads. Instead partial computation has to be passed manually on each call.

imagining-iteratee-io-in-scheme.scm

2011-02-17

Dealing with external library and single-threaded runtime environment

My recent works with using external C libraries with chicken and gambit cue me to two problems that are shared by other language implementation that runs on a single OS threads (ruby, phyton, for example).

The problems are: (1) how to not block when calling external C library, (2) how to service callback, and (3)how to service parallel callbacks.

There are many solutions to these problems. The ones that I think can be applied to *nix, windows, osx, ios and android are as follows:
[Assumptions: pthread and pipe are available on the intended platform, and pthread creates threads that do not block other pthread threads. If there is no pthread, use other threading libraries with the above properties]

For the problem of blocking when calling an external library

Setup: Use pthread to create worker threads. Create two pipes for each worker thread. One for signaling to worker thread of a pending request, the other for signalling the master of a waiting response. Each thread should have its own mailbox. The mailbox should be able to take request and response data. It can be as simple as having void* slots. As a worker thread can work only with a request at a time, it does not have to be assigned a perennial mailbox. A new one can be created for each request and a pointer to it is send in the request notification signal. This simplifies the management of the mailboxes.

Operation: Use FFI to populate the mailbox's request slot with pertinent data. Send a request notification signal to an idle worker. If using a temporary mailbox, pass along a pointer to it in the signal. At this point, there should be a language thread that monitors the response notification pipe. It could be a dedicated thread or the current thread.

An idle worker thread should block reading the request notification pipe for signal. If a signal is received, it should access its mailbox for request data and proceed accordingly. The response should be put in the mailbox's response slot and a signal should be send to the response notification pipe.

For the problem of accepting [parallel] callbacks

It would have been nice to be able to call into the implementation directly from the external library. But it won't work with gambit and chicken which impose its own structure on the stack to support TCO. Even if it is not a factor, it will not support parallel callbacks because the implementations will perform unsynchronized modifications to internal global structures.

So, a solution to this is to use mailbox and pthread again. Presumably the parallel callbacks are done through pthread. Each callback is performed on a different pthread thread.

Setup: this time only one pipe is needed. It will be used to send request notification from external to scheme-land.

Operation: upon a callback, create a new mailbox. Stuff a pthread conditional variable in there along with request data. Send a request notification with a pointer to the mailbox. Make sure that the writing to the pipe is synchronized so that only one thread writes at a time. Then wait on the CV.

On scheme land, the thread that monitors the request notification pipe should spawn a new scheme thread to handle the request. After the request is processed and response put in the appropriate mailbox slot, signal the CV and be done.

Back to the pthread thread: upon the CV signal, the thread execution is resumed and can return from the callback properly.

2006-11-05

Continuation support in ruby

I heard today that Ruby 2.0 is going to abandon support for continuation, at least initially until things have stabilised a bit. It is no longer a news, it is just that I have not been active in Ruby community for a while.

The Problem with Continuation Support in Ruby 1.x

My initial reaction upon hearing that was "What a pity". On second thought, I realised that dropping continuation initially makes sense. The support for continuation in Ruby 1.x is missing an ensure procedure that is continuation-friendly; meaning one that is called only once one a given path is no longer accessible.

$create_cont_k=nil

def do_something(k)
  puts "Do something called"
  $create_cont_k = k
end

def do_something_else
  return unless $create_cont_k
  puts "Do something else called"
  k = $create_cont_k
  $create_cont_k = nil
  k.call
end


def create_cont
  callcc{|create_cont_k| do_something(create_cont_k)}
ensure
  puts "Ensure called"
end

create_cont
do_something_else

# /tmp $ ruby1.8  /tmp/ensure-run-multiply.rb 
# Do something called
# Ensure called
# Do something else called
# Ensure called

A proper ensure mechanism that supports explicit continuation formation system, like Ruby 1.8, would have produced:

# /tmp $ ruby1.8  /tmp/ensure-run-multiply.rb 
# Do something called
# Do something else called
# Ensure called

Notice how "ensure" is supposed to be called only once. I have a sample implementation of such continuation-observant ensure mechanism in system-managed-unwind-protect-in-sisc for SISC, a scheme implementation.

"But, but, what if I really want something like ensure that is called each time a code section is called?", you asked. In other words, you want something like Ruby 1.8's multiple-shot ensure in this new world of single-shot ensure.

That is not a problem and don't think that you are being unreasonable for asking this feature. It is useful to be able to guarantee execution of some code upon exiting a dynamic environment.

A dynamic environment is the environment that your program can access at any given time. The environment can change with each instruction executed by the machine.

But such one-sided guarantee does not really do anything interesting. How about a guarantee that some code is also executed upon entering a dynamic environment, thus having a symmetric aspect.

Scheme has dynamic-wind that does the above:

(define *CREATE-CONT-K* #f)

(define (do-something k)
  (display "Do something called\n")
  (set! *CREATE-CONT-K* k))

(define (do-something-else)
  (when *CREATE-CONT-K*
    (display "Do something else called\n")
    (let ((k *CREATE-CONT-K*))
      (set! *CREATE-CONT-K* #f)
      (k))))

(define (create-cont)
  (dynamic-wind
      (lambda () (display "Entering...\n"))
      (lambda ()
        (call/cc
         (lambda (create-cont-k)
           (do-something create-cont-k))))
      (lambda () (display "Exiting...\n"))))

(create-cont)
(do-something-else)

;; /tmp $ sisc -x /tmp/dynwind.scm 
;; Entering...
;; Do something called
;; Exiting...
;; Do something else called
;; Entering...
;; Exiting...

The utility in having a in/excursion guard can't be understated. In SRFI-34, dynamic-wind is used to install a custom exception handler. Yes, a custom exception handler; this is probably a strange concept for some people. Why would one have different exception handlers on the same piece of code? The first reason is "why not?". A dynamic language restricted to having a static exception handler feels incomplete. The second reason is more practical. Since you can in/ex-curse from/to any context (via calling a provided continuation object), how an exception is handled in a given context is not necessarily the same as in other different contexts.

Thus, a complete example of how multiple-shot and single-shot ensure example co-existing (sorry, in scheme as there is no Ruby implementation with single-shot ensure yet):

(class-path-extension-append! (list "file:/home/ysantoso/share/project/scheme/unwind-protect/"))

(require-library 'unwind-protect)
(import unwind-protect)

(import s2j)
(define (do-gc) ((generic-java-method '|gc|) (java-null (java-class '|java.lang.System|))))

;; do-something and do-something-else functions are elided for brevity

(define (create-cont)
  (dynamic-wind
      (lambda () (display "Entering...\n"))
      (lambda ()
        (unwind-protect
          (call/cc
            (lambda (create-cont-k)
              (do-something create-cont-k)))
         (display "Ensure\n")))
      (lambda () (display "Exiting...\n"))))


(create-cont)
(do-gc)
(do-something-else)
(do-gc)

;; /tmp $ sisc -x /tmp/dynwind.scm 
;; Entering...
;; Do something called
;; Exiting...
;; Do something else called
;; Entering...
;; Exiting...
;; Ensure

Notice how "ensure" is called just once even though there are two incursion into the protected code block.

The last deficiency in Ruby 1.x is the restriction that a continuation has to be resumed from the same thread that reifies it.

def do_something_else
  return unless $create_cont_k
  puts "Do something else called"
  k = $create_cont_k
  $create_cont_k = nil
  t=Thread.new { k.call}
  t.join
end

# /tmp $ ruby1.8  ensure-run-multiply.rb 
# Do something called
# Ensure called
# Do something else called
# ensure-run-multiply.rb:13:in `call': continuation called across threads (RuntimeError)
#       from ensure-run-multiply.rb:14:in `join'
#       from ensure-run-multiply.rb:14:in `do_something_else'
#       from ensure-run-multiply.rb:25

(originally from http://microjet.ath.cx/WebWiki/2006.11.05_Continuation_Support_in_Ruby.html)

2006-10-24

System-managed UNWIND-PROTECT in SISC

FORM: (unwind-protect BODYFORM UNWINDFORMS...)
Scheme's call/cc provides a flexible way to control execution flow. Its flexibility allows for different approaches to implementing unwind-protect.

Dorai Sitaram's "Unwind-Protect in Portable Scheme" shows a portable implementation of unwind-protect. It does so by constricting the flexibility of call/cc. User would have to specify when to call the unwindforms part of unwind-protect. In certain situations, it is desirable to have this level of control. In others, it would be akin to having to manually manage memory allocation.

The other approach is having an automatically executed unwindforms such as the one described by Taylor R. Campbell, "2006-05-01 On control brackets and resource release". Having the system manages the execution of unwindforms is more in line to traditional implementations of unwind-protect in other languages. It is this approach that interests me.

By associating a protector cell to the bodyform, we can rely on the GC mechanism cleaning up the protector cell once =bodyform='s continuation is no longer reachable. If it is no longer reachable, then it is safe to execute the unwindforms.

He also describes an optimisation of a common case where =bodyform='s continuation is never reified. Without it, there is only one =bodyform='s continuation and once the execution passes through the end of bodyform, it is safe to continue to unwindforms.

In his 'blog', he provides a sample implementation for MIT-Scheme. The implementation would have to be platform-specific since it hooks into the GC. However, it is easy to port that to other platform.

An Implementation in SISC

As a user of SISC, and as someone who has seen many applications (including SISCWeb) using dynamic-wind as a poor-man's unwind-protect, having a system-managed unwind-protect in SISC is a good idea. As I was not aware of any existing implementation, I proceeded to create one using Taylor Campbell's example as the starting point.

To hook into Java's GC finalisation process, I used GCHook.java. Then unwind-protect.scm implements the rest.

unwind-protect-in-sisc

(originally from http://microjet.ath.cx/WebWiki/2006.10.24_UnwindProtectInSISC.html and http://microjet.ath.cx/WebWiki/2006.10.27_UnwindProtectInSISCPart2.html)