Rhope Blog

Blog Home Downloads Documentation RSS

BlastEm 0.2.0

by Mike Pavone

I've released a new version of my Genesis emulator. In addition to fixing a bunch of bugs I added an OpenGL rendering backend, turbo and slow modes and GDB remote debugging support. You can download it from the main BlastEm page. A more complete list of changes from version 0.1.0 is available here.

Permalink/View Comments

ICFP Contest 2012: A new language makes for fun and frustration

by Mike Pavone

July 17, 2012
A new language

About 4 months ago I started work on a new programming language, tentatively called TP. The goal was to create a language that would be amenable to use in a structured editor on a tablet (TP is short for tablet programming). Syntactically it takes a lot of inspiration from Smalltalk. Also coming from Smalltalk is the idea of making true and false separate types with an if/else construct implemented as a method on those types and using closures for the blocks. I rather liked Javascript's object literals so I borrowed that idea, though objects in TP are not nearly as dictionary like as those found in Javascript. Modules are just objects (or lambdas that return an object) and import can be used to add messages to any object from any other object, not just modules.

I had hacked together an implementation in Javascript using PEG.js for parsing and done a bit of work on a prototype structured editor before I stopped working on the project about 2 months ago. About 2 weeks before the contest, I decided it might be fun to try and use TP rather than Rhope this year assuming I could get a native backend of some sort working for the contest. On July 7th (the Saturday before the contest), I had a basic C backend that could compile some very trivial programs and on the evening of the 9th closures were working well enough to support if:else. I continued to work on the language that week and by Thursday night I had closures as methods working properly (i.e. you could close over variables in the constructor or a function said constructor was nested in) and some very basic string support.

You can poke at the source for TP in the repository. In particular, checkout the samples and modules directories for an idea of what TP code looks like.

Frustration

The first half of Friday felt pretty good. My teammate, Bill, was picking up the language well and despite having to stop and add some bindings for file IO to the language I felt like our pace was good. As the day progressed; however, we started running into serious bugs in the language implementation. As a result, I spent most of my time during the first 2 days of the contest working on the compiler while Bill worked on the simulator.

Things started to look up on Sunday morning. We were able to get the simulator working for the basic game and I was finally able to turn my attention to our bot. By the end of the contest I had a bot that could solve the smaller basic maps. Unfortunately fatigue and deficiencies in the string library prevented Bill from successfully implementing any of the other game modes and I was too busy trying to make our bot suck less to help.

Bot Strategy

Our bot performs a breadth first search of all valid moves and every k steps it picks the n best states according to a heuristic based on the number of lambdas collected, the distance to the next goal (either a lambda or the open lift) and whether the lift is still accessible. For our submission k was set to 3 and n was set to 128. Additionally, we maintained a hashset of game states (only the hashes themselves were stored for space reasons) to eliminate useless paths (waiting when no rocks are in motion, moving back and forth over the same spaces, etc.). We also stored the current best terminal state, so that if we failed to find a solution we could return that.

Results

With the settings we used in our submission, our bot is able to solve contest1, contest3, contest4, contest5 and contest7 with scores matching the best ones on the web validator. It solves contest2 with a score of 280 (one less than the best). It manages a respectable 1129 on contest6. On contest8 it fails to stop the initial falling rock from blocking the lift and eventually gets trapped in the chamber on the right side of the map. It ends with a score of only 706. Unfortunately, for contest9 and contest10 it takes far to long to end its search and I didn't have time to implement SIGINT handling so it won't return it's current best terminal solution when time is up. Eventually (after 10+ minutes) it comes up with a score of 1943 for contest9.

Since support for the other game modes was never finished in the simulator and the bot depends on the simulator code it generally doesn't do well on maps using them (though it does manage a 280 on flood2).

You can find our submission in our repo.

Closing Thoughts

While I'm somewhat disappointed with the final performance of our bot (and I'm sure I'll be even more disappointed with it once I see the contest results), I'm pretty satisfied with our performance this year. The immaturity of the language was a major obstacle and time sink, but despite that we were still able to submit a reasonable entry. I also feel like we worked better as a team this year. The task was a lot of fun and a good challenge.

Permalink/View Comments

New Job

by Mike Pavone

About two weeks ago, I started a new job at Bigpoint's San Francisco office. It's a fun place to work and should present opportunities to work on interesting projects in the future.

Due to the move involved, I haven't made a whole lot of progress on Rhope the past few weeks, but I did manage to make a small amount of progress over the weekend. My hope is to get a simple native x86-64 backend working and add support for lambdas before the ICFP contest in June. At least some basic multi-thread support in the runtime would be nice to have as well, but I don't know if I'll get to it in the next month and a half.

Permalink/View Comments

Boston Too

by Mike Pavone

In a previous post, I mentioned I was looking to move on to a new job in a location that's better suited to finding the kind of jobs that interest me. That post suggested I was only interested in the San Francisco Bay area; however, I'm also interested in the jobs in the greater Boston area too. So if you have an challenging opening for a programmer in that area, feel free to send me an email at pavone@retrodev.com.

Permalink/View Comments

Rhope is Officialy Self-Hosted

by Mike Pavone

So Rhope is now properly self-hosted. Actually, it has been for almost two weeks. At some point in the hopefully not two distant future I'll do a proper release so you can get the compiler running without bootstrapping through the interpreter, but I want to do some more cleanup first. Most recently I've ported the new parser I started a while back to the version of Rhope implemented by the compiler. Unfortunately it's not as close to being done as I remember it. It only handles the top level syntax at the moment so there's still a fair amount of work before I can replace the old messy one. In the meantime, you can get the compiler by cloning the Mercurial repository. You'll need a 64-bit Linux box, a C compiler and make. To build the compiler run the following commands from the directory in which you checked out the repo:
make -f makefile.linux ./rhope -t 1 compile_old.rhope compile_old_c.rhope mkdir build ./ctobin compile_old_c.rhope -O1 mv build/compile_old_c ./rhope2c ./compile compile_old_c.rhope -O1
Once I put together a proper release it will be much simpler and hopefully I'll have resolved some of the portability issues (FFI doesn't currently have a proper way of dealing with integer types that are different sizes on different platforms and struct stat doesn't have a consistent layout from one platform to the next).

Permalink/View Comments

Hire Me

by Mike Pavone

