[SOLVED] Objects and assignment in interpreter

MTK358 · 02-14-2011, 08:10 AM

Could you explain to me how your idea of separating the internal value and objects works? Is the RHS always an internal value with the = operator, and an object with the := operator? Anyway, just help tell me how it works.

Quote:

Originally Posted by Nominal Animal

If there exists a.c.d, then where are the facts that d is a member of c and c a member of a defined? I mean the actual C data structures.

This is how my current env structure is like:

Code:

typedef enum {
    ENVTYPE_GENERIC,
    ENVTYPE_NUMBER,
    ENVTYPE_STRING,
} envtype_t;

typedef struct env env_t;
struct env {
    object_TEMPLATE // macro defining members common to everything that can be stored in a variable
    env_t *parent;
    array_t *keys;
    array_t *values;
    envtype_t envtype;
    void *internal_data;
};

And remember, the internal_data is not accessible from the program. The langauge itself has no concept of it.

For example, a number object will create a new env, set its type to ENVTYPE_NUMBER, and set its internal data to point to a double.

There are no operators, just functions that are children of the object. These functions' scopes are are to the number object itself, which means they can access the internal value like this: *((double*) scope->parent->internal_data).

And even for printing objects as text, there will be no accessing the internal value from the program. Instead, the string conversion function will check if the object has a "convert to string" method, and if not, it would just print the object type and memory address.

Nominal Animal · 02-14-2011, 03:41 PM

Quote:

Originally Posted by MTK358

Could you explain to me how your idea of separating the internal value and objects works? Is the RHS always an internal value with the = operator, and an object with the := operator? Anyway, just help tell me how it works.

You got it right.

The = is an operator which takes the internal value of the right hand side, and copies it to the internal value of the object on the left hand side. In the abstract syntax tree, both left and right sides are expressions that evaluate to an object.

The := is an operator which copies the right hand side object to the left hand side. This includes the internal value and all member objects.

Other than the internal value, I describe everything using the container_t type. At each point in time, the interpreter has two nameless container_ts as scopes: one is the local scope, and contains all local variables as children, and the other is the global scope, and contains all global variables as children.

When the interpreter encounters the expression a.b.c, it will first check the local scope for any immediate children named a. If not found, it'll check the global scope for any immediate children named a. If not found, then the expression does not match any existing object.
If a.b.c does exist, then that search will yield a pointer to a, and it will have an immediate child named b, and that will have an immediate child named c.

If you want to copy object a (the := operator here), you duplicate the container_t tree starting at a, names and child objects and all.
Because I use a tree structure, I can just recursively clone each child object.
Because the internal value is stored separately in a typed storage_t structure, I can trivially copy internal values from object to another, without copying the objects or any of their children/members.

In other words, d = a, or internal value assignment, is implemented like this:

The interpreter evaluates the left hand side abstract syntax tree. The result is a pointer, say container_t *left, to the object d.
The interpreter evaluates the right hand side abstract syntax tree. The result is a pointer, say container_t *right, to the object a.
The interpreter duplicates the storage from right to left. Effectively, in C, left->storage = right->storage;
To avoid memory leaks and to allow garbage collection, you need to of course free the old storage and logically duplicate the new storage, but I use reference counting and a garbage chain for that; I "detach" left->storage first, then "attach" to the new storage pointed to by right->storage. That's just bookkeeping you can ignore for now.

Normal object assignment d := a starts the same, but has further steps:

The interpreter evaluates the left hand side abstract syntax tree. The result is a pointer, say container_t *left, to the object d.
The interpreter evaluates the right hand side abstract syntax tree. The result is a pointer, say container_t *right, to the object a.
The interpreter duplicates the storage from right to left.
(Note that there may not be any storage to duplicate, if the object(s) do not have an internal value. The pointers are just NULL then.)
The interpreter discards the entire tree of container_ts hanging off of left->child.
(This discards all member objects from the left-hand side.)
The interpreter creates an exact duplicate tree of container_ts hanging off of right->child, and hangs it on left.

When I said I was lazy, I really meant that. Object assignment needs about three dozen lines of C code more -- two helper functions: one to destroy a tree of containers, and one to duplicate a tree of containers.

Quote:

Originally Posted by MTK358

There are no operators, just functions that are children of the object.

That won't work for assignments, since the child object cannot know which of its parents was referred to in the current expression. If you consider a.(b.c = d) (shorthand for a.b.c = a.d), you see there is no way for c to determine whether it should replace its parent b or grandparent a.

