5 ms·

> thinking about functions and how to compose them and solve problems with them, instead of going "I heard a noun, I need a class!" Are captured variables of a

> thinking about functions and how to compose them and solve problems with them, instead of going "I heard a noun, I need a class!" Are captured variables of a closures a 'noun' or a 'verb'? In the end they are equivalent, it's the same thing - state by another name. And recursions are no fun, when you run out of stack space.

ta8903 4y ago
>And recursions are no fun, when you run out of stack space. It's been a while since I read anything about this topic but they get optimized out by the compiler in most cases, right?
- MichaelMoser123 4y ago
  That is possible, if the recursion call is the last statement of the recursive function (tail call optimization). Now the recursion call is not always at the end of the function, so that this optimization does not always apply. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call Now Python doesn't do tail call optimization out of the box (surprise). but there is a module that is adding some magical decorator that fixes that: https://pypi.org/project/tail-recursive/ https://pypi.org/project/tail-recursive/ (actually need to look how they implement this decorator, it must be some serious hack.)
  - momentoftop 4y ago
    You can do tail call optimisation when the last thing you do before you return is a call. That tail call is not necessarily recursive, let alone a call to yourself. Whatever it is, its position means your current stack-frame can be reclaimed before you jump. If you can only optimise calls to yourself, you have a very limited form of tail call optimisation. It's an important point in the context of Scheme, where they made a big deal out of experimenting with continuation passing style. In CPS, all function calls are tail calls, and you want to optimise them all, even though most are not recursive.
- jcrites 4y ago
  You are probably thinking of tail-call optimization, which is when a recursive function returns the result of calling itself as its last action. These algorithms and functions are called tail-recursive. Compilers and interpreters can (more easily) optimize tail-recursive algorithms to avoid the normal cost of creating a new stack frame and making a normal function call, which means the recursive algorithm has performance more like that of an iterative implementation. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call https://llvm.org/docs/CodeGenerator.html#tail-call-optimization https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...
- KingMob 4y ago
  Not usually, no. Some languages support automatic tail-call optimization (when a recursive call is the returned value of a function, you can effectively replace the current stack with the recursively-called one), but in general, there are limits to how "sufficiently-advanced" real compilers are. Eliminating recursion might be difficult to detect if multiple functions form a mutually-recursive set, or if data structures have to be introduced to compensate for no stack (e.g., converting a depth-first search from recursive to iterative form requires a stack).
tlb 4y ago
Most dynamic languages including Scheme have unlimited recursion (limited only by total memory). Once you've gotten used to being able to use recursion, stack depth limits seem as lame as olden-days limits on string length (255 characters was common in Pascal). Javascript is a frustrating case where unlimited recursion is technically possible in modern engines, but they still often limit it to 10000 or something. Python limits it arbitrarily, just to force you to use its fancy iteration system.
- adenozine 4y ago
  It’s not quite arbitrarily. That’s an uncharitable definition. Python a) handles function arguments in a way that would make recursive functions awkward to use and b) cares about stacktraces being meaningful, so TCO would be a worse tradeoff towards that end as well. There’s trampolines in almost any programming language to implement recursion if necessary, and python has itertools to build what Scheme calls streams, for arbitrary computation.
- dragonwriter 4y ago
  > Python limits it arbitrarily, just to force you to use its fancy iteration system. Python has an arbitrary and low default limit because it isn’t optimized (because stack traces are considered important), abd call depth is an effifiency issue that risks blowing up without a limim because of stack depth, and failing fast in the likely-erroneous case of deep call stack given all that is just sensible. Python also. Lets you alter the limit at runtime; ita a soft, not hard, limit. The hard limit is stack space.
  - tlb 4y ago
    People often talk about accidental infinite recursion, but that seems like a rare mistake. I might have done it twice in a 40 year career? It's much rarer than an accidental infinite loop, which (almost) no language tries to protect you against. It doesn't seem worth giving up useful recursion. Python's "solution" requires changing a global, which is an ugly thing for a library that wants to recurse to do.