I've plateaued at my current job. I haven't felt challenged there in a long time and that's unlikely to change anytime soon. My current location in Connecticut, isn't exactly a great place for exciting programming jobs unless you want to work in the financial industry. To that end, I'm looking for a job in the San Francisco Bay area.

If you work for a tech company in that area looking for a programmer that's comfortable with language design and implementation, reverse engineering or more mundane things like web development I might be the guy you're looking for. If you want to learn more, check out my resume or send me an email.

Permalink/View Comments

Compiler Status

by Mike Pavone


The Rhope compiler is mostly self-hosting now. There are actually two versions of the compiler: one written in the version of Rhope implemented by the old interpreter and one written in the version implemented by the compiler. The compiled version of the compiler produces output, but that output is somewhat broken. The C code it generates compiles successfully but the resulting executable does not work as intended. Further the compiled version of the compiler is excruciatingly slow due to some inefficiencies in the string implementation. Once I get the performance reasonable I should be able to fix the issue with the incorrect output relatively easily and then the version targeting the interpreter can be removed.

Permalink/View Comments

Foreign Function Interface

by Mike Pavone

I've gotten a basic version of the foreign function interface working in the Rhope compiler. Currently, you can only call functions that are in the C standard library or the Rhope runtime, and the types it supports is limited, but I hope to address that soon.

Here's an example of how to declare a foreign function in Rhope:
Foreign C:libc { putchar[char(Int32,Naked):result(Int32,Naked)] }
The above declares a C foreign function in the library libc named putchar with one input and one output. In this case both the input and the output is an unboxed signed 32-bit integer. After putting this declaration in the toplevel of a Rhope source file, you could call putchar is if it were a normal Rhope worker.

Adding the FFI has allowed me to write the implementation of Array mostly in Rhope with a few small helper functions in C. Once the FFI is finished, writing an initial version of the File type will be relatively straightforward. Once I have access to file I/O, I just need to implement higher order functions and a few more types (String, List and Dictionary) and I should be able to get the Rhope compiler compiling itself (with a few small modifications due to changes I've made in the language).

Permalink/View Comments

Date and Time

by Mike Pavone

I have this bad habit of having a burst of productivity, setting a tentative schedule based on said productivity and then having a lull in my productivity causing me to totally miss my goal. I haven't really made much progress on the compiler since my last post. I have made some progress on some other areas though, the biggest one being the addition of a Date Time object. There's been a Unix Time[] worker in the repository version of the interpreter for a while now, but if you wanted to do anything useful with the values it returned you were pretty much on your own. Now date.rhope has some basic code for converting those values into a more useful format and formatting into human readable strings.

For instance, you can do:
[Now[]]Format["M/D/Y h:m:s a"]
and you would get backsomething like
12/4/2009 06:53:00 AM

There also some convience functions for common date formats like:
[Now[]]RFC 2616
which will return a date in the preferred format specified by RFC 2616 (HTTP 1.1) like so:
Fri, 04 Dec 2009 06:53:00 GMT

The code needs a fair amount of work (leap year code isn't quite right, leap seconds aren't handled, no support for date math, etc.), but it's a start. For now it should be good enough for me to finally add dates to my blog entries and add caching to my simple Rhope webserver.

I'm actually planning on making a number of other enhancements to the webserver this month. The shared hosting provider that I host the main retrodev site on has raised their rates and Linux VPS hosting has gotten quite cheap so the plan is to consolidate the Rhope website and the main retrodev site onto a single VPS. I'd like to avoid having to run multiple webservers so I need to improve support for static content (thus the caching) and add support for FastCGI or something similar for the repository.

Hopefully this will result in a more stable (Linux on a proper server rather than Syllable Desktop on a desktop class machine with no case) and faster loading site for Rhope as well as simplifying my hosting a bit. If I'm lucky I'll even save a little money by reducing my home electric usage.

Permalink/View Comments

Compiler Status

by Mike Pavone

In the past couple of weeks I've made some good progress on the Rhope compiler. It can currently compile a number of simple Rhope programs to C. Here's what language features that are working:
- Worker definition
- Worker calls
- Blueprint definition
- Method definition
- Method calls
- Type annotations on both worker arguments and object fields
- Basic integer operations and literals(Int32 type only)
- Boolean literals (Yes,No) and the If method
- Blueprint literals and the Build worker

I haven't put together a proper release for this yet and I probably won't until the compiler can compile itself. For now you can checkout a copy from the repository. My current goal is to get the compiler compiling itself and make a proper release before the end of October. What follows is basically my todo list to get to that milestone.
- Add a basic type inference engine
- Add support for unboxed operations on primitive integers
- Add support for a simple Array type
- Write implementations of String and List using said Array type
- Add a mechanism for calling native C functions
- Write a basic implementation of File in Rhope
- Write an implementation of Dictionary in Rhope

Technically, Array support isn't required for String or List, but it useful for performance reasons and it will be needed for the FFI anyway. Once all that is done, my next goal will to get all the features this blog uses working (basically everything required for the compiler plus multi-threaded execution, transactions and networking support). I hope to have that done by the end of November.

My last post didn't generate any responses so if you have the itch to work on a compiler feel free to join in. Send me an email, leave a comment here or just clone the repository and get started if you want to help.

Permalink/View Comments

Rhope Wants You

by Mike Pavone

Up until now, Rhope has been open source in the sense that the source has been released under an OSI approved license (namely the 3 clause BSD license), but not in the sense that it accepted external contributions. This was partly because no one had expressed much interest in contributing, but also because I felt the direction of the language was not well enough defined for outside contributions to be terribly useful. However, I now have a much better idea of what Rhope needs to be and it's clear that if Rhope will ever be more than just a hobby language I'm going to need some help.

To that end, I've opened a public repository containing Rhope's source code. Currently this repository contains the Alpha 2 source with some fixes and enhancements, the beginnings of a compiler and some initial work on a new runtime (take a look at the runtime directory). To get your own copy of the repository you'll need Mercurial. Once you have that installed, you can enter hg clone http://rhope.retrodev.com:8000/main somedir, where somedir is the directory you want to store your copy in.

If you want to contribute, send me an e-mail mentioning what you would like to work on at pavone@retrodev.com or leave a comment on this post so that duplicate effort can be avoided.

Permalink/View Comments

Status Update

by Mike Pavone

I haven't posted about what I've been up to in regards to Rhope in a while so I figure I should write up a small update.

I have put some work into the existing Rhope interpreter. Some bugs have been fixed, the GUI library has been ported to GTK and I got it running on the Nokia N810. I was going to clean these changes up and release them as Alpha 3, but I decided that the time has come for a proper Rhope compiler. The existing Rhope interpreter is a prototype designed to let me explore how the language should work and the public releases were intended to get feedback from others. That exploration is largely complete (for now, obviously the language will continue to evolve over time) and it has become clear that there are too many flaws in the current implementation for it to make sense to continue working on it.

To that end I have started working on a Rhope compiler. The compiler is being written in Rhope itself as will the language runtime when I get to that phase of the implementation. To that end, I will be adding optional static typing, some more primitive types to the language, enhancements to global stores. Most Rhope code will not need to use these features, but they will be available.

So far I've made some progress on code for producing serial code out of a Rhope dataflow graph and on C and x86 backends. Unfortunately, I have been unable to work on Rhope as much as I have in the past as I no longer am able to commute by train. I'll do a release as soon as I have something that can compile at least simple Rhope code.

Permalink/View Comments

Taking Out the Garbage

by Mike Pavone

There are two main approaches to automatic memory management: reference counting and garbage collection. Reference counting is probably the simpler of the two the implement. Each object gets a reference counter. When a new reference to the object is created the counter is incremented and when a reference is destroyed the counter is decremented. When the counter reaches zero the object is freed. Garbage collection is a little more complicated. Basically, unreferenced objects are allowed to pile up for a while until some threshold is reached and then the garbage collector goes through the stack and globals looking for live objects (i.e. ones that are still pointed to directly or indirectly by a stack or global variable) which are kept. Everything else is freed. The exact mechanism by which that is accomplished varies somewhat based on the type of garbage collector used, but that's the basic idea.

As always, when there's more than one way to implement a feature there are some tradeoffs involved. The three biggest problems with reference counting are performance, cyclic references and the space overhead of the counter itself. There's not much to say about the performance issue. Updating a counter every time you copy or destroy a pointer adds a significant amount of overhead, especially when it needs to be done atomically. Similarly the space overhead is a simple to understand problem. Cyclic references are a little more complicated. The simplest instance of this is when an object contains a pointer to itself. In such a case, the reference count of the object will never reach zero unless the pointer to itself is manually removed. For that simple case there is a simple solution, but an object can contain a pointer to another object that points back to the first or their could be a whole chain of objects that eventually point back to the beginning. You can either put the burden of managing the problem on the shoulders of the user of the language via weak references and/or having them manually break cycles or you use a garbage collector.

Garbage collectors aren't without their flaws either. To my knowledge, the types of garbage collectors that have the best performance characteristics pause the execution of the entire program to run the garbage collector and collection is done serially. {http://en.wikipedia.org/wiki/Amdahls_law Amdahl's Law} tells us that the maximum speedup from adding more cores/processors is limited by the percentage of the computation that is serial and garbage collection is often not an insignificant percentage. There are parallel garbage collectors, but my understanding is that they are currently considerably slower than the state of the art in non-parallel collectors. Another smaller problem with garbage collection is that in order to be fast, you typically have to let it accumulate a significant amount of garbage between collections which requires the set of allocated memory to be quite a bit larger than the actual memory being used. The final major problem is that the garbage collector is really only take into account memory resources in use when deciding when to do a collection, but things like file handles and other I/O related resources are often held by objects as well. In a garbage collected environment, it might be quite a long time between when an object goes out of scope and when its destructor is finally called. This can lead to all sorts of problems.

