spec/comprehension: string construction support

[cueckoo]

Originally opened by @rudolph9 in cuelang/cue#113

@mpvl Would you folks be open to extending the spec of comprehensions to support the construction of strings?

Given and string is effectively an array of char bytes it like it fits the existing spec with regard to the construction of an array.

Obviously the import "strings" built in package is able to achieve this functionality but it seem natural to include it in the language core.

Proposed syntax follows:

strAry = ["bar", "buz"]
joinedStr: "\( str for str in strAry )"

Which would evaluate to:

joinedStr: "barbuz"

I would expect to the following to be valid:

import "strings"

strAry = ["bar", "buz"]
joinedStr: "\( str for str in strAry )"
joinedStr: strings.Join(strAry, "")

[cueckoo]

Original reply by @mpvl in cuelang/cue#113 (comment)

Personally I would expect there to be spaces between the strings. Is there precedence for this interpretation in other languages?

It seems to be very specific functionality to make it in to the spec. Most of the recent features were neutral to the size of the spec, or even shrunk it a bit. This will have a fairly large impact with, seemingly, very little benefit. Note also that using strings.Join in your example is shorter, and in my view, also clearer. I would be more inclined to implement a feature that automatically inserts import statements (like goimports).

That said, we have been thinking about a reduce functionality. This cannot be done conveniently with a builtin, as CUE doesn't have lambdas (although they exist internally). Picking some arbitrary syntax for now, you would be able to write

joinedStr: for y in strAny with x="" reduce x+y

But also here, using strings.Join would be shorter and clearer.

[cueckoo]

Original reply by @rudolph9 in cuelang/cue#113 (comment)

I thing the introduction of reduce would suffice my need. It could also be used to eliminate the existing comprehension syntax since arrays and structs could be constructed in the manor too.

detailed benefits and use case

I haven't comprised formal proof but my intuition is cuelang is largely a context-free grammar and could be modeled as a context push down-automoton with the exception of function calls such as len() or string.Join().

A function call such as len() or string.Join() can be viewed as the definitive boundary where truing complete functionality may occur.

If indeed cluelang can be considered context-free, again proof is needed, then the time and space complexity it theoretically bounded to n^2 and n^2 where n is the length of the input. Relavant paper

Perhaps comprehensions don't fall into the context-free category too, which would throw a wrench in the benefits described in the following, but provided they do and my intuition is correct; the language could be applied variety of different ways very effectively and efficiently.
For example, capturing IOT time series data across a diverse set of devices recording data in variety of different formats but ultimately being able to map data from one format another and ultimately being able to have a deterministic way building a consistent data set to use as input for a function.

This is especially powerful when you consider data expressed as cuelang being captured and processed across a distributed since the values can be evaluated in any order, even evaluated twice, and ultimately yield the same result.

For something something as common as joining strings it would be nice if crossing the Turing-complete function call boundary was necessary to represent them.

[cueckoo]

Original reply by @mpvl in cuelang/cue#113 (comment)

A function call such as len() or string.Join() can be viewed as the definitive boundary where truing complete functionality may occur.

Builtin functions are typically not worse than O(n^2), but certainly not exponential, and will not introduce Turing completeness by themselves.

But, there are references, tuples, and conditionals (via comprehensions), which, together make the language TC if unchecked, although it pretty unpractical in its usage. I haven't done so yet, but my plan is to prohibit primitive recursion. For instance, the test cases include an implementation of Fibonacci. This would then no longer be possible.

Either way, pertaining to this particular request, I suggest labeling it MaybLater and reconsider after query extensions and reduce are implemented.

[cueckoo]

Original reply by @rudolph9 in cuelang/cue#113 (comment)

That sounds reasonable.

[cueckoo]

Original reply by @rudolph9 in cuelang/cue#113 (comment)

But, there are references, tuples, and conditionals (via comprehensions), which, together make the language TC if unchecked, although it pretty unpractical in its usage. I haven't done so yet, but my plan is to prohibit primitive recursion. For instance, the test cases include an implementation of Fibonacci. This would then no longer be possible.

Somewhat relevant to the comment here cuelang/cue#145
And a little testing package I'm refining https://gist.github.com/rudolph9/eccc978e71fd9c32b0ae182ce6854c16

Either way, pertaining to this particular request, I suggest labeling it MaybLater and reconsider after query extensions and reduce are implemented.

@mpvl I don't believe I have permission to add labels.