How does the map function work in stack-based languages?

Question

In many languages, the map function takes a function and a list, and applies the function to each element of the list, returning a new list of the results. Some languages require the input function to be unary, while others allow it to be n-ary and take multiple lists as input.

However, in stack-based languages, functions work on stacks. A function may pop some number of items off the stack, do something with them, and push some number of items back onto the stack.

How does the map function work in stack-based languages? How does it work when the input functions push more than one item onto the stack?

For example, what would the following code (in a hypothetical stack-based language) do?

1 [2 3 4] {swap} map

One idea I had was to introduce a simple type system, where each function has a fixed arity, and the map function only accepts functions that pop one item off the stack and push one item back. So the above code would be rejected. However, this seems to be too restrictive.

How do real stack-based languages handle this problem?

Answer 1

The typed approach you describe generally is how typed stack-based languages work, sometimes with a little more flexibility when you have the stack before and after line up. You won't be permitted to push more than one output value, or to have no output.

For example, in Kitten, the type of map is <A, B> (List<A>, (A -> B) -> List<B>) - taking in a list of A and a function from A to B. For a fixed function, this isn’t any more restrictive than the corresponding signature from Haskell ((a -> b) -> [a] -> [b]).

Factor isn’t typed to the same extent, but its stack effects do specify the same shape for map’s function argument: ( ... elt -- ... newelt ); this means that the stack has to be the same shape before and after applying the quotation, but the data types don't have to match.

For a language with quotation combinators to inject arguments, there's typically no loss of generality from requiring the function be typed this way. For a language that mandates you leave the rest of the stack in the state you found it, you might be able to use some values non-destructively, under the same conditions as for untyped languages below.

For a fully-typed system something like {swap} map is necessarily prohibited, because the type of the resulting elements from lower on the stack is unknown, so the resulting collection would be heterogeneous. For something like Factor where the goal is only stack safety, this can be ok.

In both cases, something like {dup} map is a no go: it's a static error that the stack depth mismatches. Pushing more than one value to the stack is not allowed, because there would be unknown numbers of values left afterwards, so it simply doesn't work.

---

Untyped languages are a slightly different story, since they don't have to care about keeping the stack values in a known state. The canonical stack-based language, Forth, in general just doesn’t have these sorts of higher-order functions in the first place — it’s aimed at a more machine-level execution model. Others that do, like Joy and some higher-level Forth dialects, most often treat the operation as a single-return function, and would treat the top element on the stack as the replacement. Depending on their implementation, something like 1 [ 2 3 4 ] { swap } map might

• Work as you probably expected (-1 to every item); this is what would happen in Joy.
• Error out, because you’ve gone off the end of the isolated stack containing only arguments that this language evaluates functions on, and lower items were never moved in.
• Just break, because you’ve interfered with the internal state of the map function, which is what was on the stack immediately below the element you’re processing, and when it resumes it does something wrong or illegal.

Any of those is generally reasonable, though the latter is probably the more principled stack-based approach and what you’d expect in a machine-level Forth, for example. The first behaviour can be obtained either by “cheating” with state off the language-level data stack, or by including a separate parallel stack for iteration data (here’s one that does that). The middle case is either a leaky implementation strategy, or really an instance of being a little bit typed, like Factor.

If you dup instead of swap, you'd still break in the final case, probably leave copies of all the items behind in the first case, and who knows in the middle case. It’s conceivable that a system could take all of the added stack items and put them all into the output collection (so really performing a flat map/bind rather than a functor map), but I couldn’t name one that does.

For the parallel/zip-map case you mention, Joy has a two-list map operation, but no higher than that. It just pushes and takes the two items in order. You could swap items between lists if you wanted.

Answer 2

I tried some stack-based or concatenative languages to see how the following codes work:

1 [2 3 4] {add} map

1 [2 3 4] {swap} map

1 [2 3 4] {dup} map

add pops two items off the stack and pushes one back. swap pops two items off the stack and pushes two back. dup pops one item off the stack and pushes two back.

Joy

As @Michael Homer said, Joy simply treats the input function as a single-return function, and would treat the top element on the stack as the replacement. The rest of the stack is not affected.

1 [2 3 4] [+] map put .

