[This is from a paper we’re submitting to the International Conference on Functional Programming (ICFP 2025)][update: the paper was rejected because we included our names, violating anonymity]

Introduction

Recursion and iteration are the Yin and Yang of programming. Conventional languages support both, but tend to favor the Yang – iteration. Java and C, for example, have elaborate while and/or for statements but can’t easily return functions as results. Python is a bit better. The Yin, we might say, is strong in that one. 

Even Python, however, still limits the use of functions. It does not allow partial application and has a very restricted lambda expression. Even in Python the positive Yang is dominant.

Iteration, however, has its problems. Even simple while loops can be hard to understand (let alone verify) because the state changes not just with every step of the iteration but with each execution of each assignment statement in the body.

The problems with iteration led to the invention of the pure functional languages in which there is no iteration. In these languages everything is done with recursion, and the closest we get to iteration is tail recursion. In a language like Haskell not only is the Yin dominant, the Yang is almost completely missing.

The pure functional languages have proved remarkably successful, Haskell in particular. Yin has proved capable of practical applications. But functional programmers often confess to missing iteration. To switch metaphors, recursion is “pure” and iteration is “impure,” but they long for impurity. Sometimes this longing is expressed in almost Freudian terms, opposing recursion, associated with Virtue, and iteration, associated with Vice. Supposedly Vice has an unhealthy attraction and tempts the poor programmer away from Virtue.

Can we resolve this and satisfy this longing without plunging programmers into the depths of Vice? We believe so. Our strategy is to take a pure (dark) Yin language and add a controlled, declarative form of iteration that sheds a bit of light. The functional language is PyFL, an experimental language being developed by the authors. We extended PyFL with the declarative while construct that provides a little illumination in the dark. The extension process was simple and straightforward and ought to be applicable to other functional languages. 

[technical sections omitted]

Yin and Yang Revisited

When we introduced the Yin and Yang metaphor we thought carefully about which to identify as which. Yin and Yang are not completely symmetrical; they have different connotations. Briefly, Yang is positive, bright, active whereas  Yin is negative, dark, passive.

Given that this is a functional programming conference our first choice was make recursion the positive Yang; but we changed our minds. Our machines are all iterative and it takes sophisticated engineering to make them support recursion and hierarchical data structures (e.g. nested lists). 

Of course this is necessary because there are plenty of applications, like parsing, that call for Yin -recursive algorithms and hierarchical data structures. But there are plenty more (e.g. numerical analysis) that naturally involve Yang – iterative algorithms and linear data structures (arrays).

One give away is the yearning phenomenon mentioned earlier. If recursion were bright and positive, why would its proponents long for the dark and negative? But if the recursive side is dark and negative it only makes sense that recursionists would long for Yang, for the bright and positive.

The evidence is that in terms of practical applications the positive Yang is dominant – the majority of problems are best solved with iterative algorithms and linear data structures.

Artificial Intelligence (AI) is a case in point. For many decades the standard approach (Good Old Fashioned AI, or GOFAI) was heavily Yin, relying on recursive algorithms and hierarchical data structures. The programming was done in Yin languages like Prolog.

But GOFAI was never very successful. The translations were laughably bad and only a massive effort produced a winning chess program. The Asian game Go (Baduk, Wei-Chi) with its massive 19×19 board completely defeated GOFAI.

Then along came neural networks and machine learning. The translations are excellent and Go was mastered in a few days. The computations are all linear algebra, arrays and iterative algorithms. Even the hardware (Nvidia chips) are iterative. A triumph for Yang.

The obvious question is, if Yin is so dark, why the enthusiasm for purely recursive languages (as evidenced by ICFP itself)? The answer is that bright Yang – iteration – has its own dark side, its own Yin. (Notice that in the traditional Yin/Yang image there is a white Yang spot within the dark Yin figure and vice versa. There is Yang within Yin and Yin within Yang). The presence of (side) effects (among other things) makes the programs hard to understand, verify, or modify. Yin, on the other hand, has its own corresponding bright Yang side, due mainly to the absence of side effects.

How do we escape these conflicts between Yins and Yangs? We’re proposing a compromise or synthesis: a Yin language with a strong positive side augmented with a little bit of Yang, with a limited negative side. We have shown that a little bit of Yang goes a long way.

[I’m adding these remarks, which are not in the paper]

These considerations shed light on the nature of the language Lucid. We used to argue that Lucid is a Yin language- a functional language – but that’s not the case. Lucid is strictly first order. My student Rondogiannis found a way to add some higher order functions and preserve the eductive implementation; but only for certain higher order types. In particular Rondogiannis’ approach can’t handle functions that return other functions as results.

The only conclusion to be drawn is that functions in Lucid are not first class objects and hence Lucid is not a functional language. With its emphasis on streams and indexing, it is a Yang – iterative – language.

In fact, in the development of Lucid indexing and eduction have priority. Features, such as higher order functions, that clash with eduction, are not pursued. The developers of GLU doubled down on the Yang and introduced arbitrary dimensions (and the pylucid interpreter now supports a space dimension). Lucid is a Yang language (a Yanguage?)

All this suggests that Lucid would be improved by adding a small amount of Yin, as PyFL was improved by adding a small amount of Yang. Which small amount?

One possibility is Rondogiannis’ (restricted) higher order functions, although that would be ambitious and would have to involve some kind of type declaration scheme. A tiny step in this direction would be limited second order functions, that take first order function parameters. This would take care of about 95% of the use of higher order functions in numerical analysis, where function parameters are common.