Re: Factual error was Re: Brainstorming: Best of all Worlds

Ian Hickson:
> > > [halting problem]

Dave Raggett:
> > You are incorrect on this point. Please re-read the XForms Transitional 
> > draft spec as I have clarified the wording based upon how my 
> > implementation works, and it should be noted that this has been tested 
> > on a much wider range of browsers than Web Forms 2.0 has at this point 
> > in time.

Ian Hickson:
> The new spec doesn't change the UA requirements, so you still (as far 
> as I can tell) require UAs to do static analysis of turing complete code, 
> which, here, reduces to the halting problem. (All you've done is made such 
> cases non-conforming, but that doesn't affect the UA at all.)

Static analysis of programs doesn’t correspond to solving the halting
problem, depending on what sort of analysis you need to do.  If one of
the conditions for a calculate attribute is that its expression needs to
halt, then yes, that’s obviously a problem.  From my reading, the static
analysis that’s required by XForms Transitional is just the dependency
analysis, which should always be possible.  Whether it comes up with
useful dependencies without resorting to evaluating some of the
expressions during the analysis is another matter though…

> There are other problems, too, such as how to handle fields whose exact 
> lists of dependencies themselves depend on other field, e.g. because 
> the calculate="" field does something like:
> 
>    calculate="document.forms[0][document.forms[0].field.value] + 1"

…so with this example (or with

  document.forms[0][document.forms[0].field.value].value + 1

which I think is what you meant), if you allow limited evaluation of the
expression during analysis (rendering it therefore not truly static),
the dependencies will be:

  document
  document.forms
  document.forms[0]
  document.forms[0].field
  document.forms[0].field.value
  document.forms[0][document.forms[0].field.value]
  document.forms[0][document.forms[0].field.value].value

If any of these values change, then the form field with the calculate
attribute on it needs to be recomputed.

Static analysis wouldn’t allow the implementation to determine the

  document.forms[0][document.forms[0].field.value]

dependency, since it depends on whatever the current value of the
‘field’ field is.  That’d mean it has to watch all form fields in form
number 0.  If the calculate attribute is in that same form, then that
just introduced a cycle into the dependency graph.

> It's also unclear to me how UAs should handle cyclic graphs (which can't 
> be sorted topologically)

This would just need to be defined.  The common thing to do would be to
say that cycles cause the whole thing not to work.  In some uses of
one-way constraint systems, it is desirable to iterate to see if you can
converge on a value.  I don’t think that’s the case here.

> or graphs whose dependencies are either truly or 
> apparently random (e.g. because the field used depends on the return value 
> of an XMLHttpRequest call to a remote server).

Yeah, just like with the above example, with static analysis you cannot
know what the value will be, so the dependencies must be set up to
handle *all* possible values.

Ian Hickson:
> > > In the case of declarative calculations it is also not clear how
> > > the feature could be made to degrade gracefully without breaking
> > > full implementations.

That’s true.  From IRC earlier, discussing a simple use case of
automatic “order totals” in forms:

<heycam> i think such things would be easier with things like
  calculate=""
<heycam> (if calculate="" were done properly)
<heycam> but (and this is the big "but" that is going to cover much of
  the discussion in this group, i think), it's the backwards
  compatibility / fallback issue that is troublesome for such proposals
<heycam> if you need to write script to fall back when there's no
  support for calculate="", then you may as well forget writing the
  calculate="" in the first place
…
<schnitz> yes, and one could tend towards being less today-oriented and
  still adding it, even though you need a script fallback, because there
  is this general alignment that this should, over time, move out of
  script space, and become declarative, or behavior :-)
…
<heycam> schnitz, yeah, that's the main the argument for this alignment,
  right?  if you ever want to introduce non-incrementally-developed new
  behaviour into html, it'll be much harder without alignment guiding
  you there

It’s a problem.  You want shiny new features, but authors will only use
them if they’re supported, and implementers may not implement it until
they see that authors want it.

I wonder (out loud–well, in type) how much of a help XBL2 can be in
bridging this gap between times when features are not implemented and
when they are.  It may be an argument, though, if those features do work
perfectly well using the XBL implementation, that they don’t need to be
implemented in the browser at all.

(Oh and by “if calculate="" were done properly” above I mean not using
arbitrary JavaScript.  When I was working on CSVG [1] (IIRC Dave saw me
and my poster on it at WWW2004) I decided on XPath as the expression
syntax.  In the end, I think that was wrong–not because I have anything
particular against XPath, since it’s not bad for selecting things from
XML documents, but because the syntax got clunky with the custom
functions that fetched SVG-specific information from elements.  What was
better about XPath than arbitrary JS though was the fact that it was
much easier to analyse for dependencies.  I think a subset of JS syntax
would be good for XForms Transitional: that way you can leverage both
the implementation of the JS engine and authors’ knowledge of JS, but
constrain expressions so that they can’t have any nasties in them.)

Cameron

[1] http://www.csse.monash.edu.au/~clm/csvg/

-- 
Cameron McCormack, http://mcc.id.au/
 xmpp:heycam@jabber.org  ▪  ICQ 26955922  ▪  MSN cam@mcc.id.au

Received on Friday, 23 March 2007 05:51:19 UTC