freenode/#lisp - IRC Chatlog
Search
20:07:22
phoe
Which ironclad digest should I use for hashing passwords? I don't want to go for SHA1 since it smells insecure to me as of late.
20:08:44
phoe
The current bit of code I have is https://plaster.tymoon.eu/view/754#754 - please bash the hell out of it if you see anything wrong with it.
21:37:00
jcowan
beach: I have just read the chapter on data representation in the SICL manual, and I would urge you to seriously consider the possibilities of nanboxing on 64-bit systems.
22:37:31
jcowan
It's a pretty fundamental decision, and controls whether 64-bit floats can be implemented as immediates.
22:38:59
Bike
is there any chance we could have the log links split up more? both clients i use mess it up
22:41:02
Shinmera
Bike: You can use the same site as for the #clasp logs. https://irclog.tymoon.eu/freenode/%23lisp
22:42:31
Bike
to be nan it has to have all 1s in the exponent, or no? seems like that's cutting down the number of bits a fair amount
22:43:48
jcowan
It's because 64-bit addresses are really only 48 bits wide, or only 47 bits if you exclude kernel space and are not on Solaris.
22:46:03
Bike
well i'm thinking of fixnums. shorter fixnums is fine, but not being able to do arithmetic immediately might be sorta painful.
22:48:12
Shinmera
if the exponent is all ones you can't just directly operate on integers like you can when they're lsb-0 tagged.
22:50:34
Younder
I saw jackdaniels McClim demo yesterday. Pretty cool. Is there a emacs style editor for McClim as the is in CLIM?
22:51:06
jcowan
I agree that doubles are less frequent, but I submit that is because Lisp defaults to single-float and single-float is typically IEEE 32.
22:51:41
Shinmera
Even if the read float type was double float I would still say that integers are far more common.
22:53:48
jcowan
Yes, certainly. I'm just wondering if there isn't suitable trickery for doing integer arithmetic without masking off the high tag.
22:56:53
Shinmera
I'm also not sure I like the idea that performing a bad float op that results in a NAN could suddenly produce something that is interpreted as something other than a double by the implementation.
22:59:02
Shinmera
I would think the quiet NAN is exactly the problem, no? Since then you get a value back that is NAN and might have whatever in the remaining bits.
22:59:23
aeth
I think double-floats are less common than they could be in part because CL is not the best language for double-floats.
23:00:50
jcowan
Shinmera: In this scheme, quiet NaNs are doubles (whose value is the abstract NaN); signaling NaNs are pointers, fixnums, characters, or whatever.
23:01:24
jcowan
Chicken uses a low-bit 1 tag for fixnums (no nanboxing) and does not appear to suffer much performance loss for it.
23:02:21
Shinmera
So how do you catch if a double op produces a nan? Check manually after every double op?
23:02:52
jcowan
this is certainly true of hardware operations, and you can make it true in software by construction.
23:03:02
Shinmera
Yeah but you, as a software man, would probably want to know when your ops suddenly produce nans
23:07:32
jcowan
FP signals are unrelated to signaling NaNs. As far as I can tell, nobody uses the latter for anything.
23:11:31
jcowan
(perhaps Either would be a better analogy, although it is not guaranteed that when you put a QNan through an arithmetic operation, you get the same QNan (in the sense of bits) back.
23:14:26
jcowan
"Unrelated" was too strong. Attempting to operate on an SNaN does indeed raise an FPE *provided* the processor supports that and the FPP is configured to raise SIGFPE (or equivalent) in that case.
23:34:20
jcowan
Shinmera: So no, I don't always want eager detection of problems. Sometimes retrospective detection is the Right Thing, as an invalidity in one part of a complicated operation may not affect the rest of it. But I hasten to add that I am not really a floating-point programmer myself, and am simply repeating what I have been told.
1:04:10
z3t0
hey all, last time I was here I was directed to a diagram flowchart for choosing whether to choose an array/vector etc.
2:23:45
jcowan
beach: My experience (approaching 60) is that I don't *need* less sleep, I just *get* less sleep
2:25:04
jcowan
Did you see my message about nanboxing? It would make fixnum arithmetic a little more expensive but allow IEEE double floats to be immediately represented.
2:26:33
jcowan
The idea is to hide a 48-bit pointer (and all nested spaces such as fixnums etc.) within the 2^52 bits of quiet NaNs
2:34:31
beach
jcowan: Current tagging schemes make fixnum addition and subtraction into a single instruction.
2:35:22
jcowan
Unfortunately I can't help you with that; I was last concerned with assembly language in PDP-11 days.
2:36:38
Bike
not that i'm not also concerned, but i do wonder. the way sicl does fixnum arithemtic now it always involves a branch anyway
2:37:38
Bike
and i mean, that'll probably be slower than a mere arithmetic operation like masking, right?
2:39:55
Bike
What I'm saying is that the additional cost from the nanboxing may be tiny compared to the cost of the overflow check, so using nanboxing might not be so bad.
2:41:23
Bike
I'm saying, if the overflow check is in there, it seems like it would be more expensive than the additional cost due to nanboxing.
2:46:20
Bike
I think you would have the exponent bits all be 1 for the NaN, so the fixnum is in the low 52 bits, maybe with the low two tag. For unsigned fixnums you could machine add them, and then check... some bit for overflow, and then maybe mask it so it's still a proper NaN.
2:47:39
Bike
Well... let's say the highest bit is still sign. Then if there's an overflow, it will carry over into the exponent and then into the sign, so maybe it will trip the machine overflow flag normally.
2:48:44
beach
So if the upper bits are 0 (not counting the sign) then the overflow would never be tripped.
2:51:31
verisimilitude
Wouldn't it be more pleasant and more efficient to implement integers seperately?
2:51:55
verisimilitude
That is, tell the machine to use integer instructions when only integers are involved.
2:51:59
beach
verisimilitude: You can't do it separately if you want every Lisp object to be a word.
2:53:02
verisimilitude
See, what I'd do is simply limit the precision of floats until it was convenient.
2:53:57
beach
verisimilitude: I mean, yes, you can do that, but then you would have your own float format.
2:54:25
rme
The good thing about single floats is that it's pretty easy to arrange to make them be iimmediate data on a 64-bit Lisp.
2:54:44
verisimilitude
The current suggestion seems to be to do what JavaScript implementations do, with careful checking.
2:56:09
jcowan
With machine performance *and* no boxing *and* decent precision, floats might be more popular
2:57:06
beach
My current thinking is that it is rare to do double-float arithmetic on values that are passed as arguments and return values. With so called "aggressive" inlining, my guess is that most such arithmetic would be on arrays or on unboxed lexical variables.
3:00:31
beach
Like I said, I think most double-float arithmetic in Common Lisp would be on arrays specialized to double float and on unboxed lexical variables.
3:03:09
beach
Anyway, since all of SICL is implemented in Common Lisp, the exact representation of things is visible in a very small number of places, I don't think this is a decision that has to be made a priori.
3:08:02
beach
In fact, one can even imagine several SICL variants. One could be optimized for double-float arithmetic and another for fixnum arithmetic.
3:08:43
beach
Such a thing would be much harder with a system that has representation information spread all over the code base.
3:48:39
beach
LdBeth: Why would start at such a low level, and why would you build a non-GC system first?
4:29:05
beach
epony: LdBeth wrote this: <LdBeth> So, my plan is an assembler first, and a non-tradition GC subset of Lisp aims only for high performance, and then layers of Common Lisp for user space applications.
4:31:59
beach
epony: I am worried that LdBeth is planning yet another implementation that is built up from some lower-level code. I have seen how writing such an implementation is very painful, and it results in code that is not very maintainable.
4:32:38
beach
epony: I am particularly worried, because there seems to be widespread belief that this is the only way to create a Common Lisp implementation.
4:34:18
epony
I would qualify that down-up approach an exercise in pre-processors for assembler though, with lisp driven something above it.
4:36:58
beach
Well, here is why I am worried: At some point, Common Lisp code has to be evaluated. That requires an interpreter or a compiler. A compiler can not be reasonably written in anything other than Common Lisp. So the bottom-up approach seems to call for an interpreter. But then, as we know, interpreters are slow. So then a compiler is needed anyway. And now you have two evaluators.
4:37:30
epony
It will be interesting to me for the sake of curiosity if this has any practical realisation, or it is a plan that may be difficult to follow up as you explain.
4:39:18
verisimilitude
Wouldn't it be fair to write that only the special operators and some other considerations need be treated specially and everything else to be compiled could be treated in a more general matter?
4:39:45
verisimilitude
It's not hard to imagine how to compile nested function calls to machine code.
4:39:53
beach
Plus, the bottom-up approach requires a lot of the code to be written in a subset of Common Lisp. Then, the maintainer has to keep track of exactly what subset is allowed in every situation. While it may be possible to do that for someone who is writing the system from scratch, it becomes increasingly hard over time.
4:41:35
verisimilitude
Now, I've been intending to compile a list of Common Lisp subsets that would be treated like this, in varying orders of dependence and whatnot, as one of the first steps towards my implementation; when I do, would you want me to point the article out to you, beach?
4:42:31
beach
verisimilitude: No thanks. I have already decided that I am not willing to work in a subset of Common Lisp which is why SICL is built the way it is.
4:42:33
LdBeth
beach: I considered use a subset of languages for system programming rather than a full impl of CL, mainly to avoid GC on real time execution.
4:43:01
epony
I think the down-up approach is applicable to low level languages, as they have no high level abstractions (which they can do as extensions e.g. libraries).
4:43:48
verisimilitude
It's not out of place to think of Common Lisp as an abstract language that is still capable of behaving low level.
4:44:33
beach
verisimilitude: How do you plan to evaluate the first Common Lisp code that needs to be evaluated?
4:45:24
epony
Now, question is GC the capability that limits applicability to virtualised machines or is it a prerequisite for these.
4:45:55
LdBeth
beach: yes, I read that paper about real time programming in Lisp. But a parallel language may also gives benefits such as static type.
4:45:56
verisimilitude
If, by the compiler, you mean what turns finalized code into machine code, then perhaps.
4:46:18
verisimilitude
I'm inclined to believe it would be easier to write it as machine code, at that level of it, though.
4:47:15
verisimilitude
I mean the final step that traverses the processed list and writes the actual machine code.
4:47:42
verisimilitude
The MACROEXPANDer, optimizer, and other higher mechanisms would be written in a subset of Common Lisp.
4:47:58
beach
verisimilitude: The lowest level Common Lisp code that is going to execute on top of the lowest level non Common Lisp, how will it be executed?
4:49:33
verisimilitude
Before we continue, beach, I do want to point out that I've been giving far more thought to the subsets and the calling convention and other details, so I may not yet have fully consistent ideas of this particular aspect of my planned implementation.
4:49:45
LdBeth
epony: you might see Haskell, Go, Rust, Ocaml get a lot of benefits from bootstraping
4:50:27
verisimilitude
With that written, the compiler only needs to be able to compile special operators and functions.
4:51:11
verisimilitude
Getting to that point requires more Common Lisp, to MACROEXPAND and whatnot, but it boils down all the same.
4:51:23
LdBeth
verisimilitude: I think what you mean is DSLs for extending CL, such as pattern matching syntax?
4:52:21
verisimilitude
When I used ``compiler'' in my second to last message, I meant the lowest part of the compiler that only processed what has already been processed by the higher parts of the compiler, which would need Common Lisp.
4:52:22
beach
verisimilitude: I suggest you think hard about how this thing will be bootstrapped. Then you write that down. Then I will read it and give you feedback.
4:53:38
verisimilitude
Most of the COMMON-LISP package is easily convenience functions; it's what's not that would need to be implemented in machine code.
4:53:40
epony
I suspect the goal is a machine that runs to fulfill the features and capabilities of the language, so a subset is in fact a different language in that sense is a pre-processor for low level languages.
4:54:38
beach
verisimilitude: It is not possible for me to glue together the pieces of information you are giving into a coherent whole. I would have to look at a complete description of the bootstrapping process.
4:55:22
beach
epony: But why on earth would one subject oneself to the pain of not using things like CLOS?
4:55:49
verisimilitude
You see, beach, I'm particularly interested in optimizing for space, which is what I would use to differentiate my implementation; I've enjoyed considering a Common Lisp implementation in which the entirety of the COMMON-LISP package is written in a different language that can be made very small. However, this would be bothersome, and so implementing enough of the language to implement the rest and working on an efficient compiler for
4:56:38
verisimilitude
As an example, beach, and I'm thinking a RISC machine such as MIPS, there's no reason NULL shouldn't boil down to just two instructions, or eight bytes.
4:57:55
beach
verisimilitude: I'll comment further when I see your technique for bootstrapping this thing. I have given bootstrapping a lot of thought, and I could not possibly build a Common Lisp system this way. It would be too painful for me, and I don't enough remaining life expectancy to make it work.
4:58:42
verisimilitude
Well, I look forward to showing you my hard work, when it's in a state for showing, beach.
4:59:14
beach
verisimilitude: The Cleavir part of SICL is already used for the main compiler of Clasp.
4:59:16
verisimilitude
Would you care to read the two instructions I believe NULL necessitates, before moving to a different topic?
5:02:13
beach
Why would you build an entire implementation around a test that is almost never performed?
5:04:48
epony
That would be fruitful to rewrite in low level language directly and spawn a number of such primitives as programs?
5:06:01
beach
epony: It may be too early in the morning for me, but I am missing the context of your utterances. What is "That" in "That would be fruitful"?
5:13:51
epony
I think the bottom-up approach ends up in a different family of languages, and the choice of example was suited for them.
5:20:41
beach
verisimilitude: Fine. But again, it would be great to see a more detailed des corruption of your bootstrapping stages. That way I can give you feedback.
5:24:51
beach
So my point is: If someone wants to write a Common Lisp system, presumably, that person likes Common Lisp as a language (why write such a system otherwise?).
5:25:30
beach
Then, why would that person inflict pain on himself or herself by writing that system in some other language?
5:26:01
beach
And why would that person add to the pain by not being able to use wonderful tools such as CLOS to write most of the system.
5:26:43
beach
Especially since, by using this technique, the person would then also create much more code, and code that is much more difficult to maintain.
5:27:48
verisimilitude
Well, beach, part of the reason I'd write a Common Lisp implementation in the first place is to demonstrate my tool used in part to write it.
5:30:13
verisimilitude
I figure, beach, that a full Common Lisp could easily fit within half a megabyte, and really far less.
5:31:05
verisimilitude
I seek to optimize in ways that lead space to O(1), at the cost of speed, in fact.
5:31:50
verisimilitude
As an example, it's fair to write that a package contains more symbols than it exports, in general.
5:32:28
rme
Back in the late 80's, a bunch of my former coworkers and colleagues worked at a tiny software company called Coral Software. They made a (CLTL1) Common Lisp that ran on a 1MB Macintosh Plus, and they worked really hard to get it that small.
5:32:37
verisimilitude
So, rather than having a list containing every symbol in that package, why not only maintain the export list, use list, and leave what remains in a global symbol list or table. You save space, that way, since every symbol has a home package anyway.
5:32:50
epony
A quick search of bootstrap lisp shows this https://github.com/robert-strandh/Bootstrap-Common-Lisp
5:33:23
verisimilitude
If you want to DO-SYMBOLS, simply loop through the entire symbol storage, only using what is valid.
5:34:24
verisimilitude
If you omit debugging information and strings, I figure, perhaps, a Common Lisp could reach 128K or 256K, easily.
5:35:08
verisimilitude
Now, there are ways to cheat, by using dummy functionality the standard technically allows, but that would be just that, cheating.
5:38:29
verisimilitude
I figure, even if each function consumed a kilobyte, that would still be less than a megabyte.
5:38:45
verisimilitude
I then figure that the vast majority of the functions could fit in far less than a kilobyte.
5:46:57
verisimilitude
Would you write any language implementation in itself, beach, or would you recognize that a language isn't necessarily best suited to describe itself, in addition to efficiently? Is this opinion solely towards Lisps?
5:55:09
phoe
you can't do (symbol-package 'cl::foo) though for example since this is undefined behaviour
5:55:35
phoe
'cl::foo will intern symbol FOO in CL at read-time and interning anything in CL is undefined
5:56:14
verisimilitude
I'm inclined to believe, from what I've checked through the HyperSpec, that this would work, beach.
5:56:54
verisimilitude
The basic idea is to make constant the amount of other storage necessary to store a certain type of symbol, by heuristically choosing which is likely to be the most numerous.
5:57:12
verisimilitude
It would be entirely reasonable in this scheme to treat the COMMON-LISP package differently, which I've already considered.
5:57:28
verisimilitude
The special code for this case would easily be dwarfed by the list or other structure, justifying it.
5:58:22
verisimilitude
So, COMMON-LISP would only contain symbols that would be external and so code using this would treat it differently, to save more space.
6:40:16
phoe
This should work. There is no requirement that there are any non-external symbols in the CL package.
6:50:08
jackdaniel
libecl.so which provides complete Common Lisp implementation when stripped occupies 4MB of memory
6:51:36
jackdaniel
cmp.fas (which provides compiler -> C -> native code) adds additional 1.2MB (without it code is interpreted)
6:52:25
jackdaniel
what is noteworthy since libecl is a shared object multitude of applications may use it (so it is not 100 apps x 4MB but rather 100 apps + 4MB in term of space)