Jump to content

  • Log In with Google      Sign In   
  • Create Account

The Bag of Holding

Oh. Yeah.

Posted by , 30 November 2012 - - - - - - · 705 views
Yeah, this just happened:

Attached Image

Abusing speed for fun and profit (not that kind of speed)

Posted by , 30 November 2012 - - - - - - · 626 views
It's a slow Friday afternoon so I figured I'd brain dump some things I've been playing with for Release 14 of Epoch.

As I've mentioned in the past, one of my proof-of-concept programs for R14 is a raytracer. This is for a few reasons:

  • Raytracing is just cool (and I have a nostalgic soft spot for it for ancient historical reasons)
  • Good raytracers can test a language's type system to its limits in the name of compactness
  • A raytracer can test a language's execution model to its limits in the name of performance

The raytracer project already revealed a lot of bugs and weak spots in the R13 type system implementation, which I've also mentioned before. So it's already been a huge win just on getting things in the language to work correctly and intuitively.

The other thing it did was light a fire under my butt to get Epoch's runtime performance more sane. The VM model I've been developing under is great for prototyping and knocking out features, but when it comes to execution speed, it leaves a lot to be desired. For comparison, a 300x300 pixel render of a single shaded sphere was taking over 8 seconds under the old, pure VM. I got that down to around 2 seconds by optimizing the VM implementation, but that's just not enough.

Back in the day, I worked on a realtime raytracing engine that could have done that scene at 40FPS on a sub-GHz CPU without breaking a sweat. I haven't ported the raytracer to C++ to benchmark the feature set, but my gut feeling is that anything in excess of 30ms for rendering time of that image is far too slow. In a perfect world, I want that sphere to be drawn basically realtime - and I think that may be doable.

In the interests of accomplishing that, I've started moving large swaths of the program into "[native]" functions. [native] is a tag which can be applied to Epoch functions which instructs the VM to run that function (and anything it tries to call) as native code. This is done by translating the VM bytecode into LLVM bitcode and then running the LLVM JITter to produce machine code that does the same things.

A fair amount of that transformation is trivial. Thanks to LLVM's static single assignment model, it's pretty easy to convert Epoch VM instructions to streams of comparable LLVM instructions. Thanks to the optimization passes in LLVM, turning that into insanely fast machine code is a walk in the park.

As a total side note, the "entity" model I built into Epoch ages ago has proven very useful for JITting. Since loops, conditionals, and other "code block" constructs are already abstracted in a convenient way in Epoch (and in the VM bytecode), it's drop-dead simple to convert an Epoch entity into an LLVM basic block. It's also wildly extensible - I could add more types of entities to Epoch and have them automatically support JITting just by dropping in a few lines of code.

So getting some of the raw arithmetic (ray/sphere intersections, vector normalization, dot products, etc.) into native code was a breeze. Where things got sticky was when it came time to start supporting the more interesting features of Epoch.

Sum types and pattern matching were the last two things I managed to get working in the JITter, so I'll ramble a little bit about those.

In Epoch, a sum type is stored basically as a struct that looks like this (in C):

struct SumType
   unsigned ActualTypeTag;
      // Each base type has an entry here, so e.g. int and float
   } Contents;

Thankfully, LLVM has first-class support for structure types, so adding the tagging was easy. Where it got painful was the union - LLVM has no union types.

What I wound up doing was kind of hacky, but it works: at JIT time, I look through all known possible types that might be stored in the union. The one with the largest size (in bits) becomes the "type" of the contents field of the LLVM struct. I then simply store things in those bits and occasionally do a type cast to reinterpret the bits as the correct type. So basically, more or less exactly what a C/C++ compiler would do with a union in the first place.

The difference is that Epoch unions are designed so that if you put type A into a sum type, you can never get back out anything but type A. If you replace the contents with something of type B, the type is now "permanently" type B. So it's 100% type safe and can't be used to do things like convoluted reinterpret_cast<> hacks. So the Epoch compiler will never emit an unsafe sequence of instructions that causes data to be misinterpreted via a sum type, which I think is pretty nifty. (Granted, it limits the usefulness of Epoch if you need bit hacks, but I have plans for fixing that via other mechanisms.)

Pattern matching became much more interesting, particularly the part where Epoch supports multiple dispatch via type matching. For example, consider this snippet:

