c3d / xl

A minimalist, general-purpose programming language based on meta-programming and parse tree rewrites
GNU General Public License v3.0
270 stars 15 forks source link

Rework the symbol table to store actual definitions #19

Open c3d opened 4 years ago

c3d commented 4 years ago

Currently, the symbol table in the compiler is implemented as an XL prefix, renamed as Scope, containing definitions that are stored as infix.

The addition of a symbol is done by inserting them in a somewhat nonsensical name for a rewrite and its children. This means that printing a symbol table as a regular tree gives a somewhat unexpected result.

(lldb) xl symbols
nil tell host:text, code:tree as integer is builtin tell
( invoke host:text, code:tree as tree is builtin invoke
nil; reply code:tree as integer is builtin reply
( listen_forking as integer is builtin listen_forking
nil; nil); listen_hook hook:tree as tree is builtin listen_hook
( listen_received is listen_received
nil; nil); nil); ask host:text, code:tree as tree is builtin ask
( listen_on port:integer as integer is builtin listen_on
nil; nil); listen as integer is builtin listen
nil; nil

This is for an entry that really contains the following definitions:

xl symbols.pointer
tell host:text, code:tree as integer is builtin tell
invoke host:text, code:tree as tree is builtin invoke
reply code:tree as integer is builtin reply
listen_forking as integer is builtin listen_forking
listen_hook hook:tree as tree is builtin listen_hook
listen_received is listen_received
ask host:text, code:tree as tree is builtin ask
listen_on port:integer as integer is builtin listen_on
listen as integer is builtin listen

The lookup is O(log(N)) by selecting which branch to follow using a tree hash.

I believe that it's possible to store the entries without the nil, simply balancing between left and right as you need.