DEV Community: Ben Bavar

Submit vs Break on Enter on ChatGPT Website

Ben Bavar — Sun, 27 Apr 2025 03:14:49 +0000

When you use, say, Messenger at facebook.com, pressing the Enter key sends your message without fail. But the ChatGPT website is a bit more capricious. Resize your browser window to the wrong dimensions, and you lose the ability to submit your prompts via Enter (unless you simultaneously press Control/Command, which takes some getting used to); instead, you have to click the submit button with the upward pointing arrow on it, which can be a hassle. If you're curious at what window width the submit-on-Enter feature is disabled, here's what I've found.

At first I just eyeballed it, using my MacBook's screenshot tool (Shift-Command-5). The crucial change seemed to occur at a width somewhere between 768 and 770 pixels. But to get a more precise measurement, I opened the Elements panel (Option-Command-C) in Chrome DevTools to inspect the width of the <html> and <body> elements as I resized the window: 768px. At any width less than or equal to this, rather than submitting your query to GPT, the Enter key adds a newline, or line break,¹ to the query. If you shrink the window just a single pixel further to a width of 767px, and proceed to open the left-hand sidebar, which contains the list of your past chats, then the sidebar overlaps the text input field. The current chat goes dark as well. Once that happens, you can't submit prompts at all, let alone by pressing Enter (though that's fine of course). Something tells me these two width-dependent factors are related: the sidebar's encroaching on the chat at small widths, and the loss of the submit-on-Enter option.

If you use ChatGPT in Chrome, the Enter Key For ChatGPT extension works like a charm, up to a point. It enables you to submit any new prompt using Enter, whatever your browser window's dimensions. But should you ever feel the need to edit an old prompt and resend it, your only options are to manually click Send or use the clunky Ctrl/Cmd + Enter key combo. I view this as a limitation—an inconvenience at best, an efficiency killer at worst. Granted, the limitation exists regardless of the browser window's width, with or without the extension; my guess is it's a feature rather than a bug, predicated on the (questionable) assumption that the user expects the Enter key to add a line break, not to trigger submission, while they're editing a message. The only difference the extension makes is that it precludes your adding line breaks with Enter alone, as opposed to Shift + Enter. I don't think there's anything wrong with that. In fact, that's the way it works when you edit messages at facebook.com; what's more, edits are submitted on Enter there. If anything, that's probably the behavior users of instant messaging services have come to expect.

I'm going to see if I can't write a program to overcome the aforementioned limitation. I know that browser extensions often add functionality to websites by injecting code into them, but I don't have experience with injecting my own code into a site whose source code is unavailable to me. It's high time I acquainted myself with the nuts and bolts of that process. I'll keep you updated.

Not to be confused with a paragraph break. ↩

On torch.sum and torch.Tensor.sum

Ben Bavar — Thu, 20 Mar 2025 01:25:05 +0000

I'm interested to know whether, how, and to what extent LLMs (could, if suitably designed) exhibit genuine intelligence, but to figure that out, I need to know how they work. To that end I've been watching "The spelled-out intro to language modeling: building makemore" in Andrej Karpathy's YouTube playlist "Neural Networks: Zero to Hero." Between the timestamps 44:23 and 47:20, Andrej encourages his viewers to sleuth out the answer to the following question (note: I'm paraphrasing and simplifying, abstracting away some of the particulars of Andrej's code). Let tensor be a PyTorch tensor—an instance of the class torch.Tensor, representing $array.\textrm{an }n\textrm{-dimensional array}.$ Suppose tensor has dimensions 27x27. Why can't we assume the return value of tensor.sum(1) is identical to that of tensor.sum(1, keepdim=True), and thus that tensor / tensor.sum(1) and tensor / tensor.sum(1, keepdim=True) both evaluate to the same thing?

After all, according to PyTorch's broadcasting semantics, tensor and tensor.sum(1, keepdim=True) are broadcastable, and tensor and tensor.sum(1) are as well. So tensor can be divided by either tensor.sum(1, keepdim=True) or tensor.sum(1). And as long as these two division operations are legal, it's not immediately obvious how they can yield different results. The variable tensor holds the same value in both division operations. And each of the alternate divisors is a tensor containing the sum of each "row" of tensor in dimension 1. Given all these commonalities, what difference could the value of keepdim make?

I know I've just presupposed a fair amount of knowledge. You may follow the preceding paragraph better if you watch Andrej's video first. We'll also unpack what I just said in a future post. But before I even attempt to answer Andrej's question, I have some catching up to do, learning how to read both Python code and the documentation for Python libraries like PyTorch.

Let's take a look at the documentation for torch.sum:

I'm not accustomed to Python, only C++, JavaScript, and to an extent Java. So when I tried to make sense of the relation between torch.sum, whose signature is in the image, and tensor.sum, my thought process went roughly as follows.

With both tensor and an integer n at our disposal, we can invoke a function sum in either of two ways: torch.sum(tensor, n) or tensor.sum(n). Both invocations do exactly the same thing, so far as I can tell. So either sum is the same function in both cases, or two functions with the same name have extremely similar implementations. I'll go with the former hypothesis, because it's simpler. Thus, torch and tensor share a function named sum accessible via the dot operator, .. Most likely, then, torch.Tensor and its instances, including tensor, inherit sum from torch. Now, methods can only be inherited from types, not from individual objects. So torch must be a type. It's beyond me what kind of type it is. I have heard torch described as a module. That constitutes some reason to doubt it's a class or interface. But for all I know modules are, or can be, classes or interfaces. That's how unfamiliar I am with Python lingo like "module." At all events it would seem that sum is a static method of torch, since you can call it on torch itself, not just an instance of the type torch. And since this method has a body in torch, I suspect torch is not an interface.

Again, that last paragraph is just what I thought initially, when I was a bit less Python literate. Unfortunately, my reasoning there led me astray. torch.sum(input,dim,keepdim=False,*,dtype=None) is not a static method's signature. In fact, it's not a method signature at all, since sum is not a method of torch. Why it's not a method of torch takes a little explaining.

By definition, a function $f$ is a method of $x$ if and only if (i) $f$ is an attribute belonging to some type $t,$ and (ii) $x$ is or instantiates $t .$ As it happens, the function sum is an attribute of a type, namely torch.Tensor. So, by our definition, sum is a method of torch.Tensor and of any instance thereof. But it's not a method of torch. For sum to be a method of torch, torch would have to either be or instantiate a type of which sum is an attribute. Being a module—which, much like a Java package, is a namespace—torch is not a type, much less the kind of type that has attributes (i.e., a class/struct or interface). So the only way sum can be a method of torch is if torch instantiates (is an instance of) a type of which sum is an attribute. Now, torch does instantiate types, namely the superclasses of the types.ModuleType class: object and ModuleType itself. But sum is not an attribute of ModuleType or object.

Therefore, while sum is an attribute of torch and a method of torch.Tensor and its instances, it's not a method of torch, let alone specifically a static method of torch.

Modules such as torch, it turns out, are objects in Python, seeing as they are instances of the ModuleType class. Virtually everything in Python is an object, including classes and instances of types like int and bool that you might expect to be primitive, as are the corresponding types in other languages. That torch is an object explains how it can have attributes despite being a module rather than a class or interface. (Interfaces technically don't exist at all in Python. Had I known this, I could've immediately and decisively ruled out that torch is an interface, rather than tentatively ruling that out based on torch's having a callable function.)

How then do torch and torch.Tensor have the attribute sum in common? It can't be that Tensor inherits the function sum from torch. Nor can torch and Tensor inherit sum from some type other than Tensor. This is because only types, not modules, can stand in a relation of inheritance.

I take it what happens is that Tensor derives sum from torch, but through a different mechanism than inheritance. The function sum is originally defined in the module torch, and subsequently sum is associated with the class Tensor. There are two places sum can be so associated with Tensor: inside and outside the definition of Tensor. Here's how it would look inside the class definition:

def sum(input, dim, keepdim=False, *, dtype=None):
    # Insert body

class Tensor:
    def sum(self, dim, keepdim=False, *, dtype=None):
        return sum(self, dim, keepdim, dtype)
    # Insert rest of class definition

And outside the class definition:

def sum(input, dim, keepdim=False, *, dtype=None):
    # Insert body

class Tensor:
    # Insert class definition

Tensor.sum = sum

(Note: we're to imagine one of the above code snippets is in some file in the torch module/package directory.) Either way, this is not true inheritance. It's reusing the torch module's implementation of sum to implement Tensor.sum, either via invocation of torch.sum in the definition of Tensor.sum, or via monkey patching (assigning torch.sum to Tensor.sum, after Tensor is defined). We shall see in due course which of these two approaches PyTorch's developers must've taken, assuming there's no third approach I've overlooked.

Let's glance once more at the function signature from the docs: torch.sum(input,dim,keepdim=False,*,dtype=None). There are four parameters, which are input, dim, keepdim, and dtype, in that order. (* is not a parameter but merely an indicator that the parameters after it must receive keyword arguments: arguments of the form parameter_name=value.) The attribute sum of tensor should have these four parameters as well, since Tensor.sum and torch.sum are essentially the same function. Granted, there's a good chance tensor.sum comes by its first parameter in a different way than torch.sum does. For torch.sum is defined at the module level, whereas tensor.sum is plausibly defined at the class level (as illustrated in the first code block above). Suppose that's how tensor.sum is defined. Suppose further that it's a non-static method. Then its first parameter is the class instance on which the function is called. That's just how non-static methods work in Python. So the first argument comes from the left of the dot operator, not the beginning of the list of arguments enclosed in parentheses. Even so, the first parameter is intended to receive a tensor, as is the first parameter of torch.sum. Furthermore, I think we can safely assume the remaining parameters are indistinguishable from the last three parameters of torch.sum.

Now, which parameters receive which arguments in the function calls tensor.sum(1) and tensor.sum(1, keepdim=True)? Recall that we are countenancing two mutually exclusive scenarios: (a) that, as a result of monkey patching, tensor.sum and torch.sum have the very same parameters, and (b) that, due to tensor.sum's being defined in a class, tensor.sum and torch.sum differ with respect to the source of the first argument. We can rule out (a) on the following grounds. The first argument enclosed in parentheses is 1 in both tensor.sum(1) and tensor.sum(1, keepdim=True). So given (a) and the fact that 1 is passed as a positional argument, 1 is the first argument, period. Rather than being passed for dim, it's passed for input. But like input and unlike keepdim and dtype, dim lacks a default value. So dim does not get assigned a value at all. Surely, if that were the case, tensor.sum(1) and tensor.sum(1, keepdim=True) would cause at least one TypeError. The first error Python would most likely raise is something like:

TypeError: sum(): argument 'input' (position 1) must be Tensor, not int

But failing that, Python would undoubtedly raise this error:

TypeError: sum() missing 1 required positional argument: "dim"

Since neither of these two errors is in fact raised, we've shown that (a) is not the case. Unless I have overlooked some third scenario, (c), that leaves only one possibility as to the relation between the parameters of tensor.sum and those of torch.sum: (b). That is, the first argument of tensor.sum, which function is defined in a class, must be whatever's to the left of the dot operator (unlike the first argument of torch.sum, which is the first item in the list enclosed in parentheses in the function call). That's tensor in the invocations tensor.sum(1) and tensor.sum(1, keepdim=True).

I may be getting ahead of myself. There's one complication I haven't yet discussed, which might block our inference that (b) is the case. That complication is, torch.sum is overloaded, so it has an alternative parameter list:

Only one of this overload's parameters, namely input, lacks a default value. So one need only pass one argument explicitly to avoid a missing argument error.

Let's stipulate that suggestion (a) is true, and thus Tensor has been monkey patched to have an attribute identical to torch.sum. It follows that tensor.sum has the very same overloads torch.sum has. So even if only one argument were passed between the parens, there would be no error, as long as that argument were of the right type. But therein lies the rub. The first argument the overload torch.sum(input, *, dtype=None) expects is a tensor. So tensor.sum(1) still raises one of the errors mentioned before:

TypeError: sum(): argument 'input' (position 1) must be Tensor, not int

But, contrary to my previous hasty prediction, the missing argument error is not raised. Moreover, Python interprets tensor.sum(1, keepdim=True) as an invocation of the overload with the larger parameter list, since only that overload has a parameter named keepdim. So, when tensor.sum(1, keepdim=True) is executed, we should expect Python to raise both of the errors I predicted earlier.

Again, this is all on the supposition that (a) is true. Since these error messages are not actually raised, we may infer that (a) is false. Thus, our original conclusion stands: (b) is true. It follows that tensor is passed for input in tensor.sum(1) and tensor.sum(1, keepdim=True).

At this point we can straightforwardly ascertain the values dim, keepdim, and dtype receive. If we take the positional/non-keyword arguments in the invocation tensor.sum(1), and pass them to torch.sum as keyword arguments, we get torch.sum(input=tensor, dim=1, keepdim=False, dtype=None). These two invocations are equivalent. Also equivalent (to each other) are the invocations

tensor.sum(1, keepdim=True)

and

torch.sum(input=tensor, dim=1, keepdim=True, dtype=None).

Thus, given how Tensor.sum is defined in terms of torch.sum,

tensor.sum(1)

and

tensor.sum(dim=1, keepdim=False, dtype=None)

are equivalent, and so are

tensor.sum(1, keepdim=True)

and

tensor.sum(dim=1, keepdim=True, dtype=None).

In my next post in this series, I promise to do what I had set out to do in the first place: answer Andrej Karpathy's question.

Turning Sequences of Numbers into Arithmetic Progressions

Ben Bavar — Tue, 18 Feb 2025 02:19:52 +0000

I've been thinking quite a bit about arithmetic progressions since I came across the problem "The Arithmetic Progression Detective" on Codewars. An arithmetic progression is a sequence of numbers such that, for any consecutive numbers $x_i$ and $x_{i + 1}$ in the sequence, $x_{i + 1} - x_i$ is always the same value, $d,$ known as the common difference. One example of an arithmetic progression is the sequence $5, 10, 15, 20, 25, 30,$ whose common difference $it!—5.\textrm{is---you guessed it!---}5.$

Let $s_n$ be an arbitrary sequence of integers, or terms. Let $d_n$ be the common difference of the arithmetic progression from which $s_n$ deviates by no more than one value—the incorrect value—if such a progression exists. I'm going to call $s_n$ fixable if and only if such a progression exists. If $s_n$ cannot be turned into an arithmetic progression through the replacement of just one number in $s_n,$ then $s_n$ is not fixable. Bearing this in mind, what limits can we identify to the range of fixable sequences?

Let $s_1$ be the sequence $1, 2, 4, 5.$ Let $s_2$ be the sequence $2, 5, 6, 8.$ $s_1$ is not a fixable sequence. But $s_2$ clearly is, since $s_2$ deviates by just one number from the arithmetic progression $2, 4, 6, 8.$

$s_1$ and $s_2$ have a great deal in common. Each includes four numbers. Each superficially resembles an arithmetic progression. Each contains exactly one apparent deviation, in one sense or another: exactly one step whose size differs from the others' in the case of $s_1,$ and exactly one incorrect value in the case of $s_2.$ So what difference between these two sequences makes $s_2$ fixable and $s_1$ not?

One of the first things I noticed is, unlike $s_2,$ $s_1$ consists of steps all but one of which are the same size. To see this, note the following. The step from $2$ to $4$ in $s_1$ is of size $2.$ The remaining steps in $s_1$ are of size $1.$ By contrast, in $s_2,$ each step's a different size. Steps one through three, respectively, are of sizes $3, 1,$ and $2.$ So, the only step of size $d_2$ in $s_2$ is the third and final step, from $6$ to $8.$

This goes to show you should not take for granted that $s_n$ contains more steps of size $d_n$ than of any other size, even assuming that there are four or more values in $s_n,$ and that only one is incorrect.

But this difference between $s_1$ and $s_2$ does not fully explain their differing with respect to fixability. Some sequences are like $s_1$ in that they consist of steps all but one of which are the same size, but they are still fixable. One such sequence is $1, 4, 6, 8.$ All you have to do to fix this is replace $1$ with $2.$ Really any sequence is fixable whose first or last term is the sole incorrect value. For our purposes the incorrect value in $s_n$ is defined as the one and only term whose replacement can single-handedly turn $s_n$ into an arithmetic progression.

What sets $s_1$ apart from a sequence whose first or final term is the only wrong one? Why is $s_1$ not fixable like that kind of sequence? An obvious response is that $s_1$ doesn't contain exactly one incorrect value. But I'm not satisfied with that answer. It's not wrong, but it's not illuminating either. It raises questions like: "How many incorrect values does $s_1$ contain? How exactly do we count them?" We need to explicate what makes a value incorrect and how we can tell a value meets that condition. Maybe the following is a better answer.

In $s_1$ we have a step of size $1,$ followed by one of size $2,$ followed by one of size $1.$ If we could turn that second step into a step of size $1,$ we'd be able to create an arithmetic progression. But if we try to do that by moving the second step's beginning closer to its end, we widen the first step; the first step ends where the second begins. If on the other hand we move the second step's end closer to its beginning, we widen the third step; the third step begins where the second ends.

So there are ways to decrease the size of the second step from $2$ to $1.$ But they all end up shortening or lengthening one of the other steps, such that it is no longer of size $1.$ (Well, more precisely, all our options have this result if we limit ourselves to replacing just one integer in $s_1$ with just one integer.) So we don't end up with an arithmetic progression.

That's where $1, 2, 4, 5$ differs from $1, 4, 6, 8.$ The latter sequence consists of a step of size $3,$ followed by two steps of size $2.$ Crucially, that first step has an endpoint that no other step has. That is, the first number in the sequence is where the first step begins, and no other step begins or ends with that term. So you can replace that term with any number you want, including a number $x$ such that $4 - x = 2.$ The substitution will affect no step but the first, which is the only one you want to change.

Here is a more formal proof that you cannot turn $1, 2, 4, 5$ into an arithmetic progression by replacing just one term with just one integer. We can split into two categories the integers in $s_1$ there are to replace: the numbers on the ends and those in between.

Suppose you replace exactly one of the two numbers on the ends $5).(\textrm{i.e., } 1 \textrm{ or } 5).$ Replacing $1$ changes only the size or direction of the first step, whereas replacing $5$ changes only the size or direction of the final step. So after you replace $1,$ the sizes of the second and third steps are still, respectively, $2$ and $1.$ And after you replace $5,$ the sizes of the first and second steps are still, respectively, $1$ and $2.$ But all the steps in the modified sequence must be the same size, if the sequence is to count as an arithmetic progression. So the modified sequence cannot be an arithmetic progression. In other words, you cannot turn $s_1$ into an arithmetic progression by replacing just $1,$ or just $5,$ with just one integer.

Suppose that instead you replace exactly one number strictly between those on the ends $4).(\textrm{i.e., } 2 \textrm{ or } 4).$ Let $x$ and $y$ be arbitrary integers such that $\not= 2$ and $\not= 4.$ Let $s_{1_x}$ be the sequence resulting from replacing $2$ with $x .$ Let $s_{1_y}$ be the sequence resulting from replacing $4$ with $y .$

Recall that $s_1$ is the sequence $1, 2, 4, 5.$ Consequently, $s_{1_x}$ is the sequence $1, x, 4, 5,$ and $s_{1_y}$ is the sequence $1, 2, y, 5.$ The first two steps in $s_{1_x}$ differ from the first two in $s_1;$ no other step in $s_{1_x}$ differs from its counterpart in $s_1.$ The final two steps in $s_{1_y}$ differ from the final two in $s_1;$ no other step in $s_{1_y}$ differs from its counterpart in $s_1.$

Let $b = x - 2, c = y - 4.$ Then $1 + b$ is the signed value representing the size and direction (on the number line) of the step from $1$ to $x$ in $s_{1_x} ,$ and $2 - b$ is that representing the size and direction of the step from $x$ to $4$ in $s_{1_x} .$ Furthermore, $2 + c$ is the signed value representing the size and direction (on the number line) of the step from $2$ to $y$ in $s_{1_y},$ and $1 - c$ is that representing the size and direction of the step from $y$ to $5$ in $s_{1_y} .$

$s_{1_x}$ or $s_{1_y}$ is an arithmetic progression only if all steps within it are of the same size and direction. Thus, $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c .$

But it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c .$

I shall show that neither of these is true by giving a proof by contradiction of the falsity of each.

Here is a proof by contradiction that

$1 + b = 2 - b = 1$

is false.

Assume the following, arguendo:

$1 + b = 2 - b = 1$

Then:

$1 + b = 2 - b$

$1 + 2 b = 2$ $sides)\tiny (\textrm{added } b \textrm{ to both sides})$

