Friday, August 29, 2014

Deconstructing Floats: frexp() and ldexp() in JavaScript

While working on my SqueakJS VM, it became necessary to deconstruct floating point numbers into their mantissa and exponent parts, and assembling them again. Peeking into the C sources of the regular VM, I saw they use the frexp() and ldexp() functions found in the standard C math library.

Unfortunately, JavaScript does not provide these two functions. But surely there must have been someone who needed these before me, right? Sure enough, a Google search came up with a few implementations. However, an hour later I was convinced none of them actually are fully equivalent to the C functions. They were imprecise, that is, deconstructing a float using frexp() and reconstructing it with ldexp() did not result in the original value. But that is the basic use case: for all float values, if
[mantissa, exponent] = frexp(value)
then
value = ldexp(mantissa, exponent)
even if the value is subnormal. None of the implementations (even the complex ones) really worked.

I had to implement it myself, and here is my implementation (also as JSFiddle):
function frexp(value) {
    if (value === 0) return [value, 0];
    var data = new DataView(new ArrayBuffer(8));
    data.setFloat64(0, value);
    var bits = (data.getUint32(0) >>> 20) & 0x7FF;
    if (bits === 0) {
        data.setFloat64(0, value * Math.pow(2, 64));
        bits = ((data.getUint32(0) >>> 20) & 0x7FF) - 64;
    }
    var exponent = bits - 1022,
        mantissa = ldexp(value, -exponent);
    return [mantissa, exponent];
}


function ldexp(mantissa, exponent) {
    return exponent <= 1023 ?
        mantissa * Math.pow(2, exponent) :
        mantissa * Math.pow(2, 1023) * Math.pow(2, exponent - 1023);
}
My frexp() uses a DataView to extract the exponent bits of the IEEE-754 float representation. If those bits are 0 then it is a subnormal. In that case I normalize it by multiplying with 264, getting the bits again, and subtracting 64. After applying the bias, the exponent is ready, and used to get the mantissa by canceling out the exponent from the original value.

My ldexp() is pretty straight-forward, except it needs to be able to multiply by very large numbers. The smallest positive float is 0.5-1073, and to get its mantissa we need to to multiply with 21073. That is larger then the largest float 21023. By multiplying in two steps we can deal with that.

So there you have it. Hope it's useful to someone. And here is the version I put into SqueakJS, if you're curious.

Friday, July 04, 2014

SqueakJS runs Etoys now

TL;DR: Try Etoys in your web browser without a plugin (still buggy, but even works on iPad). Feedback from more platforms is very welcome, and fixes to improve the compatibility, too.
Half a year has passed since my initial release of SqueakJS. Now I can report on some significant progress since then.

For one, I adopted a UI layout similar to Dan’s Smalltalk-72 emulator, where the debugger interface is only visible when the system is stopped. Now that the basics are working, there is no need to show the debugger all the time. Try it yourself at the Lively page.


But more importantly, many more subsystems are working now. BitBlt is almost complete (all the important modes are implemented), WarpBlt works (for scaling and rotating morphs), the image can be saved, an emulated file system supports reading and writing of persistent files. This now is enough to not only run the very old and undemanding “mini.image”, but SqueakJS now can even run the very latest Etoys image, the same version as on Squeakland. Beware of the many incomplete features and outright bugs still left to be fixed, but try it for yourself here.

While Etoys feels a lot slower than the MVC “mini.image”, and some operations take many seconds, it is surprisingly responsive for normal interaction. On the browsers with the fastest JIT compilers (Safari on Mac, IE on Windows) it is almost good enough, even though no serious optimizations were done yet. It is also interesting to see that some browsers (Chrome and Firefox) are currently significantly slower. And not just a little slower, but Safari outperforms Chrome by 200% for this workload! This is likely due to Safari›’s excellent LLVM-based FTL JIT.


The remarkable thing about the screenshot above is how unremarkable it looks. Apart from the missing white oval behind the “Home” label it looks just like it’s supposed to. In comparison, a week ago the screen still looked like this:


The difference is that Tobias Pape and I added support for Balloon2D rendering. This is Squeak’s default vector rendering engine, originally created by Andreas Raab to show Flash animations. But unlike the rest of the SqueakJS VM, we did not port the original code. Instead, our plugin intercepts the drawing commands and renders them using HTML5 canvas drawing routines. While still far from complete, it can already render one kind of important shapes: TrueType font glyphs. They are defined by BĂ©zier curves, which need to be rendered with anti-aliasing to look nice. And now that we can render text, the graphics are almost complete. Many more details still need to be implemented, especially color gradients.

