art with code

2013-08-25

Message

Hey peeps, I made a webapp for making presentations quickly. It's kinda rough and geeky but give it a spin.

https://message.fhtr.net




Feature highlights

  • super fast to write preso slides 
  • embed images, video, audio and websites 
  • timing marks to keep your script straight 
  • practice count notation to help you hone your delivery 
  • your edits are synced between devices so that you can use your phone to work on your preso in the train, then whip out your laptop at work and continue on it 
  • full themability with Stylus 
  • heck, you can even hack the slide parser JS to customize everything 
I also use it as a mobile notepad, which is kinda nice... Maybe I should make a separate product for that.

2013-08-23

Adventures in OT, part 2

I've got a couple new tidbits to add to my previous post about implementing an operational transformation library. Operational transformations are about recording your edits and streaming them to the other collaborators. The concept is simple and the implementation isn't super-complicated, but it can be a bit tricky.

Anyway, I was hooking up the transformation library to inputs and textareas. Which, well, I guess you should just use a diff algorithm, it's probably less of a browser-compatibility hassle. I ended up doing it the hard way.

I'm monitoring events on the input element and keeping track of the cursor position using selectionStart and selectionEnd. When the contents of the element change, I figure out what kind of change it was and record a cursor movement followed by insert & delete events.

If the selection is empty, the change is an insert or a delete. If the input value is longer than the previous value, the change is an insert. If the value is shorter, the change is a delete. This logic works fine until you run into iOS autocorrect.

With autocorrect, the selection is empty but the cursor jumps multiple characters forwards. So I had to add a hack to the tune of "if the cursor jumps forward, set the selection length to the distance between last cursor position and current cursor position". Which works for simple autocorrect cases, but not for the autocorrect popup menu suggest action. Anyway, it sort of works. And this is why you should use a diff algorithm to record your edits.

Here's the code I've got at the moment:

// Setup event recording for the input element.
// Record the edits to the named field inside the changelist.
// Uses username as the name for the cursor.
var recordEdits = function(input, name, changelist, username) {
  input._lastValue = input.value;
  input._cursor = {
    pos: input.selectionStart,
    length: input.selectionEnd-input.selectionStart
  }; 

  getEventNames(input).forEach(function(n) {
    input.addEventListener(n, recordEdit(name, changelist, username), false);
  });
};

// Get the list of event names for the element.
var getEventNames = function(elem) {
  var a = Object.getOwnPropertyNames(elem).join(" ").match(/\bon\S+/g).join(" ").replace(/\bon/g, '').split(" ");
  // Take out touch events as Mobile Safari
  // doesn't like touch listeners on textareas inside iframes.
  a = a.filter(function(s) { return !(/^(touch|gesture)/).test(s); });
  return a;
};

// Makes an event listener to record edits.
var recordEdit = function(name, changelist, username) {
  return function(ev) {
    // Update cursor position.
    var cursor = {
      pos: this.selectionStart,
      length: this.selectionEnd-this.selectionStart
    };

    // The value has changed. Let's record the change.
    if (this.value !== this._lastValue) {

      // Hack to handle autocorrect edits.
      if (cursor.pos - this._cursor.pos > 1 && this._cursor.length === 0) {
        this._cursor.length = cursor.pos - this._cursor.pos;
      }

      // Handle selection replacements.
      // Triggers when you've got something selected and you
      // either type something or paste something.
      if (this._cursor.length > 0) {
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: this._cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {del: this._cursor.length}});
      }

      // How much the length of the value has changed.
      // A positive value indicates that text insertion.
      // A negative value means that you've deleted text.
      var d = (this.value.length-this._lastValue.length+this._cursor.length);

      if (d > 0) {
        // Create a text insertion change.
        // Note that we insert the text from the 
        // previous cursor position. The current cursor position
        // is after the inserted text.
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: this._cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {add: this.value.substr(this._cursor.pos, d)}});
      } else if (d < 0) {
        // Create a text deletion change.
        ChangeList.addChange(changelist, {edit: name, value: {cursor: {id: username, pos: cursor.pos}}});
        ChangeList.addChange(changelist, {edit: name, value: {del: -d}});
      }
      this._lastValue = this.value;
    }
    this._cursor = cursor;
  };
};