Currently, Rhope uses reference counting. This is largely due to the fact that I didn't know the first thing about implementing a garbage collector when I started work on the language, but in some ways it fits the language well. At the moment, it's not really possible to create cyclic references as most operations are either completely functional or don't take arguments that could have references to other objects. The one exception to this is the GUI API, but even there it's not likely to be an issue in most circumstances so the biggest issue with reference counting isn't a major issue for Rhope. Reference counting brings a couple of benefits too one being that it allows the language to make updates in place in some situations and the other is that I/O objects don't have to be explicitly freed/closed.

The problem is at some point I want to add the ability for a user to define mutable objects. Once I do that I can't really ignore the problem of cyclic references anymore. For the most part I'm okay with the tradeoffs of switching to a garbage collector, but I'm not happy about the idea of having to explicitly free I/O resources. I did come across one research paper about a {http://www.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/ulterior-reference-counting.pdf hybrid reference counter/generational collector} that looks interesting, but I haven't looked at it closely enough to see if it does anything to solve the I/O object problem. Fortunately I have a while to look for a good solution as I want to get at least a basic native code compiler working before I worry about mutable user defined objects.

Permalink/View Comments

Back Up

by Mike Pavone

It took a bit longer than I hoped, but the server is back up and running at the new apartment.

Permalink/View Comments

Downtime

by Mike Pavone

I'm in the process of moving to a new apartment. Since the computer that runs this site lives in my apartment there will be some downtime starting Tuesday October 7th until sometime the following day.

Permalink/View Comments

Red Rhover: An ICFP Contest 2008 Post-mortem

by Mike Pavone

Team Rhope Burn participated in the ICFP Programming Contest again this year. This time around the task was to guide a rover to its home base while avoiding craters, boulders and Martians. The task turned out to be pretty Rhope friendly. Get DString and Split made short work of retrieving and parsing the data from the simulator and nothing about the task necessarily required a lot of processing power (though it could certainly help with certain approaches) so the slowness of the current Rhope implementation wasn't really an issue.

The contest started at 3PM local time, but I didn't really get started until I got on the train to head home from work at about 5:45. I spent the train ride trying to get the simulator to run on my laptop (didn't run in my Ubuntu install and I had a bit of trouble with the LiveCD initially). After my wife picked me up from the train station, she wanted me to tag along to Babies 'R' Us so she could pick up a baby shower gift for a friend. So it was in the Babies 'R' Us parking lot that I got a lame manual control client working (prints telemetry updates to standard out and accepts manually entered commands on standard in). By the time I got home, I had a more or less working autonomous client that would ignore obstacles and just turn towards the goal. I called up my sole teammate and he agreed to work on storing object info so we could use it with a proper pathfinding algorithm for the main round and I would continue to work on the kludgey obstacle avoidance strategy so we would have a reasonable rover for the lightning round.

