I have recently started work on Seph again. I preannounced it last summer (here), then promply became extremely busy at work. Busy enough that I didn’t really have any energy to work on this project for a while. Sadly, I’m still as busy, but I’ve still managed to find some small slivers of time to start working on the compiler parts of the implementation. This has been made much easier and more fun since JSR292 is getting near to completion, and an ASM 4 branch is available that makes it easier to compile Java bytecode with support for invoke dynamic built in.

So that means that the current code in the repository actually goes a fair bit to where I want it to be. Specifically, the compiler compiles most code except for abstractions that create abstractions, and calls that take keyword arguments. Assignments is not supported either right now. I don’t expect any of these features to be very tricky to implement, so I’m waiting with that and working on other more complicated things.

This blog post is meant to serve two purposes. The first one is to just tell the world that Seph as an idea and project actually is alive and being worked on – and what progress has been made. The other aspect of this post is to talk about some of the things that make Seph a quite tricky language to compile. I will also include some thoughts I have on how to solve these problems – and suggestions are very welcome if you know of a better approach.

To recap, the constraints Seph is working under is that it has to run on Java 7. It has to be fully compiled (in fact, I haven’t decided if I’ll keep the interpreter at all after the compiler is working). And it has to be fast. Ish. I’m aiming for Ruby 1.8-speed at least. I don’t think that’s unreasonable, considering the dimensions of flexibility Seph will have to allow.

So let’s dive in. These are the major pain points right now – and they are in some cases quite interconnected…

Tail recursion

All Seph code has to be tail recursive, which means a tail call should never grow the stack. In order to make this happen on the JVM you need to save information away somewhere about where to continue the call. Then anyone using a value has to check for a tail marker token, and if one that is found, that caller will have to do a repeated call on the current tail until a real value is produced. All the information necessary for the tail will also have to be saved away somewhere.

The approach I’m currently taking is fairly similar to Erjangs. I have a SThread object that all Seph calls will have to pass along – this will act as a thread context as soon as I add light weight threads to Seph. But this place also serves a good place to save away information on where to go next. My current encoding of the tail is simply a MethodHandle that takes no arguments. So the only thing you need to do to pump the tail call is to repeatedly check for the token and call the tail method handle. Still, doing this all over the place might not be that performant. At the moment, the code is not looking up a MethodHandle from scratch in the hot path, but it will have to bind several arguments in order to create the tail method handle. I’m unsure what the performance implications of that will be right now.

Argument evaluation from the callee

One aspect of Seph that works the same as in Ioke is that a method invocation will never evaluate the arguments. The responsibility of evaluating arguments will be in the receiving code, not the calling code. And since we don’t know whether something will do a regular evaluation or do something macro-like, it’s impossible to actually pre-evaluate the arguments and push them on the stack.

The approach Ioke and the Seph interpreter takes is to just send in the Message object and allow the callee to evaluate it. But that’s exactly what I want to avoid with Seph – everything should be possible to compile, and be running hot if that’s possible. So sending Messages around defeats the purpose.

I’ve found an approach to compile this that actually works quite well. It also reduces code bloat in most circumstances. Basically, every piece of code that is part of a message send will be compiled to a separate method. So if you have something like foo(bar baz, qux) that will compile into the main activation method and two argument methods. This approach is recursive, of course. What this gives me is a protocol where I can use method handles to the argument methods, push them on the stack, and then allow the callee to evaluate them however they want. I can provide a standard evaluation path that just calls each of the method handles in turn to generate the values. But it also becomes very easy for me to send them in unevaluated. As an example this is almost exactly what the current implementation of the built in “if” method looks like. (It’s not exactly like this right now, because of transitional interpreter details).

public final static SephObject _if(SThread thread, LexicalScope scope,
        MethodHandle condition, MethodHandle then, MethodHandle _else) {
    SephObject result = (SephObject)condition.invokeExact(thread, scope, 
                                                          true, true);
    
    if(result.isTrue()) {
        if(null != then) {
            return (SephObject)then.invokeExact(thread, scope, 
                                                true, true);
        } else {
            return Runtime.NIL;
        }
    } else {
        if(null != _else) {
            return (SephObject)_else.invokeExact(thread, scope, 
                                                 true, true);
        } else {
            return Runtime.NIL;
        }
    }
}