structure Numeric :
  integer alpha,
  integer beta

structure Textual :
  string alpha,
  string beta

operate : Numeric n -> integer gamma = n.alpha + n.beta   // addition

operate : Textual t -> string gamma = n.alpha ; n.beta   // string concatenation

So far so good; this is just function overloading based on type, right?

But wait, there's more!

type Anything : Numeric | Textual

entrypoint :
   Anything a = Numeric(40, 2)
   Anything b = Textual("Hello ", "World")


"Anything" is an algebraic sum type, which can dynamically hold either Numeric or Textual objects. The overloads are checked at run time, providing a form of virtual dispatch; I can give "operate" a Numeric or a Textual - wrapped in an Anything - and it'll automatically call the right code at runtime.

So... virtual functions without classes. So what?

One more snippet:

type Geometry : Sphere | Box | Cylinder | PolygonMesh

collide : Sphere s1, Sphere s2 -> boolean collision = false { ... }

collide : Sphere s, Box b -> boolean collision = false { ... }

collide : Cylinder c, Box b -> boolean collision = false { ... }

// and so on

Suppose I'm writing a physics engine in Epoch. I want to handle every possible combination of object/object collision easily. In C++, I'd have to do some gross thing like double dispatch wrappers or visitor patterns or RTTI or some custom hodgepodge of all of the above.

In Epoch, I write each function once, and I'm done. For any combination of Geometry I pass to collide(), the runtime guarantees that the correct target will be invoked, based on the actual types of the Geometry algebraic sum type that I handed the call.

This works in the Epoch VM using magic functions called dispatchers. They examine the passed-in arguments for a function which has been detected (by the compiler) to perform type decomposition during pattern matching. Based on the types received, the dispatcher then transparently tail-calls into the correct function, or throws an error if no overload can handle the type combo provided.

Where this got sticky in LLVM was handling the tail call into the correct target function. There are two combinations of flow that have to work:

  • An Epoch VM function calls a native function and expects type decomposition along the way
  • A native function calls some other native function and expects type decomposition

In the former case, the type dispatcher has to read from the Epoch VM's stack and heap space to do the type matching. In the latter case, most of the type data actually lives on the native machine stack. So there are technically now three implementations of type matching in Epoch: one for VM->VM calls, one for VM->native calls, and one for native->native calls.


All these shenanigans have led me to a conclusion that I've sort of orbited around in the past: the Epoch VM is evil and needs to die.

I want to get away from the VM model eventually, since writing a full-fledged performant VM is a nasty job in and of itself and I don't want to be tied to it. I'd rather integrate the garbage collection model with native code generation (LLVM has some support for this anyways) and take advantage of essentially 100% native code generation for Epoch programs.

This will be a big effort, though, for several reasons:

  • Epoch's type system is still only partially implemented in terms of LLVM
  • Calling external native code is tricky, because of marshaling between garbage-collected "Epoch space" and the rest of the universe
  • Prototyping new features is much faster in the Epoch VM than in native code, so me being lazy, I naturally resist anything that'll complicate new feature development
  • Garbage collection will have to be reimplemented on top of LLVM instead of my own hacky version that exists now
  • Adding things like lexical closures, exceptions, etc. will become a lot trickier without being able to screw with the running program state in the VM

And I'm sure there are other hurdles that escape me at the moment.

Nonetheless, I'm eager to start moving in that direction. It's pretty clear that as an execution model the VM needs to die, and Epoch will never be competitive with other languages so long as it remains chained to a half-cooked VM implementation. R14 will probably support JITting most if not all of the language to native code, and within two or three releases I'd like to fully excise the VM from the codebase.

We'll see how that goes.


Posted by , 25 November 2012 - - - - - - · 845 views
Epoch, Raytracing
300x300 pixels in 480ms.

Just for fun, here's the source of the raytracer as it currently stands:

// Some working thought-space for the raytracer project for R14

type listnode<type T> : list<T> | nothing

structure list<type T> :
	T value,
	listnode<T> next

structure Point :
	real x,
	real y,
	real z

// TODO - fix type aliases
structure Vector :
	real x,
	real y,
	real z

structure Ray :
	Point origin,
	Vector direction

structure Sphere :
	Point center,
	real radius

structure Plane :
	Point origin,
	Vector normal

