[Bug 8662] [XQuery 1.1] Need an easy way to define a recursive inline function

http://www.w3.org/Bugs/Public/show_bug.cgi?id=8662





--- Comment #3 from John Snelson <john.snelson@oracle.com>  2010-01-07 12:06:10 ---
(In reply to comment #2)
> (In reply to comment #1)
> > There are two related possibilities here:
> > 
> > a. Allow definition of named, scoped, local functions, ie:
> > 
> > declare function outer($a)
> > {
> >   declare function f1($b)
> >   {
> >     $a, f2($b)
> >   };
> > 
> >   declare function f2($b)
> >   {
> >     $b, f1($b)
> >   };
> > 
> >   f1#1;
> > };
> 
> What if I want a local function declaration at a deeper expression nesting
> level? The above syntax doesn't seem to allow for it, and "local function ...
> return ..." is effectively the above syntax adapted to allow arbitrary nesting.

I agree that this solution doesn't allow arbitrary nesting of named function
definitions, but to do that I think you need to go with option 1b.

> > b. Many functional languages have a recursive "let" whose variables are all in
> > scope for any of the bound expressions:
> > 
> > letrec $f1 := function($b) { $a, $f2($b) },
> >        $f2 := function($b) { $b, $f1($b) }
> > return $f1
> > 
> > I think I'm personally in favour of a solution like this.
> 
> This has the problem of also seemingly allowing (at least syntactically):
> 
>    letrec $x := $y, $y := $x

It does, but I don't see the problem with that. It's an infinite loop - but
there are many ways to write an infinite loop in a turing complete language.

> On the first glance this problem is already solved for globals, but that
> solution, if applied to locals, would prohibit the mutually recursive function
> declarations above. Furthermore, no simple rule can be devised, such as
> "recursive reference is legal within function body only", as that can still be
> abused:
> 
>    letrec $x := function(){$y}(), $y := function(){$x}()
> 
> The only case that can be easily statically guaranteed to be safe is the one
> where variables are directly bound to inline functions, and all recursive
> references are within bodies of said functions. At which point we get precisely
> the same semantics as "local function ... return ..." with a different syntax
> (which arguably seems to be more general than it actually is).

I don't think there's a good reason to try to avoid infinite loops in variable
values. You can already get infinite loops in functions, and we don't see the
need to try to figure out complicated rules to avoid them. Additionally there
are legitimate meaningful reasons to recursively refer to a variable from
within it's initialising expression, ie:

letrec $fibonacci := 0, 1, zipWith(function($a, $b) { $a + $b },
                  $fibonacci, subsequence($fibonacci, 2))


> > 2) Reference to self
> >    -----------------
> > 
> > I dislike the idea of a special named function which is only in scope
> > sometimes, and has a different type signature depending on where it is in
> > scope. If we went this route, I would prefer a special variable like $this or
> > $self of type function(*), which contains a reference to the current function.
> 
> It could also be a keyword that just looks like a function call. It would be
> desirable to have it properly typed, however, if only to require a static error
> if it is called with incorrect arity.

XQuery (without the optional pessimistic "Static Typing" feature) is a dynamic
typed language, so we only need to ensure that it's /possible/ for an
implementation to assign a stricter type. In this case that is entirely
possible, and I imagine exactly what most implementations would do.

> Also, any such "$this" would effectively be part of the static context, and, so
> far as I know, the existing practice is for accessors to static context parts
> to be functions, rather than implicitly-defined variables (in fact, are there
> any of the latter in the current XQuery 1.1?).

I think if it were a function, that function would return a function reference
to the current function - not /be/ the current function by a different name.

> > Another (possibly tangential but related) issue is the rules about not allowing
> > a global variable that references itself. It seems odd to allow this:
> > 
> > declare function f() { 1, f() };
> > 
> > but not this:
> > 
> > declare variable $f := 1, $f;
> > 
> > Both the function f() and the variable $f evaluate perfectly well on an
> > implementation using lazy evaluation.
> 
> But doesn't XQuery spec explicitly permit non-lazily-evaluating implementations
> by design? If so, the above construct, if allowed, would effectively have
> implementation-defined behavior with an extremely pronounced difference, with
> that not being obvious.

This is already the case. My implementation of XQuery can quite happily work
with infinite sequences, whilst others can't.


-- 
Configure bugmail: http://www.w3.org/Bugs/Public/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.

Received on Thursday, 7 January 2010 12:06:12 UTC