[HN Gopher] Bun, JavaScript, and TCO
___________________________________________________________________
Bun, JavaScript, and TCO
Author : tosh
Score : 124 points
Date : 2023-12-31 12:40 UTC (10 hours ago)
(HTM) web link (www.onsclom.net)
(TXT) w3m dump (www.onsclom.net)
| sbarre wrote:
| TCO in this article = Tail Call Optimization, not Total Cost of
| Ownership.
|
| It makes the article more interesting!
| gerikson wrote:
| It's also not Tjanstemannens Centralorganisation, the largest
| white collar union in Sweden, and also the org behind the TCO
| labelling of computer monitors.
| sbarre wrote:
| If you google TCO, at least where I am (North America),
| "Total Cost of Ownership" is the first result - and the
| dominant one on the first page of results.
|
| It's also the main definition of TCO that _most_ people are
| probably familiar with, me included.
|
| This felt like a reasonable clarification to make.
| smarx007 wrote:
| Actually, as a chiefly Java/C# person, I was hoping for the
| article to cover how Bun helps lower the Total Cost of
| Ownership of Javascript projects by helping to get off the
| hamster wheel of infinitely deep npm dependency trees, wild
| west of constant project deprecations and major version
| releases with immediate deprecation of previous versions, daily
| game of CVE alert whack-a-mole etc. Preferably, short of
| writing all the code yourself.
| sbarre wrote:
| I also assumed the other TCO when I clicked through, which
| would have been an interesting take to read for sure
| (particularly since Bun is so new, so I was wondering how
| much data would be backing this analysis), but I'm not a
| strong functional programmer so any time someone covers
| functional-adjacent topics, it's interesting to me!
|
| I'm with you on wanting to learn and explore more about Bun's
| main advantages though, the bundled tooling and some of the
| convenience APIs feel like well-planned
| time/effort/maintenance optimizations.
| midtake wrote:
| > [The tail call optimized] function is starting to look a lot
| like the orignal for loop solution. It's not very succinct or
| elegant anymore.
|
| (Brackets mine.)
|
| I don't know about succinct but I definitely like how it looks a
| lot more. It's very readable, while the ternary operator one
| looks illegible at that length. It looks shoehorned in. It's the
| programming language equivalent of trying to mumble a whole
| sentence in two syllables.
| k__ wrote:
| Yes, every language should have if-expressions. Don't know what
| they were thinking with the ternary operator.
| JonChesterfield wrote:
| One reason I've heard for the statement vs expression
| distinction, where one deliberately makes a mess of the
| syntax uniformity, is that it helps diagnostics of
| programming errors.
|
| That is, by demanding spurious restrictions on syntax and
| generally making code more annoying to write, you get to
| detect more constructs as probably bad.
|
| Line noise - semicolons in C, colons in python - is the same
| idea. Earlier diagnostics of code that probably wasn't
| intended.
|
| I don't find this remotely compelling as a language design
| choice but it's the best justification I've come across for
| why so many have the extra obfuscation between programmer and
| AST.
|
| Specifically, why would one optimise for ease of reading
| invalid code instead of for ease of reading valid code.
| Madness. But popular.
| recursive wrote:
| How are if-expressions different from the conditional
| operator? I thought one was a concrete implementation of the
| other.
| nsonha wrote:
| ternary is not the important part here, could write it with if
| and early return too.
| imjonse wrote:
| It's nice, but the downside is that relying on TCO can make your
| Bun-tested code unexpectedly break with stack overflow error if
| it ever gets run on Deno or Node. So probably a good idea to
| comment this part of the code and make sure if it's in a library
| to similarly warn the callers somehow.
| bryancoxwell wrote:
| Does serverside JS have anything similar to #ifdef?
| vlovich123 wrote:
| Yes. You can define a constant (eg IS_SERVER) which your
| bundler (eg esbuild) replaces with a specific value depending
| on what environment you're targeting. There are also ways to
| detect it using runtime globals that are only defined within
| the browser although that can be monkeypatched by your own
| code or 3p libraries you import (not common but could be a
| compat layer you add to make server side JS behave more like
| a browser).
| antipurist wrote:
| Something like if ('Bun' in globalThis) ...
| if ('Deno' in globalThis) ... if ('window' in
| globalThis) ...
|
| could be used to determine the runtime.
| timw4mail wrote:
| That certainly works for Bun and Deno, not sure about what
| is effective in Node, though.
| basil-rash wrote:
| Checking for process.versions.{node,bun} works, not sure
| if Deno has an equivalent.
| quickthrower2 wrote:
| Yes the O is more than an Optimisation, it is a change in
| semantics.
| pcl wrote:
| _> Recursion takes up precious memory on the call stack! There
| may be commands to increase the call stack size for your program,
| but there is only so much the OS will allow. Memory on the heap
| is much less restricted._
|
| This reasoning implies that tail call optimization is some sort
| of memory-segmentation workaround. This isn't accurate.
|
| A (non-TCO) recursive approach is more expensive because it uses
| O(n) bookkeeping memory, whereas the iterative approach uses O(1)
| memory. Naive recursion will allocate a stack frame for each
| "iteration", whereas the loop approach will not allocate anything
| per iteration.
|
| So, the iterative approach simply uses much less memory for large
| iteration counts; the placement of the memory in stack space or
| heap space isn't the relevant factor.
| fyrn_ wrote:
| But without TCO, even if your function doesn't have any state
| of it's own, it will use memory on the call stack. I don't
| think anything about what they said implied memory segmentation
| was the problem. It's pretty clear they mean each recusion
| increases the size of the call stack without TCO.
| rezonant wrote:
| Agreed, I think the mention of heap space was more to answer
| the question of someone new to this topic of "but wait, I can
| allocate gigabytes of data in an array, why can't I allocate
| 100,000 stack frames?"
| brabel wrote:
| The performance difference is not just about TCO, but about
| creating a new array on each iteration instead of reusing the old
| one... in Lisp, because it uses cons cells which share structure,
| appending is very efficient, so the recursive code runs as fast
| as it can get... not so much with JS arrays.
| pjmlp wrote:
| Even in Lisp, if performance matters there are other data
| structures.
|
| We are decades away when lists were the only option.
| brabel wrote:
| In the example in this blog post, I am quite certain plain
| LISP lists would still be the right choice today.
| odyssey7 wrote:
| ECMAScript continues to evolve and I suspect that there would
| have been an effort to make the spread operator into a sort of
| cons in JavaScript. It could have worked for both arrays and
| objects. However, after seeing that the entry-level bar of
| proper tail calls couldn't make it out the door for Chrome and
| V8, they might have decided not to push it and risk further
| divergence from a major implementation.
| JonChesterfield wrote:
| TCO should be table stakes. An interpreter can do it by noticing
| that the next thing is a call to itself (the interpreter), a
| compiler by reorganising the stack frame before the jump.
|
| Lots of stuff gets in the way. Destructors, varying type
| signatures, calling conventions. But for the case where it can
| happen, it should be considered an implementation error that it
| does not. Very like a space leak.
|
| edit: this ^ was evidently unclear - tail call support in an
| interpreter means recognising when the interpreter is about to
| call the interpreter and jumping there, e.g. in an eval-apply
| setup, you use one frame for the eval-apply-eval-apply skeleton
| and only spawn more for evaluation of function arguments.
|
| Tail call support in an compiler involves changing the calling
| convention to clean up before jump. At that point it's all jumps,
| whether back to the top of a loop or to some other basic block,
| because all the world is SSA to a pretty good approximation.
|
| Neither of those makes any meaningful distinction between calls-
| to-self, calls-to-sibling, calls-to-indirect and so forth. The
| TCO is easier on self calls idea comes from languages where it is
| hacked before the compiler backend in a setting where goto isn't
| allowed to cross function boundaries. Some C code will have a
| label at the top named "self" or similar and use `goto self;` to
| force the equivalent of a tail call, some compiler stacks
| implement TCO by a mechanical version of the same hack and thus
| can't deal with it crossing between different functions.
|
| edit2: If you're compiling to a target with restrictions on
| calling convention that preclude cleanup before jump (and doesn't
| sort this out itself) you are out of luck. Pick a better target
| or live in the doomed world you've created. See e.g.
| https://v8.dev/blog/wasm-tail-call for some stuff on wasm trying
| to fix itself, I haven't kept up to date with whether they did or
| not.
| anonymoushn wrote:
| TCO is broader than tail calls to the same function, but tail
| calls to the same function would certainly be a start.
| vitus wrote:
| TCO is about more than self-recursive calls -- you should be
| able to handle mutual recursion: f = x => x >
| 0 ? g(x - 1) : 0; g = x => x > 0 ? f(x - 1) : 0;
|
| (These functions don't do anything other than stress-test the
| stack, then return 0.)
|
| Note that if I changed this to, say, 1 + g(x - 1), this would
| no longer fall under the purview of tail recursion, where the
| last instruction before the return is a recursive call.
|
| The usual workaround I learned in my SICP days was to add a
| second variable for accumulating any results. And, indeed,
| that's how the blog post rewrites the recursive function.
|
| (The recursive one-liner is still wildly inefficient because JS
| doesn't implement arrays as linked lists, so the spread
| operator results in a copy for each recursive call, resulting
| in a quadratic solution. It could be made more efficient by
| using Array.prototype.push, but then it's no longer a pure
| function.)
| runarberg wrote:
| I don't think they picked the best example to showcase this,
| most JavaScript developers would write this simply as:
| Array.from({ length: n }, (_, i) => i + 1)
|
| But this example does get the point across, so I think it is
| fine. I do agree though, while reading it the inefficientness
| was screaming at me.
| leeoniya wrote:
| the reason TCO is not implemented in V8, iirc, is because of
| developer experience and needing devtools to faithfully dump the
| call stack that hasnt been flattened, because that's what's
| expected of js DX.
|
| does JSC's implementation solve this? do they exhaust the stack
| only when devtools are open, or smth? maybe they just keep the
| last 10 frames in memory for devtools? (that would make most
| sense to me)
| pjmlp wrote:
| This is a solved problem on programming languages where it is
| part of the specification, like Scheme.
|
| Basically the debugging info and what actually happens isn't
| 1:1, rather the logical model of the execution.
| twic wrote:
| What is the solution?
| pjmlp wrote:
| The debugger has metadata that allows faking the execution
| flow as if the frames haven't been erased, and how deep it
| happens to be, naturally only when active.
| anonymoushn wrote:
| This is a silly justification I think, in the sense that V8
| could implement this in a way that can provide stack traces for
| all stacks that are short enough for a human to browse while
| also executing programs that use tail calls as goto correctly.
| hajile wrote:
| Nobody cares that loops don't have stack frames. Few people
| cared for decades that async functions lost stack traces.
|
| It's just a bad excuse.
| MrJohz wrote:
| I think this article actually does a really good job of
| explaining why TCO hasn't really been an important part of the JS
| ecosystem.
|
| There's a lot of situations where recursive algorithms are really
| neat and clear. I don't know if this is the best example, but it
| shows the benefit of being able to split logic into a base case
| and a recurrence case.
|
| But, in my experience, an algorithm that elegantly fits a
| recursive relationship is rarely one that naturally fits the
| tail-call paradigm. Often part of the benefit of recursion is
| that you can store state in the stack - the very thing you need
| to avoid to use TCO.
|
| This means you often need to put in effort to create a tail
| recursive algorithm. But that often ends up looking a lot like
| the imperative case anyway - an accumulator outside the loop that
| you either mutate manually, or update in a tail call. And in my
| experience, the mutating, imperative version is usually then the
| easier to read and write (assuming you can keep mutations to a
| given scope, and not have that state leak all over the place).
| (In fairness, this might be more familiarity, though.)
|
| In the light of this, what is the advantage of TCO? In functional
| languages without mutation, it's pretty important to allow for
| functions to act on arbitrarily-sized inputs without constantly
| growing the stack. But if we have mutation, it's really just a
| different way of writing the same code. And if that different way
| is generally less clear and almost always less performant, it
| probably isn't a very useful choice.
|
| Which is why I think TCO hasn't really caught on in the other JS
| engines. It's a cool idea, and there's definitely a handful of
| cases where it's the useful way to go, but usually you'll be
| better served by writing things in the more traditional JS way.
| pjmlp wrote:
| Regardless, it has been approved as part of JavaScript
| specification and Chrome folks refuse for political reasons to
| implement it, which given the market domination everyone has
| helped them achieve is a bummer.
| MrJohz wrote:
| Firefox have also chosen not to implement it, right? Indeed,
| my impression was that Firefox were far more against the
| whole thing than Chrome, who did implement TCO but then
| removed it for various reasons.
|
| My impression is that this is less an issue with any
| particular implementor, and more with the feature not being
| fully thought through at the beginning. A lot of the browsers
| (including the Edge team at the time) ended up running into
| issues, on top of the UX/explanatory problems. That's why
| there was the alternative proposal for explicit tail calls,
| but those didn't go anywhere.
| pjmlp wrote:
| Firefox no longer matters, hence why I left it out.
| trashburger wrote:
| SpiderMonkey is still used in over 2% of the browser
| market share, and is used in non-Firefox applications
| too. I'd say it matters.
| ncruces wrote:
| 1. Complain about market dominance.
|
| 2. Any 2% of the market doesn't matter.
|
| 3. ...
| hajile wrote:
| They said it was too hard, but now they're adding it
| because of wasm, so their objection doesn't matter.
| tomashubelbauer wrote:
| I find it surprising that the JS specification also includes
| optimizations an engine should implement. I'm not sure how
| difficult TCO is to implement, but I just checked if QuickJS
| supports it or not and it seems to be one of the few ES2020
| omissions the author chose to make:
| https://bellard.org/quickjs/quickjs.pdf (3.1.1). This tells
| me it might be non-trivial to implement which if true makes
| the decision to make it a part of the specification all the
| more surprising, because that means the specification
| restricts the types of trade-offs implementers can make when
| attempting to achieve full compatibility. In other words,
| until today I was under the impression you could make a fully
| ES compatible engine, but choose to make it slow for
| implementation ease. Looks like the spec defines the floor
| for how (non)-performant the engine implementation can be in
| some cases. Is this common in other languages' specs?
|
| Edit: Oh, seeing the sibling comment, are TCO and "tail
| calls" different things? If so, I remain unclear on the
| status of TCO support in QuickJS.
| basil-rash wrote:
| Scheme (what JavaScript was based on) also requires tail
| call optimizations as part of its spec.
| mananaysiempre wrote:
| There's a bit of a naming confusion around tail calls, but
| in any case "proper tail calls", let's call them that, are
| not precisely an optimization: they are a _guarantee_ that
| any number of recursive calls of a certain kind will result
| in constant and not linear memory consumption. This permits
| some kinds of programming that can otherwise be quite
| awkward. If your program takes advantage of them (as e.g.
| often happens in Scheme), having tail calls is not an
| optimization issue, it's an implementation correctness
| issue.
|
| Now tail calls are quite annoying to implement _in C_ on
| top of a compiler that doesn't (and in fact I don't think
| any mainstream platform has a C ABI that would allow a C
| compiler to natively support them between functions of
| arbitrary types). That has always been a (solvable) issue
| for Scheme-to-C translators, and it was probably a
| consideration for QuickJS. Chrome's V8, though, is so far
| away from interpreting things in C or even translating them
| to C that I expect that any difficulties the developers
| have are of a completely different nature.
|
| (As an example, LuaJIT does support tail calls but kind of
| sucks at inferring hot loops written using them, so has
| really impressively draconian limits on how many you can
| have before the JIT aborts. They otherwise work, though, as
| is required for a valid Lua implementation.)
| MrJohz wrote:
| TCO isn't really an optimisation per se, at least in the
| sense that optimisations typically aren't observable as
| part of the semantics of a language. TCO does affect the
| semantics; it says that a recursive function that recurses
| only using tail calls will never overflow the call stack.
| That's why it's something that might get specified in the
| specification rather than just left as an implementation
| detail: it's the sort of implementation detail that
| developers might actually rely on.
|
| While in practice it probably improves the performance to
| have tail calls, theoretically, the spec isn't making a
| point about performance here, only semantics. It would, for
| example, be allowed to have a spec-compliant JS
| implementation that handled tail calls very slowly, as long
| as they are correctly don't increase the stack.
|
| As to why various implementations don't do TCO, my
| impression is that it's a combination of complexity and
| usability issues that have kept it from being implemented.
| And if some of the major browsers won't implement it, then
| I can see why other, smaller implementations don't see it
| as a priority.
| EE84M3i wrote:
| There's another consideration, you can introspect the
| stack using Error.stack (also Function.caller and
| friends?). It requires a spec change to say "it's okay to
| not not includes these stack frames in specific cases".
| This information would also presumably not show up in the
| devtools / debugger or sentry, etc.
|
| I personally more agree with not implementing it
| implicitly (although I think there was some discussion
| about having a special syntax) just because of the
| potential for confusion during debugging. E.g. if all
| tail calls are elided, then you could have stack frames
| that don't "make sense" (how did function A call function
| C? well, through function B but that frame is gone, and
| this could be really difficult in deep stacks).
| Alternatively, you could use a heuristic but that just
| raises even more questions.
| hajile wrote:
| This solvable enough by activating a shadow stack. You
| can also just note on the trace pretty cheaply that X
| function was called by a tail call function. This
| eliminates any ambiguity about what happened.
|
| It's not a different issue from async functions not
| having a stack trace and JS devs survived for decades
| without async traces just fine.
| spankalee wrote:
| What "political" reasons?
|
| My understanding of the situation is that it's entirely
| technical issues that came up after implementing.
| runarberg wrote:
| I think the most cited reason they give is diminished
| developer experience. That is when developers write a
| recursive function without intending it to be tail call
| optimized, they loose their call stack. In theory this
| makes debugging harder. However I don't--and others
| interested in JavaScript design--don't buy this reasoning.
| There is little--if any--data showing this happens to
| developers in real life.
|
| I also believe that Google's representatives at TC-39 (and
| Mozilla's to a lesser extent) knows this. Meaning they have
| other reasons for not implementing TCO. My personal theory
| is that they are very much against expending the functional
| paradigm in JavaScript. TC-39 has been very hostile towards
| any proposals which would expand the functional paradigm in
| JavaScript. The decision to advance the hack style pipeline
| operator (which uses a placeholder) over the F#
| (functional/tacit) operator is a prime example of this.
|
| This, I believe, is purely political.
| odyssey7 wrote:
| Sadly I sense something amuck against the functional
| paradigm as well.
|
| Paul Graham wrote back in 2001 that Lisp was a secret
| weapon for building a startup due to the developer
| productivity gains. https://paulgraham.com/avg.html
|
| As a corollary, the more lisp-like JavaScript is, the
| more it reduces barriers to entry for launching a tech
| company, promoting more software engineers into potential
| new competitors.
|
| Could it be that Java and Python are taught in
| universities because some members of the industry prefer
| making it more cumbersome for new grads to launch a
| company? Having significant barriers to entry is business
| strategy 101.
| jart wrote:
| Are you saying that knowing LISP makes you like an
| instant Paul Graham? If only.
| odyssey7 wrote:
| Nice try
| magicalist wrote:
| Yes, what's really important here is that TCO was added to
| the spec before the modern TC39 process was adopted. Had
| implementation and usage experience been required before it
| shipped in the spec, this conversation would have been
| concluded 9 years ago.
| hajile wrote:
| There were no technical arguments from Google. They
| implemented tail calls and performance was fine.
| Furthermore, wasm required them to add the functionality
| back to the jit.
|
| MS complained that windows APIs made it slow, but first,
| they should fix their OS. Second, chrome didn't have those
| same issues on windows. Third, they now use chrome, so it's
| no longer an objection.
|
| Firefox complained that it was work, but they're also doing
| it for wasm.
|
| This only leaves the stack trace argument, but the biggest
| cases for tail calls are where you'd already be forced to a
| loop and nobody complains that loops don't have stack
| traces.
|
| Further, you already have the same issues with async stack
| traces and activating shadow stacks in debug mode works
| just as well as those async traces.
|
| It's all about chrome devs digging in their heels because
| they took a side dumb argument and won't just swallow their
| pride and implement what developers want and the spec
| demands.
| Rapzid wrote:
| > Firefox complained that it was work
|
| LOL, as they do.
| odyssey7 wrote:
| I don't think the example is particularly good. TCO is
| essential in functional programming, where recursion shines,
| but the example given is an impure function which mutates its
| input parameter by calling Array.prototype.push. Basically,
| this isn't a demonstration of the paradigm for which TCO is
| required.
|
| We'll never know how big of a role TCO could have played in
| JavaScript over the past several years, because it hasn't been
| available outside of some narrow contexts.
| MrJohz wrote:
| I agree that TCO is essential in functional languages where
| loops and mutability are disallowed or at least heavily
| discouraged, but Javascript is not one of those languages. In
| Javascript, both mutation and and loops are very simple, and
| as I think the article demonstrates, often the clearest ways
| to express an idea.
|
| Where recursion is clearer (for example, when dealing with
| recursively nested data structures), the clearest expression
| of a function usually isn't tail recursive - that often
| requires rewriting the function to put more state into the
| function arguments.
|
| This means that tail recursion rarely matches with patterns
| used regularly in Javascript. That's not to say it's useless
| - if you want to keep to a particular functional style, or if
| you're compiling to Javascript from a language that
| emphasises recursion, then it's a useful tool to have. But in
| the former case, you're generally going to struggle with
| browser engines not being optimised for this style, and in
| the latest case, you're probably better off targeting WASM
| directly.
| odyssey7 wrote:
| I agree with everything you wrote.
|
| There's an element in this that gets at why V8's omission
| of TCO feels to me like suppression of functional
| programming. JavaScript is an incredible widely used multi-
| paradigm language, to the point that I would recommend for
| universities to replace Python and Java with JavaScript in
| their curriculums. It's just so practical for building
| software systems, has amazing tooling, connects you to a
| rich community, and allows you to cover so much academic
| ground. JavaScript has been a rocket fuel for promoting a
| vibrant, diverse software engineering ecosystem.
|
| Although you can choose to write a loop and do things
| imperatively in JavaScript, you don't have to. The
| ECMAScript spec is inclusive toward the functional
| programming paradigm by requiring that engines provide for
| proper tail calls. Functional programmers should be allowed
| to have their cake and eat it too! But TCO isn't
| implemented in V8, and the workaround is to just switch
| from functional to imperative programming.
| MrJohz wrote:
| I don't think it's the lack of TCO that's the thing
| holding JS back from getting the next great functional
| language. There's no structural pattern matching, there's
| no immutable data structures, there's nothing in the way
| of convenient syntax sugar like currying.
|
| You can mimic all of that, but it's painful, it's not
| something that Javascript is that great at. Which is fair
| enough, it doesn't need to be perfect at everything,
| that's why there's different languages. If you want
| functional programming in the browser, try using Elm or
| ReasonML. Both of those are fairly easy to use, I think
| there are even online playgrounds for both to get
| started.
| odyssey7 wrote:
| I think it's not as widely recognized as it could be just
| how forward-looking ECMAScript was in introducing
| language updates in the mid 2010s. For instance, arrow
| functions make it natural to work with partial
| application, a currying-adjacent technique.
| const times = a => b => a * b const double =
| times(2) const twiceFour = double(4)
|
| As a language feature, a function to curry a given
| function is different from proper tail calls in that it
| can be implemented as a JavaScript function rather than
| needing to be built into the JavaScript engine.
| Similarly, Haskell's own curry function is imported from
| its standard prelude. Leaving this detail up to language
| users allows a diversity of approaches and vibrancy in
| the community. Lodash has had an implementation for a
| while: https://github.com/lodash/lodash/blob/0843bd46ef80
| 5dd03c0c8d.... (Edit, found better example.)
|
| Structural pattern matching can be very elegant and it
| would be nice if ECMAScript offered it. Object
| destructuring has been added to the language, and that
| feature could be seen as a stepping stone for adding
| structural pattern matching in a later version. Proper
| tail calls however are more fundamental to the paradigm
| of functional programming, since they are necessary for
| iterative algorithms to work as well functionally as they
| do imperatively.
| Rapzid wrote:
| Shout out to F# in the browser via Fable too.
| miloandmilk wrote:
| I was looking for an alternative to rescript and
| literally just started looking at Fable this week - and
| absolutely love it in conjunction with Elmish.
| hajile wrote:
| TC39 hates FP.
|
| They have a stage 2 record/tuple proposal. Records are
| far more optimizable than JS classes since they enforce
| concrete types and can't add/remove fields.
|
| Instead, they spent massive amounts of time on private
| fields which most devs didn't want (most pushback any JS
| feature has ever received by a large margin) AND one that
| completely breaks proxies which are used by all kinds of
| libraries.
|
| Even Java is getting pattern matching before JS.
|
| They've decided pipe operators are either going to be an
| abomination or they will be cancelled entirely. So of
| this completely disregards the opinions and use cases of
| the FO devs that will be using them.
|
| This applies to all the FP proposals on their list. They
| get delayed, canceled, and neutered while niche or even
| bad features get implemented instead.
| o11c wrote:
| The real problem, of course, is that in the cases where
| compiler-based TCO is possible, the user can trivially
| refactor the function to use a loop.
| tikhonj wrote:
| Tail calls also matter for code in continuation-passing style
| (CPS).
|
| This matters for some styles of programming
| (callbacks/promises/monads/etc), but it's also very useful for
| code _emitted_ by compilers and DSLs. It 's much easier to
| encode complex control flow with CPS than just with the basic
| constructs JavaScript supports.
|
| Even for hand-written code it can be pretty important. It's
| easy to imagine rewriting simple tail-recursive functions in an
| imperative style, but it quickly gets _much_ harder, especially
| if your problem naturally decomposes into _mutually_ recursive
| functions: that is, instead of a function calling itself, you
| have multiple functions calling each other, often with a bunch
| of additional computation between each call. I 've run into
| this when writing parsers as well as custom algorithms for
| constraint-satisfaction kinds of problems. (Which are pretty
| common!)
| quickthrower2 wrote:
| Is it just me but I never use recursion in JS (or imperative
| languages generally) and it never really comes up as a need?
| jiehong wrote:
| We're using recursion at $company to validate user inputs
| because it's a user-defined tree of unknown depth.
| anonymoushn wrote:
| For example if you write a json deserializer that's generic
| over the struct you want to deserialize to (or one in JS that
| returns a JS object), you'll usually use some sort of
| recursion. My generic radix sort[0] also has recursion in it,
| which seems like the most straightforward way to write it, but
| of course any recursive function could be mechanically
| converted to one that does not use recursion.
|
| [0]:
| https://github.com/alichraghi/zort/blob/main/src/radix.zig#L...
| odyssey7 wrote:
| Nitpick: JS is multi-paradigm.
| quickthrower2 wrote:
| Yeah I should have been more specific. I mean languages where
| recursion is idiomatic for many problems because the language
| is purely functional like Haskell.
| kosolam wrote:
| This isn't a good thing if your fancy recursion code works great
| on bun but is slow in other js runtimes.
| anonymoushn wrote:
| Seems fine if you actually run it on bun.
| imjonse wrote:
| Related: Guido van Rossum's argument for why there is no TCO in
| Python.
|
| https://neopythonic.blogspot.com/2009/04/final-words-on-tail...
| Jarred wrote:
| (I work on Bun)
|
| A neat thing about tail calls in JavaScriptCore: there's an
| explicit bytecode intrinsic for it. return
| @tailCallForwardArguments(MyConstructor, this);
|
| To use this in Bun, you'd have to start Bun with the environment
| variable "BUN_JSC_useDollarVM=1" and then
| $vm.createBuiltin(mySourceCodeString)
|
| When using this intrinsic, if any of the arguments are incorrect
| or it cannot otherwise enable it, the entire process will
| probably crash. In debug builds of JSC it will have a nicer
| assertion failure but that is not enabled in release builds
|
| Example code:
| https://github.com/WebKit/WebKit/blob/17351231b4dedb62d81721...
|
| also happy to answer any questions about Bun
| CodeGroyper wrote:
| Love bun, thank you so much Mr. Sumner.
|
| What is the priority of app router integration for NextJS?
| johnfn wrote:
| > What is the priority of app router integration for NextJS?
|
| I'm not Jarred, but what do you mean by this? I'm using bun +
| app router + NextJS and everything seems to work just fine.
| atmin wrote:
| Not OP, but interested: can you deploy on a vps having only
| bun and not node?
| maxboone wrote:
| Yes
| reducesuffering wrote:
| I don't think you're talking about what GP comment is.
|
| For clarification, Bun can act as a package manager like
| npm (probably the case of "bun + app router + NextJS"
| comment), and it can act as a replacement to a node
| runtime a la Express on a VPS (I'm assuming this is what
| you mean by "yes"). But Bun currently does not implement
| enough of the Node API's to use Bun as the runtime for a
| Next.js app.
|
| From Bun themselves: "The Next.js App Router currently
| relies on Node.js APIs that Bun does not yet implement.
| The guide below uses Bun to initialize a project and
| install dependencies, but it uses Node.js to run the dev
| server."
|
| https://bun.sh/guides/ecosystem/nextjs
| CodeGroyper wrote:
| On https://bun.sh/guides/nextjs it says that bun currently
| does not implement the API to run the dev server.
| magic_man wrote:
| You can use a loop and a stack and can get recursion without
| adding all the overhead of a function call.
| refulgentis wrote:
| I spent the first year or two of my career thinking I needed to
| Do Recursion because thats what the textbooks said and hey, the
| language supports tail calls!
|
| I learned, in the sense you learn by touching a hot stove, that:
|
| A) you can't guarantee the compiler sees it as a tail call and
| optimizes it.
|
| B) you are now open to a stack overflow appearing in your
| software at any given point due to compiler changes / your own
| changes that confuse the compiler, etc.
|
| C) qed, don't do tail calls.
| kriiuuu wrote:
| Both Scala3 and Kotlin allow you to annotate functions with
| @tailrec which will give you a compiler warning if the compiler
| can't optimize. And if you use the xfatal-warn compiler flag
| the Scala code won't compile if your function is not tail call.
| FpUser wrote:
| >"I spent the first year or two of my career thinking I needed
| to Do Recursion because thats what the textbooks said"
|
| Being an old fart I've learned long ago to not follow self
| declared prophets. Recursion is a trade off that comes with the
| cost. Sometimes it makes sense to use it and sometimes (most of
| the times) it does not. You do what makes you and your
| customers happy.
| timw4mail wrote:
| Iterating over tree structures is a pain without recursion, but
| that's the only situation where I feel I _need_ recursion.
| chrismorgan wrote:
| This is not actually about Tail Call Optimisation, which is more
| flexible and optional matter of optimisation, but about Proper
| Tail Calls, which are a guarantee made in the ECMAScript 6
| specification (over implementer concerns objections)--in strict
| mode, calls in tail position _must not_ create additional stack
| frames. This is the last piece of ECMAScript 6 that most engines
| haven't implemented, because it's rather controversial: it
| actually _causes_ some performance problems, and makes debugging
| harder, and may have security issues (in 2016, Mozilla declared
| it impossible to implement across realm boundaries due to their
| security model).
|
| https://github.com/tc39/proposal-ptc-syntax has a lot of useful
| information about it all, and a proposal to make it explicit in
| syntax, such as with `return continue ...`, though I don't
| believe that's really gone anywhere. The practical situation is
| that this is the one part of the ECMAScript spec that most
| implementers ignore, and thus which you can't depend on. Which
| says to me that it should either be made optional or be removed
| from the spec. Not sure if there are any other features similarly
| disregarded. ECMAScript specification policy was different in
| those days, they operated more independently of implementers.
| (HTML was like that once too--that's roughly why WHATWG was
| formed, because the actual implementers weren't happy with how
| things worked in W3C, so they took matters into their own hands.)
|
| (Fun terminology problems here. The term TCO _is_ commonly used
| for PTC, and PTC is very close to being a subset of TCO, but the
| _mandatory_ stack frame elision which ruins debugging feels to me
| like it falls outside of TCO. In various situations, debuggers
| will mark things like "stack frame omitted" when they've
| optimised one out of existence, but you can generally compile
| things differently, or something like that, to prevent this.
| (Compiled /dynamic language variation showing up here.) But with
| PTC, it feels like the engine is kinda not even allowed to know
| that a stack frames may be absent. So I say PTC and TCO are a
| little distinct, though PTC is mostly just a subset of TCO.
| Reminds me of the terminology of tree-shaking versus dead code
| removal--where the former is essentially a subset of the latter,
| but that the effects are just _slightly_ different, though I'd
| say it's more slight in that case than this.)
| 65 wrote:
| So the optimization here is that instead of creating a new array
| every time you call the count function recursively, you're only
| modifying a single array. Thus the new array recursive function
| is significantly slower because we're storing all those arrays in
| memory when calling the count function recursively. Do I have
| that right?
| snissn wrote:
| I gave bun a test with react apps and found that it installs
| node_modules much much faster, but starting up a react dev server
| took the same time
| jart wrote:
| TCO is cool. I remember how enlightening it felt when I studied
| Scheme and came to understand how it's implemented there.
| mwkaufma wrote:
| Optimization and functional recursion is nice and all, but the
| unsung killer-feature of (mandatory) TCO is to (ab)use the stack
| as a state-machine. Each "state" is a function which tail-calls
| the next state, so it replaces the stack frame. Stack-traces now
| double as state-inspectors. Substates naturally follow from
| subroutines.
|
| I regularly use this in Lua gameplay scripting, which has proper
| tail-calls in the language spec, not just as an implementation-
| optional detail.
| koito17 wrote:
| > Languages that rely on recursion like LISPs often specify that
| TCO must be implemented in their language spec.
|
| This is inaccurate. As far as I can tell, it's only Scheme
| specifications like r5rs that have a hard requirement on tail-
| call optimization. The Common Lisp specification makes no mention
| of tail-call optimization, and Clojure -- arguably the most
| widely used Lisp today -- does not have it either (but it has
| special forms and macros that let you write recursive code and
| produce trampolines, thunks, etc. to avoid blowing up the stack).
|
| With that said, at least in the case of Common Lisp, it is true
| that many compilers will implement TCO, even though it is *not*
| required at all to conform to the specification.
| reactordev wrote:
| Not to be a dog in the fight but...
|
| How is: const count = (amount: number) =>
| (amount > 0 ? [...count(amount - 1), amount] : []);
|
| Succinct and better? It's fewer lines. It uses recursion. But
| it's obtuse and illegible syntax diarrhea that takes more time to
| grok.
|
| The for loop example above, while simple, is easily understood. A
| junior engineer could fix it. Is it faster? No. Is it easier to
| understand? Yes. I like the final example as well.
|
| Look, I'm all for being clever when cleverness is needed but some
| of you JS/TS folks take it to the extreme. I want to be able to
| read my codebase, not perform archaeological studies. I have the
| same issue with Rust syntax as well in places.
|
| I will praise the article on this though, optimizations do matter
| and having something execute orders faster will improve your
| overall experience. It doesn't have to be cuneiform. If you must
| be clever, wrap it in an abstraction that is well documented
| because you don't live forever and neither will your code, make
| it easy(ier) on the next person. While you can nest a recursive
| function in a tertiary statement coro, don't. Fire is cool but
| also burns.
|
| Btw, bun is _blazingly_ fast. I look forward to more.
| mhink wrote:
| > Look, I'm all for being clever when cleverness is needed but
| some of you JS/TS folks take it to the extreme.
|
| To be fair, this is very much a toy example meant to
| demonstrate tail recursion- although I do agree it's not a
| great example considering you need to understand the evaluation
| order of ternaries in order to understand why one version is
| tail-recursive and the other isn't.
|
| That being said: generally speaking, one might argue that using
| recursion at all is "too clever" and algorithms should just
| stick to iteration altogether. -\\_(tsu)_/-
|
| > While you can nest a recursive function in a tertiary
| statement coro, don't.
|
| Man, why do you gotta call me out like this? :D
___________________________________________________________________
(page generated 2023-12-31 23:00 UTC)