$2 b = 1$ $sides)\tiny (\textrm{subtracted } 1 \textrm{ from both sides})$

$\frac{1}{2}$ $2)\tiny (\textrm{divided both sides by } 2)$

$\frac{1}{2} = \frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But our initial assumption entails

$1 = 2 - b .$

So:

$\frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But obviously:

$\not= \frac{3}{2}$

Therefore,

$\frac{3}{2} \land 1 \not= \frac{3}{2}.$

Contradiction! We derived this from our initial assumption. A contradiction cannot be true, so neither can anything that entails a contradiction. Thus, our initial assumption must be false. Since this conclusion follows given an arbitrary integer $x,$ the proof just given demonstrates that $1 + b = 2 - b = 1$ is false regardless of what integer you substitute for $2$ in $s_{1}.$

Now let us prove by contradiction that

$1 = 2 + c = 1 - c$

is false.

Assume the following, arguendo:

$1 = 2 + c = 1 - c$

Then:

$2 + c = 1 - c$

$2 + 2 c = 1$ $sides)\tiny (\textrm{added } c \textrm{ to both sides})$

$2 c = - 1$ $sides)\tiny (\textrm{subtracted } 2 \textrm{ from both sides})$

$-\frac{1}{2}$ $2)\tiny (\textrm{divided both sides by } 2)$

