The Forum for Discussion about The Third Manifesto and Related Matters

Please or Register to create posts and topics.

Operators on tuples/'Expressively complete'/RM Pre 6

PreviousPage 2 of 5Next
> Everything else therefore must be expressed in terms of those three AFAICT. [from your earlier message]
You're perhaps suggesting the (or a) minimal set of operators should more closely follow Appendix A? We should note Hugh's cautions that A is an algebra for pedagogical purposes, not intended as a programming language, but yes-ish ...
We could adopt Appendix A's approach that t1 project { attribute-name-list } is equivalent to t1 REMOVE {<heading-of-t1> REMOVE attribute-name-list }. And it turns out from the definitions I gave that t1 TupleProject t2 === t1 TupleRemove (t1 TupleRemove t2). [Aside  this again shows the usefulness of taking a tuple to denote its heading and/or its set of attribute names.] For practical purposes (since I've implemented my suggestions) I "have allowed ourselves the luxury (some might think) of including" both operators [as Appendix A puts it].
From a more theoretical standpoint, this avoids introducing into the semantics/ontology <heading-of-t1> or attribute-name-list; it avoids REMOVE (or - or however you want to spell it) operating on attribute-name-lists as well as on tuples and on relations.
I'm also a little suspicious of REMOVE as it appears in Appendix A -- I'd go so far as to say there are two operators masquerading under the same spelling:
  • REMOVE { attribute-name-list } gets 'compiled' into a nesting of
  • REMOVE attribute-name.
