Loop and recursion

Generic loops are problematic to reason about and understand when you read the code, and therefore prone to cause bugs. I think it would be beneficial to forbid generic loops, and only have iterators.

Recursions can also be problematic since the stack usage can become unpredictable. The exception is of course tail recursions, since those can re-use that current stack frame.

If the language would prohibit generic loops and recursions except for tail recursions, would it still be useful as a generic programming language or would those restrictions make some common designs impossible?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

only tail recursion

(1) I see no problem with eliminating loops in favor of tail-recursion: I rarely/rarely/rarely use loops in OCaml, preferring almost always tail-recursion or "inductive" iter/fold/map/whatever combinators instead.

(2) eliminating non-tail-recursion completely doesn't change the expressive power of the language either: you can always CPS-translate (as we've seen in Node.JS and other languages, via the "control" monad) away non-tail recursion into tail-recursion.

BUT: (3) there is a performance penalty to be paid for only having tail-recursion: I know of no widely-used compilers that can re-infer the stack-like nature of the continuation-chain, and thereby recover the efficiency of stack-allocation of frames. And this is a serious issue if you're writing performance-sensitive code.

Continuation chains

If those are a problem depends on what parallelism the language will support, I've got some other ideas there that I really have no idea whether they will make the situation any better...

tail recursion is the same

tail recursion is the same thing as a generic loop.

And since a loop with a manual stack can do the same things as recursive functions, what have you gained from prohibiting recursive functions?

The idea was to promote

The idea was to promote better coding without sacrificing expressivity. General loops are generally looked down upon because they are hard to read and understand. Iterators and recursions are usually seen as easier to understand. The reason for limiting to trail recursions was to avoid hard to predict stack consumption.

General loops are generally

General loops are generally looked down upon

Perhaps they are looked down upon by religious extremists, but I almost never meet real programmers who complain about loops.

...recursions are usually seen as easier to understand

This would surprise me. I would posit that fewer than a third of programmers (professional, $100k+/yr jobs) can understand most recursive examples without a significant amount of effort.

Loops are ugly. That's the real complaint. They're easy to understand, but ugly. And they leak all sorts of details. But they work, and people grok them.

I would posit that fewer

I would posit that fewer than a third of programmers (professional, $100k+/yr jobs) can understand most recursive examples without a significant amount of effort.

I'd hazard that it will be the same amount of effort it took to them to get comfortable with loops. Seems to me, this difficulty is largely due to a lack of exposure since they learn imperative languages first (and often, only), not due to any inherent difficulty with recursion over loops.

Difficulty of loops and recursion

Basing on the abstraction tier model.

The general recursion over concrete types has the same abstraction tier as a loop. One need to use the first order logic to reason about both. On other hand loops are more local than generic recursion, since one does not need to switch lexcial context from loop to caller of the loop if there are only global functions (like Prolog predicates or C functions/procedures). There is also a need to aggregate context and pass it to loop function. So programs with concrete recursion are harder to understand, and this was one of major issues with Prolog program understandability for me.

If there are objects, local functions, and lambdas, this is a usage of the existensial types, so it requires the second order logic to reason about, and the code the heavier to reason about per code element since concepts belongs to the next abstraction tier. Collection operations (like map, flatMap, filter, etc.) might be easier to understand for trained mind in some cases, but they are inherintly harder to learn than loops due to the higer abstraction tier. Generally higher abstraction tiers concepts are like ammunition of higher caliber. They are more powerful, but they tax mind more.

So, the loops are easier to learn in both cases, since they are either have lower abstraction tier or they are more local. Note, I consider there a case when software engineer really understands what the code is doing and able to reason about it. And not the case when code is copied and modified from tutorials and stack overflow.

On other hand loops are more

On other hand loops are more local than generic recursion, since one does not need to switch lexcial context from loop to caller of the loop if there are only global functions (like Prolog predicates or C functions/procedures).

I'm not sure what you're trying to say here, or what "more local" means. Loops also "switch lexical context" when they update the bound variables, check the loop condition, then either resume or exit.

There is also a need to aggregate context and pass it to loop function. So programs with concrete recursion are harder to understand, and this was one of major issues with Prolog program understandability for me.

I don't see how this follows. Whatever context you need to aggregate and pass in a recursive call, you also need to accumulate in the equivalent loop.

they are inherintly harder to learn than loops due to the higer abstraction tier.

