Lambda the Ultimate

e_table and e_k are both time dependent. For the compiler case, e_table is more than likely the result of another table access, or accessed through a time-varying type.

If the goal is to build a live programming environment (where Foo.bar might become undefined if Foo changes) then the way I approach it in FRP is to treat 'Foo' as a an expression on the external source-code resource (though an intermediate 'table' might help me construct the FRP expression, the table itself needn't be reactive).

In my experience, there is no way around having symbol tables, you have to bind names to symbols somehow...would you just have FRP understand that Foo is a definition directly?

I already acknowledged that you previously asserted e_table and e_k to be time-dependent, so repeating that assertion isn't clarifying anything for me.

there is no way around having symbol tables, you have to bind names to symbols somehow...would you just have FRP understand that Foo is a definition directly?

I'd express the AST itself as an FRP expression, allowing any symbol associations to be performed functionally.

I already acknowledged that you previously asserted e_table and e_k to be time-dependent, so repeating that assertion isn't clarifying anything for me.

I thought I answered your question. e_table could be an expression that varies directly according to user input, so ya, e_k = cos(Time) or perhaps e_table = TableA if (Mouse.X > ScreenWidth/2) else TableB is valid. Pragmatically for the compiler case, e_k is a token in a text buffer, and changes when the users edits it (like the content of a text box), while e_table is either a lexical scope, global scope, or scope derived through a type, and it changes as type checking changes because you have edited something (again, user input is in the editor).

I'd express the AST itself as an FRP expression, allowing any symbol associations to be performed functionally.

I have a hard time believing that representing a tree or a symbol table directly via the functional way would be very efficient at all. The worst part is that it creates a set of false dependencies; e.g., consider the statements "a; b; c;", c is not related to a, but if you represent it as a cons list a :: b :: c :: nil, "b" is on the path to c. Now if I edit "b", everything below it in the tree has to be reprocessed, whether it really needs to be or not.

[edit] Perhaps we could use something like finger trees as done in Yi?

Ah. I actually have a couple more questions on your semantics based on your above answer. I withheld them before to avoid the confusion of presenting large 'if so, then how do you...?' decision trees.

Q1: How do you declare an assignment to an 'e_table' expression? Consider:

e_table = TableA if (Mouse.X > ScreenWidth/2) else TableB.
e_table["bob"] = "Mary".
R = TableA["bob"].

What are the semantics for R? Are you going to have it become defined or become undefined based on where the mouse is at any given moment?

Q2: How do you uniquely identify complex signals for e_k? Consider:

e_table[sin^2(Time)] = 1.
R1 = e_table[cos^2(Time)].
R2 = e_table[1-cos^2(Time)].

In this case, is R1 ever defined at some points in time? That is, is the key definition based on the value held by the signal, or by the identity of the signal?

Based on your above answer...

If R1 is not defined, then what about R2? From trigonometry: 1-cos^2(Time) = sin^2(Time), but determining observational equality is extremely non-trivial for arbitrary functions. Would you be using structural identity of the expressions for distinguishing signals? Or, even worse, would you be using object identity of the expressions?

OTOH, if R1 is defined, then how do you handle 'potential' conflicting definitions? I.e. consider:

e_table[sin^2(Time)] = 1.
e_table[cos^2(Time)] = 2.

These, of course, conflict at certain times (at Time=pi/4 + K * pi/2, for integers K). However, statically determining this conflict or collision is non-trivial for arbitrary e_k expressions, and likely undecidable in general.

Are you attempting to resolve these collisions? or do you throw an error when you encounter them? or do you use a precedence strategy? or has it simply not come up due to your limited application of Declarative Reactive Tables to the relatively restricted domain of symbol lookups?

creates a set of false dependencies; e.g., consider the statements "a; b; c;", c is not related to a

The false dependencies don't hurt performance as much as you might think. If your implementation keeps intermediate caches (i.e. wherever a computation takes so much time), then you can avoid invalidating observers if the computed value matches the one in the cache. This is a relatively 'dumb' and coarse-grained way to propagate only changes, but it will work well enough for the problem here. Functions will quickly trim down what is relevant to the semantics of given expressions, thus allowing one to avoid an invalidation when the 'semantics' of one code region is not affected by a change to another.

While the change propagation may be coarser grained than you'd prefer (it could even start at the 'whole-file' granularity and narrow down from there), it could be further improved by intelligent change-propagation optimizations on the resulting FRP expression. And I suspect the performance even of the coarse-grained approach will be superior to most alternatives.

I'm not depending on any optimizations specialized to the domain of live programming, nor specialized to a grammar or syntax. I doubt finger trees would make intelligent propagation of changes any easier by themselves. For robust reactivity, I'd prefer the 'semantics' of which changes are relevant to which other code elements be encoded ultimately within those reactive computations.

If there are a few places I'd like to see some specialized support for intelligent change propagation, they'd be on logic queries and set manipulations (joins, unions, intersection, aggregations) and a few list operations (i.e. addends - especially when wrapped by an lfold, zips, unzips, subranges). A few specialized optimizations could cover a lot of 'generic' ground for intelligent change propagation, and one could take advantage when developing the parse and AST transform functions.

Q1: How do you declare an assignment to an 'e_table' expression? ... What are the semantics for R? Are you going to have it become defined or become undefined based on where the mouse is at any given moment?

R is undefined if TableA doesn't contain "bob." In a compiler, this would lead to a "symbol not find" error, while there is generally a list of tables to look through, where the binding for "bob" would be taken from the table it is first found in (so we can say that etable[e_key] returns an option that is or else'd through a list of tables).

