Thunking semantics of :=

9 views
Skip to first unread message

Autrijus Tang

unread,
Apr 23, 2005, 6:51:04 AM4/23/05
to perl6-l...@perl.org
Greetings. In implementing :=, I have discovered two different
set of semantics in explantations. I will refer them as "linking" and
"thunking".

The "linking" semantic is akin to hard links in filesystems.
It takes the storage location in the RHS and binds its to the
name in the LHS:

$x := $x; # no-op
($x, $y) := ($y, $x); # swap

The "thunking" semantic is akin to symbolic links in filesystems.
It takes the expression in RHS and wraps it in an implicit closure,
then give that closure a name to be triggered later.
A12 has an example:

$endpos := $string.chars; # thunk, changes as $string changes

Now, those two semantics directly clash when the RHS can be
interpreted both ways. One good example would be array dereference:

my ($x, @a);
$x := @a[-1];
@a = (1..100);
say $x;

Under the linking semantic, there is no location in RHS to bind yet.
One possible interpretation is just autovivify it -- but [-1] is not
autovivifiable, so it should throw out an fatal exception under the
linking semantic right there. Under the thunking semantic, of course,
it will work as expected.

Assuming the thunking semantics however, I am not too sure about how
this can possibly work:

($x, $y) := ($y, $x); # swap?

One interpretation is that the RHS pad bindings are snapshotted,
so future calls to $x always evaluates the bound "$y" at the RHS
context, and hence give correct results. This would mean:

my ($x, @a);
$x := @a[0];
@a := ($x, $x, $x);
$x := 1;
say @a; # (undef, undef, undef)

Okay, that looks good to me. Should I go ahead and implement
the thunking semantics?

Thanks,
/Autrijus/

Juerd

unread,
Apr 23, 2005, 7:35:29 AM4/23/05
to Autrijus Tang, perl6-l...@perl.org
Autrijus Tang skribis 2005-04-23 18:51 (+0800):

> Now, those two semantics directly clash when the RHS can be
> interpreted both ways.

Not if methods for attributes like .chars promise to always return the
same variable, which would make even more sense if they were lvalue
methods. They can be put to use, like

.chars = 5; # truncate or pad

or they can be made read-only lvalues, as is a numeric literal:

$foo := 5;
$foo++; # error.

> Under the linking semantic, there is no location in RHS to bind yet.
> One possible interpretation is just autovivify it -- but [-1] is not
> autovivifiable, so it should throw out an fatal exception under the
> linking semantic right there. Under the thunking semantic, of course,
> it will work as expected.

But when do you do when the index is non-literal?

$foo := @bar[$bar];

Does this work like creating an lvalue closure { @bar[$bar] } and
calling it, does it bind to the @bar with $bar as it was at the moment
of binding?

Is it true that every thunking thing is essentially a compile time
bind, and linking(aliasing) is a runtime thing? If so, can the semantics
each have their own operator? :=, ::=. I don't know if this makes any
sense, but that has something to do with me never understanding the
purpose of ::=.


Juerd
--
http://convolution.nl/maak_juerd_blij.html
http://convolution.nl/make_juerd_happy.html
http://convolution.nl/gajigu_juerd_n.html

Ingo Blechschmidt

unread,
Apr 23, 2005, 7:05:51 AM4/23/05
to perl6-l...@perl.org
Hi,

Autrijus Tang wrote:
> my ($x, @a);
> $x := @a[0];
> @a := ($x, $x, $x);
> $x := 1;
> say @a; # (undef, undef, undef)

hm, I'd expect @a to be (1, 1, 1) (WE = when evaluated):
my ($x, @a); # $x is undef WE, @a is () WE
$x := @a[0]; # $x is undef WE, @a is () WE
@a := ($x, $x, $x); # $x is undef WE, @a is (undef, undef, undef) WE
# But those "undef"s are bound to @a[0] --
# @a := (@a[0], @a[0], @a[0]);
$x := 1; # $x is 1 WE, @a[0] is 1 WE
say @a; # (1, 1, 1)


