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

Am 17.12.2017 um 22:03 schrieb Jeremy Mikkola:

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.

It depends on how data is addressed in the language. If you wanto interpret a C-style language where every address can be cast to an int, then that's the most straightforward (though not necessarily best) approach. If it is just references to objects as in most, erm, "more modern" languages, the Id can be any type. E.g. something based on the language's data model - Int | Real | Record | Array, with type parameters as appropriate. Upside is that you leverage the Haskell GC that way, downside is that you'll need a recursive type (Array is really Array RefId, and my Haskell-fu is hilariously inadequate to properly flesh out that recursion).