freenode/#lisp - IRC Chatlog
Search
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)
7:36:18
flip214
I get "A function with declared result type NIL returned: bordeaux-threads:condition-wait" and the SBCL process stops.
7:38:01
phoe
AFAIR this is an intermittent bug that #sbcl has been hunting for in a while. You could go there and help them debug it.
8:20:39
phoe
beach: I ran into an issue when defining protools for conditions. They aren't STANDARD-OBJECTs and therefore cannot subclass protocol classes. A possible workaround I think of is to define an equivalent protocol condition type that is instead meant to be subclassed by conditions only.
8:23:46
jackdaniel
writing correct programs is not the same as writing programs that seem to work most of the time
8:24:43
jackdaniel
phoe: SBCL uses CLOS to implement conditions (but they come from condition-class hierarchy)
8:25:31
Shinmera
jackdaniel: I'm asking because 1) conditions not being under CLOS is in my opinion an oversight of the spec 2) I am curious what implementations do because of 1)
8:26:28
phoe
X3J13 thought that some kind/subset of CL could be delivered without CLOS, and they nonetheless wanted to keep conditions in even if CLOS is out
8:27:54
jackdaniel
well, it partially does – it may be a reason conditions are not defined as being clos objects.
8:30:00
phoe
Shinmera: SBCL wants to have conditions early in its build phase, earlier than it builds its PCL - that is a major issue that I have identified
8:32:35
jackdaniel
ECL has conditions before PCL is even loaded, so in principle it supports non-clos conditions (as well as clos ones which are prevalent)
8:33:04
Shinmera
phoe: That's fine, but as long as they are tied into CLOS once we hit user-land it doesn't really matter.
8:35:54
phoe
Shinmera: so what do we do? Write a set of tests for verifying if conditions are standard-objects and all associated functionality, write a CDR that holds the same assertions as the test suite, run the tests on all implementations and then try to hammer the impls until the tests pass?
8:37:03
Shinmera
Well first survey what implementations do -- record the type, class, and potentially metaclass of CONDITION.
8:37:11
jackdaniel
phoe: what you propose is writing CDR to make incorrect programms magically correct?
8:37:19
Shinmera
Once we have that info we can determine whether it's possible to paper-over or whether implementations actually would need change.
8:38:05
phoe
jackdaniel: what I propose is extending the language via a CDR in the same way some implementations already extend it
8:39:59
Shinmera
Conditions being under CLOS would be an extension in the same way that extensible sequences are.
8:40:00
jackdaniel
I think it is not an extension but rather implementation detail. maybe I've missed the part of *any* implementation manual about "extension" making conditions clos objects
8:40:20
phoe
while I understand that X3J13 did not find it meaningful to make conditions standard-objects back then (reading the notes, I assume backward compatibility with previous lisps) , I find it meaningful nowadays to do that nonetheless
8:41:01
Shinmera
phoe: From reading what you linked it seemed to me that they pretty heavily favoured making it CLOS, but then didn't have time to finalise the details of it.
8:41:27
phoe
Shinmera: I need to read it again when I'm not at work. I didn't get that impression when I read it.
8:57:33
phoe
Shinmera: I actually did a thing and things seem to "somewhat" work for the little bit of testing I have done so far. This thing is (defmethod sb-mop::validate-superclass ((class sb-mop::standard-class) (superclass sb-pcl::condition-class)) t)
9:10:58
Xof
phoe: you might have some difficulty getting slot locations right for such a hybrid object
9:11:42
phoe
Xof: I actually don't think I want to pursue this thing since it's not exactly that I would like.
9:14:33
phoe
Instead of cross-breeding standard-class and condition by means of objects that subclass both, I wonder if it would be possible to make condition a subclass of standard-object.
9:34:19
phoe
Xof: the ability to drive conditions via CLOS and MOP, even partially, sounds worth it in my opinion
10:01:30
phoe
I hit a wall today because I can't make constructors for conditions that work out-of-the-box with the stock #'make-condition
10:01:56
phoe
where I'd normally write (defmethod initialize-instance :after ...) for standard-objects
10:05:14
phoe
and workarounds like (:shadowing-import-from :my-package #:make-condition) doesn't work universally
11:34:08
phoe
TIL I can do (defmethod initialize-instance :after ((warning style-warning) &key) (print "boo"))
11:45:14
Shinmera
phoe: You can but, if I remember correctly, initialize-instance is not always called.
12:07:05
phoe
I don't want a constructor to catch anything, I want a constructor to do things whenever a my-condition is instantiated
13:28:00
elderK
I've been working on a tool to help me play with grammars. I spent my mid-semester break making several iterations of said tool. I just finished it. It let you compute the first/follow sets for an arbitrary grammar it read from stdin. It also allowed you to produce an LL(1) parse table, if possible, for said grammar. It was written in C++.
13:28:54
elderK
I will have to rewrite it some time in the future. As, it would have been a useful tool for me to have.
13:29:55
elderK
I really wanted to show a lecturer of mine the finished product. As well as some others.
13:30:24
elderK
Normally I treat VCS as backup. If only I had committed my work *as* I was building it, as usual, I could have just reverted.
13:30:44
phoe
elderK: not just you, https://github.com/valvesoftware/steam-for-linux/issues/3671 https://github.com/MrMEEE/bumblebee-Old-and-abbandoned/commit/a047be85247755cdbe0acce6f1dafc8beb84f2ac#diff-3fbb47e318cd8802bd325e7da9aaabe8L351
13:31:21
elderK
In any case, as much as this sucks, at least I know I can produce such a program. And that's worth something, the know-how too.
13:31:25
dlowe
if you use git and emacs, there's a nice git-wip library that will save every edit in a "work in progress" branch
13:31:49
elderK
I was here a few days ago, asking how to represent a state machine in CL. I was told that tagbody and gotos are a common way to do that in CL.
13:32:07
elderK
However, there is an approach I like to use from the C world and I'm not sure if it maps well to CL - and if it does, how.
13:32:56
elderK
A TAGBODY and GOs makes me think of switches and gotos. I don't really like that, so usually I have a 2D array. One axis is the current state, the second axis is the input. That let's me transition just by accessing.
13:33:07
dlowe
the way you represent a state machine in CL is with state functions that return the next state function
13:35:24
elderK
Again from C, let's say for a lexer I'm accepting some input character. Generally, I don't care about characters. I care about entire classes of characters so I have a LUT that translates a given code-point to a given class. Say, "=" to "equals" and all of the numbers and alphabet as "alphanumeric."
13:35:47
elderK
I see people doing that with giant switches in C/C++. I;d like to avoid that in CL if possible.
13:35:56
dlowe
also, you have constrained the problem to that of a state machine, whereas there are no such guarantees with tagbody
13:36:36
elderK
phoe: I'm not reading anything here. The functions that do stuff based on input, accept input as an argument.
13:37:30
elderK
I'm not interested in the actual "class" of a character. I'm interested in translating a character into something useful to me, in a sense, they become low-level tokens.
13:37:57
rumbler31
elderK: you're asking essentially if there is language support for dispatching on X, where X is some thing
13:38:35
rumbler31
you can do it with a hash table by hand, or if you can dispatch on eql, you can use generic functions
13:40:45
elderK
Let's say I care about all code points < 128. I create a hash table. Initialize it so all 128 code points are say, 'invalid. Then, I build the proper mappings.
13:41:04
dlowe
but involving the CLOS dispatch mechanism for zero benefit seems like a poor tradeoff
13:43:26
elderK
But this does raise another question: What is the accepted way to get a given character's code point? I have found char-code and char-int. And, am a little confused with the difference between them.
13:45:21
dlowe
I mean, if your cl implementation supports unicode (and most of them do, if not all of them), char-code and code-char will do the right thing
13:46:27
elderK
Then I don't have to do the decoding myself :) (I wrote a library for that some time ago. I'd certainly be happy to avoid that! :D)
13:48:29
elderK
Weird. I can't see anything in cl-unicode's API about it, itself, doing any kind of reading of characters. It lets you determine a lot of interesting properties about characters based on their name or code-point. But, that depends on the implementation giving you a code-point.
14:24:09
rk[ghost]
right, i didn't go that far.. i knew i was in google.. but when i went to type a math equation.. my mind said... operator first!
14:24:24
phoe
rk[ghost]: ssh from the second machine to the one that has the repl, or go for remote swank