Slurpy nullary vs nonslurpy nullary

After getting Life and Mandel to run on Pugs yesterday (see
http://svn.perl.org/perl6/pugs/trunk/examples/ ), today I've
made this version of Quicksort to run:

use v6;

multi sub quicksort ( ) { () }

multi sub quicksort ( *$x, *@xs ) {
my @pre  = @xs.grep{ $_ < $x };
my @post = @xs.grep{ $_ >= $x };
(@pre.quicksort, $x, @post.quicksort);
}

(1, 5, 2, 4, 3).quicksort.say;

Note the use of @xs.grep{} above.  Pugs currently has two multisub
named "grep":

* List as invocant, takes a Code arg
* Takes two args: Code and List

It sort of makes sense to me.  Please correct me if it's wrong. :)

But anyway.  The real problem is the multisub dispatcher initially
complained about the () signature, saying that it is "non-slurpy"
and may not take a list, even though the list eventually flattens
into an empty list; so I modified the definition to make () explicitly
slurpy.

However, that feels wrong, as I'd like to distinguish from a slurpy
nullnary (something that can take a list, as long as it's empty) and a
non-slurpy nullary (something that takes no arguments whatsoever).

I have been wondering whether something like 

quicksort( *[] ) 

Can mean a slurpy nullnary, but I failed to find relevant text in
Synopses, so here I am. :-)

(PS. Yes, I understand that I can use array unpacking and have
quicksort always take a single array argument, but I'd still like to
inquire about slurpy nullary...)

Thanks,
/Autrijus/

On Fri, Feb 18, 2005 at 04:25:49PM +0800, Autrijus Tang wrote:
: After getting Life and Mandel to run on Pugs yesterday (see
: http://svn.perl.org/perl6/pugs/trunk/examples/ ), today I've
: made this version of Quicksort to run:
:
:     use v6;
:
:     multi sub quicksort ( ) { () }
:
:     multi sub quicksort ( *$x, *@xs ) {
: 	my @pre  = @xs.grep{ $_ < $x };
: 	my @post = @xs.grep{ $_ >= $x };

Just as a BTW, that syntax is illegal currently, since those
curlies would be interpreted as hash subscripts.  Method syntax requires
parens if there are any (non-adverbial) arguments.  So you either need
parens for the argument:

my @pre  = @xs.grep({ $_ < $x });
my @post = @xs.grep({ $_ >= $x });

or pass an adverbial block:

my @pre  = @xs.grep:{ $_ < $x };
my @post = @xs.grep:{ $_ >= $x };

: 	(@pre.quicksort, $x, @post.quicksort);
:     }
:
:     (1, 5, 2, 4, 3).quicksort.say;
:
: Note the use of @xs.grep{} above.  Pugs currently has two multisub
: named "grep":
:
:     * List as invocant, takes a Code arg
:     * Takes two args: Code and List
:
: It sort of makes sense to me.  Please correct me if it's wrong. :)

As long as the first is always called as single dispatch, and the
second as multiple dispatch, there should be no confusion.

: But anyway.  The real problem is the multisub dispatcher initially
: complained about the () signature, saying that it is "non-slurpy"
: and may not take a list, even though the list eventually flattens
: into an empty list; so I modified the definition to make () explicitly
: slurpy.
:
: However, that feels wrong, as I'd like to distinguish from a slurpy
: nullnary (something that can take a list, as long as it's empty) and a
: non-slurpy nullary (something that takes no arguments whatsoever).

Right, it's the anchoring problem--but it's really only a problem for
compile time typing, and documenting your intent.  At run time we know
perfectly well that there are 0 arguments.

: I have been wondering whether something like
:
:     quicksort( *[] )
:
: Can mean a slurpy nullnary, but I failed to find relevant text in
: Synopses, so here I am. :-)

No, that'd mean a single array reference that has to be empty.

: (PS. Yes, I understand that I can use array unpacking and have
: quicksort always take a single array argument, but I'd still like to
: inquire about slurpy nullary...)

If we decide we need to declare non-anchoring intent (and I'm not
convinced we do), then maybe the final (or only) arg of a multi can
be declared as bare * to indicate it's not anchored to the end of
the argument list.  But the () declaration indicates already that
the function will never match a non-null list, and people might take
(*) to mean that it matches a non-null list and throws away the result.
So I think your initial solution is actually the right one from the
viewpoint of the Perl programmer.  If we need to tweak something,
it's perhaps to document the fact that *$x is required to match an argument,
while *@x isn't required to match any arguments at all.  So if you
had

multi sub quicksort ( ) { () }
multi sub quicksort ( *@x ) {

then when dispatching 0 arguments you actually have an ambiguity that
either has to be illegal or solved by ordered matching.  I think
ordered matching is more conducive to a Prolog-like mentality, and
more fail-soft, and slightly righter for Perl.  (But that doesn't say
much about ordering across different modules, does it?)

Larry

On Fri, Feb 18, 2005 at 08:26:26AM -0800, Larry Wall wrote:
> Just as a BTW, that syntax is illegal currently, since those
> curlies would be interpreted as hash subscripts.

Noted.  Which reminds me I need to implement hashes... :)

> : It sort of makes sense to me.  Please correct me if it's wrong. :)
> 
> As long as the first is always called as single dispatch, and the
> second as multiple dispatch, there should be no confusion.

Cool.  I'll see if I can adverbify other builtins, then.

> Right, it's the anchoring problem--but it's really only a problem for
> compile time typing, and documenting your intent.  At run time we know
> perfectly well that there are 0 arguments.

Uhm, yes and no.  Currently, at runtime, I have an "arityMatch"
function that compares all potential multisub matches with the
invocant and arguments; however, different candidate may impose
different contexts on the arguments (slurping == List, nonslurping
== usually Scalar).

A difficulty arises because the expressions used as arguments
is not evaluated when arityMatch is done, and for good reason --
they may do wildly different things depending on its context.

When Pugs was only implementing FP6, I could affort to force
evaluation for each multisub candidate, and see if they yield
values that can match the signature.  However, because now the
expressions may contain "say" statements, I can no longer do that.

As a concrete (not neccessarily correct) example:

multi sub foo ($x, Int $y) returns Num { ... }
multi sub foo ($x, *$a, *$b) returns Str { ... }

sub baz { given want { if (rand > .5) { ... } else { ... } } }

foo( bar(), baz() );

I fail to find a way to statically find out how many values (and what
type of values) baz() will return under "Int" and "List" contexts,
short of actually evaluating it twice.  Hence, the return type of
foo() can't be analyzed in advance because I don't know which foo()
will be invoked.

Currently it is an outstanding problem in Pugs implementation, and
that was the reason why I had to use destructive "=" instead of 
the binding ":=" for @pre and @post.  I'd be delighted to learn of a 
solution to that.

> So I think your initial solution is actually the right one from the
> viewpoint of the Perl programmer.  If we need to tweak something,
> it's perhaps to document the fact that *$x is required to match an argumen
t,
> while *@x isn't required to match any arguments at all.  So if you
> had
> 
>     multi sub quicksort ( ) { () }
>     multi sub quicksort ( *@x ) {
> 
> then when dispatching 0 arguments you actually have an ambiguity that
> either has to be illegal or solved by ordered matching.

In pugs, currently it's ordered by local vs global, then by subtyping
distance of invocants, then finally by then finally by the order of
creation of CODE objects.  That's just a working heuristics, though.

Thanks,
/Autrijus/

On Sat, Feb 19, 2005 at 12:44:49AM +0800, Autrijus Tang wrote:
: On Fri, Feb 18, 2005 at 08:26:26AM -0800, Larry Wall wrote:
: > So I think your initial solution is actually the right one from the
: > viewpoint of the Perl programmer.  If we need to tweak something,
: > it's perhaps to document the fact that *$x is required to match an argum
ent,
: > while *@x isn't required to match any arguments at all.  So if you
: > had
: >
: >     multi sub quicksort ( ) { () }
: >     multi sub quicksort ( *@x ) {
: >
: > then when dispatching 0 arguments you actually have an ambiguity that
: > either has to be illegal or solved by ordered matching.
:
: In pugs, currently it's ordered by local vs global, then by subtyping
: distance of invocants, then finally by then finally by the order of
: creation of CODE objects.  That's just a working heuristics, though.

Well, practically speaking, I think we have to resolve ties in favor
of an explicit default method, or die of ambiguity.  The creation
order of CODE objects is not reliable once you get out of the current
module, and even within a module can be unclear to the programmer once
people start flinging various compile-time blocks and evals around.

Larry

Autrijus wrote:

> A difficulty arises because the expressions used as arguments
> is not evaluated when arityMatch is done, and for good reason --
> they may do wildly different things depending on its context.
>
> When Pugs was only implementing FP6, I could affort to force
> evaluation for each multisub candidate, and see if they yield
> values that can match the signature.  However, because now the
> expressions may contain "say" statements, I can no longer do that.
>
> As a concrete (not neccessarily correct) example:
>
>     multi sub foo ($x, Int $y) returns Num { ... }
>     multi sub foo ($x, *$a, *$b) returns Str { ... }
>
>     sub baz { given want { if (rand > .5) { ... } else { ... } } }
>
>     foo( bar(), baz() );
>
> I fail to find a way to statically find out how many values (and what
> type of values) baz() will return under "Int" and "List" contexts,
> short of actually evaluating it twice.  Hence, the return type of
> foo() can't be analyzed in advance because I don't know which foo()
> will be invoked.

A6 acknowledges this fundamental problem with multiple dispatch:

If Perl can't figure out the signature of a function at compile time
(because, for instance, it's a method and not a function), then it
may not be known which arguments are in scalar or list context at
the time they are evaluated. This doesn't matter for Perl variables,
because in Perl 6, they always return a reference in either scalar
or list context. But if you call a function in such an indeterminate
context, and the function doesn't have a return value declared that
clarifies whether the function behaves differently in scalar or list
context, then one of two things must happen. The function must
either run in an indeterminate context, or the actual call to the
function must be delayed until the context is known. It is not yet
clear which of these approaches is the lesser evil. It may well
depend on whether the function pays more attention to its dynamic
context or to global values. A function with no side effects and no
global or dynamic dependencies can be called whenever we like, but
we're not here to enforce the functional paradigm. Interesting
functions may pay attention to their context, and they may have side
effects such as reading from an input stream in a particular order.

A variant of running in indeterminate context is to simply assume
the function is running in list context. (That is, after all, what
Perl 5 does on methods and on not-yet-declared subroutines.)

Personally, I think the only reasonable way of resolving this is to
assume (as in the last paragraph above) that function calls in these
kinds of indeterminate contexts are always in list context. The logic is
very simple: "We can't resolve its context; it's in an argument list;
ergo it's in list context."

But there should definitely also be a (removable) warning:

Call to baz() in indeterminate context at foo.pl line 42
(did you forget a <== ?)

Propagating indeterminate contexts or deferring subroutine calls complicates
both the semantics and the implementation far more than is necessary for the
marginal benefits likely to be gained.

 

Multiple dispatch ambiguities are always solved by calling the C<is
default> variant, or by throwing an:

Ambiguous call to multiply dispatched quicksort() at foo.pl line 42

exception if no variant C<is default>.


> In pugs, currently it's ordered by local vs global, then by subtyping
> distance of invocants, then finally by then finally by the order of
> creation of CODE objects.  That's just a working heuristics, though.

The dispatch resolution process is described in A12, under "Calling via
Multiple Dispatch". It's close to what you describe above, except the
"local vs global" distinction is a little more complex, and the
final discrimination is via C<is default>, not via C<Code> object
creation sequence.

Damian

On Tue, Feb 22, 2005 at 09:41:54AM +1100, Damian Conway wrote:
> Personally, I think the only reasonable way of resolving this is to
> assume (as in the last paragraph above) that function calls in these
> kinds of indeterminate contexts are always in list context.

So, even if the clash is Num vs Str context, we still run it
under List context?  Or is it their common ancestor, "Scalar"?

On #perl6 Luke half-jokingly suggested running it under Num|Str
context, but that is probably not going to fly. :)

> The dispatch resolution process is described in A12, under "Calling via
> Multiple Dispatch". It's close to what you describe above, except the
> "local vs global" distinction is a little more complex, and the
> final discrimination is via C<is default>, not via C<Code> object
> creation sequence.

Okay, I'll drop the Code creation order thing and make it raise a
fatal error on ambiguity, then.  Thanks!

Thanks,
/Autrijus/

Autrijus wrote:
 
>
> So, even if the clash is Num vs Str context, we still run it
> under List context?  Or is it their common ancestor, "Scalar"?

Yes. When I said "indeterminate contexts" I meant List vs Scalar. After all,
the whole point of multimethods is to cope polymorphically with Num-vs-Str
type clashes.

 
>
> Okay, I'll drop the Code creation order thing and make it raise a
> fatal error on ambiguity, then.

But only if there isn't a variant marked C<is default>.

Damian

On Tue, Feb 22, 2005 at 10:38:04PM +1100, Damian Conway wrote: 
> 
> Yes. When I said "indeterminate contexts" I meant List vs Scalar. After 
> all, the whole point of multimethods is to cope polymorphically with 
> Num-vs-Str type clashes.

In that case, and in light of the "a Pair can always pretend to be
a very small hash", is it possible that a Scalar is a List, similar
to how Array and Hash are both Lists?

List -- Hash
-- Array
-- Scalar

That way the "most common ancestor" rule can be applied without
exceptions.  Am I on crack here? :)

Thanks,
/Autrijus/