If that's one operator, it's powerfully polymorphic. (From the standpoint of higher-order typing, I'd describe it as 'poykinded'.) When I've raised this issue before, Hugh's response has amounted to: to the right of REMOVE is syntax, not an operand/you couldn't supply a variable whose value is an attribute-name-list or an attribute-name.
Quote from dandl on September 29, 2022, 4:12 am

Assume a dataset in the form of a 'tuple soup', each tuple consisting of:

  • a set of names (the 'heading')
  • Values corresponding to each of those names
  • A name and value together constitute an attribute. Each value belongs to a type, so each name also carries the type of that value.

This is a perfectly plausible data structure. Perhaps many of those tuples contain 'key' values, and the tuples are disparate facts known about each key.

Errm a TTM 'heading' is a set of name-type pairs. This becomes important when we include relation (value)s; they also have a 'heading' applying for all tuples in the relation -- which 'heading' is exactly the same ontology as a tuple's 'heading'. If you want to introduce some different thingy with some different semantics, just for tuples/tuple soup, don't call it 'heading'.

To clear up one of the items on your list before I get into the weeds:

4. T1 + T2 merges two tuples, or fails

...

Now why do you want something called JOIN?

AFAICT your + is exactly the same as JOIN is exactly the same as Erwin's proposed UNION. Note my proposal _wasn't_ for a primitive called JOIN. But rather for primitives from which you could define a possibly-failing JOIN-alike. What I don't want is any primitives that could fail -- especially if failing is the only means to communicate some perfectly usual condition back to the calling program. A well-typed +/JOIN/UNION can go wrong -- that is, fail to produce a well-typed result (or indeed any result at all).

So where you say below "will always return a new tuple value"; that's just not the case.

 

The plausible operations on this 'tuple soup' will always return a new tuple value. The primitives are:

  1. T() is the null tuple
  2. T.extend(name, value) adds an attribute to a tuple if it does not already exist.
  3. T.remove(name) removes an attribute from a tuple if it exists
  4. T1 + T2 merges two tuples, or fails
  5. TI - T2 removes attributes (names) in one found in another, or fails

AFAICT it is straightforward to write queries that can transform the tuple soup in various ways, including  adding new tuples (facts) and filling them out with default values, in order to extract relations from the soup.

What is a name in extend/remove? Must it be a literal? Can it be a variable that ranges over name literals? If so, how does the semantics and typing go for that?

I don't like those "if it [not already] exist[s]". It makes static typing intractable for functions that take tuples as arguments. That is, unless the function is specified to take only a specific tuple type as argument. In which case what you exactly can't do is build your own JOIN-alike from the provided primitives. (Or, equivalently, build a type-safe TupleExtend per my o.p. from your provided primitives.)

How does T.remove(name) differ from T1 - T2 in which T2 is T().extend(name, don'tcare)? (I might have saved you a primitive.)

Where my o.p. said "I'm assuming the D-like already supports syntax to create Tuples from attribute names and expressions", I intended that would include syntax for the null tuple TUPLE{}; Then TUPLE{ PNO "P123", SNO "S456", QTY  f(x + y) } we could take as a shorthand for extending the null tuple with three attributes. That seems to me to comfortably avoid introducing name as a further entity in the syntax/semantics.

... why do you need more than this?

I still hanker after an operator looking like PROJECT. (And I still dislike that Tutorial D lacks an explicit operator for projection.)

Set union is a total function from the set of pairs of tuples to the set of tuples, TTM tuple union is just a partial function on same.  If partial functions cause any kind of issue for you, maybe it might help to see how your toolset/language/whatever deals with other partial functions such as natural logarithm, arc sine, inverse cumulative Gauss integral, substring (e.g. SUBSTR("",2,1)), numeric division (e.g. DIV(7,0)), ...

Quote from AntC on September 29, 2022, 7:35 am

I still hanker after an operator looking like PROJECT. (And I still dislike that Tutorial D lacks an explicit operator for projection.)

http://www.thethirdmanifesto.com, section "Reference Material", "Tutorial D" has a definition for <tuple project> on pg 18/47.  So it's unclear what you mean by this.

Or maybe you meant "lacks an explicit operator NAME [that can serve as a keyword in the language] for projection", but that is not what you said.

Sorry for joining this thread rather late in the day.  It's too difficult for me to digest it all now but I'd like to make sure the following points are understood.  They probably are, but I'm just making sure ...

  1. Relations r1 and r2 are joinable iff all common attributes have the same type in both operands.  This can be checked at compile time.
  2. Tuples t1 and t2 are joinable (a.k.a. unionable) if all common attributes have the same value in both operands.  This can't be checked at compile time.
  3. As Erwin has mentioned, the presence of tuple join, whether under or over the covers, is a necessary building block for relation join.  TD makes it a syntax element for pedagogic reasons among others.

Hugh

Coauthor of The Third Manifesto and related books.
Quote from Hugh on September 29, 2022, 3:06 pm

Sorry for joining this thread rather late in the day.  It's too difficult for me to digest it all now but I'd like to make sure the following points are understood.  They probably are, but I'm just making sure ...

  1. Relations r1 and r2 are joinable iff all common attributes have the same type in both operands.  This can be checked at compile time.
  2. Tuples t1 and t2 are joinable (a.k.a. unionable) if all common attributes have the same value in both operands.  This can't be checked at compile time.
  3. As Erwin has mentioned, the presence of tuple join, whether under or over the covers, is a necessary building block for relation join.  TD makes it a syntax element for pedagogic reasons among others.

Hugh

I'm confident 1&2 are most definitely understood by all [participating in this thread].  [Except perhaps for the 'a.k.a. unionable' part where some certain people might observe that "being unionable" only means the very same thing if the upfornt requirement is that the result itself also be a TTM tuple.]

Quote from Erwin on September 29, 2022, 1:46 pm

Set union is a total function from the set of pairs of tuples to the set of tuples, TTM tuple union is just a partial function on same.

You appear not to be understanding the question I posed: 'Expressively complete' does not mean 'follows TTM slavishly'. I'm asking: are there operations on tuples that my choice of operators can't support? So far from you -- to the extent you're addressing that (not much) -- the answer is 'No'. Thank you. Thread over.

Specifically: if you want a tuple-join function that's partial, I've told how to build it from the primitives I'm supplying. How you spell that operator is up to you.

  If partial functions cause any kind of issue for you, maybe it might help to see how your toolset/language/whatever deals with other partial functions such as natural logarithm, arc sine, inverse cumulative Gauss integral, substring (e.g. SUBSTR("",2,1)), numeric division (e.g. DIV(7,0)), ...

For each of those examples, there's ways for the program to test for whether the function's arguments will give a well-defined result _before_ calling it. (Check a divisor for being zero, for example.) I'm not aware of a partial function in regular general-purpose languages for which the _only_ way to tell if it produces a well-defined result is to call it then catch an exception. That would be pretty much the definition of a language failing to be general-purpose, in my book.

 

Quote from Hugh on September 29, 2022, 3:06 pm

...

3. As Erwin has mentioned, the presence of tuple join, whether under or over the covers, is a necessary building block for relation join. ...

 

Thank you Hugh, sure. Equally 'under the covers' or not must be a building block for discovering if two tuples are joinable. If the only way provided is to throw an exception when not joinable, I strongly object to the aesthetics; I'll dispute whether that's 'expressively complete' (because IMO that makes it fall outside the language) -- and since that's my term of art, I'm the Pope and I know what I like.

Quote from AntC on September 29, 2022, 9:06 pm

I'm asking: are there operations on tuples that my choice of operators can't support? So far from you -- to the extent you're addressing that (not much) -- the answer is 'No'. Thank you. Thread over.

I suppose a function that maps, say, a tuple TUP {ANM1 namevalue1, ANM2 namevalue2} onto TUP {namevalue1 ANM1, namevalue2 ANM2} ("swap names for values and vice-versa") is going to be out of reach, but these are so pathological that they are typically out of scope in just any language.

Furthermore, if you intend to "unroll" stuff that bears resemblance to "multiple simultaneous rename" into nestings of single attribute removes, you might be in trouble for a function that maps, say TUP{ANM1 i1, ANM2 i2} onto TUP{ANM1 some_f(i2,i1) , ANM2 some_other_f(i1,i2) }.  Maybe this is to be addressed by using the tuple selector which allows you to select tuples of just any type.  If that's the case, then the only candidate functions remaining that could make the answer to your question "yes", expose the following characteristics :

  • must involve arguments like ANM1 i1 and ANM2 i2 above that cannot be eliminated (i.e. are effectively needed and used to determine the result)
  • additionally also involves an argument like t2 in your examples/definitions that is used for manipulating presence of "additional" attributes or t'other way 'round.
  • and where "splitting" ("currying" ???) the operation cannot be done because removal of t2 interferes with the other computations and removal of the other computations interferes with the operation related to t2.

Tall order, it seems.  Especially since the very existence of the concept of function currying might imply that "cannot be done" as per above, can never happen.

But you have failed in almost everything you wrote in this thread to be perfectly clear over your intentions.  You have left it in the vague whether your intent is merely definitional (as per being like A algebra) or truly operational (as per "test cases to run in Haskell").  And that is not to mention the outright contradictions as in " there's no requirement with TupleProject, TupleRemove that ... ; nor that corresponding attribute names be at the same attribute type. In case of type mis-match, the attempted equality test will get rejected at compile time. ".  (If "the attempted equality test will get rejected at compile time", then the "requirement that corresponding attribute names be at the same attribute type" really is quite there, isn't it ?)

But I'll apologise for having forgotten why it's always a bad idea to try and be helpful with, or rather despite, your hopelessly poor writing.  This time I'll try and remember.

Quote from AntC on September 29, 2022, 9:06 pm

I'm not aware of a partial function in regular general-purpose languages for which the _only_ way to tell if it produces a well-defined result is to call it then catch an exception. That would be pretty much the definition of a language failing to be general-purpose, in my book.

If the only way provided is to throw an exception when not joinable, I strongly object to the aesthetics; I'll dispute whether that's 'expressively complete' (because IMO that makes it fall outside the language) -- and since that's my term of art, I'm the Pope and I know what I like.

I thought you said you were after "minimal set".  I claim that "just try and catch the exception if you get thrown one" is functionally sufficient and is, therefore, such a minimal set.  But you reject that on grounds of "aesthetics" (you did not say you were after "aesthetics" in o.p.) and on grounds of "fails to be general-purpose" (nor did you say you were after "general-purpose" - and especially did you not say you were after "general-purpose" only in the sense of what the term means in your own idiosyncratic book).

That's a blatant case of changing goalposts in my book.

Quote from Erwin on September 30, 2022, 10:30 am

I suppose a function that maps, say, a tuple TUP {ANM1 namevalue1, ANM2 namevalue2} onto TUP {namevalue1 ANM1, namevalue2 ANM2} ("swap names for values and vice-versa") is going to be out of reach, but these are so pathological that they are typically out of scope in just any language.

I think the position within TTM is that attribute names are not values, and vice versa. (An Industrial D might support reflection/obtaining the 'print name' of an attribute as a CHAR; but not support turning a CHAR into an attribute name.) I think (TTM-style) Tuple is not the data structure for this case. Rather, that's an Association List.

Furthermore, if you intend to "unroll" stuff that bears resemblance to "multiple simultaneous rename" into nestings of single attribute removes, you might be in trouble for a function that maps, say TUP{ANM1 i1, ANM2 i2} onto TUP{ANM1 some_f(i2,i1) , ANM2 some_other_f(i1,i2) }.  Maybe this is to be addressed by using the tuple selector which allows you to select tuples of just any type.

What we can't do is write functions that select attributes by position -- because TTM insists tuples are unordered. By the same token, I've assumed there wouldn't be a way to take THE_VALUE( ) from a singleton tuple anonymously [**] -- because you wouldn't know what attribute name that was/you wouldn't know its type/it would be beyond type inference. So the only way to access attribute values is via attribute name. Then using the operations I specified:

-- TUP{ANM1 i1, ANM2 i2} onto TUP{ANM1 some_f(i2,i1) , ANM2 some_other_f(i1,i2) }

multiple_simultaneous_rename :: TUP{ANM1 INT, ANM2 INT} -> TUP{ANM1 INT, ANM2 INT};
multiple_simultaneous_rename( t ) =df TUP{ ANM1 some_f(THE_ANM2(t), THE_ANM1(t) ), ANM2 some_other_f(THE_ANM1(t), THE_ANM2(t)) };

That syntax is a mashup of Tutorial D with Haskell: the last line is the function implementation. The line above is a signature (indicated by ::) of the function, shown as type-of-arg -> type-of-result.

I'm not entirely sure what you mean by " the tuple selector which allows you to select tuples of just any type." Note I included only primitives to select THE_<attrName>( ) from a tuple. The host language's usual type inference would derive the type of that attribute's value -- or leave it polymorphic if insufficient signatures known. If your D fixes the attribute's type from its name, that's what I mean by "derive".

If that's the case, then the only candidate functions remaining that could make the answer to your question "yes", expose the following characteristics :

  • must involve arguments like ANM1 i1 and ANM2 i2 above that cannot be eliminated (i.e. are effectively needed and used to determine the result)
  • additionally also involves an argument like t2 in your examples/definitions that is used for manipulating presence of "additional" attributes or t'other way 'round.
  • and where "splitting" ("currying" ???) the operation cannot be done because removal of t2 interferes with the other computations and removal of the other computations interferes with the operation related to t2.

I certainly expect you might write a function to access attributes ANM1, ANM2 of some tuple argument which has possibly other attributes unknowable from within the function. The function's implementation would as above, grab THE_ANM1(t); TupleRemove those two attributes from t; TupleExtend the leftover with the two attributes with calculated values.

 

Tall order, it seems.  Especially since the very existence of the concept of function currying might imply that "cannot be done" as per above, can never happen.

I'm not sure you're using "currying" appropriately there. Mentioning only some of the attributes of a tuple is not currying: the whole tuple is a single argument to the function.

... You have left it in the vague whether your intent is merely definitional (as per being like A algebra) or truly operational (as per "test cases to run in Haskell").

I started by referencing RM Pre 6. A few lines later "the D-like". So no, that's not an algebra. Functional programming looks more like an algebra (no flow-of-control; no destructive update of 'variables'; no 'variables' in that sense) -- in the same way that the non-procedural parts of SQL SELECT look more like an algebra. I'll go wash out my mouth now.

And that is not to mention the outright contradictions as in " there's no requirement with TupleProject, TupleRemove that ... ;

"... that the r.h. operand's attribute names be a subset of the l.h. operand"

If you want 'safe' versions of those operators that do require the r.h. operand's attribute names to be a subset, you put a type constraint on the version: r.h. operand TupleRemove l.h. operand must be null tuple.

nor that corresponding attribute names be at the same attribute type.

That's not a requirement from TTM -- much as you (or me) might prefer so. But for the implementation of TupleJoinable's == test, that does become a requirement (as you note), checked at compile time. Again you could build a type constraint from the primitives I give -- if you insist the attributes in the r.h. operand of TupleProject &co have the same attribute types as l.h. operand.

In case of type mis-match, the attempted equality test will get rejected at compile time. ".  (If "the attempted equality test will get rejected at compile time", then the "requirement that corresponding attribute names be at the same attribute type" really is quite there, isn't it ?)

 

Yes it is, and intentionally so: attributes in common between two tuples to join must be at same type; same rule as for attributes between two relations to join.

Note ** "THE_VALUE( ) from a singleton tuple anonymously". I believe Tutorial D allows this -- or at least allows it to apply to relation values. But then also acknowledges that might fail at run-time because the relation value is not a singleton. Since my proposed operators are polymorphic (don't need to mention specific attribute names or fully stipulate Headings); I can't guarantee the result from a nesting of operators is a tuple with a single attribute. (And therefore also don't know the anonymous attribute(s) type(s)) So I'm not supporting THE_VALUE( ). Is that an insurmountable limitation?

Quote from AntC on October 1, 2022, 10:18 am

TupleExtend the leftover with the two attributes with calculated values.

My point with "interferes" was in the case when the "leftover" no longer has everything it takes to calculate the values.  I suppose it should always be possible to replace whatever reference in the calculations remains that cannot be resolved in the "leftover" with a reference to some "original source that was used to produce the leftover" where the reference can indeed be resolved.  Presumably, your answer tried to express the same thing so we might not be at odds.  It might make things "unwieldy" for the writer of the expressions, but that's not an issue when the problem is just "completeness".

PreviousPage 2 of 5Next