Declarative Gui

A fully DeclarativeGui is a GraphicalUserInterface in which documents is described or coded (under-the-hood) in such a way that there is no syntactic representation for order-of-operations. By extension, this also excludes syntactic representations of synchronization, parallelization, and data-flow. This is as opposed to what might be called a 'ProceduralGui' language, where operation ordering is implicit in the syntax. The exclusion of ordering operations as part of the syntax for DeclarativeGui does not exclude the possibility that there are some semantic statements related to what happens when (e.g. for animations, organizing sounds and music, etc.), but does mean that the order of an animation would be independent of the order of the statements in the document definition.

To simplify the text a bit and avoid LaynesLaw squabbles, I'll attempt to follow DocumentDefinitions. If unsure that a word-phrase is making a useful distinction, check there first.

Markup languages such as HTML manages to partially qualify as DeclarativeGui. Specifically, pure HTML manages to qualify as a mostly-declarative display language, but does not handle input activities (which are usually scripted) or layout (which is implicit in the syntax) in a declarative manner. This resists some forms of declarative update and composition... e.g. one can't simply add a statement introducing a new paragraph in the middle of the text somewhere, instead one must figure out where to add this statement.

The most declarative languages we know are LogicProgramming languages, specifically those without point-cuts and without precedence based on ordering of rules in the document.

Q: What would a DeclarativeGui look like under the hood?

A: A document definition for a Platonian, archetypal DeclarativeGui would look a lot like a collection of facts and logic rules (such as entailment) in a dedicated LogicProgramming language - something like DataLog, for example. However, there would still be a DomainSpecificLanguage embedded in these rules and facts, dedicated to such things as:

display primitives, properties
layout
input options or activity processing
composition of documents
animations, sounds, transitions

The DeclarativeGui Primitives:

Some of the 'facts' would be display primitives - e.g. telling the browser to draw a rectangle, insert a button, add a text field, inject a row into a particular table, etc. It could be that all facts are display primitives, or it could be that these 'display facts' are produced only by application of entailment rules over other non-display facts. The exact set of appropriate display primitives is beyond the scope of this document, but one may be inspired by HTML, PovRay, VRML, SVG, canvases, etc. If aiming to support a ZoomableUserInterface, some restrictions (especially against raster image data) would need to be made here. Properties such as color might be separate primitives. Sound-sources could be attached to display objects, with the possibility of creating size-zero objects for display somewhere.

Some of the 'facts' would be layout primitives - e.g. telling the browser that this triangle goes to the left of that rectangle, or that a particular list entry appears before or after another one. One could potentially use 'absolute layout' properties instead of 'relative layout', at some cost to composability (GUI and document mashups). Transparency might also be considered a layout primitive. It would be wise for a LanguageDesigner of a DeclarativeGui to select both display and layout primitives based on the ability to usefully define their combinations, ideally with few gotchas. Topography (inside, outside, connected, etc. from GraphTheory) is a fairly safe bet for spatial composition.

Some of the 'facts' would be composition primitives - e.g. telling the browser that a given frame contains another document (by URI), or that a given frame inherits elements (perhaps selectively) from one or more other documents. There might also be primitive 'documents' available for composition, provided by the browser, offering access to (for example) the local clock.

Some of the 'facts' would be interaction primitives - e.g. telling the browser that certain interactions (open, examine, navigation, etc.) are available, as well as hooking commands or behaviors to these interactions. Some interactions may be implied by display primitives, such as buttons, toggles, knobs and sliders, canvases and text areas, selection lists... but even for these you will need to define how to process input events. Interaction primitives will probably need some dedicated facts regarding their immediate availability (e.g. disabling of a button or option) and such based in immediately available data, along with various other properties (e.g. regarding focus, tab ordering, etc.)

We might even add temporal primitives - allowing declarative description, layout, and composition of temporal documents (such as animations, music, video), in addition to animations within the document (e.g. transitions like power-point slides). I suspect interpolation (definition of rules or facts as continuous functions of time, e.g. to make document components 'float in' from the side (position as function of time), or 'fade in' (opacity as function of time)) would be quite useful, as would rules involving discrete time (X is true is entailed by {exists T : time(T) and 100 < T}.). I suspect sound and video files or 'streams' would themselves need to be internally described on a timeline, so one would attach them to a function of time that relates their internal timeline to the external one in a continuous manner (albeit potentially not 1:1. One could be playing a video at 10T speed, or playing sounds in a loop).

