Динамический и статический компилятор (JavaScript)

Question

Я сейчас пишу компилятор JavaScript на ANTLR + Java.

Я прочитал здесь вопросы о переполнении стека о том, как продолжить выполнение - и ответ всегда состоит в том, что было бы слишком сложно выполнить статическую компиляцию (без информации JIT) динамического языка - но почему это точно? Есть, конечно, очевидная проблема с «разрешением типов», и в JavaScript может быть проблема с функцией eval - но есть ли другие причины? (потому что они не кажутся слишком сложными, чтобы преодолеть чисто статически (без JITS))

Я исключаю компиляцию на основе JIT, поскольку полагаю, что это будет слишком сложно для реализации.

У меня есть некоторый опыт написания статических компиляторов с выполнением байт-кода.

UPDATE:

Все ваши ответы действительно помогают понять проблему. Чтобы уточнить, означает ли это, что JavaScript сложнее реализовать, чем другие динамические языки?

И означает ли это, что лучше использовать интерпретатор на основе дерева, чем, например, Байт-код (если мы забываем о свойстве, которое JS всегда поставляется в необработанном исходном коде - следовательно, добавляем дополнительное время для генерации и IR, а затем выполняем его)? - или они должны быть примерно такими же легкими / трудными для выполнения?

(Я новичок в SOF; не знаете, является ли это предпочтительным способом обновления вопроса?)

Answer 1

Есть много способов, которыми этот разговор может пойти.Вот одно из направлений.В javascript почти все является объектом, и свойства или методы могут быть добавлены к любому объекту во время выполнения.Таким образом, вы не знаете во время компиляции, какие методы или свойства будут или не будут прикреплены к объекту.Таким образом, все должно быть найдено во время выполнения.

Например:

var myObj = {};

function configureObject() {
    if (something in the environment) {
        myObj.myfunc = function () {alert("Hi");}
    } else {
        myObj.myfunc = function () {document.write("Hello");}
    }
}

Теперь, когда-нибудь позже в коде, который вы вызываете myObj.myfunc(); Это неизвестно при компиляциивремя что такое myfunc или является ли это атрибут myObj.Это должен быть поиск во время выполнения.

В другом примере возьмем эту строку кода:

var c = a + b;

Что его средства полностью зависят от типов a и b и этих типовне известны во время компиляции.

Если a и b оба являются числами, то это оператор сложения, а c будет числом.

Если a или b является строкой, тодругой будет приведен к строке, а c будет строкой.

Вы не можете предварительно скомпилировать этот тип логики в нативный код.Среда выполнения должна записать, что это запрос на оператор сложения между этими двумя операндами, и она должна (во время выполнения) изучить типы двух операндов и решить, что делать.

Answer 2

Сложность написания статического компилятора JavaScript заключается в том, что в общем неразрешимо трудно определить, на какие объекты ссылаются в любой программной точке или какие функции вызываются.Я мог бы использовать тот факт, что JavaScript является динамическим, чтобы решить, какую функцию вызывать, основываясь на выводе некоторой машины Тьюринга.Например:

var functionName = RunTuringMachineAndReportOutputOnTape(myTM, myInput);
eval(functionName + "();");

На данный момент, если у вас нет предварительных знаний о том, что такое myTM и myInput, доказуемо невозможно решить, какая функция будет вызыватьсявызов eval, поскольку невозможно определить, что находится на ленте машины Тьюринга, если она останавливается (вы можете уменьшить проблему остановки до этой проблемы).Следовательно, независимо от того, насколько вы умны, и независимо от того, насколько хороши статические анализаторы, которые вы создаете, вы никогда не сможете корректно статически разрешать все вызовы функций.Вы даже не можете ограничить набор функций, которые могут быть вызваны здесь, поскольку выходные данные машины Тьюринга могут определять некоторую функцию, которая затем выполняется вышеуказанным кодом.

Что вы можете сделать, это скомпилировать код, который всякий раз, когдафункция вызывается, включает дополнительную логику для разрешения вызова и, возможно, использует такие методы, как встроенное кэширование , чтобы ускорить процесс.Кроме того, в некоторых случаях вы можете доказать, что вызывается определенная функция (или что будет вызываться одна из небольшого числа функций), а затем жестко закодировать в этих вызовах.Вы также можете скомпилировать несколько версий фрагмента кода, по одной для каждого общего типа (объектный, числовой и т. Д.), А затем выдать код для перехода к соответствующей скомпилированной трассе на основе динамического типа.

Answer 3

V8 делает это. См. Компиляция JavaScript в собственный код с V8

С не строгими EcmaScript 3 и 5 существует множество складок вокруг областей, с которыми вы не сталкиваетесь в других динамических языках. Вы можете подумать, что оптимизацию компилятора для локальных переменных легко выполнить, но в языке есть крайние случаи, когда это не так, даже игнорируя самоанализ области действия eval.

Рассмотрим

function f(o, x, y) {
  with (o) { return x + y + z; }
}

при вызове с

o = {};
o = { z: 3 };
o = { x: 1, z: 2 };
Object.prototype.z = 3, o = {};

и в соответствии с EcmaScript 3

x = (function () { return toString(); })()

должен дать совсем другой результат, чем

x = toString();

потому что EcmaScript 3 определяет запись активации как объект с цепочкой прототипов.