Yes, the fact that recursion can extent to higher levels of abstraction means those more abstract instantiations are more difficult to understand. I don't see how that makes recursion at the same "abstraction tier" less understandable though.

If anything, haven't you just argued that recursion is strictly superior since the same concept extends to more abstract domains?

Lexical context swtiching and cognitive cost

I'm not sure what you're trying to say here, or what "more local" means. Loops also "switch lexical context" when they update the bound variables, check the loop condition, then either resume or exit.

Let's consider the random example from web:

#include <stdio.h>
int main()
{
    int num, count, sum = 0;

    printf("Enter a positive integer: ");
    scanf("%d", &num);

    // for loop terminates when num is less than count
    for(count = 1; count <= num; ++count)
    {
        sum += count;
    }

    printf("Sum = %d", sum);

    return 0;
}

The for-loop happens in the context of main(..) function. So the lexical usage context is clear for it. If we replace it with recursion. We need to refactor it out as a separate function. So context of call and usage site will be separate. One need to change attention from main function to loop function. This attention switch between lexical context is extra cognitive effort. Just another random example from web example with Prolog:

mergesort([],[]).    /* covers special case */
mergesort([A],[A]).
mergesort([A,B|R],S) :-  
   split([A,B|R],L1,L2),
   mergesort(L1,S1),
   mergesort(L2,S2),
   merge(S1,S2,S).

split([],[],[]).
split([A],[A],[]).
split([A,B|R],[A|Ra],[B|Rb]) :-  split(R,Ra,Rb).

merge(A,[],A).
merge([],B,B).
merge([A|Ra],[B|Rb],[A|M]) :-  A =< B, merge(Ra,[B|Rb],M).
merge([A|Ra],[B|Rb],[B|M]) :-  A > B,  merge([A|Ra],Rb,M).

There is no clear lexical context guiding for loops. One needs to switch attention between different lexical contexts.

I don't see how this follows. Whatever context you need to aggregate and pass in a recursive call, you also need to accumulate in the equivalent loop.

But this context lives in the same lexical scope, there is no need to switch back and forth between different functions. And there is no need to aggregate local variables into an additional structure. Context switches are expensive for brain too.

If anything, haven't you just argued that recursion is strictly superior since the same concept extends to more abstract domains?

Higher-tier abstractions are not necessarily better, because the brain need to spend more efforts to learn, use, and understand them. For example, in Java one has to use a class context just to write a hello world program. In Haskell, one needs understand and use the concept of Monad for a hello world program. In Groovy, the print statement could be at the top level.

The monad and classes might be useful for other tasks, but for a hello world program they are just extra cognitive cost that an engineer has to pay. The monads and classes require the second order logic to understand.

If the task does not require higher-level abstractions, why to use them? They start to make sense only when their usefulness outweighs their cost for the specific task. And this is one of reasons why I do not use Haskell for pet projects.

The for-loop happens in the

The for-loop happens in the context of main(..) function. So the lexical usage context is clear for it. If we replace it with recursion. We need to refactor it out as a separate function. So context of call and usage site will be separate. One need to change attention from main function to loop function. This attention switch between lexical context is extra cognitive effort.

Is it more cognitive effort overall though, or is it less because each function requires less context individually? This assertion of extra cognitive effort sounds like an empirical question for which I've seen no evidence.

I will also note a strange contradiction that seems among programmers, which is that almost everyone agrees that it's wise is to build programs with small reusable functions, but then they immediately invent reasons and languages that discourage this very thing. So when you say recursion makes us "refactor [sum] out as a separate function", my immediate thought was "good!", and I've seen no convincing reason so far to change that conclusion. The sum function you describe is immediately reusable where the embedded loop is not reusable. If your language encourages loops over recursion, then it sounds to me like it's encouraging code duplication and the subsequent maintenance problems that brings.

But this context lives in the same lexical scope, there is no need to switch back and forth between different functions.

I don't see why 1 context switch somehow dominates all other software engineering considerations. Your loop has some inputs and computes a (possibly compound) result. The equivalent recursive function has some inputs and computes a (possibly compound) result. In either case, you're reasoning from inputs to outputs, but in the recursive function you need to consider less context at any given point, eg. with the loop you have to be aware of any state updates along every possible control flow path, where with the recursive function, updates to the calling context are encapsulated in the return value.