Use of a simple 'time(T)' primitive datum, along with rules describing functions over time, is very likely powerful enough to define behaviors and animations. Microsoft's XAML similarly uses one or more 'Timelines' as primitive resources to animate documents, albeit as non-monotonic entities supporting 'reset' events (which are problematic for reasons outlined in 'useful computation properties'). I don't see any real benefit from having primitive support for multiple timelines if one can simply use rules to define multiple continuous functions over time, instead. The approach here avoids a huge variety of performance, robustness, synchronization, and differential-equations pitfalls surrounding step-functions (saying what is 'true' at time T as a function of what is 'true' at time T-N, aka the FrameProblem). It might still be more powerful than necessary, but I can't think of weaker alternatives at the moment that are sufficient. Chances are, a browser would implement time(T) by taking the document time (as of the most recent update to time(T)) and adding to T the browser's delta-time since receipt of the message. This would allow continuous smooth interpolation without bandwidth expense, and would reduce issues for high-latency connections (compared to trying to use wall-clock time).

Time itself is a continuous monotonic property, of course, and so can give rise to infinite facts. It is fortunate that we are only concerned about a finite subset of these facts at any given moment! By enforcing that time is monotonic (only increases, never decreases), we can permanently garbage-collect rules that have guards such as time(T),(T < N), any time after T surpasses N. This ability to garbage-collect would, I suspect, be critical when dealing with streaming updates in an animated 'live' document under the typical sufferance of finite memory. It allows facts to 'expire' naturally.

If done correctly, distributing video and sound and animations and behaviors should be no more difficult than distributing any other document. One periodically updates facts about what animations/sounds/video to play in the immediate and long-term future to subscribers, potentially based on live interaction (e.g. videoconferencing). Due to latency, some viewers would see events slightly later than others on the wall-clock, but all views would be synchronized in terms of document-time. If done correctly, big, virtual, composable, open, distributed, 3D, animated and interactive worlds and avatars become a very real possibility. ^_^

Command Scripts

At some point, the user will cause a behavior upon the document: marking a checkbox, pushing a button, adding text to a textbox. In general, some artifacts might have default command options (like buttons and text boxes) but other display objects may still be subject to context menus, or might want to listen for keypresses or joystick manipulations. It is important that one can do something useful with these behaviors. For an interface, the most useful thing to do is send a command message to a (potentially remote) object. Feedback can come in the form of updates to the document object (potentially indirectly as a consequence of changes to a service) or replies (e.g. a response with a new document to which the browser may navigate).

The following features are required:

Identify remote objects to which command messages may be delivered. This can presumably be performed via URIs with some common or standard protocols (similar to HTTP's POST).
Constructing the command message. When dealing with simple behaviors (clicks, menu commands, etc.) this isn't a difficult task, but for most forms it will generally require some way to identify the user-controlled data field of the form.
Send the command message. There may be multiple options here depending on whether a reply is expected, whether the command is known to be idempotent (i.e. can be received more than once without causing problems), the possibility for transactional behavior, relative desire for fail-fast vs. retry, etc.

Support for conditionals, sequences, loops, exception handling, etc. aren't critical, but they do simplify reuse: flexibility options in the command language will reduce the requirement to introduce extra intermediate objects to process and filter commands. Aiming for something with reasonable flexibility, perhaps while still providing a guarantee of termination (a command-language that isn't TuringComplete) may be appropriate.

It might be possible to come up with a 'declarative' approach for constructing behaviors, allowing DeclarativeMetaprogramming based on the document state. This would have some nice properties for composing behaviors, but I do not at the moment know a convenient way to go about handling it.

Q: Why 'rules'? Can't we just use facts?

