Making Array.sort()'s comparator parametric

**Lasse Reichstein Nielsen** · Jul 20 '05, 12:38 PM

Re: Making Array.sort()'s comparator parametric

Christopher Jeris <cjeris@fake.ad dress.us> writes:
[color=blue]
> I have a table with (say) fields f1, f2, f3. I do a database
> query and what I wind up with is a structure Q of arrays:
> Q.f1[n] is field f1 in row n,
> Q.f1.length == Q.f2.length == Q.f3.length is the record count of the query.
> (This representation is of course backwards,[/color]

Hear, hear!
[color=blue]
> but that's what ColdFusion's CFWDDX facility produces, so I'm stuck
> with it.)[/color]

You have my sympathy :)
[color=blue]
> Now I have an array of row-numbers, which is supposed to represent a
> subset of the query I just made:
> A = [3, 6, 7] would represent rows 3, 6, 7 of query Q.[/color]
[color=blue]
> What I want to do is to sort A on a _specific_field _ of the query.[/color]

[color=blue]
> I tried the approach that would be obvious in Lisp:
> function comparator(fiel dname, invert) {
> function compare(m, n) {
> var comparison = Q[fieldname][m] < Q[fieldname][n] ? -1 :
> Q[fieldname][m] > Q[fieldname][n] ? 1 : 0;
> return invert ? -comparison : comparison;
> }
> return compare;
> }[/color]

Perfect. If anything, I would assigne Q[fieldname][m/n] to local
variables so that you don't look it up twice. But that's just
performance, the concept is fine.
[color=blue]
> I expected this _not_ to work since I had thought JavaScript was
> dynamically scoped.[/color]

But it isn't :). Javascript is statically/textually scoped, and
function expressions create closures.

Dynamic scope is one of the things that make me dislike Lisp. I'll
take Scheme over it any day.
[color=blue]
> That is, I had thought something like
>
> var c2 = comparator('f2' , false);
> var fieldname = 'f3';
> A.sort(c2);
>
> would sort A using the wrong order, according to f3 (since 'compare'
> isn't closed over the lexical environment containing 'fieldname').
> But it seems to work correctly. Why does it work -- or does it work
> only superficially?[/color]

It works because Javascript is textually scoped.

What sometimes confuzes is the combination of scope and assignment:

var x = 42;
function foo() {return x;}
x = 37;
alert(foo());

This alerts 37. The foo function declaration does create a closure,
but it is the variable's *location* that is captured, not its current
value. Another example that often gives headaches is:

for (var i=0;i<10;i++) {
setTimeout(func tion(){alert(i) ;},1000);
}

This creates ten functions (or one function ten times, depending on
how the browser optimizes) and schedules them for later
execution. After approximatly one second, all the functions are called.
People often expect this to alert the numbers between 0 and 9, but
in fact it alerts 10 times 10. That is because the closure for the
functions are identical, they all refer to the same *variable*, which
holds the value 10 after the loop ends.

[color=blue]
> (2)
> Another approach I thought of, but which I was unable to get to work,
> is to try making a 'functor' (function object) as in C++:
>
> function compare(m, n) {[/color]
....[color=blue]
> }
> function Comparator(fiel dname, invert) {
> this.fieldname = fieldname;
> this.invert = invert;
> this.compare = compare;
> }
>
> Unfortunately if you then do
>
> var c2 = new Comparator('f2' , false);
> A.sort(c2.compa re);
>
> the result is an error because the reference to 'this.fieldname '
> inside the body of 'compare' does not treat 'this' as 'c2' as I
> intended it to; 'this.fieldname ' is undefined.[/color]

Yes. The argument you send to sort is the pure function. The function
itself doesn't know which object it belongs to as a method (because
really, it doesn't - the object just has a reference to the function,
and the *same* function can be a method of several different objects
at the same time ... as your one compare function is).
[color=blue]
> An alternative strategy would be to try to make the Comparator
> itself applicable, i.e., instead of
> this.compare = compare;
> put
> Comparator.prot otype = compare;
> and then try
> A.sort(c2);
>
> This doesn't work; c2 can't be applied.[/color]

