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?
-
Show this thread
-
About two years into Apple BASIC programming, I was befuddled by this. I only knew loops and not recursion, so I wanted to write an outer loop that maintained a variable number of inner loops, but that wasn't supported:pic.twitter.com/2z6FsTnB6d
3 replies 2 retweets 71 likesShow this thread -
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?
5 replies 1 retweet 54 likesShow 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.
4 replies 1 retweet 40 likesShow 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.
2 replies 1 retweet 43 likesShow 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.
1 reply 1 retweet 37 likesShow 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
3 replies 2 retweets 31 likesShow 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
6 replies 4 retweets 41 likesShow 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.
5 replies 0 retweets 35 likesShow this thread -
Replying to @TimSweeneyEpic
Bash brace expansion and printf let you do this in one line, but the intuition definitely doesn't come as naturally :P Echo and evaluate something like $(printf "%s" '{x..y}'{(n commas)} ) and you're good.
1 reply 0 retweets 0 likes
Ah yes, and regular expressions provide a miniature functional logic language themselves!
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.