Reia: now without rainbow-farting Domo-kuns

[Tony Arcieri]

Syndicated from my blog.  View the original post here:

http://www.unlimitednovelty.com/2009/11/new-reia-now-without-rainbow-farting.html

The new Reia: now without rainbow-farting Domo-kuns

Well, what can be said: the buzz about Reia has died down, and several people are confused about the state of the project. Is it going forward? Is it being actively developed? What's this Peridot thing?

I recently attended RubyConf and was asked by many people about the state of Reia. My answer was always "wow, I should really blog about that" to avoid repeating the same things to people over and over (after all, the Ruby community emphasizes DRY, right?). Well, here is that blog.

The State of Reia: Forget Peridot

To put it bluntly, Reia is undergoing a ground-up rewrite. This does not mean I am abandoning the previous codebase. Far from it. Instead I am rewriting the parts of it which are problematic, and pulling in code from the previous implementation where it makes sense.

When I talk to various people who are implementing languages for fun, it seems most people are interested in producing one-off experiments with little attention to developing them into "real" languages someday that might actually be used in production by a lot of people. This certainly makes sense, and that's how I started with Reia. However, buzz grew, and so did my investment in the project. Every indicator I've been given has shown me that Reia is something a lot of people are potentially interested in, so half-assing it isn't going to cut it.

The new Reia roadmap calls for reaching complete feature parity with Erlang with as minimal an implementation as possible, then making it rock solid. At this point, while Reia will lack many of the "dream features" of the previous implementation, it will be generally usable as an alternative to Erlang. Once new language features become available existing programs can be modified to make use of them. After all this is done syntactic sugar can be added, and finally, the concurrent object model.

Initially I had thought of splitting off these additional features into a separate language, which I called "Peridot", but after long and careful consideration, this doesn't make sense. The new Reia will start as an alternative syntax for Erlang (with destructive assignment) but will grow to include all of the features I had originally envisioned.

What Was Wrong with the Previous Implementation?

Why rebuild Reia from the ground up? Can't the existing implementation be salvaged and molded into something usable?

There are a number of problems with the existing implementation. Some stem from my lack of knowledge of Erlang itself when I started. Some of them stem from my lack of knowledge of best practices when writing a language compiler in Erlang. Others stem from the organic way the language evolved. But above everything else, the problems stem from one feature I deemed absolutely necessary: eval.

I like eval lots! If nothing else, it exists for one reason: so Reia can have an interactive shell (i.e. a read-eval-print loop, a.k.a. REPL). I spend lots of my time hacking on Ruby code by interacting with it from irb, the interactive Ruby interpreter. I have a very hard time working with languages that do not provide some form of interactive interpreter nowadays.

The biggest problem with implementing eval is that you have to write your own implementation for your language. In the previous version of Reia I tried to sidestep that by using erl_eval, the Erlang metacircular interpreter, as my eval implementation. Unfortunately, to facilitate this, I ended up implementing the entire code loading process in a way which shoved everything to erl_eval. The result ended up looking something like this:



When code entered the system, it was first parsed and converted to Erlang by reia_compiler (the Domo-kuns). For module and class declarations, the code was compiled down to Erlang bytecode (the rainbow farts) which were in turn injected into the toplevel Erlang AST. In other words, the toplevel scope of any Reia file was never compiled, but simply stored as expressions, and where module/class declarations existed, instructions to load the compiled module (which itself was injected directly into the AST) were issued. This provides somewhat Ruby-like semantics for module/class declarations: they're "loaded" at the time they're declared.

The resulting Erlang AST, complete with compiled class/module fragments, was then shoved through the Erlang metacircular interpreter, erl_eval (seen in the diagram as the tornado). As you might guess, compared to compiled Erlang the metacircular interpreter is reaaaaaaaaally slow.

Once everything was said and done, the resulting class/modules were loaded into the Erlang code server, pictured here as a hungry Joe Armstrong going *nom* *nom* *nom*.

Making Reia Faster

As you may guess, an as-yet-unstated goal of this rewrite is to improve the speed of code-loading. Previously, Reia could not have a large standard library, because it took so long to load code. Furthermore, implementing a mechanism for caching compiled bytecode was impossible due to the API structure.

