generic swap method in javascript

T

Thomas 'PointedEars' Lahn

Lasse said:
Dmitry A. Soshnikov said:
Lasse said:
The pattern
[x,y] = [e1,e2];
should be detectable at compile time, so the introduction of the
intermediate array can be optimized away.

Moreover, it can be done syntactically without brackets, as in Python:

No, it can't. Check your assumptions.
I'd prefer that.

The two of you are missing the ambiguity here which prevents that from
working as intended in JavaScript already. That is _not_ a destructuring
assignment in ECMAScript implementations: it is evaluating x, assigning e1
to y, and evaluating e2. Changing the semantics here would break a lot of
existing scripts, and is therefore not going to happen.
Or
(x,y) = (e1,e2); // except it's ambiguous with the stupid comma
operator.

That is why it should not be specified or implemented so; the LHS must
evaluate to y, and the RHS must evaluate to e2. The Mozilla people
(Brendan Eich?) picked the sensible way to provide this feature already.
But then, I think any modern type system should have arbitrary tuples.

But thanks to the comma operator, that syntax would not be backwards
compatible in ECMAScript implementations. It is highly doubtful that it
would be implemented so. So we will probably have to live with Array
initializers als tuple replacement.
Heck, I've seen languages with a swap primitive :)
x :=: y;

I cannot say I like that a lot either. I also do not think it is a pattern
useful often enough for it to deserve any special syntax; I have not used it
in production code for a decade or so, thanks to efficient built-in sort
implementations. The use of the destructuring assignment here is more of a
happy coincidence; the feature was designed for extracting elements from
Arrays instead.


PointedEars
 
E

Evertjan.

Dmitry A. Soshnikov wrote on 16 jun 2010 in comp.lang.javascript:
Swapping without "third" can be done with simple arithmetic operations:

A = A - B
B = A + B
A = B - A

Many many years ago,
on a microprocessor called 2650,
there was an assembler opcode called:

swab

... some programmers over here thought
this was the native spelling of swap.

However it ment "swap registers a and b"
 
T

Tim Streater

Evertjan. said:
Dmitry A. Soshnikov wrote on 16 jun 2010 in comp.lang.javascript:


Many many years ago,
on a microprocessor called 2650,
there was an assembler opcode called:

swab

.. some programmers over here thought
this was the native spelling of swap.

However it ment "swap registers a and b"

Was it not "swap bytes" on an operand in the PDP-11? So you might say:

swab R3 or swab (SP)

for example to swap the bytes in register 3 or the top item on the stack.
 
R

rf

Evertjan. said:
Dmitry A. Soshnikov wrote on 16 jun 2010 in comp.lang.javascript:


Many many years ago,
on a microprocessor called 2650,

Hey, I had one of those. On a development board so one could solder stuff
like expansion ports and an extra K of memory onto it.

Great fun :)

Can't remember much of the assembly language though after 35 years, except
that it was a bloody whole lot different to the IBM System 360 Assembler I
was then currently being employed to churn out line by tedious line.
 
E

Evertjan.

rf wrote on 17 jun 2010 in comp.lang.javascript:
Hey, I had one of those. On a development board so one could solder
stuff like expansion ports and an extra K of memory onto it.

Great fun :)

Can't remember much of the assembly language though after 35 years,

I bought 64 kiloBytes of memory from the States by post-order for 1000
guilders, then about $ 400 ?, while mainframe IBM memory was about $
100.000 for the same amount.

We could marvel doing a register exor "XOR0" with itself, sparing an extra
processor cycle from setting 000000 in the same register, speed mattered in
that era.
except that it was a bloody whole lot different to the IBM System 360
Assembler I was then currently being employed to churn out line by
tedious line.

Philips had programmed a 2650 cross-assembler on the 360 btw.
 
D

Dmitry A. Soshnikov

Dmitry A. Soshnikov wrote on 16 jun 2010 in comp.lang.javascript:


Many many years ago,
on a microprocessor called 2650,
there was an assembler opcode called:

swab

.. some programmers over here thought
this was the native spelling of swap.

However it ment "swap registers a and b"

Oh, didn't know; historically interesting, thanks.

Dmitry.
 
R

Richard Cornford

