So majestic, so confident. Wow.
Halfway there. I patched up some data structure the C++ compiler accepts and now need to make use of during semantic analysis. The interpreter internally uses a lot of dumb passes, I guess I could 'tidy' up some code there while I am at it and make semantic analysis straightforward two-pass.
Saturday, December 24, 2016
Log 122416
You don't want to know how sausages are made. Nor laws. Same goes for my code when I am thoroughly uninterested.
Tuesday, December 13, 2016
Rant
Just read another rant from someone who got disappointed about the state of some academic tooling.
Then don't take fricking advice from people who don't, or can't, code.
Meanwhile, I know what to do, probably even how to do it, but don't seem in the mood.
Then don't take fricking advice from people who don't, or can't, code.
Meanwhile, I know what to do, probably even how to do it, but don't seem in the mood.
Sunday, December 11, 2016
Log 121116
Just writing some stuff down since I didn't find a scheme yet to implement. So, what the interpreter now does is that it keeps all declarations in a nested map. All combinator definitions live fully qualified in the most outward range/symbol table; local ranges are used to reference renamed imported combinators or for variable declarations. Lookup and insertion are more or less O(1), more precise O(n*log(d)) where n is a small number denoting the nesting depth and d the number of declarations.
But when a namespace is entered or a using directive is encountered the global namespace is searched fully for declarations which match a prefix. I.e., quadratic behavior. In the case of the synthetic example with 6k namespaces and a total of 10k declarations, you end up with 60M lookups. (I knew that when I coded it, just didn't know what price I would pay for it in practice.)
This is, of course, utterly ridiculous. Good enough for a very short first-order approximation, not good enough to publish to Github.
Solution: Nested linked symbol tables. A namespace is nothing more than a named symbol table or range. So, I know there is an O(1) solution^1 where entering a namespace is as simple as adding a reference to a scope. I.e, four orders speedup on the synthetic example. But I guess I would need to implement a lot of nesting and I want it to be neat.
I assume this is also where namespaces originate from. It's just a trivial extension to languages which already have complex scoping rules, thus named symbol tables, like most OO languages.
^1: There is also an O(n) solution where entering a namespace, or encountering a using directive, is equivalent to importing the symbols from another scope. This is somewhat nicer since programmers are then warned for overlapping declarations. But I'll go for the O(1) behavior, thank you. I want it to be fast.
But when a namespace is entered or a using directive is encountered the global namespace is searched fully for declarations which match a prefix. I.e., quadratic behavior. In the case of the synthetic example with 6k namespaces and a total of 10k declarations, you end up with 60M lookups. (I knew that when I coded it, just didn't know what price I would pay for it in practice.)
This is, of course, utterly ridiculous. Good enough for a very short first-order approximation, not good enough to publish to Github.
Solution: Nested linked symbol tables. A namespace is nothing more than a named symbol table or range. So, I know there is an O(1) solution^1 where entering a namespace is as simple as adding a reference to a scope. I.e, four orders speedup on the synthetic example. But I guess I would need to implement a lot of nesting and I want it to be neat.
I assume this is also where namespaces originate from. It's just a trivial extension to languages which already have complex scoping rules, thus named symbol tables, like most OO languages.
^1: There is also an O(n) solution where entering a namespace, or encountering a using directive, is equivalent to importing the symbols from another scope. This is somewhat nicer since programmers are then warned for overlapping declarations. But I'll go for the O(1) behavior, thank you. I want it to be fast.
Friday, December 9, 2016
Log 120916
Right. So, after I removed some small bugs it's time to overhaul the environment data structure I use. For one, I realized I wasn't being very smart about semantic analysis and I knew that the way I represented namespaces (basically a flat list of declarations) would give me back quadratic behavior.
I did some testing on a medium sized file (34k lines, 114k words, 608k characters) containing 6k namespace declarations. Profiling indeed gave me back around 30 seconds of wasted time.
Which, well, won't do, two orders off. Time to refactor this for performance now, which probably means a bit of a dirty solution. I'll take a day or two for this.
I did some testing on a medium sized file (34k lines, 114k words, 608k characters) containing 6k namespace declarations. Profiling indeed gave me back around 30 seconds of wasted time.
Each sample counts as 0.01 seconds. % cumulative self
time seconds seconds calls name
39.96 5.95 5.95 6000 RewriteIdentify::rewrite_decl_namespace(...
24.48 9.60 3.65 42009 std::_Rb_tree...::_M_erase(...
13.77 11.65 2.05 6001 std::_Rb_tree_node...::_M_copy...
13.40 13.64 2.00 60883594 std::__shared_ptr..
4.37 14.29 0.65 63833779 std::_Sp_counted_base...::_M_release()
2.65 14.69 0.40 62664103 std::vector...::vector...
Which, well, won't do, two orders off. Time to refactor this for performance now, which probably means a bit of a dirty solution. I'll take a day or two for this.
uLisp in 2424 lines of C
The power of Lisp in 2424 readable lines of C code. I am jealous. +10KLoc of C++ now and an incredibility fat binary wasn't what I was aiming at.
Amazing!
Right. I've got rudimentary interactive mode support.
Not to worry. The first is because I haven't completely implemented escape/unescape routines, the second probably because I massage terms in the wrong order in interactive mode.
>> "hello world"
""hello world""
>> if System.true then 1 else 2
if System.true then 1 else 2
Segmentation fault (core dumped)
Log 120916
I really hate it when stuff is conceptually foggy. And I don't see a direct manner of implementing the interactive mode into the interpreter. Something with that I need to redesign the module manager and implement a module which handles interactive mode. Or something...
Nah. That's a bad idea. The module manager handles the loading of modules. And interactive mode isn't a module. Not there.
Nah. That's a bad idea. The module manager handles the loading of modules. And interactive mode isn't a module. Not there.
Subscribe to:
Posts (Atom)