A: Rules serve a similar role as XSLT and CSS. They allow raw 'user-data' to be transformed into display elements. They allow for cascading changes as a result of changing a single data value (e.g. hiding or displaying a table). They support stylistic composition (e.g. via overriding display rules). They support very powerful compression and DataDeltaIsolation for live documents. They support accessibility by allowing blind users to access the underlying user-data directly rather than forcing them to wade through screen-reader descriptions of GUI descriptions of the data. Implementation-wise, rules greatly simplify creation of new document objects (since a 'typical' document definition becomes a simple fixed set of rules plus a simple variable set of user-data). Rules support ZoomableUserInterface through both the compression effects and the fact that a browser can (with decent backwards chaining common to planners) intelligently select and apply rules based on covering broader areas first then cutting off the smaller details - which may be a very significant optimization relative to filtering out small details in the cases where the documents are highly zoomable.

We can get by with just the document-related display facts, but why would we want to? We lose much more than we gain, and we'd probably end up reinventing CSS and XSLT some other way.

Q: How is a DeclarativeGui updated?

A: I favor the pure document model where updates are returned due to subscriptions to remote document objects, which may in turn be live documents (reflecting real systems) or may simply be interactive (being updated by user input).

That said, while I strongly discourage this approach, I can imagine something more like a DeclarativeGui 'retained mode' WebApplication design using a declarative document object model locally to the browser. In that case, each user of each document would maintain his own 'copy', there would be some commands would exist to directly manipulate the document object model, and the browser would reflect the changes to the document definition. The 'document object model' in this case would probably consist of inserting and deleting rules and facts.

Q: What would a DeclarativeGui look like to the user? How would the user interact with one?

A: Like any other GUI with the same feature-set.

Q: Can we have ZoomableUserInterface?

A: DeclarativeGui has more promise for ZoomableUserInterface than most alternative approaches, especially when combined with the document model for UserInterface. The main reason is that the browser, rather than the document, readily controls processing and can guarantee partial displays. When a very large document is represented in a very small region (e.g. 10x10 pixels) you don't need the fine details. For procedural, you would in general need to execute the procedure for the display with some input based on level-of-detail, and it would be difficult to guarantee the processing cost is commensurate with the display area.

Q: Would we benefit from something like 'cookies'?

A: No. Cookies were an awful idea baked from an inconsistent UserInterface model that couldn't decide between 'the browser displays documents identified by UniformResourceIdentifiers' and 'the browser is an application platform that runs applications named by UniformResourceIdentifiers'. (See HtmlSucks.) If either of those two positions is chosen and held consistently, there is no need for cookies. Of the two, 'the browser displays documents' allows more powerful optimizations, but also requires them - requiring separate facilities for mobile code in order to achieve optimal performance. So, no, we would not benefit from cookies. We'd benefit a great deal, however, from consistency.

Q: Realistically, what sort of performance would we be looking at with a mature implementation?

A: Good performance. Procedural programming generally offers better hand-optimizations, but a mature implementation for a declarative language will allow document definitions to be compiled just as easily, with caching where appropriate. In the context of ZoomableUserInterface with thousands of composed documents, performance could easily be an order-of-magnitude better for equal levels of displayed detail simply by having better ability to limit processing based on available level-of-detail. But, ignoring the ZUI, performance would be decent, especially if we're comparing equals to equals (i.e. procedural with guaranteed termination to declarative with guaranteed termination). I suspect the DeclarativeGui would never quite catch up with optimized procedural when displaying a single document in complete detail, if only because every DeclarativeGui document definition would, in ideal circumstances, ultimately be compiled to optimized procedural, and the compilation step would represent a small performance hit. But it could come close.

Relevantly, the minor performance hit buys other features, such as a significant degree of composability (e.g. ability to merge documents), accessibility (e.g. ability to associate display components with user-derived facts), etc.

Q: Realistically, what level of portability would be achieved between languages and platforms?

A: No advantages or disadvantages for portability. Declarative languages are a pain to implement, but it would be implemented just a few times with portable frameworks and ForeignFunctionInterfaces handling most cross-system and cross-language portability issues.

But sometimes people say 'portability' when they really want 'composability' (e.g. the ability to integrate documents with application-frameworks). A faithful adherence to the document model for UserInterface provides a lot of composability in any case, and the DeclarativeGui still offers the same advantages named above in the section of 'why rules?': simple definitions for document objects, ability to compose and stylistically override documents, and essentially 'mash up' documents with application facilities.