And:
my ($x, @a); # $x is undef WE, @a is () WE
$x := @a[0]; # $x is undef WE, @a is () WE
@a = ($x, $x, $x); # $x is undef WE, @a is (undef, undef, undef) WE
# Those "undef"s are real undefs
$x := 1; # $x is 1 WE, @a[0] is 1 WE
say @a; # (1, undef, undef)


Opinions?


--Ingo

--
Linux, the choice of a GNU | To understand recursion, you must first
generation on a dual AMD | understand recursion.
Athlon! |

Larry Wall

unread,
Apr 23, 2005, 1:21:56 PM4/23/05
to perl6-l...@perl.org
On Sat, Apr 23, 2005 at 06:51:04PM +0800, Autrijus Tang wrote:
: Greetings. In implementing :=, I have discovered two different

: set of semantics in explantations. I will refer them as "linking" and
: "thunking".

Congratulations--you've rediscovered "call by ref" and "call by name",
but computer scientists tend to associate those concepts with calls
for some reason. :-)

In fact, the name "thunk" was invented for Algol, because it did
call-by-name, and was widely reviled for its inability to swap
two parameters. Nevertheless, computer scientists liked the
"definitionalness" of call-by-name, and have used it to write
pseudocode for years. It's hard to implement efficiently, but it
does let you defer some decisions about lvalueness.

: The "linking" semantic is akin to hard links in filesystems.


: It takes the storage location in the RHS and binds its to the
: name in the LHS:
:
: $x := $x; # no-op
: ($x, $y) := ($y, $x); # swap
:
: The "thunking" semantic is akin to symbolic links in filesystems.
: It takes the expression in RHS and wraps it in an implicit closure,
: then give that closure a name to be triggered later.
: A12 has an example:
:
: $endpos := $string.chars; # thunk, changes as $string changes

As Juerd pointed out, a ref to an lvalue works just as well to track
changes. The := operator is intended to use hard linking semantics.

: Now, those two semantics directly clash when the RHS can be


: interpreted both ways. One good example would be array dereference:
:
: my ($x, @a);
: $x := @a[-1];
: @a = (1..100);
: say $x;
:
: Under the linking semantic, there is no location in RHS to bind yet.
: One possible interpretation is just autovivify it -- but [-1] is not
: autovivifiable, so it should throw out an fatal exception under the
: linking semantic right there. Under the thunking semantic, of course,
: it will work as expected.

I would prefer the exception.

: Assuming the thunking semantics however, I am not too sure about how


: this can possibly work:
:
: ($x, $y) := ($y, $x); # swap?
:
: One interpretation is that the RHS pad bindings are snapshotted,
: so future calls to $x always evaluates the bound "$y" at the RHS
: context, and hence give correct results. This would mean:
:
: my ($x, @a);
: $x := @a[0];
: @a := ($x, $x, $x);
: $x := 1;
: say @a; # (undef, undef, undef)
:
: Okay, that looks good to me. Should I go ahead and implement
: the thunking semantics?

No, I think just treat the RHS as a context that says: "Give me
an lvalue if you can, otherwise give me an rvalue". One of the
motivations for making {...} always return a closure is so that it
would be really easy to specify a thunk when you really want one.
But the flip side of that is we want to discourage implicit thunking
in favor of explicit thunking. One benefit of that is that we give
the optimizer more information about the intent of the programmer.
It will be better for efficiency if we don't have to clone a bunch
of closures unnecessarily.

We could make some kind of ruling that binding closures to a container
gives that closure the ability to proxy for the container if you use
the container as something other than a closure. But there are
probably inconsistencies in that approach, unless we only allow
such binding to containers that could not be used directly as a
a closure reference. Have to think about that some more.

Larry

Autrijus Tang