Function calls don't necessarily have to create any objects.
Most function calls can be handled by just putting the
arguments on the stack and using them from there.

It is possible for - foo = [bar, bar = foo][0]; - to be optimised by a
complier such that no array object is ever created. The thing that
makes such an optimisation unlikely is that the construct is not that
common and javascript compliers need to be able to work quickly at
delivering an executable and so don't have much time to spend looking
at uncommon constructs to see if they could be optimised.
Which itself implies the creation of very temporary objects.

The pattern
[x,y] = [e1,e2];
should be detectable at compile time, so the introduction of the
intermediate array can be optimized away.

Can be, but still the behaviour is specified in terms of objects being
created.
If the deconstructing assignment is introduced, it's likely to
be used exactly for swapping variable values, and then I'll bet
that optimization will be made.

Probably. This reminds me of the pre-ES5 discussions on -
Object.defineProperty - where it was suggested that the property
defining process could be heavily optimised to get rid of all of the
implied object creation. That is fine if you are using object literals
as the 'attributes' argument, but it seems likely that it will be
common to want to define numerous properties with identical property
descriptors. In that case it would seem like a good idea to create a
single object and pass it to multiple call to - Object.defineProperty
-, while it may actually be more efficient to write (copy-paste)
identical object literals for the 'attributes' argument for each call,
if an optimisation exists to treat that construct as syntax rather
than just a method call.

Richard.
 
V

VK

We could marvel doing a register exor "XOR0" with itself, sparing an extra
processor cycle from setting 000000 in the same register, speed mattered in
that era.

EX (SP),HL ;;EX - from EXchange obviously
;;ZX Spectrum, Zilog Z80
;;my sweet youthhood :)
 
V

VK

To summarize the main discussion on the OP question about a generic
swap method in JavaScript:
http://groups.google.com/group/comp.lang.javascript/msg/d4920b7b20b920a7

The language and DOM interface specifics imply three distinct
situations for swapping values and it currently eliminates the
possibility of having a separate polymorphic method (function)
covering all of three together. Such situations are:

1. Swap stay-alone primitive values, thus primitive values which are
not property of any JavaScript object other than Global itself.

2. Swap property values of two JavaScript objects.

3. Swap elements of HTMLCollection (DOM0) or NodeList (DOM1 and
higher). Such collections normally do not allow direct assignments to
their members so specific DOM methods usage will be needed.


1.Swap stay-alone primitive values, thus primitive values
which are not property of any JavaScript object other
than Global itself

JavaScript functions receive primitives by value and there is no
keyword/flag to alter it to by reference pass. Respectively there is
no possibility in JavaScript to make a separate subroutine for stay-
alone primitives swap. The only option remains to use an inline set of
statements for each case. If swapping needs to be done more than once
in the same script it may be suggested to pre-declare the intermediary
variable and use a uniform set of statements, possibly pretty-printed
in a block of statements to make it visually as "functional" as
possible, for instance:

var iswap = null;

// DO other stuff

var v1 = 10;
var v2 = 15;

// swap block:
{
iswap =
v1, v1 = v2, v2 =
iswap
}

Note 1: By using the fact of Global properties reflection in window
host object it is possible to move the code in a separate subroutine
and to pass arguments as identifier literals:

var v1 = 10;
var v2 = 15;

swap('v1', 'v2');

function swap(a, b) {
var tmp = self[a];
self[a] = self;
self = tmp;
}

This approach doesn't seep too convenient or flexible but still should
be mentioned for situations where window host object is presented.

Note 2: By using the destructuring assignment introduced in JavaScript
1.7 and currently supported on newest Gecko platforms it is possible
to use a shorter syntax like

var v1 = 10;
var v2 = 15;

[v1, v2] = [v2, v1];

See also: https://developer.mozilla.org/en/new_in_javascript_1.7
The use of destructuring assignments eliminates the necessity of an
intermediary variable but possibly introduces additional objects
creation: therefore the possible productivity gain remains disputable,
see this thread for details and arguments.

Note 3: If the swapping values are non-negative integers lesser or
equal to OxFFFFFFFF (dec 4294967295) then it is possible to avoid an
intermediary variable by using the XOR swap algorithm:
http://en.wikipedia.org/wiki/XOR_swap
Such approach is much lesser universal and it may break the internal
optimization mechanics, see wiki article and Lasse Reichstein Nielsen
in this thread:
http://groups.google.com/group/comp.lang.javascript/msg/af6f0ec2d576d8c6

