[chc4]

Re: operational semantics, you can in fact "cheat" and lots of languages do. It's just difficult. Luajit and other tracing JITs optimize away implementation details or use specialized datastructures in the cases where no code depends on introspection behind the curtain, with trace poisoning and falling back to "proper" evaluation in cases where it's needed.

[chrisseaton]

Right - a Lisp list is conceptually a linked-list. How the compiler chooses to implement the list is up to it - it can use an array as long as it can meet the specification and give useful performance.