The next few hours were basically wasted. I was trying to get the LiveCD running on my laptop to properly drive my old 21" CRT so I could have just a short glance between the screen I was doing my development on to the one on which the simulator was running. In the end I couldn't get it to work right so all the fiddling was just wasted time I could have better spent on the task itself. My teammate had more severe problems getting a workable environment and so wasn't able to contribute anything until the following day.

After giving up on my stupid monitor issue, I pulled an all-nighter to work on the lightning round submission. By about 10 AM local time (7AM contest time), I had a rover that could avoid obstacles by turning left. I had tried to get it to choose the optimal direction, but it just ended up changing it's mind over an over resulting in it aiming right for the obstacle so I kept the simple turn left approach for the lightning round. There was code in my lightning round entry to avoid Martians by treating them as stationary objects with radius 0.4 + their current speed times some multiplier. Unfortunately, the interpreter had a bit of a bug that resulted in everything after the decimal point getting truncated when converting a string to a floating point number. Since both the base radius (0.4) and the multiplier I was using were less than 1, the Martians ended up having an effective radius of 0 so they ended up being ignored.

So I submitted what I had that morning and then went off to my friend's bachelor party. That took up pretty much the whole day and I was exhausted afterwards (no sleep + 3 hours of paintball will do that) so I didn't work on the submission any more until Sunday after church. My teammate did finally manage to get his dev environment straightened out though so he produced a bug fix so that objects that are further away than home base are ignored and a number of test maps that our current rover couldn't really handle. He really enjoyed making the maps so I suggested he whip up a little test harness that would allow us to test a bunch of maps unattended and then make some more test maps.

I decided to try and make our current rover less hackish rather than try something fancy like implementing A* pathfinding. I fixed the aforementioned floating point bug and then attempted to get the rover to successfully pick an "optimal" direction for avoiding obstacles. This took way too long as we weren't really modeling the physics of the way the rover turned. The collision avoidance code would just increment away from the goal angle (the angle to home base) until it found one that was clear without taking into consideration whether the rover was physically capable of turning to that path before it collided with the obstacle. This tended to cause the rover to either pick an unrealistic direction or to oscillate between two directions when trying to avoid an obstacle.