End of stay-alone primitives situation. To be continued with two other
situations. Corrections are welcome.
 
D

Dmitry A. Soshnikov

"Dmitry A. Soshnikov"<[email protected]> writes:

Example:
function foo(a,b) { return a + b; }
This function doesn't contain any closure constructions.
It doesn't access any scoped variables.
It doesn't use the arguments object.
There is nothing preventing an implementation from just reading
parameters off the stack, add them together, and return the
result (on the stack or in a register).

Yeah, logically, yes; I mentioned it the article of closures -- it can
be a general approach in any language -- if a functions do not have free
variables (with possibly analazing the whole chain), then it easily can
put arguments onto stack (or even, yes, registers), rather than use heap
for that, as generally is in languages which supports closures.
The pattern
[x,y] = [e1,e2];
should be detectable at compile time, so the introduction of the
intermediate array can be optimized away.

Moreover, it can be done syntactically without brackets, as in Python:

x, y = e1, e2;

I'd prefer that.
Or
(x,y) = (e1,e2); // except it's ambiguous with the stupid comma operator.

Damn, really, ambiguity. This could be a good question for "quiz" also
(after everybody have learned that comma returns evaluation of its last
operand):

var a = 10, b = 20;

// everybody knows, that
// comma operator returns the
// evaluation of the last operand

20, 10; // 10

a, b // 20, the same, the last

a, b = b, a;

// or even so:

a, b = 20, 10;

console.log(a, b); // 10, 10 ? Nope, still 10, 20 of course ;)

Yes, this syntax (because of backward compats) isn't acceptable for ES;
in contrast with Python.
But then, I think any modern type system should have arbitrary tuples.

Heck, I've seen languages with a swap primitive :)
x :=: y;

Interesting. Yes, why not? A good syntactic sugar, increasing the
abstraction, (even if it will cause some performance penalty) is good.
Try that for strings :)

Yeah, I know sure. Just mentioned thinking about numbers at that time
(with numbers also can be overflow, by the way).
It's generally a bad idea to be "too smart" in a high-level language.
If you do:
int x,y;
...
x^=y;y^=x;x^=y;
to swap integers in, say, C++, then the compiler might not be able to
do as good a job as if it could recognize that you were doing a
swap. It might know low-level tricks for swapping that can't be
expressed directly in the high-level language (like knowing that
both values are in registers at the moment,

I've checked for the interest in the MS Visual Studio, in C++ -- nope,
it either do not know such optimization at all (even if I try to declare
vars as "register", although, the compiler can ignore it) and make full
operations -- as I see in disassembly window. Or make full optimization
removing my simple code with that operations :p Maybe it can be caught
in more complex examples and it will use that "xchg", don't know. For
the interested it possible to disassemble std:swap to see what's going
on in assembler representation. Although, that's just the particular
implementation.
so they can be swapped
by a single xchg instruction (if on x86)).

Yeah, I remember this command, although, I don't use the assembly
language on practice.

Dmitry.
 
D

Dmitry A. Soshnikov

Lasse said:
Dmitry A. Soshnikov said:
Lasse Reichstein Nielsen wrote:
The pattern
[x,y] = [e1,e2];
should be detectable at compile time, so the introduction of the
intermediate array can be optimized away.

Moreover, it can be done syntactically without brackets, as in Python:

No, it can't. Check your assumptions.

Did I say that I assume something? I confirmed. And that assertion was
related to Python. Though, I guess the word "can" made ambiguity. I mean
it "could" be as in Python. But, yeah, because of current implementation
of the comma operator, it (because of backward compats) -- can't.
The two of you are missing the ambiguity here which prevents that from
working as intended in JavaScript already. That is _not_ a destructuring
assignment in ECMAScript implementations: it is evaluating x, assigning e1
to y, and evaluating e2. Changing the semantics here would break a lot of
existing scripts, and is therefore not going to happen.


That is why it should not be specified or implemented so; the LHS must
evaluate to y, and the RHS must evaluate to e2. The Mozilla people
(Brendan Eich?) picked the sensible way to provide this feature already.


