On 25/3/06 3:53 PM, "John Cowan" <
cowan@...> wrote:
> Can someone (probably Manfred) explain to me how modules and hiding work
> in Joy0/Joy1? That was a part of the source I didn't need to figure
> out in revising Joy0 to make Joy1, and it's pretty hard to follow.
>
> I have deduced that it's the definitions of symbols rather than the
> symbols themselves that are different inside a module. Where are these
> definitions stored, and how are they revived when you invoke a public
> function?
First, some general comments.
The symbol table and its associated functions could be implemented in
several ways. The choice would depend much on what the implementation
language has to offer. But it also depends on what the implementor¹s
brainware has to offer. I made some choices, partly based on what I was
familiar with, and partly on what I was able to pick up on the fly. This was
my first attempt at using a hash method: when encountering a symbol, use a
crude hash function to compute a small number (0..9 originally), have an
array (size 10) as starting points for (10) linear lists (in fact, treated
as stacks) of structs of strings (the names) and other info. It seems to
have worked.
All built-ins are entered at start-up time, by hashing the name and consing
a new element into the linear list. Then, when in definition mode and
reading ³foo == ... bar ...², cons foo into its list, possibly shadowing an
inbuilt foo. When reading the body, and encountering bar, find bar in its
list. Do the same when not in definition mode and reading ³...baz...² So far
this is probably obvious for an implementation in C. But it is not obvious
that a Scheme implementation should follow all the details I only know
about the core concepts of Scheme, and not about the procedural parts,
especially of what the Chicken Scheme compiler can handle. I think you
should select whatever you find clearest and what you find clearest will
quite likely be what others will find clearest.
But you question was about modules and hiding. Let me take hiding first,
because it is easiest. The idea was to supply a particularly simple
structuring tool, comparable procedures/functions to that are local to other
procedures/functions in Pascal, or functions that are only visible to other
functions in the same file in C. Basic principle: Hide details of
subprograms from other subprograms that do not have to know about the
details, not even the names. Consider
HIDE
h1 == ...; h2 == ...; h3 == ...
IN
g1 == ...; g2 == ...; g3 == ...
END
Think of HIDE..END as brackets, the whole can stand wherever a single
definition foo == ... can stand, just as in arithmetic (2+3) can stand
wherever a single number can stand. The whole defines three Joy functions g1
g2 g3 that will be visible outside, normally as globally defined (but HIDE¹s
can actually be nested if one really wants it). The bodies of the the g¹s
can refer to any one of the three hidden h¹s. But after the END, the h¹s
disappear from view, only their bodies are still stored since they might be
used by any one of the g¹s. How is all this to be implemented? I reasoned
that hashing is good for the all the inbuilts and the globally defined
library and user functions, which will never be deleted (although they might
be shadowed). But the number of hidden h¹s inside a HIDE will never be
large, and so a single simple list should suffice, and no hashing is used.
This has to be what the parser does: seeing ³HIDE², start a single list of
local definitions, seeing h1 h2 h3 enter these in that list, process the
bodies ... as usual and hook the generated code to the local definitions.
When processing the bodies ... of the h¹s, first start the search in the
local list, and only when nothing has been found search the hashed large
table as normal. When reaching the IN, go in a different mode: any new
definition g1 g2 g3 is entered as if there had not been any hidden
definitions (so normally the hashed global part of the table, unless inside
a nested HIDE). But when the bodies of the three g¹s are processed, the
local list is searched first in case what was encountered was one of the
three h¹s. Finally, when END is encountered, delete (or make invisible) the
single list of hidden locals h1 h2 h3. This deletion of a single list is
much simpler than in would have been if the locals had gone through the
normal hashing process. What remains in the symbol table is just the three
g¹s, but the names of the three h¹s have disappeared.
My implementation of HIDE contains one error, which I first encountered when
I wrote the miniLISP which needs two mutually recursive functions eval and
apply. I would have liked to make them hidden, but my HIDE could not handle
the mutual recursion. So I made eval and apply global, and then mutual
recursion is not a problem. But I never got around to fixing mutual
recursion of hidden functions. Such definitions should look like this:
1 HIDE
2 eval == ³forward² ; # or anything else, say 42
3 apply == ...eval...eval... ;
4 eval == ...apply...apply...
5 IN
The definition in line 2 just enters the name eval into the local table,
with an arbitrary body that will be changed later. In line 3 the definition
of apply uses eval as normal. But now in line 4 eval is encountered again,
on the left side of ==. My implementation gets it wrong here, it enters the
name eval a second time into the list of local definitions, shadowing the
first. But apply already generated code ³forward² for the earlier version of
eval, and hence the new, required version of eval in line 4 is not called by
apply. To correct it, this should be done: After encountering HIDE, start a
new local list. Then, when a hidden definition is started (eval === ...),
first search just the local list, if not found then enter new (line 2), but
if found then use that (line 4). In either case hook the following body to
the table (and in line 4 this means overwriting the body that was there).
Your Chicken-Scheme implementation could try to fix this straight away.
Since HIDE¹s can be nested one might wonder whether all the local lists of
identifiers don¹t become too confusing. Actually this is not the case, since
in reality there only has to be one linear list of locals. On start up time
the list of locals is set to nil. Whenever HIDE is seen, the parser enters
the hiding mode, and among others this means saving in a local variable the
current linear list of locals (which may already contain something). Up to
the END, augment the local list as needed, and when END is seen, the parser
restores from the local variable the saved linear list of locals. Since the
list of locals is only augmented by consing new things to the front,
restoring
it to an earlier state just drops off the new things. I would think that any
implementation would use a very similar technique.
I realise that I still have not answered you question about modules, the
HIDE part took longer than I anticipated. But I¹ll have to study the code
for modules in some detail in order to avoid writing faulty documentation
that would only annoy you terribly. But much of it is of course similar to
the HIDE part. I¹ll come back to this within a week that¹s a long while,
but I am currently shifting after having lived in my house for 34 years ...
So please be patient.
- Manfred
[Non-text portions of this message have been removed]