Of course, this approach is not perfect. It’s still a lot of code bloat, I can’t use the stack to pass things to the argument evaluation, and the code to bind the argument method handles take up most of the generated code at the moment. Still, it seems to work and gives a lot of flexibility. And compiling regular method evaluations will make it possible to bind these argument method handles straight in to an invoke dynamic call site, which could improve the performance substantially when evaluating arguments (something that will probably happen quite often in real world code… =).

Intrinsics are just regular messages

Many of the things that are syntax elements in other languages are just messages in Seph. Things like “nil”, “true”, “false”, “if” and many others work exactly the same way as a regular message send to something you have defined yourself. In many cases this is totally unnecessary though – and in most cases knowing the implementation at the call site allow you to improve things substantially in many cases. I think it’s going to be fairly uncommong to override any of those standard names. But I still want to make it possible to do it. And I’m fine with the programs that do this takng a performance hit from it. So the approach I’ve come up with (but not implemented yet) is this – I will special case the compilation of every place that has the same name as one of the intrinsics. This special casing will bind to a different bootstrap method than regular Seph methods. As a running example, let’s consider compiling a piece of code with “true” in it. This will generate a message send that will be taken care of by a sephTrueBootstrapMethod. We still have to send in all the regular method activation arguments, though. What this bootstrap method will do is to set up a call site that points to a very special method handle. This method handle will be a guardWithTest created through a SwitchPoint specific to the true value. The first path of that GWT (guardWithTest) will just return the true value directly without any checks whatsoever. The else path of the GWT will fallback to a regular Seph fallback method that does inline caching and regular lookup. The magic happens with the SwitchPoint – the places that create new bindings will check for these intrinsic names and if one of those names is used anywhere in the client code, the SwitchPoint will be changed over to the slow path.

In summary, I think a fast path can be possible for many of these things for most programs. The behaviour when you override “if” should still work as expected, but will make the global performance of that program slower for the rest of the execution.

When does lexical scopes escape?

Seph has mutable lexical scopes. But it’s impossible to know which names will escape and which won’t – so as far as I can see, I can’t use the Java stack to represent variables except for in some small amount of very degenerate cases. I’m not sure if it’s worth it to have that code path yet, so I haven’t thought much about it.

Class based PICs aren’t a good fit

One of the standard optimizations that object oriented languages use is something called a polymorphic inline cache. The basic idea is that looking up a method is the really slow operation. So if you can save away the result of doing that, guarded by a very cheap test, then you can streamline the most common cases. Now, that cheap test is usually a check against the class. As long as you send in an instance with the same class, then a new method lookup doesn’t have to happen. Doing a getClass and then a identity equality on that is usually fairly fast (a pointer comparison on most architectures) – so you can builds PICs that don’t actually spend much time in the guard.

But Seph is a prototype based language. So any object in the system can have different methods or values associated with a name, and there is no clear delineation on objects with new names and values in them. Especially, since Seph objects are immutable, every new object will most likely have a new set of values in them. And saving a way objects and dispatching on them becomes much less performant, since the call sites will basically never work on the same object. Now, there are solutions to this – but most of them are tailored for languages where you usually use a class based pattern. V8 uses an approach called hidden classes to figure out things like that. I’m considering implementing something similar, but I’m a bit worried that the usage pattern of Seph will be far enough away from the class based world that it might not work well.

Summary

So, Seph is not terribly easy to compile, and I don’t have a good feeling for how fast it can actually be made. I guess we’ll have to wait and see. But it’s also an interesting challenge, coming up with solutions to these problems. I think I might also have to go on a new research binge, investigating how Self and NewtonScript did things.

2 Comments | By Ola Bini | In: seph | tags: bytecode, compilers, jsr292, programming language design, programming languages, seph. | #

I’m currently in the process of implementing Seph, and I’ve reached an inflection point. This point is the last responsible moment to choose what I will target with my language. Seph will definitely be a JVM language, but after that there is a range of options – some quite unlikely, some more likely. The valid choices are:

• Target Java 1.4
• Target Java 5/6
• Target Java 7
• Target Java 7 with extensions

