[Haskell-cafe] Writing an interpreter for a language with mutability

[Baa]

Hello,

IMHO interpretor written in any language will need collection of
mappings. What is the mutation?

  x = 1
  x = 2

is this a mutation? `x` is a member of some collection (dict/map) and
last line remap/rebind its value. Sure, you need collection to access
all values by name. But `x` can be complex value, for example
record/structure with fields. So, we should talk about map of maps. Is
it effective? May be you need one big tree? What kind of trees are
effective we know from RDBMS. So, obviously you need some collection.
In Python any object has ID (it can be address in virtual memory) and
reference counter - for GC. It's very common scheme.
But you can implement another scheme too: to compile tree, allocate
objects in some memory storage structure (pool/pools of objects with the
same size) and to translate names to indexes - how in done in usual
compiled languages like C, Pascal, etc. VM-based languages uses
different schemes but sometimes the same. You can allocate objects in
stack, in registers and sure heap. And you need to translate names into
indexes in those storages.

But you are right, simplest way is to allocate them in some collection
and to use hash/index/etc to access them. May be one big tree will be
good solution. So, interesting is to choose right kind of tree.

It's my IMHO :)

As idea, I can only say: it is better to check implementations of
ddifferent classical interpreting languages: Tcl, Lisp/Scheme, Basic,
Python, IO, Lua, etc. You can find many interesting ideas there

===
Best regards, Paul

> I am quite certain I am not the first to try to do this, but my
> google-fu is failing me today.
> 
> How does one go about interpreting a language with mutable objects in
> Haskell?
> 
> 
> The best approach I can think of is to represent the language's
> memory as a `Data.Map.Map RefID LanguageObject` where RefID is some
> type (probably Int) used as a reference. The LanguageObject structure
> might contain some values of type RefID to refer to other objects.
> Mutating an object involves simply replacing the value in the map at
> a given RefID.
> 
> 
> I don't like this approach for two reasons:
> 
> 1. Map lookups aren't very efficient compared with actual references
> to the value.
> 
> 2. I have to re-invent garbage collection, removing objects from the
> map when they no longer have incoming references. (Unlike simple
> interpreters for languages with immutable values, I can't rely on
> Haskell's garbage collector to do the work for me.)
> 
> 
> Is there a better approach?
> 
> 
> - Jeremy