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)

Wrapping up code

Recently I've become obsessed with the idea of "modules". I don't mean any particular module or namespacing system, but just the idea that code should run isolated, in its own environment, and interact with an explicit interface (whether it be a whole set of function definitions or simply arguments to a function).

The idea is old, and has materialized in many forms. I think the idea of OOP is a variation on modules. Each 'object' has code which runs in its own object environment, and you present 'public' methods as an interface into the code. It even gets kinda fancy with polymorphism, where an interface can represent a dynamic codebase. The problem with traditional OOP is you get abstraction leaks everywhere and interfaces usually break (and you end up losing trust in the integrity of your interfaces, which is a very bad thing).

It's hard to develop a module system in the mainstream OOP languages (C++, Java, etc.). It's because scopes are screwed up in those languages. Java forces a certain namespace pattern on you, but at least everything is an object. C++ has two scopes, the global one where you can declare functions, and the local one where you cannot declare functions. Oh, but there's also the object scope mixed in there somewhere. (Interestingly enough, you can declare nested functions in GNU C).

The point is that if I am restricted as to where I can place my code (i.e. functions), I probably won't be able to isolate code as much as I want to.

Anyway, enough about OOP (I am a disgruntled developer who didn't discover functional programming until recently). This is the kind of module pattern I like, only available in functional languages (this is Javascript):

var f = (function() {
  var result = (function(o) {
    var i = 5;
    return o.val = 4*i;
  })(getobj());
  return result;
})();

This is similar to the 'let' form in Lisp. It's simply a block level expression that represents encapsulated code. It discourages mutation which is a very good thing, and everything is nicely placed into its own little environment.

So that's one form of modules, which could work on a large system as well because of how dynamic Javascript is (and you don't need to sort dependencies). jQuery wraps everything up into a (function() { ... })() expression, and scopes itself by attaching the jQuery object to the window object. neat, eh?

In languages like Scheme, especially ones which compile to C, you need a little bit more advanced module system on the global level because it needs to sort dependencies and do proper importing/exporting. I have recently been using Gambit Scheme and adopted Snow as my module system. I extended Snow to support better options for including and/or loading libraries, and ever since I started using it I've felt very liberated (I had just come from the C++ world). I love the fact that there is no difference between an statically linked library (such as a group of C .h/.c files) and a loadable library (a dll or shared library). In fact, I can control exactly which libraries should be linked/included and which should be built as loadable libraries in my Makefile.

So whether it's simply reorganizing Javascript to get a little more isolation, or building a large complicated system with dependencies in Scheme, the idea of 'modules' is just awesome.

No more hosting for me

For some reason I always like to attempt something myself before trying to get help from others. I meant that specifically for Computer Science, but I suppose it's true most of the time actually. Ah well, sometimes it helps me because I can learn why I'm using something and why it needs to work the way it does. For example, I tried to host my own blog over at dimlylitblog.com, but I quickly realized that 1. I don't have the time to manage a web server and 2. I'm not interested enough in sysadmin stuff to do it. The reasoning was that I could do anything I wanted with my blog, so if I wanted to program a cool widget-looking thing and rendered some weird Java 3d world, I could do it.

I wanted a blog for the simple reason of keeping track of research (being able to tag posts is a great thing). And Blogspot is a great tool for doing so. It lets me spend time where I need to be spending it.

So, I'm going to start posting here about my 3d graphical developments in Gambit Scheme/Termite.

Yay for simplicity! Gambit's namespacing

For a while now I've wondered how people usually organize Scheme code in large projects. There are various module systems for Scheme implementations, and some are rather bulky. One of my main questions is how object systems relate to modules; I haven't been able to find much about this.

I like Gambit's namespace directive; beauty comes in simplicity. I know the Scheme purist guy throws up a little in his mouth whenever he thinks about it, and here's why: it uses name mangling. It seems that there are two types of Scheme programmers; those that care more about practical applications of using Scheme, and those that care more about being theoretically correct. It's rather non-deterministic which one is better. Often the purist comes out in the end when his app behaves the way it should, but many times the practical guy wins when he gets things done quick or his app runs faster.

In general, I love how dedicated the Scheme community is with being algorithmically correct. I think we should almost always favor theoretically-correct design over hacked-for-optimization design. Almost, though, because there are cases where we want to apply the greatness of Scheme to areas which require high performance, such as graphics engines. And this is where I am (designing a graphics engine), so, however imperfect it may seem, I will tend to hack the design of my scheme code to favor critical performance.

On a quick side note, it seems that Gambit represents a system which strives to be theoretically correct, but recognizes the "need for speed." Scheme48, on the other hand, will always make decisions purely based on the formal theory behind it.

Back to Gambit's module system. The namespace directive simply rewrites definitions with the supplied prefix. This maps well to Gambit's builtin define-type, which is a basic data type definition. define-type is a macro which writes out several functions which make the object, set/get its properties, etc. Using the namespace directive, these will get properly renamed.

Well, kind of. You don't exactly import and export symbols, but you simply pass a list of symbols along with the namespace declaration which claim "this namespace owns these symbols." Any reference to those variables will refer to (namespace)#(variable). If you don't pass any variables, you are claiming your namespace owns everything, which is why you lose all the standard definitions:

> (namespace ("foo#"))
> (define a 5)
*** ERROR IN (console)@2.2 -- Unbound variable: foo#define

Most of the time people explicitly list the variables they want associated with the namespace:

> (namespace ("foo#" a))
> (define a 5)
> (define b 7)
> a
5
> foo#a
5
> foo#b
*** ERROR IN (console)@7.1 -- Unbound variable: foo#b

This presents a problem though: for rewriting macros such as define-type we don't always know the real symbols to export (even if we do, it would be tedious to list them, that's the whole point of the macro). Are these the kind of problems syntax-case solves? I've heard that a proper module system works with syntax-case and this kind of thing can be done.

I want to stick with name mangling and something similar to define-type however because of the performance gain in Gambit with top-level functions. I'm not sure what to do about exporting types (aka objects), I'll have to prototype and see how much I need to use types outside of modules. I could probably get by with defining constructor/getter/setter functions that should be used by the outside world, and manually export them. That may be better anyway; only let the local namespace modify the type data directly.

Of course, I could write a tool that analyzes the code and generating a proper namespace header file. I'll have to see if that's necessary though.

We can still get macros like define-type to bind the created function to the local namespace by doing something like this:

> (namespace ("graphics#"))
> (##include "~~/lib/gambit#.scm")
> (define-type point x y z)
> (namespace (""))
> (make-point 1 2 3)
*** ERROR IN (console)@5.2 -- Unbound variable: make-point
1> ,d
> (graphics#make-point 1 2 3)
> #

Another solution might be to always use fully qualified names. I'll have to take a look at Christian Jaeger's chjmodule system to see how he handles some of this. I may look into using his system in the future.

Although it seems somewhat primitive, I like the simplicity that Gambit offers. It seems that exporting special types such as objects is an inherent problem with any module system, where special support must be built. I'd rather write that support so that I can use objects that way I want to.

Project Flow

As any reader would have guessed from the previous posts, I am starting a project. Up until now, it's been a vague collection of varying ideas. I'm "announcing" (quotes because nobody read this right now) the project now, in hopes to clarify requirements and get some work done on it.

It will be "code"-named Flow. "Code" sounds quite secret, while it's only meant to convey the temporary nature of the name. I can't think of a better one, and no, it's not named after the Spore-inspired flash game (seriously, I've had it in my head ever since I got the idea of a Scheme-based graphics engine, which was a while ago).

So, what will Flow be? It will be a collection of tools written in Scheme for developing 3d graphics and artificial intelligence. It isn't exactly focused on game creation, but rather some of the more specific and important aspects of it. And it could certainly be used for game creation, but there won't be any devices for handling game logic.

The first step is to create a graphics engine completely written in Scheme. From there I will start working on some artificial intelligence applications which will use the renderer for output, but that's for later.

'Flow' indicates how flexible the system should be. The system should feel smooth and easily configurable, while being fast.

I am still in the research/design phase of all this. I have decided on a few things though: it will use Gambit Scheme with Termite, and Javascript for UI.

In an effort to organize my research, I'm compiling a list of modules that I will start with:

Types:

1. Native (to scheme)
2. FFI (os-specific)
3. FFI (general)
   

Window
Type: FFI (os-specific)
Function: Will provide functions for creating a window and managing it, as well as functions to query display info
Dependencies: None

OpenGL Implementation
Type: FFI (os-specific)
Function: Will provide functions for calling OS specific OpenGL libraries (AGL, CGL, WGL, etc.)
Dependencies: Window

OpenGL
Type: FFI (general)
Function: Will provide methods for rendering and other various graphical operations
Dependencies: None

Math
Type: Unknown (thoughts?)
Function: Will provide methods for calculating linear algebar equations
Dependencies: None

Renderer
Type: Native
Function: Will provide higher-level functions for rendering operations
Dependencies: OpenGL, OpenGL Implementation

Scene
Type: Native
Function: Will provide functions and structures to provide scene structure and querying
Dependencies: None

I'm relatively new to functional programming, so figuring out how to structure these modules and their communication will be fun.

Gambit-C Erlang FFI

I have finished up a prototype Gambit-C Erlang FFI that I have been working on. It's a neat technique and could be very valid in a situation where you want to use Scheme for various tasks in an environment like Yaws. However, if using Scheme for more than achieving various tasks, and using it for some of its mind-blowingly weird and cool stuff and basing an application around this, you're better off using Termite.

If you're interested, you can download it.

To be able to take advantage of all of Erlang's distributing
mechanisms, we need to use a proxy Erlang process and communicate through ports, as described here:

http://www.erlang.org/doc/tutorial/erl_interface.html#5

This is what my FFI is based on. It's a very basic implementation, but it allows to write a Scheme app like this:

(load "erlang")

(define (bar num)
(+ num 2))

(define (foo num)
(* num 2))

(define (start)
(start-erl)
(let loop ((term (erl-receive)))
(if (not (eqv? term 'close))
(begin
(let* ((fun (car term))
(args (cdr term))
(res (apply (eval fun) args)))
(erl-send (erl-element res))
(loop (erl-receive)))))))

(start)

And then in Erlang do this:

 2> test:start("./test_process").
<0.38.0>
3> test:call({foo,10}).
20
4> test:call({foo,12}).
24
5> test:call({foo,25.2}).
50.4000
6> test:call({foo,12.25}).
24.5000
7> test:call({bar,100}).
102
8> test:call({bar,100.123}).
102.123
9>

Pretty neat.

All Things Distributed

One of the first languages I'm researching is Erlang. There are various solutions for distributed programming for other languages, specifically Termite for Scheme, however Erlang has proven itself to be an industrial standard. After a little research with Erlang, I can see why, and I'm definitely using Erlang for distributed processing.

Termite is great, and it may prove itself to be the industrial standard distribution system for Scheme in the next couple years. However, it has a ways to go until then. I believe its Windows support is shaky, there's only a few guys behind all the code, there aren't any libraries written with it in mind, and it doesn't have a simple c interface. Not to mention that possibly the only documentation for Termite is Marc Feeley's post about it with some examples.

With Erlang, it was extremely easy for me to sit down, get a distributed system up and running, and even add some c nodes to the network. The c interface to Erlang is what really excites me, because that means you can have a node written in any language that supports a c interface. Other nodes see the c node as an Erlang node, but it's actually completely written in C (or a language supporting native C calls). That means I could have a huge network with various nodes of Scheme, Erlang, Python, etc., but more on this later.

On top of that, you get all the benefits outlined in this post, most importantly the possibility of embedding Mnesia in any of these nodes. Also, ssh into nodes? That would be pretty cool.

It's still vague exactly how much Erlang code I will write, but it will be minimal. I plan to use Erlang for exactly what it's good for - distributing. And I'm realizing more and more that it's not just network distributing, but even local code distribution. Going back to having a network of local nodes written in different languages, each node could be written in the language that fits best for the problem that node is designed to solve. And the the language translation delay (where it's slow to call across language barriers) becomes a very small constant because each node continually runs in its own environment. It never has to leave, it just communicates with messages.

And then I'm free to distribute the system however I want, whether if its across several computers or all locally. And Erlang makes it really easy to implement fault tolerance.

I have more prototyping to do with Erlang, but this looks like it could be a very cool language to use (whether or not I'm actually writing in it :))!

My philosophy behind this project is that many recurring problems in computer programming have been solved already, and I should not re-implement anything that has a good solution already. The difficulty lies in the fact that it may be impractical, and in fact contradictory, to use certain solutions together because of the environment/nature that each involves. It's my job to figure out how closely I can integrate existing well-written solutions without sacrificing performance or design, and deciding exactly what code I need to write.

For example, I'm hoping I can do the following while keeping high performance:

1. Use Erlang for distribution of code
2. Use Scheme for its elegant syntax and advanced flow structures (like continuations) and speed (with Gambit)
3. Use Javascript for graphical 2d UI interaction because of its wealth of libraries
4. Possibly use Nebula Device 2 for rendering, depending on how hard a Scheme FFI will be
   

And I'm still heavily researching many other languages/libraries!

Introduction

So here I am, finally using a blog to keep track of different things I'm researching. I've been meaning to do this for a while.

Basically, I'm starting to research a broad amount of ways to implement a flexible development environment for interactive 3d worlds. I know that's extremely vague, but I don't even know exactly what my goal is yet. I'm sure that it won't be the pure 'gameplay' type programming because honestly that doesn't interest me as much as other things. I'm fascinated by AI and self-populating worlds, as well as advanced graphical techniques. Somewhere this will merge into an interesting place where I think the term 'game' might be applied, but only by a natural progression from an incredible amount of interaction with some smart AI creating the rules.

This blog will serve as my platform for logging technical details and personal opinions about everything I research. I will describe the process I'm going through and reflect on different ways of achieving my goal. Something I need to do soon is actually state my goal, but I can still look around at a couple things first. :)

So here's where I am now: I need to get familiar with more programming languages to get a feel for what's really possible, specifically functional (ish) languages. I will do this by researching several languages, pick a few out and develop prototype systems using those languages. On my list of languages are Lisp/Scheme, Erlang, Smalltalk, C, C++, maybe Haskell, and others. I'd love to hear peoples' comments about these languages as I'm researching each of them.

To start off, I found an interesting article about Erlang and multiplayer gaming (Writing low-pain massively scalable multiplayer servers). I'm very interested in Erlang as possibly the 'controlling' language that manages the flow of the program, while most of the actual program is written in Scheme/C++. More research is required on this though.

I really need to modularize this project and figure out how deep I want to go in each module. For example, I haven't decided if I want to develop a rendering engine from scratch or try something like Nebula Device (which looks fantastic). The deciding factor will be the languages I choose to work in and how hard that makes it to interface into an engine, but I'll most likely write the lower level modules in C++ anyway so an interface is going to be required.

Nebula Device looks awesome though, and it's worth at least a prototype to see if I should use it or not.