unread,
Apr 23, 2005, 3:47:42 PM4/23/05
to perl6-l...@perl.org
On Sat, Apr 23, 2005 at 10:21:56AM -0700, Larry Wall wrote:
> : Now, those two semantics directly clash when the RHS can be
> : interpreted both ways. One good example would be array dereference:
> :
> : my ($x, @a);
> : $x := @a[-1];
> : @a = (1..100);
> : say $x;
> :
> : Under the linking semantic, there is no location in RHS to bind yet.
> : One possible interpretation is just autovivify it -- but [-1] is not
> : autovivifiable, so it should throw out an fatal exception under the
> : linking semantic right there. Under the thunking semantic, of course,
> : it will work as expected.
>
> I would prefer the exception.

Alright. I wish I had seen this mail earlier -- because I just
implemented the call-by-name semantics with snapshotting of RHS pad.

Oh well. At least the same code can be salvaged to make iThreads
and serializable continuations work.

So, hm. What does this do?

my ($x, @a);
$x := @a[0]; # vivified or not?


@a = (1..100);
say $x;

Thanks,
/Autrijus/

Autrijus Tang

unread,
Apr 23, 2005, 3:58:25 PM4/23/05
to Juerd, Autrijus Tang, perl6-l...@perl.org
On Sat, Apr 23, 2005 at 09:50:26PM +0200, Juerd wrote:
> Autrijus Tang skribis 2005-04-24 3:47 (+0800):

> > $x := @a[0]; # vivified or not?
>
> Vivified, because you're taking a reference (not at language level) and
> you can't have a reference (at internal level) pointing to something
> that doesn't exist. At language level, you can, but only symbolically.

Okay. Implemented as r2260, with full call-by-value semantics as
defined by Larry's previous post. `bindings.t` passes under either
semantics, as expected.

Please sanity-check the following:

pugs> my ($x, @a); $x := @a[-1]; $x = 3; @a
*** Error: Modification of non-creatable array value attempted

pugs> my ($x, @a); $x := @a[0]<x>[1]<y>; $x = 3; @a[0]<x>[1]<y>
3

pugs> my ($x, @a); $x := +@a; $x = 3
*** Error: Can't modify constant item

Thanks,
/Autrijus/

Juerd

unread,
Apr 23, 2005, 3:50:26 PM4/23/05
to Autrijus Tang, perl6-l...@perl.org
Autrijus Tang skribis 2005-04-24 3:47 (+0800):
> $x := @a[0]; # vivified or not?

Vivified, because you're taking a reference (not at language level) and


you can't have a reference (at internal level) pointing to something
that doesn't exist. At language level, you can, but only symbolically.

Juerd

unread,
Apr 23, 2005, 4:07:05 PM4/23/05
to Autrijus Tang, perl6-l...@perl.org
Autrijus Tang skribis 2005-04-24 3:58 (+0800):

> Please sanity-check the following:
> pugs> my ($x, @a); $x := @a[-1]; $x = 3; @a
> *** Error: Modification of non-creatable array value attempted

Pass. (For reference: The error is in the second statement.)

> pugs> my ($x, @a); $x := @a[0]<x>[1]<y>; $x = 3; @a[0]<x>[1]<y>
> 3

Pass.

> pugs> my ($x, @a); $x := +@a; $x = 3
> *** Error: Can't modify constant item

Pass, provided that +@a (@a.elems) is rvalue. If it's lvalue, then @a
should grow to 3 elements instead.

Larry Wall

unread,
Apr 23, 2005, 4:41:21 PM4/23/05
to perl6-l...@perl.org
On Sat, Apr 23, 2005 at 10:07:05PM +0200, Juerd wrote:
: Autrijus Tang skribis 2005-04-24 3:58 (+0800):

