Tim Sweeney Discussion Posting Archive

When picking a splitter polygon, rank all polygons based on a function like this:

   Score =
      (
      (FLOAT)Balance *       (FLOAT)(OurAbs(Front-Back)) +
      (FLOAT)(100-Balance) * (FLOAT)Splits
      );

Where:

Balance = 0-100, tendency to balance tree rather than minimize cuts, 15-25 works well.

Front = polygons in front
Back = polygons in back
Splits = polygons split

For typical complex objects, the polygon count only increases by 20-30% after BSP'ing.

-Tim Sweeney, Epic MegaGames, Inc.

I've looked in Watt and Watt, FvD, Graphics Gems I-III, etc. and I have the original paper written by Blinn. However, I have yet to see an implementation of the original algorithm proposed by Blinn. Frankly, every time I've seen Bump Mapping mentioned in any text, it's just glossed over. I understand it pretty much, I just would like to see an actualy implementation. I guess my real question would be, how do you find the partial derivative of the bump function when your "bump function" is just a b/w bump map with varying heights. This is the way I would like to implement this as opposed to procedural bump mapping.

An easy way is to store your bump map as a set of 2D normal vectors. Then, you can find the angle of incidence each lightsource against it with a dot product. A bump map texture could be something like

typedef struct
 {
 float UNormal; // 0=facing straight out
 float VNormal;
 } BumpMapTexture[USize][VSize];

Of course, for space reasons, it would be best to store bump components as bytes or words.

You'd determine the UNormal from a greyscale texture by taking the X differences, i.e. (Texture[U+1][V] - Texture[U][V])/Max, and the VNormal from the Y differences.

-Tim

This is a very clever trick. I was working on a method similar to this a few months ago, but dropped it after a few hours of experimentation because of temporal problems. It produced great stills, but moving textures jiggled. I might have been missing something, though. Have you run your texture mapper at realtime speeds? Does it have this aliasing problem?

-Tim

Brian - Since it is a sphere, just compute the distance of the center(oid) of the circle to each of the surfaces. It is a SINGLE check for each sphere (you can ignore all of it's faces since you are using a sphere approximation)

Though this seems to be the correct solution at first glance, it's only an approximation. It overstates collision with convex edges. To get an exact solution, you need to either use spherical subdivision or handle convex volume edges and vertices. A better approach is probably "Don't try to do that". :-)

-Tim

If you have a 3-D BSP tree, and you walk it front-to-back, would it not be possible to compute a "shadow volume" for each polygon and determine if the next polygon to be rendered is within it? If it is entirely within the shadow volume, then it is NOT visible and does not have to be rendered. If it is only partialy within the SV then it can be *clipped* to the previous poly's SV, and only have it's visible parts drawn. That would make for a "perfect" 3-D engine with *no overdraw*. Right?

I coded this and the major problems are:

1. The shadow volume BSP's become very lopsided, so processing an additional polygon becomes more of an O(n) operation than an O(log n) operation.

2. You'll get cracks between adjacent polys unless you incorporate logic to build a seamless SVBS mesh (a slow and operation).

3. Building the SVBSP requires taking the sqrt() of the difference of two numbers which is (A) slow, and (B) numerically unstable. Given the number of times you have to do this per frame, the speed and precision problems are killer.

-Tim

3. Building the SVBSP requires taking the sqrt() of the difference of two numbers which is (A) slow, and (B) numerically unstable. Given the number of times you have to do this per frame, the speed and precision problems are killer.

Where exactly do you need to take the sqrt?

To generate a BSP which I could clip world polygons by, I built a solid 3D BSP by forming a set of partitioning planes for each visible polygon. Each partitioning plane contained the viewpoint and the line comprising the polygon's side. You just do this for all polygons in the world, in front-to-back order, until the screen is completely solid. To build those planes from a point and a line, I took a cross product, and normalized it. (In retrospect, I think this would have worked without the normalization - DOH!) :) The numerical instability came from sliver polygons, where most of the precision was lost during the cross product. This problem could have probably been overcome, as well as cracking, and optimization, but my view volume renderer was abyssimally slow in complex areas compared to simpler methods, so I didn't spend much time before moving on to other methods.

Regarding convolving the world with a sphere in order to simplify collision, that's a great idea. You could also convolve the world with a cube and end up with all-polygon geometry.

-Tim

Has anybody got information on how to generate realistic, fractal clouds for computer graphics? I would be interested in any algorithm or literature on this subject.

Here is some code I snipped from the game I'm programming.

//
// Make a random tiled 2D fractal texture of size US*VS.
// Dest is an array of US*VS floats whose values range from 0.0 to 1.0.
//
void MakeTiledFractal(FLOAT *Dest, int Size)
{
	void *MemTop = GMem.Get(0); // this is a simple memory pool

	// Make sure Size is a power of two:
	if( Size&(Size-1) ) appError("Size not power of two");

	// Make wraparound table
	INT* WrapU = (INT*)GMem.GetFast((Size+1)*sizeof(INT)); // snag some memory
	INT* WrapV = (INT*)GMem.GetFast((Size+1)*sizeof(INT));
	for( int i=0; i<Size; i++)
	{
		WrapU[i]=i;
		WrapV[i]=i*Size;
	}
	WrapU[Size] = WrapV[Size] = 0;

	// Init random index
	int iRand = 0;

	// Init base
	Dest[0] = 0.6 * 0.5;

	FLOAT Range = 0.6 * 0.5;
	int Speed   = Size;

	// Descend through mesh
	for( Speed=Size/2; Speed; (Speed /= 2, Range *= 0.5) )
	{
		FLOAT *Dest0 = &Dest[0];
		FLOAT *Dest1 = &Dest[Speed*Size];
		for( int v=Speed; v<Size; v+=Speed+Speed )
		{
			FLOAT *Dest2 = &Dest[WrapV[v+Speed]];
			for( int u=Speed; u<Size; u+=Speed+Speed )
			{
				FLOAT Base = 
					(
					+	Dest0[      u-Speed ]
					+	Dest0[WrapU[u+Speed]]
					+	Dest2[      u-Speed ]
					+	Dest2[WrapU[u+Speed]]
					) * 0.25;

		        // GRandoms->Random(seed) is just a random number
		        // from 0.0 to 1.0.
				Dest1[u-Speed] = Base + Range * 
					(-1.0 + 2.0 * GRandoms->Random(iRand+0));
				Dest0[u      ] = Base + Range * 
					(-1.0 + 2.0 * GRandoms->Random(iRand+1));
				Dest1[u      ] = Base + Range * 
					(-1.0 + 2.0 * GRandoms->Random(iRand+2));
				iRand += 3;
			}
			Dest0 += (Speed + Speed) * Size;
			Dest1 += (Speed + Speed) * Size;
		}
	}
	GMem.Release(MemTop);
}

All routines are optimized specificly for Pentium (Pentium, Pentium Pro, Pentium with MMX and Pentium Pro with MMX). Optimizations include code that hurts performance on 486(487?) and 387 processors, however such code is kept to a minimum (compared to some FPU code I have seen).

Most functions in the library are very close to optimal. Short operations, such as a vector dot product, suffer a lot of stalls due to the fact that there generally aren't many parallel operations in such short operations. However longer operations like matrix multiplies (equivalent to 3 or more parallel dot products) usually only have a few stalls of 1 or 2 cycles.

You should check out Visual C++'s optimizer. It generates stall-free code for vector and matrix operations floating point ops. I used VC++ to create a 3-component vector class and defined all of the operators - add, subtract, scalar multiply, dot product, matrix transform, etc. This makes 3D math really easy -- "trade ease of implementation for speed", I thought.

To my utter surprise, I checked the assembly code output by VC++ and its floating point was perfectly pipelined for the Pentium.

-Tim

Hope I'm posting to the right place. Does anyone know a way to elegantly crash in Win95 with DirectX running? I find that when my app crashes (Release version) while having control of the screen, the user has to reboot to get his/her screen back.

Is there a way to cast and catch an exception which leads to a code fragment for closing down directx?

void main(void)
{
 // Set up DirectX here and go into fullscreen mode.
 try
 {
  // Call your game here.
 }
 catch(...)
 {
 }
 // Shut down DirectX here.

}

This will catch most problems. Crashes that are due to calling DirectX with invalid parameters, and some other hairy system level Win95 crashes, won't recover this way, but the above is the best that one can do in Win95.

-Tim

A few years ago, while experimenting with some fractal math, I wandered upon to the identity:

if f(x) = 2x^2 - 1, then the nth iteration of f(x), i.e. f(f(f(...x))) = cos (2 ^ n * arccos(x)).

This is easy to see from the identity:
cos(2x) = 2 * cos(x)^2 - 1,
cos(4x) = 2 * cos(2 * cos(x)^2 - 1)^2 - 1
etc.

In general, if F(x) = the inverse of f(x), the nth iteration of f(g(F(x))) is equal to f( the_nth_iteration_of_g(F(x))), where f(x)=cos(x), F(x)=arccos(x), and g(x)=2x.

Interestingly, the general formula works for non-integer values of n, conveniently defining the value of the iterated function over *all* numbers.

At the time, I was working with the Mandelbrot set, trying to find a closed-form solution for f(x) = x^2 + a, for any value of a. Though I was utterly unable to generalize the above solution for 2x^2-1 (which can easily be transformed to x^2-1/2), I have always been curious as to whether a closed-form solution does indeed exist. Any takers?

-Tim Sweeney

Hi
Does anyone know how to bypass Direct3D and get straight to the HAL? This is because I want to support hardware acceleration without using Direct3D.

I was looking into this, and I don't think it's possible. In immediate mode, you build "packets" which specify vertices, texture coordinates, and stuff. It looks very much like the D3D hardware driver just takes these packets and does the minimum translation needed to send it to the card. In order words, the HAL is the lowest layer whose inputs are hardware-independent. So, short of programming directly to the a specific piece of hardware, there's no lower level in Direct3D.

Fortunately there doesn't seem to be much overhead in the D3D translation layer.

-Tim

IMO it's not very realistic to cite one shader in a game and start suggesting extentions would have improved performance, particularly when you consider that it's one arbitrary (and very impressive) example of many possibilities. If you need commodity hardware acceleration for those features then using more complex shaders could be considered a disadvantage for some time to come.

If we make the assumption that the most high-performance 3D apps will be geared towards rendering *realistic 3d environments*, then Quake is a very good example of what's needed in the short term. I think that "realistic 3d environments" is a safe and necessary assumption, since that's the most taxing widespread use of 3d hardware, especially at the consumer level. This means specializing the library a bit, but that's a time honored tradition (much as special case CPU performance was improved by caching and instruction pipelining - things which don't help all apps, but which greatly help the most common apps).

