Re: Patterns
Larry Wall wrote:
Lots of interesting ideas. But I don't think the reverse-test
situation will arise all that frequently. How 'bout we let the user
just say:
my macro statement_control:test { when .accepts: }
or some such...
IIRC, you don't even need .accepts for this. You could just say
given $pattern {
when $a ~~ $_ { ... }
when $b ~~ $_ { ... }
when $c ~~ $_ { ... }
}
...since an explicit smart-match is a boolean expression (it is, isn't
it?), and boolean expressions implicitly smart-match according to
their truth. Right?
--
Jonathan Dataweaver Lang
Re: Patterns
On Sun, Jan 07, 2007 at 03:33:19AM -0800, Jonathan Lang wrote:
: IIRC, you don't even need .accepts for this. You could just say
:
: given $pattern {
:when $a ~~ $_ { ... }
:when $b ~~ $_ { ... }
:when $c ~~ $_ { ... }
: }
:
: ...since an explicit smart-match is a boolean expression (it is, isn't
: it?), and boolean expressions implicitly smart-match according to
: their truth. Right?
Very nearly, except that ~~ merely promises to return something
that can be used as a boolean, not something that is of Bool type.
And, in fact, for a normal regex you'd get a Match object, which as
a form of Capture would then try to compare itself back to $pattern,
which is not what you want. So you'd have to force it:
given $pattern {
when true $a ~~ $_ { ... }
when true $b ~~ $_ { ... }
when true $c ~~ $_ { ... }
}
Larry
Re: Patterns
Larry Wall wrote:
Anyway, that gives us:
given $pattern {
when .accepts(42) {...}
}
which given typical usage patterns of switch statements is probably
adequately huffmanized, unless we want to go for something shorter
than accepts/rejects, like
acc/rej
pix/nix
ok/bogus
...at which point, legibility becomes an issue. .accepts() and
.rejects() seem to work well enough on a case-by-case basis - although
it occurs to me that someone who intends to put the pattern first
within a given/when construct is probably going to want to do so for
every case, or very nearly so:
given $pattern {
when .accepts($a) { ... }
when .accepts($b) { ... }
when .accepts($c) { ... }
when .accepts($d) { ... }
}
It would be nice if there were some way to factor out the .accepts()
in the above code. Maybe something like:
given $pattern {
when $a { ... } # if $a ~~ $pattern { ... ; next }
when $b { ... } # if $b ~~ $pattern { ... ; next }
when $c { ... } # if $c ~~ $pattern { ... ; next }
when $d { ... } # if $d ~~ $pattern { ... ; next }
} is backward;
Although I don't like the fact that you have to wait until reading the
whole block to find out that the cases are being processed inside-out.
--
Would it be possible to put a closure on the left and an argument list
on the right, with the effect being that the closure gets called using
the argument list? This would let you do something like:
given { ^x ~~ $pattern } {
when $a { ... } # if $a ~~ $pattern { ... ; next }
when $b { ... } # if $b ~~ $pattern { ... ; next }
when $c { ... } # if $c ~~ $pattern { ... ; next }
when $d { ... } # if $d ~~ $pattern { ... ; next }
}
or
given { ^x = $number ^y } {
when 1, 2 { ... } $ if 1 = $number 2 { ... ; next }
when 2, 3 { ... } $ if 2 = $number 3 { ... ; next }
}
(Yes, I know that this second case could be handled more flexibly
using right-side Ranges. TIMTOWTDI.)
The main problem that I have with this idea is its rigidity. The
_only_ way that the topic can be used in the above is as a test for
the 'when' clauses; and it messes with the 'when *' idiom. (But then,
any code that follows the final 'when' in a block is already the 'if
all else fails...' code; 'when *' is merely syntactic sugar to
highlight this fact.)
--
It would be nice to have something that is to 'given' as 'loop' is to
'for', letting you specify a topic and a separate case tester up
front:
test $pattern, { $^x ~~ $_ } {
when $a { ... } # if $a ~~ $pattern { ... ; next }
when $b { ... } # if $b ~~ $pattern { ... ; next }
when $c { ... } # if $c ~~ $pattern { ... ; next }
when $d { ... } # if $d ~~ $pattern { ... ; next }
}
Or, to avoid additional keywords, just say that a 'given' statement
with two arguments uses the first argument as its topic and the second
argument as the case tester to replace '{ $_ ~~ $^x }' in 'when'
clauses. Better, use 'when' as is, but introduce a 'test' alternative
that is customized by the second parameter:
given $pattern, { $^x ~~ $_ } {
test $a { ... } # if $a ~~ $pattern { ... ; next }
test $b { ... } # if $b ~~ $pattern { ... ; next }
test $c { ... } # if $c ~~ $pattern { ... ; next }
test $d { ... } # if $d ~~ $pattern { ... ; next }
when * { ... } # if $pattern ~~ * { ... ; next }
}
That way, 'given' and 'when' still behave exactly as currently
described; the case tester only comes into play when you explicitly
ask for it.
--
At this point, though, the case tester is looking like it might be
better as a property of the 'given' block:
given $pattern {
TEST { $^x ~~ $_ }
test $a { ... } # if $a ~~ $pattern { ... ; next }
test $b { ... } # if $b ~~ $pattern { ... ; next }
test $c { ... } # if $c ~~ $pattern { ... ; next }
test $d { ... } # if $d ~~ $pattern { ... ; next }
when * { ... } # if $pattern ~~ * { ... ; next }
}
Or go ahead and let TEST change the behavior of 'when' within the
block, and rely on nested blocks to allow different kinds of tests
within a 'given' block:
given $pattern
{
{
TEST - $x { $x ~~ $_ }
when $a { ... } # if $a ~~ $pattern { ... ; next }
when $b { ... } # if $b ~~ $pattern { ... ; next }
when $c { ... } # if $c ~~ $pattern { ... ; next }
when $d { ... } # if $d ~~ $pattern { ... ; next }
}
when * { ... } # if $pattern ~~ * { ... ; next }
}
...and someone silly enough to want to frequently change the case
tester within a given block is advised to use 'if' instead.
What do you think?
--
Jonathan Dataweaver Lang
Re: Patterns
On 1/5/07, Larry Wall [EMAIL PROTECTED] wrote:
Anyway, that gives us:
given $pattern {
when .accepts(42) {...}
}
I think this type of usage should be encouraged with a bit more
huffmanization. My first thought would be to add Cagainst to invert
the arguments to ~~ versus Cwith.
given @something {
when $this { ... }# @something ~~ $this
against $that { ... }# $that ~~ @something
}
That would help keep the ~~ DWIM table from trying to guess on which
side you really wanted @something on.
- Ashley Winters
Patterns
I propose that we remove the following two lines from the smart match
table in S03:
HashAny hash entry existence exists $_{$x}
Array Any array contains item* any($_) === $x
These are the two lines with Any on the right side. I want to remove
these so that we can have an extensible ~~ operator.
You can think of $x ~~ $y as saying $x matches $y, i.e. $y is some
data pattern and we are asking if $x conforms to it. I want to be
able to add my own kinds of patterns, and entries with Any in the
right side undermine this.
Why? Let's say I created a pattern which implemented another textual
matcher alongside Perl's regexes, which was more convenient for some
things (I shouldn't have to convince you that this is possible and
useful). Let's call it Irregex. I want it to work just like Perl's
regexes; i.e. I want it so that if you ask whether an array matches
it, it will match against the elements of the array as though they
were characters. So I just overload ~~ to work on (Array, Irregex)
and that overrules (Array, Any) so there is no MMD ambiguity.
However! Let's say I'm using a payroll library (or something, sorry
for the mundane examples; I'm trying to keep it realistic) which sends
a notification if any user's status matches a pattern, and it is
implemented like so:
method notify(Any|Junction $pattern) {
if @.users.status ~~ $pattern {
# send notification
}
}
This is perfectly fine, elegant code given the ~~ table. But it
breaks since we have added our new pattern type! It doesn't check if
any user's status matches, it checks if the users' statuses'
concatenated considered as atoms matches, totally wrong!
So, I'm essentially asking for ~~ to be singly-dispatched based on its
right argument, which gets to pick how to interpret the left one. In
order to encourage this usage, I propose a design like so:
role Pattern {
method match($item) {...}
}
# Code, Bool, Undef, Whatever, Num, Junction, Str, Hash, ... ...
all do Pattern
sub *infix:~~ ($item, Pattern $pat) {
$pat.match($item);
}
So to add a new pattern, you just implement the Pattern role, and you are safe.
If you are very attached do those two rows of the smart match table,
we can reimplement them as Pattern objects, at the expense of some
unreadability:
given @array {
when 42 { ... }
}
Becomes:
given @array {
when contains 42 { ... }
}
etc.
Luke
Re: Patterns
On Fri, Jan 05, 2007 at 08:47:18PM +, Luke Palmer wrote:
: I propose that we remove the following two lines from the smart match
: table in S03:
:
:HashAny hash entry existence exists $_{$x}
:Array Any array contains item* any($_) === $x
:
: These are the two lines with Any on the right side. I want to remove
: these so that we can have an extensible ~~ operator.
:
: You can think of $x ~~ $y as saying $x matches $y, i.e. $y is some
: data pattern and we are asking if $x conforms to it. I want to be
: able to add my own kinds of patterns, and entries with Any in the
: right side undermine this.
It's much worse than just those two entries, because any entry not marked
with * is currently considered reversible. However, I think you're
the path toward sanity.
: Why? Let's say I created a pattern which implemented another textual
: matcher alongside Perl's regexes, which was more convenient for some
: things (I shouldn't have to convince you that this is possible and
: useful). Let's call it Irregex. I want it to work just like Perl's
: regexes; i.e. I want it so that if you ask whether an array matches
: it, it will match against the elements of the array as though they
: were characters. So I just overload ~~ to work on (Array, Irregex)
: and that overrules (Array, Any) so there is no MMD ambiguity.
:
: However! Let's say I'm using a payroll library (or something, sorry
: for the mundane examples; I'm trying to keep it realistic) which sends
: a notification if any user's status matches a pattern, and it is
: implemented like so:
:
:method notify(Any|Junction $pattern) {
:if @.users.status ~~ $pattern {
:# send notification
:}
:}
:
: This is perfectly fine, elegant code given the ~~ table. But it
: breaks since we have added our new pattern type! It doesn't check if
: any user's status matches, it checks if the users' statuses'
: concatenated considered as atoms matches, totally wrong!
I'm not so worried about extensibility as I am about consistency between
compile time and run time, such that the optimizer can optimize without
surprising the user. But this also argues against any anonymous Any on
the right. If all the when expressions are Num, the optimizer wants to
be able to evaluate the given in a numeric context whether or not you
put + on the front of it.
: So, I'm essentially asking for ~~ to be singly-dispatched based on its
: right argument, which gets to pick how to interpret the left one. In
: order to encourage this usage, I propose a design like so:
:
:role Pattern {
:method match($item) {...}
:}
:# Code, Bool, Undef, Whatever, Num, Junction, Str, Hash, ... ...
: all do Pattern
:
:sub *infix:~~ ($item, Pattern $pat) {
:$pat.match($item);
:}
One little problem here is that .match is currently defined the reverse
of that for the method form of m//.
: So to add a new pattern, you just implement the Pattern role, and you are
: safe.
:
: If you are very attached do those two rows of the smart match table,
: we can reimplement them as Pattern objects, at the expense of some
: unreadability:
:
:given @array {
:when 42 { ... }
:}
:
: Becomes:
:
:given @array {
:when contains 42 { ... }
:}
:
: etc.
Rather than special casing array matching, I'd say we want a general form
for explicitly reversing the figure/ground. If .match demands a pattern on
the left, then
given @array {
when .match(42) {...}
}
will already reverse the test to mean 42 ~~ @array. As I say, we need to
figure out what to do with foo.match(/bar/) though.
Larry
Re: Patterns
At the moment I'm leaning toward:
$pattern.accepts($thing)
$pattern.rejects($thing)
and going the other way
$thing ~~ $pattern
$thing.match($pattern)
$thing.subst($pattern)
and most generally, something like:
$thing.does($pattern)
$thing.when($pattern)
By the way, the Pattern type is already called Selector in the
synopses. Or perhaps Selector is a bit more general. Arguably Pattern
is the role that defines .accepts and .rejects, but Selector is
really the Pattern|Junction type you use in a signature. But we can't
just have Pattern does Junction or everything turns into a junction. :/
Or maybe they should be the other way around, where Selector is the role
and Pattern is the sig type. Or maybe the sig type should be Where so
we can say
multi grep (Where $where, [EMAIL PROTECTED]) {...}
and call it with :where{...} or where = {...}. Selector is kind of
a stupid name in any event.
Anyway, that gives us:
given $pattern {
when .accepts(42) {...}
}
which given typical usage patterns of switch statements is probably
adequately huffmanized, unless we want to go for something shorter
than accepts/rejects, like
acc/rej
pix/nix
ok/bogus
Of course, all of the .rejects() variants could simply be spelled
.accepts().not, but that seem unnecessarily cruel.
Larry
Re: dis-junctive patterns
HaloO, Gaal Yahas wrote: In pugs, r7961: my @pats = /1/, /2/; say MATCH if 1 ~~ any @pats; # MATCH say MATCH if 0 ~~ any @pats; # no match So far so good. But: my $junc = any @pats; say MATCH if 1 ~~ $junc; # no match say MATCH if 0 ~~ $junc; # no match Bug? Feature? Ohh, interesting. This reminds me to my proposal that junctions are code types and exert their magic only when recognized as such. The any(@pats) form constructs such a code object right in the match while the $junc var hides it. My idea was to explicitly request a code evaluation by one of my junc = any @pats; # 1: use code sigil say MATCH if 1 ~~ junc; say MATCH if 1 ~~ do $junc; # 2: do operator say MATCH if 1 ~~ $junc(); # 3: call operator But this might just be wishful thinking on my side. --
Re: dis-junctive patterns
On Tue, Nov 22, 2005 at 09:31:27AM +0200, Gaal Yahas wrote: : In pugs, r7961: : : my @pats = /1/, /2/; : say MATCH if 1 ~~ any @pats; # MATCH : say MATCH if 0 ~~ any @pats; # no match : : So far so good. But: : : my $junc = any @pats; : say MATCH if 1 ~~ $junc; # no match : say MATCH if 0 ~~ $junc; # no match : : Bug? Feature? Feels like a bug to me. The junction should autothread the ~~ even if ~~ weren't dwimmy. And ~~ ought to be dwimmy about junctions even if they didn't autothread. Maybe they're just doing the hallway dance. Larry
dis-junctive patterns
In pugs, r7961: my @pats = /1/, /2/; say MATCH if 1 ~~ any @pats; # MATCH say MATCH if 0 ~~ any @pats; # no match So far so good. But: my $junc = any @pats; say MATCH if 1 ~~ $junc; # no match say MATCH if 0 ~~ $junc; # no match Bug? Feature? -- Gaal Yahas [EMAIL PROTECTED] http://gaal.livejournal.com/
Re: Junctions, patterns, and fmap again
On 20/09/05, Luke Palmer [EMAIL PROTECTED] wrote:
The basic idea is that, alongside Functor, you have a Zippable theory
which defines:
theory Zippable[::T] {
multi zip (T[::A], T[::B] -- T[:(::A, ::B)]) {...}
}
Where that last coloney madness is a yet-to-be-proposed tuple type
(but tuples can be emulated if they are not in the core language, so
it's no biggie). That is, zip takes two structures and figures out
how to combine them in a reasonable way into pairs of values. So:
zip([1,2,[3,4]], [[a,b], c, d])
Gives:
[[:(1,a), :(1,b)], :(2,c), [:(3,d), :(4,d)]]
Oh, looks like I was way off. So in this particular scenario, when one
side 'runs out' of structure, that part degenerates to a one-side fmap
using the leaf value as the non-hyper arg.
Of course, this is the behaviour for /built-in/ arrays--it's up to the
person defining fzip to determine how to handle their own Zippable
types. So, if they want fzip to fail() on incompatible structures, or
do some other crazy thing, they can just put that in their version of
fzip.
So it's really up to the zippable functor itself to figure out the
best way to zip. After the structures are zipped up, you fmap the
binary function on each of the tuples, resulting in a reasonable
functor structure again.
Bottom line: user-defined fzip turns two structures into one
structure of pairs (in whatever way the user deems reasonable), and
then fmap transforms the tuples of that one structure.
For things like `foo(»$x«, »$y«, »$z«)` (assuming it ends up being
supported), you would either extend fzip over n-tuples, or just use
pair-fzip repeatedly and reduce the nested pairs into a single
n-tuple.
Nope. Here it is. And it was 22 lines. :-)
http://svn.luqui.org/svn/misc/luke/work/code/haskell/hyper.hs
Thanks, that made it a lot clearer. Haskell++ :)
I just hope you and I aren't the only ones who think this is a great idea...
Stuart
Re: Junctions, patterns, and fmap again
On 19/09/05, Luke Palmer [EMAIL PROTECTED] wrote:
Part 1: fmap
I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
but I don't want to go into that right now. It basically involves
zipping the structures up into tuples and applying the function to the
tuples.
Does this mean that 'unary' (one-side) hyper would be
structure-preserving, but 'binary' (two-side) hyper would not? Or
would you take the final list of tuples and re-build a structure?
I guess it comes down to whether you want to allow binary-hyper on
values that aren't structurally equivalent. Either you flatten both
structures to lists (which might be semantically dubious), or you
disallow binary-hyper on structurally distinct arguments (which might
prohibit some useful operations). Or you do something inconsistent.
(Have you written any of these deep details up somewhere? I'd love to
read them.)
Part 2: Junctions
So my proposal is to make a Junction into a plain old Functor. So
what used to be:
if any(@values) == 4 {...}
Is now:
if any(@values) »== 4 {...}
And the only thing that makes junctions different from Sets (which are
also Functors) is their behavior in boolean context (and their ability
to be Patterns; see below).
I think this is really nice: we get rid of invisible junction magic,
yet accessing that magic explicitly is only one or two characters
away. Being able to pass junctions around as values (safely) is a nice
bonus too.
Stuart
Re: Junctions, patterns, and fmap again
On 9/19/05, Stuart Cook [EMAIL PROTECTED] wrote:
On 19/09/05, Luke Palmer [EMAIL PROTECTED] wrote:
Part 1: fmap
I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
but I don't want to go into that right now. It basically involves
zipping the structures up into tuples and applying the function to the
tuples.
Does this mean that 'unary' (one-side) hyper would be
structure-preserving, but 'binary' (two-side) hyper would not? Or
would you take the final list of tuples and re-build a structure?
Well, I've written up the details in a 40 line Haskell program to make
sure it worked. I think I deleted the program, though.
The basic idea is that, alongside Functor, you have a Zippable theory
which defines:
theory Zippable[::T] {
multi zip (T[::A], T[::B] -- T[:(::A, ::B)]) {...}
}
Where that last coloney madness is a yet-to-be-proposed tuple type
(but tuples can be emulated if they are not in the core language, so
it's no biggie). That is, zip takes two structures and figures out
how to combine them in a reasonable way into pairs of values. So:
zip([1,2,[3,4]], [[a,b], c, d])
Gives:
[[:(1,a), :(1,b)], :(2,c), [:(3,d), :(4,d)]]
In order to be consistent with the specced semantics. In order to
keep with the specced semantics of junctions, you'll probably see:
zip(1|2, 34)
Give:
(:(1,3) :(1,4)) | (:(2,3) :(2,4))
So it's really up to the zippable functor itself to figure out the
best way to zip. After the structures are zipped up, you fmap the
binary function on each of the tuples, resulting in a reasonable
functor structure again.
Hmmm, that should probably be fzip or something.
Luke
Re: Junctions, patterns, and fmap again
On 9/19/05, Luke Palmer [EMAIL PROTECTED] wrote Well, I've written up the details in a 40 line Haskell program to make sure it worked. I think I deleted the program, though. Nope. Here it is. And it was 22 lines. :-) http://svn.luqui.org/svn/misc/luke/work/code/haskell/hyper.hs Luke
Junctions, patterns, and fmap again
Okay, due to some discussion on #perl6, I'll assume that the reason my
fmap proposal was Warnocked is because a fair number of people didn't
understand it. Also, for the people who did understand, this message
includes a complete proposal for the workings of Junctions that will
fluster Damian again. :-)
Part 1: fmap
De-symmetricalize hyper. So, what used to be @foo »+« 1 is now @foo
»+ 1; the hyper marker is only on the side of the operator that is
being hypered over. Of course, we still have @foo »+« @bar.
An object may do the role[1] Functor, in which case it defines a
method 'fmap' which is a generalization of map. For instance, let's
try it with a tree.
class Tree does Functor {
method fmap (code) {...}
}
class Branch is Tree {
has Tree $.left;
has Tree $.right;
method fmap (code) {
# Return an identical tree with the leaves mapped with code
return Branch.new(
left = $.left.fmap(code),
right = $.right.fmap(code),
);
}
}
class Leaf is Tree {
has $.data;
method fmap (code) {
# Just apply code to the value in the leaf
return Leaf.new( data = code($.data) )
}
}
Now if we have a $tree that looks like:
+---+---3
| +---4
+---5
$tree.fmap:{ $_ * 2 } returns:
+---+---6
| +---8
+---10
The formal signature of fmap is, if T is a Functor:
multi fmap (T[::U], code:(::U -- ::V) -- T[::V])
That is, it takes a T of some type, and a code that maps some type to
some other type, and returns a T of that other type.
Now, hypers are just syntactic sugar for various forms of fmap:
$x »+ $y# $x.fmap:{ $_ + $y }
$x +« $y# $y.fmap:{ $x + $_ }
foo(»$x«) # $x.fmap:{ foo($_) }
I have a plan for the $x »+« $y form (and also foo(»$x«, »$y«, »$z«)),
but I don't want to go into that right now. It basically involves
zipping the structures up into tuples and applying the function to the
tuples.
Part 2: Junctions
A Junction is a set of values together with a logical operation to be
applied when the Junction is in boolean context. When you add to a
Junction, you add to each of its values. When you pass a Junction to
a function, you call the function for each of its values and
reconstruct based on the return values. All in all, a Junction sounds
like a perfect candidate to be a Functor. Except all the fmapping is
implicit, which is what makes Junctions break the transitivity of ,
the orthogonality of the patterns 1 and 2, and all that other
stuff that people like me covet so.
So my proposal is to make a Junction into a plain old Functor. So
what used to be:
if any(@values) == 4 {...}
Is now:
if any(@values) »== 4 {...}
And the only thing that makes junctions different from Sets (which are
also Functors) is their behavior in boolean context (and their ability
to be Patterns; see below).
Yeah, it's a little teeny bit longer, but I think it is pretty easy to
get used to. And now junctinve threading looks like threading (just
like with hypers). The best part is that now it is okay to pass
Junctions to functions since they don't screw with your logical
assumptions, and the signature (Junction $x) is no longer semantically
special; it is a type check just like any other typed signature (and
optional just like any other typed signature :-).
Part 3: Patterns
Like I've said before, a Pattern is a thing that can be on the right
side of a ~~ operator. Most builtin things are Patterns: numbers,
strings, regexes, lists (maybe), booleans, closures, classes, and
junctions. Pattern is really a role[2] that requires a match(Any --
Bool). So then $x ~~ $y is equivalent to $y.match($x).
Here is a table of standard Patterns:
numbers, strings: eqv
regexes: match (note this gives us /foo/.match($str) for free)
lists: dunno
booleans: boolean truth (ignores left side)
closures: apply closure and test truth
classes: .does
junctions: see below
A Junction of Patterns does Pattern under its logical operation. So
$x ~~ any($y,$z) is equivalent to $x ~~ $y || $x ~~ $z. This is the
only autothreading operation. And that is so you can say:
given $value {
when 1 | 2 | 3 {...}
when /^foo/ | /^bar/ {...}
}
The signature of grep is:
sub grep (Pattern $pat, [EMAIL PROTECTED]) {...}
So then these all make sense:
grep /foo/, @values;
grep 1|2, @values;
grep Node, @objects
And the regular closure form of grep is only for straight boolean
tests against the argument:
grep { lc eq 'foo' } @strings;
This really doesn't give us anything new. But in my opinion, it
solidifies what we already have greatly, and makes it much easier to
think about and work with (no more guessing :-). It also trivializes
the smart match table in S04.
Luke
[1] Really
Re: Argument Patterns
Luke Palmer [EMAIL PROTECTED] wrote: I think we should replace our multimethod system with a more general pattern matcher, a variadic multimethod system of sorts. Multimethods need to be variadic anyway, because we want pugs's quicksort example to work. I'd not say replace. The dispatcher will very likely be a Parrot PMC. The default dispatcher dispatches on types, matching variadic signatures should be possible too. All infix operators are multi subs. I can't imagine that we want to pay the penalty for simple operations like: $a = $b + $c to inspect the values of operands, constraints, rules and what not. [ dispatching on rules ] If the involved types need a more fancy dispatcher, their meta-class should say so. Luke leo
Re: Argument Patterns
Leopold Toetsch writes: Luke Palmer [EMAIL PROTECTED] wrote: I think we should replace our multimethod system with a more general pattern matcher, a variadic multimethod system of sorts. Multimethods need to be variadic anyway, because we want pugs's quicksort example to work. I'd not say replace. The dispatcher will very likely be a Parrot PMC. The default dispatcher dispatches on types, matching variadic signatures should be possible too. All infix operators are multi subs. I can't imagine that we want to pay the penalty for simple operations like: $a = $b + $c to inspect the values of operands, constraints, rules and what not. Having written several multi dispatch systems, I know that this is easy to optimize. If nobody has defined + on any fancy subtypes, then we can quickly fall back to a bitset-intersection dispatch algorithm on the types (or even, eew, direct lookup). If + has been defined on fancy subtypes, then we compile the quickest way to figure out whether none of the arguments are one of them, and fall back. This is a little tricky, but some elementary graph theory gets us there. Essentially, what dispatcher we're using for + depends on what kinds of +s people have defined. That's how it should be; otherwise you'll get people globally overriding + so they can stick their own dispatcher in there, which isn't a portable solution. But we always have enough knowledge to optimize the hell out of this, and they're not not handwavy we can probably optimizations. They're real, and they're pretty darn easy. Luke
Re: Argument Patterns
Luke Palmer wrote: But we always have enough knowledge to optimize the hell out of this, and they're not not handwavy we can probably optimizations. They're real, and they're pretty darn easy. I fully agree. But I like to add that a single 'where' on general types like Int, Str or even Any can seriously harm performance because than the dispatcher has to check it always and everywhere! So the Perl 6 type system let's you have your rope and tie yourself. Well, that is late binding :) -- TSa (Thomas Sandla)
Re: Logic Programming with Rules (and Argument Patterns)
Rod Adams writes:
Indeed, a great deal of logical testing can be performed with the
current P6RE definition.
For instance:
rule Equal ($x, $y) {{ $x ~~ $y or fail }};
rule Substr (Str $str, Str $in) {{ $in ~~ /$str/ or fail }};
rule IsAbsValue (Num $x, Num $y) {
{$x == $y or fail} |
{$x == -$y or fail} };
There are some things that are lacking, however. The first is that all
of the Cor fail's will get very old for typing and viewing. I would
propose that we add :a/:assert as a rule modifier, making all closures
assertions that behave exactly as if you typed a C or fail at the
end of each of them.
Or you could avoid the global modifier and write your tests in ( )
blocks instead... after all, that's what it's there for.
The really big problem, however, is the lack of generators.
I'll establish a working definition of generator as something which
offers a possible value, giving the new value each time the expression
is backtracked over, and fails when there are no more values to give.
One generator is the * combinator. It gives the longest string, then
the next shorter, then the next shorter...
Clearly, desirable generators include lazy lists, arrays, and
closures. All of which P6RE supports as ways of attempting different
rules/strings to match against, but not as different values to assign
a given $var to feed into later rules. Capturing assumes a string to
match and capture against. Capturing the null string that I match is
not terribly useful.
The only suggestion I can give for how to do this is by introducing the
hyper operator. I'm very open to other ideas, because this one does not
sit well with me, but it's all I've got at the moment. So, to give an
array as a generator, one could write:
/:a {$x = @values} test($x)/
You could do all of this with a library of rules.
/ $x:=generate(@values) test($x) /
How the generate rule is actually written is getting into some rule
engine internal stuff, but we're making sure that the rule engine has
enough hooks to do that.
I think you'll be interested in where my 'Argument Patterns' proposal
was going next, before I ran off to class (and got scared of posting it,
because people would get scared of me). But it seems to be related to
what you're talking about. Maybe we could unify the pattern proposal
and your generation ideas for logic programming.
[WARNING: highly speculative, abstract, scary content ahead]
You can create patterns outside of argument lists, too. One kind of
pattern that we're already familiar with is the junction (that's right,
I just redefined what a junction is). If you give a pattern to an array
as a subscript, it returns the pattern that matches each thing
referenced by any subscript pattern, if that makes sense.
Now, certain types of patterns can be generated. What exactly can be
generated depends on what types of patterns implement a GENERATE method
that succeeds when you call it.
Allow me to use $^ as a 'pattern variable' marker for outside of
parameter lists.
@array[$^i] # returns a lazy pattern of everything in @array, bound
# together with the corresponding $i
(@array[$^i]).GENERATE # generates every element of @array
Now, let's just combine that with another array pattern:
@a[$^i] + @b[$^i] # returns lazy pattern of everything in @a
# added to its corresponding element in @b
(@a[$^i] + @b[$^i]).GENERATE # vector sum
Now if we just spell .GENERATE with :
@a[$^i] + @b[$^i]
We have my tensor-hyper proposal back.
Not only does it work with arrays, it works with any combination of
things that can be generated. This includes arrays whose shapes are not
declared, hashes, even roles if their implementor decides to implement
GENERATE.
Now could have a similar meaning within rules, which would give you
your generator.
# print everything in @array that matches test()
/ $x := [EMAIL PROTECTED] ( test($x) ) { say $x; fail } /
Of course, that can much more easily be done with a grep, but hey,
TMTOAWTDI*, right?
The biggest question is how this interacts with sub calls. We can't
really expect sub calls to be pattern-aware: that puts constraints on
what we're allowed to do in a sub (no side-effect constraints; gee,
those kinds of constraints really go a long way). But test could
certainly implement a GENERATE method:
sub is_prime(
$x will GENERATE { primes() }
)
{
?grep { $_ == $x } primes()
}
The will generate says that the sub can accept a generic pattern and
will fill it in on the spot.
That's my first-order approximation. There is probably some higher
order stuff that proves that I'm way off.
In particular, it would be great if this stuff could be crammed into a
library, but I understand that that would be very hard for such
features...
Luke
* A = Awkward
Re: Argument Patterns
Thomas Sandla writes: Luke Palmer wrote: But we always have enough knowledge to optimize the hell out of this, and they're not not handwavy we can probably optimizations. They're real, and they're pretty darn easy. I fully agree. But I like to add that a single 'where' on general types like Int, Str or even Any can seriously harm performance because than the dispatcher has to check it always and everywhere! So the Perl 6 type system let's you have your rope and tie yourself. Well, that is late binding :) Only if you define an AUTOLOAD on your subtypes. The way to think about multimethod implementation problems is inside-out from how you think about single dispatch. The *method* is the one that knows everything, not the object. So definitions on subtypes of general types only check for those subtypes when dispatching to the methods defined in them. Luke
Re: Argument Patterns
HaloO Luke, you wrote: [..] The *method* is the one that knows everything, not the object. So definitions on subtypes of general types only check for those subtypes when dispatching to the methods defined in them. I stand corrected. Lax usage of Any is fair. Defining subtypes of general types and using them to constrain e.g. params of subs is fine, too. But defining a multi branch on a very common operator like +, * or grep for a predicate---i.e. using where---subtype is penalized. Sounds reasonable to me. MfG -- TSa (Thomas Sandla)
Re: Logic Programming with Rules (and Argument Patterns)
Luke Palmer wrote:
Rod Adams writes:
Or you could avoid the global modifier and write your tests in ( )
blocks instead... after all, that's what it's there for.
I *knew* I had seen a syntax for that before... I just didn't see it
when I scanned S05 for it.
I still want the :z modifier for matching zero length strings. That
makes sense to be global.
The really big problem, however, is the lack of generators.
I'll establish a working definition of generator as something which
offers a possible value, giving the new value each time the expression
is backtracked over, and fails when there are no more values to give.
One generator is the * combinator. It gives the longest string, then
the next shorter, then the next shorter...
I agree that * works that way... when you're matching against a
string... which I'm not. I intend for the basic call to be something
like C ~~ /test(1)/ , or more likely just C /test(1)/ . I
won't care what the current topic is. I'll match the empty string, and
everything that includes it, or nothing at all. My entire rule set will
be a series of really complex zero-length assertions.
Clearly, desirable generators include lazy lists, arrays, and
closures. All of which P6RE supports as ways of attempting different
rules/strings to match against, but not as different values to assign
a given $var to feed into later rules. Capturing assumes a string to
match and capture against. Capturing the null string that I match is
not terribly useful.
The only suggestion I can give for how to do this is by introducing the
hyper operator. I'm very open to other ideas, because this one does not
sit well with me, but it's all I've got at the moment. So, to give an
array as a generator, one could write:
/:a {$x = @values} test($x)/
You could do all of this with a library of rules.
/ $x:=generate(@values) test($x) /
I don't think this does what I want. In this, generate returns a rule
or string of some kind, matches the string being tested, captures what
matches, and then binds the capture to $x.
I have no underlying string, so the match fails right there. I want to
bind/assign to the variable _without_ matching, but _with_ backtracking
and iteration over several values.
I also now notice that I would need a C let in my example above.
How the generate rule is actually written is getting into some rule
engine internal stuff, but we're making sure that the rule engine has
enough hooks to do that.
There were some thoughts in the back of my head about how I actually
wanted a closure to be handled as a generator. I see the need to
initialize it many separate times, once on each forward attempt, can be
repeated if something after it fails, and something before it has an
alternative. But I wanted the basic concept out there before I tried
diving into that kind of detail.
Maybe we could unify the pattern proposal and your generation ideas for logic programming.
There might be unification with logical programming to be had, but I'm
not sure it's with the generation part of things.
@array[$^i] # returns a lazy pattern of everything in @array, bound
# together with the corresponding $i
How is this any different from just @array ?
(@array[$^i]).GENERATE # generates every element of @array
Now, let's just combine that with another array pattern:
@a[$^i] + @b[$^i] # returns lazy pattern of everything in @a
# added to its corresponding element in @b
(@a[$^i] + @b[$^i]).GENERATE # vector sum
Now if we just spell .GENERATE with :
@a[$^i] + @b[$^i]
We have my tensor-hyper proposal back.
This example is easily done as:
@a + @b
But it's also not terribly far removed from my hyperthreader operator in
the Junctions thread (oh, when, oh when is Damian coming back?). There
are differences, but see if that does what you need.
Not to mention that are already taken in that context as q:w//
operators.
Now could have a similar meaning within rules, which would give you
your generator.
# print everything in @array that matches test()
/ $x := [EMAIL PROTECTED] ( test($x) ) { say $x; fail } /
Problems with this:
1) in RE's are already taken for non-capturing meta's. And binding
doesn't work if you don't capture.
2) you're still trying to match the value against the string.
Not really a problem, but I had C test($x) , not C
(test($x)) on purpose. I was feeding into a rule, not a function.
The biggest question is how this interacts with sub calls. We can't
really expect sub calls to be pattern-aware: that puts constraints on
what we're allowed to do in a sub (no side-effect constraints; gee,
those kinds of constraints really go a long way). But test could
certainly implement a GENERATE method:
sub is_prime(
$x will GENERATE { primes() }
)
{
?grep { $_ == $x } primes()
}
The will generate says that the sub can accept a generic pattern and
will fill it in on
Re: Logic Programming with Rules (and Argument Patterns)
Rod Adams writes: You could do all of this with a library of rules. / $x:=generate(@values) test($x) / I don't think this does what I want. In this, generate returns a rule or string of some kind, matches the string being tested, captures what matches, and then binds the capture to $x. You're right. We probably need something like: / generate($x, @values) test($x) / I don't know when $x is hypotheticalized there, if at all. It needs to be. Maybe we could unify the pattern proposal and your generation ideas for logic programming. There might be unification with logical programming to be had, but I'm not sure it's with the generation part of things. I was decently insane last night. This generator stuff probably isn't going anywhere. It's too abstract, and not precise enough, to be a truly powerful part of the language. Luke
Re: Logic Programming with Rules (and Argument Patterns)
On Wed, Mar 09, 2005 at 08:56:22AM -0700, Luke Palmer wrote: : I was decently insane last night. This generator stuff probably isn't : going anywhere. It's too abstract, and not precise enough, to be a : truly powerful part of the language. I suspect it's another one of the many things we just try to stay within hailing distance of without trying to solve for 6.0.0. The worst that can happen is that someone later defines use coolness to turn their program into something that doesn't interoperate with standard Perl 6. Then we either bend Perl 6 to where it is interoperable, or someone rewrites all the libraries for coolness. Biologically, it comes down to more sex and a bigger gene pool, or less sex and more speciation and specialization. Sex is fun, but it probably doesn't solve all your problems. Larry
Re: Logic Programming with Rules (and Argument Patterns)
Larry Wall wrote: I suspect it's another one of the many things we just try to stay within hailing distance of without trying to solve for 6.0.0. That's cool. I was just relaying the observation that the P6RE was fairly close to being able to implement Logical Programming, which several people seem to be trying to get into Perl in some fashion or another. I can easily wait until 6.2 for this to happen (for now at least). -- Rod Adams
Re: Logic Programming with Rules (and Argument Patterns)
--- Rod Adams [EMAIL PROTECTED] wrote: I was just relaying the observation that the P6RE was fairly close to being able to implement Logical Programming, which several people seem to be trying to get into Perl in some fashion or another. When I get a chance to talk to someone about logic programming, there's frequently an aha! moment where they start to see some of the potential, but then I inevitably get the question if it's so powerful, why ain't it rich? (or something like that.) The answer, I think, is that it's generally not available in the tools that most people use. SQL, regexen and makefiles all dance around logic programming -- well, makefiles sort of stumble -- but if LP was more readily available, people would be more likely to appreciate it. Unfortunately, while Prolog is a piece of cake to learn, this thread made my head hurt. Cheers, Ovid If this message is a response to a question on a mailing list, please send follow up questions to the list. Web Programming with Perl -- http://users.easystreet.com/ovid/cgi_course/
Argument Patterns
All this Haskell programming has opened my eyes to what our multimethod
dispatch could be. As we have seen with Csort, the dispatch system is
a pattern matcher. But it's a pretty terrible one.
I think we should replace our multimethod system with a more general
pattern matcher, a variadic multimethod system of sorts. Multimethods
need to be variadic anyway, because we want pugs's quicksort example to
work.
Here's my proposal:
Inside an argument list, the first mention of a variable introduces its
binding. Later arguments require a match. We can now define 'equal':
sub equal ($x, $x) { 1 }
sub equal ($x, $y) { }
That's one of the MTOWs at least. The evaluation order of the patterns
still needs to be thought out.
There are more types of patterns. Types are patterns, and from this we
see that following a pattern by a variable binds the variable to
whatever matched that pattern. Constants are also patterns. Junctions
of patterns are also patterns. Lists of patterns are patterns, as are
hashes of patterns. In fact, the last two give us slurpy scalars:
sub length () { 0 }
sub length (*[ $x, [EMAIL PROTECTED] ]) { 1 + length @rest }
And +$name parameters:
sub length (*{ name = $name }) { }
Cwhere constrains a pattern:
sub factors ($x where { is_prime($x) }) { $x }
...
(The object in question is given as the topic of the where block:
sub factors ($x where { .is_prime }) { $x }
...
)
There will also be hooks to allow arbitrary pattern objects.
# does $x match our pattern?
method Pattern::MATCHES ($x) { ... }
And now here's the cool part. A type is defined to be a pattern (a
'class' is different, though, but it creates an identically-named type).
So instead of definining these multis (I seek to banish the 'multi'
keyword, since I seek to banish the idea of an invocant), you could also
pretend that they're methods on subtypes. A 'role' is just a collection
of methods on a type, a pattern:
role ($x where {.is_prime}) {
method factors() { $?SELF }
}
This is exactly equivalent to:
sub factors($x where {.is_prime}) { $x }
And of course, if you define a role with a name, then it becomes an
abstract type:
role Serializable {
method serialize() {...}
method clone() { restore(.serialize) }
}
And you have to tell objects that they're Serializeable.
Luke
Re: Argument Patterns
Luke Palmer wrote:
All this Haskell programming has opened my eyes to what our multimethod
dispatch could be. As we have seen with Csort, the dispatch system is
a pattern matcher. But it's a pretty terrible one.
I think we should replace our multimethod system with a more general
pattern matcher, a variadic multimethod system of sorts. Multimethods
need to be variadic anyway, because we want pugs's quicksort example to
work.
Here's my proposal:
Inside an argument list, the first mention of a variable introduces its
binding. Later arguments require a match. We can now define 'equal':
sub equal ($x, $x) { 1 }
sub equal ($x, $y) { }
That's one of the MTOWs at least. The evaluation order of the patterns
still needs to be thought out.
I thought Larry already declared that we are not making Perl act like ML
(yet).
-- Rod Adams
Re: Argument Patterns
On Tue, Mar 08, 2005 at 04:55:28PM -0600, Rod Adams wrote: I thought Larry already declared that we are not making Perl act like ML (yet). And that was re: type inferencing, not re: pattern matching. :) Thanks, /Autrijus/ pgp3tE8H37UB0.pgp Description: PGP signature
Re: Argument Patterns
Autrijus Tang wrote: On Tue, Mar 08, 2005 at 04:55:28PM -0600, Rod Adams wrote: I thought Larry already declared that we are not making Perl act like ML (yet). And that was re: type inferencing, not re: pattern matching. :) Thanks, /Autrijus/ Sorry about that. Comcast has decided I only get internet connectivity for a random 1 minute roughly every 1/2hr today, so I can't perform any back searches. I'll make a more detailed response to the original post shortly. -- Rod Adams
Patterns and junctions
I've had an idea brewing for a while, and since talk seems to have turned to reg^H^H^Hpatterns and rules again, I figured this might be the time to mention it. A while ago someone asked about whether backtracking semantics are mandatory in any implementation, or whether it would be legal to build an implementation that, for instance, has no preference among alternatives. I propose that since the empty pattern is no longer legal (and about time), we use | in patterns to indicate alternation without preference, and || to indicate try the first, then the second, etc. So cat dog fox ~~ /( fox | dog | cat )/; might match any of the three, and in fact is quite likely to match cat (since scanning the string could be a very long process), but cat dog fox ~~ /( fox || dog || cat )/; would be guaranteed to first try fox, then if that fails backtrack and try dog, and if that fails backtract to try cat. The choice of symbols parallels the junction and short-circuiting or operators, and in most cases when an alternation is specified, the programmer has no preference among the alternatives (indeed, in most cases only would could match anyway), so it seems silly to force the engine to prefer the first one. I'm imagining that in the first example, the implementation would probably build an FSA and process each letter as it comes, while the second would rely on backtracking. What think you all? -- Adam Lopresto http://cec.wustl.edu/~adam/ There's too much blood in my caffeinestream.
Re: Patterns and junctions
--- Adam D. Lopresto [EMAIL PROTECTED] wrote: I propose that since the empty pattern is no longer legal (and about time), we use | in patterns to indicate alternation without preference, and || to indicate try the first, then the second, etc. Hmm A neat idea, but can you elaborate on when it would matter? So cat dog fox ~~ /( fox | dog | cat )/; might match any of the three, and in fact is quite likely to match cat (since scanning the string could be a very long process), but cat dog fox ~~ /( fox || dog || cat )/; would be guaranteed to first try fox, then if that fails backtrack and try dog, and if that fails backtract to try cat. The choice of symbols parallels the junction and short-circuiting or operators, and in most cases when an alternation is specified, the programmer has no preference among the alternatives (indeed, in most cases only would could match anyway), so it seems silly to force the engine to prefer the first one. I thought the requirement to prefer the first was largely an optimization, so that it could bail when it had a match without continuing to search. (Wouldn't you know, it was in the *last* place I looked for it!) Are you proposing a more DFA-ish behavior, maybe? Some programs actually embad a DFA for a quick does it match? as *well* as an NFA for pulling out backreferences once the DFA finds a hit, but I doubt anybody is planning to embed a pre-matching DFA in Perl (if so, somebody please tell me now). I'm imagining that in the first example, the implementation would probably build an FSA and process each letter as it comes, while the second would rely on backtracking. Sounds like DFA/NFA to me What think you all? Dunno. Would swell the footprint some, but might have some merit. DFA's are generally faster, I believe, but P5's NFA is optimized to a beautiful degree. Might be possible just by tuning the engine some more, but then the codebase is still swelling Dan? Parrot's pure NFA, right? __ Do you Yahoo!? Yahoo! Tax Center - File online, calculators, forms, and more http://tax.yahoo.com
Re: Patterns and junctions
--- Luke Palmer [EMAIL PROTECTED] wrote: [extremely large *SNIP*] Maybe the |/|| distinction isn't needed, and we just need a declarator on rules that says they are side-effect-free, and can thus be optimized. [snip] I like this solution better than making a new operator. In Perl tradition, it puts the optimization burdon on the compiler, not the programmer. Agreed. Minimize the need for new grammar in the language, including operators, but provide a way that code can DWIM the same result. If you build it, they will come. __ Do you Yahoo!? Yahoo! Tax Center - File online, calculators, forms, and more http://tax.yahoo.com
Re: possible bugs in Exegesis 5 code for matching patterns
Steve Tolkin wrote:
{ $appendline =~ s/in_marker//;
I think this needs a backslash in front of the symbol, and a space
after in_marker, i.e. it should be:
{ $appendline =~ s/in_marker/\sp/;
Isn't the replacement part of a substitution is still a string?
Having the replacement being a rule would mean that you could write
things like:
s:e/ \* / [aeiou] /;
That would replace asterisks with 'any' vowel, without specifying which
vowel to use. That makes no sense at all. (Well, not unless it creates
a superposition, but surely Damian can't have intended to introduce
superpositions like this is the core language? Can he?)
So since pointy brackets aren't special in strings, it doesn't take a
backslash; similarly spaces should just be written as spaces.
rule fileinfo {
out_marker3 $oldfile:=(\S+) $olddate:=[\h* (\N+?) \h*?] \n
in_marker3 $newfile:=(\S+) $newdate:=[\h* (\N+?) \h*?] \n
}
rule out_marker { \+ sp }
rule in_marker { - sp }
The sp means a single literal space. So I think out_marker3
means look for + + + rather than +++ which is what is really
needed to match a Unified diff.
Yes, you look to be right to me.
If these are bugs, then what would be the best way to
fix the code while retaining as much reuse as possible.
This is one way:
rule out_marker_symbol { \+ }
rule in_marker_symbol { - }
rule out_marker { out_marker_symbol sp }
rule in_marker { in_marker_symbol sp }
rule fileinfo {
out_marker_symbol3 $oldfile:=(\S+) $olddate:=[\h* (\N+?) \h*?] \n
in_marker_symbol3 $newfile:=(\S+) $newdate:=[\h* (\N+?) \h*?] \n
}
[While we're on the subject of typos, it looks like the final definition
of Cfileinfo in the exegesis has C$newfile where C$oldfile is
meant.]
But it'd probably be easier just to do:
rule fileinfo {
\+\+\+ $oldfile:=(\S+) $olddate:=[\h* (\N+?) \h*?] \n
---$newfile:=(\S+) $newdate:=[\h* (\N+?) \h*?] \n
}
That isn't a terrible cop out to repeat the symbols, since there's no
reason why the format has to use the same symbols in both places.
Smylers
possible bugs in Exegesis 5 code for matching patterns
Here is a discussion thread of Exegesis 5
http://www.perl.com/pub/a/2002/08/22/exegesis5.html at
http://developers.slashdot.org/developers/02/08/23/1232230.shtml?tid=145
But the signal/noise is too low, with side tracks into
Monty Python etc.
In section Smarter alternatives there is this code:
{ @$appendline =~ s/in_marker//;
I think this needs a backslash in front of the symbol,
and a space after in_marker, i.e. it should be:
{ @$appendline =~ s/in_marker/\sp/;
That a small issue. But the following is more
important because it strikes at the ease of
using inheritance of grammars (i.e. patterns).
In
http://www.perl.com/pub/a/2002/08/22/exegesis5.html?page=5#different_diffs
we see the code:
rule fileinfo {
out_marker3 $oldfile:=(\S+) $olddate:=[\h* (\N+?) \h*?] \n
in_marker3 $newfile:=(\S+) $newdate:=[\h* (\N+?) \h*?] \n
}
rule out_marker { \+ sp }
rule in_marker { - sp }
The sp means a single literal space.
So I think out_marker3 means look for + + +
rather than +++ which is what is really needed
to match a Unified diff. Similarly for in_marker3
Or am I missing something?
If these are bugs, then what would be the best way to
fix the code while retaining as much reuse as possible.
Hopefully helpfully yours,
Steve
--
Steven Tolkin [EMAIL PROTECTED] 617-563-0516
Fidelity Investments 82 Devonshire St. V8D Boston MA 02109
There is nothing so practical as a good theory. Comments are by me,
not Fidelity Investments, its subsidiaries or affiliates.
