4 ms·

While I agree with the author that there's something about Rust (my day-job lang & goto personal lang these days) that just lacks... elegance... I've also never

While I agree with the author that there's something about Rust (my day-job lang & goto personal lang these days) that just lacks... elegance... I've also never found the Lisp (and many other FPs) emphasis on recursion all that compelling. Aesthetically or computationally. I find the programs written this way hard to reason about and read. Personally. For me, the underutilized gold mine feels like logic languages (Prolog et al.) Though I know recursion is used there a lot, too.

epgui 3y ago
It’s like anything else, you get used to it just as easily.
- cmrdporcupine 3y ago
  I take it as: mathematicians like recursion, so they put some recursion in your recursion...
  - epgui 3y ago
    There's a strong argument to be made that mathematicians tend to build the simplest abstractions conceptually, especially in comparison to computer scientists. Personally, when I stumble upon some maths, I pay close attention. It has paid off.
- whartung 3y ago
  ...or don't use it. Scheme likes to tout it because of tail call optimization. Common Lisp can do it, but doesn't really shove it as a first principle of "Common Lisping" (and CL does not dictate tail call optimization). I don't use it (save when it's necessary). I just iterate using the supplied iterators (do, dolist, loop, whatever). I can't speak to other functional languages.
  - ska 3y ago
    CL's iteration primitives are more capable that those provided by most languages, which often makes for a very clean approach. Recursion is sometimes the easiest way to reason about a problem though, so it's nice to have decent support and TCO.
    - epgui 3y ago
      > Recursion is sometimes the easiest way to reason about a problem though Yes, it's one of the things that allow FP algorithms to be more declarative. It's difficult to seriously argue that recursion is fundamentally more complex-- the contrary argument is more obvious to me. Everything that's left is the fact that it requires people to unlearn things, which is uncomfortable and requires effort, but unfamiliarity is not an indicator of complexity.
thuuuomas 3y ago
Have you checked out any of the minikanren logic programming environments people have implemented in scheme? The Reasoned Schemer is an accessible introduction to that space if you’re not put off by the socratic-themed dialogue. & the Barliman demo is still pretty exciting even after LLM codegen. https://youtu.be/er_lLvkklsk https://youtu.be/er_lLvkklsk
- nerdponx 3y ago
  I'd like to see a practical use case for Minikanren other than quines. It's fun and interesting, but I'm not smart enough to go from "a tiny set of primitives" to "solving practical problems". I had trouble even implementing the basic "moses is a man" examples you see in Prolog tutorials.
  - cmrdporcupine 3y ago
    Yeah me too I was just looking at an Elisp port (!) of minikanren the other day, and, yeah, all the examples were algorithmic puzzles, rather than solutions to problems.
  - tmtvl 3y ago
    MiniKanren has been used in the medical world: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9562701/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9562701/
- erichocean 3y ago
  It's also available in Clojure: https://github.com/clojure/core.logic https://github.com/clojure/core.logic If you want to write one yourself, it's pretty easy: https://www.youtube.com/watch?v=y1bVJOAfhKY https://www.youtube.com/watch?v=y1bVJOAfhKY
pfdietz 3y ago
I don't think Common Lisp has an emphasis on recursion. As evidence, consider that it doesn't in the standard require any kind of tail recursion optimization and has multiple ways of doing iteration. Scheme is the language with the fetish about doing things with recursion.
- cmrdporcupine 3y ago
  That's fair. Any time I've decided to spend time in the sexpr-world, I've gone straight to the hard stuff, into Scheme. Apart from Elisp, anyways. I've never worked in the source tree of a large Common Lisp program. Though I've bought the books and read the tutorials etc.
- ctrw 3y ago
  Common lisp let's you do recursion when you need it and not when you don't. Using recursion for iterating through a list is stupid because you bury the lead in the middle of a function and you do the same thing until you stop. Using recursion for a tree or more connected graphs isn't because they are fundamentally recursive.
  - xdavidliu 3y ago
    you can argue that lists are fundamentally recursive too: they are a car and and cdr, where the cdr itself is another list.
    - cmrdporcupine 3y ago
      This is actually the core of what I was getting at. The way Lisp lists are constructed and processed actually encourages recursive methods. But, again, it's probably because I've been exposed to too much Scheme that this sits so prominently in my mind. I've never worked in a large scale Common Lisp code base.
      - pfdietz 3y ago
        Not really. You don't want to recurse down the tail of a list, as in practice that's a great way to overflow the stack. In practice, you want to recurse only on the elements of a list. And that's just how you'd handle a tree whose nodes are vectors instead of lists. So the implication that lists lead to recursion is a red herring. Scheme is misleading because of its fetish of implementing iteration with tail calls.