The vast majority of code people write operates on fewer than 6 variables at any given point. If loops encourage entangling partially overlapping but disjoint contexts, that sounds like a terrible idea for any real code. If recursive functions instead encourage separating contexts so you need only consider the relevant information to the problem at hand, that sounds like a win.

I'm sure we could go back and forth on this all week, so absent any empirical evidence I don't see any reason to accept your claims. You see the different lexical scope as a disadvantage, where I instead see it as an advantage.

And there is no need to aggregate local variables into an additional structure.

I still don't see how this follows. Any local variable in a loop would be lifted into a function parameter in the recursive equivalent. There's literally no additional structure, you're just moving the location of the bindings.

If the task does not require higher-level abstractions, why to use them?

Then don't use them if they're not appropriate. But if the same thought pattern for less general abstractions can be extended to more general abstractions, then that's useful. Why would I learn 3 different concepts to achieve a given level of abstraction if I can simply learn 1 that smoothly generalizes to cover all of them?

For instance, what is the loop-based equivalent of defining a recursive type? If you can't imagine how this could be expressed, then you must acknowledge that programmers need to understand how to apply recursion anyway. You speak of cognitive load, but you don't seem to apply it evenly in different contexts.

Context switch cost

I will also note a strange contradiction that seems among programmers, which is that almost everyone agrees that it's wise is to build programs with small reusable functions, but then they immediately invent reasons and languages that discourage this very thing. So when you say recursion makes us "refactor [sum] out as a separate function", my immediate thought was "good!", and I've seen no convincing reason so far to change that conclusion. The sum function you describe is immediately reusable where the embedded loop is not reusable. If your language encourages loops over recursion, then it sounds to me like it's encouraging code duplication and the subsequent maintenance problems that brings.

Inner-outer-block context switch has less cost because of visual locality. Also, there is no indirection step, and there is no cognitive effort to resolve this indirection. Any indirection has additional resolution cost. If there is a reuse of code, indirection cost is compensated by learning what function does and reusing that knowledge. For a single use, indirection cost may or not be offset by cost of having larger procedure.

The particular variant of sum in the example has about zero reuse potential, since it is a very specific variant of sum. So, it does not make sense to separate it into function basing on reuse. Also, separating to function does not reduce complexity of main(...) noticeably, so there is no reason to move it out basing on it.

Also, too many procedures or functions have own cost as they pollute global namespace in the tier 3 languages like C.

The vast majority of code people write operates on fewer than 6 variables at any given point. If loops encourage entangling partially overlapping but disjoint contexts, that sounds like a terrible idea for any real code. If recursive functions instead encourage separating contexts so you need only consider the relevant information to the problem at hand, that sounds like a win.

Separating context and creating a good abstraction is an effort. It might help or not later, but the ultimate goal of programming is not creating a good code. The goal is 'getting things done'. Generally, the code with total cost of 2h is better than code with total cost of 6h (including creation, maintenance, etc.), if the code works the same. Balancing different costs is a major part of the art of programming. Good engineering is not only about the code, it is about how the code solves real-life problems.

Some tasks worth investing time to optimize form or performance, some do not. The loop abstraction allows a quick solution to many tasks by sharing context, so one does not need to spend time to separate contexts. If task really need abstraction, the abstraction could be refactored out later. Forcing people to use abstraction everywhere is just creation of overheads.

Software is not written once except for few cases. It is evolving entity, so it does not have to be perfect. The particular piece of code might be as well dropped in the future, so all extra efforts spent on it will be wasted. The quality of the code should be just sufficient for the task. Overengineering might be a bigger problem than sloppy code in the long run.

For instance, what is the loop-based equivalent of defining a recursive type? If you can't imagine how this could be expressed, then you must acknowledge that programmers need to understand how to apply recursion anyway.

Böhm–Jacopini theorem says that recursion could be replaced by iteration. And considering stack-size limitations it has to be done quite often.

The particular variant of

Inner-outer-block context switch has less cost because of visual locality. Also, there is no indirection step, and there is no cognitive effort to resolve this indirection. Any indirection has additional resolution cost.

Maybe, maybe not. Again, this is an empirical question, not a claim you can validate via introspection about how your mind works. We're all guilty of too much hand waving in programming language debates.

The particular variant of sum in the example has about zero reuse potential, since it is a very specific variant of sum. So, it does not make sense to separate it into function basing on reuse. Also, separating to function does not reduce complexity of main(...) noticeably, so there is no reason to move it out basing on it.

