Вы используете слово «неизменный» нестандартным способом, который сбивает людей с толку. Если некоторые данные неизменны, мы имеем в виду, что они не будут меняться в течение всей жизни программы. Я думаю, что вы спрашиваете так: Haskell позволяет вам рассматривать функции как объекты первого класса, чтобы вы могли создавать новые функции из старых на лету. Вы задаетесь вопросом, как это могло бы быть скомпилировано в машинный код, когда компилятор не знает, какие функции будут существовать до времени выполнения. Это хороший вопрос.
Я опишу часть подхода, который можно использовать. Не обязательно то, что делает любой настоящий компилятор. Это всего лишь теоретическая идея, чтобы дать вам представление о том, как можно скомпилировать функции, созданные на лету. (На самом деле, я использовал это в игрушечном компиляторе.)
Вот функция Haskell
f x = let w = 3*x
g y = w+2*y in g
f так же, как вы описываете. Он создает новую функцию с именем g, которая удваивает свой аргумент и добавляет 3*x. Затем он возвращает новую функцию. Как эта функция может быть скомпилирована, если вы даже не знаете, что это за функция, пока x не передан в f?
Компилятор может выполнить этап, называемый Лямбда-лифтинг . Он видит, что вы локально создаете функцию с именем g, и извлекает ее как глобальную функцию. Там есть подвох. Мы не можем сделать g глобальной функцией, потому что она зависит от локального значения, w. Таким образом, мы извлекаем g как глобальную функцию, передавая ей w аргумент:
g' w y = w+2*y
Теперь компилятор может переписать f, чтобы вернуть g', предоставив ему необходимый аргумент:
f' x = let w = 3*x in g' w
Теперь вы можете спросить: «Если g' требует 2 аргумента, как мы можем вернуть g' x, который поставляет g' только с одним аргументом?». Внутренне компилятор может сделать то, что называется замыканием . Он представляет g' w как структуру, содержащую пару объектов, указатель (или что-то еще) на глобальную функцию g' и значение w. Теперь компилятор может просто скомпилировать g' как обычную функцию. Я надеюсь, вы видите, что мы исключили любое место, где можно было бы построить новую функцию. Каждый раз, когда мы применяем g' w ко второму аргументу, компилятор может обнаружить, что в нем уже сохранен первый аргумент, и передать его и второй аргумент в g'.
Еще раз подчеркну, что существует множество способов компилировать функциональный код, и я только что описал одну вещь, которую вы можете сделать. Но только показ одного пути должен устранить некоторые тайны вокруг факта, что это вообще возможно. Настоящий компилятор может оптимизировать ваш код разными способами и устранить даже необходимость создания замыкания. Я думаю, что последний стандарт C ++, вероятно, реализует новый lambda, как я описал.
Мне кажется, я понимаю, откуда ты. Когда я начал изучать Haskell, я был очень "как это компилируется в язык ассемблера?" человек. Поэтому, после того, как я начал зацикливаться на понимании Haskell, я просто остановился, написал свой собственный компилятор для функционального языка на основе этой статьи, а затем вернулся к Haskell с более глубоким пониманием. SASL не компилируется вообще, как Haskell, но он научил меня достаточно, чтобы было легче понять, как Haskell компилируется .