Ok, so it's a bit hacky. And it probably doesn't work all that well on IE. Perusing the code for ShareJS, it had a comment about IE converting \n linebreaks into \r\n linebreaks. Which would screw up cursor positions compared to other browsers.

Enough about hooking up input events. The other thing I got kinda working are writes based on a log table. Usually you'd need to have a document lock to do writes reliably. Because you need to transform new events based on events that arrived from other clients. So you can't insert new changes directly into the changelist, but need to read in tail = changelist[newChanges.lastSeenVersion..-1], then rebase the newChanges on top of the tail and push the transformed changes to the changelist. Which means that you want to lock changelist during tail read, transform and transform push. Otherwise you might get other changes in before the push and your transform goes FUBAR.

But hey, if you have an atomic push, you could do this: record the lastSeenVersion for the newChanges and push it into the changelist without transformation. Then change the changelist execution function so that it transforms the changes that have lastSeenVersion set. That way the result stays the same compared to pre-transforming the changes, though it'll cost you some performance. Not to worry though, you transform the newChanges and atomically replace the non-transformed version with the transformed version. Zing! Now the changelist results remain consistent even if other writers push more junk on top of the changelist while you're transforming.


2013-08-19

Algebra with compass and straightedge

Thought: could you use a compass and a straightedge to do basic math?

Let's see. First we need to define a couple of things. Like zero. Let's use a zero-length point as the zero. Draw a long straight line, put a mark on it somewhere in the middle. There's your zero and line of numbers.

How to represent numbers? Line segments, right? Take the ruler and draw a few short lines. You can move the short lines to your line of numbers using the compass. Measure line with the compass, move the compass to the line, make a mark with the other end, there you go. Our numbers are lines that are on the number line.

With that, we can add positive numbers. Suppose you have three lines: A, B and C. To add them together, you'd first copy A to the number line, then B starting at one end of A and C at one end of B. The resulting long line is the three lines added together.

To get a proper group going, we're going to need a way to negate lines. So, let's add a direction to the lines. Put a short line A on the number line with one end at zero. Jot a small arrowhead at the other end. Now you can negate A by flipping it around so that the arrow points in the opposite direction. A + -A would go from zero to A, then all the way back to zero. To draw A and -A, first move A to start at zero, then rotate the compass 180 degrees and make a mark on the other side of zero. That's -A.

To add these arrows together, we need to add a rule. You need to attach the non-arrow start of a line to the arrowhead of the previous line. And the result of addition can be represented as a single arrow, going from the start of the first line to be added with the arrowhead at the arrowhead of the last line.

Ok, we have numbers and their negations. We can add lines and subtract lines. And they seem to obey associativity A + (B + C) = (A + B) + C and commutativity A + B = B + A. The addition operator requires us to define A as any arrow pointing to the same direction as A and that has the same length as A. Other group axioms, A + 0 = A seems to be ok, ditto for A + -A = 0.

Right, I think we have an additive group. How about multiplication?

You can multiply two of these vectors together by doing the addition but then rotating the second arrow by 90 degrees. Then add the first vector after the second, rotate it, and repeat once more for the second vector. Now you have a rectangle. The area of the rectangle is the result of the multiplication.

Now wait a minute, how do you convert that into a vector on the number line? It's an area, a completely new dimension, totally different unit from the number line segments. Right. Well, maybe this is not the kind of multiplication we really want. Let's try to find something else.

Ok, first, define one. It's some vector. Probably pretty short. Or maybe long. It's arbitrary. So we have our one.

Let's draw a multiplication line. It's just a long straight line. Jot a zero mark on there, copy the one-vector on the line. Now draw another one-vector at the end of the previous one, but rotated 90 degrees. Draw a dotted line from the zero mark to the end of the second one. There we go, 1 multiplied by 1. Is 1.