This highlights one strength of Squeak: The VM and its plugin modules present a well-defined, stable interface to the outside world. That is what makes a machine truly “virtual”. In contrast, other systems rely on FFI (the foreign function interface) or similar techniques for extension. While convenient during rapid development, it does not keep the interface small and stable. That interface is overly broad and unpredictable. Typically, client code must be special-cased per platform. It's calling C functions directly, which may or may not exist on a given platform. That makes it much harder to move the system to another platform, and in particular one that is completely different, like the web browser. The Squeak Etoys image on the other hand did not have to be modified at all.

What I’d like to see fixed in Squeak is that there should be working fallback code for all non-essential primitive functions. This would make it much easier to get up and running on new platforms.

For SqueakJS, bugs need to get fixed, and many features are still missing to run Etoys fully. Adding support for other Squeak releases than Etoys would be great (closure/Cog/Spur images). Contributions are welcome: fork my github project.

Friday, December 20, 2013

SqueakJS: A Lively Squeak VM

I'm proud to announce SqueakJS, a new Squeak VM that runs on Javascript:


It was inspired by Dan's JSqueak/Potato VM for Java, and similarly only runs the old Squeak 2.2 mini.image for now. But I developed it inside the Lively Kernel, which allowed me to make a nice UI to look inside the VM (in addition to all the Lively tools):


It represents regular Squeak objects as Javascript objects with direct object references. SmallIntegers are represented as Javascript numbers, there is no need for tagging. Instance variables and indexable fields are held in a single array named "pointers". Word and byte binary objects store their data in arrays named "bytes" or "words". CompiledMethod instances have both "pointers" and "bytes". Float instances are not stored as two words as in Squeak, but have a single "float" property that stores the actual number (and the words are generated on-the-fly when needed).

For garbage collection, I came up with a hybrid scheme: the bulk of the work is delegated to the Javascript garbage collector. Only in relatively rare circumstances is a "manual" garbage collection needed. This hybrid GC is a semi-space GC with an old space and a new space. Old space is a linked list of objects, but newly allocated objects are not added to the list, yet. Therefore, unreferenced new objects will be automatically garbage-collected by Javascript. This is like Squeak's incremental GC, which only looks at objects in new space. The full GC is a regular mark-and-sweep: it's marking all reachable objects (old and new), then unmarked old objects get removed (a very cheap operation in a linked list), and new objects (identified by their missing link) are added to the old-space list. One nice feature of this scheme is that its implementation does not need weak references, which Javascript currently does not support.