This prints [3 4 5] 1. Try it online!

1 [2 3 4] [swap] map put .

This prints [1 1 1] 1. Try it online!

1 [2 3 4] [dup] map put .

This prints [2 3 4] 1. Try it online!

Factor

I don't know Factor, so I'm not sure if I'm doing it right. But the result is really interesting.

USING: math sequences ;

1 { 2 3 4 } [ + ] map

This errors as expected. The error message is Data stack underflow, followed by some stack trace that I don't understand. Attempt This Online!

USING: kernel sequences ;

1 { 2 3 4 } [ swap ] map

It prints (Attempt This Online!):

--- Data stack:
4
{ 1 2 3 }

The result is unexpected but understandable. It seems that it treats map's function argument as a function that takes one argument, returns one value, and possibly modifies the stack as a side effect. So here, [ swap ] map first swaps 2 and 1, where it returns 1 and leaves 2 on the stack. Then it swaps 3 and 2, and finally 4 and 3. So the result is { 1 2 3 }.

USING: kernel sequences ;

1 { 2 3 4 } [ dup ] map

It gives a stack effect error (Attempt This Online!):

The input quotation to “map” doesn't match its expected effect

For more information, evaluate:
    "inference-branches" help

Input   Expected                  Got
[ dup ] ( ... elt -- ... newelt ) ( x -- x x )

The first two examples above doesn't seem to check the stack effect. However, a simple modification to the first example gives a stack effect error:

USING: math sequences ;

1 1 1 { 2 3 4 } [ + ] map

Attempt This Online!

I don't understand why adding two 1s to the stack makes a difference. Does it mean that Factor checks the stack effect after evaluation instead of before?

Kitten

Kitten is static-typed. I can't find an online interpreter for it, so I tried it on my computer.

1 [2, 3, 4] { (+) } map

It is rejected by compile-time type checking as expected. Here is the error message on REPL:

<interactive>:1.16-17: I can't match the type 'R...'
<interactive>:1.16-17: with the type 'R..., A'

<interactive>:1.16-17: the type 'R...'
<interactive>:1.16-17: occurs in the type 'R..., A' (which often indicates an infinite type)

<interactive>:1.16-17: you may have a stack depth mismatch

However, the second example is accepted:

1 [2, 3, 4] { swap } map

The REPL prints:

[1i32, 2i32, 3i32]
4i32

The result is the same as Factor's. It seems that map's type isn't as restrictive as I thought. At least it allows functions that push and pop the same number of items, even if this number is not 1.

1 [2, 3, 4] { dup } map

This is also rejected by compile-time type checking.

I read the source code of Kitten's standard library, and found that map's type signature is map<A, B, +P> (List<A>, (A -> B +P) -> List<B> +P). Kitten has a simple effect system called Permissions. +P might be related to it.

Cognate

It seems that Attempt This Online! isn't working for Cognate, so I tried it on my computer.

Unlike most other stack-based languages, Cognate is prefix instead of postfix.

Print Map (+) List (2 3 4) 1;

This errors with Stack underflow.

Print Map (Swap) List (2 3 4) 1;

This also errors with Stack underflow.

Print Map (Twin) List (2 3 4) 1;

This prints (2, 2, 3, 3, 4, 4). It also shows a warning: Exiting with 1 object(s) on the stack.

Cognate's documentation isn't very clear, so I don't really know how it works. It might be one example of "error out, because you’ve gone off the end of the isolated stack" in Michael Homer's answer.

Uiua

Uiua is a new language that combines stack-based and array programming. It is also prefix.

map is called each in Uiua, and is represented by the symbol ∵. Usually we don't need it, because most functions are already vectorized.

∵+ [2 3 4] 1

It prints [3 4 5] as expected, and shows a warning that ∵ is not needed. Try it online!

∵∶ [2 3 4] 1

swap is called flip and is represented by :. The code above prints (Try it online!):

[1 1 1]
[2 3 4]

The top of the stack is still [2 3 4], while the 1 below it becomes [1 1 1]. This is unexpected. I don't understand it at all.

∵. [2 3 4] 1

duplicate is represented by .. The code above prints (Try it online!):

1
[2 3 4]
[2 3 4]