In a realistic 3D environment, the main polygon-level capabilities that are sorely needed now are:

* Multipass texture rendering, for:

• Texture maps
• Detail textures/microtextures
• Bump maps
• Light/shadow maps

* Vertex lighting options for:

• Gouraud shading
• Specular highlighting

High end hardware already does the vertex lighting, so the main area that needs improvement in OpenGL for the next few years is multipass texture rendering, and more advanced texture options (like bump mapping). This is a good direction for OpenGL, because it lets us get a huge (i.e. 5X-10X) improvement in apparent detail, just by adding multiple simultaneous texture mapping support to 3d hardware - something that is well defined and much easier to do in hardware than, for example, improving straight polygon rendering speed by 5X-10X.

I think you do need one texture matrix per simultaneous texture map you're rendering (whether the multi-pass rendering is done with multiple passes, or it's done simultaneously). The Quake case of light maps aligned 16:16 on texture maps is too special case, especially when one wants to extend it to dynamic lighting/shadow maps, where different coordinate systems are favorable.

In reality, this just means that each polygon vertex needs one (x,y,z) value and multiple texture (u,v,r,g,b) values (pardon the probably incorrect representation, I'm a newbie to hardware, I'm referring to two texture coordinates and an RGB lighting value). So hardware just needs the ability to interpolate "n" pairs of (u,v,g) coordinates, when n is small, i.e. 1-4.

The only major question is - what blending operations are needed between the multiple texture sources, color sources, and screen? For guidance, one can just look at the coolest raytraced, radiosity rendered, and other computer generated scenes around, and you don't need that many operations to capture 99% of the most common elements:

• Shadowing (multiply texture map texel by light map texel)
• Bump mapping (multiply computed bump-map light value by light map texel). Bump mapping could be achieved by generating a very low res (i.e. 16x16) specular highlight texture at each triangle vertex, and doing an (ugh) 5-way (i.e. bilinear -> trilinear -> 4-way -> 5-way) interpolation
• Fogging (multiplying for attenuation then adding fog)
• Alpha blending with interpolated or texture-lookup alpha for transparent and reflective surfaces

There are probably a few others, but the number of supported combinations can be kept small, by limiting the support to options which are very useful in rendering realistic environments.

-Tim

I was thinking about the logistics of writing a texture mapper which maps textures from 2D Fourier or DCT space, directly onto the screen. This approach would seem to have many advantages, such as the ability to perform anisotropic texture filtering, by convolving the texture with an anisotropic filter kernel (a simple operation since convolution in the texture doman corresponds to multiplication in the Fourier doman).

It's trivial to write a texture mapper which renders an nxn texture directly from Fourier space using n^2 multiplies per pixel. With an FFT operation a faster execution time should be possible, i.e. n * log(n) for a FFT. However, that operation works for arbitrary pixels, and it seems that a much faster operation might be possible, by exploiting the fact that texture mapping involves tracing a spatially linear (though not necessary temporally linear, due to perspective correction) path through a texture.

Has anyone tried this? Is anyone aware of past work on this topic? Does this seem like a good idea, or can someone with more experience in Fourier transforms find fault with this approach?

-Tim Sweeney, Epic MegaGames, Inc.

(bunch of cool routines deleted)

Another interesting approach is to use the FPU, which automatically computes the index of the highest bit, using something like this:

Input DD 0
Temp DD 0
Output DB 0 ; log 2 of input

fild [Input] ; 4 cycles?
xor eax,eax ; free
fst [Output] ; 3 cycles
mov eax,[Output] ; 1 cycle
and eax, ??? ; 1 cycle, the value of ??? is left as an excercise to the
reader. :)
shr eax, ??? ; 1 cycle
add eax, ??? ; 1 cycle adjust for exponent bias.
; The idea of the above is to extract the exponent.

This would always be about 11 cycles, and I reckon it would be faster than the other methods posted, because their average case performance suffers from branch misprediction penalties which are pretty expensive especially on PentiumPro class processors.

-Tim Sweeney, Epic MegaGames Inc.

Hi,

I'm a game developer who is interested in garbage collection. The most recent game engine I worked on (Unreal, see http://www.unreal.com/) contains a built-in scripting language quite similar to Java, that is based on garbage collection for memory management. See http://unreal.epicgames.com/unrealscript.htm for an overview of my little language -- it's pretty simplistic, but it does implement some neat object-oriented features such as language-level support for dynamic state (a.k.a. mode) switching and scoping of functions.

My current garbage collector is based on a simplistic and non-optimized "mark and sweep" routine that isn't performed in realtime. Once every few minutes (when the game's level changes), I just go off and perform a full, no-conservative garbage collection pass. It's a simple routine, because I do it at a known point in my code where I know there aren't any references to objects on the stack, and I have a single root object through which all active references can be traced. Object orientation is cool for games and 3D environments -- my root object is sort of a "pointer to the 3d world". My script language maintains class "meta-data" listing all variables and their references, so it is a simple process to determine where object references reside in other objects.

For reference, I typically have 10,000 separate objects in memory. A typical object is a few hundred bytes, and references a few other objects. About 80% of my objects are known to be unchanging at runtime, for example game data like sounds, music, texture graphics, and animation data.

Anyway, for my next game, I want a much more general-purpose, realtime garbage collector. I've read a few books on garbage collection, and looked at links on the web, so I have a general idea of what's possible. But I was wondering if anybody might give me guidance on some topics:

1. Since >80% of my objects are constant at runtime, I can be clever and precompute information about their internal references and cycles (since they're known not to change after construction), and not have to ever check them in realtime for my garbage collector. Is this a generally known / researched technique, or did I invent something here? :-)

2. Since I'm defining my own language, I thought of using a new "visitor" keyword (that puts constraints on an object-reference variable), that means "this local variable (or function parameter) refers to an object, but it's not allowed to 'gain roots', so you can't assign it to a global variable, instance variable, or static variable". This is analogous to the meaning of "const Typ* Ptr" in C++, "Ptr points to an object, but you can't change it". The idea behind this is that it enables the compiler to detect that I don't need to do any garbage collection work on a temporary object. For example:

// Transform a point by a matrix.
// Here we promise not to "root" p or m.
void transformPointByMatrix( visitor point p, visitor matrix m )
...

// Do some stuff.
point p = new point(1,2,3);
matrix m = new matrix(1,2,3,4,5,6,7,8,9); // create a new 3x3 matrix.
transformPointByMatrix(p,m);
return;

In this case, assume that the transformPointByMatrix function is defined in some other module, so I can't compile-time inline it. But with the "visitor" keyword, the compiler *can* realize that the objects "p" and "m" can't possibly gain any roots in the code above, so it can be explicitly destructed, without any GC overhead. Whereas, without the "visitor" keyword, both "p" and "m" become garbage and the collector eventually has to deal with them.

The other thing I like about this "visitor" limitor is that it helps programmers avoid making stupid memory management mistakes, keeping objects referenced that shouldn't be. For example, think about Windows screen painting "device context" objects, temporary objects which are passed into a function for rendering purposes. These objects are only safe/usable for the duration of that function, after which they become invalidated. So I'd like the language to make it *impossible* for a programmer to sneakily "save off a copy of the object".

Also seems neat for "secure client" languages like Java, where you might want to pass in a high-level object to a function, but prevent it from being retained.

Is this a theoretically sound technique?

3. I'm a huge OOP proponent, but one aspect of OOP that I'm still uncomfortable with is the concept of "object lifetimes". In C++, object lifetimes were explicitly controlled by the app (for better or for worse). But there are lots of cases where that's very desirable, for example:

- A class encapsulating the TCP socket. The TCP socket might be closed at any point, after which the socket object is invalid. Without explicit object lifetime management, you have to write a lot of special case code to prevent these invalid objects from being used wrong, for example if( i_havent_been_closed ) {do normal logic}else{just ignore the call}.

- GUI windows that might be closed at any time.

- Objects in a game. When the game logic determines their life is over (i.e. if you kill a player), you remove it from the world and you *don't* want any references to them to remain!

Has anyone found a way to implement "explicitly managed object lifetimes" in OOP soundly?

For example, I was thinking about a specialized kind of object with the semantics "all references to this object must be weak; the object isn't garbage collected; it must be explicitly destroyed; when destroyed, all weak references to it are set to NULL, and an optional notification function for each reference is called". These would involve some extra overhead, such as maintaining backpointers at all times, but it seems like it might work.

4. References between objects in my game (and in 3D environments in general) tend to be clusered: they form groups, where objects within a group contain tons of references to other objects in the group, but objects in a group contain a fairly small number of references to *other* groups. So I've been trying to devise a GC algorithm that takes this into account. Any suggestions?

5. Can anyone point me to techniques I can use in my language / compiler to make garbage collection simpler or faster? I'm lucky to have freedom over designing the language, compiler, and runtime, so anything is possible. And I need to manage thousands objects in realtime and 60 frames per second, so performance is important.

6. Since this is a game, realtime performance is more important than anything else. I can afford to waste a certain percentage of available memory for garbage objects, and I can afford the time to maintain reference counts and incrementally scan to collect garbage, but I *can't* afford to have any long pauses -- and here in game land, spending more than 1 msec on garbage collection per 15 msec frame is the limit of acceptability. So, what is the best incremental "do a little bit of GC work at a time" approach? Note that I don't have to worry about "references to objects stored on the stack", since I can design my game to do garbage collection once per frame, in my update loop where I'm 100% sure there are no references to object on the stack.

Thanks for any help!

-Tim

My script language maintains class "meta-data" listing all variables and their references, so it is a simple process to determine where object references reside in other objects.

To satisfy the curious (and to cut down on suggestions about things you already know about), it would be interesting to tell the list from which source you drew your meta-objects; for instance, CLOS (e.g. _Art of the Meta-Object Protocol_) or Smalltalk or one of its variants, like the late lamented Actor from Whitewater which provided Borland (nee Inprise) with ObjectWindows.

Actually, the way UnrealScript handles "metaclass data" is very cool! When I saw the Java language spec, I thought their handle of metaclass data was a big hack, i.e. "Let's define a bunch of fixed-length data structures in the .class file to describe the contents of this object". So, Java is a beautiful object-oriented language, that is stored in a great contradiction of hardcoded "C" style data structures.

In UnrealScript, each unique class is described in a unique object of class "UClass". The UClass contains the name of the class, a packaging info, a list of all functions, all consts, all variables, etc.

Functions are described by UFunction objects.

Variables are described by UProperty objects. There are specific UProperty objects for various data types:

UIntProperty (a 32-bit integer variable)
UFloatProperty (a 32-bit floating point value)
UStringProperty (a variable length string -- I treat these as variables, *not* references to objects like Java does).
UReferenceProperty (a reference to an object).

In addition, UProperties can be parameterized. For example, a fixed length array of integers of is parameterized by a UFixedArrayProperty object that contains a UIntProperty object. I plan to extend this to constrained generic types (like C++ templates) for our next project.

This ends up naturally exposing complete introspection to the language, so something like the Java reflection API isn't needed. Just access your "class" object and its "variable" objects directly...I wish Java worked that way.

But from the garbage collector's point of view, I just do a recursive mark-sweep of active objects, starting at the root. It's like (oversimplified a bit):

MarkSweep( UObject* Obj )
{
	if( Obj==NULL || Obj->AlreadyMarked )
		return;
	Obj->AlreadyMarked = 1;
	UClass* Cls = Obj->GetClass(); // Gets pointer to class metadata.
	for( UProperty* Prop=Cls->FirstProperty; Prop!=NULL; Prop=Prop->Next )
		if( Prop->IsAReferenceToObject )
			MarkSweep( (UObject*)((BYTE*)this + Prop->Offset) );
}

Unreal definitely requires large (by general consumer standards) amounts of physical memory, and one of the questions you no doubt spend a lot of time considering is how much effort to go to to deal with the fact that the Win32 platforms do such a bad job of managing VM.

;-)