Of these, the first options isn’t really interesting for Seph, so I’ll strike it out right now. The other three choices are however still definitely possible – and good choices. I thought I might talk a little bit about why I would choose each one of them. I haven’t made a final decision yet, so that will have to be the caveat for this post.

Before talking about the different choices, I wanted to mention a few things about Seph that matters to this decision. The first one is that I want Seph to be useful in the real world. That means it should be reasonably fast, and runnable for people without too much friction. I want the implementation to be small and clean, and hopefully as DRY as possible – if I end up with both and interpreter and just-in-time compiler, I want to be able to share as much of these implementations as possible.

Java 5/6

The easiest way to go forward would be to only use Java 5 or 6. This would mean no extranice features, but it would also mean the barrier to entry would be very low. It would mean development on Seph would be much easier and wouldd in general make everything simpler for everyone. The problem with it would mainly be implementation complexity and speed, which would both suffer compared to any of the Java 7 variants.

Java 7

There are many good reasons to go with Java 7, but there are also some horrible consequences of doing this. For Seph, the things that would make things from Java 7 is method handles, invoke dynamic and defender methods. Other things would be nice, but the three previous ones are the killer features for Seph. Method handles make it possible to write much more succinct code, not generate lots of extra classes for each built in method, and many other things. It also becomes possible to refer to compiled code using method handles, so the connection between the JIT and the interpreter would be much nicer to represent.

Invoke dynamic is quite obvious – it would allow me to do much nicer compilation to bytecode, and much faster. However, I could still build the same thing myself, to much greater cost and it would also mean inlining wouldn’t be as easy to get.

Finally, defender methods is a feature of the new lambda proposal that allow you to add new methods to interfaces without breaking backwards compatibility. The way this works is that when you add a new method to an interface, you can specify a static method that should be called when that interface method is invoked and there are no other implementations on the concrete classes for a specific object. But the interesting side effect of this feature is that you can also use it to specify default implementations for the core language methods without depending on a shared base class. This will make the implementation much smaller and more flexible, and might also be useful to specify required and optional methods in an API.

The main problem with Java 7 is that it doesn’t exist yet, and the time schedule is uncertain. It is not entirely certain exactly what the design of the things will look like either – so it’s definitely a moving target. Finally, it will make it very hard for people to help out on the project, and also it won’t make Seph a possible language for people to use until they upgrade to Java 7.

Java 7 with extensions

It turns out that the interesting features coming in Java 7 is just the tip of the iceberg. There are many other proposed features, with partial implementations in the DaVinci project (MLVM). These features aren’t actually complete, but one way of forcing them to become more complete is to actually use them for something real and give lots of feedback on the feature. Some of the more interesting features:

Interface injection

This feature will allow you to say after the fact that a specific class implements an interface, and also specify implementations for the methods on that interface. This is very powerful and would be extremely helpful in certain parts of the language implementation – especially when doing integration with Java. The patch is currently not very complete, though.

Tail calls

Allowing the JVM to perform proper tail calls would make it much easier to implement many recursive functional algorithms easily. Since Seph will have proper tail calls in the language, this will mean that I will have to implement this myself if the JVM doesn’t do it, which means Seph will be slower based on this. The patch seems to be quite good and possible to merge and harden to the JDK at some point. Of all the things on this list, this seems to be one of things that we can actually envision see being added in the Java 7 or Java 8 time frame.

Coroutines/continuations

Both coroutines and continuations seem to be possible to do in a good way, at least partially. Coroutines might be interesting for Seph as an alternative to Kilim, but right now it seems to be a bit unstable. Continuations would allow me to expose continuations as a first class citizen which is never bad – but it wouldn’t give me much more than that.

Hotswapping

Hotswapping of code would make it possible to do agressive JITting and then backing out from that when guards fail and so on. This is less interesting when we have invoke dynamic, but will give some more flexibility in terms of code generation.

Fixnums, tuples, value types

We all want ways of making numbers faster – but these features might also make it possible to efficiently represent simple composite data structures, and also things like multiple return values. These are fairly simple features, but have no real patch right now (I think).

Light weight code loading (anonymous classes)

