, , and backtracking.
How do C and C differ with respect to backtracking? For instance, foobar ~~ / [a..z]+ [ ... ] /; Both sides of the C happen in parallel, so I would guess that they both match foo then stop. Please correct me if that's wrong. Were we using the procedural conjunction: foobar ~~ / [a..z]+ [ ... ] /; I would guess that the LHS matches as much as it can (foobar), then the RHS matches foo. Since foobar ne foo, the regex engine backtracks on the LHS matching fooba and then the RHS matches foo again. Again, since fooba ne foo, the regex engine backtracks as before and this behavior continues until both sides match foo (or, in the general case, it can determine that the conjunctions can't match the same portion of the string) Or it's much simpler than that and both of the regexes above just fail because of the greediness of C+ and there is no intra-conjunction backtracking. So ... anyone care to enlighten me on how this is supposed to work? Thanks, -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
Re: , , and backtracking.
Jonathan Scott Duff wrote: How do C and C differ with respect to backtracking? For instance, foobar ~~ / [a..z]+ [ ... ] /; Both sides of the C happen in parallel, so I would guess that they both match foo then stop. Please correct me if that's wrong. As written, this match would fail, since '[a..z]+' would match foobar while '[ ... ]' would match foo. '' requires that both sides match the same start and end points. I suppose that it might be worth considering requiring only the start points to match, and having the conjoined match use the earliest end point; so that the above match would then match foo instead of failing. But it's entirely possible that there's something faulty with this approach. The difference between '' and '' is that '' evaluates the two sides in an arbitrary order, possibly even in parallel; '' always evaluates the left side first, and only bothers with the right side if the left side matched. -- Jonathan Dataweaver Lang
Re: , , and backtracking.
On Thu, Sep 06, 2007 at 01:25:12PM -0500, Patrick R. Michaud wrote: : Were we using the procedural conjunction: : : foobar ~~ / [a..z]+ [ ... ] /; : : I would guess that the LHS matches as much as it can (foobar), then : the RHS matches foo [...and then backtracks the LHS until a : conjunctional match is found...] : : Or it's much simpler than that and both of the regexes above just fail : because of the greediness of C+ and there is no intra-conjunction : backtracking. : : I think we definitely allow intra-conjunction backtracking. : PGE implements it that way. That's what I think. : On a somewhat similar question, what happens with a pattern : such as : : foobar ~~ / foo.+? | fooba / : : The LHS initially matches foob, but with backtracking could : eventually match foobar. Do the longest-token semantics : in this case cause the RHS to be dispatched first, even : though the token declaration of the LHS _could_ match a : longer token prefix? Yow. ICATBW. Non-greedy matching is somewhat antithetical to longest-token matching. But basically it boils down to this: Does the longest-token matcher ignore the ? and do foo.+ | fooba or is there an implicit ordering above and beyond the DFA engine of foob | fooba || fooba | fooba || foobar | fooba || I think longest-token semantics have to trump minimal matching here, and my argument is this. Most uses of *? have additional information on what terminates it, either implicitly in what it is matching, or explicitly in the next bit of regex. That is, you'd typically see either foo\w+? | fooba or foo.+? wb | fooba In either case, the clear intent is to match foobar over fooba. Therefore I think the DFA matcher just strips ? and does its ordinary character by character match, relying on that extra info to match the real extent of the quantifier. Larry
Re: , , and backtracking.
On Thu, 2007-09-06 at 12:37 -0700, Larry Wall wrote: Yow. ICATBW. The what now? -'f
Re: , , and backtracking.
On Thu, Sep 06, 2007 at 12:37:37PM -0700, Larry Wall wrote: On Thu, Sep 06, 2007 at 01:25:12PM -0500, Patrick R. Michaud wrote: : On a somewhat similar question, what happens with a pattern : such as : : foobar ~~ / foo.+? | fooba / : : The LHS initially matches foob, but with backtracking could : eventually match foobar. Do the longest-token semantics : in this case cause the RHS to be dispatched first, even : though the token declaration of the LHS _could_ match a : longer token prefix? Yow. ICATBW. Non-greedy matching is somewhat antithetical to longest-token matching. I agree. One thought I had was that perhaps non-greedy matching could also terminate the token prefix. [...] I think longest-token semantics have to trump minimal matching here, and my argument is this. Most uses of *? have additional information on what terminates it, either implicitly in what it is matching, or explicitly in the next bit of regex. That is, you'd typically see either foo\w+? | fooba or foo.+? wb | fooba In either case, the clear intent is to match foobar over fooba. Therefore I think the DFA matcher just strips ? and does its ordinary character by character match, relying on that extra info to match the real extent of the quantifier. Does this still hold true for a non-greedy quantifier in the middle of an expression... ? I.e., foobazbar deborah ~~ /foo .+? b.r | fooba | foobazb / matches foobazbar debor ? (I completely grant that the examples I'm coming up with here may be completely nonsensical in real application, but I'm just exploring the space a bit.) Pm
Re: , , and backtracking.
On Thu, Sep 06, 2007 at 03:49:42PM -0700, Larry Wall wrote: : On Thu, Sep 06, 2007 at 04:02:19PM -0500, Patrick R. Michaud wrote: : : I agree. One thought I had was that perhaps non-greedy matching : : could also terminate the token prefix. : : Well, that's more or less arguing it the other way. It kind of assumes : your fooba-ish arguments are smart enough to test for non-r after. The more I think about it, the more I like this approach. Most token should be matched in ratchet mode, and I think minimal matching is perhaps a form of cheating: Look for the nearest end of this without me actually bothering to parse the middle. And certainly any reasonable grammer is going to be checking that a keyword is properly terminated by a word boundary anyway. Larry
Re: , , and backtracking.
On Thu, Sep 06, 2007 at 04:02:19PM -0500, Patrick R. Michaud wrote: : I agree. One thought I had was that perhaps non-greedy matching : could also terminate the token prefix. Well, that's more or less arguing it the other way. It kind of assumes your fooba-ish arguments are smart enough to test for non-r after. : [...] : I think longest-token semantics have to trump minimal matching here, : and my argument is this. Most uses of *? have additional information : on what terminates it, either implicitly in what it is matching, or : explicitly in the next bit of regex. That is, you'd typically see : either : foo\w+? | fooba : or : foo.+? wb | fooba : : In either case, the clear intent is to match foobar over fooba. : Therefore I think the DFA matcher just strips ? and does its ordinary : character by character match, relying on that extra info to match : the real extent of the quantifier. : : Does this still hold true for a non-greedy quantifier in the : middle of an expression... ? I.e., : : foobazbar deborah ~~ /foo .+? b.r | fooba | foobazb / : : matches foobazbar debor ? I suppose one approach would be to limit the DFA to the longest known constant string, and then rerun any variable branches individually to see if they will actually match something that long. Alternately, if the DFA engine is smart enough to kick out all the matches of the foo .+? b.r branch then it could conceivably be taught to return the shortest one rather than the longest one. Course, the question after than is, what if you mix minimal with maximal quantifiers? Another consideration is the efficiency of matching that pattern against foobazbar ~ 'b' x 1. That would definitely run faster if you cut off the DFA after the longest known token, or as soon as the DFA reduces to one possibility, presuming you can know such a thing. Any way we work it, there will be a way to use it wrong. Larry
Q: Can colons control backtracking in logical expressions?
Consider this code:
if (specific_condition())
{
if (detail())
{
act();
}
}
elsif (general_condition())
{
act();
}
Logically, this turns into:
if ((my $sc = specific_condition()) detail())
|| (!$sc general_condition())
{
act();
}
Both look horrible, of course. I'd like to rewrite them as
if (specific_condition() :: detail()) || general_condition()
{
act();
}
so that if specific_condition() succeeded, it would cause the entire
expression to fail if detail() failed.
The use of :: comes, of course, from rexen.
Is this feasible?
=Austin
Re: Q: Can colons control backtracking in logical expressions?
Austin Hastings wrote:
Both look horrible, of course. I'd like to rewrite them as
if (specific_condition() :: detail()) || general_condition()
{
act();
}
so that if specific_condition() succeeded, it would cause the entire
expression to fail if detail() failed.
The use of :: comes, of course, from rexen.
Is this feasible?
Not in Perl itself. But you could always put 'em in regexen:
if (/(specific_condition()) :: (detail()) | (general_condition())/)
{
act();
}
However that's just showing off. All you really need is:
if ( specific_condition() ? detail() : general_condition() )
{
act();
}
;-)
Damian
Re: Q: Can colons control backtracking in logical expressions?
All you really need is: if ( specific_condition() ? detail() : general_condition() ) Oops! That's the Perl 5 version. In Perl 6, of course, it's: if ( specific_condition() ?? detail() :: general_condition() ) Which means you *do* get to use the :: after all! (Just not where you might have expected ;-) Damian
RE: Q: Can colons control backtracking in logical expressions?
-Original Message-
From: Damian Conway [mailto:[EMAIL PROTECTED]
Since paren's aren't required with keywords, can they still serve as rex
delimiters?
No. For other syntactic reasons parens aren't allowed as rule
delimiters at all. And only /.../ delimit raw matches. Every other
delimiter
requires an explicit 'm'.
I keep forgetting poor Cm.
Sadly, it doesn't generalize well:
if (specific() :: detail1() :: detail2()) || general() {...}
becoming
if (specific() ? detail1() ? detail2() : FALSE : general() ) {...}
to say nothing of readability.
Your proposed version is hardly a model of readability either. ;-)
Hmm. You'll want to take that up with the folks responsible for the rex
syntax. :-O
Besides, the correct solution there is just:
if (specific() ?? detail1() detail2() :: general()) {...}
For some value of correct I suppose. Using ??:: within an if/else context
makes my skin crawl, stylistically. :-(
=Austin
Re: Q: Can colons control backtracking in logical expressions?
[EMAIL PROTECTED] (Austin Hastings) writes:
if (specific() ?? detail1() detail2() :: general()) {...}
For some value of correct I suppose. Using ??:: within an if/else context
makes my skin crawl, stylistically. :-(
Ah, then use if!
if (if(specific()) { detail() } else { general() }) {
...
} else {
...
}
--
Complete the following sentence: People *ought* to weigh bricks, cats
and cinnamon in the same units because... - Ian Johnston
Re: Q: Can colons control backtracking in logical expressions?
On Fri, Apr 02, 2004 at 03:05:30PM +0100, Simon Cozens wrote:
: [EMAIL PROTECTED] (Austin Hastings) writes:
:if (specific() ?? detail1() detail2() :: general()) {...}
:
: For some value of correct I suppose. Using ??:: within an if/else context
: makes my skin crawl, stylistically. :-(
:
: Ah, then use if!
:
: if (if(specific()) { detail() } else { general() }) {
: ...
: } else {
: ...
: }
What's that? PL/Ruby?
In Perl 6 that would more clearly be written:
if do { if specific() { detail() } else { general() } } {
...
} else {
...
}
or, of course,
if specific() ?? detail() :: general() {
...
} else {
...
}
Sorry, Perl 6 is just not going to confuse statements and expressions.
A statement is the artificial equivalent of a sentence, and it's no
coincidence that every natural language has something like a sentence
for the purpose of clocking and resynchronizing the discourse.
I think pinning the large-scale control structures to the discourse
structure is a really good idea, both for the computer trying to
decide what error message to spew, and for the person who is going
to have to try to decipher that error message. To break that in
the name of orthogonality ignores the linguistic evidence built up
over many thousands of years. Even an almost purely RPN language
like Japanese likes to use honorifics and/or a bunch of particles to
mark the ends of its sentences, yo?
Larry
Re: Q: Can colons control backtracking in logical expressions?
On Fri, 2004-04-02 at 10:01, Larry Wall wrote:
Even an almost purely RPN language
like Japanese likes to use honorifics and/or a bunch of particles to
mark the ends of its sentences, yo?
Hai, and it's not just there to help in error reporting. Imagine the
case:
if if if if if ... {...} else {...} {...} else {...} {...} else {...}
{...} else {...} {
...
} else {
...
}
so very, very far from readability. Even if you try to indent in some
logical way, it's just painful.
What's more, your,
if specific() ?? detail() :: general() { ... }
is also:
if ((my $s = ?specific()) detail()) || (!$s general()) { ... }
If you prefer to avoid trinary logic constructs directly. I'm not sure
if using the ? there does what I want (which is to strip away any
potential side-effects on $s for when I evaluate it again). It would be
nice to have an un-lazying operator of some sort which could assert a
lack of side-effects as a side-effect.
--
Aaron Sherman [EMAIL PROTECTED]
Senior Systems Engineer and Toolsmith
It's the sound of a satellite saying, 'get me down!' -Shriekback
RE: Q: Can colons control backtracking in logical expressions?
-Original Message-
From: Larry Wall [mailto:[EMAIL PROTECTED]
On Fri, Apr 02, 2004 at 03:05:30PM +0100, Simon Cozens wrote:
: [EMAIL PROTECTED] (Austin Hastings) writes:
:if (specific() ?? detail1() detail2() :: general()) {...}
:
: For some value of correct I suppose. Using ??:: within an
: if/else context makes my skin crawl, stylistically. :-(
:
: Ah, then use if!
:
: if (if(specific()) { detail() } else { general() }) {
: ...
: } else {
: ...
: }
What's that? PL/Ruby?
In Perl 6 that would more clearly be written:
if do { if specific() { detail() } else { general() } } {
...
} else {
...
}
or, of course,
if specific() ?? detail() :: general() {
...
} else {
...
}
Sorry, Perl 6 is just not going to confuse statements and expressions.
A statement is the artificial equivalent of a sentence, and it's no
coincidence that every natural language has something like a sentence
for the purpose of clocking and resynchronizing the discourse.
I think pinning the large-scale control structures to the discourse
structure is a really good idea, both for the computer trying to
decide what error message to spew, and for the person who is going
to have to try to decipher that error message. To break that in
the name of orthogonality ignores the linguistic evidence built up
over many thousands of years.
Or, as per the original:
if specific()
{
if detail()
{
act();
}
}
elsif general()
{
act();
}
Even an almost purely RPN language like Japanese likes to use
honorifics and/or a bunch of particles to mark the ends of its
sentences, yo?
I'm witcha, homie. Word.
However, what I was trying for was not so much destroy the end product of
thousands of years of linguistic evidence, as more of the kind of
abstractions that have happened before. In this case,
A :: in a rex is just a form of 'cut', and 'cut' is a valid expression
modifier, so we'll put the same operators (or similar ones) to use outside
the context of rexen.
=Austin
Backtracking syntax
Backtracking syntax includes:
:, ::, :::, commit, cut
I like the way the ':' looks in patterns. But I noticed I have
several niggles about a number of other aspects of the
above syntax. All the niggles are minor, individually, but
they added up to enough that I thought I'd see what the
bikeshed might look like in another color.
First, the niggles:
1. It's nice how the ':', '::', and ':::' progression indicates
progressively wider scope. But I would be surprised if
newbies don't say to themselves, now just how wide a
scope am I backtracking when there's three colons?.
2. Typo-trap: I can imagine it being fairly easy for some
people to miss, during debugging, both the visual and
behavioral distinction between '::' and ':::'.
3. It seemed odd how the commit and cut assertions
switch to the general ... syntax. I felt like it would be better
if they avoided the general syntax, and preferably had some
family resemblance with the first three backtracking controls.
So, how about something like:
: # lock in current atom, ie as now
:] # lock in surrounding group, currently ::
: # lock in surrounding rule, currently :::
:/ # lock in top level rule, currently commit
:// # cut
Thus, redoing a couple examples from synopsis 5:
m:w/ [ if :] expr block
| for :] list block
| loop :] loop_controls? block
]
rule subname {
([alpha|_] \w*) :/ { fail if %reserved{$1} }
}
m:w/ sub subname? block /
--
ralph
Re: Backtracking syntax
[EMAIL PROTECTED] (Me) writes: 1. It's nice how the ':', '::', and ':::' progression indicates progressively wider scope. But I would be surprised if newbies don't say to themselves, now just how wide a scope am I backtracking when there's three colons?. Why would newbies be writing three-colon regexes? -- dhd even though I know what a 'one time pad' is, it still sounds like a feminine hygiene product.
Re: Backtracking syntax
[EMAIL PROTECTED] (Me) writes: 1. It's nice how the ':', '::', and ':::' progression indicates progressively wider scope. But I would be surprised if newbies don't say to themselves, now just how wide a scope am I backtracking when there's three colons?. Why would newbies be writing three-colon regexes? By newbie I meant it in a relative sense, ie. someone who is learning those particular features. The newbie could be an expert in Prolog and Perl 5. And I'm more concerned about when they are reading some existing patterns than when they are writing one. -- ralph
Re: Backtracking syntax
Backtracking syntax includes: :, ::, :::, commit, cut 1. It's nice how the ':', '::', and ':::' progression indicates progressively wider scope. But I would be surprised if newbies don't say to themselves, now just how wide a scope am I backtracking when there's three colons?. What problem there is? Scopes are atom/group/rule - I don't see any possible misunderstanding there as these scopes are so natural. 2. Typo-trap: I can imagine it being fairly easy for some people to miss, during debugging, both the visual and behavioral distinction between '::' and ':::'. If that really is big problem, it can be solved easily by using proper editor which supports high-lighting. ::: could be shown with different color or bold while :: uses some other syntax. 3. It seemed odd how the commit and cut assertions switch to the general ... syntax. I felt like it would be better if they avoided the general syntax, and preferably had some family resemblance with the first three backtracking controls. So, how about something like: : # lock in current atom, ie as now :] # lock in surrounding group, currently :: : # lock in surrounding rule, currently ::: :/ # lock in top level rule, currently commit :// # cut I find :,::,::: to be a lot easier to remember than :,:],: - and also easier to type. While commit and cut don't follow same syntax, I don't really see any better solutions. Better solution should IMHO keep :,::,::: and offer better alternative only to commit. cut doesn't really belong to this serie as it's different backtracking-operation and so it can and should have different syntax. I wonder if might be usefull instead of commit with proper syntax-highlighting. -- Markus Laire 'malaire' [EMAIL PROTECTED]
Re: Backtracking syntax
[EMAIL PROTECTED] (Markus Laire) writes: While commit and cut don't follow same syntax, I don't really see any better solutions. commit is sufficiently hard that it musn't be confused with the colon series. I wonder if might be usefull instead of commit with proper syntax-highlighting. Yeah. :: should show up in bold, ::: in bold with a red background, and should blink. -- I would imagine most of the readers of this group would support abortion as long as fifty or sixty years after conception for certain individuals - Michael Stevens
Re: Backtracking syntax
On 22 Sep 2002 at 21:06, Simon Cozens wrote: [EMAIL PROTECTED] (Markus Laire) writes: While commit and cut don't follow same syntax, I don't really see any better solutions. commit is sufficiently hard that it musn't be confused with the colon series. Yes, I didn't think that enough. :,::,::: only affects current rule while commit goes further to possibly affect other rules also, so it must have different syntax. -- Markus Laire 'malaire' [EMAIL PROTECTED]
Re: Backtracking syntax
On Sun, Sep 22, 2002 at 01:39:29PM -0500, Me wrote:
So, how about something like:
: # lock in current atom, ie as now
:] # lock in surrounding group, currently ::
: # lock in surrounding rule, currently :::
:/ # lock in top level rule, currently commit
:// # cut
I kinda like it, since :: and ::: look very similar to me, too. (I
don't buy the syntax highlighting argument, partly because I often
encounter code in bw printouts, perlmonks, or wherever.) Though I'd
probably prefer cut stayed cut. And those mismatched brackets
bother me, too. What about
:- :
:: - :[] or [:]
::: - : or :
commit - :// or /:/
cut- :cut or :cut or :cut or just stay cut
Then again, I've never been convinced of the similarity between : and
::. To me, a single colon is modifying another operation, so it's like
the ? non-greedy modifier. Is that incorrect? Everything else does
something when backtracked over; the only thing : has in common with
them is that it has something to do with backtracking.
Btw, is /:/ ambiguous? I can't remember if there's any way a /pattern/
can be followed by a colon.
Staring at the third column above, I can't help wondering if [:cut],
:cut, and /:cut/ would all be useful. But not enough to really think
about it and figure out what they would mean, exactly -- my brain and
cut are still having some marital difficulties.
Thus, redoing a couple examples from synopsis 5:
m:w/ [ if :] expr block
| for :] list block
| loop :] loop_controls? block
]
rule subname {
([alpha|_] \w*) :/ { fail if %reserved{$1} }
}
m:w/ sub subname? block /
m:w/ [ if :[] expr block
| for :[] list block
| loop :[] loop_controls? block
]
rule subname {
([alpha|_] \w*) :// { fail if %reserved{$1} }
}
m:w/ sub subname? block /
or
m:w/ [ if [:] expr block
| for [:] list block
| loop [:] loop_controls? block
]
rule subname {
([alpha|_] \w*) /:/ { fail if %reserved{$1} }
}
m:w/ sub subname? block /
Re: backtracking into { code }
Ken Fox wrote:
A question: Do rules matched in a { code } block set backtrack points for
the outer rule?
I don't believe so. From A5:
A pattern nested within a closure is classified as its own rule,
however, so it never gets the chance to pass out of a {...} closure.
Indeed, to get a rule in a closure to even continue matching from the same
point in the string, you would need to write:
rule expr1 {
term { m:cont/operators/ or fail } term
}
Backtracking would just step back over the rule as if it were atomic
(or followed by a colon).
Damian
Re: backtracking into { code }
Damian Conway wrote:
rule expr1 {
term { m:cont/operators/ or fail } term
}
Backtracking would just step back over the rule as if it were atomic
(or followed by a colon).
Ok, thanks. (The followed by a colon is just to explain the behavior,
right? It's illegal to follow a code block with a colon, isn't it?)
After talking to Aaron yesterday, I was wondering if sub-rules are
meant to backtrack at all.
Does the following example backtrack into foo?
rule foo { b+ }
rule bar { a foo b }
If it doesn't, I think we're restricted to pure LL(1) grammars.
That would suck. Apoc 5 is so close to ANTLR or precc that it would
be a shame not to be LL(k).
I've been playing around with converting regex operators into
Perl 6 attribute grammars and they look good. If backtracking into
rules doesn't work though, these conversions don't work.
a ?rule x { a | null }
a *rule x { a x | null }
a +rule x($i=0) { a x($i+1) | ($i0) null }
a {n,m}rule x($i=0) { ($i$m) a x($i+1) | ($i=$n) null }
The non-greedy versions just reverse the productions, so for example
a *? rule x { null | a x }
- Ken
Re: backtracking into { code }
[NOTE: BCCing off-list to protect private email addresses]
On Fri, 2002-08-30 at 09:07, Ken Fox wrote:
Does the following example backtrack into foo?
rule foo { b+ }
rule bar { a foo b }
This was the bit that got me on-board. I did not see the need for
backtracking into rules until he pulled out that darn C+. Until then I
was convinced that you could just step over the sub-rule in backtracking
and treat it as atomic. Lack of formal education is biting me here. :(
I await the response with interest.
Re: backtracking into { code }
On Fri, 30 Aug 2002, Ken Fox wrote:
: Ok, thanks. (The followed by a colon is just to explain the behavior,
: right? It's illegal to follow a code block with a colon, isn't it?)
I don't see why it should be illegal--it could be useful if the closure
has played continuation games of some sort to get backtracking.
In the normal case it's a no-op, since closures don't normally get
control back when backtracked over.
: After talking to Aaron yesterday, I was wondering if sub-rules are
: meant to backtrack at all.
:
: Does the following example backtrack into foo?
:
:rule foo { b+ }
:rule bar { a foo b }
Yes, it must. It's only rules embedded in closures that are exempt
by default, I think.
Larry
Re: backtracking into { code }
Larry Wall wrote: On Fri, 30 Aug 2002, Ken Fox wrote: : Ok, thanks. (The followed by a colon is just to explain the behavior, : right? It's illegal to follow a code block with a colon, isn't it?) I don't see why it should be illegal--it could be useful if the closure has played continuation games of some sort to get backtracking. Apoc 5 has It is an error to use : on any atom that does no backtracking. Code blocks don't backtrack (at least that's what I understood Damian to say). Are zero width atoms treated specially? And can you give me an example of a continuation game? That sounds sort of like my original question. Great news about backtracking into sub-rules. Perl 6 is going to be a lovely system to work with. I think it's going to suffer a bit from the same declarative-face vs procedural-heart** that Prolog does, but it hits the little language target perfectly. - Ken ** Prolog uses a cut (!) operator to control backtracking just like Perl 6. A big problem (at least for me...) is learning when ! just makes things run faster vs. when ! gives me the wrong answer. Maybe I just haven't used Prolog enough to get my brain wrapped around it.
Re: backtracking into { code }
On Fri, 30 Aug 2002, Ken Fox wrote: : Apoc 5 has It is an error to use : on any atom that does no : backtracking. Code blocks don't backtrack (at least that's what : I understood Damian to say). Code blocks don't backtrack *by default*. But you can do anything in a closure. : Are zero width atoms treated specially? Code blocks are zero width *by default*. But you can do anything in a closure. : And can you give me an example of a continuation game? That sounds : sort of like my original question. Nope. I don't understand continuations. :-) : Great news about backtracking into sub-rules. Perl 6 is going to : be a lovely system to work with. I think it's going to suffer a bit : from the same declarative-face vs procedural-heart** that Prolog : does, but it hits the little language target perfectly. There's a famous book called Golf is Not a Game of Perfect. : ** Prolog uses a cut (!) operator to control backtracking just like : Perl 6. A big problem (at least for me...) is learning when ! just : makes things run faster vs. when ! gives me the wrong answer. Maybe : I just haven't used Prolog enough to get my brain wrapped around it. The purists would say that the cut operator is always the wrong answer even when it gives the right answer. I am not a purist. In case you hadn't noticed... Larry
Re: backtracking into { code }
Larry Wall wrote: There's a famous book called Golf is Not a Game of Perfect. Well now I'm *totally* confused. I looked that up on Amazon and it has something to do with clubs and grass and stuff. That's completely different than what I thought golfing was. ;) Seriously, though. I have a positive and confident outlook that Perl 6 will be a lovely system for hacking grammars. - Ken
backtracking into { code }
A question: Do rules matched in a { code } block set backtrack points for
the outer rule? For example, are these rules equivalent?
rule expr1 {
term { /operators/ or fail } term
}
rule expr2 {
term operators term
}
And a comment: It would be nice to have procedural control over back-
tracking so that { code } can fail, succeed (not fail), or succeed and
commit. Right now we can follow { code } with ::, :::, etc. but that does
not allow much control. I'm a little afraid of what happens in an LL(Inf)
grammar if backtracking states aren't aggressively pruned.
- Ken
Re: backtracking into { code }
On Thu, 2002-08-29 at 08:05, Ken Fox wrote:
A question: Do rules matched in a { code } block set backtrack points for
the outer rule? For example, are these rules equivalent?
rule expr1 {
term { /operators/ or fail } term
}
rule expr2 {
term operators term
}
And a comment: It would be nice to have procedural control over back-
tracking so that { code } can fail, succeed (not fail), or succeed and
commit. Right now we can follow { code } with ::, :::, etc. but that does
not allow much control. I'm a little afraid of what happens in an LL(Inf)
grammar if backtracking states aren't aggressively pruned.
Well, if /.../ is returning a result object (Let's say
CORE::RX::Result), then I would imagine it's an easy enough thing to let
you create your own, or return the one from a rule that you invoke.
e.g.:
rule { term { /operators/.commit(1) or fail } term }
The hypothetical commit() method being one that would take a number and
modify the result object so that it commits as if you had used that many
colons.
{} inside a rule would, I imagine be implemented like so:
sub rxbraces ($code) {
my $stat = $code();
if $stat.isa(CORE::RX::Result) {
return $stat;
} else {
my $r is CORE::RX::Result;
$r.success($stat); # Boolean status-setting method
return $r;
}
}
Or the moral equiv In other words, it should be able to return a
result of your choosing.
Sorry if I've missed some of the design. My Perl 6 pseudo-code may not
be legal.
Re: backtracking into { code }
Aaron Sherman wrote:
rule { term { /operators/.commit(1) or fail } term }
The hypothetical commit() method being one that would take a number and
That would only be useful if the outer rule can backtrack into the
inner /operators/ rule. Can it?
I agree with you that a commit method would be useful -- especially when
used on $self. I'd probably write your example as:
rule { term { m/operators { $self.commit(1) }/ or fail } term }
which is of course just a complicated
rule { term { m/operators :/ or fail } term }
BTW, why isn't fail a method? Then a rule could pass itself to a sub-rule
and allow the sub-rule to fail it's parent, but not the entire match. Isn't
failing just invoking the last continuation on the backtrack stack?
- Ken
Re: backtracking into { code }
On Thu, 2002-08-29 at 10:28, Ken Fox wrote:
Aaron Sherman wrote:
rule { term { /operators/.commit(1) or fail } term }
The hypothetical commit() method being one that would take a number and
That would only be useful if the outer rule can backtrack into the
inner /operators/ rule. Can it?
Of course not. In the same way that
rule foo { b }
rule bar { a foo+ b }
abb =~ /bar/
would not. You backtrack OVER it, and that's when your commit (of
whatever degree) would come into play.
I agree with you that a commit method would be useful -- especially when
used on $self. I'd probably write your example as:
rule { term { m/operators { $self.commit(1) }/ or fail } term }.
which is of course just a complicated
rule { term { m/operators :/ or fail } term }
There's no way that can affect anything, as : doesn't affect calling
rules, e.g.:
rule foo { b : }
rule bar { a foo+ b }
abb =~ /bar/
will match, because the foo rule never needs to backtrack. If foo had
used C commit , then you'd fail, but that's a horse of a different
animal.
The goal was to dynamically cause backtracking over inline code to fail.
Re: RFC 104 (v1) Backtracking
hi,
So how is that different from:
do BLOCK1 until do BLOCK2
It's the same.
But the real fun starts when blocks and functions can suspend and
resume.
{ ...
# Return value and suspend.
suspend $i;
# Next iteration will resume here
...
} andthen { ... };
-- Johan
]- BIG GREEN hm
I will say wrong point of view. Why ?
You are looking at this code at "Procedure semantic side" of view.
Let'see how this look to me... "declarative guy" :")
"Suspend" works for me like "INBLOCK CUT".
I will ask what will happen in recursive block if you place the "end
conditions" before suspend :")
=
iVAN
[EMAIL PROTECTED]
=
Re: RFC 104 (v1) Backtracking :ref
=head1 REFERENCE Icon language brief intro : http://www.cs.arizona.edu/icon/intro.htm
Re: RFC 104 (v1) Backtracking
Jonathan Scott Duff wrote: On Tue, Aug 15, 2000 at 05:47:53PM -0600, Nathan Torkington wrote: I want @result = @a || @b; to be like: (@result = @a) or (@result = @b); That's what all my students keep expecting it to mean. And that's what I keep wishing it meant too. -Scott -- Jonathan Scott Duff [EMAIL PROTECTED] So we want to define operator||, in a list context, operating on two lists, to choose between them and return a list, rather than imposing scalar context. We want ( LHS || RHS ) to mean, ( LHS-BOOLEAN() ? LHS : RHS ) Correct? -- David Nicol 816.235.1187 [EMAIL PROTECTED] Does despair.com sell a discordian calendar?
Re: Component wise || and RFC 82 (was Re: RFC 104 (v1) Backtracking)
On Tue, Aug 15, 2000 at 10:26:13PM -0600, Nathan Torkington wrote: I like the idea of adding the context-aware operators, but I don't think I'd use them as often as I use "the number of things in the array". I think most Perl programmers would be in the same camp. Unless you can show a couple of cool things that this makes possible, that is. So I'd say: option, yes. Default, no. I also like the idea of context-aware operators. I don't know if I like them enough to want to break with former practice, but I do know that I don't like the idea of making them optional. This would be the mother of all action-at-a-distance hells: set_size(@elts * 5); # size = Five times the number of elements. set_size(@elts * 5); # $size = The number of elements -- someone # turned on context-sensitive operators, # 2000 lines above here. I don't know what the right thing to do is. Context is crypto enough these days, without shifting the rules on operator contexts around. Perhaps the benefits outweigh the breakage that will occur. - Damien
Uses for array notation (was Re: RFC 104 (v1) Backtracking)
Mark Cogan wrote:
At 12:39 PM 8/16/00 +1000, Jeremy Howard wrote:
It seems obvious that @a should be the whole array @a, not the size of
the
array. If I want to check the size of @a, I should have to do so
explicitly,
with scalar or $#.
This is non-obvious if you think that || is a flow control statement, so
think about * for a moment:
@c = @b * @a;
But, to me at least, arrays aren't something you multiply. Multiplication
applies to numbers (scalars), and returns a scalar, so when you see
@c = @b * @a
it should be clear that something funny is going on.
Well, they're not something you multiply in Perl now. But there's plenty of
languages where you can, and it's ever so convenient.
And, really, what is wrong with:
@c = map {$a[$_] * $b[$_]} (0..$#a);
Numerical programming is all about manipulating arrays (or n-dim tensors,
but they're just order array slices really). Writing such programs in a
language that requires explicit loops is not only a pain, but creates code
that bears no resemblance to the numeric algorithm it's implementing.
Furthermore, it's out of the question in anything other than low-level
languages, because the looping and array dereferencing is much too slow.
It also makes easy things easy:
@full_names = @first_names . @surnames;
and with the extension to scalars as one operand (coming in v2!):
@quoted_lines = ' ' . @raw_lines;
or
@histogram = '#' x @num_recs;
It's pretty clear what working on 'the whole array' means here, I think.
I disagree. In particular, think of it from the point of view of someone
who hasn't studied computer science.
What should:
@a = defined @a;
return?
defined() is a function. Under the proposed extension of RFC 82 from
operators to functions, this example should return a list of booleans, where
each is true if the corresponding element of the original list was defined.
Under Perl 5.6, 'defined @a' is deprecated. This RFC would give it a useful
meaning (in a list context).
Treating || as a special case is asking for trouble. If you want a flow
control statement, use one:
@result = @b unless @result = @a;
|| may be a suboptimal example, but I think the idea that a @-variable
without an iteration function refers to the array as a whole, and not its
elements is an intuitive one, and having array iteration magically happen
when you're not looking is dangerous.
It seems funny if you're not used to it. But that's because we learn that
lists are hard, and computers have to loop. After just a little unlearning
it actually becomes quite intuitive, and is generally picked up with no
additional trouble by new students. Programmers shouldn't have to know how a
computer implements things behind the scenes--which is really what requiring
explicit looping forces.
Array notation (was Re: RFC 104 (v1) Backtracking)
Mark Cogan wrote:
At 11:11 PM 8/15/00 -0400, Chaim Frenkel wrote:
You are missing the beauty of vector/matrix operations.
No, I'm not; I'm opining that the vast majority of Perl users don't need
to
do vector/matrix ops, and that they don't belong in the core.
The vast majority of Perl 5 users don't, because it's a pain in Perl 5. They
use other languages instead, but those other languages aren't nearly as nice
as Perl in almost every other way. Why not open up Perl for a whole new
class of folks?
The math folks
really would like to be able to describe the operation wanted and have
perl do the optimization.
Then maybe they should use a dedicate math extension to Perl, like PDL.
You've got to be joking! You think PDL is a simple convenient add-on to Perl
that provides these features? It's not! PDL is an astonishing hack by some
incredibly clever people, but it still _does_not_ support array notation,
and optimised loops have to be written in yet *another* language named PP,
which is compiled into C by a special compiler, and linked into the program.
This is the absolute best that can be done right now, and the PDL folks
deserve a medal for what they've achieved. But really, no-one should have to
jump through these kinds of hoops!
Would adding another character be helpful
@result = @a x|| @b?
@result = @a ||| @b?
or perhaps a modifier?
@result = @a || @b forall;
(Blech, that just doesn read right.)
Perhaps we just need a two-list map, which aliases $a and $b like sort():
@result = map {$a || $b} @a,@b;
No. It would need to be n-list, and it would have to handle slices and
lazily generated lists incredibly cleverly. map is too generic to easily
make the kinds of optimisations required for array notation.
I don't know how to convince you here. There's a feature that, if added to
Perl, would make my life and many of my collegues lives easier. I know this
for a fact because I've used it elsewhere. I doesn't break much that can't
fairly easily be incorporated into P52P6, it's a generic abstraction that
applies to many things other than numeric programming (it's great for string
manipulation!), and it's proved itself elsewhere.
I'm not ruling out a modifier, as Chaim outlined, although I agree that the
word 'blech' comes to mind. But this is too good an opportunity to see it
just disappear. Have a look at the examples in RFCs 23, 76, 81, 82, 90, and
91, which combine together to provide as strong a data manipulation language
as you'll find anywhere. Over the next few days I'll be updating these to
include more examples, particularly non-numeric ones.
Re: RFC 104 (v1) Backtracking
There's also the cut operator which I didn't see mentioned in the RFC.
It blocks backtracking so that something like this:
B1 andthen B2 andthen cut B3 andthen B4 andthen B5
wouldn't backtrack to B2 once it forwardtracked to B3.
]- I tried minimalistic approach as small as possible additions to the Perl
language, we get only the "backtrack" mechanism i.e. something that is
harder or slower to be done outside of the perl core.
The rest should be done outside . (I too want all in the core)
Example :
my $cutState = 0;
{
{ block1 } andthen { block2 } andthen { block3 } andthen
if ($cutState) { last AFTER}
else { $cutState = 1}; 1;
}
andthen { block4 } andthen { block5 };
}
AFTER:
code
not sure will this also do the job :
{ $cutState = $cutState ? last AFTER : 1 } .
So the CUT is candidate for module. Offcourse I preffer all syntax to be
embeeded, cut,fail ... but if I tried in this way there is smaller chance
this to get in the core ..
Think, it is only around 10 lines of code to be added in perly.y i.e. 10
lines C code in Perl-core.
Mainwhile CUT is small too :")
Okay, the more I think about it, the more I think it should be a
module.
]- How this can be done as module ?
=
iVAN
[EMAIL PROTECTED]
=
Re: RFC 104 (v1) Backtracking
They behave similarly like , ||, and, or operator with one main
distinction they "backtrack" for example:
{ block1 } Bandthen { block2 };
This would be a good use of the to-be-liberated = operator:
{ block1 } = { block2 };
In any case, "andthen" doesn't seem like a good choice.
Other possibilities:
therefore
implies
segue
seq
so
]- any proposal for the name are welcomethey must be two. the
reason I decided to use this is cause it works like/is similar to -
if-then-else, also look like and/or comparions operator.
The Prolog operators "," and ";" are already overused in perl.
THEN is not used by PERL, so here comes :
AND+THEN
OR+THEN
:")
=
iVAN
[EMAIL PROTECTED]
=
Re: RFC 104 (v1) Backtracking
raptor wrote: ]- I tried minimalistic approach as small as possible additions to the Perl language, we get only the "backtrack" mechanism i.e. something that is harder or slower to be done outside of the perl core. The rest should be done outside . (I too want all in the core) I don't know if you noticed the earlier thread, but there's a few people (including myself) who are still having trouble understanding how your proposal works. Could you please provide a brief idiomatic example of some code where this proposal would provide a real practical benefit--enough that slow learners like myself can really understand what it makes easier, and how? It would be great if you could provide the equivalent Perl 5 code too. TIA, Jeremy
Re: RFC 104 (v1) Backtracking
Johan Vromans wrote: Damian Conway [EMAIL PROTECTED] writes: As I understand things: BLOCK1 andthen BLOCK2 evaluates BLOCK1 and then if BLOCK1 evaluates to "true" evaluates BLOCK2. If BLOCK2 evaluates to "true" we're done. If BLOCK2 evaluates to "false", then BLOCK1 is re-evaluated. So how is that different from: do BLOCK1 until do BLOCK2 It's the same. But the real fun starts when blocks and functions can suspend and resume. There's already an RFC for coroutines that proposes allowing suspension and resumption of subroutines. Do the proposed backtracking operators buy anything that do/until/coroutines don't provide?
Re: RFC 104 (v1) Backtracking
"MC" == Mark Cogan [EMAIL PROTECTED] writes: is equivalent to @a = (\$a, \$b, \$c); rather than what you wrote. MC Ah, so it is. I'd argue that that's broken and should be handled with map MC or for. Err, That's not an accident. Larry designed that in. chaim -- Chaim FrenkelNonlinear Knowledge, Inc. [EMAIL PROTECTED] +1-718-236-0183
Re: RFC 104 (v1) Backtracking
Damian Conway wrote:
So how is that different from:
do BLOCK1 until do BLOCK2
???
Because if BLOCK1 ever evaluates to False, the operation terminates.
It's more like
do { r = f1() } until ( not r or f2() );
--
John Porter
Re: RFC 104 (v1) Backtracking
On Wed, Aug 16, 2000 at 07:42:33PM +1000, Jeremy Howard wrote:
raptor wrote:
]- I tried minimalistic approach as small as possible additions to the
Perl
language, we get only the "backtrack" mechanism i.e. something that is
harder or slower to be done outside of the perl core.
The rest should be done outside . (I too want all in the core)
I don't know if you noticed the earlier thread, but there's a few people
(including myself) who are still having trouble understanding how your
proposal works.
Could you please provide a brief idiomatic example of some code where this
proposal would provide a real practical benefit--enough that slow learners
like myself can really understand what it makes easier, and how? It would be
great if you could provide the equivalent Perl 5 code too.
Here's some perl psuedo code that'll implement the "andthen" semantics:
BLOCK1 andthen BLOCK2 andthen BLOCK3 andthen BLOCK4
B1: if (BLOCK1) {
B2: if (BLOCK2) {
B3: if (BLOCK3) {
B4: if (BLOCK4) {
return "true"
} else { goto B3 }
} else { goto B2 }
} else { goto B1 }
}
return "false"
The semantics for "orthen" are similar:
BLOCK1 orthen BLOCK2 orthen BLOCK3 orthen BLOCK4
B1: unless (BLOCK1) {
B2: unless (BLOCK2) {
B3: unless (BLOCK3) {
B4: unless (BLOCK4) {
return "false"
} else { goto B3 }
} else { goto B2 }
} else { goto B1 }
}
return "true"
As for examples where this would be of benefit ... I really can't think
of any.
-Scott
--
Jonathan Scott Duff
[EMAIL PROTECTED]
Re: RFC 104 (v1) Backtracking
Johan Vromans wrote: So how is that different from: do BLOCK1 until do BLOCK2 It's the same. No, not quite. See my other post. -- John Porter
Re: RFC 104 (v1) Backtracking
iVAN Georgiev [EMAIL PROTECTED]:
They behave similarly like , ||, and, or operator with one main
distinction they "backtrack" for example:
{ block1 } Bandthen { block2 };
This would be a good use of the to-be-liberated = operator:
{ block1 } = { block2 };
In any case, "andthen" doesn't seem like a good choice.
Other possibilities:
therefore
implies
segue
seq
so
--
John Porter
Re: RFC 104 (v1) Backtracking
On Wed, Aug 16, 2000 at 08:26:26AM +1000, Jeremy Howard wrote: Doesn't RFC 82 (Make operators behave consistantly in a list context) provide this functionality? This is perfectly valid under that proposal: @result = @a || @b; Which applies '||' component-wise to elements of @a and @b, placing the result in @result. I'm no Prolog guru, so feel free to correct me if I'm missing something here. I think you're missing the backtracking part (I'm no guru either). As I understand things: BLOCK1 andthen BLOCK2 evaluates BLOCK1 and then if BLOCK1 evaluates to "true" evaluates BLOCK2. If BLOCK2 evaluates to "true" we're done. If BLOCK2 evaluates to "false", then BLOCK1 is re-evaluated. Er, let me see if I can write the logic better: 1. eval BLOCK1 2. if "false", stop, else goto 3 3. eval BLOCK2 4. if "true", stop, else goto 1 It's kind of an all-or-nothing expression with side effects (evaluating the blocks). This sort of logic can be extended to N blocks too. Though I think if we're going to support backtracking like this, we'll need to support the cut operator as well (! in prolog) (Note the only prolog I've done was about 10 years ago for about 2 weeks and about 2 years ago for 2 or 3 weeks in a programming languages class at a university) -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
Re: RFC 104 (v1) Backtracking
As I understand things: BLOCK1 andthen BLOCK2 evaluates BLOCK1 and then if BLOCK1 evaluates to "true" evaluates BLOCK2. If BLOCK2 evaluates to "true" we're done. If BLOCK2 evaluates to "false", then BLOCK1 is re-evaluated. So how is that different from: do BLOCK1 until do BLOCK2 ???
Re: RFC 104 (v1) Backtracking
Jeremy Howard writes: @result = @a || @b; Which applies '||' component-wise to elements of @a and @b, placing the result in @result. *Ptui* That's not how *I* want || to behave on lists/arrays. I want @result = @a || @b; to be like: (@result = @a) or (@result = @b); That's what all my students keep expecting it to mean. Nat
Component wise || and RFC 82 (was Re: RFC 104 (v1) Backtracking)
Nathan Torkington wrote: Jeremy Howard writes: @result = @a || @b; Which applies '||' component-wise to elements of @a and @b, placing the result in @result. *Ptui* That's not how *I* want || to behave on lists/arrays. I want @result = @a || @b; to be like: (@result = @a) or (@result = @b); That's what all my students keep expecting it to mean. Note that RFC 82 (http://tmtowtdi.perl.org/rfc/82.pod) proposes that _all_ operators behave the same way in a list context. To me, this consistancy would be a real win. The behaviour you're discussing is described in RFC 45. RFC 45 proposes a special case for the || operator, which is only using its short-circuiting functionality, not its 'or' functionality. In this case I would think that using an explicit 'if' would be more appropriate. I'm working with the maintainer of RFC 45 at the moment to see if we can get the consistency of component-wise behaviour in a list context without losing the ability to short-circuit in an assignment. A potential compromise would be to say that RFC 82 only applies to operators that do not short-circuit. However, my view is that the loss of consistency through such a step would be a substantial source of confusion. It would also mean that overloaded operators with a lazily evaluated parameter would not work in a consistent manner.
Re: RFC 104 (v1) Backtracking
At 05:47 PM 8/15/00 -0600, Nathan Torkington wrote: Jeremy Howard writes: @result = @a || @b; Which applies '||' component-wise to elements of @a and @b, placing the result in @result. *Ptui* That's not how *I* want || to behave on lists/arrays. I want @result = @a || @b; to be like: (@result = @a) or (@result = @b); That's what all my students keep expecting it to mean. Seconded. It seems obvious that @a should be the whole array @a, not an iteration over its elements. If I want to iterate over @a, I should have to do so explicitly, with a for() or map(). --- Mark Cogan[EMAIL PROTECTED] +1-520-881-8101 ArtToday www.arttoday.com
Re: RFC 104 (v1) Backtracking
At 12:39 PM 8/16/00 +1000, Jeremy Howard wrote:
Mark Cogan wrote:
At 05:47 PM 8/15/00 -0600, Nathan Torkington wrote:
Jeremy Howard writes:
@result = @a || @b;
Which applies '||' component-wise to elements of @a and @b, placing
the
result in @result.
*Ptui* That's not how *I* want || to behave on lists/arrays.
I want
@result = @a || @b;
to be like:
(@result = @a) or (@result = @b);
That's what all my students keep expecting it to mean.
Seconded.
It seems obvious that @a should be the whole array @a, not an iteration
over its elements. If I want to iterate over @a, I should have to do so
explicitly, with a for() or map().
It seems obvious that @a should be the whole array @a, not the size of the
array. If I want to check the size of @a, I should have to do so explicitly,
with scalar or $#.
This is non-obvious if you think that || is a flow control statement, so
think about * for a moment:
@c = @b * @a;
But, to me at least, arrays aren't something you multiply. Multiplication
applies to numbers (scalars), and returns a scalar, so when you see
@c = @b * @a
it should be clear that something funny is going on.
And, really, what is wrong with:
@c = map {$a[$_] * $b[$_]} (0..$#a);
?
(or, for that matter:
push @c, $a[$_] * $b[$_] for (0..$#a);
)
in both cases it's clear that you're iterating over the elemnts in the array.
It's pretty clear what working on 'the whole array' means here, I think.
I disagree. In particular, think of it from the point of view of someone
who hasn't studied computer science.
What should:
@a = defined @a;
return?
Treating || as a special case is asking for trouble. If you want a flow
control statement, use one:
@result = @b unless @result = @a;
|| may be a suboptimal example, but I think the idea that a @-variable
without an iteration function refers to the array as a whole, and not its
elements is an intuitive one, and having array iteration magically happen
when you're not looking is dangerous.
---
Mark Cogan[EMAIL PROTECTED] +1-520-881-8101
ArtToday www.arttoday.com
Re: RFC 104 (v1) Backtracking
You are missing the beauty of vector/matrix operations. The math folks really would like to be able to describe the operation wanted and have perl do the optimization. Would adding another character be helpful @result = @a x|| @b? @result = @a ||| @b? or perhaps a modifier? @result = @a || @b forall; (Blech, that just doesn read right.) chaim "MC" == Mark Cogan [EMAIL PROTECTED] writes: MC At 05:47 PM 8/15/00 -0600, Nathan Torkington wrote: Jeremy Howard writes: @result = @a || @b; Which applies '||' component-wise to elements of @a and @b, placing the result in @result. *Ptui* That's not how *I* want || to behave on lists/arrays. I want @result = @a || @b; to be like: (@result = @a) or (@result = @b); That's what all my students keep expecting it to mean. MC Seconded. MC It seems obvious that @a should be the whole array @a, not an iteration MC over its elements. If I want to iterate over @a, I should have to do so MC explicitly, with a for() or map(). -- Chaim FrenkelNonlinear Knowledge, Inc. [EMAIL PROTECTED] +1-718-236-0183
Re: RFC 104 (v1) Backtracking
At 11:11 PM 8/15/00 -0400, Chaim Frenkel wrote:
You are missing the beauty of vector/matrix operations.
No, I'm not; I'm opining that the vast majority of Perl users don't need to
do vector/matrix ops, and that they don't belong in the core.
The math folks
really would like to be able to describe the operation wanted and have
perl do the optimization.
Then maybe they should use a dedicate math extension to Perl, like PDL.
Would adding another character be helpful
@result = @a x|| @b?
@result = @a ||| @b?
or perhaps a modifier?
@result = @a || @b forall;
(Blech, that just doesn read right.)
Perhaps we just need a two-list map, which aliases $a and $b like sort():
@result = map {$a || $b} @a,@b;
---
Mark Cogan[EMAIL PROTECTED] +1-520-881-8101
ArtToday www.arttoday.com
Re: RFC 104 (v1) Backtracking
"MC" == Mark Cogan [EMAIL PROTECTED] writes: MC What should: MC @a = defined @a; MC return? Counter example:@a = \($a, $b, $c); (Not really a full fledged counter example since it is a liter list.) Treating || as a special case is asking for trouble. If you want a flow control statement, use one: @result = @b unless @result = @a; MC || may be a suboptimal example, but I think the idea that a @-variable MC without an iteration function refers to the array as a whole, and not its MC elements is an intuitive one, and having array iteration magically happen MC when you're not looking is dangerous. Not unless you are coming from a math background or are an old basic programmer, and would like to have matrix operations built in. chaim -- Chaim FrenkelNonlinear Knowledge, Inc. [EMAIL PROTECTED] +1-718-236-0183
Re: RFC 104 (v1) Backtracking
At 11:43 PM 8/15/00 -0400, Chaim Frenkel wrote: "MC" == Mark Cogan [EMAIL PROTECTED] writes: MC What should: MC @a = defined @a; MC return? Counter example:@a = \($a, $b, $c); I guess I'm missing the point; how is this different from @a = [$a,$b,$c]; which works to be the same as push @a, [$a,$b,$c]; ? [] MC || may be a suboptimal example, but I think the idea that a @-variable MC without an iteration function refers to the array as a whole, and not its MC elements is an intuitive one, and having array iteration magically happen MC when you're not looking is dangerous. Not unless you are coming from a math background or are an old basic programmer, and would like to have matrix operations built in. But we're trying to decide what is best for perl as a whole, not just what is good for math people who use perl. I don't think that the requirement that a relatively small portion of the user base put : use magical_array_iteration; at the top of their code is too outre. (and, for that matter, it might be nice to have an environment variable that implicitly sets -M command line options in the same way that PER5LIB sets -I. That way, math types can just set their perls to preload all the modules they want.) --- Mark Cogan[EMAIL PROTECTED] +1-520-881-8101 ArtToday www.arttoday.com
Re: RFC 104 (v1) Backtracking
On Tue, Aug 15, 2000 at 08:59:25PM -0700, Mark Cogan wrote: At 11:43 PM 8/15/00 -0400, Chaim Frenkel wrote: Counter example:@a = \($a, $b, $c); I guess I'm missing the point; how is this different from @a = [$a,$b,$c]; Well, I've lost the point of this thread, but @a = \($a, $b, $c); is equivalent to @a = (\$a, \$b, \$c); rather than what you wrote. -Scott -- Jonathan Scott Duff [EMAIL PROTECTED]
Re: RFC 104 (v1) Backtracking
At 11:05 PM 8/15/00 -0500, Jonathan Scott Duff wrote: On Tue, Aug 15, 2000 at 08:59:25PM -0700, Mark Cogan wrote: At 11:43 PM 8/15/00 -0400, Chaim Frenkel wrote: Counter example:@a = \($a, $b, $c); I guess I'm missing the point; how is this different from @a = [$a,$b,$c]; Well, I've lost the point of this thread, but @a = \($a, $b, $c); is equivalent to @a = (\$a, \$b, \$c); rather than what you wrote. Ah, so it is. I'd argue that that's broken and should be handled with map or for. --- Mark Cogan[EMAIL PROTECTED] +1-520-881-8101 ArtToday www.arttoday.com
RFC 104 (v1) Backtracking
This and other RFCs are available on the web at
http://dev.perl.org/rfc/
=head1 TITLE
Backtracking
=head1 VERSION
Maintainer: iVAN Georgiev [EMAIL PROTECTED]
Date: 14 Aug 2000
Version: 1
Mailing List: [EMAIL PROTECTED]
Number: 104
=head1 ABSTRACT
Backtraking mechanism is core functionality of languages like PROLOG.
Perl-regex engine has this ability too.
Adding this mechanism to our programming arsenal will bring alot of
new functionality. Will help us solve problems that otherwise cost us
alot of time and effort (laziness).
A new paradigm to Perl - DECLARATIVE programming.
=head1 DESCRIPTION
The whole gang-bang can be done with only two new operators: andthen, orthen.
They behave similarly like , ||, and, or operator with one main
distinction they "backtrack" for example:
{ block1 } Bandthen { block2 };
mean this:
if "block1" return true(1) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
but if "block1" return false(0) the end result is false(0)
or to be more clear this is the Perl equivalent/example:
my $res = 0;
{
my $ex1;
{ $l = (rand() 0.3) ? 1:0;print "block1=$l\n"; $ex1=$l};
if ($ex1)
{
my $ex2;
{ $r = (rand() 0.7) ? 1:0;print "block2=$r\n"; $ex2=$r};
if ($ex2) { $res = 1 } else { redo }
};
};
print "The result is : $res\n";
Similarly "orthen":
{ block1 } Borthen { block2 };
mean this:
if "block1" return true(1) the end result is true(1)
but if "block1" return false(0) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
OR this:
if "block1" return true(1)
we evaluate "block2" and return true(1)
w/o taking in consideration the result of "block2" evaluation.
but if "block1" return false(0) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
=head2 USAGE
Good candidates for "backtracking" are XML processors,
analytical "permutations!", expert systems and many more...
Cycle:
my $i = 0;
{$i++; $i = 10 } andthen {print $i};
equivalent to:
for (my $i=1;$i++;$i=10) {print $i};
=head2 FURTHER WORK
As you saw I tried to propose as small change to the perl
core/language as possible, which can be easily implemented.
What else we can expect?
One good addition that can we thought about is implementing
the Perl BLOCK's as forth-state BLACKBOX structure not as
it is now i.e. two states, what I mean ?
Currently AFAIK we have "entering" and "leaving" the block.
We can have "direction" i.e. with "backtrack" mechanism we
can enter the block from previous block or from the next one -
the four "states" are - enter(-),leave(-),reevaluate(-),fall(-),
we will need also to count how many times the block has been
in all of these states. We can leave the old behaviour as
default(in the name of speed) and only when the Perl programmer
need these states to use "state" pragma.
use state "2";
use state "4";
BUT this will be alot of work, so for now andthen, orthen
are enough. If backtracking is made as more general algorithm
it can be used both by Perl itself and regex engine ?!!
=head1 IMPLEMENTATION
There is many possible implementations one of them you saw
in DESCRIPTION section, it can also be implemented as
while, until cycle...
If I was perl-core hacker you now will be reading
and applying the patch :"), I believe that this can be very
easily implemented as just adding several lines in perly.y
(please excuse my ignorance if this is not the case)
=head1 REFERENCES
perldoc perlre
The Prolog Language:
http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_10.html
Coroutining facilities:
http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_8.html
