Junctions - feedback and desires
Terrence Brannon
meeting last night
http://www.hcoop.net/~terry/perl/talks/p6-junctions/index.html
and two questions/desires came out of it:
1: will it be possible to know which element of a junction is
currently being used? E.g.:
my @first_set = qw(1 1);
my @new_set = qw(1 1.4 1 1 8 1 1 1 0.8);
my $any_new_set = any(@new_set);
my $any_first_set = any(@first_set);
if ( (abs($any_first_set - $any_new_set)) > 0.5) {
"a variation in the readings is too large".say;
printf "we we examining %d and %d when it happened",
$any_new_set.current, $any_first_set.current ; # desired feature
}
2: Unless the array of values can be specified lazily, it will not be
practical to use Perl 6 Junctions on large datasets. For example I
might like to be able to specify a sub ref/closure whose execution yields a
new array value or undef when no more values. I.e.:
sub mynext {
my($age) = $sth->fetchrow_array;
$age
}
my $junction = any(\&mynext) ;
3: Do junctions short circuit? I.e., whenever the condition is met,
does it continue immediately. Using the example from point #1, can we assume
that the body of the "then" branch will fire when 8 of @new_set is
encountered?
Rod Adams
>I gave a talk on Perl 6 Junctions at the Thousand Oaks Perl Mongers
>meeting last night
>
> http://www.hcoop.net/~terry/perl/talks/p6-junctions/index.html
>
>and two questions/desires came out of it:
>
>1: will it be possible to know which element of a junction is
>currently being used? E.g.:
>
>my @first_set = qw(1 1);
>my @new_set = qw(1 1.4 1 1 8 1 1 1 0.8);
>
>my $any_new_set = any(@new_set);
>my $any_first_set = any(@first_set);
>
>if ( (abs($any_first_set - $any_new_set)) > 0.5) {
> "a variation in the readings is too large".say;
> printf "we we examining %d and %d when it happened",
> $any_new_set.current, $any_first_set.current ; # desired feature
>
>}
>
I do not believe that is possible.
This is the "filtering" or "unification" behavior that people keep
wanting junctions to have, which they do not.
A given junction always has all of the values it was made with. No more,
no less. If you want something else, you have to make a new junction.
Consider that it's been decided that :
$j = 11|0;
10 < $j < 1
Is true. $j retains the 0 even after the 0 failed a test.
As for the "current" value, there is only a current value during
threading. In this example, the threading is fully contained in C<
(abs($any_first_set - $any_new_set)) > 0.5 >. By the time the printf
comes, the threading is long past.
If you wish to change the behavior, you're welcome to put out some
proposals. But I'll warn you from experience that Damian is rather
stubborn about the current behavior. =)
>
>2: Unless the array of values can be specified lazily, it will not be
>practical to use Perl 6 Junctions on large datasets. For example I
>might like to be able to specify a sub ref/closure whose execution yields a
>new array value or undef when no more values. I.e.:
>
>sub mynext {
> my($age) = $sth->fetchrow_array;
> $age
>}
>
>my $junction = any(\&mynext) ;
>
>
You now have a junction whose only value is a coderef.
I do not believe that you can create a 'lazy junction'. But I don't
recall the topic coming up before, so we'll have to wait for Damian to
come back unless someone else knows for certain.
>3: Do junctions short circuit? I.e., whenever the condition is met,
>does it continue immediately. Using the example from point #1, can we assume
>that the body of the "then" branch will fire when 8 of @new_set is
>encountered?
>
>
Yes, they short circuit.
However, your second statement might be a bit misleading. When the 8 is
encountered, the evaluation of the junctions terminates, and then
processing moves on to the next statement, in this case the say. What
you said might be construed as the junctions were still being threaded
when the the say and printf occurred.
HTH,
-- Rod Adams
Sam Vilain
> I do not believe that is possible.
> This is the "filtering" or "unification" behavior that people keep
> wanting junctions to have, which they do not.
Aww! But what about all the great problems that could be expressed
with them? I know of two languages that consider this to be a core
feature now (Prolog, Oz[1]).
> A given junction always has all of the values it was made with. No more,
> no less. If you want something else, you have to make a new junction.
> Consider that it's been decided that :
>
> $j = 11|0;
> 10 < $j < 1
>
> Is true. $j retains the 0 even after the 0 failed a test.
I can't see how this can be possible with the possibility of
autothreading as described in [2]. Maybe the example you suggest is
true, if both comparisons happen "simultaneously", but what about this
one?
if ($j < 10) {
if ($j < 1) {
say "$j took on two values at once";
}
}
Let's say that the implementation chose to implement the first if() by
auto-threading. The first thread where $j == 11 succeeds. The second,
where $j == 1 fails. In the second thread, $j == 11 fails.
It is by this assumption that the example in [3] was built.
But wait, isn't (10 < $j < 1) likely to produce the same opcode tree
as if($j<10){if($j<1){}} ?
> As for the "current" value, there is only a current value during
> threading.
Isn't the threading conceptual, and actual threading invoked only when
the optimiser has finished using available logic / set theory operations
to prevent absurd numbers of threads being made that exit immediately?
Sam.
References:
1. http://xrl.us/fehh (Link to www.mozart-oz.org)
A representation of send+more=money in Oz
2. http://dev.perl.org/perl6/synopsis/S09.html
Some contexts, such as boolean contexts, have special rules for dealing
with junctions. In any scalar context not expecting a junction of values,
a junction produces automatic parallelization of the algorithm. In
particular, if a junction is used as an argument to any routine (operator,
closure, method, etc.), and the scalar parameter you are attempting to
bind the argument to is inconsistent with the Junction type, that
routine is "autothreaded", meaning the routine will be called
automatically as many times as necessary to process the individual scalar
elements of the junction in parallel.
3. An implementation of send+more=money using Perl 6 Junctions
http://svn.openfoundry.org/pugs/examples/sendmoremoney.p6
http://xrl.us/feis (revision at time of writing this message)
Dave Whipp
> I do not believe that you can create a 'lazy junction'. But I don't
> recall the topic coming up before, so we'll have to wait for Damian to
> come back unless someone else knows for certain.
My understanding is that all lists are conceptually lazy. "any(2..Inf)"
is perfectly valid.
Rod Adams
The list being fed into the junction can be lazy. But I believe that the
list gets iterated over completely in the creation of the junction, so
C< any(2..Inf) > is valid, but melts your processor similar to C< sort
2..Inf >.
My impression has been that after the creation of a junction, the values
that junction has are set in stone. Allowing some form of lazy list to
add values at will seems a bit counter to me. But if @Cabal think it's
okay to have lazy junctions, I won't argue with them.
-- Rod Adams
Rod Adams
> Rod Adams wrote:
>
>> I do not believe that is possible.
>> This is the "filtering" or "unification" behavior that people keep
>> wanting junctions to have, which they do not.
>
>
> Aww! But what about all the great problems that could be expressed
> with them? I know of two languages that consider this to be a core
> feature now (Prolog, Oz[1]).
I'm not disputing that it would be powerful. I'm simply saying that as
currently defined, junctions do not behave in this fashion. It also does
not make a lot of sense to filter out restricting values in a none()
junction.
And as one who recently proposed a way of getting Prolog like features
in Perl (through Rules, not Junctions), I understand the appeal
completely. Junctions are not the way to that goal. They are something
different.
>
>> A given junction always has all of the values it was made with. No
>> more, no less. If you want something else, you have to make a new
>> junction. Consider that it's been decided that :
>>
>> $j = 11|0;
>> 10 < $j < 1
>>
>> Is true. $j retains the 0 even after the 0 failed a test.
>
>
> I can't see how this can be possible with the possibility of
> autothreading as described in [2].
because it gets interpreted as:
10 < $j < 1
--> (10 < $j) && ($j < 1)
--> (10 < any(0, 11)) && (any(0, 11) < 1)
--> any(10 < 0, 10 < 11) && any(0 < 1, 11 < 1)
--> any(false, true) && any(true, false)
--> true && true
--> true.
> Maybe the example you suggest is
> true, if both comparisons happen "simultaneously", but what about this
> one?
>
> if ($j < 10) {
> if ($j < 1) {
> say "$j took on two values at once";
> }
> }
The C<say> would occur, even with the first condition as C< $j > 10 >,
as you likely intended it to be.
Taking multiple values at once is what junctions are all about.
People seem to forget the role the predicate plays in junction
evaluation. You thread over the different values, gain a result, and
then use the predicate to recombine the results into a single scalar.
If instead I had said:
$j = 11 & 0;
10 < $j < 1
it would be false, because C< all( true, false) > is false.
$j itself never changes. It is always a collection of values with a
predicate. If you wish to have a junction with different values in it,
you have to create a new one.
>
> Let's say that the implementation chose to implement the first if() by
> auto-threading. The first thread where $j == 11 succeeds. The second,
> where $j == 1 fails. In the second thread, $j == 11 fails.
Except that the threadings are indendent of each other.
$j = any(0,11);
$j != $j;
is true.
$j != $j
--> any(0,11) != any(0,11)
--> any(0 != any(0,11), 11 != any(0,11))
--> any(any(0 != 0, 0 != 11), any(11 != 0, 11 != 11))
--> any(any(false, true), any(true, false))
--> any(true, true)
--> true
Similarly:
$j = all(0,11);
$j == $j;
is false.
>
> It is by this assumption that the example in [3] was built.
That assumption is in err, and the example does not generate the
solutions desired
See my response to it in
http://www.nntp.perl.org/group/perl.perl6.language/19428
>
> But wait, isn't (10 < $j < 1) likely to produce the same opcode tree
> as if($j<10){if($j<1){}} ?
Well
if 10 < $j < 1 { ... }
if 10 < $j { if $j < 1 { ... }}
Could easily wind up with the same opcodes. Unless the optimizer saw
something in the first one where it could prove C< $j < 1 > is false.
>
> > As for the "current" value, there is only a current value during
> > threading.
>
> Isn't the threading conceptual, and actual threading invoked only when
> the optimiser has finished using available logic / set theory operations
> to prevent absurd numbers of threads being made that exit immediately?
The optimizer can skip threading over values that it can prove will not
affect the outcome. That's short circuiting.
But asking the optimizer to know in advance what is absurd is a tall order.
Even without junctions, someone could make $j an object with an
overloaded set of compare operators against Num. And there's no way for
the compiler to know if those operators are consistent and transitive.
(One could hope they were, but you never know).
I would not call the threading conceptual. It's a very real thing.
> 2. http://dev.perl.org/perl6/synopsis/S09.html
>
> Some contexts, such as boolean contexts, have special rules for dealing
> with junctions. In any scalar context not expecting a junction of values,
> a junction produces automatic parallelization of the algorithm. In
> particular, if a junction is used as an argument to any routine
> (operator,
> closure, method, etc.), and the scalar parameter you are attempting to
> bind the argument to is inconsistent with the Junction type, that
> routine is "autothreaded", meaning the routine will be called
> automatically as many times as necessary to process the individual scalar
> elements of the junction in parallel.
In the cases above, the routine being threaded over is the comparison
operator, not the surrounding code block that contains it.
-- Rod Adams
Uri Guttman
>>
>> My understanding is that all lists are conceptually
>> lazy. "any(2..Inf)" is perfectly valid.
>>
>>
RA> The list being fed into the junction can be lazy. But I believe that
RA> the list gets iterated over completely in the creation of the
RA> junction, so C< any(2..Inf) > is valid, but melts your processor
RA> similar to C< sort 2..Inf >.
i was under the impression that junctions could be smart about ranges
like that and do it correctly. sort can't possibly handle that but some
junctions and ranges would work fine. it isn't hard to convert that
(with the proper boolean) to a boolean expression internally.
RA> My impression has been that after the creation of a junction, the
RA> values that junction has are set in stone. Allowing some form of lazy
RA> list to add values at will seems a bit counter to me. But if @Cabal
RA> think it's okay to have lazy junctions, I won't argue with them.
lazy only when you can actually cheat IMO.
uri
--
Uri Guttman ------ u...@stemsystems.com -------- http://www.stemsystems.com
--Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
Luke Palmer
> Dave Whipp wrote:
>
> >Rod Adams wrote:
> >
> >>I do not believe that you can create a 'lazy junction'. But I don't
> >>recall the topic coming up before, so we'll have to wait for Damian
> >>to come back unless someone else knows for certain.
> >
> >
> >My understanding is that all lists are conceptually lazy.
> >"any(2..Inf)" is perfectly valid.
> >
> >
> The list being fed into the junction can be lazy. But I believe that
> the list gets iterated over completely in the creation of the
> junction, so C< any(2..Inf) > is valid, but melts your processor
> similar to C< sort 2..Inf >.
Well, if we guarantee that .states never returns two of the same value,
then of course you can not call .states on an infinite junction.
And indeed, while it's possible to do this (taking the range to be an
arbitrary infinite list):
if any(2...) > 100 {...}
You'll melt if you do this:
if any(2...) < 2 {...}
We could make junctions smart about ranges, so that the latter can just
fail, but I argue that we can only do it well in the simplest of cases.
It's probably better not to allow infinite ranges in junctions.
On the other hand, if we give junctions well-defined semantics in terms
of their underlying lists (such as orderedness), then lazy junctions may
be just fine. There's a lot you can do with lazy lists, and there are a
lot of very nice idioms having to do with junctions, and I'd like to
find a way to make those two things not be mutually exclusive.
Luke
Sam Vilain
> And as one who recently proposed a way of getting Prolog like features
> in Perl (through Rules, not Junctions), I understand the appeal
> completely. Junctions are not the way to that goal. They are something
> different.
> People seem to forget the role the predicate plays in junction
> evaluation. You thread over the different values, gain a result, and
> then use the predicate to recombine the results into a single scalar.
> solutions desired
I've changed examples/sendmoremoney.p6 in the pugs distribution to use
junctions correctly to demonstrate that they *can* be used to solve these
sorts of problems, and that it is just a matter of semantics and writing
code correctly.
However, poor semantics can make the task of writing optimisers
unnecessarily difficult or impractical, as Bourne demonstrated.
in short, it seems people want this:
my $a = any(1..9);
my $b = any(1..9);
my $c = any(0..9);
if ( $a != $b && $b != $c && $a != $c &&
($a + $b == $a * 10 + $c) ) {
print "$a + $b = $a$c";
}
To mean this (forgive the duplication of collapse() here):
sub collapse($x, $sub) { $sub.($x) }
sub collapse($x, $y, $sub) { $sub.($x,$y) }
my $a = any(1..9);
my $b = any(1..9);
my $c = any(0..9);
collapse($a, $b, -> $a, $b {
($a != $b) &&
collapse($c, -> $c {
if ( ( $b != $c ) && ( $a != $c ) &&
($a + $b == $a * 10 + $c) ) {
say "$a + $b = $a$c";
}
});
});
(and YES THAT WORKS <g>).
However, the former keeps the optimisation out of the algorithm, so that
when someone comes along later with a nice grunty optimiser there is more
chance that it gets a go at the entire solution space rather than having
to fall back to exhaustive searching.
(which might have to find ways to prove associativity of &&, etc, to make
`real' optimisations).
I'm trying to see a way that these two ways of using junctions are
compatible. As I see it, people want to stretch out the time that the
junction is "true", to something non-zero, without having to explicitly
create all those closures.
Getting the old behaviour would be easy, just set a variable in the `if'
clause:
my $j1 = any(1..5);
my $j2 = any(5..9);
my $they_equal;
if ($j1 == $j2) {
# intersection of sets - $j1 and $j2 are any(5), any(5)
$they_equal = 1;
} else {
# symmetric difference of sets - $j1 and $j2 are now
# any(1..5), any(5..9) (where $j1 != $j2 :))
}
if ($they_equal) {
}
Now, the `where $j1 != $j2' bit there, which looks like it's on crack, is
a way of representing that instead of actually calling that second branch
24 times, it could be calling it with two junctions which are `entangled'
(or, if you prefer, `outer joined'). $j1 and $j2 appear almost untouched
- except any test that uses $j1 and $j2 together will not see the
combination of ($j1 == 5) and ($j2 == 5).
I mean, wouldn't it really be nice if you could write stuff like this:
my @users is persistent("users.isam");
my @accounts is persistent("accounts.isam");
my $r_user = any(@user);
my $r_account = any(@account);
if ( $r_account.user == $r_user ) {
say("That junction is:", $r_user);
}
$r_user at that point represents only the users which have at least one
object in @accounts for which there exists an $r_account with a `user'
property that is that $r_user member[*].
The closure would then either be run once, with $r_user still a junction
(if the interpreter/`persistent' class was capable of doing so), or once
for every matching tuple of ($r_account, $r_user). We're still talking in
terms of Set Theory, right?
One last thing - that comment about any(@foo) == one(@foo) not
checking for uniqueness in a list is right - the correct version
is:
all(@foo) == one(@foo)
Sam.
Footnotes:
* - any relational database `experts' who want to remind me of which
normalisation form rules this breaks, please remember that RDBMSes
and normalised forms approximate Set Theory, which this is trying to
do as well, so I believe such discussion is irrelevant.
Rod Adams
>Rod Adams <r...@rodadams.net> wrote:
>
>
>
>>Well
>> if 10 < $j < 1 { ... }
>> if 10 < $j { if $j < 1 { ... }}
>>
>>
>>Could easily wind up with the same opcodes.
>>
>>
>
>No. In the first case $j is evaluated just once. In the second case it's
>evaluated twice.
>
>
You're right. I just dived through the archives and found that chained
operators are an exception. Sorry for missing that.
Which can be a mess explaining to someone how
if 0 < $x && $x < 10 {...}
can be true when
if 0 < $x < 10 {...}
is false.
Though I suppose if we can extend this to a general rule of "if it only
appears once, it can only be threaded once", it makes a certain amount
of sense.
-- Rod Adams
Larry Wall
useful. After all, that's what the whole universe runs on. But most
mortals will want the classical view to be the default, so we'll
require some kind of explicit markup or pragma if you want to extend
entanglement further out than comparisons. That's why junctions can't
be passed into a function unless the function specifically allows it,
for instance. (Then there's the matter of sneaky return values.)
The only alternative is to autothread every conditional, and I don't
think we'd survive the lynch mobs if we did that. Maybe there's some
middle ground here that I don't see, but if so, I don't see it. And if
I don't see it, all the other Pooh bears will have trouble with it too.
Larry
Luke Palmer
The collapsing behavior of Quantum::Entanglement (and what is being
expressed as wanted here) is actually a sort of parallel logic
programming. Instead of trying and backtracking, it's just doing it all
at once.
Instead of providing a collpasing junction type which will confuse the
heck out of people, I think it's best to concentrate on how we will
integrate logic programming in the language. And the best way to
concentrate on that at this point might be not to think about it at all.
But junctions might be our ticket into the world of logic programming.
We'd have to change them, but there are some amazing parallels between
what junctions currently do and what regexes do (regexes even use the
same symbols) and what my "Argument Patterns" proposal does with
junctive types, which are both logical programming frameworks.
So let's put it in the back of our minds. It's going to be in the front
of mine for the day, but I might not come up with anything.
Luke
Rod Adams
Yes, it does work, given the current state of autothreading.
Well, you'd need a C< use junctions; > in order to store a junction in a
variable. And I'm not certain if that changes the autothreading behavior
of the closures or not. You might have to declare the collapses as:
multi sub collapse ($x is none(Junction), $sub) {...};
multi sub collapse ($x is none(Junction), $y is none(Junction),
$sub) {...};
to get it to thread correctly. I'm not sure. (Pretty sure you'd need the
'multi' in there).
It's also a perfect example of where my hyperthreader operator (it
hasn't been nailed down yet what the exact syntax is (or even if it
exists), I'm waiting for Damian to get back to continue that thread.) is
a better tool than junctions. Assuming we use my »« syntax,
SEND+MORE==MONEY could be written as:
sub test ($s, $e, $n, $d, $m, $o, $r, $y) {
if "$s$e$n$d" + "$m$o$r$e" == "$m$o$n$e$y" &&
all($s,$e,$n,$d,$m,$o,$r,$y) == one($s,$e,$n,$d,$m,$o,$r,$y)
{
say "$s$e$n$d + $m$o$r$e == $m$o$n$e$y";
}
}
test(»1..9«, »0..9«, »0..9«, »0..9«, »1..9«, »0..9«, »0..9«, »0..9«);
Using Damian's every() syntax, the last line becomes:
test(every(1..9), every(0..9), every(0..9), every(0..9),
every(1..9), every(0..9), every(0..9), every(0..9));
It's extremely brute force and inefficient, but it works.
I have the philosophical problem with your use of junctions in this
context due to the fact that you are completely ignoring the predicate
of the junction. The C< all(...) == one(...) > is an excellent use of
junctions, that makes use of the predicates when the junctions are
evaluated. If you want threading without the predicate, I give you the
hyperthreader (well, I'm trying to).
I'll also point out that what you wrote above is a lot more readable as:
for 1..9 -> $a {
for 1..9 -> $b {
next unless $b == none($a);
for 0..9 -> $c {
next unless $c == none($a, $b);
if $a + $b == $a * 10 + $c {
say "$a + $b = $a$c"
}
}
}
}
>
> I mean, wouldn't it really be nice if you could write stuff like this:
>
> my @users is persistent("users.isam");
> my @accounts is persistent("accounts.isam");
>
> my $r_user = any(@user);
> my $r_account = any(@account);
>
> if ( $r_account.user == $r_user ) {
> say("That junction is:", $r_user);
> }
I'm fairly certain that I'll be writing a Set class if no one beats me
to it.
use Sets;
my @users is persistent("users.isam");
my @accounts is persistent("accounts.isam");
my $s_validusers = set(@accounts».user) - @users;
for values $s_validusers -> $user {
say "$user is a valid user";
}
>
> $r_user at that point represents only the users which have at least one
> object in @accounts for which there exists an $r_account with a `user'
> property that is that $r_user member[*].
>
> The closure would then either be run once, with $r_user still a junction
> (if the interpreter/`persistent' class was capable of doing so), or once
> for every matching tuple of ($r_account, $r_user). We're still
> talking in
> terms of Set Theory, right?
If you want Set Theory.. use Sets. Or use some form of Logical
Programming which builds the sets implicitly for you, and does all the
filtering and backtracking you're asking for.
Both topics have been explored recently. The results of that exploration
can be summarized as:
- Sets would make a nifty module to have around.
- Integrating Logical Programming into Perl needs a lot more thought and
effort than will likely happen before 6.0.0. Modules grafting LP into
Perl and/or Parrot are welcome.
-- Rod Adams
Thomas Sandlaß
> I have the philosophical problem with your use of junctions in this
> context due to the fact that you are completely ignoring the predicate
> of the junction. The C< all(...) == one(...) > is an excellent use of
YES, and much clearer than when this test is buried under code
that has to be written if you only have simple tests and boolean
connectives.
> junctions, that makes use of the predicates when the junctions are
> evaluated. If you want threading without the predicate, I give you the
> hyperthreader (well, I'm trying to).
I fully agree to this. I interpret the junctions as "oracle values":
the predicate is used to properly address them when you ask e.g. "is
any of your values greater than 10?". You shouldn't assume an inner
structure. And as Rod points out, many examples are using the inner
structure and the auto-threading while *ignoring* the predicate.
Regards,
--
TSa (Thomas Sandlaß)