I eventually managed to come up with a really hackish solution that worked pretty well for the test maps. The code would search for the first angle on either side that passed all visible obstacles starting from the goal angle. The rover would then choose the one that was closest to its "adjusted" current angle rather than the one closest to the goal angle. The "adjusted" angle was the angle reported by the telemetry data modified based on the current turning state and the turn speed parameters with a bit of fudge to try and account for rotational acceleration. This worked okay, but I suspect it will fall apart on a map that had different rover parameters (didn't have time to test for this unfortunately).

After that, I worked on improving our Martian avoidance behavior. Up to that point, we treated Martians as a stationary object with a radius of 0.4 (their actual radius) plus somewhere between 1 to 3 turns of movement (I experimented with different values at different times). This worked for the dumb Martians in the sample simulator, but it equally favored a path in front of a Martian as one behind it which seemed like it could be a problem in later heats. It also resulted in avoiding a Martian by a much greater distance than necessary when passing behind it. The new Martian avoidance code checked for intersection with a line segment extending 3 turns from the front tip of the Martian (assuming that it goes straight at its current speed) and then used the standard obstacle collision detection with radius 0.4 if that check passed. Not sure if it was really worth the effort. It helped our time on 1 run on spiral. Who knows how it will pan out with the actual contest maps.

I think the last change I made before submitting was to make some modifications to my fudge factor for the collision check to try and take into account the rover's current speed and distance to the object. Not too sure how this one will pan out in the actual contest either. I think I may have ended up making the rover a bit to aggressive in taking a close path to obstacles. Time will tell.

Overall I'm pretty happy with how the contest went for us this year. I think we submitted a very solid lightning round entry and our main round entry was at least good enough not to be embarrassing. Rhope has matured a lot since last year and wasn't really a major obstacle to our success like last year. I do wish I had taken a step back every once an a while and evaluated my approach (Monday morning it became clear to me that I should have abandoned the kludgey angle based collision detection and done some simulation based on turn commands instead, but it was too late at that point). I'd also like to try and have a slightly bigger team next year and try to get everyone in the same place. I was pretty productive this weekend, but I suspect my teammate would have been able to produce a lot more if we were physically in the same location. Most importantly though, I had a lot of fun and I look forward to participating again next year.

If you want to check out our rover, you can download our main round submission or our lightning round submission. Both contain source (and a 32-bit Linux binary) of a slightly updated version of the Rhope interpreter with support for things like sine and cosine, though the lightning round one has a bug with parsing floating point strings (this bug also exists in the stock Alpha 2 interpreter).

Permalink/View Comments

Rhope Alpha 2 Released

by Mike Pavone

Rhope Alpha 2 is now available from the downloads page! Here are the major new features:

- New parser written in Rhope itself
- Less ugly syntax
- A primitive interactive mode (aka REPL)
- Checkboxes and dropdowns (Syllable only)
- Tail call optimization
- An experimental Nintendo DS port

For more details check the README in the download of your choice (yes there's actually a README this time).

It took me a bit longer to get this out the door than I had hoped, I'm quite happy with this release. It doesn't feel nearly as rushed as alpha 1 did.

I'll probably working solely on improving performance for the next month. The ICFP Programming Contest is fast approaching and Rhope's current performance could be an issue depending on the problem this year.

Permalink/View Comments

Rhope Crash and Burn

by Mike Pavone

Sometime during the development of Rhope, I thought it would be neat to make an entry into the ICFP programming contest and then release the language immediately after the competition was over. By the time the 2007 ICFP contest came around, I decided Rhope was ready enough to give it a shot. I knew I had basically no shot at winning (the ICFP contest is challenging enough with a mature language), but I figured Rhope was ready enough that I wouldn't completely embarrass myself. So I called up a couple of my college buddies and team Rhope Burn was formed.

In the time leading up to the contest, one of my teammates said he was interested in trying to use the visual part of the language for our entry. I rather liked this idea, but there was a small problem. I had abandoned the old visual editor as an unmaintable wreck of source code. My intention was (and still is) to rewrite the editor in Rhope itself once the language had the requisite features to do so. At the time, the interpreter could only run a single program at once and there was no functionality to construct a program from within the language itself so writing this new editor wasn't particularly possible (well I could have made one that translated the visual program into a textual program, but that would have made the graphical language a second class citizen).

So I started in on adding the necessary features in the hopes I could get at least a basic visual editor working in time for the contest. For some inexplicable reason I didn't think to do a SVN commit or at least a backup of the current source code before I started this little endeavor. This proved to be fatal to our chances in the contest, but I'll get to that later.

At this point, neither of my team members knew how to program in Rhope. Being the procrastinator that I am, I only managed to deliver them a tutorial a few days before the start of the contest. Responding in kind, neither of them actually looked at the tutorials until after the contest started. To make matters worse, one of them decided he wouldn't be able to learn the language in time to be of any help.

Those changes I started working on to support the visual environment introduced some rather nasty bugs in the interpreter and the most recent copy of the source I had from before I started that change was too old to be useful. There were also other serious bugs in the interpreter that I was unaware of. I hadn't written anything other than relatively trivial programs in Rhope at that point. Once I started working on our competition entry, a bunch of new bugs I hadn't seen before came out of the woodwork. As a result, I spent more time fixing bugs in Rhope than working on the problem. Since my sole remaining teammate was still a Rhope novice, he wasn't able to make up for my huge drop in productivity.

Sometime late Sunday night, we had written a DNA interpreter. Individual parts had been tested, but the program as a whole had not. I added my teammate's code to mine and gave it a spin. The interpreter crashed.

It didn't make any sense. His code worked fine by itself and so did mine, but when I put the two together the interpreter would crash right away. With my mind addled by lack of sleep, I wouldn't figure out the problem until my commute to work the following morning. Team Rhope Burn had failed.

Still, participating in the contest was a valuable and enjoyable experience. For the first time, someone other than me had written code in Rhope. It was also my first experience working with a distributed team of programmers and my first experience with a coding competition. Our lack of success also made it clear that Rhope wasn't ready for public consumption.

Rhope has come a long way in the past year, so hopefully team Rhope Burn won't fail so spectacularly in 2008's competition. I'm still looking for one or two people to join the team. If you want to join, e-mail me at pavone@retrodev.com or add a comment here.

Permalink/View Comments

Origins

by Mike Pavone

I did my first work on what eventually became Rhope in late 2005. At the time, I was working at a small company working on tools for data driven publishing. One of the tools I was working on was a data import plugin for Adobe InDesign. Such a tool can be a boon when you're producing a large catalog both by saving time and removing much of the tedium; however, most designers producing these hefty catalogs still produce them by manually copying and pasting data in from spreadsheets. There are a number of reasons why this persists, but one of them is that doing anything more than a basic import requires a bit of logic. To deal with this, most import plugins have some kind of simple scripting language.

Most print designers are not programmers. A web designer will probably have at least some exposure to Javascript and maybe even one of the common server side languages like PHP, but the print world is still largely programming language free. As a result they tend to avoid anything that looks like programming including the scripting languages built into these tools. I started to think about how to tackle this problem and remembered an interesting game I played in high school in which you built a virtual robot and then programmed it using a "box and wires" programming environment. So I started looking online for existing languages with a similar concept and stumbled upon Prograph, Labview, Pure Data and the dataflow paradigm. As a result of my perusing, I formed an initial concept of what I wanted the language to look like and I added concurrency support as a secondary goal.

So with a preliminary design in hand, I set off to write my first prototype of Rhope (then called Visuality). By the end of 2005 I had it working to the point that it did ... something. That something wasn't useful, the interface sucked, there was no real concurrency support and the interpreter was incredibly inefficient, but it did actually run a trivial program. With this small victory under my belt, I began work on a more efficient, multi-threaded interpreter. A couple of weeks later, I was stuck. A novice at both writing interpreters and multi-threaded code, I was having trouble wrapping my head around the problem of writing a thread-safe, reasonably efficient interpreter for supporting this implicitly parallel language. So I decided to put my language aside for a while and work on other things. Eventually I started working on an open source Palm OS clone called Knose OS.

So for quite a few months, I didn't touch Rhope at all and focused all of my energies on Knose. In July of 2006, I got a new job that required a more extensive commute. So I had two 20 to 30 minute train rides each day and I kept myself entertained by working on Knose. At some point, I think in September or October that same year, I accidentally left the flash drive with the latest Knose sources at home. With few other entertainment options during my train ride, I turned back to Rhope. Progress was slow for a while as I had to reacquaint myself with the code, but I was a bit frustrated that none of the people who said they wanted to help with Knose had actually produced anything so I stuck with Rhope.

Eventually I got past the hump of writing the first version of the multi-threaded interpreter and I started to write some trivial programs. At this point, Rhope was still a completely visual language and it was clear that code density (or lack thereof) was an issue. To an extent, the issue could be solved by making the visual elements less chunky, but a large part of the problem was inherent in the language itself. An expression like If[[n] < [2]] was made up of 4 distinct "boxes" with wires connecting them. Even if I made the boxes as small as possible and made the "wires" connecting them have no length, it would still be 4 lines of text. To solve this problem, I decided to make Rhope a hybrid textual/visual language. A user could write Rhope code in a completely visual environment, use a more traditional text based environment or they could mix the two by putting textual expressions inside visual blocks.

Some of the quirks in Rhope's syntax are actually the result of this close relationship to the visual language. The "positional" inputs (i.e. something(0) refers to the first input, blah(1) the second, etc.) in particular came directly from the way the visual language worked at the time. Since inputs were already using parentheses and lists were already using curly brackets (at least I think List literals were implemented at that point), my choices for characters for other parts of the language were rather limited.

Over time the visual environment stagnated. It had changed from being the primary motivator for the project to a secondary goal and it was badly in need of a rewrite. The old visual editor no longer compiles and so for the moment Rhope is strictly a textual language. That will change eventually. Writing the new visual editor is on the roadmap to version 1.0. It's just not a priority right now.

So that's pretty much all of the interesting turns in the road leading up to Alpha 1. The overall direction of the language didn't change much after that point though there were a few interesting events in between, one of which I'll post about in the near future.

Permalink/View Comments

Developing on the Fringes

by Mike Pavone

Visitors to the Rhope download page might be a little surprised that the language is available for Syllable, an alternative OS that makes desktop Linux look like the big leagues. Those who peruse the documentation might be even more surprised to find that Syllable has the most complete GUI support in Rhope while more mainstream platforms like OS X and Linux have no GUI support at all. This would seem a rather curious choice. Why would I spend time supporting a fringe operating system with less than 10 thousand users when I could be improving support for operating systems with millions (maybe even billions) of users? While a small part of my reason is simply that I like Syllable and want to see it succeed, there's a more important strategic reason: It's easier to make a big splash in a pond than in an ocean.

What I mean by this is that when you release a new piece of software for one of the big three platforms it's easy to be ignored. Unless your software is in a completely new category, chances are good that there is already another piece of software similar to yours that has more features, fewer bugs and an active user base. For some categories (like say programming languages or text editors) there could be quite a few competitors that match that description. Obviously, this makes your job of getting users a lot harder. Many of your potential users are already using a competing application and those that are looking for software in the category are much more likely to stumble across the established competitor. In such a case, you can't just be a little bit better than what's already out there, you need to do at least one thing a lot better and you'll probably need to do at least a competent job at a good chunk of the other things your competitors do.

On a fringe OS, like Syllable, the competitive landscape is much clearer. On Syllable, there is only one GUI e-mail app, one GUI web browser, only two text editors (but only one supports "advanced" features like syntax highlighting), no office productivity apps, and while quite a few programming languages have been ported, only C++ has access to the Syllable GUI. That makes Rhope only the second language to support the Syllable GUI (though currently only in limited form). That means to get people writing real applications in Rhope, all I have to do is make it a better choice than C++. I don't have to beat Python, Ruby, C#, Java, Lisp, etc.

How has my choice to support Syllable so well in Rhope worked out so far? Pretty well from my perspective. I've had twice as many downloads for the Syllable build of Rhope as the OS X build. I consider that to be pretty impressive given the huge disparity in the size of their respective user bases. Both the windows build and the source package each have twice as many downloads as the Syllable build, so clearly going Syllable only for Rhope doesn't make a lot of sense, but it's a significant enough of a percentage to easily justify continued attention to the Syllable port. It will be interesting to watch the importance of the different platforms as the language matures. Obviously, if Rhope goes anywhere as a language the Syllable user base will be dwarfed by more prominent platforms. But in the more immediate future, I suspect Syllable users will play an interesting role. Right now, no one besides me is actually using Rhope for anything useful (at least as far as I know, if you're doing something cool with the language let me know!). Once Rhope gets some users releasing useful programs written in the language, I suspect that Syllable users will be disproportionately represented. Time will tell.

So what does this mean for you? I suppose it sort of depends. If you're writing software to make money, targeting a fringe OS like Syllable probably doesn't make a lot of sense, but you can maybe make the case for targeting a less popular mainstream platform like OS X as others have already done elsewhere on the web. On the other hand, if you're writing software for your own enjoyment, the fringes are worth considering. I've found that one of the most satisfying parts of developing software is knowing that somewhere is knowing that people are using what you've created and actually find it useful. I think fringe operating systems provide a unique venue for providing that, particularly when the software you're interesting in writing is in a well tread category.

Permalink/View Comments

Alpha 2 and Beyond

by Mike Pavone

I want to give a quick overview of what's coming down the pipe for Rhope. First, here's what to expect in Alpha 2 (apart from bugfixes):
- New parser written in Rhope itself
- Slightly less strange syntax
- Basic tail call optimization
- More robust GUI support (might be Syllable only until Alpha 3)
- Support for more transaction handling options (maybe)

Before version 1.0 is released I'd like to see the following as a minimum:
- VM based interpreter
- Basic native code compiler
- Anonymous workers (full lexical closures might not make it though)
- At least basic GUI support for all "officially supported" platforms (currently Windows, Syllable, OSX and *nix/X11)
- Working visual version of the language that integrates well with the text version

These feature goals aren't set in stone though. If there's a feature you'd like to see sooner rather than later let me know. As usual, you can reply to this blog post directly, send a message to the mailing list or e-mail me at pavone@retrodev.com

Permalink/View Comments

The Problem with HTML

by Mike Pavone

Putting together the simple Rhope web framework that powers this site got me thinking a bit about web technologies and HTML in particular. The promise of the HTML/CSS combo is a nice one. Stick your content in a semantic container (HTML) and then let a completely separate file handle presenting this semantically arranged data in a pleasing fashion (CSS). In theory, such a clean separation of content and presentation should bring a host of benefits. Skinning an HTML document or web based application should just be as simple as modifying the style sheet. Devices with small displays should be able to ignore the stylesheet and still display the page sensibly. Software should be able to easily parse the HTML and do meaningful things with it without any fuss. Viewers that present web pages in an innovative way should be easy to create. Somehow it seems that the reality of HTML and CSS fars fall short of the theoretical promise of the concept.

Why is that? One of the main obstacles I see is that most websites today are not technical manuals. I'm serious. Okay, perhaps I stated my point in a slightly misleading fashion. It might be better to say HTML defines a rather rich set of semantic tags if the document you're trying to represent in it happens to be a technical manual. Just take a look at a list of all the tags available in HTML 4. There are tags for source code snippets, sample output, variables, acronyms, abbreviations, definitions of a list of terms and more. All of these can be quite useful for technical documents, but most of those tags I mentioned are rarely used on modern websites (the code tag being a notable exception). There's no tag to mark something up as a blog post or perhaps something more generic like a news item. There's no tag for denote a piece of text as a user comment. You can't even clearly differentiate between the main body of a page and a navbar with HTML's vocabulary.

If HTML's semantic tags were a better match for today's websites, we might not need a separate format for news feeds. A feed reader would just parse the main page of the blog or news site and pull out the elements that were necessary. CSS heavy pages wouldn't have to turn into an unusable mess when the stylesheet doesn't load if HTML made it easy for browsers to differentiate between the "meat" of a page and sections devoted to things like navigation. With those same semantic features, mobile browsers could more easily reformat pages for small screens. The list goes on.

This isn't the only problem though. The appeal of being able to properly separate content and presentation is pretty strong even if the content half uses a crappy vocabulary. Unfortunately, the HTML/CSS combo doesn't seem to deliver too well on this front either. The multitude of HTML templating systems alone would seem to be indicative of a problem here. If CSS was enough for presentation, you would think that web applications would just spit out HTML in a format that was arranged logically and CSS would take care of all the skinning.

One of the biggest problems I see with CSS is that too much of it assumes a more or less linear document. So elements that follow each other logically in the HTML document tend to follow each other visually in the final output. Such an assumption isn't always a bad thing. In running text, this is exactly the behavior you want so if your document is mostly made up of running text (like say technical documentation) CSS does a great job. If your document has a mix of running text and other elements or several loosely related bocks of running text (like on a fair number of modern websites) it does a sort of okay job. If most of your content isn't running text (like say in a web application) it does a pretty crappy job.

Now CSS doesn't completely leave you in the lurch when you want to break out of the linear flow assumption. The position and float properties give you some flexibility with breaking elements out of the linear flow. Things like sidebars and page headers aren't too hard to do with CSS. There are certain cases of those kind of elements that can be a little awkward, but overall the situation isn't too bad. However, if you want to re-arrange things within the flow you're going to have problems. CSS can't even do something as simple as displaying the children of a block element in the reverse order than they appear in the original HTML.

Another problem I see in CSS is that each element is an island in relation to its peers for the most part. One of the things that made HTML tables attractive for layout is that the size and position of a single table cell took into account the cells around it as well. Eventually, the ability to make arbitrary elements behave like tables, table rows and table cells was added to CSS, but it's an all or nothing affair (and it's also not supported in any currently shipping version of IE). Either you get all of the formatting features of tables or none of them. You can't say "these two divs shouldn't wrap if the viewport is narrow, but otherwise treat them like normal block elements". Then there are scenarios that tables didn't handle well and CSS also blissfully ignores. For instance, suppose you want two elements side by side and you want one of them to have a fixed width and the other to take up some percentage of what's left over in the viewport.

