4 ms·

> As a result of these design choices there is always a single unique and canonical result for any Bosque program. This means that developers will never see int

> As a result of these design choices there is always a single unique and canonical result for any Bosque program. This means that developers will never see intermittent production failures or flaky unit-tests! So Bosque programs are not allowed to receive input from the outside world? > When an error occurs in deployed mode the runtime simply aborts, resets, and re-runs the execution in debug mode to compute the precise error! Again, no interaction with the outside world? Or are all inputs recorded during the entire execution? It doesn't seem like this could work as specified in many real-world scenarios... EDIT: > This compiles recursive functions into a CPS form that uses constant stack space, eliminating any possible Out-of-Stack issues So recursion cannot depend on input from the outside world? Either 1. I'm missing something, 2. Bosque programs indeed cannot receive input from the outside world, or 3. these claims seem a bit exaggerated...

dkersten 6y ago
> Again, no interaction with the outside world? Or are all inputs recorded during the entire execution? Inputs would need to be cached (eek, if there’s a lot of state loaded from external services or databases, or if that state is sensitive and you want to control where it may get persisted), but more importantly, output needs to be not output on the rerun (eg database writes and api calls). > So recursion cannot depend on input from the outside world? I’ve made a few mini languages (mostly for fun or for myself, but also external DSLs for end users) and I’m a big fan of not allowing unbounded loops. (Although bounded by a dynamic value like an input or the length of a runtime list is ok, so not quite the same thing as described here, it just needs to know the number of iterations before the loop begins) It makes it much easier, in my opinion, to prevent bugs, but of course it does mean you give up expressive power, so while it works for DSLs it’s not great for general purpose languages. I’m also a big fan of synchronous programming languages. I made one that basically runs inside a database transaction and reruns on conflict.
- wizeman 6y ago
  Sure, but they are not simply saying that they do not allow unbounded loops, that is what some languages do already, like Coq. They are saying that the compiled program "uses constant stack space, eliminating any possible out-of-stack issues". This seems impossible unless recursion cannot depend in any way on inputs from the outside world. Mind you, even if you have constant stack space that does not mean that you won't run into an out-of-stack issue. You can still run out of stack space if it is constant, because it might not fit in memory. It would probably be trivial to construct such a program. Furthermore, a program with constant stack space may even run out of stack space during execution (due to the kernel overcommitting memory, for example).
  - gliese1337 6y ago
    There is a difference between "running out of stack memory" and "running out of memory used to store stack-structured data". Any recursive algorithm can be mechanically transformed into an equivalent iterative algorithm that uses only a single activation record on the system call stack. If you perform that transformation on an entire program, then the total depth of the call stack is a static property of the call graph in the source code, and it does not depend in any way on run-time inputs from the outside world. The only way to run out of stack space then would be to write a program whose static, constant stack space requirements are indeed too large for the machine it is run on. Transformed algorithms may, of course, require "manually" tracking data in a stack structure, and use of such a data structure may indeed result of running out of memory depending on what inputs are provided, but that's just "running out of memory, which we happened to be using to hold a stack-like data structure", not "running out of stack".
    - wizeman 6y ago
      To me it just seems that you're arguing semantics... I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... So as far as I understand, there is no transformation that would make any recursive program use "constant stack space", unless of course, you just use some other memory to store what you'd store on your stack (but then again, that doesn't mean your stack has constant space, it just means that you're not using the default OS-provided stack space as a stack, and you're using other memory as a stack instead). Apart from that, as I said before, even if you had "constant stack space" it does not mean that you won't have out-of-stack issues.
timon999 6y ago
The Bosque paper says the following: > JavaScript took an interesting step by decoupling the core compute language in the JS specification from the IO and event loop which are provided by the host [...]. We take the same approach of decoupling the core compute language, BOSQUE, from the host runtime which is responsible for managing environmental interaction. So it seems that Bosque doesn't do IO directly, but instead specifies how a given input is mapped to some output.
- wizeman 6y ago
  From what you're quoting and from what you're saying, it seems that Bosque (the core compute language) can indeed receive input from the outside world, even though it comes from the runtime (which Bosque considers the outside world). Which means that some of the claims I quoted don't seem entirely accurate, and the other one only seems possible if the input (and possibly some state) is recorded...
kd0amg 6y ago
>> This compiles recursive functions into a CPS form that uses constant stack space, eliminating any possible Out-of-Stack issues > So recursion cannot depend on input from the outside world? Why would CPS prevent recursive code from doing I/O or using its results?

dkersten 6y ago

> Again, no interaction with the outside world? Or are all inputs recorded during the entire execution? Inputs would need to be cached (eek, if there’s a lot of state loaded from external services or databases, or if that state is sensitive and you want to control where it may get persisted), but more importantly, output needs to be not output on the rerun (eg database writes and api calls). > So recursion cannot depend on input from the outside world? I’ve made a few mini languages (mostly for fun or for myself, but also external DSLs for end users) and I’m a big fan of not allowing unbounded loops. (Although bounded by a dynamic value like an input or the length of a runtime list is ok, so not quite the same thing as described here, it just needs to know the number of iterations before the loop begins) It makes it much easier, in my opinion, to prevent bugs, but of course it does mean you give up expressive power, so while it works for DSLs it’s not great for general purpose languages. I’m also a big fan of synchronous programming languages. I made one that basically runs inside a database transaction and reruns on conflict.

wizeman 6y ago
Sure, but they are not simply saying that they do not allow unbounded loops, that is what some languages do already, like Coq. They are saying that the compiled program "uses constant stack space, eliminating any possible out-of-stack issues". This seems impossible unless recursion cannot depend in any way on inputs from the outside world. Mind you, even if you have constant stack space that does not mean that you won't run into an out-of-stack issue. You can still run out of stack space if it is constant, because it might not fit in memory. It would probably be trivial to construct such a program. Furthermore, a program with constant stack space may even run out of stack space during execution (due to the kernel overcommitting memory, for example).
- gliese1337 6y ago
  There is a difference between "running out of stack memory" and "running out of memory used to store stack-structured data". Any recursive algorithm can be mechanically transformed into an equivalent iterative algorithm that uses only a single activation record on the system call stack. If you perform that transformation on an entire program, then the total depth of the call stack is a static property of the call graph in the source code, and it does not depend in any way on run-time inputs from the outside world. The only way to run out of stack space then would be to write a program whose static, constant stack space requirements are indeed too large for the machine it is run on. Transformed algorithms may, of course, require "manually" tracking data in a stack structure, and use of such a data structure may indeed result of running out of memory depending on what inputs are provided, but that's just "running out of memory, which we happened to be using to hold a stack-like data structure", not "running out of stack".
  - wizeman 6y ago
    To me it just seems that you're arguing semantics... I mean, what is the difference between "stack memory" and "heap memory allocated to store the stack", other than the fact that the OS preallocates the first one for you by default? To me, "the stack" and "a stack-like data structure stored in the heap that is used as a stack to replace what would otherwise be the stack" is functionally the same thing... You know that (given appropriate conditions) you can just allocate stack frames wherever you want and point your stack pointer to whatever you want, whenever you want, right? This is what the Go compiler does to prevent Go programs from running out of the stack space provided by the OS by default. But AFAIK they don't advertise that Go programs use constant stack space and you don't have to worry about out-of-stack issues... So as far as I understand, there is no transformation that would make any recursive program use "constant stack space", unless of course, you just use some other memory to store what you'd store on your stack (but then again, that doesn't mean your stack has constant space, it just means that you're not using the default OS-provided stack space as a stack, and you're using other memory as a stack instead). Apart from that, as I said before, even if you had "constant stack space" it does not mean that you won't have out-of-stack issues.

timon999 6y ago

The Bosque paper says the following: > JavaScript took an interesting step by decoupling the core compute language in the JS specification from the IO and event loop which are provided by the host [...]. We take the same approach of decoupling the core compute language, BOSQUE, from the host runtime which is responsible for managing environmental interaction. So it seems that Bosque doesn't do IO directly, but instead specifies how a given input is mapped to some output.

wizeman 6y ago
From what you're quoting and from what you're saying, it seems that Bosque (the core compute language) can indeed receive input from the outside world, even though it comes from the runtime (which Bosque considers the outside world). Which means that some of the claims I quoted don't seem entirely accurate, and the other one only seems possible if the input (and possibly some state) is recorded...

kd0amg 6y ago

>> This compiles recursive functions into a CPS form that uses constant stack space, eliminating any possible Out-of-Stack issues > So recursion cannot depend on input from the outside world? Why would CPS prevent recursive code from doing I/O or using its results?