Q2: How do you uniquely identify complex signals for e_k? ... In this case, is R1 ever defined at some points in time? That is, is the key definition based on the value held by the signal, or by the identity of the signal?

Based on the value held by the signal. In the example, R2 is defined while R1 is only defined at Time = pi / 4 + n*pi. The table isn't really designed for continuously changing continuous values, its designed for values that aren't expected to change very often, and change in very discrete ways (e.g., the key as a string going for "Fo" to "Foo").

[edit] To be honest, I've only used this kind of table as symbol tables.

Are you attempting to resolve these collisions? or do you throw an error when you encounter them? or do you use a precedence strategy? or has it simply not come up due to your limited application of Declarative Reactive Tables to the relatively restricted domain of symbol lookups?

Duplicate definition is possible and handled. If you add a value to the table twice, we have a few options: ignore the second definition, but record an error and add a dependency to the table entry (this is what I did in the Scala IDE), or actually store both entries and let reader's flag ambiguity (rather than a simple option, we now have none, once, and many as possible map access results). Collisions are actually a common problem in writing compilers (because people might accidentally define things twice :) ).

If your implementation keeps intermediate caches (i.e. wherever a computation takes so much time), then you can avoid invalidating observers if the computed value matches the one in the cache. This is a relatively 'dumb' and coarse-grained way to propagate only changes, but it will work well enough for the problem here.

Ah! I see how this could work for the AST, but not for the context propagated down through the AST during type checking. If the symbol tables are represented as trees themselves, then you'd have to somehow track what part of the tree something depends on (perhaps by transforming them?). Also, I assume you'd get burnt when things were defined before they were used (e.g., def g = f(); def f : int = 42), although I guess you could process the tree in two passes.

I don't know, I'm skeptical that intelligent change propagation is possible in general, if only because I have yet to see it. I'm perfectly happy dealing with non-functional data structures if there is some strong way in reasoning about them. So I'm ok with trees and tables that are implemented as mutables on the inside but appear declarative on the outside, even if that isn't very pure.

R is undefined if TableA doesn't contain "bob."

Obviously. The question, however, was how the assignment of e_table["bob"]="Mary" affects whether TableA contains "bob", noting that e_table==TableA whenever Mouse.X > ScreenWidth/2.

Ah! I see how this could work for the AST, but not for the context propagated down through the AST during type checking.

To minimize changes, one must express the analysis in a manner that trims unnecessary collisions. For example, given Types (a set of types) and a particular value V, it helps to filter down which Types are relevant to checking V and deciding whether to invalidate it. A change in V forces a re-filter, but a change in Types only forces a re-check of V if it modifies which Types might be relevant to V.

It helps if developers can annotate the FRP expression for 'suggested' caching points, rather than leaving this to chance. In a way, your use of symbol tables is similar to intelligent memoization of expressions at a point you thought most relevant: symbol declarations.

However, the language still needs to be designed to support live programming. Consider: if the language ain't designed to handle it, a missing semicolon might properly invalidate hundreds of kilobytes of 'included' files.

I don't know, I'm skeptical that intelligent change propagation is possible in general

I agree!

But I'm not nearly so skeptical that intelligent change propagation is possible in very specific yet widely useful cases. Tail recursion is rather specific but widely useful, and so could be carefully selected specific 'change propagation'.