There are some other problems I see in the HTML/CSS combo, but they are less pertinent to the original point. So what's an author of web content or framework designer to do? I think we need to stop writing HTML by hand. To a certain extent, this is already happened. So called "data-driven" websites make up a significant chunk of the web today, but I think we need to go further. We need to stop writing HTML templates too. I think web frameworks need to start abstracting HTML and present the applications that use them with a logical semantic model of the page that doesn't necessarily have a 1:1 relationship with the HTML that gets generated as a result. The HTML that gets generated also needs to be as CSS friendly as possible and where CSS doesn't provide enough flexibility the framework needs to provide a mechanism to re-arrange the output without resorting to HTML-filled templates or modifying the code of the application using the framework. I'm not 100% sure what such a framework would look like, but I think it's going to be my goal as I work on Rhope's web framework.

Permalink/View Comments

Initial Documentation Complete

by Mike Pavone

Last night (Feb 27), I made another update to the documentation and I'm happy to announce that all companies implemented in the interpreter itself now have all of their methods properly documented. This means that for the moment, the documentation is complete. There's still quite a bit to be done before I'll consider the documentation for Rhope to be passable, but as I mentioned in my previous post that requires some updates to the software.

I also made a few updates to improve the stability of the web server running this site. Previously no validation was done on the documentation file, which in combination with some errors in the documentation file itself led to runtime errors that caused the interpreter to exit when certain pages were requested. Certain other pages would fail to load. Validation has now been added and the documentation file has been fixed so these issues should be gone. I've also whipped together a tiny shell script that will restart the web server if it crashes or exits for some reason. Why I didn't think to do this earlier is beyond me.