Ah, I now understand your original dilemma! What a long and circuitous route it has been

If you differentiated between statements and expressions, you could temporarily detach the first env on the left hand side you encounter when evaluating any statement, but it would be a fragile hack. And I remember you don't want to differentiate statements and expressions anyway.

I believe you must have at least an assignment operator as a real operator the interpreter handles internally. Then, you could handle the assignment very much the same way I do, except with envs instead of containers. If you think about it, assignment is special, so you're not compromising anything.

Nominal Animal

MTK358 · 02-14-2011, 04:33 PM

Assignment (along with member access) is a real operator, not a function.

Also, the idea was not to make a copy of the object, but to make another reference to it (like Java). For example:

Code:

MyObject = func
    value = 0

    setValue = func x
        value = x
    end

    getValue = func
        value
    end

    this
end

a = MyObject()
a.setValue(5)

b = a
b.setValue(8)

a.getValue() # evaluates to 8 (not 5)
b.getValue() # evaluates to 8

Nominal Animal · 02-14-2011, 06:55 PM

Quote:

Originally Posted by MTK358

Assignment (along with member access) is a real operator, not a function.

Good, then I think this is feasible.

Quote:

Originally Posted by MTK358

Also, the idea was not to make a copy of the object, but to make another reference to it (like Java).

Okay, that changes my model.

So a = b makes a an alias of b, so that all changes to either one will show up in the other, too? To create a new object by just copying all members and data, you use e.g. a = b.duplicate()? But if you do a = c then b is not affected (so b != c), right?

In the interest of being as clear as possible, I'll use new names for these modified structures:

reference_t - A type that names a variable or a member, and refers to an object (of generic_t type)
generic_t - A generic object type, pretty close to your env concept
data_t - Polymorphic structure describing internal object contents, like numbers, strings and functions

I'll still use trees instead of arrays, because the allocations are much simpler. Here are the structure definitions in C:

Code:

#include <stdlib.h>
#include <stdint.h>
#include <string.h>

enum data_type {
    TYPE_STRING = 1,
    TYPE_INTEGER,
    TYPE_DOUBLE,
    TYPE_FUNCTION,
};

typedef struct reference reference_t;
typedef struct generic generic_t;
typedef struct data data_t;


/* Payload data structures:
*/

struct integer_payload {
    int64_t value;
};

struct double_payload {
    double value;
};

struct string_payload {
    size_t length;
    unsigned char string[];
};

struct function_payload {
    /* Persistent scope for closures, NULL for normal functions */
    struct generic *scope;
    /* Function code to execute, one will be always NULL */
    struct generic *(*builtin)(struct generic *, struct generic *);
    struct node *script;
    /* Function parameter names and default values. */
    size_t parameters;
    struct reference *parameter[];
};


/* This type names an object.
*/
struct reference {
    struct reference *garbage;
    struct generic *object;
    long references;
    size_t name_length;
    unsigned char name[];
};

/* This type defines an instance of an object.
*/
struct generic {
    struct reference *child; /* First child */
    struct reference *next; /* First sibling */
    long references;
    struct data *value;
};

/* This type defines the internal value of an object.
* This is polymorphic, and follows C99 rules for aliasing.
*/
struct data {
    struct data *garbage;
    long references;

    enum data_type type;
    union {
        struct integer_payload integer;
        struct double_payload number;
        struct string_payload string;
        struct function_payload function;
    } payload[];
};


/* Here is how to allocate data for an integer:
*/
struct data *new_data_integer(const int64_t value)
{
    const size_t bytes = sizeof(struct data)
                       + sizeof(struct integer_payload);
    struct data *data;

    data = malloc(bytes);
    if (!data)
        return NULL;

    data->chain = NULL;
    data->references = 0L;
    data->type = TYPE_INTEGER;
    data->payload[0].integer.value = value;

    return data;
}


/* Here is how to allocate data for a string:
*/
struct data *new_data_string(const void *const string, const size_t length)
{
    const size_t bytes = sizeof(struct data)
                       + sizeof(struct string_payload)
                       + (length | (size_t)7) + (size_t)1;
    struct data *data;

    data = malloc(bytes);
    if (!data)
        return NULL;

    /* Clear end of string, including padding (1 to 8 zeros) */
    memset((char *)data + bytes - 8, 0, (size_t)8);

    data->chain = NULL;
    data->references = 0L;
    data->type = TYPE_STRING;
    data->payload[0].string.length = length;
    memcpy(data->payload[0].string.string, string, length);