Nope. You are putting the function object as the prototype of your
constructor. However, you then create a new (non-function) object.
So, c2 is not a function, it just has one as a prototype.
[color=blue]
> So, does (1) work, and why or why not?[/color]

Yes, for all the right reasons.
[color=blue]
> And is there a way to make something like (2) work?[/color]

Try either:
---
function Comparator(fiel dname,invert) {
this.fieldname = fieldname;
this.invert = invert;
}
Comparator.prot otype.compare = function (m,n) {
var a = Q[this.fieldname][m];
var b = Q[this.fieldname][n];
var compare = (a<b?-1:b<a?1:0);
return this.invert?-compare:compare ;
}
function makeComparator( fieldname,inver t) {
var comparator = new Comparator(fiel dname,invert)
return function(m,n){r eturn comparator.comp are(m,n);}
}
---
.... i.e., make an object with a method, but store that
object in a closure, or
---
function makeComparator( fieldname,inver t) {
var comparator = function(m,n) {
var fieldname = arguments.calle e.fieldname;
var invert = arguments.calle e.invert;
var a = Q[fieldname][m];
var b = Q[fieldname][n];
return (!invert-invert)*((b<a)-(a<b)); // very short-hand :)
}
comparator.fiel dname = fieldname;
comparator.inve rt = invert;
return comparator;
}
---
.... i.e., store the values directly on the function object (functions are
objects) and access it as arguments.calle e (modern browsers only).

None of these are better than the pure closure based way.

[color=blue]
> Apply (1 6 2 4)(3 7) to domainname to reply.[/color]
You just don't want non-mathmaticians to reply, eh :)
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'

**Richard Cornford** · Jul 20 '05, 12:38 PM

Re: Making Array.sort()'s comparator parametric

"Christophe r Jeris" <cjeris@fake.ad dress.us> wrote in message
news:uad62j4ux. fsf@fake.addres s.us...
<snip>[color=blue]
>(1)
>I tried the approach that would be obvious in Lisp:
>function comparator(fiel dname, invert) {
> function compare(m, n) {
> var comparison = Q[fieldname][m] < Q[fieldname][n] ? -1 :
> Q[fieldname][m] > Q[fieldname][n] ? 1 : 0;
> return invert ? -comparison : comparison;
> }
> return compare;
>}[/color]

When the comparator function is called an "execution context" is entered
and an internal object referred to (in ECMA 262 Section 10.1.3) as the
"variable" object is created and initialised. With comparator
initialisation of the variable object involves creating a property with
the name of each of the formal parameters of the function, assigning the
parameter values to then and then creating a function object with the
inner function definition and assigning a reference to that function to
a property of the "variable" object called "compare". The effect of
returning a reference to the (unique to each invocation of comparator)
inner function from the function call is to preserve the variable object
from the execution context of the call to comparator. This is required
because inner functions can access the parameters and local variables
(effectively any property of the "variable" object) from their outer
function(s) whenever they are subsequently executed.
[color=blue]
>I expected this _not_ to work since I had thought JavaScript was
>dynamically scoped. That is, I had thought something like
>
>var c2 = comparator('f2' , false);
>var fieldname = 'f3';
>A.sort(c2);[/color]

When the comparator function is called an "execution context" is entered
and an internal object referred to (in ECMA 262 Section 10.1.3) as the
"variable" object is created and initialised. With comparator
initialisation of the variable object involves creating a property with
Identifier resolution in the execution context of a call to the inner
function returned by a call to comparator starts with a search of the
"variable" object in its execution context then, because it is an inner
function, the "variable" object from the execution context in which it
was created is searched. So the identifier "fieldname" is resolved as a
property of the "variable" object from the execution context in which
the inner function was created, which has whatever value was passed to
the comparator function as its "fieldname" parameter when it was called
in order to return the inner function.