Permalink/View Comments

Documentation Update

by Mike Pavone

I updated the documentation late yesterday (Feb 24) and while it's still not complete it's a lot better than what was available when Rhope was released on the 21st. Currently the only companies with missing method documentation are Custom Widget, Input Box, Program, Real Number, Screen Window and Whole Number. Screen Custom Widget is currently completely absent from the documentation. These omissions should be taken care of within the next day or so and at which point all the workers and companies that are implemented in the core interpreter will have at least basic documentation.

After that, I need to make some enhancements to the code that generates the documentation. I need to add a field for storing where a worker or company is implemented so I can add documentation for things implemented in extendlib and the web framework without confusion. I also need to add some support for "article" style documentation and the ability to add nicely formatted code examples to the existing pages. If there's anything else you want to see in the documentation let me know by commenting on this blog entry, posting in the mailing list at Google Groups or by e-mailing me directly at pavone@retrodev.com

Permalink/View Comments

Usage Note

by Mike Pavone

There's a small bug that a fair number of people have been running into. It seems the argument checking code isn't working properly so the interpreter just crashes if you run it with no arguments. This should be fixed in the next release, but in the meantime please invoke rhope in the following manner:

rhope <filename>
OR
rhope -t <num> <filename>

Where <filename> is the name of a file containing Rhope sourcecode with an extension of .vistxt and <num> is the number of threads to use in the thread pool (default is currently 4). If you're using windows and want to use the GUI features you need to replace rhope with rhope_gui in the examples above.

Also note, that if the file passed to the rhope interpreter doesn't contain a Main worker and doesn't Import a file that does, the interpreter will probably crash (this also will be fixed in the next release). The source files that are included with the interpreter itself (extendlib.vistxt, framework.vistxt and webserver.vistxt) are libraries and don't define Main so don't try to run those directly. All the files in the examples archive do define Main however, and can be run directly.

Permalink/View Comments

Getting Started with Rhope: Semantics

by Mike Pavone

This post is going to give an overview of the major semantic differences between Rhope and most mainstream languages. It will focus mainly on differences related to concurrency but it won't be limited exclusively to those topics.

One of the biggest semantic differences between Rhope and most other languages is that all operations automatically operate in parallel. Take a look at the following code:

Do Something[]
Do Something Else[]

In the above snippet, Do Something and Do Something Else would execute simultaneously. Of course, not all code can be run in parallel. If one operation needs to work on data produced by another operation, those operations need to be executed serially.

foo <- Do Something[]
Do Something Else[foo]

In the above example Do Something Else won't execute until Do Something is done. More generally, a call to a worker isn't performed until all of its inputs have been provided with data. The order the statements doesn't have an effect on execution order. The above example could have had its lines arranged in the reverse order and its behavior would have been the same. This behavior has an interesting side effect. Basic flow control structures like If, can be normal Workers that selectively output data.

foo,bar <- If[some expression]
Print[foo]
Print[bar]

