Here's a neat test of programming language expressiveness: Can you write a function PrintXY taking an integer n>=0 that prints all strings of length n containing only the characters 'X' and 'Y'? Can you do it without recursion, and without assuming n<=64? Is it readable?
-
-
Because BASIC supported GOSUB recursion only, without a parameter stack, I eventually abandoned it in frustration and wrote a compiler for a Pascal style language. The recursive solution is easy, but the question still stands: why are for-loops too weak to express this?
Show this thread -
A Haskell programmer will use some higher-order library functions to build a list comprehension over a variable number of permutations, but that's tricky and just moves the recursion to a library function.
Show this thread -
There's actually a deep answer to this: looping over just mutable loop variables isn't very powerful. A set of n simple nested loops of k iterations each can only explore k^n possibilities, and n must be static. We can't handle n being a variable.
Show this thread -
This is another area where the functional logic language family is more powerful. There, we can loop over multi-valued choices (like little forks whose scope is limited to the enclosing loop) and gather all of their results in sequence through backtracking.
Show this thread -
Here, let "a..b" represent the choice of all values in the range from a to b, and "for(a) do b" loop over all choices in a, producing an array containing the values of b. Then we can write a simple loop like:pic.twitter.com/yVYAUSLSR3
Show this thread -
New expressive power comes from our ability to nest choices inside of loops, where each iteration explores all choices. Then we can variably "exponentiate", and write PrintXY as:pic.twitter.com/loFkBD2RaC
Show this thread -
Is this a quirky, special-case language feature? Definitely not; it has well-defined semantics and increases the expressive power of loops. And it's what 14-year-old me intuitively tried to do in Apple BASIC.
Show this thread -
There are many interesting solutions in this thread. The C and JavaScript solutions seen akin to mechanical devices that crank out solutions. One is an astonishingly short Haskell composition of library functions:https://twitter.com/tikhonjelvis/status/1265453175219183616?s=20 …
Show this thread -
There is generally a barrier to reading these solutions. In one case you have to run through the behavior of imperative code in your head to understand what it does. In another you have to understand the near magical incantation of pointfree function compositions.
Show this thread -
The more a solution can resemble a simple recitation of the problem to be solved, and rely on the compiler to generate the code, the better for ease of reading and writing code.
Show this thread
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.