Proof of concept of a trampoline-based promise resolver. This ensures that all promise chains take up the same base amount of stack space.

gistfile1.js

function nextTick(f) {
	setTimeout(function() {
		console.log('tick');
		f();
	});
}

// Minimal amount of Promise groundwork necessary for a proof of concept.
function Promise(then) {
	this.then = then;
}

function fulfilled(value) {
	var p = new Promise(function(onFulfilled) {
		return (typeof onFulfilled === 'function') ? promiseFor(onFulfilled(value)) : p;
	});

	return p;
}

function isPromise(promiseOrValue) {
	return promiseOrValue && typeof promiseOrValue.then === 'function';
}

function promiseFor(promiseOrValue) {
	if (!isPromise(promiseOrValue)) {
		// It's a value, not a promise.  Create a resolved promise for it.
		return fulfilled(promiseOrValue);
	} else if (promiseOrValue instanceof Promise) {
		// It's a when.js promise, so we trust it
		return promiseOrValue;
	}
}

// A trampoline that all promise handlers execute from.
// This ensures that thenning doesn't increase the stack height.
function makeTrampoline() {
	var callstack = [];
	return {
		push: function(f) {
			callstack.push(f);
		},

		process: function() {
			while (callstack.length > 0) {
				console.log("step");
				callstack.pop()();
			}
		}
	};
}

// A basic deferred
function waiting(trampoline) {
	var handlers = [];

	var waiter = {
		then: function(f) {
			var waiter = waiting(trampoline);
			handlers.unshift(function(value) {
				waiter.resolve(f(value));
			});
			return waiter.promise;
		},
		resolve: function(value) {
			handlers.forEach(function(f) {
				trampoline.push(f.bind(undefined, value));
			});
			return waiter.promise;
		},

		promise: null
	};

	waiter.promise = new Promise(waiter.then);

	return waiter;
}

// The "first" deferred in the chain gets a new trampoline.
// When this deferred is resolved, the trampoline should begin processing.
var trampoline = makeTrampoline();

var waiter = waiting(trampoline);
var promise = waiter.promise;

for (var i = 0; i < 100000; ++i) {
	promise = promise.then(function(value) {
		console.log(value);
		return value + 1;
	});
}

waiter.resolve(1);
nextTick(trampoline.process);

Interesting, I think this is similar to the queue impl. Looks good to me, and should handle "infinite" promise chains without blowing the stack. Maybe we're converging on something, which might be a sign that this is a good path to a solution!

I'll update my gist with the changes that attempt to prevent platform tick/timer queue starvation, so you can take a look.