$\frac{1}{2} = \frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But our initial assumption entails:

$1 = 2 + c$

So:

$\frac{3}{2}$

$\frac{3}{2}$ $of=)\tiny (\textrm{transitivity of} =)$

But obviously:

$\not= \frac{3}{2}$

Therefore,

$\frac{3}{2} \land 1 \not= \frac{3}{2}.$

Another contradiction! Since this conclusion follows given an arbitrary integer $y,$ the proof just given demonstrates that $1 = 2 + c = 1 - c$ is false regardless of what integer you substitute for $4$ in $s_{1}.$

Recall that $s_{1_x}$ is an arithmetic progression only if

$1 + b = 2 - b = 1.$

And $s_{1_y}$ is an arithmetic progression only if

$1 = 2 + c = 1 - c .$

But as the foregoing proofs by contradiction show, it is true neither that

$1 + b = 2 - b = 1$

nor that

$1 = 2 + c = 1 - c .$

Therefore, neither $s_{1_x}$ nor $s_{1_y}$ is an arithmetic progression. But $s_{1_x}$ is the result of replacing $2$ in $s_1$ with an arbitrary integer, and $s_{1_y}$ that of replacing $4$ in $s_1$ with an arbitrary integer. So, no matter what integer you substitute for $2$ or $4$ in $s_1,$ you don't thereby get an arithmetic progression.

But if you can't get an arithmetic progression by thus replacing just $2$ or $4,$ and you can't do so by thus replacing just $1$ or $5,$ then you can't do so by thus replacing just $1, 2, 4,$ or $5.$ But that means you can't do so by replacing just one integer with just one integer, since $1, 2, 4,$ and $5$ are all the integers there are to replace in $s_1.$

Therefore, you cannot turn $s_1$ into an arithmetic progression by replacing just one term with just one integer.

From the above proof, what lesson should we draw concerning sequences other than $s_1?$ This is my takeaway.

Let $s_3$ be some sequence of integers $x1,x2,…,xℓ−1,xℓx_1, x_2, \dots , x_{\ell-1}, x_\ell$ of length $ℓ≥4.\ell \geq 4.$ (To be clear, we know $s_3$ includes the four values $x1,x2,xℓ−1,x_1, x_2, x_{\ell-1},$ and $xℓ.x_\ell.$ We don't know if $s_3$ includes other values.) Let $\leq i \leq \ell.$ Let $x_i$ be the $ithi^{\textrm{th}}$ number in $s_3.$ Let $d_i = x_{i + 1} - x_i.$ Let step $i$ be the step in $s_3$ from $x_i$ to $x_{i + 1}.$ Note that replacing $x_i$ with a different integer changes only step $i - 1$ and step $i .$

Let $s_{3_z}$ be the sequence resulting from replacing $x_i$ with an arbitrary integer $z .$ Let $x_{i_z}$ be the $ithi^{\textrm{th}}$ number in $s_{3_z}.$ Let $d_{i_z} = x_{i + 1_z} - x_{i_z}.$ The subscript of $x_{i + 1_z}$ should be read as $i + 1)_z,$ not as the expression $i + 1_z$ with which $1_z + i$ is interchangeable.

