freenode/#lisp - IRC Chatlog
Search
11:05:25
beach
Quicksort has a very bad case where it takes up linear stack space if you do it recursively, and quadratic time.
11:14:57
schweers
shka: if my memory serves me correctly, sorting lists is faster than sorting vectors in sbcl.
11:15:32
MichaelRaskin
I think for large lists sorting pre-sorted list is slower than sorting a reverse-sorted list in SBCL
11:21:42
beach
shka: Or else you use merge sort which requires O(n) extra space, so the same as a list.
11:23:29
schweers
beach: did you suggest that quicksort can be implemented without recursion? Am I missing something really obvious?
11:25:30
schweers
beach: I mean this quote: “<beach> Quicksort has a very bad case where it takes up linear stack space if
11:25:43
MichaelRaskin
Well, you can always replace recursion with a loop with your own fully controlled stack data structure
11:26:59
beach
schweers: One easy way would be to recurse on the shorter of the two parts, and iterate on the other.
11:27:04
MichaelRaskin
You might be able to keep it logarithmic-stack with tail-call-optimisations (easy if you roll your own stack control)
11:34:22
beach
That's now how I have seen it described. I have always seen it as choosing an arbitrary pivot.
11:47:53
beach
I maintain my suggested project using merge sort with O(1) extra space if there is no stack space available.
11:50:31
beach
MichaelRaskin: Fast Stable Merging and Sorting in Constant Extra Space, by Bing-Chao Huang and Michael A. Langston.
11:51:23
beach
MichaelRaskin: Practical In-place Mergesort by Jyrki Katajainen, tomi Pasanen, Jukka Teuhola.
11:52:23
beach
MichaelRaskin: But my suggested project has the same twist as some previous papers of ours. Namely use the stack if there is space.
11:53:21
MichaelRaskin
But using stack doesn't buy you _that_ much compared to strategic one-time allocation anyway
11:53:35
beach
Wow, the more I think about it, the more preposterous I find the idea of coming to IRC because of boredom.
11:54:06
beach
MichaelRaskin: Sure, but you would have to know that you have that much memory available in the heap, and you many not have.
11:54:40
TMA
beach: that's just O(1) space merge; you still need to keep track what subsequence are you trying to merge, and as there are O(N) subsequences at the tails, you need O(logN) bits of storage to remember which subsequence you are merging
11:55:16
beach
TMA: I don't remember the details, but what you are saying seems to contradict the results of both those papers.
11:55:53
MichaelRaskin
I think the real answer is we want O(1) cells, and a call is always more than log n bits
11:57:10
TMA
beach: I think I have read at least one of them. they are not concened with the recursive subdivision and recombination that takes O(logN) space but only with the merge step, which ordinarily takes O(N) space but they brought it down to O(1)
11:57:57
beach
TMA: If I ever take up that project, I'll definitely read those papers with what you are saying in mind.
11:58:23
MichaelRaskin
Because for merging you can enumerate the needed merges in advance without any care for data contents
11:59:21
beach
Personally, I am less interested in the theoretical result than in an implementation that is fast for most cases and uses little space when it has to.
11:59:29
TMA
the other twist might be that they might be using the convention that pointer size is O(1) irrespective of N
12:00:14
MichaelRaskin
Because you are about allocating O(1) extra records. And integers are usually pointer-length etc.
12:03:24
TMA
[that is wrong from the theoretical standpoint ... you cannot store the number of elements in less than O(log_2(N)) bits ... although you can do away with O(1) with the additional requirement that N < 2^k (because O(k) = O(1))
12:04:26
MichaelRaskin
TMA: there is more than one theoretical model used for complexity definitions, though
12:08:07
MichaelRaskin
I am not sure making a stable heapsort is a worse idea than implementing the constant-space merges
12:08:26
TMA
if I can assume N < 2^128, I can keep track of the 'subsequence to merge next' in one pointer of 128 bits and one level indicator of 7 bits ... <2^32 its 32 bits and 5 bits ... for practical purposes (finite universe) those are both O(1), but ... :)
12:13:32
MichaelRaskin
I think I have a few ideas that should work, but I haven't verified I don't miss something
12:18:27
beach
MichaelRaskin: Also, merge sort is chosen because it divides the sequence in two, each with the same number of elements. So the constant time overhead is minimized. I don't see how heapsort can be guaranteed to have such good behavior.
12:19:31
MichaelRaskin
Well, the constants are of course a bit worse than merge sort, especially merge sort with extra memory available
13:53:24
Satou
Does anyone here use Drakma for http requests? I cannot seem to be able to find a way to send a file through POST
13:56:38
MichaelRaskin
I think :parameters '(("upload" . #p"/tmp/file.txt")) worked for me last time when I tried.
13:57:54
Satou
Right now I use :parameters `(("file" . ,filepath)) which the filepath gets passed through as a function argument. Thanks MichaelRaskin, I'm going to try that
14:17:27
Myon
which component is at fault if I'm getting http://paste.debian.net/1030665/ on Ubuntu bionic?
14:18:15
Myon
(this is already after updating build-app and cl-asdf to what's in Debian unstable, where it works)
14:26:15
Satou
MichaelRaskin, Well, it's seems I'm making some progress, but I cannot use yason to parse the output of that (my goal is to make an IPFS API client in CL)
14:28:34
Satou
Here's an example, but I cannot seem to be able to use yason:parse on the flexi-stream it returns afterwards. I get a #\F fell through ECASE exception
14:30:45
schweers
I have a package question: I have a package #:FOO which :USEs a package #:BAR. I want to change this fact [i.e. #:FOO should no longer :USE #:BAR]. Any tips on how to do this without restarting the lisp?
14:41:36
svillemot
Myon: it's not obvious at first glance, and I don't have the time to investigate now, sorry
15:18:51
MichaelRaskin
Try reading data yourself, outputting it and also feeding it to yason as a string
15:21:51
Satou
I've set drakma's header-stream to *standard-output*. What it returns is a bad request (400)
15:36:29
Satou
I have to go for now, but I'll be back in a few hours. Thank you MichaelRaskin, oni-on-ion
15:39:30
oni-on-ion
i think the URL request is different for both of his scenarios. just read about drakma myself yesterday
15:59:23
gendl
Hi, does anyone know about the Slime error with "error in process filter: Wrong number of arguments" which started happening in Emacs 26.1? Apparently it is fixed in the latest slime, but not the one available through Quicklisp yet. How would I go about getting the latest Slime ahead of next QL release?
16:01:42
gendl
edit: I see Version 21 released here: https://github.com/slime/slime/releases, while Version 20 came with latest quicklisp. I'll go ahead and try installing version 21 (although I'm very spoiled on Slime installation with quicklisp-slime-helper).
16:03:26
MichaelRaskin
Well, there might be problems if your pre- and post- environment is different and it cannot just reload the library by name
16:03:49
fiddlerwoaroof
I don't know if the latest release has the fix, but the git HEAD version did when I encountered this problem
16:04:31
fiddlerwoaroof
The error I'm getting when I run the image is [2018-06-25 08:56:24 [ERROR]] SSL initialization error: Can't create new SSL CTX
16:05:11
Fade
gendl: well, my emacs config is a bit eccentric, but there's a commented example in it setting an explicit load path: https://github.com/fade/dot-emacs
16:08:02
fiddlerwoaroof
Here's a reproduction with backtrace: https://lpaste.net/4197350252799328256
16:18:22
beach
flip214: Am I understanding you right that you don't feel confident telling me whether or not the GC specification you checked for me seems reasonable?
16:53:40
littlelisper
can anyone please explain me what set-macro-character and get-macro-character do, in a simple language?
16:54:10
flip214
beach: well, you wrote that you'll make the paper more explicit -- that's what I'm waiting for before giving an (a final) opinion.
16:55:29
flip214
I hope that I can clean up all the things on my mind currently (do a brain-GC, more or less ;) to then be able to think about your paper in honest.
16:56:16
littlelisper
Beep-Lord: i get that they are used to make custom reader. but just tell me what it does on a high level
16:56:27
flip214
right now, I'm feeling out-of-memory and can't process any deep thoughts... I hope to change that later this week (Friday)
16:58:58
flip214
littlelisper: the macro character "#" dispatches to various reader function based (loosely) on the next character; this dispatch table can be read and set with this functions
17:01:26
pjb
littlelisper: to udnerstand them you have to read chapter 2. notably 2.2 Reader Algorithm.
17:01:42
Bike
littlelisper: when you set the reader macro function on some character, it means that when the reader hits that character at the start of something, it calls that function to get the read object.
17:02:21
pjb
littlelisper: basically, READ knows how to parse and read only 1- symbols, 2- integers, 3- floating-point numbers. That's all.
17:03:14
pjb
so the syntax of lisp is actually very simple, since it is almost entirely customizable.
17:10:42
littlelisper
(set-macro-character #\] (get-macro-character #\))). does this mean that the reader replaces ']' by ')'?
17:11:17
pjb
littlelisper: if reading something starting with ) makes any sense! The reader macro on #\) just signals an error.
17:12:28
pjb
littlelisper: notice that to read lists, READ uses a function similar to READ-DELIMITED-LIST (but not this function, since it is not able to read dotted-list). This function can be used in a reader macro for #\[ to read lists terminated by #\].
17:13:26
pjb
Now, the reader macro for #\) will probably mention #\( in its error message. This may not be the best choice for #\], since it would be confusing to the user. It would be better to implement your own reader macro for #\] with a specific error message.
17:14:08
pjb
Notice that you also want to make #\] a terminating reader macro, so you can write [a b c] and not have to write [ a b c ] ; <- notice the space.
17:14:42
pjb
Happily, this is what happens by default (the optional non-terminating-p parameter is nil by default).
17:15:46
pjb
If the macro was non-terminating, it would be that if there was no space before, it wouldn't be interpreted as a reader macro, but as a consituent character of the previous token.
17:17:45
pjb
For example, # is a non-terminating reader macro: (quote (a#b c##d)) #| --> (|A#B| |C##D|) |#
17:29:17
gendl
Fade: I just upgraded Slime the quick & easy (and probably dangerous) way -- manually copied the slime-2.21 into quicklisp/dists/quicklisp/software/slime-v2.21, then edited quicklisp/dists/quicklisp/installed/systems/swank.txt to point to that one.
17:31:04
gendl
Anyway, I usually install quicklisp clean each time anyway rather than trying to update in-place. That's probably overkill, but another reason I do it is to keep down the size of the quicklisp directories that we distribute ourselves with Gendl and Genworks GDL releases.
17:50:27
MichaelRaskin
beach: some cleanups help, but I am not sure how to break 30x slowdown in compilation speed. Or 30x runtime slowdown, but runtime doesn't feel completely absurd, at least.
18:30:08
makomo
gendl: your software is interesting stuff and a good showcase of what CL software looks like
18:31:31
makomo
gendl: for example "G102 Video 3" isn't very informative (and has no description either), and i think that's it's very interesting to see
18:31:46
makomo
including "common lisp" somewhere in the description as well would allow people to find common lisp stuff more easily as well :-)
18:32:23
makomo
(i'm watching the video because i'm interested in what the software does and how it's used btw)
18:51:19
Smokitch
What is the difference between generic dispatch and multiple dispatch? And is generic dispatch just called generic because of generic functions?
18:53:21
dlowe
"generic dispatch" is the process of calling the correct method given a generic function.
18:53:42
dlowe
"multiple dispatch" is the process of deciding which method is correct by using the types of multiple arguments.
18:54:26
dlowe
In other languages with "objects," typically generic dispatch is only based on the type of one of the parameters.
18:56:37
makomo
and where does the adjective "generic" come from? i suppose it's just from the name "generic function", i.e. "the dispatch within a generic function"
19:02:06
dlowe
I speculate that it's generic with respect to applying the function. The normal function call is a specific case of a generic function.
20:48:49
MichaelRaskin
beach: and of course it is a completely different story what to do when a condition is signalled in the debugged thread…
21:00:52
varjag
is there a simple way to convince hunchentoot to not treat + as whitespace in request parameters?
21:22:02
White_Flame
but you should probably be using a function to safely encode your parameters instead of special casing it
21:45:10
MichaelRaskin
beach: also an interesting question what exactly should happen for step-over for a form that contains a go or throw that might land inside or outside that form.
21:47:11
White_Flame
in my experience in other languages with thrown exceptions, that tends to just continue running, unless you have "pause on exceptions" set
21:48:13
MichaelRaskin
If I already take 30x hit for both compilation and runtime, adding actual logic for handling that might be a good idea…
22:16:47
White_Flame
is there a moderator for #lispcafe? kinda needs it as epony went there from here