Timeline for What are some possible "functional" memory structures?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2016 at 16:54 | history | tweeted | twitter.com/StackCompSci/status/774290007645425665 | ||
| Sep 9, 2016 at 16:33 | answer | added | chi | timeline score: 3 | |
| Sep 9, 2016 at 12:51 | history | migrated | from stackoverflow.com (revisions) | ||
| Aug 31, 2016 at 21:44 | comment | added | the8472 | "However, is there any storage element that can handle such thing directly?" - Time. Applying a function does not mutate in place, it mutates into the future while the past remains unchanged. Of course you will need a time machine to access past states, or absent that, make copies. | |
| Aug 31, 2016 at 4:38 | comment | added | Carl Dong | Yeah, Lambda Calculus seems much less "physical" than Turing Machine, Well, I agree CS stackexchange might be the place to go, though. Is it possible to move the question there? | |
| Aug 31, 2016 at 4:34 | comment | added | Bergi | Well, yes: a memory device with a built-in garbage collector is an implementation of a storage type on which you can run such functions in constant memory. I guess it would need a distinction between symbols (primitive values) and pointers (objects) in its interface as well as an entry point to the reference graph. I don't know whether such has been formalised in any computational model, though. You might get better answers at Computer Science on that. | |
| Aug 31, 2016 at 4:27 | comment | added | Carl Dong |
But what about functions that are supposed to run in constant memory? For example(in pseudo-Haskell, this sums 0 to n) fix $ \rec (n,acc) -> if (n == 0) then acc else rec (n-1, acc+n). I know in array-like memory, there either need to be a GC or mutation. However, is there any storage element that can handle such thing directly? (Well, the more I write about it the more I think it is impossible... But I might be limited by my knowledge)
|
|
| Aug 31, 2016 at 4:21 | comment | added | Bergi | There's no need to destroy them. We just will run out of memory eventually for some inputs, like on every physical device. A garbage collector is an implementation detail that helps to reduce the memory requirements. It will use mutation (unlike lamda expressions) and be written in assembly (or something that compiles to it). | |
| Aug 31, 2016 at 4:14 | comment | added | Carl Dong | I think GC is needed because Lambda Expressions never manage memory. At least, not the "array" like memory we generally have. In which case, we need to find a way to allocate objects as we evaluate an expression, and destroy them after evaluation. | |
| Aug 31, 2016 at 4:13 | comment | added | Carl Dong | For "device" I mean physical memory. And, forget about the Turing Machine I just mentioned. I use the term to contrast Lambda Calculus. Think about Assembly and Lambda Expressions instead. | |
| Aug 31, 2016 at 4:11 | comment | added | Bergi | What do you mean by "device"? Why do you think you need garbage collection? A turing machine has infinite memory. | |
| Aug 31, 2016 at 3:31 | history | asked | Carl Dong | CC BY-SA 3.0 |