Structures¶

I created Idio’s structures as a sawn-off version of LiSP’s MEROONET object-oriented objects (as I want to go down the Tiny-CLOS route for object-oriented objects) but before seeing SRFI-9’s Record Types.

Idio structures are similar to but not the same as Scheme Records. Ultimately, what we want is an object that has named fields which we can access by, er, name.

It’s a naming mess and I cannot claim to have helped the situation in any way.

At this point, the words object and value become even closer entwined as these structure values are a reduced form of another language’s object oriented objects. Indeed, they might even be the basis of an implementation of Tiny-CLOS’ objects.

This isn’t helping either as we now have to manipulate a structure type and a structure instance in the same code block.

I often end up with st and si initialisms.

I think we’ve seen the broad idea: we define a structure type which gives the structure and its fields names and then we go onto create instances of that structure type.

For a structure type:

define-struct bar x y

which creates a structure type called bar with fields x and y. This declaration of which would create a number of structure manipulation functions such as make-bar and bar?.

For a structure instance:

foo := make-bar 1 2

whereon I can access the elements with getters and setters:

bar-x foo            ; 1
set-bar-y! foo 10
bar-y foo            ; 10

or the more visually pleasing (but computationally expensive):

foo.x                ; 1
foo.y = 10
foo.y                ; 10

Ideally, with some savant type inference, we might determine that foo is an instance of bar and substitute in the most efficient structure accessing methods possible. In the meanwhile ./value-index has to work things out the hard way.

Features¶

One aspect of these structures, due to their provenance, is that internally they support a hierarchy. This is most visible with conditions:

Idio> help ^rt-hash-key-not-found-error
struct-type: ^rt-hash-key-not-found-error  > ^runtime-error > ^idio-error > ^error > ^condition

fields (message location detail key)

Here we’re seeing that ^rt-hash-key-not-found-error is derived from a ^runtime-error which is derived from an ^idio-error which is derived from an ^error which is derived from a ^condition.

^rt-hash-key-not-found-error appears to have four fields, message, location, detail and key, although the first three are actually defined alongside ^idio-error and all derived conditions inherit those three fields. ^rt-hash-key-not-found-error has added the key field which is relevant to the condition.

We can’t use inheritance for Idio-defined structure types because of an issue with recursing up the inheritance tree to find out what fields have been previously defined in order that we can define a complete set of accessors. (This is partly because we could try to define a structure type using a parent type that hasn’t been defined yet.)

However, where we can inherit, then, for both the structure type and the structure instance the array of fields (symbols or values respectively) is the collection of all inherited fields. So, the structure type for ^rt-hash-key-not-found-error will have four field names in its structure, the combination of the three it has inherited plus the one defined for itself. Correspondingly, an instance of that type will have four values.

Implementation¶

For structure types:

gc.h¶

typedef struct idio_struct_type_s {
    struct idio_s *grey;
    struct idio_s *name;                     /* a symbol */
    struct idio_s *parent;                   /* a struct-type */
    size_t size;                             /* number of fields *including parents* */
    struct idio_s* *fields;                  /* an array of symbols */
} idio_struct_type_t;

#define IDIO_STRUCT_TYPE_GREY(ST)            ((ST)->u.struct_type->grey)
#define IDIO_STRUCT_TYPE_NAME(ST)            ((ST)->u.struct_type->name)
#define IDIO_STRUCT_TYPE_PARENT(ST)          ((ST)->u.struct_type->parent)
#define IDIO_STRUCT_TYPE_SIZE(ST)            ((ST)->u.struct_type->size)
#define IDIO_STRUCT_TYPE_FIELDS(ST,i)        ((ST)->u.struct_type->fields[i])

Where, using the examples above:

name is the symbol bar or ^error
parent is #n or ^condition
size is 2 or 0
fields is a C array of Idio symbols as we will (ultimately) index into them with an integer

For structure instances:

gc.h¶

typedef struct idio_struct_instance_s {
    struct idio_s *grey;
    struct idio_s *type;                     /* a struct-type */
    struct idio_s* *fields;                  /* an array of values */
} idio_struct_instance_t;

#define IDIO_STRUCT_INSTANCE_GREY(SI)        ((SI)->u.struct_instance.grey)
#define IDIO_STRUCT_INSTANCE_TYPE(SI)        ((SI)->u.struct_instance.type)
#define IDIO_STRUCT_INSTANCE_FIELDS(SI,i)    ((SI)->u.struct_instance.fields[i])

#define IDIO_STRUCT_INSTANCE_SIZE(SI)        (IDIO_STRUCT_TYPE_SIZE(IDIO_STRUCT_INSTANCE_TYPE(SI)))

where:

type is a reference to a structure type (duh!)
fields are a C array of Idio values which we can index with an integer

