Adding a "list of T" type

[vpax]

A basic type Zeek lacks is a form of list or queue: an efficient way to maintain a sequence of elements optimized for adding at the end and removing from the beginning (or potentially vice versa). It's possible to create the equivalent using table[count] of T but that's much more heavyweight since it supports random access, and also clunkier because it has no innate notion of "beginning" or "end".

My immediate use case is to allow efficient management of a large number of items that conceptually have individual, fixed-duration timers associated with them. Adding them to the end of a common queue and expiring the front when it's sufficiently old would provide a simple way of managing these.

For now I propose implementing a simple form of FIFO queue that allows appending to the back and removal from the front. Given that the keyword list is already reserved (and queue is not), that's the natural name to use. (Internally this would probably be called TYPE_QUEUE since TYPE_LIST already has a separate internal meaning.)

The usual for loop would iterate over the items, from front to back, and likewise the usual |x| size operator would return the number of items in the list. delete l for a list l would clear it.

There should be syntax for accessing the front and back elements, and for removing the front item and adding a new item to the back. For two of these there's fairly natural syntax - l[0] to access the front item of the list l, and l += e to add the element e to the back of l, ala' vectors.

The other two aren't so obvious to me. One thought - not great - is --l for removing the front item in l and returning its value. Logically, l[|l| - 1] could refer to the last element of l, but that's clunky, and - more than l[0], I think - suggests that random-access would work for lists, which I'm not thinking would be supported. I'm open to other thoughts for this. It'd be great to avoid BiFs, as currently they can only provide dynamic type-checking rather than static. We could add new keywords, as is done for copy, but that should go through a deprecation cycle, and it'd be unfortunate to delay this functionality for an entire major release. Maybe for now we just don't provide a way to access the last element (other than via iteration).

For all of these, referring to items not in the list (such as accessing the front of an empty list) would generate run-time errors, in keeping with Zeek's style for other such operations. Down the line we could also consider adding various attributes to help with managing lists.

[vpax]

Some updates:

I've now implemented this and have it working (including with various frameworks), other than for script optimization. Talking with @timwoj, he was persuasive that we should make the queues accessible from either end. Not hard, implementation-wise, given the internals are a C++ deque anyway ...

... however this then brings up / deepens the question of syntax. We need effective ways to:

• Access the front or back of the queue
• Add to the front or back of the queue
• Pop from the front or back of the queue

For a list q, access is fairly natural as q[0] for the front, q[-1] for the back, and q[i] for an integer value i (which at run-time must be either 0 or -1). These generate run-time errors for empty queues or out-of-range i.

Adding to the back of a queue is naturally expressed as q += v similar to vectors ... however it's not obvious how with existing syntax to best specify add-to-front. We could use q = v + q where under the hood for efficiency this would be recognized as either updating q or creating a new list in the case of q2 = v + q.

Pop-from-front can be expressed as --q (a little weird) ... whereas pop-from-back could be expressed as q-- (weirder, and a grammar change since currently -- can only come before an expression).

Talking with @ynadji, a different possibility is to leverage the existing << and >> shift operators, albeit in a somewhat idiosyncratic fashion:

• Add-to-front: v >> q
• Add-to-back: q << v
• Pop-from-front: v = << q
• Pop-from-back: v = q >>

but this isn't so pretty, either, and would also involve changing an existing operator to have new positioning in the grammar. There may also be some lingering ambiguities when you have list of list of ...s and thus need to cascade << operators (not sure).

One other point: in experimenting with some scripting, it's already become apparent that sometimes it would be handy to iterate over two lists in parallel. You can do this easily by converting them both to vectors using q as vector of T, but for a big list that's going to be a bunch of copying. Another possibility would be to expand for loops to support parallel iteration, such as

for ( v1, v2 in L1, L2 )
 ...

though I think I'd only want that supported for lists, not for other container types (because it'll be rarely used for them, and the implementation will be a headache).

Comments on these appreciated ...

