Tuesday, August 22, 2006

Groovy and Scala Multithread Actors

Parallel exection of Methods.

In my last blog entry I used a MetaClass to change the method execution modell. Some days ago a paper surfaced in the german Java newsgroup about parallel execution of methods in Scala. I found it quite interesting, but maybe there is a way to have that for Groovy too?

I think it is possible using a custom MetaClass again. Again we would collect the method calls, but this time we would use multiple threads to execute the methods. Using a pool for that could be a good choice. Anyway, I don't want to go too much into the details this time, but if you look at my last blog entry and exchange the method execution part with something like:

   stack << method 
while (stack) {
def call = stack.pop()
ThreadPool.run(delegate,call)
}
}
And then make asynchronous access to the stack to put the frames on, then it would work there too. A special method might be needed to synchronize the method calls again. Something like "metaClass.waitForMethodCalls()". Again we could use a method to switch between parallel and normal execution, just like we have done with recursive and iterative execution before. And of course we have the same disadvantages as the last time. Maybe I will have somewhen a bright idea how to solve the return value problem in a much nicer way than using a global variable. I will let you know it then.

And of course I wouldn't propose such a solution for working on a Cell processor, where we simply use as many Threads for the method calls as cells are available... but maybe, with a bit more research, this could be used to make an efficient execution system without the need to explicitly handle Threads. Yes... well... there is the synchronization problem. Not only to wait for methods to end their calls, but also to synchronize access on variables.

As always when walking on the edge, you should know what you do.

Iterative Method Execution Modell in Groovy?

I wonder if that is possible... what? uh, sure, you don't know what I mean. Ok, let us see...

def foo(){
bar()
}

def bar(){
foo()
}
You may know this example from the tail recursion article a few days ago. But I want to extend that example now and to this:
def foo(){
bar()
baz()
}

def bar(){
foo()
baz()
}

def baz(){}
So every method makes an recursion step and then calls the empty baz method. Congratulations, we succesfully eliminated a tail recursion. While executing these methods may never end in a endless loop, as we need to keep a trace to remember we have to call the baz methods, the available recursion depth isn't as deep as I wish it would be. The last time we work around the problem using Closures... Maybe this would work today again? But what to put in the closure? The calls? No that's no solution. Maybe a special version, that means "make a recursive call and give me what you intend to execute after". So our foo might transform into
def foo(){
recursiveCall (this.&bar) {baz()}
}
we would put the Closure on our own Stack, leaving this method and then execute bar first.
def recursiveCall(Closure method, Closure tail){
stack << tail
stack << method
}
And foo would not be called normally, but this way:
def recursiveCallEntry(Closure method) {
stack << method
while (stack) {
stack.pop().call()
}
}
recursiveCallEntry(this.&foo)
what about tree like structures?
def foo() {
bar1()
baz1()
bar2()
baz2()
}
could be a tree iteration or something. This would be converted into:
def foo() {
recursiveCall(this.&bar1){baz1()}
recursiveCall(this.&bar2){baz2()}
}
And does it still work as it should? After executing these methods we have a stack like this one:
bar2,baz2,bar1,baz1
With bar2 on top. That's bad, bar1 needs to be executed first. So we need to reorder that.. but not in recursiveCall. You may see that recursiveCall, is doing something like a collection step. Collecting all method calls that we need to do. So if we collect all the calls the recursiveCall methods do in a list or something, we can simply revert the list and then put the elements in the correct order on the stack. As our recursiveCallEntry method does have the real control over the custom stack, we can use that method.
def recursiveCallEntry(Closure method) {
stack << method
while (stack) {
frame = []
stack.pop().call()
stack.addAll(frame.reverse())
}
}