zelphirkalt 4y ago
While in the end captures variables and classes might be equivalent, captured variables seem low-fat while a class is usually instantiated (otherwise please use a struct, enum, record, namespace, ...) and comes with usually mutable members. Setting them in a non-mutating functional way would probably require to create a whole new instance of the class (object). Often a class is an overkill of a concept for something simpler hiding in it (like a record or struct) and too many people do not think about making things simpler once they typed the word class. A function on the other hand forces one to think of function calls and not some kind of state that was set earlier, splitting time in parts of before setting that state on an object and after. A function (when using the term more strictly) will always give the same result for the same input. I get more guarantees about my program than I get when classes and instances of them are mutated. Recursion can solve problems very elegantly at times. When I use it in other non-TCO languages, I always think about stack depth and consider externalizing the stack as an option. One thing mathematical, that I understood much better through SICP was hiw Church numerals work and how they could serve as numbers in theory. Another one was derivatives, since one writes a symbolic calculation of derivatives in SICP. Then the Newton method for finding zeroes. Basically any such topic, that one needs to implement in the exercises of SICP, because one has to get familiar with how it works more, in order to implement it.
- MichaelMoser123 4y ago
  Interesting perspective https://github.com/MoserMichael/jscriptparse https://github.com/MoserMichael/jscriptparse - this is my pet project, it's an educational / shell scripting language. It tries to allow for concise expression, and you have a REPL/shell. Ideally I want to fit this niche as well, where you can solve these problems in a concise manner (well, maybe slightly more concise than python or javascript, and with a subset of the features that you would expect with a programming language for grown ups) Here is the tutorial: https://github.com/MoserMichael/jscriptparse/blob/main/PYXTUT.md https://github.com/MoserMichael/jscriptparse/blob/main/PYXTU...
  - zelphirkalt 4y ago
    I like the "What I learned" section. Maybe I should steal that idea for my own projects, even if only for my future self and maybe to put in words any revelations I had during development. One could even think about putting all kinds of thoughts and conclusions into such a document or a separate section of the readme.

ta8903 4y ago

>And recursions are no fun, when you run out of stack space. It's been a while since I read anything about this topic but they get optimized out by the compiler in most cases, right?

MichaelMoser123 4y ago
That is possible, if the recursion call is the last statement of the recursive function (tail call optimization). Now the recursion call is not always at the end of the function, so that this optimization does not always apply. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call Now Python doesn't do tail call optimization out of the box (surprise). but there is a module that is adding some magical decorator that fixes that: https://pypi.org/project/tail-recursive/ https://pypi.org/project/tail-recursive/ (actually need to look how they implement this decorator, it must be some serious hack.)
- momentoftop 4y ago
  You can do tail call optimisation when the last thing you do before you return is a call. That tail call is not necessarily recursive, let alone a call to yourself. Whatever it is, its position means your current stack-frame can be reclaimed before you jump. If you can only optimise calls to yourself, you have a very limited form of tail call optimisation. It's an important point in the context of Scheme, where they made a big deal out of experimenting with continuation passing style. In CPS, all function calls are tail calls, and you want to optimise them all, even though most are not recursive.
jcrites 4y ago
You are probably thinking of tail-call optimization, which is when a recursive function returns the result of calling itself as its last action. These algorithms and functions are called tail-recursive. Compilers and interpreters can (more easily) optimize tail-recursive algorithms to avoid the normal cost of creating a new stack frame and making a normal function call, which means the recursive algorithm has performance more like that of an iterative implementation. https://en.wikipedia.org/wiki/Tail_call https://en.wikipedia.org/wiki/Tail_call https://llvm.org/docs/CodeGenerator.html#tail-call-optimization https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...
KingMob 4y ago
Not usually, no. Some languages support automatic tail-call optimization (when a recursive call is the returned value of a function, you can effectively replace the current stack with the recursively-called one), but in general, there are limits to how "sufficiently-advanced" real compilers are. Eliminating recursion might be difficult to detect if multiple functions form a mutually-recursive set, or if data structures have to be introduced to compensate for no stack (e.g., converting a depth-first search from recursive to iterative form requires a stack).

