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
10:59:42
pjb
lisbeths: only if your machine is a universal turing machine, and only if your problem size grows to the infinity!
11:00:41
pjb
with actual finite machines, in actual finite universe, you better use O(n) over O(9999999999log(n))
11:04:42
lisbeths
3:59 AM <pjb> lisbeths: only if your machine is a universal turing machine, and only if your problem size grows to the infinity! -- as computers double in feature count each 2 years they approach infinity
11:05:52
pjb
If your problem can be held in the computer memory, and can be solved before you shut down the computer, then it's all O(1).
11:06:35
lisbeths
what about a server that is critical and must never shut down like the simulator that runs my skyrim game
11:08:28
pjb
Yes. Say otherwise, our computers are not turing machines, they're DFAs. Very big ones, but still.
11:09:30
pjb
Also, said otherwise, if you assume infinite stack or infinite memory in your programs, you have bugs (critical security bugs even!). You must take into account those finitude, and handle the errors.
11:10:06
lisbeths
you can choose to bound your algorithms in the lc but only if you know the size of the computer specs
11:21:34
lisbeths
the non monadic code on the puulc should run the same way on the pdp6 as they do on a computer today if there is enough memory
11:27:18
aap
what is PUULC? are you talking about my pdp-6 implementation of the binary lambda calculus?
12:35:47
lisbeths
I am very hardcore about puulc and I have some pretty powerful friends who are gonna investigate it for me
13:12:34
lisbeths
what seems to be the disagreement is how much ambiguity there is to the logical consequences of the lambda calculus
13:44:48
lisbeths
I have access to some powerful coders who shall plunder the knowledge of the lambda calculus for me
14:54:56
jackdaniel
I knew a firefighter, he had this looong ladder, so sometimes he was in a high place