6
\$\begingroup\$

So, there's a community consensus that functions from stack based languages can leave their output on the stack. This question is about an edge case for that. Suppose the correct result is some value x. Also suppose that that you are working with a stack based language that has an unlimited well of x's on the stack. Is it then valid to leave the stack unmodified?

For example, if the task is "output 0," and my language has an infinite well of zeroes on the stack, is a zero-length function valid? (Disregarding the fact that zero-byte solutions are sometimes considered invalid because they have zero bytes).

| |
\$\endgroup\$
  • \$\begingroup\$ Out of interest: Is there a stack-based language with a infinite well of zeroes that allows a function to be defined in zero bytes? \$\endgroup\$ – Dennis Dec 8 '16 at 3:22
  • \$\begingroup\$ @Dennis I know there are stack based languages with wells of zeroes, but I've no idea about defining a function in zero bytes... That was just an oversimplified example \$\endgroup\$ – Socratic Phoenix Dec 8 '16 at 3:26
  • 3
    \$\begingroup\$ Related: Truthiness in Brain-Flak and similar stack-based languages \$\endgroup\$ – Dennis Dec 8 '16 at 3:27
  • \$\begingroup\$ @Dennis: 7 doesn't have an infinite well, but its stack-equivalent starts with one or two no-op functions on the stack, depending on how you count it (which can also be interpreted as integers, with a value of 0 or 1 depending on which representation of integers you're using). 7's one of those languages which gives you a bunch of building blocks and how you interpret them is mostly up to you. \$\endgroup\$ – user62131 Dec 9 '16 at 8:01
5
\$\begingroup\$

While I broadly agree with Mego's answer, I find that it leaves a few important cases as implications, and I think it would be clearer to spell them out explicitly.

I admit that the answer you linked isn't very explicit about how stack-based I/O works for functions, but there is a sort of unwritten but accepted set of rules that such functions adhere to (at least the ones I've written or reviewed), so this answer tries to collect these:

  • When the function is called, input is given as a number of values on top of the stack. The function must not assume that the input is the only content of the stack. In particular, the function should work regardless of the stack contents beneath the input.
  • If the input is a list of variable length, the individual values may appear as separate values on the stack, but then there either needs to be an appropriate terminating value (e.g. a -1 if all elements are guaranteed to be non-negative numbers) or the number of elements should be on top of the stack.
  • At the end of the function, all input values should be replaced with the output values. Any part of the stack that wasn't part of the input has to remain unchanged.
  • As for input, variable-sized output is possible either by terminating it with an appropriate value or by storing the number of values on top.
  • Finally, if the solution is entirely indistinguishable (by the means of the language) from a solution that follows the above rules, it's valid.

The last point is where infinite stacks come into play. In general, a function can't work with the infinite well at the bottom of the stack, because you're not allowed to make any assumptions about what lies between the input and the infinite well. However, if your function detects that there is nothing between the input and the infinite well, and the output is identical to the default value of the infinite well and it's impossible to distinguish implicit values from explicit ones, then the function can return on an "empty" stack.