type Geometry : Sphere | Plane

structure Color :
	real r,
	real g,
	real b

structure Light :
	Point location,
	Color color,
	real intensity

dot : Vector ref v1, Vector ref v2 -> v1.x * v2.x + v1.y * v2.y + v1.z * v2.z [native]
dot : Vector ref v1, Point ref v2 -> v1.x * v2.x + v1.y * v2.y + v1.z * v2.z [native]
dot : Point ref v1, Point ref v2 -> v1.x * v2.x + v1.y * v2.y + v1.z * v2.z [native]

intersect : Plane ref p, Ray ref r -> real t = 100000.0
	// TODO - implement plane intersection code

intersect : Sphere ref s, Ray ref r -> real t = 100000.0 [native]
	real b = dot(r.direction, r.origin)
	real c = dot(r.origin, r.origin) - 1.0
	real disc = 4.0 * (b * b - c)

	if(disc > 0.0)
		real distSqrt = sqrt(disc)
		real t0 = 0.0
		if(b < 0.0)
			t0 = (-2.0*b - distSqrt) / 2.0
			t0 = (-2.0*b + distSqrt) / 2.0

		real t1 = c / t0

		if(t0 > t1)
			real temp = t0
			t0 = t1
			t1 = temp

		if(t1 > 0.0)
			if(t0 < 0.0)
				t = t1
				t = t0

intersect : nothing, Ray ref r -> 100000.0

structure Camera :
	Point location,
	Vector direction,
	real horizontalFOV,
	real verticalFOV

structure Scene :
	list<Geometry> objects,
	list<Light> lights,
	Camera camera

test : nothing, Ray ref r, Geometry ref closest -> 100000.0

test : list<Geometry> ref geometry, Ray ref r, Geometry ref closest -> real t = 100000.0
	real thist = intersect(geometry.value, r)
	if(thist < t)
		t = thist
		closest = geometry.value

	listnode<Geometry> nextnode = geometry.next
	real nextt = test(nextnode, r, closest)
	if(nextt < t)
		t = nextt

findclosesthit : Scene ref scene, Ray ref r, real ref t, Geometry ref closest
	t = test(scene.objects, r, closest)

shade : Scene ref scene, Ray ref r, real t, Sphere ref obj -> Color c = 0.0, 0.0, 0.0
	real px = r.origin.x + r.direction.x * t
	real py = r.origin.y + r.direction.y * t
	real pz = r.origin.z + r.direction.z * t

	// Hack: assume our intersection point lies on a unit sphere, so the normal == point
	Vector normal = px, py, pz
	Vector lightdir = 3.0 - px, 3.0 - py, -8.0 - pz

	real i = dot(normal, lightdir)
	if(i > 0.0)
		c.r = i * 0.306
		c.g = i * 0.584
		c.b = i * 0.816

trace : Scene ref scene, Ray ref r -> integer c = 0
	Geometry closestobj = scene.objects.value
	real t = 100000.0

	findclosesthit(scene, r, t, closestobj)
	if(t < 100000.0)
		Color color = shade(scene, r, t, closestobj)
		c = rgb(color)

structure Point2D :
	integer x,
	integer y

structure Rect :
	integer left,
	integer top,
	integer right,
	integer bottom

structure PaintInfo :
	integer hdc,
	boolean erase,
	Rect paintarea,
	boolean restore,
	boolean incupdate,
	integer reserved0,
	integer reserved1,
	integer reserved2,
	integer reserved3,
	integer reserved4,
	integer reserved5,
	integer reserved6,
	integer reserved7

structure WindowClass :
	integer Size,
	integer Style,
	(WindowProc : integer, integer, integer, integer -> integer),
	integer ClassExtra,
	integer WindowExtra,
	integer hInstance,
	integer hIcon,
	integer hCursor,
	integer hBackgroundBrush,
	string MenuName,
	string ClassName,
	integer hIconSmall

structure MessageInfo :
	integer hwnd,
	integer message,
	integer wparam,
	integer lparam,
	integer time,
	Point2D point

GetModuleHandle : integer null -> integer handle = 0 [external("Kernel32.dll", "GetModuleHandleW")]
RegisterClassEx : WindowClass wc -> integer16 atom = 0 [external("User32.dll", "RegisterClassExW")]
CreateWindowEx : integer exstyle, string classname, string windowname, integer style, integer x, integer y, integer width, integer height, integer hwndparent, integer hmenu, integer hinstance, integer param -> integer windowhandle = 0 [external("User32.dll", "CreateWindowExW")]
ShowWindow : integer hwnd, integer cmdshow -> integer success = 0 [external("User32.dll", "ShowWindow")]
GetMessage : MessageInfo ref msg, integer hwnd, integer filtermin, integer filtermax -> boolean success = false [external("User32.dll", "GetMessageW")]
TranslateMessage : MessageInfo msg -> boolean success = false [external("User32.dll", "TranslateMessage")]
DispatchMessage : MessageInfo msg -> integer unused = 0 [external("User32.dll", "DispatchMessageW")]
BeginPaint : integer hwnd, PaintInfo ref paintinfo -> integer hdc = 0 [external("User32.dll", "BeginPaint")]
EndPaint : integer hwnd, PaintInfo paintinfo -> integer success = 0 [external("User32.dll", "EndPaint")]
PostQuitMessage : integer exitcode [external("User32.dll", "PostQuitMessage")]
DefWindowProc : integer hwnd, integer msg, integer wparam, integer lparam -> integer ret = 0 [external("User32.dll", "DefWindowProcW")]
DestroyWindow : integer handle -> integer ret = 0 [external("User32.dll", "DestroyWindow")]

LoadCursor : integer hinstance, integer cursorid -> integer cursorhandle = 0 [external("User32.dll", "LoadCursorW")]

MessageBox : integer hwnd, string message, string caption, integer style -> integer ret = 0 [external("User32.dll", "MessageBoxW")]

	buffer RenderedBitmap = 300 * 300 * 4

normalize : Vector ref in [native]
	real length = sqrt(in.x * in.x + in.y * in.y + in.z * in.z)
	in.x = in.x / length
	in.y = in.y / length
	in.z = in.z / length

rgb : Color ref c -> integer ret = 0
	ret += cast(integer, c.b * 255.0)
	ret += cast(integer, c.g * 255.0) * 256
	ret += cast(integer, c.r * 255.0) * 65536

timeGetTime : -> integer ms = 0 [external("WinMM.dll", "timeGetTime")]

entrypoint :
	Point zero = 0.0, 0.0, 0.0
	Vector zero2 = 0.0, 0.0, 0.0

	Sphere sphere = zero, 1.0

	Color white = 1.0, 1.0, 1.0
	Light light = zero, white, 1.0

	list<Geometry> objects = sphere, nothing
	list<Light> lights = light, nothing
	Camera camera = Point(0.0, 0.0, -10.0), Vector(0.0, 0.0, 1.0), 1.0, 1.0

	Scene scene = objects, lights, camera

	Ray ray = Point(0.0, 0.0, -10.0), zero2

	integer startms = timeGetTime()

	integer yoffset = 0

	integer y = 0
	integer x = 0

	real rayy = 0.0

	while(y < 300)
		rayy = cast(real, 150 - y) / 300.0
		yoffset = (300 - y) * 300
		x = 0
		while(x < 300)
			ray.direction.x = cast(real, 150 - x) / 300.0
			ray.direction.y = rayy
			ray.direction.z = 1.0

			integer c = trace(scene, ray)
			plotpixel(RenderedBitmap, (yoffset + x), c)



	integer endms = timeGetTime()

	print("Render complete, time in ms: " ; cast(string, endms - startms))


AdjustWindowRect : Rect ref r, integer style, boolean menu -> boolean result = false [external("User32.dll", "AdjustWindowRect")]

DisplayWindow :
	integer IDC_ARROW = 32512
	integer WS_OVERLAPPEDWINDOW = 13565952
	integer CW_USEDEFAULT = -2147483648
	integer SW_SHOW = 5
	integer MB_ICONEXCLAMATION = 0x30

	integer hInstance = GetModuleHandle(0)

	WindowClass wc = sizeof(wc), 0, MainWindowProcedure, 0, 0, hInstance, 0, LoadCursor(0, IDC_ARROW), COLOR_WINDOWFRAME, "", "RaytracerClass", 0

	Rect adjusted = 0, 0, 300, 300
	AdjustWindowRect(adjusted, WS_OVERLAPPEDWINDOW, false)

	integer hwnd = CreateWindowEx(0, "RaytracerClass", "Raytracer", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, 0, adjusted.right - adjusted.left, adjusted.bottom - adjusted.top, 0, 0, hInstance, 0)

	ShowWindow(hwnd, SW_SHOW)

	Point2D pt = 0, 0
	MessageInfo msg = 0, 0, 0, 0, 0, pt

	while(GetMessage(msg, 0, 0, 0))

structure BitmapInfoHeader :
	integer size,
	integer width,
	integer height,
	integer16 planes,
	integer16 bitcount,
	integer compression,
	integer sizeimage,
	integer xppm,
	integer yppm,
	integer used,
	integer important

SetDIBitsToDevice :
	integer hdc,
	integer xdest,
	integer ydest,
	integer width,
	integer height,
	integer xsrc,
	integer ysrc,
	integer startscan,
	integer scanlines,
	buffer ref bits,
	BitmapInfoHeader ref bitmap,
	integer coloruse
	integer unused = 0
  [external("Gdi32.dll", "SetDIBitsToDevice")]

MainWindowProcedure : integer hwnd, integer message, integer wparam, integer lparam -> integer ret = 0
	integer WM_PAINT = 15
	integer WM_DESTROY = 2
	integer DIB_RGB_COLORS = 0

	if(message == WM_PAINT)
		Rect prect = 0, 0, 0, 0
		PaintInfo ps = 0, false, prect, false, false, 0, 0, 0, 0, 0, 0, 0, 0

		integer hdc = BeginPaint(hwnd, ps)

		BitmapInfoHeader bitmap = sizeof(bitmap), 300, 300, 1, 32, 0, 0, 0, 0, 0, 0
		SetDIBitsToDevice(hdc, 0, 0, 300, 300, 0, 0, 0, 300, RenderedBitmap, bitmap, DIB_RGB_COLORS)

		EndPaint(hwnd, ps)
	elseif(message == WM_DESTROY)
		ret = DefWindowProc(hwnd, message, wparam, lparam)

Clearly, most of the bulk is boilerplate for interacting with Windows. The actual raytracing logic is pretty compact, and easy to extend via the wonders of Epoch's multiple type dispatch system.

I really don't have much point for this entry except to exude happiness that I managed to get enough of the JIT native code generator working to do most of the heavy lifting in native code instead of using the VM.

I've said this before when neck-deep in LLVM, but I'm seriously pondering just killing off the VM entirely and shifting over to 100% native code generation. It's not terribly hard, just really tedious to get right, and the gains are magnificent.

A couple days ago it was taking 8 seconds to draw the same image that I can now produce in less than half a second. Some of that came from fiddling around in the VM but most of it came from native code execution. The real beast is going to be getting full support for the Epoch type system implemented in native code; I can sort of access structures in the current model but the whole thing is kind of rickety and fragile. It'll take some serious effort to get the JIT code up to a point where it's robust and generalized.

Anyways... enough rambling. It's 3:30 AM and I should probably go to bed.

Tasty, tasty raytracing!

Posted by , 23 November 2012 - - - - - - · 937 views
As threatened, I've been working on a raytracer implemented entirely in Epoch. The results so far are promising:

Attached Image

Render times are hovering around 1.8 seconds for a 300x300 pixel image. Considering that the image itself should be drawable in basically real-time, there's obviously a lot of room for improvement in the VM.

However, that 1.8 second figure is already down from over 8 seconds when I started on the raytracer project, so I'd say I've already accomplished some pretty decent speedups in the VM just from playing around with this.

I also haven't turned on JIT native code generation for any part of this (the JITter needs a lot of love) so there's a good chance I can speed it up another order of magnitude by executing native code instead of running everything on the VM.

All in all, not a bad bit of work, I must say. It's fun by itself to work on raytracing again, but I get to intermingle that with working on my own compiler and language, so I've been having a blast :-)

Eat Your Dogfood. It's Tasty.

Posted by , 20 November 2012 - - - - - - · 853 views
So a few days ago I shipped Release 13 of the Epoch programming language.

Turns out, that was a bad idea.

R13 has some seriously aggressive features in it. There's support for native algebraic sum types, type aliases (both "weak" in the sense of C/C++ typedefs and "strong" in the not-weak sense), and - most interestingly for me - templates. Moreover, R13 includes a lot of back-end refactoring to support all these features in a clean and relatively nice way.

As it happens, all of the unit tests for R13 functionality pass. So I was comfortable firing it out the gate, thinking that it was covered well enough that I could start writing some test software against R13's compiler and get some cool demo programs done.

One of the demo programs I wanted to write is a simple raytracer. This is for two reasons: first, a good raytracer can be a compact piece of elegant code. A bad raytracer can be a nightmare, as I know from firsthand experience. If Epoch allows the program to be written in a clean and elegant way, that's good; if the implementation has to be messy and gross, that's bad.

The other reason is it'll give me a nice foundation for improving the native-code JIT system, which will be crucial for keeping performance acceptable in running Epoch programs.

I had barely started working on the raytracer implementation when I found my first type system bug in the R13 compiler.

Long story short, I've spent almost all my time post-R13 fixing bugs that shouldn't have shipped in the first place.

Why did this happen? I have a suite of unit tests, including tests for all the new features. They all passed. Where did the bugs creep in?

The problem with unit testing something like a compiler is combinatorial explosion. Sure, templates work. Type aliases work. Sum types work. But once you reach the point where you need to use a templated sum type to store a type alias which refers to a sum type that might contain a templated structure instance, stuff gets messy.

Epoch is still a pretty fast-and-loose project in terms of development discipline, and I rather appreciate the freedom to fire off quick releases and move forward at my own pace. I'm interested in preserving that "culture", but at the same time, I really need to revisit my reliance on simplistic unit tests.

The only remotely non-trivial program I routinely test in Epoch is the Era IDE prototype, which isn't exactly stretching the compiler's limits at this point. Adding the raytracer to the test suite will be good in multiple ways: it will ensure that a decent cross-section of features gets tested as it would be used in real software; it will demonstrate good practices for writing software in Epoch; and it will provide a benchmark of both compiler and VM performance that I can hopefully continually improve on over time.

But that may not be enough. I think I need to start writing borderline-pathological test cases to make sure that all the cobwebs are swept out of the corners of the language - both in terms of design and in terms of implementation.

Good times.

Holy #&%* Release 13!

Posted by , 17 November 2012 - - - - - - · 696 views
So, yeah. I decided I didn't have any patience and went ahead and shipped R13.

Check it.

Templates! Type system enhancements! Bug fixes! It's got it all!

Release 13 preparations

Posted by , 15 November 2012 - - - - - - · 594 views
So now that templates are basically working, it's time to seriously start plotting the 13th release of the Epoch programming language.

I've hammered out a few basic cleanup and documentation tasks, but there's still a lot of room for improvement. My hunch is that at this point I'll probably set about documenting the code as it stands and churning through as many small refinements as I can stomach. Eventually I'll get horrifically bored with all that and decide to just package the whole thing up and ship it off as a release.

The project's issues list continues to shrink, although there's still a lot of really big-ticket items left on there. I'm personally kind of hung up on the desire to make sure that R13 accurately reflects my dedication to producing a quality piece of software. At the same time, though, I want to ship a release if for no other reason than to commemorate a significant milestone in the language's history.

My perfectionist side insists that all the documentation be complete and a minimum of TODOs be left littering the code, but my pragmatic (and substantially impatient) side will probably win out. In the end, I expect R13 to be mostly a celebration of the improve type system and template engine more than a paragon of clean code design and spotless implementation. I'm OK with that.

Of course, the big question is, after R13, what next?

Epoch has shifted its emphasis over the years several times, depending on what was predominantly motivating me to work on it at various times. There have been a number of lofty goals for the language, with varying degrees of focus depending on the month and year:

  • Something, anything but C++
  • A powerful metaprogramming language
  • A powerful framework for programming DSLs
  • Some kind of parallel processing workhorse
  • Some kind of distributed computing workhorse
  • Just a fun experimental base for prototyping out the way I want to write software, versus how I "have to" write it in contemporary languages

At this point, it's kind of a monster hybrid of all of those goals, and I'm slowly filtering through the apparent contradictions and conflicts until I manage to distill the whole nebulous mess into a coherent language.

That said, here's a glimpse of what I'd like to do.

One of the big questions left for Epoch is how to handle its object model. Type inference and template expansion become undecidable in the presence of certain type system features - namely, subtyping and certain forms of inheritance. This is a problem.

Another big question is how to combine heterogeneous computational hardware support (e.g. GPGPU stuff) with distributed processing with threading with whatever else might come up. This is just a messy question in general.

The last major question is runtime model. Right now things are basically run on a VM, but I've got prototype code in place for JIT compilation to native code via LLVM, which is really cool. Unfortunately, native code generation does not always play well with garbage collection and the other must-have features of the language.

On the face of it, those three questions may seem to lead in very different directions. Is Epoch a native language or a managed one? Does it do really well at modeling object-oriented systems, or does it support rich type inference and minimal explicit type annotation? And how does all the parallel/concurrent processing stuff fit in?

My answer is pretty simple, and dare I say so myself, fairly elegant.

Epoch will not have an object model, nor threading support, nor will it abandon the use of a VM as a runtime model.

Instead, Epoch will divide computational concerns into tasks. A task is simply a self-contained unit of work; think of it like an object, but without the restriction of living in some particular "memory space" or running on some specific thread.

An Epoch task is like a job in a job-based thread pool system. You can't access its memory from outside. All you can do is send it messages. In the same vein, the task cannot communicate to anything outside itself, except by sending messages.

Tasks, by virtue of being self-contained, can therefore be scheduled freely by the runtime. This includes spanning multiple CPU cores, or offloading to a GPU, or even moving them onto an entirely different network node.

A task can be tagged with a "hint" that tells the compiler and runtime how best to handle the task's computational processes. Tag it with [native] and it will be JIT-compiled to native code and run in a lightweight "green thread" on any available CPU core(s). Tag it with [gpu] and it will be compiled instead to a GPGPU program and executed on your graphics hardware. Tag it with [remote] and it can be transparently distributed across a network and load-balanced to an available Epoch-running machine on a whim.

Since tasks are lightweight by default, you can spin up thousands or millions of them with no problems. Tasks completely replace the need for object instances in traditional OO languages, while simultaneously solving a host of other software challenges in a single shot.

It's a pretty weird way to think of software development. I'm not even entirely sure I buy into the idea yet myself. But it feels right, it feels elegant and clean and powerful and robust, and it seems very promising.

The best part is, it won't take much work to make it happen. Almost all of Epoch's history has been slowly moving this direction in some sense or another, and it feels to me like this is just the culmination of years of subconscious rumination on how I really want to think about writing programs.

So what's next after Release 13?

Why, release 14, of course! And R14 will bring with it a few interesting changes:

  • entrypoint will become a task
  • Task support for green threads will be introduced
  • JIT compilation to native code will be enhanced a bit
  • Garbage collection will be refined in a few important ways

My idea for the R14 "demo app" is to write a basic raytracer. Via the virtues of JIT compilation and the task model, I think it could trivially harness all available CPU cores on a machine, and perform pretty damn well.

So the R14 goal, in a nutshell, is to deliver a language and a runtime platform that is suitable for performance-intensive software creation.

After that, it's all just polish and features. I'm starting to think this thing might actually become a viable development platform someday!

I'm still not entirely sure I believe that it works

Posted by , 13 November 2012 - - - - - - · 627 views
The following Epoch program now compiles and executes:

// Simple implementation of a singly linked list holding arbitrary data

type listnode<type T> : list<T> | nothing

structure list<type T> :
	T value,
	listnode<T> next

prepend<type T> : list<T> ref thelist, T value
	list<T> newlist = value, thelist
	thelist = newlist

append_recurse<type T> : list<T> ref thelist, nothing, T value
	list<T> newlist = value, nothing
	thelist.next = newlist

append_recurse<type T> : list<T> ref thelist, list<T> ref tail, T value
	append_recurse<T>(tail, tail.next, value)

append<type T> : list<T> ref thelist, T value
	append_recurse<T>(thelist, thelist.next, value)

next<type T> : list<T> ref thelist -> listnode<T> tail = thelist.next
next<type T> : nothing -> listnode<T> tail = nothing

checkvalue<type T> : list<T> ref thelist, T expected
	assert(thelist.value == expected)

checkvalue<type T> : nothing, T expected
	print("Unexpected end of list")

dumplist<type T> : list<T> ref thelist
	listnode<T> nn = thelist.next

dumplist<type T> : nothing