It is horrible to load byte code at runtime in Java at this point. The reason is that to be able to make sure your loaded code gets garbage collected, you will have to load each chunk of code in a new class in a new classloader. This becomes very expensive very fast, and also endangers permgen. Anonymous classes make this go away, since they don’t have names. This means you don’t actually have to keep a reference to older classes, since there is no way to get to them again if you lost the reference to them. This is a good thing, and makes it possible to not generate class loaders every time you load new code. THe state of this seems to be quite stable, but at this point JVM dependent.

The price

Of course, all of these lovely features comes with a price. Two prices in fact. The first price is that all the above features are incomplete, ranging from working patches to proof of concepts or sketches of ideas. That means that the ground will change under any language using it – which introduces hard version dependencies and complicates building. The other price is that none of these features are part of anything that has been released, and there are no guarantees that it will ever be merged in Java at any point. So the only viable way of distributing Seph would be to distribute standard build files with a patched OpenJDK so that anyone can download and use that specific JDK. But that limits interoperability and causes lots of other problems.

Somewhere in between

My current thinking is that all of the above choices are bad. For Seph I want something inbetween, and my current best approach looks like this. You will need a new build of MLVM with invoke dynamic and method handles to develop and compile Seph. I will utilize invoke dynamic and method handles in the implementation, and allow people to use Rémi Forax’ JSR 292 backport to run it on Java 5 and 6. When Java 7 finally arrives, Seph will be more or less ready for it – and Seph can get some of the performance and maintainability benefits of using JSR 292 immediately. At this point I can’t actually use defender methods, but if anyone is clever enough to figure out a backport that will allow defender methods to work on Java 5 or 6, I would definitely use them all over the place.

This doesn’t actually preclude the possibility of creating alternative research versions of Seph that uses some of the other MLVM patches. Charles Nutter have shown how much you can do by using flags to add features that are turned off by default. So Seph could definitely grow the above features, but currently I won’t make the core of the language depend on them.

8 Comments | By Ola Bini | In: blogging, seph | tags: davinci, invoke dynamic, java, java 7, jsr292, method handles, mlvm, programming language design, seph. | #

I’ve been dropping a few hints and mentions the last few weeks, and I thought it was about time that I took some time to preannounce a new project I’m working on. It’s going to be much easier writing my next few blog posts if people already know about the project, and my reasons for keeping quiet about it have mostly disappeared. It’s also a moot point since I talked about it at the Emerging Languages camp last week, and the video will be up fairly soon. And I already put the slides online for it, so some things you might have already seen.

So without further ado, the big announcement is that I’m working on a new language called Seph. Big whoop.

Why?

I already have Ioke and JRuby to care for, so it’s a very valid question to ask why I would want to take on another language project – outside my day job of course. The answer is a bit complicated. I always knew and communicated clearly that Ioke was an experiment in all senses of the word. This means my hope was that some of the quirky features of Ioke would influence other languages. But the other side of it is that if Ioke seems good enough as an idea, there might be value in expanding and refining the concept to make something that can be used in the real world. And that is what Seph is really about. That blog post I wrote a few weeks ago with the Ioke retrospective – that was really a partial design document for Seph.

So the purpose of Seph is to take Ioke into the real world while retaining enough of what made Ioke a very nice language to work with. Of course, being the person I am, I can’t actually avoid doing some new experimentation in Seph, but they will be mostly a bit safer than the ones in Ioke, and some of the craziest Ioke features have been scaled back a bit.

Some features

So what’s the difference? Seph will still be prototype based object oriented, in the same way as Ioke. It will definitely consider the JVM its home. It will be homoiconic, and allow AST manipulation as a first class concept – including working with message chains as a way of replacing blocks. It will still have a numerical tower. It will use almost exactly the same syntax as Ioke. It will still allow you to customize operators and precedence rules.

The big difference. The one that basically makes most all other design changes design themselves is a small but very important difference: objects are immutable. The only way you can create new objects is by creating a new object that specifies the difference. This can be done either by creating a new child of the existing object, or creating a new sibling with the specified attributes changed. In most cases, the difference between the strategies isn’t actually visible, so it might be an implementation strategy.

Now once you have immutable objects but still focus on polymorphic dispatch, that changes quite a lot of things. It changes the core data structures, it changes the way macros work, it changes the flow of data in general. It also changes what kinds of optimizations will be possible.

Another side effect of immutability is that is becomes much more important to have a good module story. Seph will have first class modules that ends up still being simple Seph objects at the same time. It’s really a quite beautiful and simple scheme, and it makes total sense.