Now take some other lines, say 4 and 5. The 4-line is 4 times longer than the one-line. And the 5-line 5 times. Multiply 4 by 5. Draw the 4-line in the place of the second one-line. So that it's standing up, one unit away from zero. Then draw a line from zero through the end of the 4-line. Right, that's the line that multiplies numbers by 4. When it's one distant from zero, it's 4 units up. When the distance is two, it's 8 units up. And so on.

Now copy the 5-line on the multiplication line. And draw a normal to the multiplication line through the end of the 5-line. This is the line that multiplies numbers by 5. Where the 4-multiplier line and the 5-multiplier line cross, there's the result. The normal vector from the multiplication line to the result point is the number 4 times 5. To convert it into a number line number, rotate it 90 degrees so that it's flat on the number line.

Division is, well, there's a trick to it. You want to create the number 1/A. So let's do the multiplication line thing again. This time, draw an upright one-vector A units away from zero. Draw a line from zero through the end of that vector. Then draw a normal line one unit away from zero. The crossing point of those two lines is 1/A.

2013-08-14

Quick thought on Hyperloop

Hyperloop basics (or my understanding)

A lightweight car resting on an air cushion, propelled along a low-pressure tube by track-mounted linear motors. The car counteracts the air piling up in front of the vehicle by pumping it to the rear with a compressor

Low air pressure and air cushion make for low friction, so one linear motor can slingshot the vehicle for a hundred klick glide. The vehicle has batteries and electric motors to pump air, power the cabin and control the air bearing to maintain distance from the tube walls.

Thought experiment

Speed of sound in air is primarily determined by the square root of air temperature. If you fill the tube with hot air, the speed of sound inside the tube goes up. In 1000 C air you can do subsonic travel at 750 m/s. Go for 2200 C and it's 1000 m/s, or Mach 3 in normal atmosphere.

The thermal conductivity of air has a linear relation to its density: at 0.1% density thermal conductivity is also 0.1%. So, if you can cool the tube material and the vehicle to counter a 1 C temperature increase at normal air density, that cooling would suffice to counter 1000 C at 0.1% density.

But heat moves from cold to hot. If the air temperature is 1000 C, you can cool the vehicle by heating a part of it above 1000 C. Alternatively, you could use a thermal buffer to soak up the heat during brief hot air stints, and release the heat when transferring to a slow & cold part of the loop.

2013-08-13

Writing an Operational Transformation library

Recently I've been indulging myself in that most noble of endeavours, re-implementing existing technology for no good reason. The object in this matter: Operational Transformations. A.k.a. the thing that you can use to make multi-user-editable documents.

The concept is simple: record the user actions on the client, send them to the server, the server merges them into the document and sends the resulting changes out to other clients. The implementation is, as I have had the pleasure to discover, not quite as simple.

Sure, maintaining the list of changes, that part is easy. Have an array for the event log, push changes that come from the client into the log, send back the events that happened since the client's last synced version.

ChangeList = function() {
  this.log = [];
  this.version = 0;
  this.newChanges = [];
  this.snapshots = {};
};

ChangeList.prototype.add = function(event) {
  this.newChanges.push(event);
};

ChangeList.prototype.addNewChanges = function(newChanges) {
  this.log.push({version: this.version++, changes: newChanges});
};

ChangeList.prototype.changesSince = function(version) {
  var log = this.log, i = this.log.length - 1;
  while (i >= 0 && log[i].version > version) {
    i--;
  }
  return log.slice(i+1);
};

ChangeList.prototype.sync = function(cl) {
  var changes = this.changesSince(cl.version);
  var newChanges = cl.newChanges.splice(0);
  this.normalize(changes, newChanges);
  this.addNewChanges(newChanges);
  for (var i=0; i<changes.length; i++) { 
    cl.log.push(changes[i]);
  }
  cl.version = this.version;
};

ChangeList.prototype.normalize = function(prevChanges, newChanges) {
  // Tweak newChanges according to prevChanges.
};

