freenode/#sicl - IRC Chatlog
Search
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)
10:15:59
beach
Logic programming is usually a great way to turn a polynomial algorithm into an exponential one.