Replacing exactly one integer $x_i$ in $s_3$ can only turn $s_3$ into an arithmetic progression on the following condition:

$∃y∃c(y−xi=c∧d1=⋯=di−1+c=di−c=⋯=dℓ−1).\text{\small F}\text{\tiny IXABLE}\text{\small : } \small \exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

Here is an informal, rough English translation of the logical notation above. There are integers $y$ and $c$ such that

(I) $c$ is the difference between $y$ and $x_i,$ and

(II) lengthening step $i - 1$ (if there is one), and shortening step $i$ (if there is one), by $c$ units ensures all steps have the same size and direction.

Allow me, now, to prove that $s_{3_z}$ is not an arithmetic progression if $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

Assume the following, arguendo:

$s_{3_z}$ is an arithmetic progression, and $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

You know what we have to do. Derive a contradiction!

By the definitions of $x_i$ and $s_{3_z},$ $x_i$ is the $ithi^{\textrm{th}}$ number in $s_3,$ and $s_{3_z}$ is the sequence resulting from substituting $z$ for $x_i$ in $s_3.$ Thus, the $ithi^{\textrm{th}}$ number in $s_{3_z}$ is $z$ rather than $x_i.$ By definition, $x_{i_z}$ is the $ithi^{\textrm{th}}$ number in $s_{3_z}.$ So, given that $x_{i_z}$ and $z$ are each the $ithi^{\textrm{th}}$ number in $s_{3_z},$ it must be that $x_{i_z} = z.$

Since $x_{i_z}$ is the only number in $s_{3_z}$ that differs from the number at the corresponding position in $s_3,$

$∀j≠i(xj=xjz).\forall j \neq i (x_j = x_{j_z}).$

So, $x_{i + 1_z} = x_{i + 1}.$

So, by the definition of $d_{i_z},$

$d_{i_z} = x_{i + 1} - z.$

Solving for $x_{i + 1},$

$x_{i + 1} = d_{i_z} + z.$

Then, from the definition of $d_{i_z},$ we get

$d_{i - 1_z} = x_{i_z} - x_{i - 1_z}.$

So, seeing as $x_{i_z} = z$ and $x_{i - 1_z} = x_{i - 1},$ we may conclude that

$d_{i - 1_z} = z - x_{i - 1}.$

Then we solve for $x_{i - 1}$ as follows:

$x_{i - 1} = z - d_{i - 1_z}.$

Now let's take our solutions for $x_{i + 1}$ and $x_{i - 1},$ and combine them with the following information. The definition of $d_i$ implies that $x_{i + 1} = d_i + x_i$ and $x_{i - 1} = x_i - d_{i - 1}.$ Taking all these facts into account, we see both that