Clearly, the accessor functions can be made to be relatively quick if we can translate a field name into a field index after which accessing a structure instance’s field value is a simple array index.

Reading¶

There is no reader input form for either a structure type or a structure instance.

Writing¶

In both case we’ll use an invalid reader input form, #<...>.

For structure types we want to recurse through the structure inheritance hierarchy printing out field names as we go:

Idio> ^idio-error
#<ST ^idio-error #<ST ^error #<ST ^condition #n>> message location detail>

Note the leading ST for structure type. The #n following ^condition indicates that ^condition does not inherit from anything else, it is the root of this hierarchy.

For structure instances we want the structure type and the values of the fields (with their names!):

Idio> make-condition ^idio-error "msg" "loc" "det"
#<SI ^idio-error message:"msg" location:"loc" detail:"det">

Note the leading SI for structure instance.

C / Idio Overlap¶

Manipulating structure types is complicated because there are several types which we want to manipulate in both C and Idio – conditions are the obvious example: they are generally raised in C and we want to write handlers for them in Idio.

The structure type is defined in C, usually, as it is needed long before the VM gets to run. C however, can manipulate the structure elements directly and doesn’t need accessors etc.. All it does need to do is add the structure type’s name into the environment.

That itself is repetitive and mildly complicated, so there are a bunch of C macros to help. For conditions:

condition.h¶

#define IDIO_DEFINE_CONDITION0(v,n,p) ... *stuff*

where

v is the C variable name we want to manipulate (which was declared with external linkage etc.)
n is the C string name – to be converted to an Idio symbol
p is the parent type

The 0 in the C macro name is indicating that there are zero fields associated with this condition type.

IDIO_DEFINE_CONDITION2(v,n,p,f1,f2) indicates there are two fields to be added.

The macros get used in the likes of:

idio_init_condition() in src/condition.c¶

IDIO_DEFINE_CONDITION0 (idio_condition_error_type,
                        "^error",
                        idio_condition_condition_type);

*

Idio, on the other hand, only needs the accessors – so long as the name exists. However, we can flip things around a bit. Rather than having two roughly similar forms we can make define-struct a wrapper to what would have been the specialized define-struct-accessors-only.

struct.idio¶

define-template (define-struct name & fields) {
  #T{
    ;; define bar (make-struct-type 'bar #n '(x y))
    define $name (make-struct-type '$name #n '$fields)

    define-struct-accessors-only $name $@fields
  }
}

This requires a make-struct-type name parent fields form (in src/struct.c) which will return a structure type value which is set in the environment as $name – define-struct is a template, remember, so $name expands out to whatever the first argument to define-struct was.

Note that the parent argument is always #n.

define-struct-accessors-only is now the generic form for constructing all the accessory methods: make-name, name? etc..

define-struct-accessors-only (in lib/struct.idio) is quite complicated as it involves templates generating templates using constructed and generated symbols. There’s some examples in the commentary that show the expanded forms which might make it a bit easier to read.

Now we have define-struct-accessors-only we can use it for our conditions (defined in C) … except – for reasons I don’t quite recall but I’m sure they were good – conditions have a similar but not quite the same system. So, in fact, we call:

condition.idio¶

define-condition-type-accessors-only ^error ^condition error?

which is going to define error? as a predicate testing that the value passed is a condition and is an instance of the ^error condition type. There are no fields so no field accessors are created.

condition.idio¶

define-condition-type-accessors-only ^rt-hash-key-not-found-error ^runtime-error rt-hash-key-not-found-error? \
     (key rt-hash-key-not-found-error-key)

Here, in addition to the rt-hash-key-not-found-error? predicate we will define an accessor, rt-hash-key-not-found-error-key for the field key.

Arguably we could have derived the accessor name from the condition type name and the key but this method allows some flexibility in naming.

Operations¶

Structure Types¶

function make-struct-type name parent fields¶: create a structure type called name with inheriting from the parent structure type and adding fields

function struct-type? value¶: Is value a structure type

function struct-type-name st¶: return the structure type’s name from st

function struct-type-parent st¶: return the structure type’s parent from st

function struct-type-fields st¶: return the structure type’s fields from st

function struct-type-isa st type¶: return #f unless the structure type of st is type in which case return #t

function struct-type-isa st type¶: return #f unless the structure type of st is type in which case return #t

Structure Instances¶

function make-struct-instance st values¶: create a structure instance of structure type st with values values

function struct-instance? value¶: Is value a structure instance

function struct-instance-type si¶: return the structure instance’s structure type from si

function struct-instance-fields si¶

return the structure instance’s fields from si

This is returning the values of the structure instance. I guess the name could be better…

function struct-instance-ref si field¶

return the value of field from structure instance si

If field is not a field of the type of si then a ^runtime-error condition will be raised.

function struct-instance-set! si field value¶

set the value of field field in structure instance si to be value