    return data;
}

The memory allocation for polymorphic objects conforming to C99 aliasing rules is a bit complicated, and the payload references funny, so I added code on how to create integer or string data.

Reference counting is used on all three types for automatic garbage collection and copy-on-write optimizations. The garbage fields in the data_t and reference_t are only used to chain them when they are in the garbage; the next field is reused for that in the generic_t type. In all types, the references fields tells how many different pointers point to this object. When this drops to zero, it will be moved to the garbage chain, to be collected later, at a point when the interpreter threads don't have temporary internal pointers pointing to these lying around.

It is important that you notice how reference_t and target_t types are intertwined: their pointers always point to things of the other type, never to the same type as themselves. This is absolutely required to get the object aliasing right with sensible code.

So, logically having a.b == "c" means that following C data structures must exist (ignore the C variable names):

Code:

reference_t *variable_a;
generic_t   *object_a;
reference_t *member_b;
generic_t   *object_b;
data_t      *value_c;

variable_a->object == object_a;
variable_a->name_length == 1;
variable_a->name == "a";

object_a->child == member_b;
object_a->next == NULL;
object_a->value == NULL;

member_b->object == object_b;
member_b->name_length == 1;
member_b->name == "b";

object_b->child == NULL;
object_b->next == NULL;
object_b->value == value_c;

value_c->garbage == NULL;
value_c->type == TYPE_STRING;
value_c->payload[0].string.length == 1;
value_c->payload[0].string.string == "c";

To evaluate a = b, you first evaluate the left hand side to find out the variable or member (reference_t *left) to assign to. Then you evaluate the right hand side to find out the object (generic_t *right) to assign.
Then you discard the entire tree of objects starting at left->object, and replace it with a duplicate of (the entire tree) right. In C, this is just a glorified left->object = right; except that first the new generic_t/reference_t tree is walked thorough and each reference count increased, then the old generic_t/reference_t is walked to decrease the reference counts and unused items moved to the garbage chains, and then the actual assignment is done.

If the left hand side is an anonymous expression, you create an anonymous reference to it first (an reference_t structure with empty name). That way all expressions are actually evaluated to a reference_t. (For right hand sides in an assignment, generic_t *right = ((reference_t *)right_hand_side)->object.)