: > Please sanity-check the following:
: > pugs> my ($x, @a); $x := @a[-1]; $x = 3; @a
: > *** Error: Modification of non-creatable array value attempted
:
: Pass. (For reference: The error is in the second statement.)
:
: > pugs> my ($x, @a); $x := @a[0]<x>[1]<y>; $x = 3; @a[0]<x>[1]<y>
: > 3
:
: Pass.
:
: > pugs> my ($x, @a); $x := +@a; $x = 3
: > *** Error: Can't modify constant item
:
: Pass, provided that +@a (@a.elems) is rvalue. If it's lvalue, then @a
: should grow to 3 elements instead.

rvalue, I think. Extending an array should probably be a special method,
though we might allow

@a.elems = 3;

or some such.

Larry

Nigel Sandever

unread,
Apr 23, 2005, 11:37:23 PM4/23/05
to perl6-l...@perl.org
On Sun, 24 Apr 2005 03:47:42 +0800, autr...@autrijus.org (Autrijus Tang) wrote:
>
> Oh well. At least the same code can be salvaged to make iThreads

Please. No iThreads behaviour in Perl 6.

Nobody uses them and whilst stable, the implementation is broken in so many way.

But worse, the underlying semantics are completely and utterly wrong.


Larry Wall

unread,
Apr 24, 2005, 12:00:11 AM4/24/05
to perl6-l...@perl.org
On Sun, Apr 24, 2005 at 03:37:23AM +0000, Nigel Sandever wrote:

Are you confusing iThreads with pThreads? Or are you recommending we
go back to the pThreads fiasco?

From what I've read, the trend in most modern implementations of
concurrency is away from shared state by default, essentially because
shared memory simply doesn't scale up well enough in hardware, and
coordinating shared state is not terribly efficient without shared
memory. If you are claiming that modern computer scientists are
completely and utterly wrong in moving that direction, well, that's
your privilege. But you should be prepared for a little pushback
on that subject, especially as you are merely badmouthing something
without goodmouthing something else in it's place.

Larry

Nigel Sandever

unread,
Apr 24, 2005, 3:51:31 AM4/24/05
to perl6-l...@perl.org
On Sat, 23 Apr 2005 21:00:11 -0700, la...@wall.org (Larry Wall) wrote:
> On Sun, Apr 24, 2005 at 03:37:23AM +0000, Nigel Sandever wrote:
> : On Sun, 24 Apr 2005 03:47:42 +0800, autr...@autrijus.org (Autrijus Tang)
wrote:
> : >
> : > Oh well. At least the same code can be salvaged to make iThreads
> :
> : Please. No iThreads behaviour in Perl 6.
> :
> : Nobody uses them and whilst stable, the implementation is broken in so many
way.
> :
> : But worse, the underlying semantics are completely and utterly wrong.
>
> Are you confusing iThreads with pThreads? Or are you recommending we
> go back to the pThreads fiasco?
>

I certainly am not advocating a shared-by-default, or everything-shared model.

>
> From what I've read, the trend in most modern implementations of
> concurrency is away from shared state by default, essentially because
> shared memory simply doesn't scale up well enough in hardware, and
> coordinating shared state is not terribly efficient without shared
> memory. If you are claiming that modern computer scientists are
> completely and utterly wrong in moving that direction, well, that's
> your privilege. But you should be prepared for a little pushback
> on that subject, especially as you are merely badmouthing something
> without goodmouthing something else in it's place.
>

When I said "iThreads", I was referring to the only defenition I can find for
iThreads, the Perl 5.8.x implementation.

The "broken underlying semantics" are

1) The fork-like, "duplicate-everything-in-the-process-at-the-point-of-spawn".

This makes spawning a thread heavier than starting a process in many cases. It
makes using (the p5 implementation of) iThreads an exercise in frustration
trying to avoid the semantics it imposes.

2) The shared-memory is really multiple-copies-with-ties.

This removes 90% of the benefits of shared-memory, whilst doing nothing to make
it easier to use. The user is still responsible for locking and synchronisation,
but looses the ability to use either ties or object-semantics to encapsulate it.
That forces every programmer to re-invent the techniques in every program as it
is nearly impossible to write clean, effcient apis and put them into modules.

