[qsort]

This is an interesting approach (and also raises interesting questions concerning the relative power of languages, i.e. how adding various features relates to moving from binary logic -> regular languages -> ... -> turing complete, but I'm overthinking it...), but isn't it a tad too limiting? You at least need recursion to do anything that isn't completely trivial in Scheme, even for a CS 101 course. Wouldn't you outgrow them so quickly that you'd end up with "just Scheme, but more annoying" within a couple lessons?

[TheAsprngHacker]

You can have recursion right from Beginning Student Language (which lets you define top-level functions and call them recursively). Structural is taught early, together with lists. Structural recursion is explained together with recursive data: To unpack the data (any data, not just recursive), unpack the inner members, and therefore the structure of the program follows the structure of the data.

As someone who is taking the accelerated version of this course right now, but had prior functional programming experience, I did feel limited at first. Some other people responded negatively to the student languages because they weren't "mainstream."

As for the expressive power of languages, as a matter of fact, Felleisen wrote a paper that rigorously defines this idea. Here is a talk by Shriram Krishnamurthi that discusses it: https://pwlconf.org/2019/shriram-krishnamurthi/ It turns out that local transformations (macros) do not add expressive power. A language feature adds expressive power if you can find two programs that are observationally equivalent in the base language, but not the extended language.

[jj8]

It might feel limited for students with prior programming experience. However, my first programming course (in high-school) used BSL & co, taught from “How To Design Prgrams” (1), and it didn’t feel restrictive. Having to manually recurse, construct lists, &c. made clear exactly what later abstractions and syntactic sugar did. Rather than feeling that my hands had been tied before being introduced to, for example, higher order function, I felt I’d been granted superpowers once i had: nearly every function we’d previously struggled to write could now be written in one or two lines, and we even understood fully what those lines meant! Admittedly, this excitement was that of an absolute beginner.

(1) https://docs.racket-lang.org/htdp-langs/index.html