def recursiveCall(Closure method, Closure tail){
frame << method
frame << tail
}
As you see we no longer revert the order in recursiveCall, since we do this explicitly with frame.revert in recursiveCallEntry. Using this system we can bypass the normal stack, build our own stack and get a much better depth. But "recursiveCall(this.&bar1){baz1()}" looks really ugly. Oh.. do we need that? why distinguish between the real recursive call and the non-recusrive calls? No, I don't think so.
def foo() {
recursiveCall this.&bar1
recursiveCall this.&baz1
recursiveCall this.&bar2
recursiveCall this.&baz2
}
That is better, but still not nice. We could use Strings for the method name, but we then loose the object we want to execute the method closure on. Oh.. and parameters? In the end the code would look like
recursiveCall (this, "baz2", null)
to call the baz2 method. what most people probably don't know is that such a line already exists in the bytecode, because each normal method call is done by using a method of ScriptBytecodeAdapter. So if had a flag method or something we could use that to execute our methods and keep the readability. Oh no, again a crazy idea is born.
def foo() {
switchToIterativeCallSystem()
bar1()
baz1()
bar2()
baz2()
switchToRecursiveCallSystem()
}
but wait... do we really have to do that on the ScriptBytecodeAdapter? We can do that with the MetaClass too! We simply need to replace the MetaClass for "this" with our own crazy version...
class IterativeCallerMetaClass extends  DelegatingMetaClass {
def stack =[]
def frame
boolean iterativeCallSystem=false

public IterativeCallerMetaClass (final MetaClass delegate) {
super(delegate);
}

def invokeMethod(Object object, String methodName, Object[] arguments) {
if (iterativeCallSystem){
frame << [object,methodName,arguments]
} else {
delegate.invokeMethod(object, methodName, arguments);
}
return null
}

def recursiveCallEntry(Closure method) {
stack << method
while (stack) {
frame = []
def call = stack.pop()
delegate.invokeMethod(call[0], call[1], call[2]);
stack.addAll(frame.reverse())
}
}
}
And the complete calling code would maybe llok like this:
def foo() {
metaClass.iterativeCallSystem = true
bar1()
baz1()
bar2()
baz2()
metaClass.iterativeCallSystem = false
}

this.setMetaClass ( new IterativeCallerMetaClass (this.getMetaClass()) )
Disadvantages? Yes, sure. This completly ignores the return value. And sadly I don't see a way to fizzle it in. I mean a call foo(foo(1)) is really something like "tmp = foo(1); foo(tmp)". That means I need the value of "tmp" while I am still in the collection phase, where it isn't available, since the call isn't done then. Next disadvantage is, that that MetaClass only works on one object. Any foo.toString(), where foo!=this, isn't collected. Which directly leads to the next problem, logic operations are executed before the values are available.

To work around that we can put all that code in Closure and add these closures to the custom MetaClass stack, but that gives again problems with local variables and such. If you have a tree with an unknown number of children and you want to do an depth first search on the children, you would normally do something like that:
def search(node,constraint) {
if (constraint(node)) return node
node.children.each{search(it,constraint)}
}
But when you want to use our iterative system...
def search(node,constraint) {
metaClass.add {
if (!found && !constraint(node)){
node.children.each {search(it,constraint)}
} else {
found=node
}
}
}
That's an ugly level of indirection... I used the global variable found to indicate if we need to search deeper, this avoids the return value. Then the closure will be put on the stack and executed when the data is available, collecting the search calls and later execute each of them. This can only work if all actions other than pure method calls on this are done in closures.

Conclusion:
This let's me think that such an solution should be much more easy in Ruby. But as I don't know enough about Ruby I don't know if there is such a MetaClass system as we have in Groovy. But being able to simply put the method body on the stack instead of a closure would be nice. Anyway, it works. We can also remove the "metaClass.iterativeCallSystem=" lines with the convention that the system is always active. Of course this works with a builder just as fine as with a normal class, you only have to do the job of our MetaClass in the builder then.

You see, many tricks can be done with the MetaClass, even a total different method execution model. Ok, not toally different, as the VM still does the invocation and still keeps a trace, but we successfully shortend that stack trace. Oh, and of course the above works for tail recursion just as well. You can say we included them here already. Of course the solution developed into a completly different direction than my previous post about tail recursion.