The duplication and tied-updates makes using shared memory so slow and clumsy,
that it can be quicker to freeze/transmit-via-socket/thaw shared data between
processes, than to share a piece of memory within a process.

3) Using the low-level pthreads api as the basis for the user view of threading.

This precludes the use of native thread features on any platform that has
extended or better api, and forces the programmer to deal with the ultra-low-
level at which that API is defined without any of the control that he would have
if using it directly.

> Larry

njs.

Aaron Sherman

unread,
Apr 24, 2005, 1:29:04 PM4/24/05
to Nigel Sandever, Perl6 Language List
On Sun, 2005-04-24 at 07:51 +0000, Nigel Sandever wrote:
> On Sat, 23 Apr 2005 21:00:11 -0700, la...@wall.org (Larry Wall) wrote:

> > From what I've read, the trend in most modern implementations of
> > concurrency is away from shared state by default, essentially because
> > shared memory simply doesn't scale up well enough in hardware, and
> > coordinating shared state is not terribly efficient without shared
> > memory.

Keep in mind that, these considerations aside, Parrot is implementing an
interpreter-per-thread model, so much of the debate for P6-on-Parrot is
moot.

http://groups-beta.google.com/group/perl.perl6.internals/msg/18b86bff49cac5a0?dmode=source
We'd decided that each thread has its own interpreter. Parrot
doesn't get any lighter-weight than an interpreter, since trying
to have multiple threads of control share an interpreter seems
to be a good way to die a horrible death.
-Dan Sugalski / 14 Apr 2005

> When I said "iThreads", I was referring to the only defenition I can find for
> iThreads, the Perl 5.8.x implementation.
>
> The "broken underlying semantics" are
>
> 1) The fork-like, "duplicate-everything-in-the-process-at-the-point-of-spawn".
>
> This makes spawning a thread heavier than starting a process in many cases. It
> makes using (the p5 implementation of) iThreads an exercise in frustration
> trying to avoid the semantics it imposes.

Keep in mind that for Parrot, this won't be as big a deal. It will mean
that thread-creation will probably stomp all over the gains in
performance that the JIT gives you, but that irons itself out over time
(so again, long-lived threads are more efficient than short-lived ones).

> 2) The shared-memory is really multiple-copies-with-ties.
>
> This removes 90% of the benefits of shared-memory, whilst doing nothing to make
> it easier to use.

Again, given Parrot this is not as big a deal. "tying" is just a matter
of adding vtable entries, and one layer of PMC indirection is not a huge
hit.

It does mean that shared access to low-level types (int, str, etc) will
preclude their being implemented as truly low-level types (i.e. they
will be PMCs, not int, str, etc. in Parrot). However, I can't really
imagine a sane shared-access scheme that would not take this hit.

> That forces every programmer to re-invent the techniques in every program as it
> is nearly impossible to write clean, effcient apis and put them into modules.

Again, I think letting Parrot (or whatever underlies your given P6
implementation) do a lot of this work for you allows you, once again, to
do the right thing.

> The duplication and tied-updates makes using shared memory so slow and clumsy,
> that it can be quicker to freeze/transmit-via-socket/thaw shared data between
> processes, than to share a piece of memory within a process.

Again, I doubt you'll see the same behavior on top of Parrot. Then
again, this is arm-waving, and I don't know what state threading is in
in the Parrot world.

> 3) Using the low-level pthreads api as the basis for the user view of threading.
>
> This precludes the use of native thread features on any platform that has
> extended or better api, and forces the programmer to deal with the ultra-low-
> level at which that API is defined without any of the control that he would have
> if using it directly.

Hopefully we can abstract that away a bit, and presumably you could
always write a Parrot module to provide some native semantics for
threading, but that would require some deep Parrot spelunking.


Reply all
Reply to author
Forward
0 new messages