I haven't done UnrealScript programming, so I'm not entirely certain quite what "compile time" means for you (as opposed to "link time" or "load time"), but... your compiler can fairly easily do "escape analysis" on code to determine what parameters passed to methods _cannot_ result in capturing a reference, since you don't permit long-lasting closures or continuation capture. In the long run, your compiler will be better at it than most humans (and it will work with existing code).

UnrealScript is like Java in this regard: it's based on the "open world" hypothesis: base interfaces are assumed to never change, but implementations can change and new classes can be added anywhere in the hierarchy without losing binary compatibility.

So there isn't any way to tell that "the object reference I'm passing to a function won't become rooted" except by actually calling it and seeing (because you might be calling a new subclass's version of the function that does something evil).

Are you familiar with Eiffel? While we often think about such things (handles which need immediate reclamation) in storage management terms, that's not really always appropriate. Eiffel's precondition/postcondition model puts he issue of whether e.g. a window is open or closed into a much wider realm of correctness guarantee based on preconditions and postconditions.

Now, Eiffel uses a lot of static analysis to make the condition checking useful, and Eiffel doesn't have a C-like separate compilation model either. But Meyer's contract-driven model of design is a powerful one. I doubt whether your target audience would enjoy such things, but if the bulk of hat they are doing is re-using your basic UnrealScript objects (which is what I would suspect) then it may be practical.

I've been reading up on Eiffel a lot recently and I'm actually really excited about the "programming by contract" possibilities (please don't tell any other game programmers, they'll laugh at me!)

Can you help me understand something about pre/postconditions? I understand the Eiffel syntax, but I don't understand how they relate to the compiler: are pre/postconditions actually analyzed and/or proven by the compiler? My C/C++ background leaves me pretty skeptical, guessing they'll just be translated into runtime assertions. With Unreal's distribution model (10 partner companies using the engine for creating their own games, and hundreds of enthusiasts programming modifications and releasing them on the internet [check out http://www.planetunreal.com/, it's cool what users are doing nowadays]), when it comes to issues like object lifetimes and referential integrity constraints, I try to avoid making any assumptions that the language can't catch at compile-time and give you an error message about...because people are doing too much crazy stuff with the code.

Thanks a lot for all the help, it's greatly appreciated!

-Tim

Hello,

Thanks for all the feedback everyone has given regarding optimizing a game programming language for garbage-collection efficiency. It has been a great help.

I've started prototyping my collector and its data structures, and will probably be seeking more advice once I get into all the hairy details. I'm having a hard time finding the right set of tradeoffs to make, regarding immediate vs incremental collection, and robustness of support for multithreading.

Once idea I've always liked, despite its huge implementation hurdles, is "immediate garbage collection", where all references to objects are subject to a write-barrier and some logic that causes all objects to be collected the very instant they become garbage. I'm not talking about a simple reference counting scheme (which has pitfalls with cyclic references), I mean a fully general GC scheme that notices immediately when groups of objects in the rooted graph become disjoint.

I like the concept because I'm a big fan of deterministic behaviour, and I've always been a little uneasy about the idea of garbage objects "eventually" being cleaned up.

Ok, so here's what I've come up with:

1. Absolutely naieve implementation: Each time a reference is updated or goes out of scope, start at the root object and do a full mark-and-sweep through all objects and determine which ones are garbage. Advantage: always instantaneous. Disadvantage: Incredibly inefficient.

2. Faster implementation: Assign each object a positive number, starting with 0 at the root. For each object, maintain for lists of references: (incoming, outgoing) x (to lower numbered objects, to higher numbered objects). Enforce a rule that every object always has at least one incoming reference from a lowered number object. Whenever a reference changes that breaks this rule, move the offending object to the end of the list (make it the highest numbered object), and readjust the other objects--which may cause them to recursively fall to the bottom of the list. In this process, some objects that land at the bottom of the list will have no upward references, and those objects have immediately become garbage. The overhead of this is (on a 32 bit machine) 8 bytes per object + 24 bytes per reference variable. This has a lot of O(n^2) performance cases, for example many double-linked list implementations, but I think the algorithm can be restructured to never be worse than O(n). Still this is impractically slow.

So, my question is: is there any reasonably efficient way to do instantaneous garbage collection, using a write-barrier function that can immediately determine that objects have become garbage?

-Tim

I'm a game programmer, but lately I found out about Haskell, Cayenne, and dependent type systems. As a beginner, I have a few questions about dependent types and proofs-as-types systems. This is for fun and enlightenment rather than important research, so please don't feel obliged to respond unless you enjoy doing so.

1. In propositional logic, one can use {x:Nat|x<10} to express the subset of natural numbers less than 10. Hindley-Milner extensions have been proposed to support subset types, such as Sokolowski's:

http://www.ipipan.gda.pl/~stefan/Papers/research.html

This seems very useful; is there a good reason why this hasn't been adopted by languages like Haskell and ML?

2. In languages like Augustsson's Cayenne:

http://www.cs.chalmers.se/~augustss/cayenne/

One can model both programs and proofs in a uniform language. Why isn't this an area of huge interest, i.e. with would-be Sun Microsystems trying to popularize new mainstream languages based on this technology?

While Java is receiving tremendous hype, it's mostly an incremental improvement over C++, whereas this stuff is *revolutionary*, having the potential to make commercial software far more reliable. It seems surprising there isn't widespread interest.

Is it that people are turned off by the theoretical undecidability of powerful dependent type systems? This doesn't seem too likely to cause real-world problems -- reasonable programs tend to be easy for a typechecker to analyze.

3. Is there anything preventing the programs-with-proofs concept from being taken to the extreme? For example, building abstract definitions of:

• sets
• monads
• groups
• lambda calculi
• categories
• sorting functions

and concrete instances containing proofs that they obey the appropriate laws. I've seen a few assorted systems along these lines, but nothing universal. Has anyone attempted to build a comprehensive set of types and proofs for mathematical objects or categories this way?

4. I noticed the following analogy between ordinary types and dependent types:

A=>B <-> All(x:A).B
A*B  <-> Exists(x:A).B
A+B  <-> ___________

Can we fill in the blank meaningfully, i.e. is there a useful notion of "dependent sum"?

Would it be valid to say that "A+B" is not actually a primitive type itself, but instead corresponds to the existential subset type:

Exists( {t|t==A or t==B)} ).t

Where the {x|P(x)} represents the notion of "subset types" as described above? One can read this as: there exists a type t, equal to either A or B, such that we encode a single value of type t. This encoding of sums is (I think) a more flexible version of Cardelli's "Any/TypeOf/ValueOf" definitions:

