freenode/#sicl - IRC Chatlog
Search
3:46:37
beach
I hadn't quite realized the power of that technique. In particular, I hadn't realized that it could handle left-recursive grammars.
6:05:50
splittist
(I do sometimes wonder, if parsing is such a solved problem it shouldn't be covered in compiler courses, why do new languages have reserved keywords...?)
6:08:02
no-defun-allowed
I don't know if I see the relation between the two parts of that question. Suppose reserving them keeps the syntax context-free?
6:08:52
no-defun-allowed
A Haskell or ML program fragment like let let = 2 in let requires us to know let is bound as a variable while parsing the body, and it looks pretty bad in my opinion.
6:10:21
moon-child
that's still context free, it just requires more lookahead. And considering haskell allows you to define new operators, I don't think they're very concerned with being syntax-free at all
6:10:52
moon-child
as for looking bad, that's a matter of taste; you can always make things that look bad. let lét = 5 in lét, for instance
6:16:38
moon-child
no-defun-allowed: oh, no, hmmm, that would require infinite lookahead. Because 'let let = 2 in let a b c d = whatever' is valid (defining a to be a function with parameters b c d), but you wouldn't know until you get to the = whether that's binding a or applying let
6:18:21
beach
splittist: When I was in charge of the undergraduate program, I split the traditional compiler course into two: "syntactic analysis" and "compilation".
6:19:18
beach
Part of the reason was that syntax analysis would be useful without compilation, like for creating DSLs and such.
7:07:33
beach
This masters thesis on packrat parsing seems quite well written. I am enjoying reading it so far.
7:14:05
beach
Hmm, what I read before (Wikipedia?) seemed to suggest that packrat parsing can handle left recursion, but the thesis says it can't. I was thinking it could if the alternatives were ordered carefully.
8:37:10
MichaelRaskin
If your left recursion is structured simply enough, you can do a pretty trivial trick (that's what I did whenever I needed it)
8:38:07
beach
Maybe so, but the paper cited by splittist seems to solve the general problem and again, it is a document well written.
8:39:02
MichaelRaskin
(They even say in the abstract that patological cases have superlinear parse time)
8:41:21
beach
My (admittedly small) family says that an adverb followed by a perfect participle should not make the two tied with a hyphen.
8:45:04
MichaelRaskin
beach: I guess my point is moot because you might only need 3.2 from the paper (direct left recursion) which is indeed well written, and clearly still packrat, and equivalent to the simplest thing done for this case.
8:53:33
splittist
Working on Clime, I feel I'm doing proper modern programming: sending strings over sockets...
9:00:50
heisig
Now that our technique with the client arguments is documented, I can finally move on to the type inference stuff.
9:02:43
beach
We also need to convince someone to modify Incless, but I guess I need to do that simultaneously with SICL.
9:03:29
heisig
The SIMD patches are not directly tied to Petalisp. But people finally want SIMD that I am receiving patches for my half finished sb-simd library.
9:06:25
beach
I think Bike gave up on Baker's method in favor of canonicalization. Maybe the reason was that Baker's method would be unable to handle the CONS type.
9:07:54
beach
Then, if we go back to my musings about the purpose of type inference from the other day, a type like CONS would probably be enough for the purpose of performance.
9:08:46
heisig
My plan right now is to have separate generic functions for precise type inference, and for approximate type inference.
9:10:54
heisig
There are some cases where subtypep is guaranteed to be precise. And many further cases where it should be. For that to work, I can't just turn (CONS A B) into CONS.
9:11:38
heisig
But a compiler will most certainly want approximate type inference, where the result is a type that is guaranteed to include the actual type of the value in question.
9:17:28
beach
You would have to solve the halting problem in order to get precise types, unless by precise type inference you mean something else.
9:18:43
heisig
Now I get it. The problem was that I wrote 'precise type inference', when I actually meant 'precise reasoning about types'. I don't plan to tackle the halting problem.
9:19:40
beach
So then I need to understand (at some point) what "precise reasoning about types" implies.
9:20:23
heisig
Your loop example is an interesting problem, because an approximate type inference will have to switch from interval types to non-interval types eventually, or it won't terminate.
9:25:02
beach
I can't figure out how you could do type inference without a finite approximation of the type system, and with such an approximation, you obviously can't represent everything.
9:42:03
beach
Or to take an example using CONS: (loop with list = '() for i from 100 to 110 do (loop for j from 100 to 110 do (push (if (zerop (mod (ackermann i j) 7)) "yes" 234) list)) (finally (return list)))
12:06:36
heisig
Yes, I do. (https://github.com/marcoheisig/Petalisp/tree/master/code/type-inference)
12:07:12
heisig
It is very fast and doesn't even cons. Obviously, SICL will have slightly different requirements than Petalisp.
12:08:09
beach
I suppose. I don't quite see how you can take advantage of it, since you are not in control of the underlying Common Lisp implementation.
12:08:50
beach
I suppose you could take advantage of how (say) SBCL optimizes certain declarations etc.
12:10:13
heisig
Petalisp uses the result to store results in specialized arrays, when possible. And it uses the type inference to eliminate certain type checks.