The problems start when you have to implement the normalize method. For operations that are associative and commutative, it's simple: you don't have to do anything. (1+2)+3 = (3+1)+2 and so forth, the order of the operations doesn't matter. Likewise for idempotent operations: abs(x) = abs(abs(x)).

The troublesome ones are the operations where the order does matter. For example, (1+0)*2 != (2*0)+1. Or, say, editing text. The raison d'être of this whole library. It being one of the complex cases does make life difficult for the poor implementer.

How does one represent text editing operations anyhow? You should at least have one operation that writes to some point in the text. And another that erases what you have written. It would also be nice to keep track of the cursor position and preserve local sanity.

Imagine that you're stuck in the middle of a sentence, trying to think up the exact word to use. At the same time, Joe Danger is hammering his keyboard at full steam on the page above you, chronicling his daring exploits in forgotten jungles and deadly deserts. The truly excellent thing for your cursor to do would be to stay there, stuck in the middle of the sentence, blinking lazily away without a worry in the world. As Joe's tale of adventure and peril grows, it should push your sentence and your cursor forward at the same pace.

ChangeList.prototype.normalizeString = function(prevChanges, newChanges) {
  var i,j,k;
  var cursors = {};
  for (i=0; i<prevChanges.length; i++) {
    var changes = prevChanges[i].changes;
    for (j=0; j<changes.length; j++) {

      // Find all text-editing ops in prevChanges.
      var cmd = changes[j];
      var edit = (cmd.write || cmd.erase);
      if (edit) {
        var pos = edit.pos;
        var move = edit.value.length || -edit.value;

        // Adjust text-editing ops and cursors in newChanges accordingly.
        for (k=0; k<newChanges.length; k++) {
          var ncmd = newChanges[k];
          var nedit = ncmd.cursor || ncmd.write || ncmd.erase;
          if (nedit.pos > pos) {

            // Move new ops that come after the edit.
            nedit.pos = Math.max(pos, nedit.pos+move);

          }
        }

      }

    }
  }
};

Alright, now your local space make senses, even if the text elsewhere is in a state of flux. I think we're getting somewhere. Oh wait, how do you get the final text out? All we have now is a list of changes. A list of changes is completely useless unless you can execute it.

To execute the changelist, we should go through the changes and replay them. For that we need an initial state and a way to apply changes to it. In functional programming parlance, foldl applyChange initialState changes. In JavaScript, pretty much the same.

ChangeList.prototype.execString = function() {
  var snapshot = this.snapshots.string;
  if (!snapshot) {
    snapshot = {value: '', version: 0};
  }

  // Execute changes on top of the snapshot.
  var initialState = snapshot.value;
  var changes = this.changesSince(snapshot.version);

  var result = initialState;
  for (var i=0; i<changes.length; i++) {
    result = this.applyStringChanges(result, changes[i]);
  }

  // Update the snapshot to the latest synced state.
  this.snapshots.string = {value: result, version: this.version};

  // Apply unsynced changes to get the final result.
  return this.applyStringChanges(result, {version: -1, changes: this.newChanges});
};

ChangeList.prototype.applyStringChanges = function(state, changeList) {
  var i, changes = changeList.changes;
  for (i=0; i<changes.length; i++) {
    var ch = changes[i];

    if (ch.write) {
      state = state.slice(0, ch.write.pos)
          .concat(ch.write.value, state.slice(ch.write.pos));

    } else if (ch.erase) {
      state = state.slice(0, ch.erase.pos)
          .concat(state.slice(ch.erase.pos + ch.erase.value));
    }
  }
  return state;
};

Hooray! String playback is in! Now the easy part is over! I haven't yet made textareas emit string change objects and maintain cursor state. I believe that it will be full of Bad Times fighting browser incompatibilities and APIs. But who knows, it might be simple as well. Excited to find out!

The OO-like implementation above was written solely for this post, if you want to get the slightly nutty tested version with JSON editing, here's a gist. I'll put up a proper GitHub repo once I manage to sync the edits with clientside editors and prove that it actually works.

Thanks for reading, have a cookie. 🍪

Blog Archive