[bbannier]

For a list q, access is fairly natural as q[0] for the front, q[-1] for the back, and q[i] for an integer value i (which at run-time must be either 0 or -1). These generate run-time errors for empty queues or out-of-range i.

This makes a lot of sense, and as a casual user of vector I would expect these to exist for a random-access container like list (not necessarily for a strict queue, but that's not what this is about).

Adding to the back of a queue is naturally expressed as q += v similar to vectors ... however it's not obvious how with existing syntax to best specify add-to-front. We could use q = v + q where under the hood for efficiency this would be recognized as either updating q or creating a new list in the case of q2 = v + q.

Again as a casual user, these would have at first have unclear semantics to me (does += add to front or back?). This could become more confusing if I locally used a list to implement a LIFO or FIFO. More generally, I feel that even if such an operator (or worse: the ones suggested after) would allow to write very concise code, they appear to be more geared towards expert and would be hard to discover (e.g., the docs likely would have just prose documenting them, not a list of API functions; no nice way to implement good completion support for them in https://github.com/bbannier/zeek-language-server). For all these reasons I could see that these custom operators could lead to hard to maintain and understand code.

Separately, I remember that we previously talked about potential confusing type behavior around vector of any's += (if the RHS is a vector, do we insert or the RHS as an element or chain it to the LHS?). In a related PR I argued such an operator for vector ideally should have exactly one semantic (either append or chain), but we have overloaded semantics for historic reasons.¹

I personally would prefer the following interface:

# This provides functions not special statements.

# Add a single element (i.e., no `chain` semantics).
global push_front: function(xs: list of any, x: any);
global push_back: function(xs: list of any, x: any);

# Remove a single element.
global pop_front: function(xs: list of any, x: any);
global pop_back: function(xs: list of any, x: any);

These should be pretty clear to most people familiar with basic data structures and easy to find (e.g., from grepping over shipped script code or searching the docs). The implementation of the bifs could invoke type conversions as needed (e.g., to append a bool to a list of count), or raise an error like we currently do for e.g., vector's += for type mismatches. This would require no parser changes which might require adding less new ad hoc validation there. Having these in bifs would even allow to implement most of this in a plugin (we'd need to unblock declaring list values currently rejected by Zeek's parser, theoretically all the rest could happen in bifs).

---

One other point: in experimenting with some scripting, it's already become apparent that sometimes it would be handy to iterate over two lists in parallel. You can do this easily by converting them both to vectors using q as vector of T, but for a big list that's going to be a bunch of copying. Another possibility would be to expand for loops to support parallel iteration, such as

for ( v1, v2 in L1, L2 )
 ...

To me this looks like a very special flavor of zip which again could be hard to discover, and likely also (not) compose in surprising ways (if I can "join" over two lists, why not over 1024?). The reason we seem to have a need for this might be that Zeek does not have a concept of iterators which lazily yield values (likely too technical for most Zeek users). The reason conversion to vector would help is that we that have special syntax for vector iteration.

Instead of expanding that special syntax to more types, a more general fix could be to add an enumerate-like construct instead which users might be familiar with from other languages. Wrapping a container (random-access or not) in enumerate would successively yield tuples of (index, value) to support vector-like iteration,

local xs = vector(1, 2, 3);       # Any container.
for ( i, x in xs ) {}             # Currently supported.
for ( i, x in enumerate(xs) ) {}  # Equivalent.

enumerate would need runtime support and essentially create a special purpose lazy iterator (which is not directly exposed to users).

With that a zipped iteration could look like this for any random-access container (which list should be):

local xs = vector("A", "B", "C");
local ys = vector("a", "b", "c");

# Not even binding value here for more uniform access in loop body.
for ( i, _ in enumerate(xs) )
	{
		print xs[i], ys[i];
	}

though I think I'd only want that supported for lists, not for other container types (because it'll be rarely used for them, and the implementation will be a headache).

I believe ideally adding language-level constructs should unlock more than a single use case, not only to be useful, but also since this makes it easier for users to develop familiarity with them elsewhere.

Footnotes

1. You filed https://github.com/zeek/zeek/issues/3714 since we do not even consistenly provide the overloaded += semantics of vector for other containers. My personal feeling would be that we do not want this for more types to avoid more potential confusion around containers over any. ↩

[ckreibich]

Looks like there are at least three topics: structuring access/push/pop for the new list type, "Zeekiness" in terms of syntactical solutions vs explicit functions, and how to potentially implement parallel iteration on multiple lists.

I'll pick the middle one first. Zeek has long favored reliance on operators or keywords over explicit functions. This is controversial but I am rather partial to that, for a couple of reasons: once you're used to developing in that style, it feels quicker. Since Zeek doesn't use the "object-oriented" style of many other scripting languages (foo.append(x), foo.insert(x), etc) it means such functions have to stand alone, like your suggested push_front(foo, x), which I think feels ad-hoc since we generally don't use them for any important operations, plus we generally do not want to broaden reliance on any if we can help it.

Second, how to structure these operations for lists. Since we already have add s[foo] and delete s[foo], I was thinking we could expand their use:

# Append an element to a list:
add l[-1, "foo"];
# Prepend an element to a list:
add l[0, "foo"];

# Remove one element from the front:
first = delete l[0]
# Remove one element from the back:
last = delete l[-1];

These have some obvious pros/cons — the add looks a bit unusual, but could serve as a generic insert as well. The delete could double for deleting elements anywhere, possibly including ranges, or occurrence of a given member too (delete l[2:5], delete l["foo"]), plus you already suggested delete l to clear the whole list.

I tinkered with directional concatenation/separation operators since I initially liked the idea of starting from <</>>, but I didn't end up liking any of them. In particular, I couldn't find any style for popping off elements that looked natural. Also, it seems that there are several other potential operations that we might eventually need helper functions for (think reversing, splitting, etc). So I'm wondering whether the "object-oriented" style is something we should consider adding.

Third, parallel iteration. I'm partial here to the enumerate() model, since it's quite powerful to have a numerical index and the element in one go. I have found this useful in Python many times. But I've not spent much time thinking about this use case in Zeek.

[vpax]

I agree that adding functions - while fitting the style of some languages - is pretty far removed from the Zeek style, which emphasizes syntax. And I likewise find that once you get used to it, it feels fluid. Regarding adding object oriented style, that's a big topic, so I'll leave it to another time. For the other two points - syntax and enumerate() - I'll reply to each separately so that if it's apt we can use reply threads to track the particular discussions.

[vpax]

Regarding syntax, I think using add in this way means that add x[-1, "foo"] behaves in two quite different ways: if x is a set, then it's adding an element that corresponds to two indices, -1 and "foo"; but if x is a list, then "foo" is no longer an index but instead a value associated with a pseudo-position -1. That's fairly peculiar. (And the ambiguity for sets with multiple indices means it wouldn't work well as a general insert operator.)

Here's my current thinking, where e denotes a list element and L a list:

• e + L returns the list that has e added to the beginning of L. The interpreter knows to special-case L = e + L so that it efficiently adds e to the beginning of L without creating an intermediary.
• L + e returns the list that has e appended to the end of L. As with vectors, L += e specifies appending without needing to create an intermediary.
• L[0] accesses the beginning of L and L[-1] the end.
• To pop from the beginning ,we use either e = --L or e = delete L[0].
• To pop from the back, we use either e = L-- or e = delete L[-1].

For these last two, I find the -- syntax a bit more fluid, but the delete syntax a bit more intuitive. I think making delete an expression (it's currently instead a statement) is not all that large of a change (and if we went with e = L-- then that also requires some grammar adjustments). So to my thinking, all in all this tips towards using delete for pop operations.

[vpax]

Regarding enumerate(), how would that work for a type like list that isn't random-access?