This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 1743 - [FS] technical: 5.15 Function Declaration: a function can reference any function
Summary: [FS] technical: 5.15 Function Declaration: a function can reference any function
Status: CLOSED FIXED
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: Formal Semantics 1.0 (show other bugs)
Version: Last Call drafts
Hardware: All All
: P2 normal
Target Milestone: ---
Assignee: Jerome Simeon
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2005-07-18 23:53 UTC by Michael Dyck
Modified: 2006-11-13 05:20 UTC (History)
0 users

See Also:


Attachments

Description Michael Dyck 2005-07-18 23:53:28 UTC
5.15 Function Declaration

SCP / rule 1 / premise 3
"statEnv1 |- FunctionDecl : Typer"
    No, you can't do this in SCP, because (as you just said) STA of
    function bodies must wait until you have a statEnv.funcType that
    contains *all* function signatures.

    Instead, back in 5 / STA / rule 1, there should be a judgment that
    typechecks function bodies, something like:
        statEnv |- func-bodies-okay-in PrologDeclList1
    which recurses down PrologDeclList1 and whenever it comes across a
    non-external FunctionDecl, performs STA on it (using a statEnv that
    knows all function signatures).

    One snag is that that statEnv will also know all declared variables,
    but a function is not allowed to reference variables that are declared
    after it in the Prolog.  In that case, maybe STA of function-bodies
    *should* be done as part of SCP, but SCP should be preceded by a phase
    that collects just the function signatures.

"Note that the static context processing is performing type checking of
the function, as defined below."
    See above.

"Note also that the type checking is done in the new environment in which
the function declaration has been added which ensures that recursive calls
are type-checked properly."
   It only handles self-recursion, not mutual recursion, not even just
   forward references.
Comment 1 Jerome Simeon 2005-07-27 04:36:09 UTC
Agreed. If we want to do that properly, I do not see any other alternative than
to have two passes over the prolog. One to gather the function signature, then
the process that is currently described as static context processing.

This is similar to what I suggested to deal with comment
http://www.w3.org/Bugs/Public/show_bug.cgi?id=1578
which deals with a similar issue but at the level of normalization
of function overloading.

One way to deal with this would be to do the following three things:

(1) add a sentence in the processing model (Section 3.2.1 Processing model)
to indicate that function signatures from each module must be obtained just
after parsing, and be available for normalization, and static context processing.

(2) assume that those function signatures are available as part of the
initial static context.

(3) fix the static context processing not to add again the corresponding
function signatures since they will be assumed to be available already.

- Jerome
Comment 2 Michael Dyck 2005-08-03 07:22:59 UTC
I don't think it's that simple. Obtaining function signatures involves expanding
QNames, which is affected by (the processing of) various PrologDecls.
Comment 3 Jerome Simeon 2005-08-30 15:34:47 UTC
I still think that is the best way forward to avoid the complexity of adding 
context during normalization, and possible another phase in the processing 
model. Since we will not fully formaly specify that part, but use an english 
description, I think we can mention the aspect related to namespace resolution.