tlb 4y ago

Most dynamic languages including Scheme have unlimited recursion (limited only by total memory). Once you've gotten used to being able to use recursion, stack depth limits seem as lame as olden-days limits on string length (255 characters was common in Pascal). Javascript is a frustrating case where unlimited recursion is technically possible in modern engines, but they still often limit it to 10000 or something. Python limits it arbitrarily, just to force you to use its fancy iteration system.

adenozine 4y ago
It’s not quite arbitrarily. That’s an uncharitable definition. Python a) handles function arguments in a way that would make recursive functions awkward to use and b) cares about stacktraces being meaningful, so TCO would be a worse tradeoff towards that end as well. There’s trampolines in almost any programming language to implement recursion if necessary, and python has itertools to build what Scheme calls streams, for arbitrary computation.
dragonwriter 4y ago
> Python limits it arbitrarily, just to force you to use its fancy iteration system. Python has an arbitrary and low default limit because it isn’t optimized (because stack traces are considered important), abd call depth is an effifiency issue that risks blowing up without a limim because of stack depth, and failing fast in the likely-erroneous case of deep call stack given all that is just sensible. Python also. Lets you alter the limit at runtime; ita a soft, not hard, limit. The hard limit is stack space.
- tlb 4y ago
  People often talk about accidental infinite recursion, but that seems like a rare mistake. I might have done it twice in a 40 year career? It's much rarer than an accidental infinite loop, which (almost) no language tries to protect you against. It doesn't seem worth giving up useful recursion. Python's "solution" requires changing a global, which is an ugly thing for a library that wants to recurse to do.

zelphirkalt 4y ago

While in the end captures variables and classes might be equivalent, captured variables seem low-fat while a class is usually instantiated (otherwise please use a struct, enum, record, namespace, ...) and comes with usually mutable members. Setting them in a non-mutating functional way would probably require to create a whole new instance of the class (object). Often a class is an overkill of a concept for something simpler hiding in it (like a record or struct) and too many people do not think about making things simpler once they typed the word class. A function on the other hand forces one to think of function calls and not some kind of state that was set earlier, splitting time in parts of before setting that state on an object and after. A function (when using the term more strictly) will always give the same result for the same input. I get more guarantees about my program than I get when classes and instances of them are mutated. Recursion can solve problems very elegantly at times. When I use it in other non-TCO languages, I always think about stack depth and consider externalizing the stack as an option. One thing mathematical, that I understood much better through SICP was hiw Church numerals work and how they could serve as numbers in theory. Another one was derivatives, since one writes a symbolic calculation of derivatives in SICP. Then the Newton method for finding zeroes. Basically any such topic, that one needs to implement in the exercises of SICP, because one has to get familiar with how it works more, in order to implement it.

MichaelMoser123 4y ago
Interesting perspective https://github.com/MoserMichael/jscriptparse https://github.com/MoserMichael/jscriptparse - this is my pet project, it's an educational / shell scripting language. It tries to allow for concise expression, and you have a REPL/shell. Ideally I want to fit this niche as well, where you can solve these problems in a concise manner (well, maybe slightly more concise than python or javascript, and with a subset of the features that you would expect with a programming language for grown ups) Here is the tutorial: https://github.com/MoserMichael/jscriptparse/blob/main/PYXTUT.md https://github.com/MoserMichael/jscriptparse/blob/main/PYXTU...
- zelphirkalt 4y ago
  I like the "What I learned" section. Maybe I should steal that idea for my own projects, even if only for my future self and maybe to put in words any revelations I had during development. One could even think about putting all kinds of thoughts and conclusions into such a document or a separate section of the readme.