But thanks to the comma operator, that syntax would not be backwards
compatible in ECMAScript implementations. It is highly doubtful that it
would be implemented so. So we will probably have to live with Array
initializers als tuple replacement.

Yep.

the feature was designed for extracting elements from
Arrays instead.

Possibly, it's from what is called pattern-matching in more older
languages (such as e.g. Erlang). There, if you want to extract elements
from "something" where "something", one can use that pattern matching:

[A, B] = [1, 2]

A and B will have 1 and 2 respectively. The same:

{Data, {OtherData, AndOther}} = {10, {"test", [1, 2, 3]}} to bind three
variables.

Dmitry.
 
D

Dmitry A. Soshnikov

On 17.06.2010 17:13, Dmitry A. Soshnikov wrote:

There, if you want to extract elements
from "something" where "something",

err, where "something" is _any_ term, but not only array (list). This is
a common ideology, thought, in other languages is presented partly, e.g.
only for arrays. Although, JS 1.7 supports this feature not only for
arrays, but for objects also.

Dmitry.
 
V

VK

(continuation, see http://groups.google.com/group/comp.lang.javascript/msg/a5f99302e2a1c5a5)

2. Swap property values of two JavaScript objects

JavaScript objects are passed to function by reference value (the
"reference value" term is used to disambiguate C-like *reference which
doesn't exist in JavaScript). That allows to make a separate swap
subroutine as long as the property name can be passed as a literal,
for instance:

var jso1 = {'prop1' : 10};
var jso2 = {'prop1' : 15};

swap(jso1, jso2, 'prop1');

function swap(jsobj1, jsobj2, prop) {
var tmp = jsobj1[prop];
jsobj1[prop] = jsobj2[prop];
jsobj2[prop] = tmp;
}

End of property values of two JavaScript objects situation. To be
continued with the last situation. Corrections are welcome.
 
B

Benjamin 'BeRo' Rosseaux

Am 17.06.2010 11:55, schrieb Tim Streater:
Was it not "swap bytes" on an operand in the PDP-11? So you might say:

swab R3 or swab (SP)

for example to swap the bytes in register 3 or the top item on the stack.

Even on x86/x64 does exist a swap opcode instruction called xchg as
shorthand for "exchange", for example

xchg eax,ebx

which swaps the content between the registers eax and ebx.
 
R

Richard Cornford

On 17.06.2010 0:41, Lasse Reichstein Nielsen wrote:


Yeah, I know sure. Just mentioned thinking about numbers at that
time (with numbers also can be overflow, by the way).
<snip>

With javascript's double precision floating point numbers overflows
are possible, but loss of precision seems (much) more likely. Consider
what will happen if A is a number at the upper range of possible
number representations, say 1.0e308 and B is a number close to the
smallest (positive) number, say 5.0e-324. But the numbers don't have
to be as extreme as those:-

var A = 1.0e9;
var B = 1.0e-9;

A = A - B
B = A + B
A = B - A

// A is now zero
// B is now 1000000000

I have a vague recollection of once being shown a 'swapping' algorithm
for signed integers (with no third variable) that used only bitwise
operations to swap the values, avoiding any risk of overflows.
Obviously in javascript that would only be viable for 32 bit integers,
and adding two of those will not overflow the range of integers that
can be represented by an IEEE double precision floating point number.

Richard.
 
V

VK

(continuation, see
http://groups.google.com/group/comp.lang.javascript/msg/a5f99302e2a1c5a5
http://groups.google.com/group/comp.lang.javascript/msg/c90c13f264ada061
)

3. Swap elements of HTMLCollection (DOM0) or NodeList (DOM1 and
higher)

Such collections normally do not allow direct assignments to their
members so specific DOM methods usage will be needed. IE DOM model
provides a proprietary swapNode method:
http://msdn.microsoft.com/en-us/library/ms536774(VS.85).aspx
The W3C DOM model is still missing such method so different voodoo
dances with removeChild/appendChild/etc. are so far needed.
As the native swap method times more effective than any voodoo, first
it should be tried to use it if presented. If not, then the most
simple/effective replacement for init.W3Swap is highly welcome in this
thread.

<!DOCTYPE html>
<html>
<head>
<title>Test</title>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">
<script type="text/javascript">

var swapNodes = null;

function test() {
var pcol = document.getElementsByTagName('P');
swapNodes(pcol, 1, 2);
}

function init() {
swapNodes = (/*@cc_on true || @*/ false) ? init.IESwap : initW3Swap;
test();
}

init.IESwap = function(collection, index1, index2) {
var parentElement = collection.item(0).parentElement;
parentElement.children(index1).
swapNode(
parentElement.children(index2)
);
}

init.W3Swap = function(parentElement, index1, index2) {
// your code goes here
}

</script>
</head>

<body onload="init()">
<p>P1</p>
<p>P2</p>
<p>P3</p>
</body>
</html>

..
 
T

Thomas 'PointedEars' Lahn

Dmitry said:
Lasse said:
:
Lasse Reichstein Nielsen wrote:
The pattern
[x,y] = [e1,e2];
should be detectable at compile time, so the introduction of the
intermediate array can be optimized away.
Moreover, it can be done syntactically without brackets, as in Python:
No, it can't. Check your assumptions.

Did I say that I assume something?

It sure looked so: "... can be done ..., [the same] as in Python".
I confirmed.

OK, that was easy to misunderstand.
the feature was designed for extracting elements from Arrays instead.

Possibly, it's from what is called pattern-matching in more older
languages (such as e.g. Erlang). There, if you want to extract elements
from "something" where "something", one can use that pattern matching:

[A, B] = [1, 2]

A and B will have 1 and 2 respectively. The same:

{Data, {OtherData, AndOther}} = {10, {"test", [1, 2, 3]}} to bind three
variables.

Thanks for the example. It led me to find out that

var [data, [otherData, another]] = [10, ["test", [1, 2, 3]]];

works in JavaScript 1.8.2 (and probably all 1.7+), too (that is,

data === 10
otherData === "test"
another === [1, 2, 3]

afterwards.)


PointedEars
 
D

Dmitry A. Soshnikov

On 17.06.2010 19:05, Thomas 'PointedEars' Lahn wrote:

var [data, [otherData, another]] = [10, ["test", [1, 2, 3]]];

works in JavaScript 1.8.2 (and probably all 1.7+), too (that is,

data === 10
otherData === "test"
another === [1, 2, 3]


Yeah, moreover, pattern matching for objects also works since 1.7 as I see:

let {a: n} = {a: 10};

Thus, `n' becomes 10. It can be useful for shorthands in enumeration of
objects:

for (let {longPropertyName: name, otherProperty: other} in object) {
print(name, other);
}

Dmitry.
 
D

Dmitry A. Soshnikov

<snip>

With javascript's double precision floating point numbers overflows
are possible, but loss of precision seems (much) more likely. Consider
what will happen if A is a number at the upper range of possible
number representations, say 1.0e308 and B is a number close to the
smallest (positive) number, say 5.0e-324. But the numbers don't have
to be as extreme as those:-

var A = 1.0e9;
var B = 1.0e-9;

A = A - B
B = A + B
A = B - A

// A is now zero
// B is now 1000000000

I have a vague recollection of once being shown a 'swapping' algorithm
for signed integers (with no third variable) that used only bitwise
operations to swap the values, avoiding any risk of overflows.
Obviously in javascript that would only be viable for 32 bit integers,
and adding two of those will not overflow the range of integers that
can be represented by an IEEE double precision floating point number.

Yeah, and XOR algorithm won't help also in this case:

A ^= B;
B ^= A;
A ^= B;

// the same
// A is now zero
// B is now 1000000000

Dmitry.
 
D

Dmitry A. Soshnikov

On 17.06.2010 19:19, Dmitry A. Soshnikov wrote:

for (let {longPropertyName: name, otherProperty: other} in object) {
print(name, other);
}

Err (forgot the correct syntax). Should be "for each" and this approach
is better use to iterate an array of objects:

var array = [
{a: 10, b: 20},
{a: 30, b: 40, c: 50}
];

for each (let {a: x, b: y} in array) {
print(x, y);
}

Result:

10, 20
30, 40

Dmitry.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,078
Messages
2,570,570
Members
47,204
Latest member
MalorieSte

Latest Threads

Top