$d_i + x_i = x_{i + 1} = d_{i_z} + z$

and that

$x_i - d_{i - 1} = x_{i - 1} = z - d_{i - 1_z}.$

Of course, that means $d_i + x_i = d_{i_z} + z$ and $x_i - d_{i - 1} = z - d_{i - 1_z}.$ Solving both these equations for $z,$ we get

$z = x_i + d_i - d_{i_z}$

as well as

$z = x_i - d_{i - 1} - d_{i - 1_z}.$

From those two equations, we derive

$x_i + d_i - d_{i_z} = x_i - d_{i - 1} - d_{i - 1_z},$

which we simplify to

$d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1}.$

From our assumption arguendo that $s_{3_z}$ is an arithmetic progression, it follows that $d_{i - 1_z} = d_{i_z}.$ Given the conjunction of this equation with $d_i - d_{i_z} = d_{i - 1_z} - d_{i - 1},$ it is provable that

$diz=di+di−12,d_{i_z} = \frac{d_i + d_{i - 1}}{2},$

which can be rewritten as

$d_{i - 1} = 2d_{i_z} - d_i.$

The fact that $s_{3_z}$ is an arithmetic progression tells us the following as well:

$d1z=d2z=⋯=di−1z=diz=di+1z=⋯=dℓ−2z=dℓ−1z.d_{1_z} = d_{2_z} = \dots = d_{i - 1_z} = d_{i_z} = d_{i + 1_z} = \dots = d_{\ell - 2_z} = d_{\ell - 1_z} .$

And considering that $s_{3_z}$ is indiscernible from $s_3$ apart from $z’sz\textrm{'s}$ having been substituted for $x_i,$ this must be true:

$∀j((j≠i−1∧j≠i)→dj=djz).\forall j ((j \neq i - 1 \land j \neq i) \to d_j = d_{j_z}).$

This means that, for all numbers $j$ equal to neither $i - 1$ nor $i,$ we can replace $d_{j_z}$ with $d_j$ in the chain of equations presented immediately prior to the universally quantified generalization:

$d1=d2=⋯=di−2=di+1=⋯=dℓ−2=dℓ−1.d_1 = d_2 = \dots = d_{i - 2} = d_{i + 1} = \dots = d_{\ell - 2} = d_{\ell - 1} .$

Time for another proof by contradiction! We want to establish the truth of

$d_{i - 1} + (z - x_i) = d_i - (z - x_i),$

so we assume the negation of that for the sake of argument:

$di−1+(z−xi)≠di−(z−xi).d_{i - 1} + (z - x_i) \neq d_i - (z - x_i).$

From this we derive

$di−1≠2diz−di,d_{i - 1} \neq 2d_{i_z} - d_i,$

which contradicts our previous conclusion that

$d_{i - 1} = 2d_{i_z} - d_i.$

Therefore,

$d_{i - 1} + (z - x_i) = d_i - (z - x_i),$

which completes our subproof!

It goes without saying that both the integer $z$ and the difference $z - x_i$ exist. So, we have found a $y$ and a $c$ such that

$x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}.$

If you're curious, $z$ is our $y,$ and $z - x_i$ is our $c .$ That is, we can go from

$z−xi=z−xi∧d1=⋯=di−1+(z−xi)=di−(z−xi)=⋯=dℓ−1\small z - x_i = z - x_i \land d_1 = \dots = d_{i - 1} + (z - x_i) = d_i - (z - x_i) = \dots = d_{\ell - 1}$

$∃y∃c(y−xi=c∧d1=⋯=di−1+c=di−c=⋯=dℓ−1).\exists y \exists c (y - x_i = c \land d_1 = \dots = d_{i - 1} + c = d_i - c = \dots = d_{\ell - 1}).$

And then we've established $FIXABLE.\text{\small F}\text{\tiny IXABLE}.$ So we have finally derived a contradiction from our initial assumptions. Recall what those assumptions were: $s_{3_z}$ is an arithmetic progression, and $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$ From these we ultimately concluded $FIXABLE,\text{\small F}\text{\tiny IXABLE},$ which contradicts the second of our two initial assumptions.

So, either $s_{3_z}$ is not an arithmetic progression, or $FIXABLE.\text{\small F}\text{\tiny IXABLE}.$ But this disjunction is just another way of saying $s_{3_z}$ is not an arithmetic progression if $¬FIXABLE.\neg\text{\small F}\text{\tiny IXABLE}.$

And that's what we set out to prove!

Are Generics Really That Generic?

Ben Bavar — Mon, 10 Feb 2025 10:07:50 +0000

One thing you'll notice about the Collection interface is its use of generics. In the interface definition, the data type of Collection objects' elements is not specified. Their type is represented as E, a mere placeholder or type parameter. Collection<E> is thus what we call a generic type. Collection<String> and Collection<Collection<E>> are examples of specific types—though, in the latter case, still a generic type—instantiating Collection<E>. These instances of the type Collection<E> are parameterized types. The types String and Collection<E> substituted for E in Collection<E> are type arguments.

Collection's being a generic type allows Java developers considerable latitude in choosing element types when implementing or instantiating collection classes. I don't know about you, but I'm more familiar with generics (templates) in C++ than in Java. So when I saw the type parameter E in the Java docs, I was tempted to read it as a placeholder for nearly any type, even a primitive type. But that can't be right, given what we know about collections and their elements in Java. Think about it. If that were true, what would that mean?

You could then create a Collection object with elements of a primitive type like int. For example, you could create a Set object on the model of the mathematical set of integers ${1,2,3}.\lbrace 1, 2, 3 \rbrace .$ And you wouldn't have to use the wrapper class Integer to accomplish this. You could just do Set<int> set = new HashSet<>() {{ add(1); add(2); add(3); }};.