This is also why your arguments aren't convincing. Even if I accepted your conclusion of this example, as you yourself basically just stated, it's trivial code that's not representative of anything realistic.

Also, too many procedures or functions have own cost as they pollute global namespace in the tier 3 languages like C.

I want to be clear that I'm not saying recursion is superior in every language. You should use the idioms that are common to whatever language you're using, but if you're designing a language per the posted topic, recursion seems superior for anything but contrived examples.

Separating context and creating a good abstraction is an effort. It might help or not later, but the ultimate goal of programming is not creating a good code. The goal is 'getting things done'.

...with an eye towards ensuring you can continue to get things done later. I agree abstraction requires effort. Even if recursion has more cognitive load, it would be negligeable. Recursion vs. iteration will simply not make or break your project.

The loop abstraction allows a quick solution to many tasks by sharing context, so one does not need to spend time to separate contexts. If task really need abstraction, the abstraction could be refactored out later. Forcing people to use abstraction everywhere is just creation of overheads.

Code is read far more often than it is written, so I could very easily object to your arguments that any language defaults that encourage you to organize your code around small functions will pay large dividends down the road. I have presented just as much evidence of this claim as you have about your claims for recursion, so neither of us should have convinced a skeptic. Like I said, I could do this all week, and we'll ultimately end up in exactly the same place: with no way to resolve who's right because we're debating an empirical question without any data.

Böhm–Jacopini theorem says that recursion could be replaced by iteration. And considering stack-size limitations it has to be done quite often.

Of course it could be. That's rather beside the point I was making, which is that recursion appears in many different contexts and you can reuse the the same operational thinking in all of them. If your language has loops and type-level recursion, well you've just doubled your conceptual load for no good reason that I can see, unless you have some notion of what would constitute a type-level loop.

Upfront vs hotspot abstraction introduction

...with an eye towards ensuring you can continue to get things done later. I agree abstraction requires effort. Even if recursion has more cognitive load, it would be negligeable. Recursion vs. iteration will simply not make or break your project.

I would disagree about negligible. Understanding recursion requires a mind shift, after that it is easier. Inductive reasoning is a skill that need to be seriously trained. If brain is trained along the line, each usage of the recursion reduces cost a bit.

I do see this when doing code reviews. The cost of recursion is hard to estimate and boundaries (like the stack size) are harder to control, and people do make mistakes there. Tail recursion optimization is only applicable for linear structures, and it is easy to disable it. In contrast, cost of loop is more apparent for beginners, as it is easier to compile in the brain to lower-level constructs.

Also, consider the compiler complexity for efficient recursive functions and loops. This compilation need to be done not only by software before execution, but by brain as well to understand a general idea how it runs.

This is also why your arguments aren't convincing. Even if I accepted your conclusion of this example, as you yourself basically just stated, it's trivial code that's not representative of anything realistic.

The code is realistic in sense that there are a lot of such small processing pieces spread along of typical enterprise application. And such pieces are rarely reusable, because they are dependent on data-type, task, and context. And it demonstrate precisely the thing that does not worth creating a separate abstraction, and it lives just fine as a loop. But in case of recursion, one will be forced to create a separate named abstraction for it, paying extra cognitive cost.

Code is read far more often than it is written, so I could very easily object to your arguments that any language defaults that encourage you to organize your code around small functions will pay large dividends down the road.

There is a difference between forcing and encouraging. Forcing would just create a language with the high development cost. One of reasons why Haskell is not popular is because too much things are forced: immutability, monads, recursion, etc.

Even for reasoning about simple imperative tasks like IO, one need to translate imperative-looking DSL to 'pure functional code' and then translate functional code to imperative machine code in the mind, just to understand performance implications and the operation order. Scala or Kotlin allow writing imperative code for imperative tasks, there is no artificial pure-functional step in the reasoning. Brain will eventually short-circuit this reasoning, but this extends time needed to learn the language and makes critical early adoption stages more problematic.

For a new language it is important to support paying only for things you need, rather than forcing high upfront costs. Simple things should be done in a simple way. If one needs to spend more cognitive efforts to get simple things done, one would just use some other language. Doing it in another way might lead to repeating the fate of Haskell, that failed to get a noticeable market share despite all hype.

