shift/reset with correct dynamic environment for Gambit

I think there's a lot of potential for delimited continuations in graphics engines, and I plan on using them in what I'm working on. I am using Gambit Scheme however, which does not have a full shift/reset implementation. For the past couple weeks I looked into implementing shift/reset for Gambit (with a fixed dynamic environment), and I got it to work! I posted the following message on the Gambit list earlier today:

"Hello everyone,

I have been studying delimited continuations recently. After being
blissfully enlightened, I really wanted to have them in Gambit (with a
*correct* dynamic environment). I wasn't sure if this was possible
non-natively though (at least safely), because Gambit's dynamic
environment is somewhat complex, and I have to be able to
destructively manipulate the dynamic environment to make sure the
delimited continuation truly has its own dynamic environment 'slice'.

However, I figured out how to (hopefully safely) manipulate Gambit's
dynamic environment, and I have a full implementation of shift/reset
running in Gambit. This implementation is based off Oleg Kiselyov's
work; his paper is here:

http://okmij.org/ftp/Computation/dynamic-binding.html#DDBinding

I am not sure of the performance implications of the Gambit version of
shift/reset. I am unhappy with how much has to happen per reset or
shift, but such is the cost of a non-native implementation.
Unfortunately it goes against the grain of Gambit; after looking at
some of Gambit's internals, Marc obviously has fine-tuned the code to
be very efficient, and each reset or shift call is quite heavy
compared to call/cc. Marc... what are thoughts on a native
implementation of shift/reset?

I included some tests which show that the dynamic environment does
act the way we expect. [see 'tests.scm', snipped the tests out for the sake of this post]

If you are a zipped tar kind of guy:
http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-gambit.tar.gz

Or you just want the files:
http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-fixed.scm
http://james.tech.coptix.com/files/shift-reset-gambit/shift-reset-broken.scm
http://james.tech.coptix.com/files/shift-reset-gambit/tests.scm

'shift-reset-fixed.scm' contains the full shift/reset implementation.
'shift-reset-broken.scm' contains a naive implementation with a broken
dynamic environment.
'tests.scm' has some tests to show how the dynamic env is fixed. Note
that at the top you can include 'shift-reset-broken.scm' instead of
the fixed version to see how the dynamic env would normally be broken.

James"

Scheme Raytracer Optimized

Marc Feeley, the creator of Gambit Scheme, tweaked my raytracer and got it to run twice as fast. Here's what he said about it:

"The main thing that helped performance is the avoidance of mixed type arithmetic, that is cases when an operator is called with numbers of different types, such as

   (let ((x (sqrt 1.5))) (* x 2))

These mixed-type calls are not handled efficiently. To properly
implement the semantics of Scheme, they are implemented with an
actual function call to the library. Here the (* x 2) will actually
call the "*" function in the library. One transformation I applied
to your code is to convert integer constants to a floating point
value, when the other operand was also a floating point number. For
example:

   (let ((x (sqrt 1.5))) (* x 2.0))

"

Simply changing the numeric operations to use explicit types indeed increases the speed 2.2x. The second and third image in my previous post now only take ~186s to render instead of ~415s. Impressive! If I optimized the math and tweaked it even further, we'll have a pretty fast raytracer on our hands.

Edit: I meant to post the new source code, you can find it here: schemeray-0.2.tar.gz

Scheme Raytracer written in a couple of days

5/26/2009 Update: I have moved over to http://jlongster.com. You can find Schemeray there.

So there's a Haskell raytracer, a Perl raytracer, and even a Javascript raytracer. Where is Scheme in all this? The Raytracer language comparison includes Scheme, but I can't find any source for it. I decided to write a raytracer in Scheme to give it some credit.

Scheme Raytracer v0.1 supports Phong illumination, sphere/plane/triangle intersection, .obj file loading, and reflections as its basic features.



Example of loading a .obj ("TIX" are the last three letters of the company I work for, COPTIX, but the COP in the mesh need reconstruction so I took them out):





Source code (Gambit Scheme, includes .obj file): schemeray-0.1.tar.gz
Or just view the main file: schemeray.scm

I've fairly new to Scheme, meaning I've been studying it (along with functional languages in general) for a while but haven't coded anything of substance in it. I'm interested in working in Scheme for 3d graphics, and I figured a raytracer is a great place to start feeling out Scheme for that kind of work.

I was right - I learned a lot about what I love about Scheme and what I miss from other languages. This article could go in all sorts of directions, but I'm going to keep it simple, post some screenshots and list some pros and cons about Scheme. Serious profiling is out of the question because the raytracer hasn't been optimized yet. It is currently written using Gambit Scheme.

The second and third image took ~415s to render. The mesh consists of 84 triangles which, without any spatial partitioning implemented, slows down the rendering a bit. A few spheres with full effects renders in ~30s, but none of these numbers mean much because I haven't optimized anything. I tried running it on Chicken just to see speed differences but I couldn't get the syntax-case egg working. At some point I'll profile different schemes with this which may merit a write-up.

What I Liked

These are a few things I liked about Scheme. I suppose I should say that I'm coming from a C++ background.

1. Code and data equivalence. My scene was simply a list of property lists, something in the form of
   

   (define scene `((sphere ,(make-vec3d .2 .5 .5)
                        ,(make-vec3d -10 0 50)
                        10)
                  (light ,(make-vec3d 1.0 .8 1.0)
                         ,(make-vec3d 0 30 50)))
   

   and I can map over it. This is just a simple example, but especially in testing it's very flexible to be able to construct arbitrary lists as well as inspect functions.
   
   
2. 'write' and 'read' are beautiful functions. It's an elegant abstraction of parsing, something which I usually dreaded in C++.
   
   
3. Naming conventions. Because of Scheme's lack of constraint on variables names, I can do things like
   

   (let ...
   (n.l (saturate (vec3d-dot n l)))
   (r.v (saturate (vec3d-dot r v)))
   (o-a.n (vec3d-dot (vec3d-sub origVec a) n)))
   

4. General readability of code. Once you get used to s-expressions, reading mathematical expressions becomes very natural.

Things I Miss

Just a few things that I caught myself reminiscing about.

1. Types. I'm a big fan of types not so much for compile-time error checking, but mainly for determining the execution path. I think it leads to elegant code. We all know that repetitive code (or patterns) indicate that something's wrong. And I find this pattern in Scheme:
   

   (define (generic-operation a)
   (if (pair? a)
   (operation (cdr a))
   (operation a)))
   

   I don't think Scheme should be a statically typed language. I'm just saying that I need refactor that kind of pattern out somehow. Possibly a simple macro would do, or maybe I need an object system like Meroon. At least generic methods are needed; if you take a look at the raytracer code, I had to manually dispatch actions to the sphere, lights, planes, etc. because there isn't any automated dispatching.
   
   
2. A solid module system. This applies to Scheme in general, not to an specific implementation (I know that Scheme48 has a nice module system). I miss a standard module system because, for example, if I wanted to use Meroon I would have to figure out how to integrate it with whatever module system I choose. If a standard module system existed, properly written libraries would already be integrated. I know that R6RS includes a module system, but from what I hear it's broken. Here's hoping a standard module system is implemented across implementations soon.

Half-way through writing the raytracer I realized how much I miss types, and I looked at Haskell. It's a very elegant language, but I just couldn't pull myself away from the expressiveness of Scheme. So I'm sticking with Scheme, and it's just a matter of tailoring the syntax for my needs.

(forgive formatting inconsistency, I'm still fighting a little with blogspot)