As it happens, this initialization is perfectly syntactically acceptable. But it causes a type error. That comes as no surprise, since only non-primitive values are allowed in collections. So, seeing as E represents the type of elements in a collection, it can't be a primitive type.

This raises a question about how generic generics really are. Perhaps no type parameter is so generic as to allow arguments of both reference types and primitive types. Or perhaps some type parameters, like E in Collection<E>, are less generic than others. But what could account for type parameters' having different levels of generality?

Only one mechanism exists in Java for controlling type parameters' generality. That mechanism is to use the extends keyword to specify a type parameter's upper bound: roughly, the most general type argument allowed. More precisely, a type parameter's upper bound is the type of which any type argument must be a subtype, lest a compilation error result.

But no bound is specified in Collection. It's just public interface Collection<E>, not public interface Collection<E extends SomeSupertype>. (Granted, the definition does say Collection<E> extends Iterable<E>. But that use of extends just makes Collection a subinterface of Iterable. It doesn't establish an upper bound of E.)

So we know there's no explicit bound requiring E to be a reference type. Could there be an implicit one? As a matter of fact, there could. And there is, in a sense.

Consider a class or interface SomeType<T>, such that extends does not occur between the angle brackets enclosing the type parameter. When the definition of SomeType is compiled, Object replaces T. This happens by default, since no bound for T is specified in the definition of SomeType. Due to this default behavior, T is bounded in that it must be a subtype of Object. As such, it cannot be a primitive type, nor can it be a supertype of both reference types and primitive types. So, if we want, we can call Object the implicit upper bound of T. Alternatively, we can say T has no upper bound. T can be any type of object, after all!

Now we can see why E does not allow primitive type arguments in Collection<E>. Primitive types are not subtypes of Object. In fact, no primitive type is a subtype of a more fundamental type—hence the descriptor "primitive." But any type parameter T must be a subtype of Object. For there are only two possibilities. One is that Object is the (implicit) upper bound of T. The other is that T extends SomeSupertype.

Suppose Object is the upper bound of T. Then, by the definition of "upper bound," T must be a subtype of Object.

Suppose instead that T extends SomeSupertype. Even though T is technically a supertype of itself, SomeSupertype cannot be T. The type a type parameter extends must be distinct from the type parameter. So T cannot be a primitive type; it's a subtype of a distinct type. Moreover, all (non-null) non-primitive types are subtypes of Object. So T must be a subtype of Object.

So, no matter what, T has to be a subtype of Object. That means any type parameter, including E, must be a subtype of Object—which entails E is a reference type rather than a primitive type.

What have we learned? Type parameters have varying generalities depending on their bounds. But there's a limit to how general these "generics" get. They can only allow type arguments which are subtypes of Object. Thus, no type parameter is generic enough to allow primitive type arguments in addition to reference type arguments.

Collections, Demystified

Ben Bavar — Sun, 09 Feb 2025 04:45:38 +0000

I am writing this with a view to making headway in wrapping my head around Oracle's Java docs. Simply reading these dry documents is for me a daunting task, to say nothing of comprehending them! But I have found that the information becomes more interesting, and the process of reading more tolerable, when I put in the effort to conceptualize the info in a way that makes sense to me—which makes sense, since info can hardly interest you if you don't understand it.

Fortunately I have some idea as to how I can break this task down into subtasks. At present I am primarily interested in the core Java interfaces. These are the interfaces in the core Java SE APIs, defined in Oracle's API specification for Java SE.

Let us begin with what Oracle identifies as "[t]he root interface in the collection hierarchy": the Collection interface. There's a lot to learn about Collection. In this post we'll focus on what collections and objects of type Collection are.

Collections

According to Oracle, collections are groups of objects called elements. Some collections can contain duplicates of their elements. We call these bags. Other collections cannot. Call them boxes.