IMHO Kotlin is a good example of a well-balanced language: simple things are simple, higher-tier abstractions might be gradually introduced when needed. Kotlin allows evolving program on complexity hotspots, rather than doing abstraction optimization everywhere upfront.

Recursion is just a function call

When I code recursion, I see the recursive call as just a function call, and the appropriate function to call just happens to be the same function I call from.

While this might seem like it makes recursion easy to understand, I have had some other problems with it. It makes me forget that there might be stack costs associated, and that there might be cases where the recursion never ends.

I guess this is the reason I came up with the idea that the language should only allow tail recursions, since I at least do not need to worry about stack explosions. What is left is whether the compiler can detect cases where the recursion will never end?

I'll just close by

I'll just close by reiterating that I disagree with just about everything you've asserted here, and I've still seen no evidence for these claims. Perhaps your conclusions grew out of experience reviewing code written by people with more experience with imperative JVM languages, but I see no reason to generalize this as if it's representative of human cognition or programming in general, which is essentially what you're asserting.

About the only thing we seem to agree on in this thread is that Kotlin is a nice language, at least compared to what's generally available and supported for the JVM.

You might like Guy Steele's

You might like Guy Steele's presentation about replacing many kinds of loops map-reduce https://www.youtube.com/watch?v=ftcIcn8AmSY

Thanks for the link!

There were also some interesting things about parallelism.

Separate questions

I'm trying to wrap my head around the connection, if any, between the questions of general loops versus iterators, iteration versus recursion, and general recursion versus tail recursion.

The difference between general loops and iterators is an imperative-versus-declarative thing, I think? That is, a general loop is inherently sequence-oriented and can draw on the entire logic of the context in which decisions are to be made, while an iterator is parallelizable (if the language design chooses to go that way) and is more regulated in what it can draw on for its decisions. The iterators' constraints on what they can use for their decisions seems to me to be unique amongst all the constructs mentioned, in that both general iteration and both kinds of recursion would seem to draw on the full context for their decisions. The matter of serial/parallel (or is it imperative/declarative) seems quite left open by recursion; general iteration is the only one of these devices that takes a strong position on the matter (solidly in the imperative camp).

Encapsulation

Iterators, in concert with syntactic sugar in some languages, encapsulate the loop mechanics.

It's mainly a matter of taste.