http://research.microsoft.com/Users/luca/Papers/TypeType.ps

5. Cayenne has a construct for defining records:

s = struct {a=1; s="hello";}

Has anyone tried defining such records as functions from strings (corresponding to tags) to dependent types? i.e.:

s :: (x::String).
    if      x="A" then Int;
    else if x="s" then String; -- else _|_

s = (x:String)->
    if      x="A" then 1;
    else if x="s" then "hello";

Such functions seem to obey the ordinary rules of records.

A variation on this theme is to represent certain records as "functions from types to dependent types". These seem to be signature-free records, which may be useful for composing Cayenne-style proofs without committing to specific proof names.

6. Looking at the bigger picture, are "programs with proofs" of practical value in future commercial software? I have to wonder if we're simply trading "bugs in programs" for "bugs in proof types".

For example, I can easily write a "qsort" function, test it with sample data, and be pretty confident it's ok.

But, what is the "proof type which all sorting functions must inhabit"? I have no idea, but suspect it's very complex and dependent on other proofs such as those governing ordering relationships. Given human fallability, it seems just as likely to write the wrong "proof type" (hence prove the wrong thing) as write an buggy program. Is this a problem in practice?

Thanks,

-Tim

There is a neat isomorphism between mathematics and type theory. Using ~= to indicate isomorphism, we have (roughly):

sum of numbers ~= disjoint union of types
product numbers ~= cartesian product of types
exponentiation ~= function spaces
"sigma" summations ~= dependent products
"pi" products ~= dependent functions
successor function ~= "maybe" monad

In mathematics, there is a progression between the operators of addition, multiplication, exponentiation, etc., known as the Ackermann hierarchy.

The next operation in the sequence is often called "tetration" and refers to iterated exponentiation. Let us write a^b for "a raised to the power of b", and then a-->b for b raised to its own power a times, i.e.:

1-->b = b
2-->b = b^b
3-->b = (b^b)^b
...

Now I am trying to understand the type-theory analogy to tetration. Given "unit" as the one-valued type, "bool" as the two-valued type, "three" as the three-valued type (isomorphic to "maybe bool"), etc., clearly:

unit-->t ~= t
bool-->t ~= t->t
three-->t ~= (t->t)->t
four-->t ~= ((t->t)->t)->t

So, what is going on here? "bool->t" is the type of identity functions on t; "three-->t" is especially interesting because it is the type of fixpoint operator from t->t to t.

This hints that there may be some computational utility here. Is there a useful type-theory interpretation of tetration?

And is there a useful interpretation of tetration on infinitary types, like lists, i.e. list(nat)-->nat? In particular, I am interested in defining the corresponding value-level operation whose type corresponds to a tetrant. In other words, pardoning the pecular notation, fill in the blank:

* An injection inl(123) or inr("a") is of sum type nat+string.

* A pair (123,"a") is of product type nat*string.

* A lambda \t->t+123 is of function type nat->nat.

* A ______ is of tetrant type t-->u.

-Tim

In Haskell, only a single notion of "function application" exists, where a function f::t->u is passed a parameter of type t, returning a result of type u. Example function calls are:

1+2
sin 3.14
map sin [1:2:3]

However, a higher-order notion of function application seems sensible in many cases. For example, consider the following expressions, which Haskell rejects, despite an "obvious" programmer intent:

cos+sin -- intent: \x->((cos x)+(sin x))
cos(sin) -- intent: \x->cos(sin(x))
(cos,sin)(1,2) -- intent: cos(1),sin(2)
(+)(1,2) -- intent: (+)(1)(2)
cos [1:2:3] -- intent: map cos [1:2:3]

From this intuition, let's postulate that it's possible for a compiler to automatically accept such expressions by translating them to the more verbose "intent" listed above, using rules such as:

1. Operator calls like (+) over functions translate to lambda abstractions as in the "cos+sin" example.

2. A pair of functions f::t->u, g::v->w acts as a single function from pairs to pairs, (f,g)::(t,u)->(v,w).

3. Translating function calling into function composition, like "cos(sin)".

4. Automatic currying when a pair is passed to a curried function.

5. Automatic uncurrying when a function expecting a parameter of type (t,u) is passed a single value of type t.

6. Applying a function f:t->u to a list x::[t] translates to "map f x".

I wonder, are these rules self-consistent? Are they unambiguous in all cases? Are there other rules we can safely add?

It also seems that every statement above is simply a new axiom at the type checker's disposal. For example, to describe the general notion of "cos+sin" meaning "\x->(cos(x)+sin(x))", we say:

for all types t,u,v,
for all functions f,g :: t->u,
for all functions h ::u->u->v,
h (f,g) = \x->h(f(x),g(x)).

Is this "higher order function application" a useful notion, and does any research exist on the topic?

-Tim

It should reflect arithmetic laws of tetration, which for example relate (b ^^ (a1*a2)) with b^^a1 and b^^a2 or so, but are there any? So how should (a,b)-->t be defined?

I couldn't find any papers on this topic, so I'm trying to work out the laws now. The interesting ones are (a*b)^^c and (a^b)^^n. They don't seem to be as "obvious" as the rules for exponents and products, though.

There is also a notion of "dependent tetration" which is even more mysterious. Just as Sigma(a:t).b corresponds to "dependent sum" (with types or numbers) and Pi(a:t).b corresponds to "dependent product", there is a Tetra(a:t).b corresponding to "dependent tetration".

This operation is mysterious because exponentiation, the operator upon which tetration is defined, is the first operator in the Ackermann hierarchy which is not symmetric. So we can't just carelessly say that Tetra(a:t).f(a) = ((...->f(e2))->f(e2) where e1,e2,... are the elements of type t. The result of Tetra(a:t).f(a) depends on the order in which we choose the elements of t. Which begs the question: *which* order is appropriate?

Perhaps our notion of dependent products and dependent functions is currently oversimplified, since we are neglecting this hidden "ordering" which is implicitly involved, but can neatly be hidden because sums and products are symmetric, up to isomorphism, i.e. a+b~=b+a and a*b~=b*a. I wonder, are there useful types (in a type theory) for which sum and product are not so neatly symmetric? One such construction is to apply the rules of simple matrix algebra, but put types inside the matrices rather than numbers. The resulting types commute: (a*b)*c~=a*(b*c) but we don't have a*b~=b*a, since the "shape" of the resulting matrix depends on the ordered dimensions of the inputs.

-Tim

While prototyping a compiler using Girard's Linear Logic as a type system and implementing, in it, a math library supporting the Geometric (Clifford) Algebra, I noticed a striking resemblance. Are these two systems known to coincide?

My conjecture: Linear Logic and Geometric Algebra are, in an axiomatic and semantic view, equivalant; as:

• The linear logic's "times" operator corresponds to the Geometric Algebra outer product.
• Linear "with" corresponds to the geometric product, with semantics analogous to the set-theoretic "exclusive or".
• "Par" matches the meet operator (the dual of the "times" and therefore of the outer product).
• "Plus" is the dual of the geometric product.
• "Nil", A_|_ corresponds to multiplication by the unit pseudoscalar.
• The "!" operator in linear logic appear to roughly correspond to the reverse of a multivector, and "?" to the conjugate of a multivector.
• The grade of a homogeneous multivector is analogous to the number of linear terms that appear in each conjunctive subterm of an expression. GA operations which raise, lower, and retain the grade, are analogous to linear logic with respect to the number of linear assumptions.
• The GA interpretation of linear implication "A -o B" is (surprisingly) not an exponential, but in fact the inner product, seeing that it is the algebras' sole grade- (uniqueness count-) lowering operation.
• The entire duality of linear logic (between conjunction and disjunction, and so on) is carried out identically to the duality of Clifford Algebra, between outer products and the meet operation.
• The "1", "T", "_|_", and "0" of linear logic correspond to 1, the unit pseudoscalar, the unit pseudoscalar again, and zero.

Going through Hestenes' book on Geometric Algebra and Girard et al's "Advances in Linear Logic", the correspondence runs so deep that I find it hard to believe the systems do not correspond.

Interestingly, the development of Geometric Algebra was developed to treat spaces and their subspaces as first-class constructs in a single algebra, with the new geometric product bringing together terms of dimensionality; while Linear Logic was invented to treat uniqueness (in a certain view, a form of dimensionality) as a first-class construct, using the "with" (do-only-once) operator to formalize the uniqueness dimension of values.

It would thus be delightful to see that these two operators, and perhaps the entire formalisms of GA and LL, contain the same substance, developed independently, as they were, almost a hundred years apart.

I would be interested in a counterexample, or references on this correspondence if it is known.

-Tim Sweeney

I finally found the solution to a type theory problem that's been bugging me for years. It's a twist on the "function parameters are covariant" problem, in the special case of mathematical objects like vector spaces and matrices.

Here I will use functions from natural numbers (or an upper-bounded subset of natural numbers) to real numbers to represent vectors. You can think of such functions as fixed-length arrays of real numbers, or of floating point numbers -- I will be lax with the terminology.

The Problem

When determining whether one function type (or array type, or vector type) is a subtype of another, type systems treat the function parameter type contravariantly. Conceptually, this isn't what one wants with mathematical objects like vectors.

I will use fixed-length arrays as an example below and assume classic array typing rules. However, you could see the same issue in C++ by declaring a class vec2d {float x,y;} and a class vec3D: public vec2D {float z;}, and a subclass vec4D containing yet another component.

Example of the problem in C-style pseudocode:

