World: r3wp

Brian, what do you think about this?

match: func [block rule /local recurse result] [
    result: false
    parse block recurse: [
        some [
            rule (result: true)
            |
            into recurse
            |
            skip
        ]
    ]
    result
]

example:

qml-test: [
    qml
    [toc

        [toc-title [font opts [face "georgia"] "Table of contents"]]
        [h1 [font opts [face "georgia"] "one"]]

        [para [font opts [face "georgia"] "bla " [font opts [face "times"] 
        "bla"]]]

        [h1 [font opts [face "georgia"] [font opts [face "times"] "two"]]]

        [para [font opts [face "georgia"] [font opts [face "times"] "bla 
        bla"]]]
        [olist

            [oitem [font opts [face "georgia"] [font opts [face "times"] "one"] 
            " cont"]]
            [oitem [font opts [face "georgia"] "two"] " cont"]
            [oitem "three"]
        ]
        [h1 "three"]
        [para "bla bla"]
        [h3 "four"]
        [para "bla bla"]
        [h1 "five"]
        [h2 "six"]
        [h2 "seven"]
    ]
]

>> match qml-test [x: ['h1 | 'h2 | 'h3] to end (probe x)]
[h1 [font opts [face "georgia"] "one"]]

[h1 [font opts [face "georgia"] [font opts [face "times"] "two"]]]
[h1 "three"]
[h3 "four"]
[h1 "five"]
[h2 "six"]
[h2 "seven"]
== true

>> match qml-test [x: 'font to end (probe x)]
[font opts [face "georgia"] "Table of contents"]
[font opts [face "georgia"] "one"]

[font opts [face "georgia"] "bla " [font opts [face "times"] "bla"]]
[font opts [face "georgia"] [font opts [face "times"] "two"]]
[font opts [face "georgia"] [font opts [face "times"] "bla bla"]]

[font opts [face "georgia"] [font opts [face "times"] "one"] " cont"]
[font opts [face "georgia"] "two"]
== true

Interesting. It would work with my XML data structure, assuming I 
used a block for the attributes rather than a hash (something I considered 
anyway).

you can also build rewrite on top of it:

rewrite: func [block rules /local rules* rule flag mk1 mk2 prod] 
[
    if empty? rules [return block]
    rules*: make block! 16
    foreach [pattern production] rules [

        insert insert/only insert/only tail rules* pattern make paren! compose/only 
        [
            prod: compose/deep (production)
        ] '|
    ]
    remove back tail rules*
    until [
        ;probe block ask ""

        not match block [mk1: rules* mk2: (mk2: change/part mk1 prod mk2) 
        :mk2]
    ]
    block
]

or, you can collect the matched values:

collect: func [output block rule /local x] [
    match block [copy x rule (append/only output x)]
    output
]

of course parse may not be the best for every kind of structure matching. 
but it can be a good start.

I would like to review how this kind of structure matching is done 
in other functional languages with the feature. I like this version 
and would use it if it were there, but they may have solved some 
problems unforseen by us already.

well the hard thing to do with parse is longest match.

My biggest problem with your rebcode rewrite rules was generating 
temporaries. I have the same problem with rewriting parse rules - 
actually more of one because of recursion problems.

if you come up with a dialect idea, let me know; maybe it's possible 
to write a compiler to parse, or we can just implement it directly.

rewrite is very tricky done this way

Perhaps a supply of temporaries could be provided to the rewriter 
for it to use, and then it would complain if it didn't have enough.

but probably rewriting is tricky in itself.

you mean, temp local words?

I mean words defined in the calling context that can be used as temporaries 
by the resulting code without having dificulties.

do you have an example? (i don't know if we can find a general solution, 
but i'm sure each problem can be solved quite easily)

Parse has this problem in particular for its temporary variables 
- they aren't very recursion safe. You can do some hacks to make 
up for missing parse keywords using code blocks, but usually those 
need some temporaries.

i usually just tend to avoid recursion when it is not really needed, 
and i try to stay alert when i need it ;)

When parsing recursive structures, you often need recursion-safe 
local variables. I run into this when writing compilers pretty often.

i have been thinking about function! values inside parse rules; parse 
could you the function code block as a rule, but "enter" the function 
when entering the rule; so you can take advantage of the function's 
context.

you could even define parametric rules

i was also wondering if it made sense to allow return values; but 
it doesn't match the current parse at all so i'm not sure.

Parse uses a lot of temporaries for doing common tricks with code 
blocks that should really be built into parse as keywords, like REMOVE, 
REPLACE, UNLESS, USE, etc.

I've wanted parametric rules for years.

there are many subtle issues with a proposal like this though.

i wonder if it's possible to experiment with it with mezz code.

make rule! [[locals] [rules]]

Using a variant on Carl's new make function! syntax.

would rule! really be different than function! ?

A new function type where the code block would be executed by the 
parse engine rather than the DO engine.

but you can't call it outside of parse anyway

and you can't use functions inside parse either

so it's just rule!: function!

You could keep the spec block mostly the same as function!, just 
like rebcode does. Calling it would call parse on its first argument. 
This would be sort-of like a parse rule compiler.

Calling it directly I mean.

but that wouldn't be very useful inside parse then

well... i need to get some sleep. this is a very interesting topic 
though. i hope we can improve parse on r3 too (the problem is deciding 
where to stop).

I need some dinner, so I'll think about this a bit and come up with 
a set of appropriate parse functions and their equivalent rewrite 
code.

Parse operations I mean.

Here are some minimum additonal parse operations, and some workarounds 
that could be used to replace them until they are implemented.

fail ==> [end skip]
check (code) ==> (tmp1: unless (code) [fail]) tmp1
remove rule ==> tmp1: rule tmp2: :tmp1 (remove/part :tmp1 :tmp2)

replace rule (code) ==> tmp1: rule tmp2: :tmp1 (tmp1: change/part 
:tmp1 (code) :tmp2) :tmp1

replace-only rule (code) ==> tmp1: rule tmp2: :tmp1 (tmp1: change/part/only 
:tmp1 (code) :tmp2) :tmp1

into-string rule ==> set tmp1 string! (tmp1: unless parse tmp1 rule 
[fail]) tmp1


Note that if parse operations are changed to take refinements or 
if these are being done as rewrite rules, replace-only and into-string 
could be expressed as remove/only and into/string. This would be 
slower in a native implementation, but about the same in rewrite 
rules. It would look more REBOL-like if that matters to you.


A rewrite engine for these workarounds will need temporaries for 
their implementation. The caller would need to provide a block of 
their own temporaries, and would not be able to reuse them in their 
code. The rewriter will need to count temporaries and complain if 
the caller doesn't provide enough. As with all parse rules, these 
temporaries will not be recursion-safe. Directly nested rules should 
be fine as long as there are enough temporaries provided.

I'm still working on parse extensions to enable recursion-safe temporary 
variables. Obviously they are a bit more involved.

I did that last year. Let's see.. the interface is make-recursive-rule 
which takes a parse rule block and outputs one that saves and restores 
temporary variables at the right time. It extends the parse dialect 
with a new 'recurse-into keyword. 

Make-recursive-rule essentially just looks for   [ recurse-into rule 
]   and replaces it with   [ save-vars   rule   restore-vars ]

Anton, I would like to see that. As it is, Gabriele and I started 
this discussion with an idea towards seeing what could be fixed in 
REBOL 3. I'm trying to come up with simple operations that parse 
could be extended with, the minimum necessary I hope. Bear with me 
or a moment.

Here's my first attempt at a pattern for recursion-safe temporaries:


use [var ...] [rule ...] ==> (tmp1: use [var ...] copy/deep [[rule 
...]]) tmp1


It would only work with a directly specified variable and rule block, 
and you should only use the temporaries directly in the rule block 
or they won't get rebound. Now, using REBOL 3's closure (probably 
better):


use [var ...] [rule ...] ==> (tmp1: do closure [/local var ...] [[rule 
...]]) tmp1


Of course this is just an example. An actual rewrite engine would 
premake the closure and insert it directly instead of making it in 
the rule and doing it. REBOL's existing function recursion support 
wouldn't work because the function returns before the rule is run.


I would prefer a native implementation of this operation if possible.