freenode/#lisp - IRC Chatlog
Search
13:18:46
pfdietz
Vectors with fill pointers can implement stacks in O(1) amortized time per operation.
13:20:02
pfdietz
This is fine unless you have real time constraints, or if you're trying to make the stack "fully persistent" (where updates can be done on past versions in a branching model of time.)
13:21:25
beach
pfdietz: Correct. I was referring to the worst-case complexity of one single operation.
13:22:21
pfdietz
It's possible to get to O(1) worst case time by a more clever approach, where the copying to the new larger vector is spread out over O(n) updates. This still doesn't help with full persistence though.
13:22:29
beach
hajovonta: You can't stick an auxiliary method that specialized according to the particular type of the closure.
13:23:06
pfdietz
Another lispy example of this is implementation of a queue with stacks. Using two stacks you can do queue ops in O(1) amortized time, but you can also do it in O(1) worst case time with some effort.
13:23:18
beach
pfdietz: The better solution that solves both problems is to use a list of constant-size vectors.
13:25:33
beach
pfdietz: Interestingly, when I came up with that solution, I checked it with the algorithms and data structures expert in the lab (I do not consider myself an expert, though I may have to rethink that), and he had never heard of it, nor had he ever contemplated the problems with the list or the vector solution (space vs real-time).
13:29:59
beach
pfdietz: Using a list to implement a stack has the problem that each element takes 2 words. So if you want a stack of bits or of DNA letters, you wast a lot of space.
13:30:47
beach
pfdietz: If you use a vector instead, you are sacrificing real-time behavior, so you can't propose it to gamers for instance. Occasionally an operation may take linear time.
13:31:28
beach
If you use a list of constant-size vectors, you can have vectors of bits, and provided the vector is big enough, you can make the 2 words waste arbitrarily small.
13:31:52
Zhivago
Gamers don't really care about real-time -- they just care about latency spikes. In practice they just make things excessively fast enough that the spikes they do get are acceptable.
13:31:56
pfdietz
There's a theme in data structure design where you layer two different kinds of data structures, using a different one for small chunks. This looks like an example of that.
13:32:10
beach
pfdietz: Furthermore, you only ever need to allocate a constant-size vector and you never need to move more than that many objects, so you have constant time operations.
13:33:10
pfdietz
And the overhead of the links can be spread over the length of the vectors, and so can be made as small as desired.
13:33:56
Zhivago
I think you'll find that gamers are happy with the terrible things that STL does to extensible vectors in most cases. :)
13:34:30
pfdietz
Where I was not clear was that you were reducing the space overhead, minimizing the constant.
13:34:54
beach
Zhivago: I actually don't care much about that particular use case. I chose the wrong example. Again, I'm sorry.
13:36:22
shka
anyway, it you can have hard real time behavior as a component in system that is supposed to have soft real time characteristics without drawback, you potentially can save yourself headache when optimizing
13:47:45
beach
pjb: Clearly, for the side-effect-free version of the stack, the vector solution is totally out. The list of constant-size vectors might still be acceptable.
13:49:02
beach
pjb: If you have very small objects, like bits or DNA letters, you can copy the entire thing very efficiently, so you are no worse off than with a pure list.
13:49:21
beach
pjb: And if you have large objects, you converge toward the pure list solution anyway.
13:51:02
pjb
This is why we have programmers: there are always special circumstances that require specific data structures and algorithms.
14:34:35
flip214
would it be too much to ask that "Beta" gets removed from the documentation pages, eg. https://www.quicklisp.org/beta/releases.html (URL and text)?
14:48:01
JuanDaugherty
so the problem I was having with mcclim demo was due to trying to run under vnc
14:56:45
Bike
somewhat to my surprise, you can pass any input stream to LOAD, as far as i can tell. but if you do, and the stream has no associated file, i'm not sure what *load-truename* and *load-pathname* ought to be bound to. anyone know?
15:01:43
Bike
I mean, for example, in (with-input-from-string (s ("print *load-pathname*)") (load s)), what is printed.
15:02:50
beach
Bike: Good question. I don't see the answer to it anywhere. Something for WSCL to specify, it seems.
15:23:40
beach
figurelisp: I am a researcher and I have chosen Common Lisp both as my research project and as a vehicle to accomplish it.
15:24:30
beach
It's because where I work, we don't have the pressure they have in some countries to get grants, etc. So I can choose what I do.
15:39:52
LdBeth
Basically I learned Lisp because I’m not required to learn any particular PL and out of mania on retro computing
15:45:23
LdBeth
Actually CLtL2 is written before I was born. So I consider it as retro. Plz forgive me if that annoys you
15:51:49
LdBeth
Just because it’s strong typed. In untyped lambda calculus even Y combinator can be applied to an int
17:40:27
flip214
https://github.com/pcostanza/closer-mop says "This page is taking way too long to load."
20:23:00
HighMemoryDaemon
Can Lisp be compiled to machine code that can be ran on computers without [insert common lisp implementation] installed?
20:24:36
random-nick
HighMemoryDaemon: does that disqualify implementations that bundle themselves with your executable?
20:25:32
random-nick
even if you somehow don't use any standard functions and macros you still have the garbage collector
20:26:02
trittweiler
HighMemoryDaemon, ECL can get you binaries that simply depend on a libecl.so dynlib.
20:27:11
sjl_
depends on what you mean by "installed". If you s-l-a-d on sbcl, it can produce a single binary that doesn't need anything else on the target machine to run.
20:27:25
random-nick
HighMemoryDaemon: SBCL can save a full image of the running system as an executable
20:27:46
sjl_
That binary will happen to include SBCL itself, so whether you consider that to be "installing" SBCL on the target machine depends on your definition of installing, I guess.
20:27:55
aeth
As far as standalone binaries, SBCL wil be the fastest, but the largest, so it depends on what you want. Probably unsuitable for a tiny script, but probably most suitable for a game or large application.
20:30:58
earl-ducaine
HighMemoryDaemon: For the sake of completeness: the degree of local support needed for compiled code is unspecified, i.e. implementation dependant and can be , and for modern common ilsp often is, zero
20:31:47
HighMemoryDaemon
Just compiled a console hello world program in SBCL. 42 megabytes in total.
20:33:31
aeth
On the other hand, even graphical applications are much larger than 42 MB these days. Bloat.
20:33:51
pjb
HighMemoryDaemon: with ecl, you can also generate a static library libecl.a, and link your program statically, so the executable doesn't rely on a shared library to be pre-installed.
20:34:35
sjl_
HighMemoryDaemon: Right, that includes SBCL itself. e.g. if your hello world app crashes you'll get the full debugger and Lisp environment.
20:36:20
marvin4
is there a way to avoid packing sbcl together with every executable? or do language spec require full enivornment available at runtime
20:37:49
pjb
marvin4: yes, instead of using sbcl, use another CL implementation. Then sbcl won't include itself with the executable.
20:38:36
HighMemoryDaemon
What are the most common uses of Lisp in the modern day? GUI applications, web servers, AI, ..? I have a feeling that with a lot of uses you don't need to worry about compiling to native machine code.
20:39:27
Bike
compiling to native code is usually useful. compiling gives you static error checks, and machine code is generally faster than interpretation.
20:39:52
Bike
it is a general purpose programming language. do people ask what java is "for"? it's such a weird question to me
20:40:02
aeth
HighMemoryDaemon: Two uses are common enough for their own channels: #lispgames and #lispweb
20:40:34
aeth
Lisp was also traditionally very large in AI, but it was mainly used for old school AI, not machine learning, so relatively speaking it's probably much smaller there than it was.
20:42:04
earl-ducaine
HighMemoryDaemon: If you're concerned about the size there are various compression schemes you could lookat.
20:42:23
Bike
i think sbcl already incorporates several, so it might be hard to squeeze it much more
20:42:46
earl-ducaine
HighMemoryDaemon: A quick export shows that gzip will compress it into a 12M file.
20:43:59
earl-ducaine
HighMemoryDaemon: (sbcl) Presumably the executable has various sparse memorry areas that are simply read into their location when the executable is loaded.
20:48:41
HighMemoryDaemon
earl-ducaine: That's cool. With Gzip are you just talking about reducing the download size for the end user or is their a way to actually zip an executable that unzips on launch?
20:49:19
aeth
HighMemoryDaemon: here's a bunch of them: https://dto.itch.io/ https://itch.io/jam/lisp-game-jam-2018/results
20:58:14
earl-ducaine
HighMemoryDaemon: Launch plain SBCL from bash shell and past this lisp code https://gist.github.com/earl-ducaine/c1a59ab3d9384d318fbe715abbff0eb6 into the terminal
21:15:16
HighMemoryDaemon
earl-ducaine: One thing I'm confused about though is the ":save-lisp-and-die" that is attached to the function name. I'm not so confused as to what it does but what is that syntax feature of Lisp called? I haven't seen that before.
21:15:52
sjl_
HighMemoryDaemon: save-lisp-and-die is the name of the function. sb-ext is the package
21:17:35
sjl_
you could also (use-package :sb-ext) first, and then just use (save-lisp-and-die ...) but that would import a ton of other stuff you don't need, so usually people just use the package-qualified name for stuff like that.
21:23:08
HighMemoryDaemon
Using the "time" command on Linux, I can see that a compiled+gzipped "hello lisp" app takes 0.15s to execute. The compiled+not-compressed "hello lisp" app takes 0.02s to execute.
21:25:09
sjl_
right, it takes time to decompress it first. it's a tradeoff between disk space and startup time
21:32:35
scymtym
there is also the minor difference that multiple SBCL processes cannot share as many memory pages when compression is used
21:48:59
drduck
Howdy. What's an actively maintained library for common-lisp that's similar to hibernate for java, in that it's an ORM mapping tool?
21:52:38
_death
personally I don't use ORMs, but I think an actively maintained one is https://github.com/fukamachi/mito
23:15:31
aeth
Any list that lists GCL among its recommendations is so incredibly uncurated that I wouldn't trust anything on it.
23:16:34
akkad
and it's list gets out of date often, to show you inperfections that it is done by hand.
23:17:05
aeth
For that list to have gotten out of date and have GCL on it, it would have had to be written in 2005 or so.
23:46:40
jasom
We should have a "If you say you are using X on #lisp, we won't laugh you out of the channel" curated list.
23:50:14
aeth
If you're going to recommend a bunch of things in the same category, you should be opinionated and not just list them alphabetically. e.g. I'd recommend trying SBCL, CCL, and ECL in that order. awesome-cl puts SBCL last because it's alphabetical and ultra-niche ABCL first!
23:58:17
akkad
but cl has an image issue, and this goes a long ways to teach potential developers how cool it is
0:01:51
p_l
akkad: when GCL was making doornails look lively, XEmacs was still something I would suggest over Emacs :)
0:02:05
aeth
akkad: It's not good for the image of CL (a dead implementation that's barely supported by the ecosystem does not make a good first impression) or for the security of CL programmers (SBCL or CCL would patch a security issue next month... GCL would patch it in 5 years maybe?) to recommend inactive implementations.
0:04:11
aeth
It's a lot harder to determine things about commercial implementations. It's likely they're not in the ASDF+Quicklisp ecosystem with the rest of us and if there's some issue it *could* still be patched quickly through a commercial support contract even if there's one user.
0:08:20
aeth
aeth-lisp is also alive if someone is willing to pay $500,000 a year or whatever. Even if it has basically 0 presence anywhere else.
0:11:20
aeth
Josh_2: It's a lot harder than it looks. I can't just "git clone https://github.com/sbcl/sbcl.git" because I also have to find-and-replace all instances of the strings "SBCL", "sbcl", "Steel Bank Common Lisp", etc., except on the relevant copyright/contributor pages, etc.
0:43:13
p_l
aeth: SCL is kinda dead, moxcl is probably alive but isn't a full implementation, Liquid, Franz and Genera are in similar state of undead (you can still get support), I actually don't know about Interlisp because it feels at times that the owners forgot there was a language implementation under the program they were selling
0:45:15
p_l
(I'm ignoring implementations that died back on DOS or were so obscure good luck finding mentions, let alone software or parts)