Re: Functional Symbol Tables

On 2007-07-09, bison <sgillespie@bisonofborg.com> wrote:
  > I'm trying to figure out a way to implement symbol tables in a
  > functional style, but I can't figure out a way to do that. The only
  > way I can think to do it is to keep track of names during parsing for
  > each scope and upon entering a scope add these bindings to the
  > existing table.


Sorry, but I am not sure that I understand your problem.


Let me explain what I did with symbol tables in the functional-style
transformation formalism ASF+SDF:


My nested symbol tables are defined like (edited to make it look like BNF).


Symbol-layer ::= "single" "{" Symbol* "}" Symbol-layer
                                | "null" "{" "}"


Symbol-layer is a nested list of scopes. At the bottom in a "null" scope
without symbols (between the curly brackets). The null-scope is prefixed by a
stack of "single" scopes, each with a list of Symbols (Symbol*) in it.
(in reality, I have two other forms of scopes, hence the keyword "single").




On this syntax, I defined a number of functions for creating and deleting scopes:


"new-null-layer" -> Symbol-layer
"new-single-layer" ( Symbol-layer ) -> Symbol-layer
"del-layer" ( Symbol-layer ) -> Symbol-layer


and some functions for adding and getting symbols to these scopes:


"may-add-symbol" ( Symbol-layer, Symbol ) -> Boolean
"add-symbol" ( Symbol-layer, Symbol ) -> Symbol-layer
"get-symbol" ( Symbol-layer, Identifier ) -> Symbol


(slightly simplified w.r.t. reality). Note that Symbol contains the name of
the symbol, so it can be added to the table without specifying an Identifier.




  > I read somewhere that you can pass around your ST through arguments.


With functional programming, you don't have global variables, everything is a
parameter of the function that is executed.




  > My thought about that is that if you are using recursion, you will
  > lose all of your mappings once that call is returns. Does anyone have
  > any thoughts on this?


Euh, I guess so. Normally, you return any interesting results (such as the
modified symbol table) as return value from the function call, and recurse
into the next phase, passing the table as argument, like


"compile" ( text ) -> code


could be implemented as (extremely simplified)


[] compile(text) = code
when ast := parse(text),
            sym := new-single-layer(new-null-layer),
            sym2, ast2 := typecheck(sym, ast),
            code := codegen(sym2, ast2)


ie, to execute "compile(text)", first do "ast := parse(text)", then "sym :=
new-single-layer(new-null-layer)", etc, until you have done "code :=
codegen(sym2, ast2)". Finally, return the code by "= code" at the first line.


Each successive call takes arguments returned as results by the previous call.




Does this answer your question?


Albert

Return to the comp.compilers page.
Search the comp.compilers archives again.