Decide strategy for evaluating references

[lucaswerkmeister]

GraalEneyj needs a strategy for evaluating references: at what point is e. g. the reference Z28 turned into the actual project_name object?

Broadly speaking, I see two ways forward:

1. References are runtime objects. Evaluating a reference AST node merely returns that runtime object; resolving the actual reference happens at a later stage, at the discretion of whoever is holding such a reference instance (e. g. received as a function argument).
2. References are evaluated as soon as a reference AST node is evaluated and do not exist at runtime. If an object of type Z9 is created (e. g. by the Z38 “abstract” builtin, which turns a list of (key, reified value) pairs into an object), it is evaluated immediately.

The problem with the second approach is that eneyj contains a lot of circular references, and a naive implementation of that approach runs into a problem like this:

• Evaluate, say, Z28: parse all its entries, then evaluate them one by one.
• Start with the first key, Z1K1: the type.
• Evaluate Z6.
• Evaluate its type, Z4.
• Evaluate its type, Z4.
• Evaluate its type, Z4.
• …

Introducing references as runtime objects, as I did in 73eeb26c1adcd89872506b893a07c97594f83b0a, is one way to break that infinite loop: you never actually evaluate Z6, you just have a reference with that ID. But this also has its downsides: I’m already beginning to see how it gets annoying that wherever you have a value, you need to deal with the possibility that it’s actually a reference which you need to evaluate first (e. g. in ZFunctionCallNode and ZValueBuiltin). So I’d like to look into the alternative as well.

Another way to break the cycle that I can think of is to register objects early, before they’re complete. The naive approach looked something like this:

• Start evaluating Z28
  • Start evaluating Z6
  • Start evaluating Z4
    • (infinite loop here)
  • write fully evaluated Z4 to global scope / object registry / whatever
  • write fully evaluated Z6 to global scope
• write fully evaluated Z28 to global scope

But we could also try something like this:

• Start evaluating Z28
• Write empty Z28 to global scope
• Evaluate Z28’s Z1K1
  • Start evaluating Z6
  • Write empty Z6 to global scope
  • Evaluate Z6’s Z1K1
  • Start evaluating Z4
  • Write empty Z4 to global scope
  • Evaluate Z4’s Z1K1
    • Returns Z4 (still empty) from global scope
  • Add Z4 as Z4’s Z1K1
  • Evaluate other members…
  • Add Z4 as Z6’s Z1K1
• Add Z6 as Z28’s Z1K1

With some Truffle tricks, it should be possible to optimize this just as well as if objects were truly immutable from the start, even though at the beginning they’re actually mutable.

[vrandezo]

Yes, you identified the core problem. That's called lazy vs eager evaluation, and then there are steps in between. Both should return exactly the same results, but run into different corner-cases where one of them doesn't return at all because it runs out of time or memory.

In eneyj I went for a lazy approach if the implementation used a Z7 function call, for an eager approach if the implementation was a Z16 code, and customised for builtins. Particularly the Z31 if can easily run into endless loops if we first evaluate the consequent and the alternative before evaluating the condition and then only choosing one.

I was starting to implement Z100 evaluate to allow any implementation to choose its evaluation strategy, but I think I overshot it and that's now too complicated. This should be simplified.

Here's the reasoning for the evaluation strategy that eneyj chooses:

• the lambda calculus based implementation of the Z7 evaluation uses naturally a lazy approach.
• in order for the code snippets to work, I have to evaluate the arguments first, so that's why I choose an eager approach for the Z16s
• the builtins were the way they were because, well, it had to support Z31 if, so the builtin implements their evaluation strategy explicitly.

I am really not sure eneyj got it right, and I expect over time to see people rewriting that core evaluator again and again. So my suggestion would be to try whatever is easiest for you now, and then see which of the tests work and which don't, and then see if adjustments are needed.

[lucaswerkmeister]

I think we can close this. Approach one seems to be working reasonably well for now: references are runtime objects and usually passed around as-is, and only a few builtins resolve them on-the-fly. (Maybe we should resolve references before calling code implementations, but that shouldn’t be a big issue.)