One case: "recognize a list extended by a few elements followed by a fold in the same direction (rfold if extended at front, or lfold if extended at end)". In that case, one only needs to keep the prior fold state (which often is the same as the result of the fold), and fold more elements into it. (If one can assert that the list is monotonic and linear, one may be able fully GC the resources that derive its earlier elements, but this would be much rarer for FRP than it is for Haskell's input stream.)

Another case: "a set is now a few elements larger, and is followed by a join". In that case, one only need cross the 'new' elements of the set against other sets in the join, producing potential 'new' elements in the joined set, and filter for duplicates against the prior result - rather useful for a live view of a relational query.

A lot of specific cases of this sort could be supported. Optimizations needn't be "general" to be useful.

I'm perfectly happy dealing with non-functional data structures if there is some strong way in reasoning about them. So I'm ok with trees and tables that are implemented as mutables on the inside but appear declarative on the outside, even if that isn't very pure.

I prefer to keep all 'data structures' as functional as possible, because that distributes well, is resilient (i.e. cheap redundancy), can be lazy or demand-driven, allows for later-stage logical transforms, has little need for synchronization, supports deterministic data parallelism, etc..

Composite patterns of asynchronous potentially-distributed objects (aka first-class processes) are hell to work with in a distributed programming system, which is my area of interest. Beyond that, they cause all the normal problems for logical transforms and such. I try to keep 'objects', especially mutable ones, to a minimum (shun mutable state). As a consequence, I disfavor trees, tables, UI models, etc. that introduce state any earlier than semantically required of them.

Put off side-effects for as long as possible, and reap rewards! (Haskell has put this philosophy to great use.)

Obviously. The question, however, was how the assignment of e_table["bob"]="Mary" affects whether TableA contains "bob", noting that e_table==TableA whenever Mouse.X > ScreenWidth/2.

Yes, "bob" is only contained in TableA whenever Mouse.X > ScreenWidth / 2, its written right there in your code :) This is pretty common actually, if I open up a new block around some existing definitions, all the definitions are inserted into the scope of the new block rather than the outer block, which is analogous to your example.

Put off side-effects for as long as possible, and reap rewards! (Haskell has put this philosophy to great use.)

Philosophically we disagree. Haskell requires us to pre-commit in other areas, like representing things as linked trees and linked lists when they aren't really linked trees or linked lists! Yes, everything can be expressed, but in a very unnatural way with respect to the natural solution of the problem.

representing things as linked trees and linked lists when they aren't really linked trees or linked lists

This argument confuses me. When is a representation ever the thing being represented? And what "are they really"?

In any case, I agree that Haskell makes some expressions awkward; I'd like to see a set primitive in Haskell (allowing us to easily express disorder and uniqueness), and I'd like to see a primitive for isomorphic identity (allowing us to easily express graphs with unlabeled points).

Due to issues of ambient authority, distribution, runtime upgrade, and composability with external services, I also disfavor how Haskell chooses to incorporate side-effects (a stream of IO flowing from Main, splittable for concurrency) after putting it off for as long as possible. But this isn't Haskell's fault; Haskell was just modeling the existing Unix/Windows processes, complete with all their faults. Reactive programming in Haskell could instead be expressed, but likely would require significant changes to Haskell's FFIs and 'main' and such.

I'll grant that working with sequencing monads (including the IO monad) is still expressing side-effects and imperative programming, and the "put side-effects off as far as possible" refers to stuff kept out of such expressions - especially of the IO monad.