The scope chin does not come into play at all in the resolution of that
identifier (that would have come next if no corresponding properties of
either variable object had been found) and whether - var fieldname =
'f3' - is an assignment to a local variable in another function or to a
global variable its value cannot be accessed by the inner function at
all.
[color=blue]
>would sort A using the wrong order, according to f3 (since 'compare'
>isn't closed over the lexical environment containing 'fieldname').
>But it seems to work correctly. Why does it work -- or does it work
>only superficially?[/color]

It works, though it could be more efficiently implemented by passing a
reference to an object, say - Q.f2 - as a formal parameter -
fieldObject - and then the inner function could do the comparison on the
members of that object - fieldObject[m] < fieldObject[n] - without the
need to resolve which object member of - Q - to refer to on each (and
every) reference.
[color=blue]
>(2)
>Another approach I thought of, but which I was unable to get to
>work, is to try making a 'functor' (function object) as in C++:
>
>function compare(m, n) {
> var fieldname = this.fieldname;
> var invert = this.invert;
> var comparison = Q[fieldname][m] < Q[fieldname][n] ? -1 :
> Q[fieldname][m] > Q[fieldname][n] ? 1 : 0;
> return invert ? -comparison : comparison;
>}
>function Comparator(fiel dname, invert) {
> this.fieldname = fieldname;
> this.invert = invert;
> this.compare = compare;
>}
>
>Unfortunatel y if you then do
>
> var c2 = new Comparator('f2' , false);
> A.sort(c2.compa re);[/color]

Although - c2.compare - is a property of an object it is a property that
holds a reference to a function object, and that is all that is passed
to the array.prototype .sort method. That function object has no
knowledge of whether, or which, objects hold references to it and when
the function is invoked by the Array.prototype .sort method the function
is just executed as a function (rather than as a method of c2). As a
result the - this - keyword is a reference to the global object and -
this.fieldname - etc do not refer to properties of c2 (It refers to an
undefined global variable).

<snip>[color=blue]
>So, does (1) work, and why or why not?[/color]

Yes, use it.
[color=blue]
>And is there a way to make something like (2) work?[/color]

Probably (you can emulate pretty much anything that can be done in any
other language with JavaScript) but (1) is the better option.

Though you might consider the one-time task of turning the strange
object structure you have into something more conducive to the way in
which you want to use it, rather than assuming that because that is the
form you get it in it is the form you must use.

Richard.

**Richard Cornford** · Jul 20 '05, 12:38 PM

Re: Making Array.sort()'s comparator parametric

"Lasse Reichstein Nielsen" <lrn@hotpop.com > wrote in message
news:8ylmhoj9.f sf@hotpop.com.. .
<snip>[color=blue]
> ---
>function makeComparator( fieldname,inver t) {
> var comparator = function(m,n) {
> var fieldname = arguments.calle e.fieldname;
> var invert = arguments.calle e.invert;
> var a = Q[fieldname][m];
> var b = Q[fieldname][n];
> return (!invert-invert)*((b<a)-(a<b));// very short-hand :)
> }
> comparator.fiel dname = fieldname;
> comparator.inve rt = invert;
> return comparator;
>}
> ---
> ... i.e., store the values directly on the function object
>(functions are objects) and access it as arguments.calle e
>(modern browsers only).[/color]
<snip>

In the above it should be possible to replace -
arguments.calle e.fieldname - with - comparator.fiel dname - as the outer
function local variable is a reference to the function object that is
also arguments.calle e, and that seems to work OK with, for example,
Netscape 4.

Richard.

**Richard Cornford** · Jul 20 '05, 12:38 PM

Re: Making Array.sort()'s comparator parametric

"Richard Cornford" <Richard@litote s.demon.co.uk> wrote in message
news:br34na$ie1 $1$8302bc10@new s.demon.co.uk.. .
<snip>[color=blue][color=green]
>>A.sort(c2);[/color]
>
>When the comparator function is called an "execution context" is
>entered and an internal object referred to (in ECMA 262 Section
>10.1.3) as the "variable" object is created and initialised. With
>comparator initialisation of the variable object involves creating
>a property with[/color]

Hmm. This preceding block of text is a repeat of the start of the
opening paragraph. I don't know how it found its way down here but it
should not be here. This paragraph was intended to start with:-
[color=blue]
>Identifier resolution in the execution context ...[/color]
<snip>

Richard.

**Christopher Jeris** · Jul 20 '05, 12:39 PM

Re: Making Array.sort()'s comparator parametric

Lasse Reichstein Nielsen <lrn@hotpop.com > writes:[color=blue]
> But it isn't :). Javascript is statically/textually scoped, and
> function expressions create closures.[/color]

Thanks very much for your informative response. I can't now
remember what behavior I had observed that made me think Javascript
was dynamically scoped! That's what I get for using "pure thought"
instead of actually reading the manual :)
[color=blue]
> Dynamic scope is one of the things that make me dislike Lisp. I'll
> take Scheme over it any day.[/color]