mrkeen 3y ago
> I've also never found the Lisp (and many other FPs) emphasis on recursion all that compelling. Recursion appeals to me because of immutability: I do not want to do a summation by writing the wrong answer to memory, and then updating it in-place until it's the right answer. It makes me have to think not only about what the right answer is, but when it is. But can't I just use stack variables? Well, I don't think summation of primitive ints using stack variables is too taxing, but what about computing a word-count instead of a summation? Then your 'stack variables' are pointers into Strings and mutable HashMaps. When you return the result, do you make a defensive copy? How deeply do you copy? Your clone of a HashMap can still reference mutable data in your original HashMap. Do you name your variable 'result' when it does not yet contain the result? You might have to think about the primitive/object split - when is it pass-by-value and when is it pass-by-pointer? Do you have in-values and out-values? With immutability, you only have values, and you only pass-by-value. If you're sharing objects across threads, and you decide to lock - is that sufficient? What if the caller takes the lock, does a get(), releases the lock, and then starts mutating the gotten value, bypassing the protection of the lock. Now you're thinking about defensive copies and maybe deadlocks too. Just share an immutable value without a lock. Sometimes recursion is aesthetically better, but usually it's just what you're left with after you take a big hammer to mutability and its surrounding issues. And most of the time (in Haskell but I'm guessing in Lisps too) you don't write out direct recursions, but instead use maps and folds which have recursion under the hood.
- galaxyLogic 3y ago
  I think mutable variables (inside functions) are just fine, as long as the function itself always returns the same result for the same arguments. That is the essence of "pure" I think. A function should be a "black box". I don't care what happens inside it as long its externally observable behavior is pure.
- cmrdporcupine 3y ago
  Here's what I don't like about recursion & associated world of linked lists car/cdr: Modern Computing Hardware performance characteristics. That is, missed branch predictions, and lost opportunity to apply SIMD/vector operations. On "classical" computing hardware, it's fine. On present-day architectures we're better off writing with "wider" operations across vectors rather than depth-first-ish recursive operations on scalars. But yes, for some domains, the performance doesn't matter. I just also find recursion more difficult to read in some contexts. In others, things like tree transformation etc. it's easier to read, for sure. But I am also a fan of immutable, or at least copy-on-write, data, expressed in series of functional applications, etc. etc.
colingw 3y ago
Manual recursion often isn't needed. You can get basically all of what you want from Transducers: https://github.com/fosskers/cl-transducers https://github.com/fosskers/cl-transducers

epgui 3y ago

It’s like anything else, you get used to it just as easily.

cmrdporcupine 3y ago
I take it as: mathematicians like recursion, so they put some recursion in your recursion...
- epgui 3y ago
  There's a strong argument to be made that mathematicians tend to build the simplest abstractions conceptually, especially in comparison to computer scientists. Personally, when I stumble upon some maths, I pay close attention. It has paid off.
whartung 3y ago
...or don't use it. Scheme likes to tout it because of tail call optimization. Common Lisp can do it, but doesn't really shove it as a first principle of "Common Lisping" (and CL does not dictate tail call optimization). I don't use it (save when it's necessary). I just iterate using the supplied iterators (do, dolist, loop, whatever). I can't speak to other functional languages.
- ska 3y ago
  CL's iteration primitives are more capable that those provided by most languages, which often makes for a very clean approach. Recursion is sometimes the easiest way to reason about a problem though, so it's nice to have decent support and TCO.
  - epgui 3y ago
    > Recursion is sometimes the easiest way to reason about a problem though Yes, it's one of the things that allow FP algorithms to be more declarative. It's difficult to seriously argue that recursion is fundamentally more complex-- the contrary argument is more obvious to me. Everything that's left is the fact that it requires people to unlearn things, which is uncomfortable and requires effort, but unfamiliarity is not an indicator of complexity.

thuuuomas 3y ago

Have you checked out any of the minikanren logic programming environments people have implemented in scheme? The Reasoned Schemer is an accessible introduction to that space if you’re not put off by the socratic-themed dialogue. & the Barliman demo is still pretty exciting even after LLM codegen. https://youtu.be/er_lLvkklsk https://youtu.be/er_lLvkklsk

nerdponx 3y ago
I'd like to see a practical use case for Minikanren other than quines. It's fun and interesting, but I'm not smart enough to go from "a tiny set of primitives" to "solving practical problems". I had trouble even implementing the basic "moses is a man" examples you see in Prolog tutorials.
- cmrdporcupine 3y ago
  Yeah me too I was just looking at an Elisp port (!) of minikanren the other day, and, yeah, all the examples were algorithmic puzzles, rather than solutions to problems.