This scheme also trivially supports object enumeration (Squeak's nextObject/nextInstance primitives): If the object is old, the next object is just the next link in the list. Otherwise, if there are new objects (newSpaceCount > 0) a GC is performed, which creates the next object link. But if newSpaceCount is 0, then this was the last object, and we're done.

The UI for now copies the Squeak display bitmap pixel-by-pixel to a typed array and shows it on the HTML 2D canvas using putImageData(). Clipboard copying injects a synthetic CMD-C keyboard event into the VM, then runs the interpreter until it has executed the clipboard primitive in response, then answers that string. This is because the web browser only allows clipboard access inside the copy/paste event handlers. You can drag an image file from your disk into the browser window to load it.

Besides running it on your desktop, you can install it as offline web app on an iPad:


On the iPad there is neither right-click nor command keys, but the menu is available on the inside of the flop-out scrollbars. It needs a fairly recent browser, too - it works in iOS 7, but apparently not in older ones. On Android it works in Chrome 31, but not quite as well (for example, the onscreen-keyboard does not come up on an Galaxy Note tablet).

Go to the project page to try it yourself. The sources are on GitHub, and contributions are very welcome.

Have a great Christmas!

Monday, February 25, 2013

Smalltalk Bindings for Minecraft Pi

The Raspberry Pi is a cute little computer. Quite cheap at $35, you plug in USB keyboard+mouse and a TV as monitor. And it is surprisingly capable, even for running 3D games.

One particularly interesting game is Minecraft: Pi Edition. As in other Minecraft versions, the main goal is to create a world. But unlike other versions, you can not only use the tools provided by the game, you can make your own tools! That's because it comes with a programming interface.

The Minecaft world is made of little cubes, and you normally place or remove these blocks by hand, one after another. This is fun, but for larger structures also quite cumbersome. For example, this rainbow here might take a long time to construct manually:


But I did not make the rainbow by hand. I programmed it, using the Smalltalk programming language. It's just these dozen lines of code in the Squeak programming environment:


Squeak is already installed on the Raspberry Pi, because Scratch was made in Squeak. Of course you need a little more to make this dozen lines of code work. Mojang (the developers of Minecraft) have provided "bindings" for the Python and Java programming languages, but not for Smalltalk. So I had to make these bindings first.

Here are the Bindings

Now you can use the bindings too, because I am publishing my code:
http://ss3.gemstone.com/ss/minecraft.html
Squeak can either run on the Raspberry Pi itself (a VM is already installed) or on another computer in your network.

There are two packages, 'Minecraft-Pi-Base' and 'Minecraft-Pi-Demo', load them in this order. At the time of writing, the demo package has only the rainbow method in it. The code is not heavily commented, but from the examples it should be fairly obvious how to use it. 

The bindings are still somewhat basic, but cover all the functions of the current Minecraft-Pi 0.1.1 release. There is certainly room for improvement. E.g. it would be nice to add symbolic block names, so you could write "wool" instead of "35". And the hit testing (when you right-click on a block with your sword) works, but could be made more convenient to use, perhaps by introducing an event class like in the other bindings.

I made the repository open, so anyone can easily contribute. I'm curious what others will come up with.   Like, control Minecraft from Etoys or Scratch? How about a Croquet bridge? Build a little game? In any case, have fun! :)

Saturday, October 20, 2012

Squeak Etoys running on OLPC XO-3 tablet

SJ brought a hand-assembled XO-3 prototype to the OLPC Community Summit in San Francisco (mass production only starts when someone puts in a large-scale order), and of course I tried to run Etoys on it. It's pre-installed (as on all XOs) and worked right out of the box.

I was able to paint and drag objects, but since there is no right-click support yet there was no halo to bring up a new viewer. Also, touch targets are rather small for my adult-sized hands, and since there are no hover events, some features don't work correctly (as we found out with the iPad version two years ago).

So more work is needed, as well as for the XO-4 which has a multitouch screen in addition to a keyboard and touchpad. Help welcome :)

Monday, August 29, 2011

Squeak Etoys on ARM-based OLPC XO-1.75

First post this year, yikes! The last one was about ESUG 2010 in Barcelona, now I just returned from ESUG 2011 in Edinburgh. While I was there, a package with the shiny new XO-1.75 prototype arrived.

Incredibly, the pre-installed Etoys simply worked! Never mind the change in processor architecture, the Fedora folks have done a great job compiling the Squeak VM for ARM and so Etoys just works. Of course that's just as it should be, but it's still awesome. And e.g. Squeakland's own Etoys-To-Go would not have worked, as it only includes binaries for Intel-compatible processors.

Another great addition is a 3-axis accelerometer. The Linux kernel's driver exposes it as a file at /sys/devices/platform/lis3lv02d/position. Gotta love the unix design of exposing devices as files. All it took to make this usable from an Etoys project was just an object with ax, ay, and az variables that get set with one simple textual script:
Another simple script can use this to control a ball (the "rebound" script just keeps it on-screen):
Fun all around—it's a bit a hard to see the yellow ball in the Video, but Jakob enjoys it anyway:
Also, uploading from Etoys directly to Squeakland using Wifi just worked. Yay!

Update: If you want to try my uploaded project on your XO-1.75, you need to save it once from Etoys, quit Etoys, and run it again. Otherwise it won't work - it was signed by my key so the Etoys security sandbox prevents it from opening the accelerometer device. The saved copy will be signed using your key so no sandboxing happens.

Monday, September 20, 2010

ESUG 2010 in Barcelona

This year's conference logo was designed by my good friend Patty Gadegast.
I just returned from the European Smalltalk User Group conference in Barcelona, Spain. It was a really nice experience. There was too much going on to report everything here, so I will just pick some favorites.

Photo by Bert Freudenberg

The event was hosted by citilab CornellĂ . It started off with a Camp Smalltalk over the weekend. I already met quite a few people there. I couldn't mingle as much as I hoped to because I had to get the first Etoys 4.1 release candidate out of the door:
Photo by Adriaan van Os
Close by was "Yokohama Wok", a Japanese/Spanish restaurant with the best all-you-can-eat buffet imaginable. You could have everything from freshly cut ham to sushi, grilled steak or seafood, bread, pasta, rice, fruits, cake, desserts.
Photo by Bert Freudenberg
I talked to Stef (president of ESUG) and gave him a Squeak Etoys button, which he ended up wearing the whole week:
Photo by Bert Freudenberg
We also played together in a 2-on-2 Magic game (which we promptly lost ...):

