Well, happy New Year to everyone I guess. I can't say I am terribly amused with progress over the last month or so. For one, the slight change in semantical processing is something I should be able to code in a day or two/three, and somehow nearly a month has passed so far. I really wanted my source code on Github by now! But I also hurt my wrist which took two weeks to recover, so there is that too.
But I am back to programming, still in progress of implementing the data structure (simple multiple-linked nested symbol table), and discovered I probably need to overhaul it once again. Reason: I forgot a design decision in my former approach which uses one map for global symbols and one map for local analysis. And I made that decision because I want to go from source code to evaluation fast, and using one static symbol table and another one for local analysis means I'll be able to parallelize more in the long run.
So, now I need to figure out whether it is worth it to preemptively defensively code a global static and local dynamic table approach.
Pff. Design decisions over not even .5KLoc of code. It's a good thing it is only a hobby project because as a manager I would never hire myself to write any code.
Monday, January 2, 2017
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.
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.
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)
Subscribe to:
Posts (Atom)