void Use3DVector(float[3] my3DVector) {
    ...do something here
}
void Example() {
    // Declare a 2D vector and a 4D vector.
    my2DVector b={1,2};
    my4DVector a={1,2,3,4};
 
    // Use the 4D vector. This succeeds because it's typesafe:
    // a 4D vector has all the components of a 3D vector and more.
    Use3DVector(my4DVector);
 
    // Use the 2D vector. This fails because it's not typesafe: a 2D
    // vector doesn't have certain components that a 3D vector has.
    Use3DVector(my2DVector);
}

In other words, traditional type systems inherently use these subtyping relationships

.. <: float[4] <: float[3] <: float[2] <: float[1]

This is the opposite of how mathematicians look at vector spaces. They see 1D space as a subspace of 2D space; 2D space as a subspace of 3D space, etc:

float[1] <: float[2] <: float[3] <: ..

The Solution

Define a new type "zero" which is a subtype of "float". Type "zero" has only one instance, the value "0". By definition of subtyping, all zeros are floats, but not all floats are zeros. This is sound.

Since "zero" has only one instance, variables of type "zero" don't need to be stored; they take up no runtime storage. Since they take up no storage, you can store infinitely many of them in a fixed-sized data structure. I exploit this to represent vectors as infinite-length arrays consisting of a finite number of reals, followed by an infinite number of zeros.

Now, instead of looking at vectors in the Java style (float[0], float[1], etc.), we view them with dependent types, like:

ForAll(i nat).if i<3 then float else zero // a 3d vector
ForAll(i nat).if i<1 then float else zero // a 1d vector

Or concepually, you can think of vectors as the examples below, where "..." stands for "followed by infinitely many zeros":

{float,float,float,zero...}
{float,zero...}

If you define a generic type constructor vec(i) in the style above, you'll find that it's exactly what mathematicians want:

vec(1) <: vec(2) <: vec(3) <: ...

You can verify this by looking at the "ForAll" expressions above, verifying that for every possible input value "i", the corresponding subtyping rules hold. For example: {real,zero...} <: {real,real,zero...} because (looking at the first elements) real<:real, and (second elements) zero<:real, and (subsequent elements) zero<:zero, etc.

Other Benefits

You can then derive types from constants, i.e. {2,1,0} has the type of a 2D vector because the third component is 0, whose exact type is zero rather than the more general float.

You can also type strangely-shaped vector spaces like {float,zero,float,zero...} -- the space of vectors with only X and Z components.

In languages supporting dependent types and pattern matching, many mathematical rules automatically fall out of the results. For example, transforming a vector by a matrix which has one column of zeros yields a vector with the corresponding component set to zero -- not just at runtime, but in the type system as well, as long as the zeros are statically known.

Summary and Future Work

By changing our representation of vectors from fixed-length arrays of reals, to infinite-sized arrays containing finitely many reals and infinitely many zeros, vectors now obey the subtype=subspace rules mathematicians want, rather than the covariant subtyping of traditional fixed-length arrays and records.

I am currently working on extending this approach to deal with the multivectors of Geometric (Clifford) Algebra. There are many ways of doing this which don't involve any new type-theory constructs, but clearly nothing we can build out of ordinary dependent types will admit ordinary scalars, and the newly-defined vectors here, as elements of any more general multivector type.

However, I've found a new construct, sort of a "dimensionality-indexed transparent product" that gives you multivectors compatible with traditional scalars, and the vectors defined here. Better yet, it admits imaginary numbers, complex numbers, quaternions, and spinors of arbitrary dimensionality as subtypes; and it always knows the more specific derivable type of your result. This is still somewhat sketchy but I'd be glad to share it if there is any interest.

-Tim

If a language has complete support for introspection (discovering all fields of objects at runtime), then it's easy for users to implement arbitrary persistence algorithms, such as XML or various binary formats. So a desire for persistence can be simplified into a more general desire for complete (perhaps Java-style) introspection support.

-Tim

"Charles Hixson" <charleshixsn earthlink.net> wrote in message news:3B7BF417.5030509 earthlink.net...

It would be desireable if D provided support for the implementation of persistant objects. Basically some way of reading back in as objects of the same type that they were when they were stored, and then using them as objects of that type.

As far as I can tell, this requires that "virtual" objects be allowed to be called by any function, and that they raise a "Does Not Understand" exception if the object that they actually turn out to be doesn't understand the method. Since type identification information is already being stored with each object, a large part of the necessary is already in place.

N.B.: I am not saying that D should implement these features. Merely that it would be desireable if the support for them were designed into the language, so that if they were implemented as libraries, they would fit in smoothly.

Using "+" for string concatenation always leads to confusing ambiguities. In a language without overloading or templates, this can still work, but requires the user to sometimes perform mental gymnastics figuring out "why am I getting weird results using + in this context?"

However, if templates or overloading are present, then you run into even worse ambiguity problems. To avoid ambiguity, you really need to have separate syntax for:

adding (i.e. integers).
concatenating arrays (strings just like any other case).
prepending one t to a t[].
appending one t to a t[].

Note that this is provable rather than speculation. :-)

-Tim

"Overlord" <peewee telia.com> wrote in message news:9lgrsh$2e8c$1 digitaldaemon.com...

In D strings can be copied, compared, concatenated, and appended like

str1 = str2;
if (str1 < str3) ...
func(str3 + str4);
str4 += str1;

But if you want to add a integer into this, does(or will) D support it this(or in some simmilar way)?

int i=10;
char[] str = "abc";

str1 = i;         // str1="10"
if (str == i) ...
func(str + i);    // abc10
str += i;         //same as above

Argh, no! Printf and scanf are ugly remnants of C's limitations. Printf made sense in the ANSI C days, but it and its terribly potential for runtime crashes and subtle bugs have no place in a modern language.

C#'s solution is an interesting good compromise, something like:

print("{1} picked up {2} {3}s",person,count,item);

The HUGE advantages are:

1. It is typesafe. The parameters must be convertable to strings, and their type isn't (redundently or incorrectly) specified in the format string."

2. It's easily localizable to other human languages because arguments can be reordered. This is really critical for shipping software internationally, where the order of nouns, verbs, etc., vary.

An even slightly better approach is to have a new "concatenate with formatting" operator which takes a formatting string and a variant and returns a new string. For example:

"{1} picked up {2} {3}s" $ person $ count$item

The $ operator has the following effects:

"{1} picked up {2} {3}s" $ "tim" = "Tim picked up {1} {2}s"
"Tim picked up {1} {2}s" $ 12 = "Tim picked up 12 {12}'s"
"Tim picked up 12 {1}s" $ "marble" = "Tim picked up 12 marbles"

Therefore

"{1} picked up {2} {3}s" $ "tim" $ 12 $ "marbles" = "Tim picked up 12 marbles"

This is very general, and could be extended with other appropriate natural language features useful to localization such as pluralization.

-Tim

"Richard Krehbiel" <rich kastle.com> wrote in message news:9lgkos$251p$1 digitaldaemon.com...

For goodness' sake, don't take printf from C verbatim.

The programmer himself must match the format specifier to the data type.
The programmer himself must align the number of the format specifiers to number of arguments.
The programmer himself must align the positions of the format specifiers the positions of arguments.

Make a printf where the format specifier is adjacent to the variable.

I have a function that works this way:

my_printf("a=%d", (int)a, " b=%d", (int)b, (char *)NULL);

i.e. it takes a format strng containing *one* argument; the arguments(s) following are for that format specifier; multiple pairs of format/argument can be supplied.

Perhaps in D, the end of the variable argument list to Dprintf can be rather than having the programmer be diligent to add the NULL at the end every time. Actually, if you add Real Macros, printf can be a macro which knows the number and data types of the arguments:

Dprintf("a=", a, " b=", b, "\n");

--
Richard Krehbiel, Arlington, VA, USA
rich kastle.com (work) or krehbiel3 home.com (personal)

I personally miss the preprocessor when I use Java.

Agreed, but only because of Java's limitations (no templates, etc.), and not because I *want* to use macros.

And templates! Yes they are complex stuff and I wish they were easier but... they allow you to do things that you would otherwise be unable to do, or have to pay dearly for.

Agreed 100%! I would never consider writing a large-scale program in a language without template-style functionality. It's really astounding how much simplification and generality one can attain with templates -- not just talking about the cannonical (and IMO poor) example of "container classes", but for complex related type hierarchies, parser tools, math structures, etc.

The stigma of templates being useful just for container classes and a few other isolated cases (which a language could well implement as a special feature) is really unfortunate. I suppose that's because container classes are the next obvious step for a C programmer. But if you spend a few weeks experimenting with languages like Haskell (not useful for practical programming, but a GREAT thing to learn), you come back to C++ templates with a completely new perspective and start writing code in a much more compact and general way!

(Here I'm advocating template-style functionality -- I actually think the C++ syntax for templates is pretty kludgy, but that's a minor issue in the grand scheme of things.)

Unfortunately, right now in C++, it is difficult and unintuitive to do, but it is possible (there's a nice book that discusses some of these things, and you'll be amazed at what they can get templates to do - Generative Programming by Krzysztof Czarnecki, and Ulrich W. Eisenecker).

Agreed 101%!

-Tim

As someone who writes tons of vector math code in production applications, my feeling is that a language which doesn't support operator overloading and template-style programming is really going to be really painful for moden math-intensive applications, such as games, modelling programs, etc.

I'm not necessarily advocating C++'s approach (operator overloading can be confusing, such as using an overloaded "<<" operator to represent both bit shifting and character output!)

Haskell-style "typeclasses" are an interesting replacement for general operator overloading. This approach encapsulates the idea that a given operator like "+" or "*" should have the same notional meaning everywhere, even when operating on different data types.

A simple example is that "+" and "*" would belong to the "numeric" typeclass. If you create a new numeric typeclass of your own (for example, a "bigint" class), then you declare your class to belong to the "numeric" typeclass, and implement those specific operators. However, you wouldn't be able to create a "+" operator for a non-numeric class.

This can map to popular languages easily by having your class implement an abstract interface (aka typeclass) and provide an appropriate static or friend function for those operators.

However, this approach doesn't extend well to more general situations. For example, say you define a template like vector<float,4> (a mathematical 4-component vector), one wants the ability to multiply those vectors by scalars using "*", which requires the more general form of overloading.

-Tim

"John Fletcher" <J.P.Fletcher aston.ac.uk> wrote in message news:3B78E154.BC62E006 aston.ac.uk...

Quote from the specification for D:

Operator overloading. The only practical applications for operator overloading seem to be implementing a complex floating point type, a string class, and smart pointers. D provides the first two natively, smart pointers are irrelevant in a garbage collected language.

Another quote:

D has many features to directly support features needed by numerics programmers, like direct support for the complex data type and defined behavior for NaN's and infinities.

Comment:

For numerical computing it is convenient to define classes e.g. vectors, matrices and other entities beyond complex numbers, such as quaternions. For this overloading of operators such as +, -, +=, etc means that top level code can be easily written and readable.

John Fletcher

Okay, why is it that everybody thinks the C preprocessor is terrible and needs to be avoided?

Because it's terrible and needs to be avoided, of course!

C++ only has it for compatability; Java and C# and D don't have one. I just don't get this one.

Historically (beginning with C), macro preprocessors have served as a kludge to compensate for a lack of language power and optimizer ability. Macros were good an necessary in the C days, because you could often come pretty close to C++ style template programming if you were clever enough, using macros for casts and other tricks. You could also use them to construct optimized code (i.e. by defining the body of a loop in a macro, and unrolling the loop 100 times with the macro).

With a modern language, these kludges should not be necessary. If there is any particular case where you feel you could express a program more cleanly by using macros, then I recommend looking at that as a language or optimizer flaw to be fixed, and not a need for macros.

Unreal (the game) is probably a good production-code example. It's around 250,000 lines of code and uses macros for the following:

1. To expose metaclass information (i.e. class names, default constructors that a serializer can call) -- like MFC's techniques. All of this code would be unnecessary if the language supported classes as first-class objects (i.e. you can pass around a classref* which "represent" the class and exposes its static functions), static virtual functions, and static constructors.
2. To comment out large blocks of code. Would be unnecessary if /*...*/ comments could be nested.
3. To implement debug-specific code. This is actually unnecessary, a bad old habbit. We would be just as well off having a global constant debug=0 or 1, and having if(debug) {...} instead of #if debug.
4. To implement platform-specific headers. Only necessary because headers are necessary.
5. To perform template-style tricks. If the language has a great facility for type dependency (whether like C++ templates, or more general like Haskell), all of these things would be unnecessary. Even C++ templates aren't complete enough, i.e. there are no template typedefs (true type synonyms), and most production compilers have bizarre template bugs limiting what you can do.

I'm 100% sure the Unreal code would be simpler and cleaner if the language supported the above and all preprocessor support were eliminated.

-Tim

In D, get'ers and set'ers take advantage of the idea that an lvalue is a set'er, and an rvalue is a get'er:

class Abc
{
    int myprop;
    void property(int newproperty) { myprop = newproperty; } // set'er
    int property() { return myprop; } // get'er
}

which is used as:

Abc a;
a.property = 3; // equivalent to a.property(3)
int x = a.property; // equivalent to int x = a.property()

Why??!? :-) In current reasonable languages "a.x" is a variable access and "a.f(x)" is a function call.

Why complicate this so that "a.x" could either be a function call or a variable access, depending on its (possibly very complicated) context?

Also, this seems to create ambiguity (or context-specific special-casing of sematics) with function pointers. Given a reference to a function p taking a parameter, p=a could either mean calling it with a parameter of a, or initializing it to a.

I know Bertrand Meyer advocated this approach in Eiffel, but this has been shown to be one of several areas (along with, i.e. covariant typing on function parameters) where Eiffel's type system is unsafe and problematic.

Thus, in D you can treat a property like it was a simple field name. A property can start out actually being a simple field name, but if later if becomes necessary to make getting and setting it function calls, no code needs to be modified other than the class definition.

That breaks with open-world modules. For example, given a module declaring a class like:

class c
{
    int a;
};

How can you subclass it later on in another module like:

class d: public c
{
    int a() {...}
};