Photo by Bert Freudenberg
On Monday I gave my Squeak Community Update talk, outlining what has happened in the Squeak and Etoys communities lately. Got some nice comments afterwards, including the request to give an  Etoys demo the next time. I of course used Etoys to give the presentation, but did not really include an Etoys introduction for people who had not seen it before. But I got a slot in the "show us your projects" session on Tuesday where I made up for that with a 10 minute demo.
Photo by Adriaan van Os
Gonzalo Zabala and his students from Argentina presented Physical Etoys:
Photo by Adriaan van Os


I also liked the Xtreams presentation by Martin Kobetic:
Photo by Adriaan van Os

I was session chair on Wednesday morning, so I could see Travis' update on Pango text rendering from the first row. Would love to have that in Squeak, but it only builds easily on Linux:
Photo by Adriaan van Os

But the most exciting thing on Wednesday was of course that Physical Etoys won the ESUG Innovation Technology Award:
Photo by Adriaan van Os
On Thursday, I participated in a panel discussion about open-source licenses, organized by Julian Fitzell and Jason Ayers of Cincom.
Photo by Adriaan van Os

In the projects session, Ricardo demoed some of his Etoys work done during Google Summer of Code:
Photo by Adriaan van Os

Besides showing his graphing tools, the comic-like bubbles were a favorite with the audience:
Photo by Adriaan van Os

Dale showed the beginnings of Bibliocello, a repository for Monticello packages that can actually analyze them. You get to search implementors and senders across all packages, take statistics etc.
Photo by Adriaan van Os

And at the end of the day, an exciting demo was given by HwaJong Oh, a Smalltalker and iPhone developer from Korea. He demonstrated Drag-and-Drop for Squeak Tools, e.g. dragging the object held in an instance variable directly to another inspector.
Photo by Adriaan van Os

He also used cool animated mind-maps for his introduction:
Photo by Adriaan van Os

The highlight on Friday was Lukas' Helvetia presentation. I particularly liked the integration of PetitParser with the Smalltalk tools.
Photo by Adriaan van Os

All in all it was a rather refreshing conference at a great location with interesting people. Looking forward to next year's ESUG :)

Tuesday, June 15, 2010

Squeak Etoys on iPad

In preparation of making Etoys work on the recently announced OLPC tablet, I ported it to the iPad. Here is a video—read on below for some details:



This might look exciting, and it certainly is, but it feels actually a lot more clunky than it looks. You may have noticed the little target circles I added whenever a finger touches the screen. That's to know where exactly the finger hit. It's really hard to hit anything, took me a while of training to hit the colorful halo handle buttons on first try. We really need to redesign the user interface before giving this into the hands of kids ...

But for now, some technical details: John McIntosh ported the Squeak Virtual Machine to Apple's touch-based OS last year (source available at isqueak.org). I modified it slightly to enable multi-touch and keyboard input. Also, I rewrote his code to deal with touch events in Squeak, and added multi-touch handling to Morphic. Fortunately, Morphic was designed to handle multiple "hands" (pointing devices) from the beginning, so adding this was much easier than in a system that assumes there is only one mouse. That's why moving multiple objects at the same time, and painting with more than one finger, just works once the events are in the system.

So far this is just an early test. We should work on improving the Etoys touch UI in next year's release. The Sugar menu bar works fine, but everything else is way too small. At least we have the luxury of being able to test Etoys already—getting the rest of Sugar running on a touch device might take a while. Hopefully OLPC will have developer machines soonish. If this test has shown one thing, then that there is lots of work to do (and it may even be necessary to start over).

Monday, January 04, 2010

How to write a Sugar activity in Squeak/Etoys

Milan just started a blog describing how to write activities in Squeak, see his first post. There are already a few of these, most notably the games by Robert Hirschfeld's students at the University of Potsdam, Germany. But so far the process is only documented in mailing list posts. Way to go, Milan!

Monday, December 22, 2008

Peaceful Holidays ...

... and a Happy 2009 to everyone from me and my family.
Presented by my XO-hugging USB men (who seem to have more memory capacity than me at times).
Featuring a seriously tree-infested Etoys project, with snow (for those living south who cannot enjoy the white fluff this time of the year).
And see you at 25C3 I hope!