Q: Can we specify transition effects (across updates)?

A: Likely, yes. If we can define temporal documents, then I suspect one can also define transition effects even for otherwise static documents. Essentially, a transition from one document-version to another is:

Delete facts that previously had some infinite time dimension but are now out-of-date.
Add some intermediate transformative facts, likely some combination of interpolation-rules and discrete rules, that go from T_now to T_now+K for some constant K in the future. These rules would essentially 'expire' (become useless, except for instant replay) at time T_now+K, so could be subject to GarbageCollection.
Add some rules for a final state that are true for all time after time T_now+K.

Once the steps are defined for such a transition, one should be able to abstract the transition rules by introducing 'animation facts'. E.g. the above might be abstracted as a statement 'myAnimation(T_now,X,Y,Z,K).' plus several 'static' rules that are tied to 'myAnimation'. This would simplify injecting the transition into updates, at the cost of providing more 'static' rules to the document. (A few more static rules for a document isn't a significant problem if documents are allowed to simply inherit from other documents, thus allowing some documents to serve as shared libraries of such rules.)

The difference, then, between a transition and an animated document would be that transitions end. By comparison, animations can continue forever, cycle, etc.

There are many less-expressive forms of transitions if we restrict ourselves to otherwise atemporal documents, but the approaches I've discovered seem to depend very largely on browser-supported 'transition effects' in about the same sense as transitions between PowerPoint slides - an approach I believe to be stagnant and tacky. The problem is that complex or arbitrary transitions require a time-element. Composable transitions require synchronization primitives equivalent to before and after and while.

That said, I'm rather fond of the idea of supporting temporal documents, so perhaps I'm just not looking hard enough for less expressive solutions.

Useful Computation Properties:

Totality: computation of the display (and by extension of the language defining it) at any given time is guaranteed to terminate without errors. Note that "without errors" only means that the computation, if its expression is well formed, will complete without conditions that need to be met or exceptions that need to be handled externally, and without any undefined behavior or results; specifically, "without errors" does not mean that the computation completed is the correct one or that the resulting display is the desired one! Totality is a powerful property, especially since it guarantees that the mother of all optimizations (PartialEvaluation) can be performed to any arbitrary degree and is guaranteed to halt, and other analysis is also possible (since the language is not TuringComplete, it is not subject to RicesTheorem).

Determinism: if the document's processing is allowed to reach completion within the semantics of the language, then its final state is deterministic. For DeclarativeGui, the semantics of the language exclude any implicit and explicit ordering and synchronization between statements themselves (even statements saying what happens when synchronize only those events, not the statements) so determinism for DeclarativeGui means that all evaluation orders lead to the same set of display facts and the same display. It also means that massive parallel processing is guaranteed to succeed, which is a rather nice promise for performance. Determinism for logic languages places some restrictions on use of 'constraint' logic and 'negative' logic. E.g. consider:

x :- not y. y :- not x.

... use of negatives like this allows for two different 'solutions': x but not y, y but not x. Overcoming this either requires adding some sort of precedence rules, such as order-dependence (which is painful and arbitrary) or explicit precedence (which is even more painful and more arbitrary), or requires avoiding use of negatives and certain other constraints. E.g. one could disfavor negatives, but might still be able to support a weaker (and mostly sufficient, especially with workarounds in other areas) option like 'defaults'.

Determinism as an advantage here needs only to extend as far as the document definition processing. If the actual layout within stated constraints is left up to the browser, then that means the determinism requirement is only up to the statement of constraints, as opposed to the fulfillment of them. Non-determinism at a higher layers can still be useful, e.g. to allow a browser to take full advantage of the current size of a viewport.

Data Driven: No history is needed, both for interface elements and display elements. This means avoiding step functions (where rules in future frames are based on rules in earlier frames) and requires that all elements of a document (even alert boxes and such) be part of the document definition rather than existing as 'interactions between document and browser'. Additionally, it means avoiding display events (e.g. temporal resets) where missing an event may cause the display to fall out of synchronization with the document object. Data-driven documents will benefit from these restrictions by being more robust, offering simple persistence and easier ZoomableUserInterface, supports versioning and history without synchronization details, and so on. Also called 'ImmediateModeGui', and a fuller description of the advantages is provided there.

Eventual Consistency: If a document and all its dependencies are given long enough without updates, then, by the end of that period, everyone observing the document will agree that the documents are the same (at least under-the-hood, before accounting for browser-side stylization and screen limitations). Eventual consistency for documents allows significant relaxations of ACID in order to improve liveness, and is actually relatively easy to achieve in the document model for UserInterface. The fact that, for a DeclarativeGui, the order of statements in the final document isn't particularly relevant, makes it even easier. Actual consistency is rarely achieved if documents are continuously updated, but eventual consistency guarantees that it will, at least, be 'mostly' achieved.

Externally Driven: Updates to the document's rules and facts either occur via composition (a change in inherited rules) or from external systems (live updates). This is just a bit stronger than 'no step function', since it excludes the possibility of updates to the document caused directly by user-input. If user-input changes a document, it occurs indirectly via a command message to an external service (which might just happen to be an update-facet for the document object) feeding back as an update the document. This is a KeepItSimpleStupid rule, since it ensures that all updates to the document occur by the same mechanism, and doing so greatly simplifies multi-user sharing for documents (since one doesn't need to manage two forms of update commands).

