9
$\begingroup$

An expression-oriented language sounds appealing, as I could have code logic inline in expressions and initializers. An if statement could just return the last expressions in their blocks similar to in Rust I believe:

x = if condition {y} else {z}

A switch could similarly return the last expression in their case blocks.

However, what could a loop return in a way that would be useful?

$\endgroup$
1
  • 1
    $\begingroup$ Mathematica is expression-oriented but dynamically typed. Loops in Mathematica simply returns None, unless you Break with some value. $\endgroup$
    – alephalpha
    Commented Jun 3, 2023 at 5:16

5 Answers 5

10
$\begingroup$

I like the answer from kaya3, but I think there's a better option.

Treat the body of the for loop as an expression itself, and treat every iteration as evaluating that expression. Then put the results in a list and return that list as the result of the loop.

In other words, this would be perfectly valid:

squares: []int =
for (i = 1; i <= 10; i += 1)
{
    i * i;
};

(I apologize if this isn't readable. This code is using the syntax of my own language.)

After this code, squares would be a list of the squares up to 100.

This has a few advantages.

  • After the loop, you know how many times the loop executed because that's the length of the list.
  • The only special case you need to worry about is an empty list, but that's a typical case for lists anyway.
  • Finally, you wouldn't have to differentiate between iterations that ended normally, used continue, or used break; they all can return a value and have those values added to the list.

My language does this. In fact, it does this for every kind of loop, which makes things really convenient.

Say you have a list of users, and you want a list of just their favorite things. You would write this:

faves: []Favorite =
foreach (user: users)
{
    user.favorite_thing;
}

And then I don't feel so bad!

$\endgroup$
14
  • 7
    $\begingroup$ That sounds like .map with extra steps. $\endgroup$
    – Bbrk24
    Commented Jun 3, 2023 at 1:35
  • 1
    $\begingroup$ It is, and that's where the idea came from. My examples don't show this, but sometimes, it's more readable to have a complicated loop with a body of code instead of a complicated lambda. And map would make it complicated to do an early break, for example. $\endgroup$ Commented Jun 3, 2023 at 1:41
  • 1
    $\begingroup$ Early break could be done by running until some sentinel value (like nil), or by passing a ref bool to the callback. $\endgroup$
    – Bbrk24
    Commented Jun 3, 2023 at 1:51
  • 1
    $\begingroup$ I was thinking something more like this. $\endgroup$
    – Bbrk24
    Commented Jun 3, 2023 at 2:08
  • 2
    $\begingroup$ @abel1502 in my language, if a loop body returns void, the compiler skips generating the coffee that would generate the list. Most uses of a loop as a statement, such as an event loop, fall under this and thus, do not become memory sinkholes. $\endgroup$ Commented Jun 3, 2023 at 13:47
7
$\begingroup$

The main issue is that a for loop might iterate 0 times. For a C-style for(init; cond; step) loop the condition might be initially false; for a for-each loop over an iterable, the iterable may be empty. So there needs to be some value which is returned in that case. (If you only allow do-while loops then you can avoid this problem, but the language will not be as expressive.)

Therefore the sensible way of returning a value seems to be as an option type: if the loop iterates at least once, then the value is Some(x) where x is the value of the body on the last iteration, otherwise if the loop iterates zero times then the value is None.

Alternatively, you could also allow Rust-style break <expr> as a way of returning a value from a loop expression, in which case the value could be some built-in sum type designed for the purpose (example below in Rust syntax):

enum ForResult<S, T> {
    None,
    Some(S),
    Break(T),
}

However, this may cause some inconveniences. If ForResult is used for every for loop even if there is no break expression inside it, then the type system will force the programmer to handle the impossible Break(_) case. On the other hand, if a regular Option is used for loops with no break expressions, then two for loops could have incompatible types when the programmer wants them to be compatible (e.g. in the two branches of an if/else expression).

Lastly, it's worth mentioning that in Rust a for loop does have a value, namely (), a unit value. This is a perfectly viable option for an expression-oriented language, though probably not what you were looking for as an answer.

$\endgroup$
3
  • $\begingroup$ "The main issue is that a for loop might iterate 0 times" The common solution to that is to require an else branch. $\endgroup$
    – Longinus
    Commented Jun 3, 2023 at 23:54
  • $\begingroup$ @Longinus For a loop? I know that Python has else branches for for loops, but they aren't required, and they don't only execute when the loop iterates zero times. (They execute whenever the loop completes without breaking.) I see you've mentioned Zig as an example in your answer ─ are there any others which do require loops to have else clauses? $\endgroup$
    – kaya3
    Commented Jun 4, 2023 at 11:54
  • $\begingroup$ I think so, unless my memory merged the two orthogonal concepts. I'll have to go through the FLL and AltJS corpora (of which I have been procrastinating for 6~8 months instead of porting them to PLDB) to find them. I'll report back later. $\endgroup$
    – Longinus
    Commented Jun 4, 2023 at 16:22
7
$\begingroup$

The setup

I'll take a different approach than the other answers.

What if we actually allow statements to be a new kind of expression, different from the others? What if that new kind of expression even had its own operations? Let's find out!

Let's say that in our language we actually "embed" the statements into the expressions like this.

A statement can be thought of as an "action." Two actions can be combined to form another action. For example, if you have an action x and an action y, you can use a sequencing operator (call it ;;) to combine them into a new action. This new action will first do the x action and then do the y action.

Say we want to print 1 and then print 2. These are two actions. You might write this print(1) ;; print(2). Of course, you can come up with much better syntax, this is just for illustration. ;; is a binary operation that takes two actions and gives you back another action (the "combination" of the two argument actions).

While loops

Alright, now what is a loop in this language? Well, let's start with a while loop. We can actually think of a while loop as a function that takes a Boolean expression (the conditional) and an action (the body) and returns an action. The action it returns is the action that repeats the while loop body action while the conditional is true.

while actually doesn't need to be a keyword here and, in fact, there are ways you could implement it inside standard library of the language.

You could write it like this (again using a made-up syntax purely for illustration; there are much better ones):

while(x > 5,
  (print(x) ;; x := x-1))

It looks like I've just written a while loop in a super weird way. And that is technically true. However, we've also gained something new. Actions are now first-class values in our language!

We can actually pass around the loop body I've written above. Say you want to abstract the notion of "looping 15 times." You can write a function

repeat15 =
  fun(a) =>
    let i := 0
    in
    while(i < 15, (a ;; i := i+1))

Now you could write

repeat15(print("*"))

and you'll print out 15 *s.

Also, if we wanted to, we could distinguish actions from "regular values" (like integers or strings) at a type level. We can do this by creating an Action<T> type for actions that produce a value of type T. We can distinguish between a string value we already have in our hand from an action that produces a string value. And, furthermore, we can pass both of those kinds of things around at will.

But what is the difference between an Action<Int> and an Int? Well, it's the exact same as the difference between /bin/ls and a list of files (paraphrasing a quote from Shachaf).

For loops

A for loop (or a foreach loop) can be thought of as a function that takes in a list and a "parameterized action" (a function that gives you back an action). It returns an action that does this: it will take each item of the list in turn and give it to the "parametrized action."

For instance,

for([1,2,3,4], fun(x) => print(x))

would print 1 2 3 4 (writing spaces for newlines).

So, what does a for loop return here? It returns an action! It doesn't return any particular value produced by the loop. It returns an action that actually performs the loop itself.

I mentioned that we can also have a version of ;; that passes a result from the first action to the second. Here's what that could look like. Call that operator -->:

getLine() --> (fun(x) => print(length(x)))

This would read in a line from standard input and print its length.

Note that ;; is just a special case of this:

a ;; b

is the same as

a --> (fun(_) => b)

As I've mentioned, you can come up with a better syntax. In fact, there already are better syntaxes. The reason is that these ideas already exist.

And that leads me directly to...

The punchline

What I've just described is a particular case of the concept of a monad (in the form in which it appears in programming languages).

Now, there is some debate about how people should learn about monads. Ultimately, I can only provide part of the answer for this.

I've only described part of one specific monad here. I believe to learn them properly you must experiment with a variety of them. For example, look at the list monad, the reader monad and the proxy monad. There are plenty more, but that is some variety to start with. Think about how the "bind" operation works for each of them works, in each particular case.

In the context of this question, the list monad in particular would be useful to look at. Also, my answer to a question here talks about the Maybe and Either monads in a somewhat similar style to this answer.

I also did not describe the mathematical laws they must obey (though there is a relatively intuitive way to look at these laws in terms of actions).

I've only scratched the surface of a particular monad here, but hopefully this answer can provide some useful ideas.

The particular monad I've described is roughly like Haskell's IO monad, though I've left all calls to writeIORef, readIORef and newIORef implicit. Also, the let-in in the repeat15 should really be a call to -->. I've simplified that for the purposes of demonstration. There are many other monads, as well. It remains the case that --> is the basic "action combining" operation. In Haskell, this is called >>=. Likewise, the Haskell name for ;; is >>. There's also an operation that will take a "regular value" and give you an action that simply produces that value without doing anything else. This is sometimes called (in Haskell) pure or (confusingly) return. It's also sometimes called "unit."

$\endgroup$
3
  • 2
    $\begingroup$ Welcome to PLDI! This is a great answer, though I guess it does create a bit of a chicken-and-egg if I'm reading it right...what's the T in the Action<T> for a for loop? :p $\endgroup$ Commented Jun 6, 2023 at 3:07
  • $\begingroup$ @RydwolfPrograms Good question! In that case, it would be the "unit type." This is a type that only has a single value. In Haskell this is called () and in Standard ML it is called unit. So, in our sort of made up syntax, let's call this type Unit and we could write Action<Unit>. Let's use the name tt for the only value of type Unit. Now, let's contrast this with Bool. If you have a variable x of type Bool, you know it must either be true or false. On the other hand, if y has type Unit you know it must be tt. It contains no information, but you can easily build it $\endgroup$ Commented Jun 6, 2023 at 3:13
  • $\begingroup$ Now that I think of it, though, using the unit type like that is only one approach. You could actually the incorporate ideas from the other answers into this and choose something else for T. In fact, you could implement each of those inside a language that has this sort of action type. $\endgroup$ Commented Jun 6, 2023 at 3:19
6
$\begingroup$

A common approach at stateful loops in languages with expression-oriented syntaxes is to see them as conditionals where the loop either stops itself with a result, or invokes an else branch.

Hence,

let x = while y do z else w

is interpreted as

let x =
    let _tmp = None
        rec _f() =
            if ((_tmp is None) and y) then (z; _f())
            else ()
        _ = _f()
        in
    if _tmp then _tmp
    else w

where _tmp holds the eventual result (in the below example set by break).

An actual, useful, example may look like this:

find[A](x: A, xs: Iterable(A)): Maybe(Index(xs)) =
    let i = 0 in
    foreach e in xs do
        if e == x then
            break i
        else
            i += 1
    else
        None

test "loop" with
    assert(find(5, 0.toIncluding(10)) == 5);
    assert(find(5, positiveEvenIntegrals.toIncluding(10)) == None)

Zig is a precedent there. Python and Ruby both have related features but lacking the returned value aspect.

$\endgroup$
3
$\begingroup$

One option is outputting the loop guard. This has the advantage of always having a value even if the loop is run 0 times, but somewhat restricts how the initialization of the loop could work.

For example, consider code like this:

let i = 0;
let d = for (b=1; i<10; i++) {
    b*=2;
}

Here, it d will equal 1024, the final value of b. Note we type b=1 not let b=1 since the variables declared in that place have special meaning and that position in the loop should not be confused with a normal statement.

It could even work with normal variables if your language supports tuples:

let x,y = for (b=1, i=0; i<10; i++) {
    b*=2;
}
// x=1024, y=10

The advantages of this method are:

  • Always produces a value even if the loop terminates after 0 iterators
  • Outputting the final value after repeated operation is potentially quite useful

Disadvantages:

  • Restricts types of operations that can be performed in the left most expression of a for loop
  • Requires declaring variables before the loop if you don't want them included in the output, polluting scope.
$\endgroup$
3
  • $\begingroup$ If the loop's value is always equal to the value of a specially nominated variable (b in this example), does it need to be the loop's value? You could equally write the same loop followed by let d = b;. I suppose there is the opportunity for this to be a shorthand when a loop appears in other places, but it's a non-obvious shorthand to me at least. $\endgroup$
    – kaya3
    Commented Jun 3, 2023 at 13:30
  • $\begingroup$ @kaya3 True, I think this idea might be even more terrible than I thought $\endgroup$
    – mousetail
    Commented Jun 4, 2023 at 14:25
  • $\begingroup$ It's not terrible! Just maybe it needs a syntax that makes clearer what value is produced. $\endgroup$
    – kaya3
    Commented Jun 4, 2023 at 17:21

You must log in to answer this question.

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