entrypoint :
	list<integer> numbers = 1, nothing

	append<integer>(numbers, 2)
	append<integer>(numbers, 666)
	prepend<integer>(numbers, 0)


	assert(numbers.value == 0)
	listnode<integer> node = next<integer>(numbers)
	checkvalue<integer>(node, 1)

	node = next<integer>(node)
	checkvalue<integer>(node, 2)

	node = next<integer>(node)
	checkvalue<integer>(node, 666)


This is the first implementation of a generic data type container in Epoch.

Suffice it to say it took a monumental effort to pull that off, and I am thoroughly exhausted. The fact that it's 4 AM has nothing to do with that.

Lots of cleanup needed now... there's a host of ugly hacks and leftover cruft floating around the code, and it'll take some time to improve things to the point where I'm happy with the implementation of templates in the language.

The flip side, though, is that I built a working implementation of templates in what amounts to a couple of weekends of work and a spare evening, so I'm pretty darn happy with that.

Refactoring makes my brain hurt.

Posted by , 09 November 2012 - - - - - - · 681 views
So as threatened, I implemented generic types last weekend. Took about a solid afternoon to make it happen, so not bad at all.

In the process, I realized that there's just a ton of code in the Epoch compiler in particular that's... gross. So I took a few days and cleaned it up substantially. As a bonus, adding namespaces to the language should be pretty smooth now, once I get around to it.

There's still a lot of cleanup left to do, and even more documentation; the code is in a sorry state these days due to a combination of neglect and churn... which, now that I say it out loud, is a weird combination.

Anyways, bottom line is that I need to spend a healthy chunk of time just going through the entire code base and making it sleek. Apparently people actually download the code on occasion, so it's worth making sure that the quality reflects on my actual programming habits and not my quick-and-dirty prototyping habits :-D

I'll probably split the next few weeks between minor cleanup tasks and implementing generic (i.e. templatized) code generation. That's going to be a nightmare.

Back in the saddle

Posted by , 03 November 2012 - - - - - - · 770 views
So once again I've dug out and dusted off the code for Epoch. The last several days have been pretty productive; I finished off the implementation and testing of algebraic sum types, and now the following program compiles and passes all tests:

// Simple implementation of a singly linked list holding integers

type listnode : list | nothing

structure list :
	integer value,
	listnode next

prepend : list ref thelist, integer value
	list newlist = value, thelist
	thelist = newlist

append : list ref thelist, integer value
	append_recurse(thelist, thelist.next, value)

append_recurse : list ref thelist, nothing, integer value
	list newlist = value, nothing
	thelist.next = newlist

append_recurse : list ref thelist, list ref tail, integer value
	append_recurse(tail, tail.next, value)

next : list ref thelist -> listnode tail = thelist.next
next : nothing -> listnode tail = nothing

checkvalue : list ref thelist, integer expected
	assert(thelist.value == expected)

checkvalue : nothing, integer expected
	print("Unexpected end of list")

dumplist : list ref thelist
	listnode nn = thelist.next

dumplist : nothing

entrypoint :
	list numbers = 1, nothing

	append(numbers, 2)
	append(numbers, 3)
	prepend(numbers, 0)


	assert(numbers.value == 0)
	listnode node = next(numbers)
	checkvalue(node, 1)

	node = next(node)
	checkvalue(node, 2)

	node = next(node)
	checkvalue(node, 3)


I'm pretty happy with that, considering I've been gone for the last several months (jeez... was it really April that I made the last release!?). (For the record, I haven't been slacking off... I just shipped this little game nobody's ever heard of during that time.)

Next up, I'm tackling generic programming. The easy part will be generic structures:

structure testwrapper<type T> :
	T contents,
	string tag

entrypoint : 
	testwrapper<integer> intwrap = 42, "number"
	testwrapper<string> strwrap = "test", "text"

	assert(intwrap.contents == 42)
	assert(strwrap.contents == "test")


It'll be much harder to implement generic functions:

add<type T> : T a, T b -> T sum = a + b

entrypoint :
	integer foo = add<integer>(40, 2)
	integer bar = add<real>(3.0, 0.14)

	assert(foo == 42)
	assert(bar == 3.14)


Hopefully I can knock out the quick foundation of generic structures over this weekend (it's pretty trivial) and then dig into generic code gen later on.

So that's what's up.

November 2012 »