Any comments on that plan?
Comment 4 Jerome Simeon 2005-08-30 15:35:42 UTC
As an additional note, I think the real clean way to do this is to perform 
namespace resolution during normalization, but that is too big a change to the 
specification at this point.
Comment 5 Michael Dyck 2005-09-02 00:52:03 UTC
(In reply to comment #3)
> 
> Any comments on that plan?

I think it's a weak plan.  I realize that there are times when you have to
step outside the formalism and define something in prose, but I don't think
this is one of those times.

Making two passes over the Prolg doesn't seem that complex to me. Try this:

========================================================================
(1)

5 / STA / rule 1:

Take premise 1:

    statEnvDefault |- PrologDeclList =>stat statEnv with PrologDeclList1

and split it into 2 passes, yielding this rule:

    statEnvDefault |- PrologDeclList =>stat1 statEnv1
    statEnv1       |- PrologDeclList =>stat2 statEnv2 with PrologDeclList1
    statEnv2       |- [ QueryBody ]_Expr = Expr2
    statEnv2       |- Expr2 : Type
    -------------------------------
    PrologDeclList QueryBody : Type

========================================================================
(2)

Split 5 / SCP / rule 2 into the recursive rules for the two passes:

    statEnv  |- PrologDecl     =>stat1 statEnv1
    statEnv1 |- PrologDeclList =>stat1 statEnv2
    ------------------------------------------------------
    statEnv  |- PrologDecl; PrologDeclList =>stat1 statEnv2


                [ PrologDecl ]_PrologDecl = PrologDecl1
    statEnv  |- PrologDecl1    =>stat2 statEnv1
    statEnv1 |- PrologDeclList =>stat2 statEnv2 with PrologDeclList1
    ------------------------------------------------------
    statEnv  |- PrologDecl; PrologDeclList =>stat2 statEnv2
                                         with PrologDecl1 ; PrologDeclList1

And similarly for 5 / SCP / rule 1:

    -----------------------------
    statEnv |- () =>stat1 statEnv

    -------------------------------------
    statEnv |- () =>stat2 statEnv with ()

========================================================================
(3)
Define the "statEnv |- PrologDecl =>stat1 statEnv1" judgment...

(a) For PrologDecls other than VarDecl and FunctionDecl, simply
    take the existing =>stat rule and change '=>stat' to '=>stat1'.

(b) For VarDecls, it's a pass-through:

    ---------------------------------
    statEnv |- VarDecl =>stat1 statEnv

(c) For FunctionDecls, it only pulls out the function signature.
    Replace 5.15 / SCP / rule 1 with:

    [ FunctionDecl ]_FS = FunctionSignature
    statEnv |- QName of func expands to expanded-QName
    statEnv1 = statEnv + funcType(expanded-QName => FunctionSignature)
    ---------------------------------------
    statEnv |- FunctionDecl =>stat1 statEnv1

where []_FS adapts much of 5.15 / Normalization, but notably does not
involve []_Expr:

    [ declare function QName ( ParamList? ) ... ]_FS
    ==
    fn-sig ( [ ParamList? ]_ParamSig ) as item*

    [ declare function QName ( ParamList? ) as SequenceType ... ]_FS
    ==
    fn-sig ( [ ParamList? ]_ParamSig ) as SequenceType

    [ $ VarName                 ]_ParamSig == item*
    [ $ VarName as SequenceType ]_ParamSig == SequenceType

========================================================================
(4)
Define the "statEnv |- PrologDecl =>stat2 statEnv1" judgment...

(a) For PrologDecls other than VarDecl and FunctionDecl,
    it's a pass-through:

    not(PrologDecl is a VarDecl)
    not(PrologDecl is a FunctionDecl)
    ---------------------------------------
    statEnv |- PrologDecl =>stat2 statEnv

    (Or you can enumerate the cases if you like.)

(b) For VarDecls, take the rules of 5.14 / SCP and change '=>stat' to
    '=>stat2'.

(c) For FunctionDecls, take 5.15 / STA / rule (1|2) / conclusion, and
    change ": Typer" to "=>stat2 statEnv".

========================================================================
Comment 6 Michael Dyck 2005-09-02 00:59:39 UTC
(In reply to comment #4)
> I think the real clean way to do this is to perform 
> namespace resolution during normalization,

I'm not sure that would work very well. It sounds like we'd then have
resolved-names in the post-normalization query, so the Core would need a
concrete syntax for expanded-QNames.

Comment 7 Michael Kay 2005-09-02 07:51:30 UTC
Sorry to step in without having really followed the thread, but it sounds to me
like an excellent idea that the core should have a concrete syntax for expanded
names. In fact, I think the user language should have such a syntax too - it
makes life much easier for people generating queries. It's not difficult to come
up with such a syntax, for example one could use some non-ASCII characters, perhaps

«uri»local-name

Michael Kay
Comment 8 Jerome Simeon 2005-09-02 13:16:09 UTC
I agree this can be done, and thank you for sketching a proposal. In my view 
at this point in the game, this is more a question of how much work should we 
put into this.

This seems like a lot of material to solve something which is really a 
processing model question. We really need to add a processing phase, which
is in essence what you suggest. Or we need to build this during normalization 
(which is what my own implementation does by the way), but of course this 
leads to a much bigger change.

Are you firmly against the non formal approach for this issue? If you are,
we may want to go for your proposal. If you think you can live with the non 
formal approach, I will probably prefer it so we can spend the time processing 
the many other last call issues.

For the records, I kind of agree with Michael Kay's statement that having a 
syntax for expanded names in the core would be great. That is mostly 
tangential to this thread though.

Best,
- Jerome

Comment 9 Michael Dyck 2005-09-03 01:31:45 UTC
(In reply to comment #8)
> I agree this can be done, and thank you for sketching a proposal.

(Well, I'd say it was more like "complete instructions" than a "sketch", but
anyway...)

> This seems like a lot of material

By my count, it's 4 more inference rules and 4 more normalization rules. That's
a lot? Or if you're thinking of the changes to existing rules, those are mostly
search-and-replace.

> to solve something which is really a processing model question.

I don't understand what you mean by "a processing model question", or why that
affects whether it should be formalized. (Are Normalization and SCP also
processing model questions?)

> We really need to add a processing phase, which is in essence
> what you suggest.

If you mean "processing phase" in the sense that each premise of 5/STA/rule_1
constitutes a processing phase, then yes, I'm suggesting adding one. (Or rather,
I'm saying you *need* to add one, to correctly express the static semantics of
VarDecls and FunctionDecls.)

If you mean "processing phase" in the sense of 3.2.1's "sub-phases" of static
analysis, then no, I'm not suggesting adding another -- the divisions between
those "sub-phases" (other than Parsing) are bogus. (See Bug 1547.)

> Are you firmly against the non formal approach for this issue?

Currently, yes. The only argument in favour of a non-formal approach seems to be
that it would be less work, which doesn't strike me as compelling, or even true.
(I don't think "adding a sentence to the processing model" would be anywhere
near detailed enough for a normative specification of the static semantics.)
Comment 10 Jerome Simeon 2005-09-06 15:21:32 UTC
Michael,

Sorry for the unhappy use of the word "sketch" in my note. I just had written
before I had a chance to look at the details of your proposal.

I've just spent that time, and I agree it looks complete, and is not that hard
to implement.

I think I would now agree with you that is the best course of action.

Thanks you again for spending the time to write a concrete solution, this is
very very useful.

- Jerome
Comment 11 Michael Dyck 2005-09-07 02:40:02 UTC
(In reply to comment #10)
> I think I would now agree with you that is the best course of action.
> 
> Thanks you again for spending the time to write a concrete solution, this is
> very very useful.

Yay!
Comment 12 Jerome Simeon 2005-09-27 08:25:03 UTC
Your proposal was adopted by the working groups.
Best regards,
- Jerome
Comment 13 Michael Dyck 2006-05-02 08:08:26 UTC
(In reply to comment #12)
> Your proposal was adopted by the working groups.

The CR does not reflect this.
Comment 14 Jerome Simeon 2006-08-01 12:55:49 UTC
Implemented as suggested. This will be reflected in the next publication.
- Jerome
Comment 15 Jerome Simeon 2006-11-13 05:20:09 UTC
Fix for the comment is now simpler and handled as part of the resolution for bug #1705.

- Jerome