The similar question comes up with binary-compatible evolution of modules (i.e. Java's list of rules, "You can do the following things to evolve a class without breaking existing precompiled modules that depend on it". That's an essential thing that's vital to writing real-world programs, such as applications supporting plug-ins. The only sound solution to this is that every variable access in a program has to translate to a virtual function call, which obviously isn't reasonable.

-Tim

Frequently in the D news group you reject ideas because they don't "feel right". Respectfully submit that this is not a basis for informed decision. printf doesn't "feel right" to me and never did.

Language syntax is a creative work, influenced by history and aesthetics. Making a language "feel right" is vital to its success!

If D cannot use the STL (or a wrapped version of the STL), not many people will be using it.

Baloney! STL is something only a C++ programmer could appreciate.

Witness that when STL is translated to a language with a more flexible type system (such as Haskell), it basically "disappears" into much simpler native language functionality -- and you realize that half of STL consists of workarounds for C++ limitations, while the other half consists of workarounds for STL's limitations.

STL-like techniques have no place whatsoever in a cleanly designed language.

-Tim

Aw, c'mon guys. For n bits, you only need log2(n) xors and shifts.

uint16_t d;
uint16_t t0,t1,t2,t3;
int parity;

t0=d^(d>>8);
t1=d^(d>>4);
t2=d^(d>>2);
t3=d^(d>>1);
parity=t3&1;

-Tim

His code is wrong but his statement is right, and your statement about a worst-case complexity of Theta(n) for the parity of an n-bit number is wrong. Consider the following code:

int uint16_parity( uint16 x ) {
x = x ^ (x >> 8);
x = x ^ (x >> 4);
x = x ^ (x >> 2);
x = x ^ (x >> 1);
return x & 1;
}

Gunnar,

Thanks for the correction. I should've known better than to post a piece of code without testing it. :-)

-Tim

There exist many simple ways to construct the natural numbers from set theory, such as:

0 = {}
n+1 = {n,{n}}

Then one typically constructs the integers from equivalance classes of pairs of natural numbers, such that:

{a0,{a1}}={b0,{b1}} iff a0+b1=a1+b0

Is there a simple way to construct the integers directly from set theory, without making use of equivalance classes? In other words, I'm looking for a simple representation of the integers such that each integer is represented by a unique set, rather than an equivalance class of sets.

As a bonus it would be nice if the representation admitted a straightforward definition of addition, subtraction and multiplication.

Thanks,

Tim Sweeney

Here I will use the notation f^-1(x) for the inverse function of f(x), and in general f^n(x) for the nth iteration of f(x). For example, f^3(x) = f(f(f(x))).

Some obvious identities involving iterated functions are:

if f(x)=x+c then f^n(x)=x+nc
if f(x)=x*c then f^n(x)=x*c^n

A few more identities can be derived in closed form, such as f(x)=a*x+b. However, deriving a general formula for f^n(x) turns out to be remarkably hard, even for simple f.

Now, given f(x)=g(h(g^-1(x))), it's easy to see that f(f(x))=g(h(h(g^-1(x))).

And more generally, f^n(x)=g(h^n(g^-1(x))).

This identity is useful for determining the nth iteration of a function f(x), when we can represent f(x) as a composition of the functions g and h, where h is a function simple enough to determine h^n(x) directly.

For example, we know that

2*cos(x)^2-1=cos(2*x)

Replacing x with arccos(x), we have

2*x^2-1=cos(2*arccos(x))

Now, cos(2*arccos(x)) is of the form g(h(g^1(x))) where g(x)=cos(x) and h(x)=2x. Therefore, we derive

if f(x)=2*x^2-1 then f^n(x)=cos(2^n*arccos(x))

When I derived this result 13 years ago, it went a great way towards understanding the behaviour of chaotic dynamic systems: in iterating 2*x^2-1 many times, one quickly notices that small perturbations of the input value have a dramatic effect on later results. The mechanism for this becomes much less mysterious when you consider the equation cos(2^n*arccos(x)) as n grows large: the function is zooming through oscillations of the cosine function at an exponential rate.

With some simple scaling that doesn't affect the end results, one can transform these equations to

f(x)=x^2-1/2

Which just happens to be a point on the Mandelbrot set (defined by iterations of f(x)=x^2+c) where c=-1/2+0i.

So, I have a few questions related to this topic:

1. Are there any studies or research papers on the general study of determining f^n(x) for various functions?

2. Is a closed-form solution known for f^n(x) given f(x)=x^2+c?

3. Are there any studies or general results on f^n(x) where n is:

- Rational. Such a notation is clearly meaningful, i.e. f^2/3(x) is the function g(x) such that f(f(x))=g(g(g(x))).

- Real, i.e. f^pi(x). The iterative meaning of such a notation isn't obvious but from the obvious example of f(x)=x+c implying that f^n(x)=x+n*c it seems that such an extension could be defined.

Thanks,

Tim Sweeney

I have downloaded a lot of papers by David Hestenes and others on geometric algebra and am reading the book Clifford Algebra to Geometric Calculus by Hestenes,but I am still looking for some pratical examples of calculations done using this system of geometric algebra. Does anyone know of any examples?

Hello,

In writing 3D graphics code in C++, I've used geometric algebra to represent points (3D vectors), planes (3D bivectors), and quaternions (3D spinors, the sum of a bivector and a scalar). This approach works quite well, though I haven't yet found any fundamental improvements in using geometric algebra over more traditional matrix approaches.

Hestenes presets the basis-free nature of geometric algebra as one of its biggest strengths, but if you're a computer guy, the first thing you'll do in writing a geometric algebra library is to make the basis explicit.

-Tim

Does anybody know of work on extensions of Church Numerals beyond the natural numbers?

Church Numerals are a convenient way of encoding natural numbers in the lambda calculus. A Church Numeral N is a function that, given a function F as input, returns F iterated N times. In other words:

0 = lambda(f).lambda(x).x
1 = lambda(f).lambda(x).f(x)
2 = lambda(f).lambda(x).f(f(x))
n+1 = lambda(f).lambda(x).f(n(f)(x))

Church Numerals are interesting because they admit a very simple representation of addition, multiplication, and exponentiation:

a+b = lambda(f).a(f)(b(f))
a*b = lambda(f).a(b(f))
a^b = lambda(f).lambda(g).g(f)

In this spirit, we can write computationally valid (though perhaps mathematically odd-sounding) expressions such as:

sin*cos (x) = sin(cos(x))
sin^3 (x) = sin(sin(sin(x)))

One can imagine extending Church Numerals (as entities of the lambda calculus) beyond the natural numbers in an analogous way to extending the natural numbers to the integers, rationals, or reals: just as "2" is a function that iterates its argument twice, "-1" is a function that returns the inverse of its argument.

I'm intentionally oversimplifying, of course: such an "inverter" function only makes sense when its argument is a function with a valid inverse, but that does not necessarily invalidate the concept. Such a condition of invertability could perhaps be expressed in a sufficiently powerful dependent-typed lambda calculus.

I'm interested in any pointers to research along these lines because this seems like it may be a fruitful way of extending well-known mathematical concepts (such as addition, multiplication, and exponentiation) into functional concepts, in a well-defined way.

-Tim

I wasn't expecting someone to mention ZZT here! :-) Once in a while I take a short break from game programming and work on an interesting side-project. Currently I'm fascinated with the applications of type theory, and am experimenting with extensions that increase expressiveness at the expense of decidable typechecking and possibly even reduction.

Regarding Church Numerals, another thought along these lines is to extend the lambda calculus with a new primitive "-1", not itself definable as a finite lambda term, and define a new (possibly incomplete) reduction rule for it which captures the essence of a negative church numeral: that for all terms f and x, f(-1(f)(x))=-1(f)(f(x))=id.

It was mentioned that -1 is the fixed point of y=y+y+1, but that leads to an infinite expansion that does not appear to be computationally useful.

It is interesting to restate a problem such as "y such that f(y) = x", as -1(f)(x). Not that this causes a solution to magically appear! But it does move the problem from solving an equation to evaluating an expression in a lambda calculus augumented with the primitive "-1".

The notion of negative Church Numeral terms makes varying degrees of sense in different calculi. It is most interesting in a logic programming framework supporting terms with multiple "potential" values such as McAllester's Ontic: http://www.autoreason.com/. In this sort of framework, it seems that every function has a unique and perfectly sensible (though possibly multivalued, and not necessarily computable) inverse.

Regarding exponentiation ("a^b = lambda(f).lambda(g).g(f)"), this agrees with convention for all natural numbers, except for the somewhat questionable case of 0^0=0.

[Disclaimer: I'm presenting this experimentally and have not attempted to prove the soundness of the proposed extensions.]

Does Microsoft take the possibility of using C# for game development seriously? It seems like it could be considered either as a gameplay scripting language or as a full-blown development language once DirectX9 ships with full .NET support.

The language seems very capable in most regards and has many attributes of an excellent game scripting language, but it's garbage collection pauses seem to be a showstopper flaw. In prototype code that does an amount of realtime object creation that is reasonable for a current generation game, i.e. around 100 object allocations per frame at 60 fps, I'm seeing pauses of 2-3 seconds that occur once every 5-10 minutes.

Is this a feature or a bug?

Obviously one can't ship an action game that hits a 5 second pause every 5-10 minutes!

Note that in this scenario the amortized time going to garbage collection (under 3% of execution time) is totally acceptable. What's unacceptable is that it all happens at once and makes the application appear to be locked up. In a realtime app such as a game that attempts to run at 60 fps, it is necessary to establish a realtime expectation on garbage collection overhead (not a hard guarantee, but an expectation that we can count on being broken only very infrequently), such as "the garbage collector will never use more than 1 msec within any 10 msec period of time".

Also, out of curiosity, is this the same issue that causes the Visual C++ IDE to lock up for 5 seconds every 5-10 minutes? (I was assuming this was related to the non-Microsoft Perforce source control integration we use, but after experimenting with C# I wonder if this is an unavoidable aspect of managed code).

The .NET framework is awesome and I really hope this isn't a fundamental flaw of managed .NET code.

-Tim

Is there a reasonable way to concatenate two arrays in C#? As far as I can see:

1. There is no built-in operator to concatenate arrays.

2. There is no way of writing a general array concatenation function because C# doesn't support templates (as one would use in C++) and doesn't support low-level hacking to work around the need for casts (as one would use in C).

So, every time I want to concatenate two arrays, I have to create a new array of the proper length, then copy both arrays' data into the new array - something that takes 3 big complex lines of code, when I really want to just say "a+b".

Any thoughts? (Please pardon me if I'm missing something obvious!)

-Tim

F(A,B,0) = A+B
F(A,B,1) = A*B
F(A,B,2) = A^B
For instance F(3, 4, 3) = 3^(3^(3^3))

So F grows rather rapidly whith 'i'... What I would like to do is to interpolate F so that 'i' may be any real number, which would produce a function where addition, multiplication etc are only a special case. I think this is very faschinating, but I really have NO IDEA of how to do it.

This is a fascinating question, but I too have been unable to find any research of significance on the topic. It seems quite curious that such a fundamental question remains not only unanswered but also practically unasked.

Thoughts:

- Such a function of a,b,i isn't expressable as a Taylor series, because it grows arbitrarily fast.

- We shouldn't expect such a function to be commutative or associative for arbitrary i.

- It is not clear whether such a function would be continuous.

- It is not clear that mainstream mathematical tools are suitable for answering this question. In fact, given the lack of research into such topics, it is likely not.

Here is another interesting way of asking the question, which I pose recreationally because it hasn't been studied rigorously.

Rephrase your problem in the lambda calculus by defining f' as (lam i)(lam a)(lam b)f(a,b,i). And then f(a,b,i) is just i'(f)(a)(b), where i' is the generalized Church numeral corresponding to the real number i.

What is a Church numeral? It's a way of encoding numbers as functions, such that:

0 = (lam f)(lam x)x
1 = (lam f)(lam x)f(x)
2 = (lam f)(lam x)f(f(x))
...

What is a generalized Church numeral? It's their extension to the reals:

-1(f) = "the" inverse of the "function" f.
1/2(f) = "the" "function" g such that for all x, g(g(x))=f(x)

Where "the" and "function" are oversimplifications (in general, such objects are not one-to-one and are thus more general relations than functions, and in general they are not unique, so formally we might talk about equivalance classes of relations satisfying the Church numeral criteria.)

How does one compute with generalized Church numerals? This is an open question which, to my knowledge has not been studied. However, I think this does represent at least meager progress, in the same way that writing i=sqrt(-1) enabled the study of complex numbers before their properties were fully understood. To study something, one must first acknowledge that the thing might exist.

-Tim

Hello,

If your interest is directed towards type systems of real-world programming languages, focusing on type inference is not necessarily the most productive direction to take. As I see it, the subject mostly dead-ends around the point of sophistication of the Haskell type system, after which it becomes undecidable or at least unwieldy. This does not seem like a feature that will make it into future programming languages that are widely used. Though, the underlying concept of unification is very powerful and seem more promising -- if unification is your primary interest, then it could be very useful to explore it in other, more practical, situations than type-inference algorithms.

Here are two type-theoretic subjects that I feel hold the most promise towards improving future type systems:

1. The representation of "very dependent types", as originated by Jason Hickey. See http://www.cs.caltech.edu/~jyh/papers/fool3/default.html for the original paper. In earlier type systems, terms could reference (by symbolic binding or de Bruijn index) the 'parameter' part of outer lambda expressions. Very dependent types also expose the 'function' part of outer lambda expressions, but in a more general way than the recursive mu binder: they preserve partially-known information.

Thus you can use very dependent types to form arbitrarily complex dependent-typed records with recursive dependencies. This provides a framework that seems an ideal framework for representing object-oriented concepts such as self-type dependence (without resorting to a new binder as in Cardelli's object calculi), as well as uniformly representing dependent mathematic structures such as groups or rings. In my experience, very dependent types have proven very easy to work with and well-known concepts such as Cardelli's explicit substitutions approach, and Cardelli's subtyping-of-recursive-types are easily extensible to very dependent types.

As far as I'm aware, there is only one paper on this topic and the value of this research topic hasn't been widely recognized yet.

2. Type systems that combine non-determinism (at least at the type level) with type-forming and type-specification operators. The breakthrough paper on the topic is David McAllester's description of the Ontic language: http://ttic.uchicago.edu/~dmcallester/ontic-spec.ps. This also appears to be the only paper on the topic and the value of the research hasn't been widely recognized yet.

The notion of non-determinism in Ontic isn't the scary or impractical kind that is associated (by practical programmers) with languages like Prolog; here it can be used purely as a type-system tool that enables you to express such concepts as "the type containing the elements 1, 2, and 3"; "an element whose value is either 1, 2, or 3", "a subtype of the type of natural numbers", "the type of all subtypes of natural numbers", etc. The Ontic type system provides a direct and intuitive representation of concepts which are either difficult or indirect and circuitous to express in more traditional dependent-type systems.

One of the neat things of Ontic is that the idea of a typechecker assigning type judgements to each term context in the form "a:T" is replaced by the more general idea of assigning a (hopefully finitary) set of possible values to each term. This makes it easier to deal with complex subtyping situations such as f-bounds and recursive types.

Please note that I am not a type theorist, but a practical programmer who follows type theory research in search of ideas that may contribute towards future practical programming languages, so my advice here is biased in a direction that others are likely to disagree with.

-Tim

Hello,
A common mathematical definition of the greatest common denominator GCD(a,b) expresses the function in terms of the prime factors of the arguments: GCD(2^a0*3^a1*5^a2*...,a^b0*3^b1*5^b2*...) is 2^min(a0,b0)*3^min(a1,b1)*5^min(a2,b2)*... This definition extends easily to rational numbers, where the exponents of the prime factors may be negative. So we have, for example, GCD(2/3,5)=1/3.

The standard GCD algorithm on natural numbers (in C++ syntax) is:

int gcd(int a,int b) {return a==0? abs(b): b==0? abs(a): gcd(b,a%b);}

Where "a%b" means "the remainder obtained when dividing a by b".

In an attempt to be clever, I've extended the remainder operation to rationals by defining (a/b)%(c/d) to be (ad%bc)/bd where a,b,c,d are integers. This appears to extend the above GCD algorithm to rationals in the expected way. Any comments on whether this is sound?

Also, given possibly negative integers a,b, is there a standard convention on the sign of gcd(a,b)? I'm assuming it should be positive (it's the *greatest* common denominator after all), but don't want to miss out on any potential generality that could be gained.

Finally, is there an extension of the gcd operation to reals that brings some meaning to terms like gcd(e,pi)? Obviously in this case one would have to reason with something besides prime factorizations.

-Tim Sweeney

I'm developing a programming language similar in its type structure to McAllester's Ontic, where types and values are represented in a unified, dependent-typed framework. One of the major problems of the compiler is to characterize the cardinalities of various types in programs, and I'm posting this to informally share my results, and see if anyone has references to similar work. Here goes:

Every type T can be thought of as having a cardinality, Card(T) characterizing the number of unique elements of that type T. The cardinality of the empty type is 0, the cardinality of the unit type is 1, the cardinality of the boolean type is 2, the cardinality of the natural numbers is a countably infinite cardinal.

In this language, we can say:

- "1" is a single value, so it's cardinality 1.

- "1|2|3" is either 1, 2, or 3. It has 3 potential values, so its cardinality is 3.

- "a-natural-number" can potentially be any natural number, so its cardinality is countably infinite.

- Given a variable "x" representing an unknown natural number, "x|3" reduces to the single value "3" if x=3, or the two distinct potential values "x" and "3" if x!=3. In this case, we have to say its cardinality is 1|2. Thus to each term the compiler assigns not a single cardinality, but a set of potential cardinalities.

Characterizing the precise set of potential cardinalities of a term is a hard problem, especially as the complexity of the type system grows. However, conservatively approximating the potential cardinalities of an expression is tractable, and this is the course I've pursued.

I draw potential cardinalities from the set {0,1,m} where "m" stands for "many". Thus we can precisely characterize the cardinality of the empty type as 0 and the unit type as 1, while the cardinality of 1|2|3 and a-natural-number are both conservatively approximated as "m". The expression "x|3" above has cardinality 1|m.

This affects the language design in the following way. Each type-theoretic operator (such as "intersection of types", "union of types", "product types", "disjoint union of types" has a table characterizing the potential cardinality of the result as a function of the cardinalities of the input. For example, in {0,1,m} approximation, in a language with only atomic values and not functions, we can describe the union operation with:

{0} {1} {m}
{1} {1|m} {m}
{m} {m} {m}

In other words, the union of 0 with an element cardinality x is itself x, while the union of two elements of cardinality 1 can either be of cardinality 1 (if the elements are equal) or m (if unequal).

Everything I've said so far can be applied to set theory as well as type theory.

Now, the presence of functions in the type system complicates the cardinality characterization considerably, and becomes dependent on the intricate details of the type theory.

If the full variance of functions is built into the type theory, then every function of the form a->b is a subtype of c->d if b<:c and c<:a. In a type system without a universal element (u such that every type in the type theory is a subtype of u), every function is of cardinality "m", because every function has infinitely many subtypes. In the presence of a universal element, functions from the universal element to elements of cardinality 1 is itself of cardinality 1 because there are no subelements.

Since practical functions like lambda(x:a-natural-number).x have infinitely many subelements, they receive cardinality "m". This isn't completely satisfactory, because my language requires that programs be observationally deterministic -- "3" is a valid program, while "3|4" is not (though 3|4 may be used as an intermediate term in part of the program, for example as the domain of a function). Unfortunately classifying a function as cardinality "m" (which is necessary for the cardinality to be correct) prevented programs from being functions.

The realization that saved the day is that we can make a distinction between items that are observably multivalued (like 1|2) and items that are observably single-valued (like that function above) but, because of the nature of function variance, are inhabited by multiple subelements. To make the distinction, I draw cardinalities from the set {0,1,m,1f,mf} where {1f,mf} categorize sets of functions and {1,m} categorize sets of atomic values. Examples:

"1" has cardinality 1
"1|2" has cardinality m
"lambda(x:a-natural-number).x" has cardinality 1f.
"lambda(x:a-natural-number).x|x+1" has cardinality mf.
"1|2|lambda(x:a-natural-number).x" has cardinality m|om.

I have lookup tables for all of the basic type operations over the cardinality set {0,1,m,1f,mf} and everything behaves as expected. I can think of many extensions to the cardinality set of varying degress of usefulness but {0,1,m,1f,mf} seems sufficient for my purposes.

I'm interested if anybody has any comments or references to similar work. So far the only discussion I've found of cardinality is in the paper on Mercury (www.cs.mu.oz.au/research/mercury/information/ doc-latest/reference_manual_6.html), where there is a lattice of "determinism categories", and that only scratches the surface.

-Tim

Hi David,

Here are the practical reasons:

1. Since my programming language is aimed at practical applications, I require that all complete programs be deterministic -- in other words, any non-determinism (multivaluedness or zerovaluedness) is limited to internal computations, and not the observable results of running the program. This requires verifying that the program's type is of cardinality 1.

2. Like Ontic, I use nondeterminism to express the idea that a term has more than one potential value. Thus lambda(x 1|2|3|4).x+7 is a function whose domain is the range of integers from 1-4. This particular expression can't reduce any further: we can't evaluate "x+7" because we don't know what value x will take on. However, we can reduce the function lambda(x 3).x+7 to lambda(x 3).10, because we know that "x" can only take on the value 3. In general, whenever reading a function parameter, or a "recursive self-value", I need to examine the cardinality in order to determine whether a reference (formally, a de Bruijn index) can be released or whether it needs to remain there in the normal-form. This is why the potential cardinality set {0,1,m} works well for my application: all the language rules intimiately care about is whether a term is uninhabited, single-valued, or multivalued. There is no compiler logic special-cased, for example, for cardinality-2 elements.

By "recursive self-value", I mean an expression like {x 3|5|7,y x+3}. I represent such things as arrays with a special kind of de Bruijn index referring back to the enclosing function, rather than its parameter. This turns out to be a very expressive notation, allowing object-oriented data structures a la James Hickey's "Very Dependent Types" -- a type can not only depend on function parameters, but also on recursive values that aren't precisely known at specification time. For example {t:type,n:nat,a[n]:t} is an array containing a type t, a natural number n, and an array of n elements of type t. It's of cardinality m, but unifies with (for example) {char,7,"

3. The language takes the Curry-Howard isomorphism literally, and is the first language I know of that attempts this. (Whether this is a good idea remains to be proven). In it, "false" represents the 0-element type. For every type "t" (which is inherently a single-valued thing), the term ":t" means "the set of potential values of that type". Thus :false is of cardinality 0, :unit is cardinality 1, :int is of cardinality m (multivalued), etc.

My conditional expressions "if a then b else c" actually branch based on the cardinality of the condition. So there is no special boolean type along the lines of Haskell's "type Bool = True | False". If the cardinality is known at compile-time, the conditional expression reduces to one of its branches. Otherwise (i.e. if the cardinality is 0|1|m), it remains in normal form.

This brings up another topic of having to determine, at compile-time, for expressions whose cardinality is multivalued, whether the runtime is capable of reducing it to a known cardinality -- something that doesn't have to be done perfectly; any conservative approximation is fine. In other words, if you say "if {fermat's last theorem} then 2 else 3", the compiler gives you an error indicating that the condition is undecidable by the compiler.

I have a question: At least in my implementation, the base function is transformed to take an extra argument which of course will be the function itself. This is fine for when the function is appiled solely within the body of the function itself because I'll transform every use of the function to pass in the extra argument. The problem is this: What should happen if the function is passed to some other function not expecting the extra argument? What if the recursive function returns itself?

This should all work automatically if you're managing your environments/closures properly.

If you are looking into a purely runtime solution, look for information on closures (a combination of a function, and an "outer environment" - a binding of values to all of the variables in outer function contexts). In an ordinary language, at runtime, all variables in lambdas "outside" the current lambda are guaranteed to have well-defined values when it comes time to apply the current lambda.

If you're looking for a compile-time solution, check out Luca Cardelli's paper on "Explicit Substitutions". This is a compile-time mechanism for keeping track of bindings, and scales well to complex situations of functions calling functions recursively with functions as parameters. See http://www.pps.jussieu.fr/~curien/ExplicitSub.pdf. If this is too big a leap (the presentation is very technical) do a Google search for "de Bruijn indices" for background.

Personally, I find it easiest to represent recursive functions without the Y combinator approach (i.e. without passing a function "to itself")