And maybe a word about the execution speed. Of course you add an additional level of indirection for method calls, our delegating MetaClass. So instead of doing one mthod call we do much more of them, for example when testing the stack if it is empty, when getting the top frame and more. But if your focus is on avoiding a stack overflow it works just fine.

Wednesday, August 16, 2006

Tail Recursion in Groovy?

Is it possible?

Tail recursion can be very useful when traversing big lists or trees using recursive methods. The JVM doesn't support tail recursion - maybe there is a way to simlulate them. But first, what is a tail recursion?

A tail recursion is, well I thik the wikipedia explanation is quite good ;) For me the important thing here is to reduce the Stack pollution and not to get an exception from the JVM, because the trace got too big. So a transformation of one kind or another is needed to avoid that.

I know 3 kinds of techniques to accomlish this:

  1. use the compiler to transform the recursion into a loop
  2. let the vm recognize the recursion and eliminate it
  3. mark tail recursion specially and react different then normal
To number 1 I must say, that we could do this in Groovy - partially. That would only work for self recursive functions and it requires the ability to ask the method execution part if that method call is a call to the current method or not. For Java, the last thing is out of question, there is no such query mechanism at runtime to do that. And there is no need, as all methods are selected at compile time. So Java could have this kind of tail recursion. In Groovy we can't be sure if the method we want to call is really being executed. And we may not be sure that the parameters we give really result in the desired method to be executed. Of course we could implement such a query system in Groovy and then we would have the answer. But that would give us only a partial solution as I mentioned already.

Then number 2. Well as long as the Java people don't decide that Java should have that, there is no way for us to get that done in Groovy. Groovy is not a VM in the VM, it is a runtime which does influence the method calls, yes, but it has no real control over the stack.

So what about number 3? Is there something we could do to get tail recursion? Before I get deep in the details imagine the stack that is created for
def foo(){
bar()
}
def bar(){
foo()
}

foo()
We will create a stack element for foo, then, when calling bar, we will create a new stack element for bar. After this one again for foo, and this would go on until the JVM complains about the stack becoming too big. What if we would now not directly cal the method, but return from the current stack frame and then do the call? Using Closures we can simulate that:
def foo(){
{bar()}
}
def bar(){
{foo()}
}
def cl = foo()
while (cl!=null) {
cl = cl()
}
With the result, that the function foo is called and returns with the closure. After this, the closure is called, which does call bar. Then bar returns with the closure and the stack size becomes 0 again. Then the closure is again called. This continues till someone forcefully terminates the program, since we crated an endless loop. Of course it is not very nice to have to do that this way. An autmatism would be nice.

So let us say there are keywords like... trreturn and trcall, well not nice, but it is just for illustration. This signals the runtime to not to simply return after the call was made, but to examine the result and react to this. You need to know, that a normal method call foo() is in fact this: ScriptBytecodeAdapter.invokeMethod("foo"). So instead of using the normal invoke we use the our special invoke method invokeMethodTR.
def invokeMethodTR (String name) {
def c = invokeMethod(name)
while (c instanceof TailCall) {
c = invokeMethod(c.name)
}
return c
}
and foo would be for the compiler:
def foo(){
return new TailCall(name:"bar")
}
a normal user would see this:
def foo(){
trreturn bar()
}
But the initial call to foo must be done using trcall, so the complete program would look like:
def foo(){
trretrun bar()
}
def bar(){
trreturn foo()
}
trcall foo()
This way to do this has actually two problems:
  1. Calling such a method from Java would give a TailCall isntance.
  2. a void method can't return a TailCall instance
The most easy way to go around that would be not to avoid it. Instead we could use it as marker for the method and remove the trreturn:
TailCall foo(){
bar()
}
TailCall bar(){
foo()
}
trcall foo()
The TailCall instance may not only transport the method name and arguments, but also a return value if needed.