But methinks you, Sean, complain about an extraneous issue. Haskell can make expressing many programs straightforward, including those with side-effects, and could do far more with better support for EDSL syntax (which is why O'Haskell and such exist, developed to provide the syntax). The reasons I would favor a set primitive is not because it couldn't be represented well enough, but rather for performance - letting the underlying implementation know about disorder, such that it may be leveraged in the representation and lazy operations.

But the whole "expression of things in Haskell in particular" remains extraneous to the benefits of "putting off side-effects for as long as possible". I would compare your argument to complaining about all reactive programming based on the pains with layout from a bad experience with Microsoft Excel.

In any case, I agree that Haskell makes some expressions awkward; I'd like to see a set primitive in Haskell (allowing us to easily express disorder and uniqueness), and I'd like to see a primitive for isomorphic identity (allowing us to easily express graphs with unlabeled points).

I'm having a hard time making sense of this.

Computational structures are inherently ordered, and sets can only be computationally simulated by hiding or ignoring this underlying ordering. Since ordering has significant performance implications, what would you hope to gain by trying to hide this at a primitive level?

Similarly, equality, identity and isomorphism are ridiculously complicated issues to handle, and you often need to customize these for the task at hand. How would it be a benefit to take a particular version as primitive and remove those choices from the programmer?

Computational structures are inherently ordered, and sets can only be computationally simulated by hiding or ignoring this underlying ordering.

Hence, I used the phrasing "express disorder", as in the developer is indicating to all interpreters (human and machine) that order is not a concern. This extra knowledge offers some freedom to perform certain transforms that would be illegal if order was relevant.

Of course humans can normally express among one another that order isn't relevant (for example, they do so by calling something a 'set' instead of a 'list'), so the purpose of a primitive is to express this property to the machine - to the optimizers, serializers, allocators, persistence system, garbage collection, etc. - such that it can be used to the most possible advantage.

Since ordering has significant performance implications, what would you hope to gain by trying to hide this at a primitive level?

The vast majority of performance implications of ordering are negative. Disorder allows greater performance. Expressing disorder allows the implementation to more effectively leverage it. Even at the small scale, CPU developers reorder operations to take advantage of controlled disorder. And the benefits of expressing disorder to the machine grow more significant with scale.

This isn't to say sets take full advantage of disorder. Sets express two properties: disorder and uniqueness. These are the properties of data collections: seeing the same data twice adds no information, and seeing two pieces of data in a different order doesn't change its meaning. Since sets match the properties of data collections, they are at least as useful as lists. The uniqueness property, however, hurts performance almost as much as the disorder helps it (though uniqueness needn't be applied except for certain observations on the set).

Similarly, equality, identity and isomorphism are ridiculously complicated issues to handle, and you often need to customize these for the task at hand. How would it be a benefit to take a particular version as primitive and remove those choices from the programmer?

I am not suggesting we "remove those choices from the programmer". A developer would have all the same choices as normal, plus an additional one to let the language handle it. The same is true for sets: if a developer wished to represent a set as a list or binary tree or lambda abstraction or OOP composite, he or she remains free to do so.

And what are the advantages of letting the language handle anything? Reduced burden on the developer, minimization of semantic and syntactic noise, potential for 'big picture' optimizations, potential for enhanced type-safety, integration with serialization, allocation, collection, etc..

My interest in isomorphic identity in particular is that there simply is no clean way to express it at the moment. Most mechanisms of building or representing unlabeled graphs involve first labeling the vertices for use in a matrix or association list or edge-set. But there is no final step that wipes up those labels or at least expresses that they carry no relevant information... they proceed to hang around forever. Since the outputs carry information about how (and where) they were constructed, that can be problematic for rewriting and optimizing graph algorithms.

I consider graphs almost as important to computation as sets, but isomorphic identity is useful even outside graphs - in many places where names have a finite scope and are used strictly to express relationships within that scope. For names in the global space we can use capabilities, but in the functional space we cannot do so without bumping into issues of referential transparency.

RE: "ridiculously complicated issues" - unless you're talking about behavioral equality, it really isn't such a complicated issue. Term rewriting systems deal with all these issues inherently. Haskell supports structural identity for canonical forms of most data structures. Expressing that a 'label' within a graph or space carries no information outside that space, in order to allow isomorphic identity, is a relatively straightforward tweak on structural identity.

so the purpose of a primitive is to express this property to the machine - to the optimizers, serializers, allocators, persistence system, garbage collection, etc. - such that it can be used to the most possible advantage.

I see what you are saying, but in the absence of a concrete design proposal, this sounds like a "sufficiently smart compiler" argument: nice in principle, messy in implementation.

unless you're talking about behavioral equality, it really isn't such a complicated issue. Term rewriting systems deal with all these issues inherently. Haskell supports structural identity for canonical forms of most data structures. Expressing that a 'label' within a graph or space carries no information outside that space, in order to allow isomorphic identity, is a relatively straightforward tweak on structural identity.

This sounds very much like alpha conversion, a notoriously knotty issue for something so conceptually simple.

Also, are you suggesting that we should violate the levels of abstraction, i.e. let the source code level and the machine level know more about each other for the sake of automatic optimizations? That seems much more dangerous to me than any benefits we might receive from it. (Plus we have C/C++ for that. ;-) )

I see what you are saying, but in the absence of a concrete design proposal, this sounds like a "sufficiently smart compiler" argument: nice in principle, messy in implementation.

A "sufficiently smart" compiler would infer where order isn't relevant, magically obtaining this information from incomplete information about where the output goes.

are you suggesting that we should violate the levels of abstraction, i.e. let the source code level and the machine level know more about each other for the sake of automatic optimizations?

No. I'm suggesting that we express our semantics in a manner that all interpreters (rather than just the humans) can grok them. Constraints must be observed (i.e. we can't be observing duplicates when aggregating a set, and we shouldn't allow regular 'folds' over the elements of a set unless we can prove the function is commutative and associative), but 'disorder' is removing a constraint relative to lists and other data types. A removed constraint does not require anything special from the 'machine level', therefore it is not a specification. Rather, it offers some freedoms.

I have elsewhere discussed 'annotations' - the ability to mark code with suggestions - suggestions to the optimizer, suggestions to the safety analysis, suggestions for code display or integration with the IDE and automated help systems, suggestions of many sorts. One might suggest a particular function be memoized, or that a particular pure function be computed or lazily. Annotations aren't allowed to affect semantics, and ignoring them must be legal. Thus, technically, laziness should be semantic in a language with divergent functions, but in total functional programming 'laziness' is strictly a performance issue and may thus be relegated to annotations. An annotated 'lazy' function might be computed eagerly by the implementation for purpose of partial evaluation or whatnot.

These annotations don't quite violate abstraction, but they may come close enough in the ways that matter.

But I was not suggesting sets and isomorphic identity as annotations. I want them as semantics. The actual implementation needn't be anything special. Most of the time, we don't worry about exactly how Haskell's lists are implemented. The same would be true for sets. The high-quality implementations of set semantics can always come later, after sets are already in use and thus applications exist for benchmarking against.

Methinks, by avoiding expression of 'set' semantics on the basis of "order has performance implications", it is you who has special expectations about relationships between the source code and the machine level. By avoiding expression of 'set' semantics where they are appropriate, you hinder efforts to produce a quality 'set' implementation that (long term) promises performance and much, much greater scalability.

A "sufficiently smart" compiler would infer where order isn't relevant, magically obtaining this information from incomplete information about where the output goes.

You've leaped from "sufficiently smart" to "miraculous": this would clearly violate Rice's Theorem in the general case.

You are still putting a lot of onus on the compiler to do the right thing under whatever circumstances it finds itself in.

I have elsewhere discussed 'annotations' - the ability to mark code with suggestions - suggestions to the optimizer, suggestions to the safety analysis, suggestions for code display or integration with the IDE and automated help systems, suggestions of many sorts.

This topic has been discussed here as well, and it is not exactly untried: C has a bunch of these like volatile, register, etc.

The problem with such annotations is that they blur the abstraction levels and make code less deterministic, and thus harder to debug. They are also harder to learn to use properly, because it is harder to get good feedback on what they do and when they help or hurt. They can also have very odd secondary consequences.

Methinks, by avoiding expression of 'set' semantics on the basis of "order has performance implications", it is you who has special expectations about relationships between the source code and the machine level.

On the contrary, my position on this is fairly simple: source code is the place for algorithmic reasoning. When I say "performance" in this case, I mean algorithmic complexity not constant factors performance, which often IS the domain of compilers and machines.

If you don't to deal with the implementation of sets, just use a standard set implementation from your library. No messing with the semantics of the language is required, nor any smart compilers.

You are still putting a lot of onus on the compiler to do the right thing under whatever circumstances it finds itself in.

Let's compare this to another situation: representing the pervasive "list" concept. A list is either cons(Head Rest)|nil. But there are dozens of tweaks one might make on a list's implementation for performance:

1. We can make the list compute lazily to avoid computing more than we need. Sometimes, this offers a big performance enhancement.
2. Similarly, we can make it lenient or parallel.
3. We can chunkify the list, to reduce the memory overhead spent indirecting through pointers, and to improve memory locality.
4. We can represent the list as a rope or finger tree, to allow high-performance addend, subrange, positional element access, and even such things as logical reversals.
5. If a functional list is represented in a linear context, we can sometimes updates to the list element directly.
6. If we know in advance a list is going to be consumed by zipping with another list, we might be able to zip them at construction.
7. Lists as reactive expressions may want some tweaks for change propagation. These tweaks are also likely to be special based on concurrency, persistence, etc. issues.
8. We may wish to tweak allocators based on issues of persistence, performance, or concurrency issues.

One could go on and on, of course. And one could make the same arguments about data trees, and (of course) about sets.

Now, we have a couple different philosophies:

• We give programmers access to all the minutiae details they need to implement all the different variations of list, of set, of . The programmers then are responsible for managing dozens of variations of the same data structure, of remembering all the do's and do-nots, of integrating them with FFIs and serializers and smart pointers and concurrency...
• We make this the responsibility of the compiler, and we offer it some help via such as primitives (like linear typing) and annotations (i.e. suggest parallelization). The compiler chooses or constructs a variation that meets all known requirements. The decision is hidden from the developer, but influenced by the developer.

I'd think one should be consistent when choosing this philosophy.

C++ obviously chooses the 'give programmers access'. This results in a low-level language where the developers are responsible for most optimizations. When the context isn't fully known up front, the developers often make a choice that later requires a lot of workarounds to integrate with the rest of the system.

Haskell developers, OTOH, largely choose to let the implementation handle the low-level details, thereby putting the "onus" on the compiler to - your words - do the right thing under whatever circumstances it finds itself in. There are, of course, a few exceptions to prove the rule; e.g. Haskell's vectors could have been achieved with lists and a few annotations about usage.

Except I don't believe it is an 'onus'. The compiler is doing a right thing even if it uses just one list implementation for everything. It might compare poorly in benchmarks, but it still meets all semantic requirements. I consider it an opportunity: a compiler has opportunity to improve performance based on knowledge of a restricted context, and a developer may advise the compiler of this opportunity.

The problem with such annotations is that they blur the abstraction levels and make code less deterministic, and thus harder to debug. They are also harder to learn to use properly, because it is harder to get good feedback on what they do and when they help or hurt.

Sure, they have all these problems. But you need to add some perspective: how much do they hurt compared to the alternative philosophy of simply forcing the programmers to deal with a Cartesian product of variants and context-based 'tweaks'?

The annotations are there to support developers in collaborating with the compiler to meet requirements. Getting rid of the annotations does not get rid of the requirements. Getting rid of the annotations only means that there is no more collaboration with the compiler.

On the contrary, my position on this is fairly simple: source code is the place for algorithmic reasoning.

If you don't to deal with the implementation of sets, just use a standard set implementation from your library.

Ah, I take a different position: language is a tool for expressing and composing concepts. Algorithms are semantic noise - a sometimes necessary evil due to an inexpressive language, a bit like defining the idea of folding a flag in terms of a specific procedure for doing so.

I don't want sets as a primitive to "avoid dealing with their implementation". I want them as a primitive because Haskell's implementation involves a ton of semantic dissonance - the ordered lists representing a set have different meaning to the machine than to the human, and that (to me) is a fundamental language problem.

Of course, not everyone shares that philosophy, so I don't use it in arguments. Instead, I reference the symptoms of it, such as potential performance. In the case of a set primitive, the opportunity for scalable performance is a direct consequence of the more precise semantics match between what the developer is trying to say and what the interpreter is understanding.

I consider it an opportunity: a compiler has opportunity to improve performance based on knowledge of a restricted context, and a developer may advise the compiler of this opportunity.

I still think your imputing too much intelligence to the compiler relative to what is currently possible. Human beings aren't that great at taking advice unless you spell it out for them; machines are even worse. ;-)

language is a tool for expressing and composing concepts. Algorithms are semantic noise - a sometimes necessary evil due to an inexpressive language, a bit like defining the idea of folding a flag in terms of a specific procedure for doing so.

This sounds like we are back to the "Do What I Mean" principle. You certainly can create a generic "fold the flag" command, but if it doesn't fold it the way you like, or if it doesn't work on flags of odd shapes (say the flag of Nepal), you are kind of hosed.

Declarative programming is all well and good in some fairly restricted circumstances, but at present anyway, algorithms are still pretty central to programming.

I want them as a primitive because Haskell's implementation involves a ton of semantic dissonance - the ordered lists representing a set have different meaning to the machine than to the human, and that (to me) is a fundamental language problem.

What is wrong with something like Data.Set or equivalent thereof? You don't have to use ordered lists or trees directly.

Human beings aren't that great at taking advice unless you spell it out for them; machines are even worse. ;-)

Wrong, Marc. Humans aren't that great at taking advice. You can end the sentence there. :-)

Machines will at least take advice if you spell it out for them.

I've done quite a bit of work with heuristics based interpretation, and I'd say machines can take advice quite well if they have a framework and context for understanding it. The degree to which it needs to be "spelled out" really depends on how much context already exists.

This sounds like we are back to the "Do What I Mean" principle. You certainly can create a generic "fold the flag" command, but if it doesn't fold it the way you like, or if it doesn't work on flags of odd shapes (say the flag of Nepal), you are kind of hosed.

If you can't say what folding the flag means, without saying how to do it (even with a 'generic' definition), then your language is too weak for that expression. You assume too much: I never said I wanted a program that folds the flag. Maybe I want one that recognizes the act when it is performed by others, such that I can trigger events (while the flag is being folded, play the anthem...).

Declarative programming is all well and good in some fairly restricted circumstances, but at present anyway, algorithms are still pretty central to programming.

I agree. Algorithms mean the language is low level, but I don't believe we can escape them. To some degree, we can abstract away from them (using such things as multi-methods, rules-based programming, and strategy pattern) and if we ever start developing in languages integrated with large databases of strategies and algorithms (and perhaps possessing some limited ability to create its own) we may very well avoid algorithms in common programming, or at least relegate them to 'advice' rather than semantics.

What is wrong with something like Data.Set or equivalent thereof? You don't have to use ordered lists or trees directly.

Data.Set has a few semantic problems. For example, you cannot implement Data.Set's 'elems' or 'toList' at a referentially transparent functional layer if you want to support semantic disorder.

One also won't be able to take much advantage of it - i.e. for allocations, serializations, reactive change propagation, distribution and parallelization, etc.

I also have a thing against nominative typing. It doesn't fit well with distributed programming. (One bumps into all sorts of versioning, upgrade, naming problems when faced with the questions: is my Data.Set is the same as your Data.Set?)

Other than those things, I don't have a problem with the sort of abstract type with interface exhibited in Data.Set. Abstract types serve a useful role, filling in where language semantics fall short. If I was refused a first-class set type that tells my interpreter I'm using a set, either an abstract type or the use of a more OO-functional-style "codata" record would be my next choice.

I've done quite a bit of work with heuristics based interpretation, and I'd say machines can take advice quite well if they have a framework and context for understanding it. The degree to which it needs to be "spelled out" really depends on how much context already exists.

I guess this is the heart of my concern. I have no doubt that heuristics can be very effective in highly specific situations where context is constrained and well-understood.

But when you talk about adding a primitive to a general-purpose PL, by definition you don't know in advance what context it is going to be used in. It could be used in any context, and it is really hard to give it any heuristics that aren't going to fail wildly for some unexpected but real context that comes along.

I think this is a general rule for designing for the special case vs. designing for the general case. Special cases often have clever automated solutions, but general cases are often better solved by keeping things simple and "dumb".

Each case where a primitive is used can be considered separately. Some will be special cases, subject to optimizations. Some will lack constraints on context and will need to fall back to a simple and "dumb" general case solutions.

Even the dumb solution could be reasonably high quality, supporting O(lg(N)) ops, sharing structure, etc. - though this might not be ideal for the final context.

Some sets may specialize later. A JIT allows this to some degree, but is often difficult to apply (the analysis cost might counterbalance the specialization benefits). More broadly useful, for immutable sets one can also re-specialize after any serialization or otherwise when producing a new set from an old one (i.e. wherever shared structure for the set itself ain't worthwhile). That is, upon receiving a message across a network, one will need to load this 'set' into some data structure on the other side, and the context will often be well known - i.e. whether the set will be processed in a linear manner or whatnot.

Are you assuming that a primitive in a general purpose language requires one 'general purpose solution to rule them all' that handles every instance of a set?

Are you assuming that a primitive in a general purpose language requires one 'general purpose' solution for every instance of a set?

I'm afraid I didn't follow you very well in this post, but I would say that for a good PL design, I would expect a primitive to be generally applicable within the language and behave reasonably consistently wherever it is used.

As far as I understand, it seems that these properties wouldn't hold true in your proposal.

Would you say that tail recursion is not "good PL design" because the 'apply' primitive should be generally applicable and should "behave consistently wherever it is used"? What about function inlining? or partial evaluation? or selecting eager vs. lazy application based on dataflow?

If you don't reject the use of context for selecting implementation for each use of the 'apply' primitive, then why would you reject similar use of context for selecting implementation for each use of the 'set' primitive?

The set primitive can still be applied in arbitrary contexts. The developers can still make the same observations on a given set. But, based on which observations are made, and in which context the set primitive is applied, there may be optimizations that offer better performance by whichever metrics are most relevant in context.

Based on your statements, I'd assume you reject all optimizations because they result in 'inconsistent' behavior.

You two have already wandered way off from the original topic, and it's been quite entertaining to read, so I don't have to worry too much about derailing you further. You claimed "Computational structures are inherently ordered, and sets can only be computationally simulated by hiding or ignoring this underlying ordering." and from what I see below dmbarbour either agrees with you, or doesn't disagree enough to contest this particular point.

I think that is an astoundingly bold claim that is worth digging into a little. What do you mean by "computational structure"? It seems below that you have concrete representations of data-structures in mind, although the term could be interpreted in a much more general way. What do you mean by "inherently ordered"? Again, from the conversation that follows below I think that you are thinking of the spatial layout of data-structures, although that is only one possible ordering on computational structures.

Finally, with respect to your exact definitions of the above, why must such a structure be inherently ordered?

Finally, with respect to your exact definitions of the above, why must such a structure be inherently ordered?

I thought no on would ever ask. ;-)

In mathematics, it is perfectly OK to say "let x be a set of y elements", and poof it is "there", conceptually without ordering from the start.

In computation, any structure must be created in inductive steps which induces an order on the sequence of these steps, and all components must be referenceable. Any system of references is isomorphic to one or more ordering, with the obvious default to take the order of creation of the references. We take it for granted that we can iterate over computational structures, which also implies an ordering.

From this point of view, at a basic level any computational structure has at least one order, and may in fact have multiple basic orders to choose from.

Hopefully without opening too big a can of worms, one way to phrase what I'm saying is that the Axiom of Choice holds trivially for all computational structures.

Obviously in a practical sense on a von Neumann machine, you can always induce orders based on the numeric representations of memory locations and data values, again possibly with many choices of ordering for more complex structures. But I see that as a consequence of the fundamental conceptual ordering of computation rather than as the cause.

Haskell can trivially encode sets with no notion of order:

 type Set a = a -> Bool 

With an enumerable type for 'a, you can build up a finite set datatype as a pair containing a size and a membership function supporting all of the usual operations, such that there is no inherent notion of order in the elements of type Set a.

Haskell can trivially encode sets with no notion of order

Just because the order is hidden from you by the interface doesn't mean the order isn't there. Just iterate over the set and it magically reappears.

You can't iterate over Matt's set.

You could iterate over all instances of an enumerable type, though, asking for each instance whether it is a member of the set, potentially stopping if you know the size of the set (this is what Matt was saying above).

But, really, that is not the sort of 'set' I'm wanting.

You can't iterate over Matt's set.
You could iterate over all instances of an enumerable type

The enumeration order of the parameter type induces an iterative order on the set.

Perhaps, though that seems a stretch. You can't really say the order is a property of the set itself, and most enumerable types have more than one enumeration order (I think the only exceptions are the 0 and 1 types). Further, the order you're discussing here is independent of the spatial properties of the description of the set both at the source layer and the underlying representation layer.

Of course, given that not all types we want in sets are enumerable, I think that Matt's argument isn't particularly relevant.

I agree with your earlier claim that there is always an ordering in the representation, starting with how the set was described or represented in source code. Whether this ordering has semantics and thus needs to be maintained from operation to operation or over time is an entirely separate issue. (In practice, represented order may vary 'over time' - independent of in-language operations - due to persistence and redundancy and distribution issues.)

A set may legally offer a different order each time you iterate it - but you cannot iterate a set in a pure referentially transparent layer; you need authority for non-determinism, i.e. through an IO monad or Oracles. What you can do at a referentially transparent layer is aggregations with commutative and associative functions. A legal aggregation on a set is to produce a sorted order.

A set may legally offer a different order each time you iterate it - but you cannot iterate a set in a pure referentially transparent layer; you need authority for non-determinism

This is starting to sound like a very odd primitive to add to Haskell. I can only conclude that I really don't understand what you are trying to do with it. ;-)

Everything you could do in Haskell would be RT. Therefore, you could not iterate in pure Haskell. Sets are subject to a variety of useful RT operations that do not involve iteration. These include union, intersect, joins, logic queries, comparison against other sets such as the empty set, aggregations. Iterating over sets isn't among my priorities.

Aggregations serve as the 'folds' of sets but for RT require commutativity and associativity. With the right aggregation functions, one could produce sorted lists from sets. Unfortunately, arbitrary aggregations are very difficult to prove safe, so most of the time we stick with sums and counts and such.

When necessary, i.e. for display or performance, one can grab an authority for non-determinism from IO to help display a set or perform an unproven aggregation in map-reduce style.

But to be honest, Haskell is not really my target language. I spoke true that I'd like semantically precise sets in Haskell, but I'm pursuing the concept actively for another language that handles the IO integration very differently from Haskell.

If you define your computational model over something inherently ordered, then every computational structure you manipulate within that model will have an inherent order. If you describe your computation as state mutations over a numerically addressed memory, then yes there is an inherent order. If you are manipulating a sequential tape, then again there is an order. If you are reducing function applications, and those functions have ordered parameters, then sure, there again is the inherent order.

But not all models are defined over something inherently ordered. If the basis of your model is sets then you can build unordered structures. If you realise this model with something that implements set membership directly in silicon, then you can actually build a real machine that performs computation over unordered structures. One obvious way to do this would be to simulate perceptrons for the set membership, or some form of associative lookup.

If you build graphs out of these unordered collections then there is no "inherent" order to process them in. This doesn't provide any kind of advantage that I'm aware of, but it does motivate the use of representations that are not inherently ordered in your other thread.

I think you can claim the Axiom of Choice without invoking order, and it should hold trivially for all computational structures - but then again, I don't really know what infinite computations "are".

But not all models are defined over something inherently ordered.
If the basis of your model is sets then you can build unordered structures.

To give some context, my perspective is shaped by reading a lot of papers related to making computation acceptable in terms of mathematics.

If you stare at Scott Domains long enough, they start to look like a Rube Goldberg device intended to ensure that all the order inherent in computation is preserved in a world (mathematics) that takes the unordered set as a primitive. A lot of intuitionistic accounts strike me as similar, in that they have to posit seemingly weird restrictions on simple things.

This has led me to believe that unordered sets are the wrong primitive for computation, and accepting sequential order as primitive for computational structures is a simpler and more natural account, and also more consonant with actual practice.

You can erase all that and start without order, but you'll just end up having to do strange and complicated things to get it back when you need to account for how things really work.

This argument confuses me. When is a representation ever the thing being represented? And what "are they really"?

An abstraction is an interface and the implementation is irrelevant in what the abstraction is, although what the abstraction "is" is highly relevant to the implementation.

But methinks you, Sean, complain about an extraneous issue. Haskell can make expressing many programs straightforward, including those with side-effects, and could do far more with better support for EDSL syntax (which is why O'Haskell and such exist, developed to provide the syntax). The reasons I would favor a set primitive is not because it couldn't be represented well enough, but rather for performance - letting the underlying implementation know about disorder, such that it may be leveraged in the representation and lazy operations.

Ok, let me re-phrase my argument: I'm more concerned with design vs. implementation. If a reactive table is implemented underneath by a magic imperative implementation or has a more pure implementation out of smaller magical primitives, or is completely pure, I'm not really thinking about that. But I do require that the table be efficient enough to be usable! For example, if a statement with very local effects in the text editor is changed, I don't want the whole world to be recomputed.

Now, I dislike Haskell simply because it takes my choices away from me. I can't define abstractions that hide details without those abstractions being so slow to be unusable. In theory you are correct, there could be some super smart compiler + annotations that makes my abstraction viable. But this doesn't exist yet, and I live in the present so...

But this is really my fault, when you said "you'd express it purely functional", I shouldn't have replied to that since its not very related: how you choose to express a declarative reactive table should be oblivious to its user. They just consume it, they see no side effects, while whether or not side effects go on behind the abstraction is a detail.

I don't see the relationship: these are definitely tables but are models of computation rather than reactive data structures. The table I've discussed isn't really a visual formalism, and its not really a spreadsheet, its just the declarative/functional reactive programming version of a "hashtable." Or maybe I'm missing something?