Timeline for λ -calculus : What is the most efficient in memory representation of functions?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2022 at 7:17 | answer | added | Bill Burdick | timeline score: 0 | |
| May 21, 2017 at 12:30 | vote | accept | Ford O. | ||
| May 12, 2017 at 21:40 | history | tweeted | twitter.com/StackCompSci/status/863146780397096960 | ||
| May 12, 2017 at 21:25 | answer | added | Joey Eremondi | timeline score: 12 | |
| May 12, 2017 at 20:26 | comment | added | D.W.♦ | Performance for what operation(s)? What do you want to do with the functions? Do you want to evaluate these functions on some value? Once, or evaluate the same function on many values? Do something else with them? Are you just asking how to compile a function (written in a functional language) so it can be executed as efficient as possible? | |
| May 12, 2017 at 19:44 | comment | added | Ford O. | @D.W. I am talking about performance / overhead. For example with efficient encoding mapping over church's list and Haskell's list should take the same time. | |
| May 12, 2017 at 19:41 | history | edited | Ford O. | CC BY-SA 3.0 |
added 189 characters in body
|
| May 12, 2017 at 14:57 | comment | added | chi | This is quite broad. There's plenty of abstract machines for lambda calculus which aim to execute it efficiently (see e.g. SECD, CAM, Krivine's, STG). On top of that, you need to consider Church/Scott encoded data, which poses more problems. E.g. in Church encoded lists, the tail operation has to be O(n) instead of O(1). I think I read somewhere that the existence of an encoding for lists in System F with O(1) head and tail operations was still an open issue. | |
| May 12, 2017 at 13:32 | comment | added | D.W.♦ | Can you edit the question to clarify what you mean by "efficient"? Efficient for what? When you are asking for an efficient data structure, you need to specify what operations you want to be able to perform on the data structure, as that affects the choice of data structure. Or do you mean that the encoding is as space-efficient as possible? | |
| May 12, 2017 at 7:36 | history | edited | Ford O. | CC BY-SA 3.0 |
edited title
|
| May 11, 2017 at 19:35 | history | edited | Ford O. | CC BY-SA 3.0 |
added 148 characters in body
|
| May 11, 2017 at 19:00 | comment | added | Ford O. | All my Google attempts failed, maybe I don't know the right keywords. | |
| May 11, 2017 at 18:59 | review | First posts | |||
| May 14, 2017 at 16:55 | |||||
| May 11, 2017 at 18:59 | history | asked | Ford O. | CC BY-SA 3.0 |