libera/#lisp - IRC Chatlog
Search
10:07:38
lisbeths
because you can implement balanced binary search trees in pure untyped unnamed lambda calculus, that shows that LC is capable of a good big O notation for general purpose algorithms
10:08:45
lisbeths
I wonder what work has been done in pure lambda calculus besides just church encoding
10:14:17
lisbeths
if youve got a large amount of contiguous memory to work with you can have a good big O notation
10:17:34
jackdaniel
you have "your own" big O notation, and define it by simulating memory with lambda calculus?
10:18:01
lisbeths
I can simulate lambda calculus in my head no disrespect I can do that thats just how I am
10:18:35
jackdaniel
and you can 'simulate' notation; that's why I claim that it is hard to take it seriously
10:19:28
lisbeths
When I say O notation what I am saying is that the graph of the worst case performance of an algorithm
10:21:27
moon-child
I'm not asking about what you don't mean, because what I'm asking about is what you _do_ mean
10:22:52
lisbeths
some that you can only see at runtime and some you can see before writing the code
10:24:41
lisbeths
actually thats not true anymore I got an associates of arts and sciences DTA and I tutored coding at everett communtity college
10:24:59
moon-child
ok, so there are specifications for _behaviour_. Not performance. How does that help us get log(m) without a cost model?
10:25:18
moon-child
(I'll add there is a legitimate way to get log(m) without a cost model, but it's not particularly useful)
10:28:04
lisbeths
the interpreter of an abstract untyped lambda calculus is an amgorithm. that interpreter is an algorithm
10:28:40
lisbeths
therefore anything that is programmed to run solely on SUULC will have some performance hits from doing so
10:30:12
moon-child
if I am clever enough, and my hardware is appropriate, my lambda calculus may make your damn tree-search constant time!
10:30:12
lisbeths
I could always be wrong and if you prove me wrong I will be very happy because that is an opportunity to improve
10:31:22
lisbeths
I would like to see a paper on how you think lambda calculus could be thus optimized that would be a nice read
10:32:23
moon-child
I don't have to produce such a paper. In fact, maybe I _can't_. If I were able to prove the opposite, that too would prove my point
10:32:54
moon-child
because it would be saying that, _WITH RESPECT TO SOME COST MODEL_, some tree search will always take a certain amount of time
10:34:01
lisbeths
my point is that the PUULC can abstractly perform at least as good as balanced binary search trees on a proper computer, and therefore it can simulate contiguous memory, and therefore it can simulate a turing machine that can achieve reasonable abstract performance albiet slower from being interpreted from the lambda calculus, and that guest machine can simulate an even slower guedt that also has good abstract performance and so on
10:34:43
lisbeths
when you are dealing with a totally abstract system you are not able to produce a cost model thats true
10:35:36
moon-child
in this 'abstract' land, where there is no cost model, there is no way to talk about performance
10:36:44
moon-child
maybe, the performance of a formal substitution is proportional to the number of people singing 'happy birthday' at the moment
10:37:08
moon-child
in abstract-land, you don't know. You have deliberately abstracted over such details, explicitly declaring that you do not care
10:37:43
moon-child
in a world where substitution had such performance characteristics, the performance of a binary tree search might be hlogm
10:38:40
lisbeths
it doenst make a huge difference if you solve a problem in o(n) or o(1 + n) or o(2n) even thats just like having a slower language
10:40:53
lisbeths
the jump from o(1) to o(log(n)) and the jump from o(log(n)) to o(n) are so much greater jumps than the jump from o(1) to o(99999) or the jump from o(n) to o(99999n)
10:43:50
lisbeths
we can say a machine that performs o(9999999999log(n)) has thr same abstract performance as o(log(n))
10:51:18
lisbeths
if you had to work on an abstract programming project like mine I think you would eventually be forced to think in the same way