Rule and Fact Order Independence: any permutation of the rules and facts in a representation of the document results in the same final set of facts and display properties. That is, there is absolutely no semantic significance, implicit or otherwise, on the order rules and facts are stated in the document definition. This doesn't quite follow from being 'deterministic' and 'declarative' (determinism may be based on order, and precedence is not synchronization) but it is a very useful rule for DataDeltaIsolation and implementation issues (since it allows you to 'forget' ordering concerns in implementation, and it allows you to ignore ordering statements when adding and removing rules and facts). Fortunately, Rule and Fact Order Independence is usually easy to achieve if you already have Totality. It does mean that resolution of 'defaults' (e.g. in an overlap situation without z-order, who overlaps whom?) should be based on arbitrary features like identifiers or lexicographic ordering of canonical representations of the facts, as opposed to position in the document definition.

Ideal Programming Model for DeclarativeGui: document-based UserInterface, the components of which (document definition, document object, document server, browser) are largely defined in DocumentDefinitions. Other components would include a PublishSubscribeModel for document objects, a simple language for issuing commands, and, of course, a LogicProgramming language tuned for use with DeclarativeGui with the above useful features.

Such a programming model would readily support:

multi-user friendly
live document friendly
network friendly
robust in the face of partial network failures
accessibility friendly
composable (mashup friendly)
CapabilityUserInterface (secure by construction, no need for permissions or proof-of-identity except at browser)
ZoomableUserInterface (infinite zoom, via composition rather than hierarchy, navigation by zooming into links ('back' is 'up'))

We could also (with some extra standardization and effort) support:

Streaming video, music.
- For ZoomableUserInterface, having music and sound be positional to a document seems appropriate, such that as you zoom out volume fades along with pixel size.
- Attach-to-HUD: if the HUD is constructed as a document, music and sound-sources attached to it wouldn't fade, and video would be 'attached to the monitor' rather than the document in order to offer a clearer view.
Accessibility:
- ability to consistently identify the most important pieces of underlying data and provide them by other means or through a translator.
- separating input-events (touch, open, enter, examine) from their input-mechanism (click, context menus, mouse hover, etc.), possibly via separation of the input+command options from their suggested mapping to user devices. Goal here is to easily allow mapping alternative mappings (gesture, voice, etc.) as well as discovery (e.g. for a blind person, a voice could describe the interactivity options aloud).
It might be useful to also support 2.5D areas that allow 2D layout of 3D objects such as 'to the left of' and some view-relative 3D layout like 'beyond' or 'in front of'. Being attached to flat surface would still allow some very neat effects, such as some combination of popping out of the surface like a monument (pop-up 2.5D) and living behind the surface as though it were a portal or window (pop-in 2.5D).
3D animated worlds (link = portal? navigation by walking through doors? could still attach 2D (documents, graphitti, textures) and 2.5D documents (deer-heads on walls, curtains and drapes, looking behind non-navigable windows to fake 3D areas) but couldn't use view-relative layout and need 6DOF within world.
Avatars, conferencing, especially avatars decided by browser and 'stylized' to world.
Transitions

What is a "subscription"?

A subscription (to X) is a request for a signal (often implemented as a callback) upon each update (of X) until you get tired of the updates and decide to unsubscribe. Doing this allows low-latency update processing without the bandwidth and processing costs associated with polling. The trade-off is complexity of subscription management, and slightly bulkier state management (due to maintaining lists of subscriptions for each cell). For very large state values, subscriptions can be optimized by just returning the deltas from the last callback - a compression mechanism DataDeltaIsolation. In general one may also subscribe to events that might never be committed to state, but that possibility isn't necessary - or even desirable - in this particular context. See PublishSubscribeModel for more detailed information.

What's next? Defining some experimental DeclarativeGui languages, working through a ton of use-cases, coming up with a reasonable set of DeclarativeGui primitives, and resolving likely issues:

default properties
uniqueness properties (i.e. some equivalent to candidate keys, along with static checking that the program maintains this. W/o static checking, one loses at least one of the useful computation properties.)
composition, templates, inheritance, stylizing, and libraries support. Potentially, 'libraries' could largely be simple inheritance-based composition of other documents. Namespaces may be an issue. Name uniqueness when performing inheritance of documents will need to be handled.
naming of display elements. Two issues in particular: should the names reflect the types, such that one is talking about 'box(x)' vs. 'x'? If they don't reflect the types, will it be less convenient to ensure uniqueness? And also, should the names be arbitrary structured values (i.e. that can contain useful information)? Or should they be simple atoms that cannot be broken down?
achieving totality with functionals (expressive enough to describe positions in terms of time, for example).

Stratified Functionals In Relational Queries (tackling 'totality with functionals')

As an example of a 'problem', one cannot do this if one wishes to have a terminating program:

  path(B,C,[B C]) :- edge(B,C).
  path(A,C,[A]++P) :- edge(A,B), path(B,C,P).

The problem is that a simple cyclic graph (like 'edge(a,b). edge(b,c). edge(c,a).') would produce infinite paths on the cycle, each with a different (unique) third variable. Example paths produced would be [a b], [c a b], [b c a b], [a b c a b], [c a b c a b], etc. Since it takes infinite time to produce infinite paths, the program isn't 'total'. QED.

Clearly, if the DeclarativeGui is to be total, it cannot allow arbitrary use of functionals. But the temporal primitives do require use of functionals, in order to define such properties as position, rotation, opacity as a function of time. The DataLog solution of simply forbidding all functionals will simply not do. So, we need something stronger than 'no functionals' but weaker than 'arbitrary functionals'. Beyond temporal primitives, functionals may also be usefully applied to a few other purposes, similarly to how SQL scalar functions are sometimes applied to data to produce columns containing values that weren't in any table in the query.

The best solution that I can come up with is to stratify the functionals according to their natural relationships then verify the stratification statically. I've experimented on paper with many other solutions, but this involves the least interference with natural expression of the program, involves no arbitrary decisions, and is the least likely to complain except where a real problem exists.

I'll provide a few definitions then some explanation:

A production rule is a logic rule that produces a new fact based on other facts. At the moment, the only production rule is entailment, basically of a form similar to 'xyz(A,B) :- xy(A,C), yz(C,B).' The production in this case is xyz(A,B).
A functional [production rule] is defined as a logic production rule with a function that might be a value-constructor on the production side. The 'might be' is based on static analysis and errs on the side of classifying too many functions as value-constructors, which is intentional.
A value-constructor is any function that produces a value that is either equal to one of the inputs or strictly smaller than one of the inputs by some function mapping the values to the natural numbers. Examples of functions that are not value-constructors include id (\x -> x), value-selectors (\a b c -> if a then b else c; \a -> a.field_x), etc.
Stratification applies to labels (names) on the production side of rules. A label for a functional will stratify 'above' one or more other labels from the pattern-match side. In particular, a label stratifies 'above' some minimal set of labels that provide inputs to value-constructors.
If there is a cycle, such that a label must stratify 'above' itself, then that is an error (statically verified). How such errors are handled is up to the browser. (I'd suggest issuing some nice big warnings, plus heuristically dropping functionals until the document stratifies then displaying whatever mess comes of having dropped display rules.)

Examples:

   path(A,C,[A]++P) :- edge(A,B), path(B,C,P).
   baz(A,B+C+D) :- foo(A,B), bar(B,C,D).

The above are both functionals, with value-constructors '[A]++P' (append) and 'B+C+D' (sum). We can observe that each input to the value constructor must come from a match in one or more of the positively matched 'facts' on the RHS.

In the 'path' case, 'path' must stratify above 'edge' (since 'A' comes from edge) and above 'path' (since 'P' comes from 'path'). Since 'path' must stratify above 'path', the document containing that rule is in error. The document could still drop the offending rule and display with a broken 'path' definition, as well as note some warning in bright red at the bottom of the page to tell the document service provider to fix his documents.

In the 'baz' case, the value 'B' is available from both 'foo(A,B)' and 'bar(B,C,D)'. We only need to have it from one of those, not both, so in this case 'baz' comes above 'bar' (which provides C and D) but does not need to be above 'foo'. In a sense, one could rewrite it. We could even use 'foo' on both sides of a functional, so long as it doesn't stratify in a cycle. Consider:

  foo(A,B+C+D) :- foo(A,B), bar(B,C,D). ;; is equivalent to:
  foo(A,B+C+D) :- foo(A,X), bar(B,C,D), (X == B). ;; but also equivalent to:
  foo(A,B+C+D) :- foo(A,B), bar(X,C,D), (X == B).

In this case, it is more optimal for the verifier to stratify 'foo is above bar' rather than 'foo is above both foo and bar', the latter of which would lead to an unnecessary complaint. In general, some search may be required for the verifier (likely the document browser) to find a valid stratification, but it only needs to find one valid stratification to confirm that computation will terminate, and the effort to do this is trivial when compared to the other search and logic problems associated with a declarative GUI document. (Even parsing is harder.)

Also, we can still have arbitrary cycles so long as they aren't functionally stratified, as per regular DataLog:

  path(A,B) :- edge(A,B).
  path(A,C) :- edge(A,B), path(B,C).

This solution is restrictive. One, for example, literally cannot compute the actual steps, or even the cost of each path, but only whether a path exists. But it's certainly flexible enough for defining properties (position, opacity, rotation, text, etc.) as arbitrary functions of time, with no risk at all of complaint (unless programmers then attempt to define time in terms of these functions...). In general, this stratification in combination with cycles allows DataLog to exceed SQL in support for scalar functions (though one is still limited to 'total' functions, of course; see TotalFunctionalProgramming), and stratification could also be used to access aggregate functions (though I'd not bother with aggregates for the DeclarativeGui until need is proven). As a rough example of using temporal primitives, this would make a box move around in an elipse... assuming the primitives like 'position' and 'box' and such existed (still need to work all that out):

  position(box(x), 100+30*sin(T), 200+40*cos(T)) :- time(T). ;; rough example

The termination guarantee using stratification is simple to verify by induction (finite data items in lowest strata, if finite data items in strata S then also have finite data items in strata S+1 based on value-constructors). It's boring to go into it. Ultimately, the prevention of cyclic value-constructors precludes infinite generators.

There are, of course, quite a few termination proofs available to a wide class of logic programs. Labeled Term Rewrite Systems seem very promising, and cover a much wider class of problems than the above, capable of testing (for example) termination of a quicksort program written in a logic language. I'm doing some research there. But the real conclusion is that achieving non-termination without painfully restricting the programmers seems to be readily within range.

Uniqueness Properties

Uniqueness is something of a sanity check. DataLog in its rare, unmodified pure form doesn't (IIRC) allow one to declare uniqueness (i.e. no equivalent to "candidate keys" or anything similar) or to check it. In practice, uniqueness in RDBMSs tends to be enforced at time of 'insert', but that's hardly the ideal case when it comes to determinism (because it leads to a RaceCondition where 'first insert wins'). For DeclarativeGui, I would like determinism. It's a nice computation property, and I'd rather not give it up without a fight. So, rather than enforcing uniqueness at time rules are added, it would be better to enforce it (or at least give proper warnings to encourage immediate repair) statically.

There are two problems: declaring uniqueness, and deciding uniqueness.

Declaring Uniqueness: Still scraping around for ideas on how to most naturally declare uniqueness (in DataLog style). Should it be in terms of candidate keys? (If so, I can't declare that 'time(T)' is completely unique, since there is no candidate key for time other than T.)

Deciding Uniqueness: This, I suspect, is the easier of the problems... so long as you ignore guard-functions and err on the side of rejecting too much. Analyzing guards for overlap would be problematic, even with total functions for guards. I wonder how much guards could be ignored in practice?

In addition to the above, uniqueness mixes with fallback/override issues.

Generic Primitives

I was just reading a document on FunctionalReactiveProgramming for images that has some relevance to the work on DeclarativeGui. (http://conal.net/blog/posts/3d-rendering-as-functional-reactive-programming/). I was wondering what the most 'generic' primitives I could define for sounds, images, video, 2.5D, 3D, animated scenes.

Conal defines 'Image' as a function on an infinite, unbounded 2D space to some properties. These properties may be anything, but would typically include color and opacity. 'Image' defined in this manner has fairly natural composition and mutation properties... e.g. one can 'rotate' the image without calculating a bunch of pixel offsets. Instead, you just rotate logically (and lazily). This definition of image does essentially require translating raster images (JPEG, BMP, TGF) into a continuous format, but that isn't too difficult a task if you're not going to bother tracing edges. While it would take forever to display an infinite 'Image' thusly, it's a non-issue since one only draws a final 'view' of the image (i.e. drawing a fragment of the image at a particular resolution).

My own issues with the definition are based on my concerns for DataDeltaIsolation and 'AvoidDrawing' optimizations like RefreshRectangles. If I were to define a very large image (e.g. 1920x1080) the way Conal does it, I would need to redraw the entire image every time even one of the underlying composition functions change. That's 2-million pixels to recompute. Additionally, every function in the composition will contribute to each of those 2-million pixels, so if there are a thousand things to compose, that's 2-billion function operations. Even on a good processor and using a powerful optimizer, you're talking seconds of update time after each change. Conal's method may be suitable for producing static images, but it seems ill-suited for a live environment.

But still, it'd be nice to have the freedom for all this available for the simple image object in a DeclarativeGui, even if weaker forms (like SVG, lines and boxes and text-areas, etc.) are made available for common cases. And it's still 'zoomable', so long as you're zooming the actual viewport.

In that line, 'generic' video would be an image as a continuous function of (2D) space and time.

If 3D is an arbitrary geometry (perhaps a 3D space of arbitrary properties? Not sure how to 'most generically' represent 3D, yet), then 2.5D is something like 3D relative to a particular 2D space (with the idea that there will be a 'fixed' view relative to the 2D space). These can also be functions of time.

Sound is what? A continuous function of time to... a continuous function of frequencies to... continuous range of intensity? That would probably be a fairly generic representation, but there might be some other representations (I think one could get away with simple time->total intensity e.g. on a wire...). Not my are of expertise, and the best choice might be more related to what composes well and which is easier to define music and sounds in than what most naturally represents the strength-on-wire. But if others have ideas, speak up. I'll see of 'The Fun Of Programming' says anything about it on the chapter for functional music programming. (http://web2.comlab.ox.ac.uk/oucl/publications/books/fop/)

What about an attribute-centric GUI kit instead of such a heavy reliance on LogicProgramming? It would be less tied to particular syntax and a particular language that way. I suggest you rename your topic LogicOrientedGui?. -t

Review: Q: Why 'rules'? Can't we just use facts? Further, if you want an "attribute-centric GUI", then create a page called AttributeCentricGui? and define it there. There is no reason, after all, to expect attribute-centric GUI is necessarily declarative. Being declarative is about means of composition (how these 'attributes' are introduced, modified, selected for display, etc.) more so than about primitives. (Related PrimitivesAndMeansOfComposition.)

I already created an example language under GuiMachineLanguage.