Re: First try (was: Re: [Pika-dev] Re: willing to help)

[Tom Lord]

    > From: "Jose A. Ortega Ruiz" <address@hidden>

    > i've been reading docs and code (and learning tla,) and finally made a
    > first attempt at contributing some code, mainly to become familiar
    > with the project. more concretely, i've implemented hash_fn for
    > vectors and pairs. it's a very small contribution, hardly worth
    > noting, but, before going on, i would appreciate if any of you could
    > take a quick look at it to be sure that i'm on the right path. it is
    > available at:

    > Revision: scm--devo--0.1--patch-3
    > Archive: address@hidden

I'l take a look at that on monday.  You need to mention the location
of your archive, though.


    > and it consists mainly on adding a new function (scm_values_hash_acc)
    > to reps/hash-values-imp.c, and use it in scm_vector_hash_fn and
    > scm_pair_hash_fn. i've also added tests in separate files
    > (unit-vector-hash.c and unit-pair-hash.c), rather than modifying the
    > existing unit-vector.c and unit-pairs.c: is this compliant with our
    > coding policies? i've observed that 'make test' does not run the new
    > tests, despite the fact that they're compiled: how do i fix it?

(I'll take a look into that monday.)


    > also, i was expecting a reps/vector-impl.[ch] module, but didn't find
    > it: shouldn't it be there? 

No, and in fact, I'll probably move your code out of
reps/hash-values-imp.c and into libscm.

reps provide the lower level `vtable' meta-type and there can be
alternative implementations of that -- but vectors are generically
implemented on top of vtable objects.


    > on a related note, i've observed that reps uses now and then
    > stuff from libscm, which prevents a clean layering of both
    > libraries: i was expecting libscm to depend on reps, but not the
    > other way round, so that we have a nice layered
    > architecture. but this does not seem to be the case (actually,
    > i've also violated my proposal when implementing
    > scm_values_hash_acc, but i can easily fix it): am i missing
    > something?

It is nicely layered -- just not the way you expect.  "Encapsulated"
might be a better word than layered.

Basically, the lowest level details of object representations go in
reps.   The next-up level of details about number representations goes
in libscm-numbers-reps.   Those two directories are supposed to permit
multiple implementations but present stable interfaces.

Everything else goes in libscm and libscm-numbers and hopefully only
needs to be implemented just once.

It's just the nature of the beast that calls happen in both directions
-- but the calls in either direction are at least to fixed APIs.



    > i was also thinking of implementing the missing
    > scm_{pair,vector}_equal_fn functions, and actually wrote a first
    > attempt at scm_vector_equal_fn, but i don't understand the 'issues' in
    > the FIXME comment: circularity does not seem to be an issue, since
    > scm_values_equal already tests its arguments using scm_values_eq,
    > preventing in this way (if i'm not mistaken) infinite recursion when
    > comparing circular structures (i've in fact tested it for circular
    > vectors). thus, a very naive impl for vectors that firsts compares
    > their lengths and, if needed, checks in turn each of their components
    > using scm_values_equal seems to work--- but then, i don't know what
    > Tom meant in his comments with the 'interrupts and stack usage'
    > issues[1]: could you please elaborate on them so that i can try to
    > provide a robust implementation?


Consider, for example, two circular lists:


        a:              b:              c:
        ---------       ---------       ---------
        | 0 | *-|------>| 0 | *-|------>| 0 | * |
        ---------       ---------       ------|--
        ^-------------------------------------'


        d:              e:
        ---------       ---------
        | 0 | *-|------>| 0 | * |
        ---------       ------|--
        ^---------------------'

and asking if A and D are EQUAL?.   Well, they have the same CAR (0),
so do they have the same CDR?   We compare B and E.   They have the
same CAR (0) but do they have the same CDR?   We compare C and A.
and so on.

In principle one could decide that EQUAL? tests for "graph
isomorphism" of circular structures.   Unfortunately, graph
isomorphism is necessarily far more expensive than just the naive
EQUAL? that work on non-circular structures.

So EQUAL? pretty has to be non-terminating in such cases.  But in an
interactive application, using Pika as an extension language, it's not
desirable to just hang forever.   The user should be able to interrupt
an operation like EQUAL? (like hitting ^G in emacs).

In the low-level primitives currently being written, the plan is to
permit interruption by having those primitives periodically poll and,
if the poll says there is an interrupt pending, return an error.   I
haven't yet put in the polling code -- so please just leave a "#undef
FIXME" there for the circularity issue.




    > i could also try my hand on reading/writing circular structures. it
    > seems that the place to handle them is scm_write_value, storing
    > information about already printed objects in a new field within
    > scm_write_params (which could be, for instance, a hashmap
    > t_scm_word * -> index, where the keys are pointers to already printed
    > objects and the values are indexes for already referenced ones). but i
    > am probably missing a lot of relevant issues here, am i not?

That should wait at least for vector-based hash tables -- but most
probably circular read and write will be coded in Scheme and compiled.


    > well, i think that's all by now :) i know that i'm actually wasting
    > more of your time that my current contributions are worth, but please
    > bear with me: hopefully, the terms will be inverted as soon as i'm
    > familiar enough with pika :)

I don't feel that my time has been wasted.   Thanks for your help.  I
hope my answers aren't to horrible. :-)

-t