(Edit: I forgot Oracle technically says a collection "represents" a group of objects, not that a collection is one. I'll have to think about how that affects what I say below.)

Boxes are like sets in set theory. Just as, in set theory, you can't have more than one of a single object in a set, you can't put more than one of the same object in a box.

Every once in a while you might see multiple instances of the same numeral in notation representing a set, such as ${1,2,2,3}.\lbrace 1, 2, 2, 3 \rbrace .$ But this is just a notational variant of ${1,2,3}.\lbrace 1, 2, 3 \rbrace .$ So is ${1,2,3,2},\lbrace 1, 2, 3, 2 \rbrace ,$ or ${1,3,2}.\lbrace 1, 3, 2 \rbrace .$ These are all the same set. Why? Because they have the same elements. There are not actually two $2s2\textrm{s}$ in the set ${1,2,2,3}.\lbrace 1, 2, 2, 3 \rbrace .$ There's only one, because the number $2$ is just a single object. Only one such number exists. No matter how many times you write the numeral $‘2’,\lq 2 \text{\textquoteright},$ it always stands for the same number.

Here's a way to see my point. Let $x$ be $2.$ Then ${1,2,2,3}\lbrace 1, 2, 2, 3 \rbrace$ is ${1,x,x,3}.\lbrace 1, x, x, 3 \rbrace.$ But obviously $‘x’\lq x \text{\textquoteright}$ denotes the same thing wherever it appears. That is, $x = x .$ So ${1,x,x,3}\lbrace 1, x, x, 3 \rbrace$ can only have three things in it: $1, x,$ and $3.$ So by substituting $‘2’\lq 2 \text{\textquoteright}$ for $‘x’,\lq x \text{\textquoteright},$ we conclude that ${1,2,2,3}\lbrace 1, 2, 2, 3 \rbrace$ can only have three things in it: $1, 2,$ and $3.$

All this to say, sets never have duplicate elements. Boxes are the same way. Consider the paradigmatic box: an object of type Set (a subinterface of Collection). (From here on out, unless I indicate otherwise, "set" means a Set object.) For any two elements e1 and e2 of a set, !e1.equals(e2). It follows, without loss of generality, that e1 and e2 are not duplicates.

You might doubt these things are true of all sets. Some sets have elements, the thought might go, that lack an equals method. If e1 were one of those elements, the method call e1.equals(e2) would be illegal. So it could not return false as needed for the negation of its return value to be true.

But you would be wrong! Any element of a collection is an object, i.e., an instance of a class. And all classes are subclasses of Object. So they all inherit the equals method from Object. For this reason, no matter the type of e1, e1 has an equals method. How can we be sure though that e2 is a valid argument to pass? We can because it's an instance of Object, as is e1, and the lone parameter of Object's equals method is of type Object.

Null Elements

So it looks like no set can contain multiple copies of an element. But hang on... Can't you put null in a collection? That's not an object. It's a value indicating the absence of an object reference. I'm the one who's wrong then! Not just any element of any collection is an object.

So, what if e1 happens to be null? Then e1 is not an instance of any class, and does not inherit an equals method from Object. In that case it's not strictly true that !e1.equals(e2). But there still are no duplicates of null in the set, according to the documentation for Set. Also, if e1 is null, it is true that e1 and e2 are not such that e1.equals(e2). Why? For those elements to be such that e1.equals(e2), that method call would have to return true. But the invocation is not allowed, so it cannot return true. So the generalization in the documentation still holds true. That is, every set contains no pair of elements e1 and e2 such that e1.equals(e2).

Now we see why Oracle chose to deny any element pair is such that e1.equals(e2), instead of affirming, like I did, that all pairs are such that !e1.equals(e2). Wording matters. But in my defense, what I said was such truthlike, much truthy. Not all pairs of elements make the negation true, but all pairs of objects in any collection do.

There being collections with null elements doesn't square with defining "collections" as groups of objects and "elements" as objects in a collection. Some collections have only null elements. No null element is an object, though each is in a collection. So, what are collections and elements? To answer this question, we have to consider two things.

First, what is it that all elements of Collection objects have in common, be those elements objects or not? If there is something they all have in common, we may keep calling all Collection objects collections, if we please. If that's what we want, we just have to revise our definition of "collection."

Second, is it true that all Collection objects are collections? Perhaps objects of that type only truly qualify as collections when they contain objects. Then, if a Collection object has only null elements, it's not a collection (group of objects). Assuming that's right, there is no need to revise our definition of "collection," just our notion of which Collection objects the less formal term "collection" applies to. (That's if you have the same notion I had—that all Collection objects are collections.)

I'll take these questions in turn. There is a common feature of all elements of Collection objects. And it's not just that they're elements of Collection objects, of course. Pointing that out doesn't help. We want to know what makes them elements!

The pertinent common feature is their being values. That is, all elements are pieces of data representable by variables or literals.

Null elements are literals. They differ from primitive literals, not with respect to whether they're values, but with respect to whether they are directly assignable—so, assignable without autoboxing—to variables of reference types. These are types like Object and HashSet. Variables of these types store objects' memory addresses.

Though primitive literals are values, they cannot be elements, as Collection objects can only hold values directly assignable to variables of reference types. This is because Collection is a blueprint for data structures that are designed to group objects together. Primitives are not objects, nor are they the types of values that point to objects. So there is no need for Collection to accommodate the inclusion of primitives as elements.

But in describing a collection as a group of objects known as its elements, Oracle seemed to be saying a collection's elements are the objects themselves, not memory addresses or literals. It seems, then, that Oracle must mean something different by "element" when speaking of "null elements" in the documentation for Set.

Suppose we want our usage of "element" to be maximally consistent. Then we're at a crossroads, semantics-wise. Either we stop calling null values elements, or we stop calling objects elements, opting to call values elements instead.

Say we stop calling objects elements. Then we can alternatively define a collection as a group of non-primitive values, and define its elements as those values. This way we can keep calling all Collection objects collections, and keep calling occurrences of null in a collection elements.

If on the other hand we reserve the term "element" for objects, then we have to say a Collection object $C$ has no elements if all $C$ "contains" is null. And if $C$ not only "contains" null, but also contains objects, we must say that those objects $C$ contains are $C′sC'\textrm{s}$ only elements—that null is not one of $C′sC'\textrm{s}$ elements. And we must deny that any variable or literal is itself an element of $C,$ since no variable or literal is itself an object.

As observed previously, if there are such things as null elements, some Collection objects are not groups of objects—specifically Collection objects with only null elements. So, by Oracle's definition, such objects are not collections. Neither are Collection objects that "contain" null instead of elements, if such objects are possible. They're not groups of objects.

The only way a Collection object $C$ containing no other objects can be a group of objects is if it's an element of itself. $C$ would then be like a singleton set (in set theory) in that $C$ has only one object as an element. But $C$ would differ from a singleton in that (i) if we count null as an element and $C$ "contains" null, $C$ has at least two elements, and (ii) $C$ is in $C .$ (In Zermelo-Fraenkel set theory, no set is a member of itself.)

We might establish a linguistic convention according to which every Collection object is automatically an element of itself. That would make the relation between a Collection object and its elements a bit more like the relation between a set and its subsets in set theory. Every set is a(n improper) subset of itself, because it contains all the elements it contains. It's an idea, but I imagine it would make matters more confusing rather than less.

I say we classify values, not objects, as elements. What do you think?