Duplication is essentially the same as assignment, except that instead of increasing the reference counts, you actually duplicate the memory structures too. (After duplication, the duplicated structures' reference counts are of course all 1.)

Defining a variable scope is easy. Just create an empty generic_t, and add all variables as its children, remembering to increase the reference count for each.

Does this help? I can write an actual example program, but not before the weekend at least.

Nominal Animal

MTK358 · 02-14-2011, 07:04 PM

No, you don't understand: ALL variables are references. It's impossible to create a variable that's not a reference and somehow directly contains the object.

env's contain dynamic arrays full of pointers to other objects.

Also, I have another question about you not using arrays but sibling objects: You have a separate data and object type field for every child object. What's that all about?

Nominal Animal · 02-14-2011, 07:49 PM

Quote:

Originally Posted by MTK358

No, you don't understand: ALL variables are references.

I do understand. The structures reflect exactly that.

Quote:

Originally Posted by MTK358

It's impossible to create a variable that's not a reference and somehow directly contains the object.

Each variable and member is named by a reference_t, which points to the object generic_t it refers to. All variables are references.

Quote:

Originally Posted by MTK358

Also, I have another question about you not using arrays but sibling objects: You have a separate data and object type field for every child object. What's that all about?

Objects themselves are just bucket-like containers. The type depends on the value, not on the object. It does not matter to the bucket if you put in a stone or a liter of water. So putting the type where the value is stored is natural to me.

To implement arrays or lists, I just create new child members (reference_t pointing to the desired generic_t objects), and name them (the reference_t) by the indices or keys -- just like you would for member objects. For a list or collection type without indices, the child members can be anonymous (then each reference_t has an empty name field.)
My foreach loops could look for example like this:

Code:

foreach a.[^[0-9]+$] as x:
    # x is now a member of a, having a name containing only digits 0-9.

where the foreach syntax is foreach list as variable: statement and a.[pattern] evaluates to an anonymous list of all members of a having a name that matches pattern.

(The reason I insist on differentiating between expressions and statements is that it does make the intepreter simpler, and I appreciate simplicity.)

Nominal Animal

MTK358 · 02-14-2011, 08:25 PM

I think the type should be stored in the object itself, not the parent. Doesn't that make far more sense?

Nominal Animal · 02-14-2011, 08:44 PM

Quote:

Originally Posted by MTK358

I think the type should be stored in the object itself, not the parent. Doesn't that make far more sense?

Who is storing the type in the parent? I'm definitely not, I'm storing the type with the value. The type is irrelevant to me, unless the value itself is used.

Nominal Animal

MTK358 · 02-15-2011, 07:52 AM

I was wrong, I got confused. It's just that this is my env struct:

Code:

typedef struct env env_t;
struct env {
    OBJECT_TEMPLATE
    env_t *parent;
    array_t *keys;
    array_t *values;
    envtype_t envtype;
    void *internal_data;
};

the envtype member says what kind of object this is (including ENVTYPE_GENERIC for scopes and objects that are created by the user and have no internal value).

If you would take this and replace he keys array with a pointer to a sibling, then the internal_data and envtype fields would be needlessly duplicated for each child, right?

Quote:

Originally Posted by Nominal Animal

My foreach loops could look for example like this:

Code:

foreach a.[^[0-9]+$] as x:
    # x is now a member of a, having a name containing only digits 0-9.

where the foreach syntax is foreach list as variable: statement and a.[pattern] evaluates to an anonymous list of all members of a having a name that matches pattern.

(The reason I insist on differentiating between expressions and statements is that it does make the intepreter simpler, and I appreciate simplicity.)

Makes the interpreter simple? Check out LISP. Writing an interpreter for it is ridiculously simple compared to just about any other language. And it has no concept of statements, just expressions.

And the foreach construct, I really dislike it. And there is a real, popular language that does a similar thing: Ruby.

I think it's bad to make the syntax and data types more interdependent. Why complicate the interpreter when you can write loops as methods of objects? You can even write the loop method in the language itself instead of C:

Code:

number = 10

number.foreach = func f
    i = 0
    while i < number
        f(i)
    loop
end

And I see separating statements and expressions as limiting. Why shouldn't you be allowed to put an if construct within an expression? And since the evaluation function evaluates everything to a value anyway (including if constructs, loops, etc.), this is not hard at all to implement. In fact, not allowing it in the syntax would be just a big waste!

Nominal Animal · 02-15-2011, 07:32 PM

Quote:

Originally Posted by MTK358

I was wrong, I got confused. It's just that this is my env struct:

Code:

typedef struct env env_t;
struct env {
OBJECT_TEMPLATE
env_t *parent;
array_t *keys;
array_t *values;
envtype_t envtype;
void *internal_data;
};

the envtype member says what kind of object this is (including ENVTYPE_GENERIC for scopes and objects that are created by the user and have no internal value).

If you would take this and replace he keys array with a pointer to a sibling, then the internal_data and envtype fields would be needlessly duplicated for each child, right?

Do all members of an env have the same type and internal data as the env? I thought they were private to each member.
Does the keys array contain the keys of every member of that object? Including all methods?

Quote:

Originally Posted by MTK358

Makes the interpreter simple? Check out LISP. Writing an interpreter for it is ridiculously simple compared to just about any other language. And it has no concept of statements, just expressions.

I meant that when using the data structures I in my example program, the interpreter is simpler if you handle expression evaluation and statement evaluation in different functions. They can and do call each other, so you don't need the distinction in the language. It was just an implementation note.

Quote:

Originally Posted by MTK358

And the foreach construct, I really dislike it.

Yeah, it was just an idea.

Quote:

Originally Posted by MTK358

I think it's bad to make the syntax and data types more interdependent.

Yes, I agree. But in my defense, I was thinking about [pattern] being a generic expression, which evaluates to the list of names matching pattern in the current scope. In the foreach example, the scope is just the specified object. I do prefer built-in language constructs (loops and conditionals at least), but I think a couple of dozen at most is enough for me. I know you disagree.

Quote:

Originally Posted by MTK358

Why complicate the interpreter when you can write loops as methods of objects?

For efficiency. The use cases I envision for a script language like this are embedded ones: as server-side scripts, or as an embedded scripting language for a larger program. In both cases it would be best to minimize the memory footprint of each instance; tight objects are a big plus. I'm not striving for any specific kind of language, as long as it handles strings, lists and arrays fast and efficiently. So, I guess our goals differ quite a bit.

Nominal Animal

MTK358 · 02-15-2011, 07:36 PM

Quote:

Originally Posted by Nominal Animal

Do all members of an env have the same type and internal data as the env? I thought they were private to each member.

What do you mean?

Quote:

Originally Posted by Nominal Animal

Does the keys array contain the keys of every member of that object? Including all methods?

It contains the names of the child object. The values array contains the objects themselves. This is how you get a reference to a child:

Code:

array_get(values, array_indexof(keys, name))

Quote:

Originally Posted by Nominal Animal

Yes, I agree. But in my defense, I was thinking about [pattern] being a generic expression, which evaluates to the list of names matching pattern in the current scope. In the foreach example, the scope is just the specified object. I do prefer built-in language constructs (loops and conditionals at least), but I think a couple of dozen at most is enough for me. I know you disagree.

The number object 10 does not contain children 1, 2, 3, 4, 5, 6, 7, 8, and 9. Its internal_data pointer points to a C double with the value of 10.0.

EDIT: Here's a tree of what the tree of envs looks like when you define a number object:

Code:

<unnamed scope env> (objtype: env, envtype: generic, internal value: NULL)
|
+-mynumber (objtype: env, envtype: number, internal value: points to double)
  |
  +-__op_add (objtype: function)
  +-__op_sup (objtype: function)
  +-foreach (objtype: function)
  |
  etc...

Nominal Animal · 02-15-2011, 08:17 PM

Quote:

Originally Posted by MTK358

What do you mean?

If you write the same diagram for a.foo.mynumber, don't you get

Code:

<unnamed scope env> (objtype: env, envtype: generic, internal value: NULL)
  │
  └─foo (objtype: env, envtype: generic, internal value: NULL)
     │
     ├─mynumber (objtype: env, envtype: number, internal value: points to double)
     │ │
     │ ├─__op_add (objtype: function)
     │ ├─__op_sub (objtype: function)
     │ ├─foreach (objtype: function)
     │ │
     │ etc...
     │
     ├─foreach (objtype: function)
     │
     etc..

If the above is correct, you do need the envtype and internal value in each env. Or did I misunderstand?

Quote:

Originally Posted by MTK358

The number object 10 does not contain children 1, 2, 3, 4, 5, 6, 7, 8, and 9. Its internal_data pointer points to a C double with the value of 10.0.

Yes, I understood that it is the foreach member function to the number object which generates the number objects internally, and evaluates its parameter expression for each one.

MTK358 · 02-15-2011, 08:26 PM

Quote:

Originally Posted by Nominal Animal

Or did I misunderstand?

A little. It's:

Code:

<unnamed scope env> (objtype: env, envtype: generic, internal value: NULL)
│
└─foo (objtype: env, envtype: generic, internal value: NULL)
  │
  ├─mynumber (objtype: env, envtype: number, internal value: points to double)
  │ │
  │ ├─__op_add (objtype: function)
  │ ├─__op_sub (objtype: function)
  │ ├─foreach (objtype: function)
  │ │
  │ etc...
  │
  ├─foreach (objtype: function) There is no foreach here! Generic envs are EMPTY when created, you add everything. 
  │
  etc..

MTK358 · 02-17-2011, 12:43 PM

Anyone?

MTK358 · 02-18-2011, 01:14 PM

I figured out functions (by putting arrays in the nodes' payload) and assignment (by adding a node that evaluates to the env and a note that evaluates to the value as children, and the name in the payload). Once I fix all the compiler errors it should be able to interpret an AST defined in main().

But there's this error:

Code:

function.h:13:18: error: expected ‘)’ before ‘*’ token
function.h:13:36: warning: no semicolon at end of struct or union

and I have no idea what's wrong. And about half of all the other errors are caused by this one.

Here's the code:

function.h

Code:

#ifndef __FUNCTION_H_INCLUDE_GUARD__
#define __FUNCTION_H_INCLUDE_GUARD__

#include "object.h"
#include "array.h"
#include "env.h"

#define function_TEMPLATE \
    object_TEMPLATE \
    array_t *param_names; \
    env_t *env; \
    object_t* (*call)(function_t*, array_t*);
typedef struct { function_TEMPLATE } function_t; // this is line 13, the one with the error

#endif

object.h

Code:

#ifndef __OBJECT_H_INCLUDE_GUARD__
#define __OBJECT_H_INCLUDE_GUARD__

typedef enum { OBJTYPE_FUNCTION, OBJTYPE_ENV } object_type_t;

#define object_TEMPLATE \
	object_type_t objtype;
typedef struct { object_TEMPLATE } object_t;

#endif