If you’re creating a new Object Oriented language, it turns out that proper tail calls is a good idea if you can do it (refer to Steele for more arguments). Seph will include proper TCO for all Seph code and all participating Java code – which means you’ll only really grow the stack when passing Java boundaries. This will currently be done with trampolining, but I deem the cost worth the benefit of a tail recursive programming style.

I mentioned above that objects are immutable. However, local variables will be mutable. It will also be possible to create lexical closures. I’m still undecided whether it’s a good idea to leave a big mutable hole in the tyoe system, or whether I should make it impossible for lexical closures to mutate their captured environment. Time will tell what I decide.

Stealing is good

Seph believes in reusing concepts other people have already made a great job with. As such, many pieces of the language implementation will be stolen from other places.

Just like in Ioke, the core numbers will come from gnu.math. This library has served me well, and I’ll definitely continue to use it. The big difference compared to Ioke is that the gnu.math values will be first class Seph object, and won’t have to be wrapped. Seph will also have real floats instead of bigdecimals. This is a concession to reality (which I don’t much like, btw).

Seph will incorporate Erlang style light weight threads with an implementation based on Kilim (just like Erjang).

As mentioned above, the core data structures will have to change. And the direction of change will be towards Clojure. Specifically, Seph will steal/has stolen Clojures persistent data structures, all the concurrency primitives and the STM. I don’t see any reason to not incorporate fantastic prior art into Seph.

As mentioned above, the module system is also not new – it’s in fact heavily inspired of Newspeak. Having no globals force this kind of thinking, but I can’t say I would have been clever enough to think of it without Gilad’s writings, though.

Basically everything else is copied from or inspired by Ioke.

Isn’t mutability the essence of Ioke?

If you have worked with Ioke, or even heard me talk about it, you might have gotten the impression that mutability is one of the core tenets of Ioke. And your impression would be correct. It wasn’t until I started thinking about what a functional object hybrid version of Ioke would look like, that I realized most of things I like in Ioke could be preserved without mutability. Most of the macros, the core evaluation model and many other pieces will be extremely similar to Ioke. And this is a good thing. I think Ioke has real benefits in terms of both power and readability – something that is not easy to combine. I want Seph to bring the same advantages.

Will you abandon Ioke now?

In one word: no. Ioke is still an experiment and there are still many things that I want to explore with Ioke. Seph will not fill the same niche, it won’t be possible for me to do the same experimentation, and fundamentally they are still quite different languages. In fact, you should expect an Ioke release hopefully within a few weeks.

So will it be useful?

Yes. That’s the whole goal. Seph will have an explicit focus on two areas that Ioke totally ignored. These areas are concurrency and performance. As seen from the features above, Seph will include several powerful concurrency features. And from a performance standpoint, Ioke was a tarpit – even if you wanted to make it run faster, there wasn’t really anything to get a handle on. Seph will be much easier to optimize, it’s got a structure that lends itself better to compilation and I expect it to be possible to get it to real world language performance. My current idea is that I should be able to get it to JRuby performance for roughly the same operations – but that might be a bit optimistic. I think it’s in the right ballpark though. Which means you should be able to use it to implement programs that actually do useful things in the Real World ™.

Is it available?

No. At the current point, Seph is still so young I’m going through lots of rewrites. I would like the core to settle down a little bit before exposing everything. (Don’t worry, everything is done in git, and the history will be available, so anyone who wants to see all my gory mistakes will have no trouble doing that). But in a nutshell, this is why this is a preannouncement. I want to get the implementation to the stage where it has some of the interesting features I’ve been talking about before making it public and releasing a first version.

Don’t worry though, it should be public quite soon. And if I’m right and this is a great language to work in – then how big of a deal is another month of waiting?

I’m very excited about this, and I hope you will be too! This is an adventure.

17 Comments | By Ola Bini | In: ioke, seph | tags: concurrency, ioke, programming language design, programming languages, seph. | #

Yesterday was the first day of the Emerging Languages Camp, a part of OSCON specifically organized for language creators and designers. You can read more about it at www.emerginglangs.com. The first day was fantastic, lots of very interesting talks and great conversations. The amount of brain power in this room is really humbling.