The key here is "it's impossible to distinguish implicit values from explicit ones". As an example, my language Labyrinth (which doesn't have functions, but it will act as an example) has infinite stacks with an implicit well of zeros at the bottom. However, it does make a difference whether you leave off with an "empty" stack or a stack with a single explicit zero on top, because there's a stack-depth command, which would count the explicit zero. Other languages, like my language Stack Cats (still no functions, but you get the point) will automatically discard any zeros at the bottom of the stack, because they're indistinguishable from the infinite well anyway.

Further, consider a hypothetical language that doesn't have an infinite well of zeros, but where the stack starts out with 1 on top, 2 below that, then 3 and so on (still an infinite well, but it contains the natural numbers instead of copies of a fixed value). In this case, it's unlikely you'll be able to make use of the infinite well at all, because the function can't assume that all of the implicit values are still there, and even if they are, putting another 1 on top is clearly different from not doing so.

So while in principle it's possible to make use of the infinite well at the bottom, this only works in the very narrow case, that there is absolutely no way to tell the difference, which is probably not worth the bytes in most cases.

| |
\$\endgroup\$
  • \$\begingroup\$ Another thing I considered addressing is languages with multiple stacks, but I think the possible semantics for multiple stacks are too varied to come up with good blanket rules for those. \$\endgroup\$ – Martin Ender Dec 8 '16 at 12:23
  • \$\begingroup\$ I don't follow your reasoning behind "the function should work regardless of the stack contents beneath the input". Obviously, we can't have submissions that require the stack to contain additional values (between the input/infinite well), but they should be allowed to require no additional values. \$\endgroup\$ – Nathan Merrill Dec 8 '16 at 14:18
  • \$\begingroup\$ @NathanMerrill That would mean you can only ever use the function if you've got no other data in your program at the moment. That's like saying your Python function only works if you haven't defined any globals at all. The general assumption for using a function in a stack-based language is that you're working on a bigger problem, then you've got an intermediate result on top of your other data, transform it with the function, and then continue working with it. If your solution only works on a clean stack, you'll have to use a full program. \$\endgroup\$ – Martin Ender Dec 8 '16 at 14:25
  • 1
    \$\begingroup\$ At least that's the standards I and several users have held all CJam function submissions to in the past. \$\endgroup\$ – Martin Ender Dec 8 '16 at 14:26
  • \$\begingroup\$ So, if I understand, you'd allow full programs to make that assumption, and not functions? I can agree with that reasoning. \$\endgroup\$ – Nathan Merrill Dec 8 '16 at 14:28
  • \$\begingroup\$ @NathanMerrill Well a full program automatically has that assumption, because it's impossible to put something onto the stack outside of the program. \$\endgroup\$ – Martin Ender Dec 8 '16 at 14:29
  • \$\begingroup\$ Well, I think I'd definitely make the clearer in your post. \$\endgroup\$ – Nathan Merrill Dec 8 '16 at 14:30
  • \$\begingroup\$ @NathanMerrill I had the impression that this entire discussion was only about functions. "So, there's a community consensus that functions from stack based languages..." \$\endgroup\$ – Martin Ender Dec 8 '16 at 14:33
  • \$\begingroup\$ Ah, I must have missed that :) \$\endgroup\$ – Nathan Merrill Dec 8 '16 at 14:34
  • \$\begingroup\$ I don't think that explicitly requiring the number of input elements for variable-length input is necessary. Consider a challenge where you are given a string and a sequence of booleans, where each boolean corresponds to a character in the string, and represents whether or not to swap the case of that character. In that scenario, the number of input elements can be implicitly specified in the string - there will be len(string) + 1 inputs. \$\endgroup\$ – user45941 Dec 9 '16 at 4:50
  • \$\begingroup\$ @Mego I'd say that's good enough - the point was, it needs to have some way to know how many inputs there are. \$\endgroup\$ – Riking Dec 9 '16 at 10:35
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – redstarcoder Dec 9 '16 at 16:12
  • \$\begingroup\$ I believe the bullet containing the function should work regardless of the stack contents beneath the input. should exclude languages with multiple stacks as they can easily create another stack before calling the function. See my *><> example here explanation on functions in *><> here. You can see expecting a clean stack is a good way of calling a function with variable length parameters. \$\endgroup\$ – redstarcoder Dec 10 '16 at 17:46
4
\$\begingroup\$

The output must replace the input on the stack

Naturally, this means it must be on top of the stack. If you are outputting multiple values, they can be combined in a single stack element like a list, or they can all be individual stack elements. The end of the output is defined as the stack element on top of the first stack element that was not part of the input (if any). For example, if your stack looked like [1, 2, 3, 4] (top is left), and you called a function f which took two arguments and returned any number of arguments, the stack afterwards must either look like [[...], 3, 4] or [..., 3, 4] (where ... represents any number of elements). [5, 3, 4] would mean the output is 5. However, [3, 5, 4] would not be valid, as it modified values on the stack below the input.

In other words, the final stack minus the output element(s) must be indistinguishable from the initial stack minus the input element(s). This means that, if you have an infinite amount of identical elements below the input, the function may remove any number of those elements, since an observer (who only sees the function as a black box) would not be able to tell whether or not any of those infinite identical elements were removed.

| |
\$\endgroup\$
  • 1
    \$\begingroup\$ In some languages such as Grass, this is impossible. \$\endgroup\$ – jimmy23013 Dec 11 '16 at 14:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .