[Caml-list] Interpreting a language with (sparse) arrays explicitly indexed

[Caml-list] Interpreting a language with (sparse) arrays explicitly indexed

[Diego Olivier Fernandez Pons]

[-- Attachment #1: Type: text/plain, Size: 1467 bytes --]

     Caml-list,

I have to write an interpreter for a language that has arrays explicitly
indexed by anything that can be sequential (list, range, set)

    {string} airports = {"ATL", "JFK"};
    range index = 1 .. 2;
    tuple recordAirport { airport : string; id : int }
    {recordAirport} otherAiports = { <"ATL", 12345>, <"JFK", 42>};

    int myArray [airports][index] = [[1, 2], [3, 4]];
    string myArray2 [a in recordAirports][i in index] = (i < a.id) ?
"unknown" : a.airport ;
    int mySliceOfArray [a in recordAirports]  = sum (i in index)
myArray[a.airport][i];

Usually the trick in interpreter implementation is to transform everything
back to "one-dimensional" objects
- simple types
- inductive constructions for lists
- curried functions

For instance in the book "Le langage Caml" the return type of the eval
function is

type value =
   | Val_number of int
   | Val_boolean of bool
   | Val_pair of value * value
   | Val_nil
   | Val_cons of value * value
   | Val_closure of closure
   | Val_primitive of value -> value
and closure = { definition: (pattern * expression) list; mutable
environnement: environnement }
and environnement == (string * value) list

I don't see however how I am going to represent a type Val_Array given that
the indexes can be of arbitrary type and in arbitrary number.
I haven't found either how to transform the arrays into inductive types like
lists to avoid the issue.

Any suggestions ?

        Diego Olivier

[-- Attachment #2: Type: text/html, Size: 2011 bytes --]

Re: [Caml-list] Interpreting a language with (sparse) arrays explicitly indexed

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 2162 bytes --]

What about hash tables ?

  | Val_table of (value, value) Hashtbl.t

If you have caml closures in your values (not in Val_closure but in
Val_primitive), it is maybe not appropriate to use the default hash function
that would choke on them. You should rather define your own hashing function
--but defining a mutually recursive `value` type and Hashtable.make
application will be delicate -- or change your representation of primitives
to avoid ocaml functions (by reifying them into a concrete datatype for
example).

On Tue, Oct 18, 2011 at 1:12 AM, Diego Olivier Fernandez Pons <
dofp.ocaml@gmail.com> wrote:

>      Caml-list,
>
> I have to write an interpreter for a language that has arrays explicitly
> indexed by anything that can be sequential (list, range, set)
>
>     {string} airports = {"ATL", "JFK"};
>     range index = 1 .. 2;
>     tuple recordAirport { airport : string; id : int }
>     {recordAirport} otherAiports = { <"ATL", 12345>, <"JFK", 42>};
>
>     int myArray [airports][index] = [[1, 2], [3, 4]];
>     string myArray2 [a in recordAirports][i in index] = (i < a.id) ?
> "unknown" : a.airport ;
>     int mySliceOfArray [a in recordAirports]  = sum (i in index)
> myArray[a.airport][i];
>
> Usually the trick in interpreter implementation is to transform everything
> back to "one-dimensional" objects
> - simple types
> - inductive constructions for lists
> - curried functions
>
> For instance in the book "Le langage Caml" the return type of the eval
> function is
>
> type value =
>    | Val_number of int
>    | Val_boolean of bool
>    | Val_pair of value * value
>    | Val_nil
>    | Val_cons of value * value
>    | Val_closure of closure
>    | Val_primitive of value -> value
> and closure = { definition: (pattern * expression) list; mutable
> environnement: environnement }
> and environnement == (string * value) list
>
> I don't see however how I am going to represent a type Val_Array given that
> the indexes can be of arbitrary type and in arbitrary number.
> I haven't found either how to transform the arrays into inductive types
> like lists to avoid the issue.
>
> Any suggestions ?
>
>         Diego Olivier
>

[-- Attachment #2: Type: text/html, Size: 2951 bytes --]

Re: [Caml-list] Interpreting a language with (sparse) arrays explicitly indexed

[Diego Olivier Fernandez Pons]

[-- Attachment #1: Type: text/plain, Size: 334 bytes --]

    Gabriel,


>   | Val_table of (value, value) Hashtbl.t


It took me two days to understand that this actually solved the problem
because it fulfils type erasure and induction on dimension, just like
functions.

Actually, that's the type of a reified curried function value -> value ->
value -> ... -> value

        Diego Olivier

[-- Attachment #2: Type: text/html, Size: 606 bytes --]