In the above example, if "some expression" evaluates to Yes the variable foo will be set to Yes and bar will not be populated. If "some expression" evaluates to No the variable bar will be set to No and foo will be left unpopulated. In either case, only one of the two calls to Print will be executed. Since the above can be a somewhat awkward way to do flow control, Rhope has a special syntax to make things a bit easier.

If[some expression]
|:
Print[~]
:||:
Print[~]
:|

The above code will do exactly the same thing as the example before it. Inside of a block (excluding the outer most block that defines the boundaries of a worker definition), ~ refers to an output of the expression. In the first block it refers to the first output, in the second block it refers to the second and so on. This can be done with any expression, not just If. The following code prints out the sum of 2 and 3:

[2] + [3]
|:
Print[~]
:|

Going back to the If example, you might be wondering how you would conditionally execute code if you didn't want to pass the result of If to the worker you wanted to execute. Rhope's block syntax has a little extra magic to deal with this. If you place a call to a worker inside a block, but don't use ~ as one of the inputs it will still create a link between the output corresponding with that block and the worker, but no data will be passed. Here's an example:

If[some expression]
|:
Print["This will be printed if the expression is Yes"]
:||:
Print["This will be printed if the expression is No"]
:|

This same mechanism can also be used to serialize IO actions:

Print["I will get printed first"]
|: Print["I will get printed second"] :|

Another major difference between Rhope and most mainstream languages is that most operations in the language have pass by value semantics. What this means is that instead of modifying an object they actually create a new object with the requested changes. While this can be less efficient, it's part of the magic juice that makes concurrent programming in Rhope so easy. You generally don't have to worry about some other piece of coding running in parallel changing the data while you're working on it. For those of you, worried about the performance of such behavior, fear not. Internally, all values are actually passed by reference. A copy is only made when an operation wants to modify a value and the reference count for the value is greater than 1.

The last semantic difference I'm going to cover has to do with global variables. In languages that use a thread model for concurrency, working with global variables can be quite a bear. You need to protect them with some kind of mutually exclusive lock and if you forget to do so somewhere you'll have a rather difficult to track down bug on your hands. Rhope borrows the concept of transactions from databases to make concurrent access to global variables a breeze. In Rhope, global variables are split into global stores which are sort of like namespaces in other languages. When a worker that has been declared to use a particular global store starts, it creates a new transaction. When the worker exits, the changes it made are committed to the store. If the store has changed between when the transaction was started and when the commit happens, the commit fails and the worker is automatically run again. Here's an example of a worker that increments a variable in a global store named foo:

Increment(0,0) uses foo
|:
::Counter <- [::Counter] + [1]
:|

That's it. The above example can be safely called multiple times in parallel with no extra work.

Permalink/View Comments

Getting Started with Rhope: Syntax

by Mike Pavone

This is designed to be a brief introduction to the syntax of the Rhope programming language for those with prior programming experience. A proper tutorial will be coming a bit later. The software running this blog doesn't currently support marking up preformatted text so I'm going to try and keep the inline examples to a minimum. Check out the downloads section for a few small example programs.

Let's start with the obvious syntax differences. I made some rather... interesting choices for punctuation in the language. Some of this will probably be cleaned up in a future release, but this post will be focusing on the here and now. |: (that's a pipe followed by a colon) is roughly analogous to a left curly bracket ({) in C-like languages and :| (a colon followed by a pipe) is roughly analogous to a right curly bracket (}) in C-like languages. Square brackets take the place of parentheses, but are only used for worker invocation (Rhope's funny name for functions/procedures). Curly brackets are only used to denote List literals. String literals are almost the same as in C, but the \x escape sequence is not supported. Assignment is done with <- (a less than symbol followed by a dash) and testing for equality is done with = (technically = is a worker and not part of the syntax).

Inputs to a worker work a bit differently than most languages in Rhope. Instead of declaring the names of the inputs up front, you instead declare how many inputs and how many outputs a worker has. Inputs and outputs are then referred to by their position with a number in parentheses. (0) refers to the first input or output (whether it refers to an input or output depends on context), (1) the second and so on. To make this a bit more readable, you can stick text in front of this number in parentheses like so: some string(0).

Identifiers can have spaces in them and internal white space is considered significant, but white space at the beginning or end of an identifier is ignored. So Get Stuff[] and GetStuff[] are not the same. Rhope is currently case sensitive. My current convention is title case for workers and companies (Rhope's funny name for classes/types) and lower case for inputs, outputs and variables, but this is not required by the language.

There are no operators (apart from assignment) in Rhope. Operations like + and - are just workers. Workers can be called with the worker name in the prefix, postfix and infix positions in relation to the arguments. So if you want to add 1 and 1, you could do: +[1,1] or [1,1]+ or [1] + [1]. There is no restriction on how many of the inputs are in each of the input groups in the infix case. There is no special syntax for method calls. [list]Index[0] (or Index[list, 0] or [list, 0]Index) will do a generic method call using the first argument (in this case list) to determine which company's method should be called. To call a method of a specific company in a non-generic fashion use the fully qualified name (the method name, followed by the @ symbol followed by the company name) like so: [list]Index@List[0].

That covers most of the oddities in Rhope's syntax. The next post will give a brief overview of some of the major semantic differences between Rhope and most imperative languages.

Permalink/View Comments

Under the Hood

by Mike Pavone

With the exception of the downloads page, the Rhope website is completely powered by software written in Rhope itself. You can download the source that makes this site tick over on the downloads page.

The site is hosted on a relatively modest setup: a 1.8GHz Athlon XP desktop with 1GB of RAM running Syllable Desktop 0.6.5. Its pipe to the internet is 30Mbit down/5Mbit up cable broadband. I'm not anticipating any major problems, but since this is the first test of the setup under a real world load don't be surprised if there are some issues if the site gets any major traffic. The download page should be issue free though as it's hosted elsewhere.

Permalink/View Comments

A Security Note

by Mike Pavone

Please note that this site doesn't currently use SSL even when you're logging in or creating an account. Passwords are also currently stored in plaintext on the server. I made a quick hack to the copy of the code that's running the site to prevent this file from being easily retrieved via the webserver, but it's obviously still a security issue. So please don't use any important passwords on this site.

Permalink/View Comments
Username: Password:
Don't have an account? Register now!