Writing an interpreter for a language with mutability

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Writing an interpreter for a language with mutability

Jeremy Mikkola
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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Baa
Reply | Threaded
Open this post in threaded view
|

Re: 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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Writing an interpreter for a language with mutability

Chris Wong-2
In reply to this post by Jeremy Mikkola
Hi Jeremy,

I'm on my phone right now so I can't link, but try searching for "IORef" and the "ST monad".

Chris

On Dec 18, 2017 10:06, "Jeremy Mikkola" <[hidden email]> wrote:
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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Writing an interpreter for a language with mutability

Joachim Durchholz
In reply to this post by Jeremy Mikkola
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).
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Writing an interpreter for a language with mutability

Jeremy Mikkola
Hi all, thank you for the replies!

The language this will interpret does not expose pointers (so it acts like the more modern languages).

I have started to try to wrap my head around IORef and that monad (anyone know of a "for dummies" guide to those?). I think that they will likely be exactly what I need.

Thanks again,

- Jeremy Mikkola

On Mon, Dec 18, 2017 at 12:31 PM, Joachim Durchholz <[hidden email]> wrote:
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).

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Writing an interpreter for a language with mutability

Tikhon Jelvis
"Write Yourself a Scheme in 48 Hours"[1] is a tutorial about implementing Scheme in Haskell. It takes the approach of modeling mutable variables in Scheme using IORefs. It's a good place to start learning about these ideas—in fact, it's pretty much how I learned Haskell.

Looking back at it now I'm not sure I would make the same decisions as the author any more, but it worked and the tutorial does a good job of guiding you through what the code does. After you follow that, you should have a good feeling for how IORefs work in Haskell and how they fit into an interpreter for a mutable language.

[1]: https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours

On Tue, Dec 19, 2017 at 9:37 AM, Jeremy Mikkola <[hidden email]> wrote:
Hi all, thank you for the replies!

The language this will interpret does not expose pointers (so it acts like the more modern languages).

I have started to try to wrap my head around IORef and that monad (anyone know of a "for dummies" guide to those?). I think that they will likely be exactly what I need.

Thanks again,

- Jeremy Mikkola

On Mon, Dec 18, 2017 at 12:31 PM, Joachim Durchholz <[hidden email]> wrote:
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).

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Writing an interpreter for a language with mutability

Will Yager

>  After you follow that, you should have a good feeling for how IORefs work in Haskell and how they fit into an interpreter for a mutable language.

I’m not sure why people jumped to IORefs so quickly. Since you need to look up variable names to get to the IORef underlying the variable anyway, it seems like you might as well avoid IO and just use a (hash)map from variable names to values.

If you really need the speed boost, you will probably want to instrument different mutable  implementations anyway, so you will probably want an interpreter that’s generic over the choice of mutable variable representation.

I would make a monad typeclass that encapsulates whatever operations you need on variables, and test it with “StateT (HashMap VarName VarVal)” (pure baseline), something with IORefs, something with ST (preferable to IO), etc.

—Will


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.