The format of the camp is that there are about 20 speakers and each speaker gets 20 minutes. This is a fairly limiting format and means the speakers will have to focus their talks quite substantially. I expected a few talks (including my own) to bomb completely because of this, but it didn’t happen during the whole day. All of the talks were very different but good in many ways.

All of the presentations are filmed by Confreaks and will be available within a few weeks.

I’ll try to write a few sentences about each presentation, with thoughts and impressions baked in.

Go

Rob Pike started out the day by talking about the history of CSP (communicating sequential processes) and the lineage of languages that led to Go. Most of the talk was based on using channels/goroutines to handle concurrency. It was definitely a good talk, but it didn’t get me more interested in using Go for anything.

Ioke/Seph

I had the second slot. I had twenty minutes to cover both Ioke and a new language I’m working on, called Seph. Against all odds, my talk went quite well and I managed to communicate the things I wanted to get said. Hopefully the audience wasn’t too bored.

Thyrd

Thyrd is a proof of concept visual language, focused on using tablets for programming – so it’s distinctly none-textual. In many cases you drag and drop operations instead of typing them. The actual development happens in a recursive grid of cells. I’m wondering what the audience for this language would be – it definitely looks intruiging though, and I like how some algorithms ended up being very easily readable and understandable.

Parrot

Allison Randall gave a talk about what’s currently happening with Parrot. It seems they are going for a new rewrite of most of the subsystems. One of the changes is going from a CISC style op code system to a RISC style. Parrot apparently has over 1200 op codes at this point, and they want to scale back everything to about 20-30 bytecodes instead. As a preparation for this, they have ripped out the JIT and will revisit most of the subsystems in Parrot to see what can be done. Allison also gave the audience the distinct impression that Parrot is still quite slow for user programs.

Ur

Of all the talks during the day, I think I understood the least of the Ur/Web talk. Ur is a functional limited programming language focused specifically on building web applications. It’s got dependent types inspired by Agda and allow you to statically check your whole program. The example shown was a simple CRUD app, and I didn’t get any impression of how complicated it would be to actually use it for a real world application. The speaker said the only real world web app he knows about is a hosting application for Ur applications that he is building himself.

Frink

I don’t think I can do this presentation justice. Frink is just incredibly cool and you should check it out. It’s a general purpose programming language, but it’s got units of measure and several other features builtin that makes it very easy to use it to calculate all kinds of interesting facts. As an example, he showed that if all people in China jumped at the same time, that would be equivalent to 4.7 on the Richter scale.

Newspeak

Gilad Bracha talked a bit about the basic ideas and principles behind Newspeak and what the current status is. Gilad focused on no global state, and all names being late bound (including class names). The first feature falls quite naturally out of prototype based OO, so it’s something both Io, Ioke and Seph has (and it’s really nice). The second feature is a bit more obscure, but I’m not sure if it gives as many benefits as the first one.

F#

Joe Pamer talked about what they had to do to take F# from a research language to something Microsoft could ship in Visual Studio 2010. Not something most of us really think about, but there are lots of challenges in doing that kind of transition. Joe covered this quite well and also gave us an insight into the current state of F#.

CoffeeScript

CoffeeScript is a language that compiles down to JavaScript. In comparison with GWT for example, it’s pretty close in semantics to JavaScript, and the generated code can be debugged and looked out without wanting to stab out your eyes. The syntax of CoffeeScript is very pleasant and looks very nice to work with (it’s indentation based, and focuses on getting lambdas to be as small as possible). Next time I’m reaching for JavaScript, I think I might just go for CoffeeScript instead. Good stuff.

Mirah

Charles Nutter covered Mirah (the language formerly known as Duby). It looks more and more complete and useful, and sooner or later I’m going to try switching most of my Java development to Mirah. The extensability features makes it possible to do metaprogramming tricks in Mirah that you wouldn’t even try in Ruby.

Io

Steve jumped in last minute to cover for the Objective-J guy who couldn’t be here. Steve covered the basics of Io, talking about concurrency and the other basic features.

It’s been a great first day, and now day two begins – so I’ll have to focus on that.

10 Comments | By Ola Bini | In: blogging, ioke | tags: conferences, emerging languages, ioke, programming language, programming language design, programming languages, seph. | #