The new code-loading API directly compiles everything, including any code which is eval'd. This not only makes everything significantly faster but also facilitates the possibility of caching and also various bugs surrounding the eval implementation. From what I've gathered elsewhere, most compiled languages generally ditch any form of metacircular interpreter and implement eval by compiling temporary modules.

Doing this in Erlang is hard, because certain expressions in Erlang create things which exist beyond when code is being evaluated, namely processes and lambdas (a.k.a. funs). This was a vexing problem to me for quite some time, but after talking with Robert "Hello Robert" Virding, one of Erlang's creators, I believe I've come upon a workable solution, even if it's a bit of a hack.

Reia will implement its own "garbage collector" process for eval'd code, which periodically checks if all the lambdas/processes created by a particular eval call are no longer in use. If so, it will remove the temporary module. If not, then it will continue to wait. It is not the greatest solution in the world, but it will get the job done.

This means no Reia code will ever go through erl_eval. Everything is compiled. This will make code loading of all sorts, and eval, much faster. There are no longer any rainbow farting Domo-kuns.

What About Neotoma?

When I originally began my rewrite of Reia, I was attempting to redo the parser using Neotoma, a Parsing Expression Grammar (PEG) tool for Erlang, similar to Ruby's Treetop.

I eventually shied away. This had little to do with Neotoma itself, but my own inability to understand PEGs, and the fact that my own inability to understand them was a roadblock in continued development. Because of this, I switched back to more familiar tools: leex and yecc, the Erlang equivalents of lex and yacc.

Neotoma has come a long way and become better than ever. I am still considering using it. I think it would be a great tool for solving a lot of problems that aren't presently solved, like handling Reia expressions within interpolated strings. This is something I might pursue when I am confident that development otherwise is coming along at a steady pace, but at this point, switching to Neotoma is a lower priority for me than developing a rock-solid core language.

Where's the Code?

If you're interested in checking out the latest Reia codebase, it's available on this branch on Github:

http://github.com/tarcieri/reia/tree/minimalist

If you're looking at master, and wondering why it hasn't been touched in months, it's because I'm hacking on the new branch, not the previous implementation.

The new implementation is not generally usable. I am still working out the nasty details of implementing a compiled eval, as well as implementing cleaner compiler internals.

But hey, if you're interested in Reia, check it out and let me know what you think.

--
Tony Arcieri
Medioh/Nagravision

[candlerb]

I strongly support what you're doing, Tony, and I think you've got the
roadmap right.

Ruby is a wonderful language, but has accumulated a lot of cruft over
the years. The last straw for me was the total pig's ear made of the
String class, which means I'm never switching to 1.9. Reia could be my
exit strategy in case 1.8 is ever abandoned (*).

The main benefits I'd get from Reia rather than just moving to native
Erlang would be:
* being able to define modules and functions interactively (can't do
that in erl shell)
* not having to decide for each line whether it ends with a dot, a
comma or a semicolon!

The roadmap suggests I can compile reia to .beam files just like
Erlang, so I could mix and match as required.

Object sugar isn't that important to me. Years ago I used to program
Transputers using Occam, so I'm comfortable with the CSP model.

So I look forward to seeing how it goes. I have built your minimalist
branch, and so far the following work in ire:
>> 2 + 2
>> a = 2 + 2; a

But the following all give syntax errors:
>> [blank line]
>> 3 < 2
>> puts(2+2)
>> "hello"
>> puts("hello")

And the following pair of lines gives an unbound variable error:
>> a = 2 + 2
>> a

Perhaps there is a real opportunity for doing Behaviour Driven
Development here, starting with simple test cases like these, as this
would also serve as documentation.

Regards,

Brian.

(*) And no, I don't want to use JRuby either.

[Tony Arcieri]

On Thu, Nov 26, 2009 at 3:22 AM, candlerb <b.ca...@pobox.com> wrote:

The roadmap suggests I can compile reia to .beam files just like
Erlang, so I could mix and match as required.

For some reason an AOT compiler which outputs .beam seems highly desirable to people.  I'd like to try to support one but there are certain difficulties involved.  It would be relatively easy to do if people don't mind dealing with Reia's different function call semantics themselves in Erlang.

 

But the following all give syntax errors:
>> [blank line]
>> 3 < 2
>> puts(2+2)
>> "hello"
>> puts("hello")

Yes, the grammar for these isn't currently present.

 

And the following pair of lines gives an unbound variable error:
>> a = 2 + 2
>> a

This is what I've been working on lately.  As I mentioned in my blog post, Reia's new eval implementation works by compiling a temporary module.  Right now there is no way to pass in a set of bindings to this temporary module, or retrieve the new set of bindings out.

This isn't terribly difficult to do: the input bindings can enter as function arguments, and the output bindings require only a relatively minor parse transform which sticks them into the function return value.

I'm working on this right now and hope to have it done relatively soon.

--
Tony Arcieri
Medioh/Nagravision

[candlerb]

> It would be relatively easy to do if people don't
> mind dealing with Reia's different function call semantics themselves in
> Erlang.

How are the function call semantics different?

The examples I've seen for the 'old' reia look similar to Erlang
method calls with pattern matching (e.g. 'def simple(0) ... def simple
(n)') but I don't know how much of this is relevant to how the 'new'
reia will look.

Or let me ask it slightly differently: in what ways will the new Reia
actually be different from regular Erlang, apart from syntax?

I mean, the example at http://github.com/tarcieri/reia/blob/master/examples/fibonacci.re
could be turned into regular Erlang source code fairly easily (apart
from the variable rebinding at the end).

Regards,

Brian.

[candlerb]

Actually, I see where my simple idea breaks down:

| def optimized_list(0, _, result)
| result.reverse()
| end
| def optimized_list(n, next, result)
| optimized_list(n - 1, next + result[0], result.unshift(next))
| end

You'd need some way of knowing what result.reverse, result[] and
result.unshift should call. Presumably you don't want to waste that
syntax by hard-coding it to lists:reverse, lists:nth and [H | T]

If I were writing a static front-end, I'd consider tagging the
variable itself with a receiving module: e.g. (ignore poor choice of
syntax)

def optimized_list(n, next, result#lists)

so that result[x] expands to lists:nth(result, x) statically at
compile time. This could be done under a case statement too:

case result
when :nil
.. do X
when a#lists
.. do Y, where a is bound to the value and is tagged as 'lists'
end

ISTM that normal erlang deals with polymorphism by tagging values:

case X
when {type1, Val}
..
when {type2, Val}
..
end

but it can also do dynamic module dispatch. You'd just have to pass
the receiving module explicitly as well as the value: and that could
be hidden under some sugar.

1> A = {[5,6,7,8], lists}. %% def myfun(result+)
{[5,6,7,8],lists}
2> {Result, ResultMod} = A.
{[5,6,7,8],lists}
3> ResultMod:nth(2,Result). %% result[2]
6

Hmm, I don't think we can necessarily rely on the 'receiver' value
always being in the first or last place in the argument list in the
erlang standard library.

Anyway, I'm just thinking aloud. I might have to give this a try, as
it would be quite a good way of learning more erlang too :-) But I'd
be very interested to hear how the new Reia will deal with this, and
other things like rebinding variables and adding functions to modules
dynamically.

[Tony Arcieri]

On Fri, Nov 27, 2009 at 2:15 AM, candlerb <b.ca...@pobox.com> wrote:

How are the function call semantics different?

Reia functions/methods aren't "arity sensitive" in the same way Erlang ones are.  This is by design: Reia will eventually permit default arguments, keyword arguments, and receiving arguments as a list via the "splat" operator, similar to Ruby.

Internally, Reia functions take the form:

myfunc({Arg1, Arg2, ..., ArgN}, Block)

and are therefore all arity 2.  Blocks are Ruby-style blocks, i.e. anonymous functions passed using special syntax.

 

The examples I've seen for the 'old' reia look similar to Erlang
method calls with pattern matching (e.g. 'def simple(0) ... def simple
(n)') but I don't know how much of this is relevant to how the 'new'
reia will look.

Or let me ask it slightly differently: in what ways will the new Reia
actually be different from regular Erlang, apart from syntax?

I'll be building support for Ruby-style blocks in from the ground up.  The previous version of Reia tried to retrofit them in after the fact.  This was mostly successful but became quite an undertaking and the resulting source code was not all that great.

 

I mean, the example at http://github.com/tarcieri/reia/blob/master/examples/fibonacci.re
could be turned into regular Erlang source code fairly easily (apart
from the variable rebinding at the end).

That particular example looks an awful lot like the Erlang counterpart, yes.

--
Tony Arcieri
Medioh/Nagravision

[Tony Arcieri]

On Fri, Nov 27, 2009 at 3:00 AM, candlerb <b.ca...@pobox.com> wrote:

You'd need some way of knowing what result.reverse, result[] and
result.unshift should call. Presumably you don't want to waste that
syntax by hard-coding it to lists:reverse, lists:nth and [H | T]

Yes, Reia has its own late binding/dynamic dispatch mechanism.

I've been looking for ways to try to hook into some of the late binding provided by Erlang (for example, dispatching calls to paramaterized modules) but I don't see a particularly easy/good way to do this.
 

--
Tony Arcieri
Medioh/Nagravision

[Tony Arcieri]

On Thu, Nov 26, 2009 at 3:22 AM, candlerb <b.ca...@pobox.com> wrote:

And the following pair of lines gives an unbound variable error:
>> a = 2 + 2
>> a

If you pull HEAD it is now persisting the bindings between successive calls to eval, at least in the shell.

The way it's presently implemented will need to change in order to support destructive assignment, but hey, it's a start.

--
Tony Arcieri
Medioh/Nagravision

[candlerb]

> If you pull HEAD it is now persisting the bindings between successive calls
> to eval, at least in the shell.
>
> The way it's presently implemented will need to change in order to support
> destructive assignment, but hey, it's a start.

It works... cool. And as you say, "a = a + 1" gives an erlangy pattern
match error.

OOI, does the beam VM allow destructive assignment, or will you have
to simulate it somehow?

[candlerb]

> Yes, Reia has its own late binding/dynamic dispatch mechanism.

And the problem may go away when you have objects implemented as
erlang processes, since dynamic dispatch would just be sending a
message. It looks like this is what wooper does.

> I've been looking for ways to try to hook into some of the late binding
> provided by Erlang (for example, dispatching calls to paramaterized modules)
> but I don't see a particularly easy/good way to do this.

Hmm, parameterized modules look interesting. I wonder what the
overhead is of wrapping core modules such as list, proplist and dict?

-module(nlist, [List]).
-export([last/0]).
last() -> lists:last(List).

-module(nproplist, [Proplist]).
-export([get_value/1, get_all_values/1]).
get_value(V) -> proplists:get_value(V, Proplist).
get_all_values(V) -> proplists:get_all_values(V, Proplist).

1> Mods = nproplist:new(lists:module_info()).
2> E = nlist:new(Mods:get_value(exports)).
3> E:last().
{member,2}

That looks pretty dynamic to me, and you can use element(1,X) to get
the name of the module ('class'). Of course, these objects don't
mutate - you'd have to return a new 'instance' as a value.

Native Erlang doesn't make it convenient to chain these left-to-right,
because you need extra parentheses:

11> (nlist:new((nproplist:new(lists:module_info())):get_value
(exports))):last().
{member,2}

But in principle it seems workable. It could read left-to-right with
some syntax to replace Mod:new(). e.g.

lists:module_info()->nproplist.get_value(exports)->nlist.last()

[Tony Arcieri]

On Tue, Dec 1, 2009 at 7:54 AM, candlerb <b.ca...@pobox.com> wrote:

> Yes, Reia has its own late binding/dynamic dispatch mechanism.

And the problem may go away when you have objects implemented as
erlang processes, since dynamic dispatch would just be sending a
message. It looks like this is what wooper does.

This is what the original version of Reia does as well.  I'd certainly like to bring that back, but there are lots of issues with the objects-as-processes approach.

One of my goals with the new Reia is to start with "immutable objects" which are simple immutable state containers that are independently garbage collected and don't run into concurrency issues, such as circular call chains.

Reia's previous dispatch mechanism did thunk to objects-as-processes without issue, however it also allowed method dispatch on "builtins" such as lists, tuples, integers, strings, etc.

 

Hmm, parameterized modules look interesting. I wonder what the
overhead is of wrapping core modules such as list, proplist and dict?

Reia originally had wrappers around all of the core types.  I'm moving away from that in the new implementation.  It increased the complexity of the implementation and hampered interfacing.

The new dynamic dispatch module is in place now:

http://github.com/tarcieri/reia/blob/minimalist/src/core/reia_dispatch.erl

Compare to the previous, more convoluted implementation:

http://github.com/tarcieri/reia/blob/master/src/core/reia_dispatch.erl

--
Tony Arcieri
Medioh/Nagravision

[Tony Arcieri]

On Tue, Dec 1, 2009 at 2:30 AM, candlerb <b.ca...@pobox.com> wrote:

It works... cool. And as you say, "a = a + 1" gives an erlangy pattern
match error.

OOI, does the beam VM allow destructive assignment, or will you have
to simulate it somehow?

Internally, BEAM allows destructive changes to its registers (HiPE has its own distinct architecture).  Single assignment is enforced by the Erlang compiler itself.  As Reia compiles to Erlang and pushes its code through the Erlang compiler.

Reia previously supported destructive assignments by versioning variables, ala Static Single Assignment (SSA) form.  You can view the previous code here:

http://github.com/tarcieri/reia/blob/master/src/compiler/reia_ssa.erl

This code was a bit convoluted and difficult to understand.  The new version will be much simpler, as the code which versions local bindings has been factored into a separate module, which can be used for other transforms that need awareness of the local bindings:

http://github.com/tarcieri/reia/blob/minimalist/src/compiler/reia_bindings.erl
 

--
Tony Arcieri
Medioh/Nagravision

[Tony Arcieri]

On Tue, Dec 1, 2009 at 2:30 AM, candlerb <b.ca...@pobox.com> wrote:

It works... cool. And as you say, "a = a + 1" gives an erlangy pattern
match error.

Destructive assignment is now working:

>> a=12;a=42
=> 42
>> a=a+1
=> 43

These sort of operations are working as well:

>> a *= 10
=> 430
 

OOI, does the beam VM allow destructive assignment, or will you have
to simulate it somehow?

In the new branch, destructive assignment required very little code.  It works by versioning variables just as you'd do "manually" in Erlang:

http://github.com/tarcieri/reia/blob/minimalist/src/compiler/reia_ssa.erl

--
Tony Arcieri
Medioh/Nagravision

[candlerb]

> One of my goals with the new Reia is to start with "immutable objects" which
> are simple immutable state containers that are independently garbage
> collected and don't run into concurrency issues, such as circular call
> chains.

Yes, I can see garbage collection would be an issue, although careful
process linkage could help too. But I think it's important eventually
to expose processes in an easy-to-use way, otherwise you lose a lot of
the benefits.

As an exercise, I started with this:

class Thing
def initialize
0
end
def initialize(n)
n
end
def inc(state)
{state, state+1}
end
end

a = Thing.new
io.write a.inc
io.write a.inc

(it could be clearer keeping state as a dictionary of 'instance
variables')

Then I worked through what it would need to turn it into working
Erlang. I ended up with a lot of boilerplate:

-module(thing).
-export([create/0, create/1]).
create() -> create_args([]).
create(N) -> create_args([N]).
create_args(Args) ->
{ok, Pid} = gen_server:start_link(thing_impl, Args, []),
thing_intf:new(Pid).

-----

-module(thing_intf, [Pid]).
-export([inc/0, destroy/0]).
inc() ->
gen_server:call(Pid, {inc}).
destroy() ->
gen_server:call(Pid, stop).

-----

-module(thing_impl).
-behavior(gen_server).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2,
terminate/2, code_change/3]).
init([]) -> {ok, 0};
init([Count]) -> {ok, Count}.
handle_call({inc}, _From, State) ->
{reply, State, State+1}.
handle_cast(_Msg, State) -> {noreply, State}.
handle_info(_Info, State) -> {noreply, State}.
terminate(_Reason, _State) -> ok.
code_change(_OldVsn, State, _Extra) -> {ok, State}.

----

1> A = thing:create().
{thing_intf,<0.37.0>}
2> A:inc().
0
3> A:inc().
1
4>

Phew! But ultimately that's what I'd like with less effort :-)

[candlerb]

> The new dynamic dispatch module is in place now:
>

> http://github.com/tarcieri/reia/blob/minimalist/src/core/reia_dispatc...

That's very clear. It looks like every call will go through two levels
of pattern-matching, e.g. for a list it would be reia_dispatch:call
(...) followed by 'List':call(...).

How are user-defined objects going to hook into this? I guess one way
would be parameterised modules, e.g.

...
call({pmod,Mod} = Receiver, Method, Arguments, Block) ->
Mod:call(Method, Arguments, Block);
...

[candlerb]

On Dec 1, 5:49 pm, Tony Arcieri <t...@medioh.com> wrote:
> Reia previously supported destructive assignments by versioning variables,
> ala Static Single Assignment (SSA) form.

Please forgive my ignorance here... I think I get the general gist of
SSA, that is you version A as A1, A2 etc, but how would this work in a
loop, or does this assume no loops other than recursive function
calls?

And what about when you have a conditional, with one branch assigning
A1 and the other A2?

17> A2 = 99.
99
18> A3 = try A1 catch error:_ -> A2 end.
* 1: variable 'A1' is unbound

[Tony Arcieri]

On Thu, Dec 10, 2009 at 7:55 AM, candlerb <b.ca...@pobox.com> wrote:

Yes, I can see garbage collection would be an issue, although careful
process linkage could help too. But I think it's important eventually
to expose processes in an easy-to-use way, otherwise you lose a lot of
the benefits.

That's what the previous implementation did with concurrent objects.  The new branch will get them back again, eventually, but I want to ensure I have complete, rock solid feature parity with Erlang first before I add them back again.

See:

http://wiki.reia-lang.org/wiki/Classes_and_objects

(it could be clearer keeping state as a dictionary of 'instance
variables')

The previous branch stored a hidden dictionary of instance variables which was transactionally updated whenever methods completed successfully.

--
Tony Arcieri
Medioh! A Kudelski Brand

[Tony Arcieri]

On Thu, Dec 10, 2009 at 8:09 AM, candlerb <b.ca...@pobox.com> wrote:

That's very clear. It looks like every call will go through two levels
of pattern-matching, e.g. for a list it would be reia_dispatch:call
(...) followed by 'List':call(...).

Keep in mind late binding is only needed if you're dispatching to a variable.  If you're dispatching to a literal (e.g. module name, list, tuple, dict, etc) there's no late binding penalty (or won't be).

How are user-defined objects going to hook into this? I guess one way
would be parameterised modules, e.g.

If you look at the previous implementation:

http://github.com/tarcieri/reia/blob/master/src/core/reia_dispatch.erl

funcall({object, {Pid, _Class}}, Method, Arguments, Block) ->
  reia_class:call(Pid, {Method, Arguments, Block});
funcall({constant, _Name} = Receiver, Method, Arguments, Block) ->
  'Constant':funcall(Receiver, Method, Arguments, Block);

These dispatch to user-defined objects and modules.

[Tony Arcieri]

On Thu, Dec 10, 2009 at 9:46 AM, candlerb <b.ca...@pobox.com> wrote:

Please forgive my ignorance here... I think I get the general gist of
SSA, that is you version A as A1, A2 etc, but how would this work in a
loop, or does this assume no loops other than recursive function
calls?

Yes, loops decompose into tail recursive functions which return the latest versions of all variables rebound within the loop.

 

And what about when you have a conditional, with one branch assigning
A1 and the other A2?

17> A2 = 99.
99
18> A3 = try A1 catch error:_ -> A2 end.
* 1: variable 'A1' is unbound

The previous version bound all "unsafe" variables in branches to their latest versions, or nil if there wasn't a latest version.  Ruby has the same behavior:

>> x
NameError: undefined local variable or method `x' for main:Object
    from (irb):1
>> begin
?>   raise 'foo'
>>   x = 42
>> end
RuntimeError: foo
    from (irb):3
>> x
=> nil

[candlerb]

> Yes, loops decompose into tail recursive functions which return the latest
> versions of all variables rebound within the loop.

What about code in a block/fun callback? e.g.

Dummy = [1,2,3],
A = 1,
lists:foreach(fun(_Elem) -> A = A + 1 end, Dummy),
io.write(A)

You could pass in the bound variables as an extra argument to the fun,
and return their new values, but I can't see how that would be usable
with the existing lists:foreach function. (This particular example
could be manually rewritten to use lists:foldl instead, but I'm
interested in the general solution)

I hope you don't mind all these dumb questions :-)

Cheers,

Brian.