Traditional loop constructs tend to require an L-Value (e.g. the CX register, or some variable named "i"), a starting value (e.g. 0), a test (e.g. the loop's stop point), and an increment size (e.g. add 1).

for (int i = 0; i < count; ++i) {
  Person person = people[i];
  // ...
}

Iterators look nicer:

for (Person person : people) {
  // ...
}

Imperative or Functional

My plan was to try to make it as functional as is practical, but I'm not sure if I'll be able to go all the way. This might have affected my impression that general loops are harder to reason about.

But since I'm an old time C programmer I can certify that loops has a tendency to be wrong, misleading or at least hard to understand. It can be hard to spot those infamous of by one errors. Coders also seem to like to do all kind of irrelevant things in the loop to save a few lines of code...

re: general loops/iterators, iteration/recursion, general/tail

I think you're onto something:

(1) [general loops vs iterators] general loops are .... general. But that also means that we cannot regulate and express the pattern of induction [chose that word on purpose] we actually mean. Using iteration combinators (and fold, map, etc) allow us to express the pattern more visibly, and that's good for program comprehension/correctness/debuggability. It also means we can get by with fewer/no imperative operations: again good for those things.

(2) [iteration vs. recursion] In _The Science of Programming_, Gries talks about invariants and convergence bounds. Using [tail] recursion makes these things more-explicit: instead of having to figure out which variables change during an iteration of a loop, we can see what the tail-call's arguments are, and match them up to the arguments of the function. Again, it makes something visible, that for the sake of correctness, we really want to know.

(3) [general vs. tail recursion] I think this simply boils down to whether you think stack-recursion is good or bad. That's it. We all know that you can convert between the two (Felleisen & Sabry taught us how).

I think I'll actually try

I think I'll actually try using those restrictions then, seems like it might work.

Loops

I just want iterators that give me a magic "i" variable. In the case of nested loops, a magic "j" variable. To override the variable name, just declare magic x.

I think that would solve most of my situations where I convert from a foreach loop to a for loop. The remaining problem is filling a buffer and doing bi-directional seeks, since that's not an iterator but a stream; in that regard cursors are more powerful than iterators and "iteratees" could potentially be structured to use extra memory to accomodate look-behind (but could create unbounded consumption - I am not sure if anyone has studied how to minimize allocations and do the look-behind lazily). An example use case is opening a file in read mode with share access, and the same file with a different handle in write mode with share access, and replacing strings.

I feel like this covers a huge array of problems that most Standard Libraries give the programmers way too many function calls to solve.

Another example on top of this is that boundary detection is often limited, so people often write imperative code to do boundary detection and manage their read buffer. A primitive to detect a pattern in a stream and use that as a boundary would be a great wait to delimit control flow.

I realize these are not really theoretical concepts, but I have often wondered why our standard libraries are so painful to use and don't concisely express what I want to say.

In this regard, I have found the terse q language for the kdb+ database to be spot on. I can imagine a less terse version of an array processing language that is as easy to write (with auto-code completion) and easier to read. I have not done much q / apl in a few years, and I can't remember all the idioms any more.

Your boundary detection

Your boundary detection sounds interesting. Could you give an example?

could you provide examples?

could you provide examples of how using the q language would make the tasks you describe easier/more-transparent? That would be interesting.

Calls and Returns

When I finally grokked that calls and returns are the same thing, I immediately started thinking about the implications of returning several results the same way most languages allow calls with several arguments, and return addresses overloaded by the type signature of the return, the same way many languages overload function calls.

So, if the function is returning an integer, the program counter goes to this address, and if it's returning a string, the program counter goes to that address. Sort of like a "goto" except with a call stack to provide context. Also the simplest possible implementation of "exceptions" as a separate type of return value.

Each call frame would determine a *set* of possible return addresses depending on what is eventually to be returned.

It's an interesting idea, and has expressive power roughly equal to scheme's call/cc. From time to time I've thought that a new programming language really ought to adopt it, with syntactic support, as a relatively simple approach that more coders could easily understand.

Anyway, this topic reminded me of it, because with overloaded calls and returns, the semantics of recursion are at the very least interesting. A tail recursion can always be represented as a loop, but the loop could wind up being very complex.

How would that work?

I don't really follow what you have in mind, but I'd be interested to.

multiple continuations

You can think of a normal continuation passing style as a singleton dictionary like `(return: (result -> k))`. Then a multi-continuation might have the form `(return: (result->k), exception: (ExceptionArgs->k), ...)`. Although the syntax might be expressed as returning vs. raising an exception, a transformation to CPS could model this as calling a choice of continuation functions.

The main benefit would be removing the 'magic' of stuff like exception handling. However, the practical benefit even for exceptions is relatively limited because, in practice, too many call frames will have stack unwind actions (e.g. C++ RAII, Haskell 'bracket').

I've tried to explore this idea for potential performance benefits, but I found that construction, maintenance, and communication of multiple continuations costs more than any gains achieved compared to simply returning a value then matching on it (and applying normal optimizations).

Er

Well, it seems that either you understand what feature is being described, or at least you think you understand... but I still don't think I understand. It sounds as if we're not talking about "multiple-value returns" here, but beyond that I'm just not getting it. :S


multi-continuation vs multi-value returns

Ray was not talking about "multiple-value returns". That's unrelated. He was speaking instead about providing a choice of continuations, i.e. a choice of multiple return addresses with different result types, pick one.

In his words, "Each call frame would determine a *set* of possible return addresses depending on what is eventually to be returned". Where he emphasizes 'set' I would emphasize the 'possible' and 'depending'. Instead of one 'return' continuation with no options, the function picks one continuation from a collection depending on the function's internal choice of results (e.g. integer, string, exception).

Aside: when thinking about this subject, I find it useful to understand 'the stack' in conventional PLs as a representation of the data needed for a program's continuation, albeit specialized for a singular 'return' continuation.

but...

Good, so we're solid on what this isn't. I'm not making sense of the words used to describe what it is. How about this:

the function picks one continuation from a collection depending on the function's internal choice of results (e.g. integer, string, exception).

This seems like the most specific description I've seen. I don't get it, but optimistically I suppose I might if I had (and understood) an example. You did try to give an example earlier, I think, but I didn't understand it. :S

(I'm really not trying to be obtuse, here; it seems I'm managing to be obtuse without trying.)

Continuation-passing syle

It sounds like continuation-passing style.

Sorry, I guess I wasn't clear.

You know the way C-descended languages use 'return(value)' to send 'value' back to the caller? The first part of what I was talking about is where 'return' takes multiple arguments and therefore the function returns a 'tuple' rather than a single value.

This is exactly the same way functions (in most languages) take a 'tuple' of arguments rather than a single argument, so I could call 'return(45,"Impeached Twice")' to return a tuple of two values.

The second part is folding up the classic 'call a function then explicitly check the return type' pattern from latent-typed languages with the same kind of type dispatch that many languages do on function calls, making it possible to do similar constructions in a language with strict type checking.

As I imagine it you'd declare 'return sites' at chosen points in the program,

(some language statement that says 'function foo may return to this place as though it had been called from here, if it returns a string+integer tuple' and says what to do with the values returned.)

and then when you actually call foo, (using some language statement having semantics like 'call function foo, and if foo returns an integer then continue from this site'.) the return would dispatch either to the same site if foo returned an integer, or to the closest frame in scope containing a matching return site for foo otherwise.

It would look first in the scope of the calling function itself, and then either to its dynamic scope (which could have implicit call-frame-stack-unwinding or or call-frame-tree-traversing semantics) or to the most closely enclosing type-matching return site. the lexical scope (which probably can't be done simply unless I have some inspiration when I spend more time thinking about it).

It doesn't really buy you the idea of 'freezing' a copy of the stack and returning to it later with an arbitrary function, which is the powerful and fundamental thing that call/cc does. But it does give you most of the things that call/cc actually gets used for.

Choice of continuations (example)

Hmm, a trivial pseudocode example might be something like this:


def divide(dividend, divisor, onOK, onErr):
  if 0 == divisor:
     (tailcall) onErr("divide by zero")
  else:
     (tailcall) onOK(dividend / divisor)

def divideOrZero(dividend, divisor, cc):
  (tailcall) divide(dividend, divisor, cc, lambda() => cc(0))

This example uses an explicit continuation-passing style, i.e. 'returns' are replaced by tail-calls to continuations. This relates to Ray's first sentence, "I finally grokked that calls and returns are the same thing" - returns are implicit continuation tail-calls.

The divide function clearly accepts "multiple continuations", where 'multiple' is just two - one for a valid result and another for divide-by-zero errors. But we could extend this, e.g. have a separate continuation for type errors.

..

To be clear, I'm not advocating this approach. I've experimented with this feature before and rejected it as impractical (compared to conventional approach: construct a variant return value then branch on it).

Even if continuations are represented by cheap compile-time constructs like 'return addresses' instead of lambdas, at least half would have a fate to be discarded unused. This is exacerbated considerably by stack-unwind operations (such as C++ RAII destructors or Java's try/finally) that would require all continuations share an unwind step, thus requiring a whole new set of continuations per frame.

CPS with multiple continuations is mostly useful as an intermediate representation for compiler optimizations (cf. Cogen in Six Lines), Church-encodings of programs or data (where the lambda argument is an interpreter), and other esoteric applications.

That's classic continuation passing. Good but not the same.

Explicit continuations like that are extremely powerful, and yes that's a very good syntax construction for them.

But I was looking for something that could work without passing around explicit continuations, because as you note they are expensive to construct and keep.

I wanted to encode the much simpler, easier-to-understand-but-not-as-powerful idea of an explicitly labeled 'return site' within whose scope a call to some function could return depending on its return types.

I think it would require that the function within whose scope the return site was found would, when returning, unwind the stack to the most recent frame where that function was called, possibly saving the unwound frames for inspection (in an error handler) or for building an explicit continuation (which I don't prefer). Otherwise the 'return site' would act very much as a goto label, but one that's restricted to being a target site for the return of some particular function and some definite tuple of types to be returned from that function.

explicit or implicit continuation passing

The explicit syntax is just to illustrate. Making them implicit won't significantly affect their cost. But greatly restricting expressiveness could reduce the cost. IIUC, you're speaking of some sort of mixed call-match control-flow structure like this:

foo(x) =>
  s : string -> return (len(s))
  i : int -> return (i + 42)
  (s,i) : (string,int) -> ...
  ...

Presumably, you would implicitly compile this call as something closer to `foo(x, dict{ onstr: addr1, onint: addr2, onsi: addr3, ... })`, using a potentially static dict pointer.

I think that the main benefit, in this case, is that you can avoid the semantics for boxing values of different types and constructing tuples for multi-type function returns.

The disadvantage is that this structure is relatively awkward to use by hand, and if expanded by compiler - e.g. `f(g(x),y) + h(z)` where f, g, h return `int | float` - will easily result in very large code.

maybe I've got it now

From all this discussion, looks to me as if it's adjacent to multiple-value returns. In the usual functional arrangement, calling specifies an operator and a tuple, and polymorphism allows selection of which function handles the call, while returning merely provides a single value. I maintained in the R-1RK (rationale of §4.9.1, $define!) that multiple-value returns are an illusion: a single value is passed into a function call, and a single value is returned; the value passed in can be parsed, in the Kernel dialect of Lisp, using a generalized definiend tree to distribute its parts into bindings in the local environment, while the value returned can likewise be parsed using a generalized definiend tree to distribute its parts into bindings in the dynamic environment. However Lisps usually, and Kernel particularly, don't do polymorphism. The proposal, if I'm finally grokking it, involves polymorphism in both directions.

This is about how to express things, after all. I'm not quite sure how it would work (and wouldn't be surprised to hear Ray isn't quite, either; one tries to push these sorts of ideas forward, and thereby learns what one didn't know before trying). When specifying a call, there's an operator that serves as a first-cut selector, and then a value (typically a tuple) for polymorphic refinement of the target of the call. When specifying a return, though, the value usually goes back to where the call came from, essentially a stack-based arrangement. Seemingly, where the call came from ought to have something to do with selecting a destination for the return, which would be an apparent asymmetry of return versus call; and it's not clear that there is any operator involved in the return.

A pseudocode example of what I had imagined....

Here's an example of what I was imagining, using a completely fictitious pseudocode to express a function that iterates a polyvalent function named 'foo' until a relevant condition is achieved.

And FWIW, John is right: this is all fairly woolly and I haven't taken it in detail. I just thought it could be relevant to a discussion about how to handle loops and recursions.


# univalent function takes 2 int args and has a single return type, int.

function fooloop (int arg1, int arg2)!int{ 
   #local variables and initialization
   int total = 0, string errmsg = '';

   repeat{
      #landing clauses are not executed unless foo returns to them.
      errmsg=landing(foo!string){
         # foo returns a string to signal an error.
         print(errmsg, stderr);
         halt(2);
       }

      addend,arg1,arg2 = landing(foo!int,int,int){
         # a 3-int return updates the args and sends a message to a monitor
         total += addend;
         updateBoard(arg1, arg2);
      }
      # function call and handling of 1-int return.
      # note that this has no effect on total unless foo returns to here.
      total += foo(arg1,arg2)!int;
   }
   until (arg1 == arg2);
   return(total);
}

Anyway, I was thinking of uses like this: de-cluttering the pattern of checking and dispatching on return types of polyvalent functions. And then thought, this also allows specifying types closely enough for full type checks, so there's more to it than that.

Each "landing clause" specifies an additional possible return address for foo when foo is called from this function, and the actual call restricts itself to handling one of the cases. But this means the whole thing can be statically type checked and compiled.

Fascinating

Ah! A variant on how the caller specifies how to handle what it gets back. An interesting variant. Invites tinkering.

Multi-valued variables would

Multi-valued variables would be fun. Might be a way of abstracting out concurrency by allowing the compiler to slice up the control flow however it sees fit.

loop constructs

If the language would prohibit generic loops and recursions except for tail recursions, would it still be useful as a generic programming language or would those restrictions make some common designs impossible?

If your PL can model a stack data type, then it's just as powerful under the constraint of tail recursion. Simply model a continuation stack as one of the recursion parameters (within each mutually recursive group that needs it). Defunctionalize as needed.

An explicit stack parameter and potential defunctionalization of the continuation is certainly less convenient to express than general recursion. But being explicit does have potential advantages. You certainly have much safer access to 'the stack' and more options to decide how to proceed with modeling exceptions, stack logging, etc..

However, if your PL has first-class functions, including function pointers or conventional 'objects', then it's very difficult to prevent general recursion even using static analysis. I doubt the idea is tenable in these conditions.

Tail recursions and first class functions

I would really like to have both... I haven't given it much thought, but would it be entirely impossible to solve this using the type system?

Both

You can easily have both first class functions and tail recursion. It's just difficult to also avoid general recursion.