| лисп, замыкания |
[Jul. 3rd, 2017|02:52 am] |
в общем, в итоге я придумал то, что до меня придумали в Lua. видимо, потому, что ничего особо другого не придумывается.
поскольку машина у меня регистровая (дебильное название, конечно; она скорее фрэймослотовая, но принято называть «регистровая» отчего-то), и локалы живут на стеке, а не выделяются в хипе (как делают обычно в компиляторах схемы, например [ладно, ладно, там делают гибридно, но не будем усложнять без нужды]), то я не могу просто таскать вместе с замыканием его окружение: его в явном виде нет.
зато я могу собрать все обращения к upvalues в массив вида «выше на L фрэймов, слот номер N». пока нам не надо создавать полноценное замыкание (а это надо только если ламбду присваивают какой-то перменной — в том числе передают как аргумент), мы обходимся бесплатным (за счёт nan boxing) «стековым недозамыканием», которое просто хранит BP (base pointer: начало стекового фрэйма родителя) на время создания, и ищет апвалуи путём путешествий по цепочке BP. элементы массива опять же укутаны в nan-ы.
а когда надо создать «настоящее» замыкание, мы просто создаём новый массив апвалуев, и заменяем все его элементы на текущие значения, используя точно то же путешествие, что и раньше. теперь у нас значения правильно закрыты.
небольшая сложность состоит в том, что нам может понадобиться закрыть другую ламбду: с ней поступаем тем же самым алгоритмом, рекурсивно. но не забываем схоронять новосозданые замыкания где-то в укромном месте, чтобы не создавать кучу замыканий для одной и той же ламбды, случайно оказавшейся в разных локалах: это будет не просто некорректно в итоге, но ещё и потенциально бесконечно рекурсивно.
тот же процесс надо провести и для всех вложеных функций, но создавать «неполные» замыкания, закрывая только обращения к апвалуям, у которых L больше, чем степерь вложенности текущей обрабатываемой функции. благо, функции у нас first class citizens, и внутри представляют из себя обычные литералы, живущие в массиве литералов (опять прелесть непрямого обращения!), так что их снова можно отпидорасить рекурсией.
в конце этих мучений у нас получится корректное замыкание, которое уже можно раздавать направо и налево. я ему ставлю флажок «full closure», чтобы не сложно трекать это в компиляторе, а дёшево откупиться ничегонеделанием в исполняторе, если флажок уже стоит.
сам по себе алгоритм несложный, но имеет нюансы, которые легко упустить или нечаянно налажать, поэтому с налёта реализовать не получилось, пришлось таки подумать.
ещё одна проблема есть с TCO: оно может грохнуть стековый фрэйм, в котором живут какие-то нужные нам апвалуи. но делать полное замыкание при этом нельзя, потому что тогда вложеные функции перестанут работать правильно (получат по копии локалов родителя, и будут изменять эти копии, что чушь). я про это не подумал, и долго пытался понять, что же за фигня происходит. решение (ещё не реализованое) в том, чтобы опять создать «частичное замыкание», закрыв только значения из того стекового фрейма, который TCO заменит на новый. то есть, строго апвалуи из текущего фрэйма, перед заменой.
вся эта гибкость по созданию частичных и полных замыканий возможна только потому, что мы не кодируем уровни и индексы напрямую в опкоде, а ходим строго индеректом через массив апвалуев. желание «оптимайзнуть», засунув всю информацию в опкод, конечно, возникает сразу, и его сразу же надо давить. иначе реализация правильных замыканий не будет сделана никогда — заебёшься функции пересобирать каждый раз. |
|
|