Conclusion:
All in all at last one additional keyword is needed to get it working? Maybe using a closure here not even that is needed. We could just say tailcall{foo()} and leave the loop part of the implementation to that method. The compiler is still needed, because someone does have to create the TailCall instances for the return. But the special invokeTR method isn't needed any longer. So any changes to the compiler are doable in no time. Regarding to my question at the start, if it is possible.. well, yes! It's not even very difficult!

Tuesday, August 15, 2006

Beyond Groovy 1.0: Groovy goes Lisp

I was always a fan of LISP, but not of the huge amount of (). Regardless the syntax, LISP gets it power through exactly that, the syntax. The late Binding of expressions and the simplicity of the language in syntax and semantic allows to extend the language itself very easily. And that again allows you to write DSLs embedded in your normal program. And how to get something like that to groovy? A list looks in groovy like that:

[1,2,3]
but that doesn't contain a operation. Adding an operation as normal Element would require a closure - I don't think that is very nice. Anyway, if you could remove the "," we would have a much nicer list:
[1 2 3]
Now let us assume that is something like a quoted list in LISP. How to get an operation inside? If we could omit the comma in general, then we could use a normal method call
add 1 2 3
which is the same as
add(1, 2, 3)
and if we need late binding, we can use closures
{add 1 2 3}
now, what is a simple program in LISP? Maybe
(defun add (x y)
(+ x y))
(add 1 2)
and what would it look like in Groovy with the optional comma?
{defun add {x y}
{x+y}}
{add 1 2}
Of course the curly braces are not that nice here, but needed. Anyway, it looks really a bit like the Lisp example, but would it work? Remember, defun would be a method call and "add" a parameter to that method. That means "add" is evaluated before defun is. So a evaluation system is needed here, that allows to handle such cases. So instead of evalutating directly to a value, we simply return a place holder. Let us name that place holder symbol here. So in fact the defun method would get a symbol and two closures. Ok, now let us define that every method call itself is first evaluted using symbols, so
{defun add {x y}
{x+y}}
would return a list with two symbols (defun and add) and two closures. Let us call the function that does this job preeval. In Groovy terms, preeval is a builder or special MetaClass, that intercepts all calls to methods and properties and does return a list of symbols and closures instead. Then a secound stage evaluation process would start and use that list to execute functions. Let us assume "defun" is delegated to some kind of method, then this method might look like:
def defun(Symbol name, Closure parameter, Closure body) {
evaluationSystem. register (
name,
preeval(arguments),
body
)
}
Again preeval would return a list of symbols, this time they wouldn't be mapped to a method, they would be used to define a scope for the body closure. And when, the the body closure asks for x and y, the evalutation system would know, that these two are in fact the arguments. After this method is available, we can define car and cdr using defun:
{defun car {list}
{list[0]}
}
{defun cdr {list}
{list[0..-1]}
}
Of course having a generic name for car and cdr would also allow the "special" functions caaar and cadar and what else. This is enough to build a powerful LISP like system. I would have to look how macros are realized in LISP, but theoretically these basics here should be enough to allow them too. And then we could do code like this:
def result = lispBuilder.eval
{defun groovy { a b}
{a.name.length() + b.name.length()*10}
}
{groovy is lisp}

assert result == 42
Anyway, that is just a crazy idea, but possible. And all this only by making the comma optional. Of course it would work without that too, but {groovy is,lisp} doesn't read as nice as the version without comma. It would also allow us to become more like Smalltalk, but I will show that in another blog entry. I just wanted to show you how it could be made possible to get something with a sligthly feeling on LISP in Groovy. I won't say that the above fragments are really LISP, but I think by developing this idea to its end it would look much like LISP. but it doesn't have to be LISP, it could be also Scheme and then we could compare Kawa and Groovy *lol*

Conclusion:
There are limitations. I mean names can't have all shapes without being put into "" and requiering a qualificator like here: this."strange variable name". And of course you won't be able to stop Groovy from doing early binding for local variables - I am not sure that is really a disadvantage. I wouldn't expect LIPS people to really migrate from LISP to Groovy just because of this blog entry here. But maybe some LISP people out there, which are forced to program on the JVM might want to consider using Groovy in the future ;)

