freenode/#sicl - IRC Chatlog
Search
23:48:06
no-defun-allowed
Shinmera: Instead of it either blowing the stack or going incredibly slowly, would it be a good idea for the hash table to signal an error if it has resized however many times, but still can't get a key into the table?
23:52:45
Bike
i feel like there ought to be some way to speed up cst:reconstruct, but since practically any macro is going to insert code that's not in the original form, it seems like we have to run an exhaustive search regardless
0:05:57
Bike
this might be an interesting case for meters. i can put in meters and see which particular macros slow things down
0:18:32
Bike
i guess if circular CSTs were marked as such, they could just be searched without consing up a hash table and stuff.
0:23:33
no-defun-allowed
What was that instruction traversing thing which would benefit from fast hash table misses again?
0:24:21
Bike
map-instructions-arbitrary-order, but as i said, in cleavir now that's no longer an issue.
0:26:05
no-defun-allowed
It would only have to check if instructions with multiple predecessors were already mapped, so the table would be used very infrequently. But if it's not an issue, then no problem.
0:30:29
no-defun-allowed
Oh, another CHT thing: should we use the same test function for keys and values? In my case, EQ works fine for testing values when doing conditional updates, as I share structure for everything.
0:32:36
no-defun-allowed
e.g there's a TRY-REMHASH which removes an entry iff the value is some expected value. It's kind of like CASing an entry.
0:35:28
Bike
well, i don't see any reason the keys and values should necessarily use the same test function
0:35:55
Bike
for example, say you have a hash table from function names to functions. then the names have a test function of EQUAL for setf names, but the values can be compared with EQ fine.
0:36:08
no-defun-allowed
I have one table mappings strings to lists of source information objects, so the keys — yeah, same thing.
0:42:29
Bike
the other day i decided a "real" lisp CAS should have a comparator argument, but i can't think of much reason to do fancy stuff except compare integers via EQL instead of EQ
3:04:48
Bike
no-defun-allowed: https://github.com/no-defun-allowed/luckless/blob/master/hashtable.lisp#L251 if you had an unconditional atomic store, it could be used here, right?
4:02:38
Colleen
beach: kpoeck said 8 hours, 7 minutes ago: I will change clasp wrt. importing uninterned symbols
4:19:27
beach
no-defun-allowed: That's a clever optimization trick, i.e. checking only instructions with multiple predecessors, and none of us thought about it. While I am still using the SICL-specific Cleavir, I might put it in. But I am hoping to convert to s-expressionists Cleavir some day.
4:51:49
no-defun-allowed
If I want to learn about register allocation, what kind of allocators would I start with? I am guessing the one you are writing about would take a while to understand (if the reader doesn't know about register allocation).
4:53:18
Bike
i've been flipping through https://www.cs.utexas.edu/~mckinley/380C/lecs/briggs-thesis-1992.pdf. it's old enough that it explains stuff pretty simply.
4:53:38
beach
The one based on graph coloring is easy to understand, including the fairly clever heuristic to get around the intrinsic intractability of the problem.
4:59:43
beach
The stuff I wrote yesterday is complicated, but not because of the algorithm, but because of the stupid x86 restrictions.
5:02:02
beach
The idea is very simple: You find yourself at a particular program point with a particular assignment of locations to lexical variables, some on the stack, some in registers, and some in both. You now need a lexical variable that is not in a register, and you are out of registers. The idea is to spill (store it on the stack) the variable that is going to be used the furthest in the future.
5:04:33
no-defun-allowed
No. It reminds me of reading about linear register allocation, of which one implementation spills the least recently used register.
7:37:50
beach
Yes, I think I understand what you mean. And that aspect is absolutely essential to the SICL project.
7:41:23
beach
Sure, and you have an additional problem in that you need to practice your English before writing something in that language.
7:42:30
beach
It is interesting that in a typical teaching program for English (that my (admittedly small) family took when she was a student), the students are supposed to read a book per week or so. In a typical software engineering teaching program, students are supposed to read no code whatsoever.
7:44:50
beach
I was trained as an engineer, and I am a very slow reader, because I was trained to understand every detail of every sentence.
7:47:00
beach
You read them to try to understand the difference between good writing and bad writing.
7:52:38
ebrasca
beach: Don't understand ppcre and decoding binary structures is very ugly how I do it.
7:54:01
beach
I guess it is the fault of Unix that they are so popular, since every data interchange has to be done in the form of streams of bytes.
8:01:59
no-defun-allowed
CL-PPCRE (and my own engine, in its own way) allow for writing regular expressions using list structure, but I forget what the former uses.
8:03:16
no-defun-allowed
ACTION notes that her accidental approach of the user numbering submatch groups is bad, and makes composition hard. To do: don't do that, number them somewhere in the compiler.
8:05:12
no-defun-allowed
Ideally (or as ideal as you get while having to serialize, and use regular expressions) the regular expression would be (let ((address (group (kleene non-whitespace)))) (join "From: <" address ">")).
8:09:25
no-defun-allowed
See the example code after <http://edicl.github.io/cl-ppcre/#create-scanner2>; I have constructor functions. But in either case, you could try to document by binding subexpressions to variables.
8:11:08
no-defun-allowed
e.g. (defvar *word* (kleene letter)) (defvar *whitespace* (plus (either #\Space #\Newline ...))) (defvar *three-words* (join *word* *whitespace* *word* *whitespace* *word*))
8:12:44
no-defun-allowed
You could almost see that like the approximate-BNF "word ::= letter*; whitespace ::= (<space> | <newline>)+; three-words ::= word whitespace word whitespace word" with some imagination.
8:56:56
heisig
About the performance of cst:reconstruct - scymtym had this idea of generating custom variants of all functions that are used during macroexpansion.
9:00:27
heisig
Now that I think about it, there are several problems with this idea. But it might be possible to overcome those.
9:05:49
beach
I don't get it. If I define a macro M then the macro function of M is going to be called during macroexpansion. How do you propose writing a custom version of that macro function automatically?
9:07:53
heisig
The custom version would be identical to the regular one, except that it would internally use CSTs instead of objects.
9:09:26
heisig
One of the problems is when such a CSTified object is placed in a closure or a global data structure.
9:09:37
beach
So if my macro definition of M calls, say, REVERSE, a CST version of REVERSE would automatically be generated as well?
9:10:37
heisig
Right. I suggest this translation is made lazily, as soon as a function is called the first time in a macroexpansion context.
9:11:35
heisig
Now that I think about it some more, there definitely needs to be a way to 'give up' this special processing and to fall back to the usual one.
9:12:14
beach
Because otherwise we would have to keep all ASTs around, including those of proprietary application code.
9:14:21
beach
But I smell some decidability issues here. Like what objects are a CSTs and what objects aren't.
9:15:10
beach
And what about the code for CST itself? Are the objects it manipulates CSTs or not in this context?
9:18:32
heisig
I would say every object is CSTified unconditionally. And the fact that all objects are actually CSTs is only visible to the special macroexpansion code.
9:19:03
heisig
As soon as there is some confusion (like when storing a CSTified object in a global, specialized array), we give up.
9:20:10
splittist
Regexs can be documented. Not a great example, but one I have to hand: https://github.com/splittist/docxdjula/blob/master/regex.lisp
9:20:59
heisig
You may be right. But I haven't found them, yet. If an actual CST is handled by the macroexpansion version of a function, it would be stored as a CST whose value is that CST.
9:23:43
heisig
Anyway, introducing such a feature is not urgent. I just wanted to write it down for the logs.
9:23:44
beach
Suppose someone who knows nothing about this special expansion idea writes a macro that contains a CST as a constant. If the macro expander treats that constant as a CST it would change the meaning compared to what the macro author intended.
9:26:43
heisig
Those two CSTs would be on different planes of existence (I hope) and couldn't be confused. Think of the CSTs used when executing such a macro as a special object representation, where objects are represented as (actual-object origin) pairs.
9:28:43
heisig
So the only places where a confusion can happen is when such a special macroexpansion function is invoked, and when such a magic object is stored in a shared place.
9:46:27
beach
Meanwhile, I need to figure out a better way of explaining the register-allocation algorithm.
9:53:09
heisig
One thing I haven't understood yet about register allocation in SICL - why don't we start by defining a register allocation interface and providing a simple default implementation?
9:55:16
beach
That's pretty much what I am doing, but for x86 only. I have abstracted out EDU, and "allocate a new register". The rest is imposed by the x86 constraints.
9:58:13
heisig
Could these constraints be formulated in a way that is independent of the architecture?
10:00:08
beach
That is also what I am doing. I am currently translating MIR instructions such as c <- a op b into r <- r op s where a and b are lexical locations or immediate inputs, c is a lexical location, and r and s are register.
10:00:47
beach
So the architecture-independent description is that the destination must be the same as the first operand.
10:03:01
beach
Er, s can also be an immediate of course. But I am currently simplifying so that s can not be a stack location.
10:09:48
heisig
I was thinking about using a domain-specific logic programming language. (But I admit I don't have much experience with logic programming)