- tmtvl 3y ago
  MiniKanren has been used in the medical world: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9562701/ https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9562701/
erichocean 3y ago
It's also available in Clojure: https://github.com/clojure/core.logic https://github.com/clojure/core.logic If you want to write one yourself, it's pretty easy: https://www.youtube.com/watch?v=y1bVJOAfhKY https://www.youtube.com/watch?v=y1bVJOAfhKY

pfdietz 3y ago

I don't think Common Lisp has an emphasis on recursion. As evidence, consider that it doesn't in the standard require any kind of tail recursion optimization and has multiple ways of doing iteration. Scheme is the language with the fetish about doing things with recursion.

cmrdporcupine 3y ago
That's fair. Any time I've decided to spend time in the sexpr-world, I've gone straight to the hard stuff, into Scheme. Apart from Elisp, anyways. I've never worked in the source tree of a large Common Lisp program. Though I've bought the books and read the tutorials etc.
ctrw 3y ago
Common lisp let's you do recursion when you need it and not when you don't. Using recursion for iterating through a list is stupid because you bury the lead in the middle of a function and you do the same thing until you stop. Using recursion for a tree or more connected graphs isn't because they are fundamentally recursive.
- xdavidliu 3y ago
  you can argue that lists are fundamentally recursive too: they are a car and and cdr, where the cdr itself is another list.
  - cmrdporcupine 3y ago
    This is actually the core of what I was getting at. The way Lisp lists are constructed and processed actually encourages recursive methods. But, again, it's probably because I've been exposed to too much Scheme that this sits so prominently in my mind. I've never worked in a large scale Common Lisp code base.
    - pfdietz 3y ago
      Not really. You don't want to recurse down the tail of a list, as in practice that's a great way to overflow the stack. In practice, you want to recurse only on the elements of a list. And that's just how you'd handle a tree whose nodes are vectors instead of lists. So the implication that lists lead to recursion is a red herring. Scheme is misleading because of its fetish of implementing iteration with tail calls.

mrkeen 3y ago

> I've also never found the Lisp (and many other FPs) emphasis on recursion all that compelling. Recursion appeals to me because of immutability: I do not want to do a summation by writing the wrong answer to memory, and then updating it in-place until it's the right answer. It makes me have to think not only about what the right answer is, but when it is. But can't I just use stack variables? Well, I don't think summation of primitive ints using stack variables is too taxing, but what about computing a word-count instead of a summation? Then your 'stack variables' are pointers into Strings and mutable HashMaps. When you return the result, do you make a defensive copy? How deeply do you copy? Your clone of a HashMap can still reference mutable data in your original HashMap. Do you name your variable 'result' when it does not yet contain the result? You might have to think about the primitive/object split - when is it pass-by-value and when is it pass-by-pointer? Do you have in-values and out-values? With immutability, you only have values, and you only pass-by-value. If you're sharing objects across threads, and you decide to lock - is that sufficient? What if the caller takes the lock, does a get(), releases the lock, and then starts mutating the gotten value, bypassing the protection of the lock. Now you're thinking about defensive copies and maybe deadlocks too. Just share an immutable value without a lock. Sometimes recursion is aesthetically better, but usually it's just what you're left with after you take a big hammer to mutability and its surrounding issues. And most of the time (in Haskell but I'm guessing in Lisps too) you don't write out direct recursions, but instead use maps and folds which have recursion under the hood.

galaxyLogic 3y ago
I think mutable variables (inside functions) are just fine, as long as the function itself always returns the same result for the same arguments. That is the essence of "pure" I think. A function should be a "black box". I don't care what happens inside it as long its externally observable behavior is pure.
cmrdporcupine 3y ago
Here's what I don't like about recursion & associated world of linked lists car/cdr: Modern Computing Hardware performance characteristics. That is, missed branch predictions, and lost opportunity to apply SIMD/vector operations. On "classical" computing hardware, it's fine. On present-day architectures we're better off writing with "wider" operations across vectors rather than depth-first-ish recursive operations on scalars. But yes, for some domains, the performance doesn't matter. I just also find recursion more difficult to read in some contexts. In others, things like tree transformation etc. it's easier to read, for sure. But I am also a fan of immutable, or at least copy-on-write, data, expressed in series of functional applications, etc. etc.

colingw 3y ago

Manual recursion often isn't needed. You can get basically all of what you want from Transducers: https://github.com/fosskers/cl-transducers https://github.com/fosskers/cl-transducers