Getting Groovy 1.0 out is currently more important than having crazy ideas about making Groovy into a overcomplicated LISP. But I must say, I really like this idea.

EDIT:
there is a small error in the artice, closures need to be concatenated by } {, there can't be a newline in between. But maybe this is another thing to change?

Sunday, August 13, 2006

Show me what you have! Featuring Groovy, Swing and db4o

Once again I had to write one of these stupid and boring GUIs. You know these things asking you stupid questions and showing irrelevant Data. Of course I do all in Groovy, no need for a IDE provided gui generation tool. So I used the SwingBuilder to make the GUI.

Really, I understand why people are asking for documentation. The 2 examples here are giving good examples, but basically you have to understand that components are registered and each property can be used using the map syntax. Embedding one component in another works using Closures. but there are things the Swing builder currently can't do. For example registering a MouseListener at a component using Closures as the functions executed by the MouseListener. Or a WindowsAdapter with Closures for certain action, like closing the window. So you still have to create a big bunch of useless classes. That's not nice. Ok, they are not that useless, because you can reuse them later.

We (the Groovy Team) had the idea to convert a closure to a class implementing a certain interface with just one method by the MetaClass or using the as-syntax. Just only that this won't help here, a listener normally has more than one method. So for now, I decided to make the helper classes, but maybe we should simply add an method to the Swingbuilder allowing to do such things. Would be possible and not that difficult I guess.

What puzzled me a bit was, that I have to do things like:


scrollpane {
viewport {
list()
}
}

Now I know a viewport is inside the ScrollPane, but that I have to do that explicitly isn't very nice. In fact I would like to have a default property and then be abel to do that:

list (scrollpane:true)

or at last

scrollpane {
list()
}

Anyway, it doesn't bother me too much.

So I wrote some glue classes like this:

class ClosureWindowClosingAdapter extends WindowAdapter {
def closure
void windowClosing(WindowEvent e) {
closure(e)
}
}

not much logic there, but it allows me to do things like that:

gui.addWindowListener (
new ClosureWindowClosingAdapter(closure:{System.exit(0)})
)

After I have done all these little things I got a nice small gui application. Just a few lines long itself, some minor helper classes and yet no data.
Yes, that's the point where db4o comes to play with us. I had many lists basically showing all available instances of one type. And I never understood why I should make a custom model here to keep multiple lists of the same objects, maybe concat these lists so they can notify each other about changes and such.

I decided I want to use a central data holder this time, the objects are extracted from there using query-by-example and, no, the data holder is not a relational database with hibernate in the foreground. I wanted to have something easy, that allows me to change the class structure and doesn't requires as much overhead as hibernate. So I used one of my helper classes and wired some db4o parts in:

class ClosureQueryModel extends AbstractListModel implements ComboBoxModel{
def cl
def getElementAt(int i){cl()[i]}
int getSize(){cl(query).size()}
def selectedItem
def addElement(foo){/* ignore */}
def remove(foo){/* ignore */}
}

combo.setModel(new ClosureQueryModel(cl:closure))

nice isn't it? Again a predefined class would make life more easy here, but well, it isn't that this helper is a big one ;) and yes, I am ignoring removal and additon of elements, since I wanted to make that completely through the database. cl(query)[i] means I need a list or array or something like that as result. Now in db40 4.3 this would have been a problem, since a query on the database does return an instance of ObjectSet, which is no such list or array. But they changed that, and in 5.2, which means I can directly use the result of the query.

For all people here not knowing how such an query looks like:

def objectSet = db.get(Foo)

yes, that's all. Foo is the class of the objects I want to have and the above query allows me to get all instances from the database. So I would create a ClosureQueryModel isntance like that:

new ClosureQueryModel(cl:{db.get(Foo)})

So now my items would be displayed... but... there is no initial data. What is missing is a functionality to add remove and update items. Well, maybe I got here a bit over the edge, because I got this crazy idea of using a mapping to show the editable fields... but on the other hand, any bean editor is allowing comparable to that. Only that I don't use explicit beans and only that I don't use these extra files for beans describing the bean. Anyway, I made a map like this one:

[name:"field",view:"Feld",collection:{it.availableFields}]

to set a property/field named field, with the display name Feld and it is chooseable from a collection, that is returned by a closure {it.availableFields}. so basically I can choose here between predefined values returned by a property or whatver I use in the closure. then I thought that a simple collection is possibly not enough. What about numbers? so I added a "create" to the map, taking a closure that produces the object:

[name:"workload",view:"Auslastung in %",create:{new BigDecimal(it)}]

create and collection would be exclusive then, but I added no test for that.

I thought, ok, the let us have a popup menu, for the crud operations and put all that logic together in a method.

addPopup(
component:jlist,
producer:WorkloadEntry.class,
maping:[
[name:"workload",view:"Auslastung in %",create:{new BigDecimal(it)}] ,
[name:"field",view:"Feld",collection:{it.availableFields}]
],
newAction:{db.set(it)},
updateAction:{db.set(it)},
deleteAction:{db.delete(it)})
}

producer is the class use to create new instances from, mapping contains the fields/properties set for the new class and how they are displayed, and the *Actions are he database methods for the crud operations. Pretty easy, but the mapping tends to be big for man fields. I should think of something different here.

I don't want to show all of the code of that method here. The method itself is 100 lines long, as much as the rest of the program. A sure sign, that it is too complicated. But well, the basic parts:

I need to display the views:

args.maping.each { item ->
label(item.view+":",constraints:gbc1)
if (item.collection != null) {
def combo = comboBox(constraints:gbc1)
combo.actionPerformed = {query.setProperty(item.name, combo.selectedItem)}
combo.setModel(new ClosureQueryModel(query,item.collection))
} else if (item.model){
def combo = comboBox(constraints:gbc1)
combo.actionPerformed = {query.setProperty(item.name, combo.selectedItem)}
combo.setModel(new ChoiceModel(item.model))
} else {
selection << textField(constraints:gbc1)
}
}

saving it would look like:

args.maping.eachWithIndex { values,index ->
def sel = getViewComponent(index)
if (sel instanceof JComboBox){
obj.setProperty(values.name, sel.selectedItem)
} else {
def val = sel.text
if(values.create!=null) val = values.create.call(val)
obj.setProperty(values.name, val)
}
}
[...]
if (args.newAction!=null) args.newAction.call(obj)
args.component.model.addElement(obj)
args.component.model.fireContentsChanged(editWindow, args.component.selectedIndex, args.component.selectedIndex)

You can see the create closure here, called if set and if a JTextField was used to display it. Maybe giving the component instead of the text only would be also a improvement and would allow other components. But this was more of a case study, not a general purpose solution.

Even without the usage of the database, such a component should be thought through. I mean you need something like that quite often.

Conclusion:
Groovy's Swing part currently consists only of the SwingBuilder. That helps a lot creating guis, but when it comes to models and listeners, the SwingBuilder lacks a huge amount of them. Models for spinner and tables are there, but not more. I think, developing Swing with such components can improve your productivity when it comes to make a prototype. You can alaways decide to change the class model and you can always change the gui itself. You could even think about a text, that you enter when a button is pressed and then that text is executed as script. Of course the combination with an plugin such as the eclipse groovy plugin would make things even more nice. But even without such self hosting features, it makes much more fun than plain Java, even if a WYSIWYG editor is involved. If I had more time for Groovy I would no go on and improve the Swing abilities of Groovy big time.. but maybe there is someone else who wants to do that. Groovy is open source and people doing such things are always welcome.

I hope I won't have to say that last part too often. Of course I would like to do all the ideas I have by myself, but I can only spend a few hours every week on Groovy and that is not quite enough to get issues fixed and to add new ideas.

a new blog - oh my, why that again?

Hi there

I am about to start my new blog here. In the future I want to let you people know about java and groovy related thoughts, problems and stories - maybe other stuff too.