You must be thinking of Emacs Lisp or some much older Lisps.
Modern Common Lisp has had lexical scope for two decades (although
unlike many languages, it provides dynamically scoped special
variables for the contexts where they're useful).
[color=blue]
> What sometimes confuzes is the combination of scope and assignment:
>
> var x = 42;
> function foo() {return x;}
> x = 37;
> alert(foo());[/color]

Well, this is the same in Scheme:
(let ((x 42))
(let ((foo (lambda () x)))
(set! x 37)
(foo)))
returns 37 as well.
[color=blue]
> for (var i=0;i<10;i++) {
> setTimeout(func tion(){alert(i) ;},1000);
> }[/color]

This took me a little longer to figure out, but I think it would
be the same in Scheme as well, _if_ you used a looping construct
which used the equivalent of set! to mutate the loop index variables
(which 'do' and the conventional Scheme tail-recursion loop do not).

[regarding function-object technique][color=blue]
> None of these are better than the pure closure based way.[/color]

Indeed, if I really can have closures, there's no reason not to
use them.

--
Chris Jeris cjeris@oinvzer. net
Apply (1 6 2 4)(3 7) to domainname to reply.

**Christopher Jeris** · Jul 20 '05, 12:39 PM

Re: Making Array.sort()'s comparator parametric

"Richard Cornford" <Richard@litote s.demon.co.uk> writes:[color=blue]
> [very informative description of scope resolution][/color]

Indeed, this looks pretty close to equivalent to Lisp closures, although
perhaps a little less uniform. I'll have to read that part of the
standard (I was going to say 'reread', but from my misconceptions about
the scope rules it's obvious I never read it in the first place :))
[color=blue]
> Though you might consider the one-time task of turning the strange
> object structure you have into something more conducive to the way in
> which you want to use it, rather than assuming that because that is the
> form you get it in it is the form you must use.[/color]

Well, I hadn't gotten that far yet. The backwardness is not a disaster,
certainly much less bad than not having the closures I thought I didn't
have.

Thank you very much for your informative and helpful reply!

--
Chris Jeris cjeris@oinvzer. net
Apply (1 6 2 4)(3 7) to domainname to reply.

**Douglas Crockford** · Jul 20 '05, 12:39 PM

Re: Making Array.sort()'s comparator parametric

> This took me a little longer to figure out, but I think it would[color=blue]
> be the same in Scheme as well, _if_ you used a looping construct
> which used the equivalent of set! to mutate the loop index variables
> (which 'do' and the conventional Scheme tail-recursion loop do not).[/color]

The correspondence between JavaScript and Scheme is surprisingly close. See
http://www.crockford.com/javascript/little.html. One thing to watch for:
JavaScript implementations do not optimize tail recursion.

Making Array.sort()'s comparator parametric

Making Array.sort()'s comparator parametric

Comment

Comment

Comment

Comment

Comment

Comment

Comment