Правила порядка определения функций верхнего уровня в Racket и Common Lisp

Question

Я обнаружил, что порядок объявлений верхнего уровня не имеет значения. Есть ли документация об этом топи c? Я не совсем понимаю.

Примеры, показывающие, что функция может быть вызвана без определения

#lang racket

(define (function-defined-early)
  (function-defined-later))

(define (function-defined-later)
  1)

(function-defined-early)
> 1

;; Common Lisp

(defun function-defined-early ()
  (function-defined-later))

(defun function-defined-later ()
  1)

(print (function-defined-early))
> 1

Answer 1

Для Common Lisp это немного сложно, поскольку реализации могут использовать интерпретированный код, скомпилированный код и сильно оптимизированный скомпилированный код.

Вызов функции в простом скомпилированном коде

Например, SBCL по умолчанию компилирует весь код. Даже код, введенный через read-eval-print-l oop:

* (defun foo (a) (bar (1+ a)))
; in: DEFUN FOO
;     (BAR (1+ A))
;
; caught STYLE-WARNING:
;   undefined function: COMMON-LISP-USER::BAR
;
; compilation unit finished
;   Undefined function:
;     BAR
;   caught 1 STYLE-WARNING condition
FOO

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

Символы имеют значение функции

В Common Lisp объекты функций для глобальных функций зарегистрированы как символы.

* (fboundp 'foo)
T
* (fboundp 'bar)
NIL

bar не имеет определения функции. Если мы позже определим функцию для bar, то код нашей ранее определенной функции foo будет вызывать эту новую функцию.

Как это работает? Код в foo выполняет поиск во время выполнения, чтобы получить значение функции символа bar и вызывает эту функцию.

Таким образом, мы также можем переопределить bar, и foo вызовет новую функцию .

Позднее связывание

Концепция выполнения функций во время выполнения часто называется позднее связывание . Это было описано для Lisp в 1960-х годах.

Таким образом, вызов глобальной функции

(bar 1 a)

концептуально в основном совпадает с

(if (fbound 'bar)
    (funcall (symbol-function 'bar) 1 a)
    (error "undefined function BAR"))

Имейте в виду, что это упрощенная модель c, и на самом деле файловый компилятор Common Lisp может использовать более агрессивные оптимизации (например, встраивание), когда поиск во время выполнения отсутствует.

Оценка форм функций

Стандарт Common Lisp гласит: Conses as Forms :

Если оператор не является ни специальным оператором, ни именем макроса, предполагается, что это имя функции (даже если для такой функции нет определения).

Answer 2

Совершенно независимо от конкретной c семантики Scheme & CL (которая, по крайней мере для CL, довольно сложна и может варьироваться различными способами), я думаю, вы не понимаете, когда вызываются функции. Я рассмотрю пример CL и приму совершенно наивную программу, которая оценивает определения, которые вы даете, по порядку. Программа, подобная этой:

(defun naively-evaluate-file (f)
  (let ((*package* *package*))
    (with-open-file (in f)
      (loop for form = (read in nil in)
            until (eql form in)
            collect (eval form)))))

Итак, хорошо, что делает эта функция, когда она просматривает ваш файл?

1. Она видит форму (defun function-defined-early () (function-defined-later)) и оценивает ее. Оценка формы defun определяет функцию function-defined-early и эту функцию, при вызове вызовет function-defined-later, которая еще не определена. Но функция не вызывается, поэтому проблем нет.
2. Он видит (defun function-defined-later () 1) и оценивает ее, что определяет (но не вызывает) function-defined-later.
3. Он видит (print (function-defined-early)), который вызывает function-defined-early и, следовательно, function-defined-later, оба из которых определены, и печатает результат.

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

---

Кроме того, такое определение с прямой ссылкой почти неизбежно, когда определение функций, если вы хотите разрешить рекурсию на языке. Рассмотрим это ужасное определение факториальной функции:

(defun fact (n)
  (if (= n 1)
      1
    (* n (fact (1- n)))))

Хорошо, когда система оценивает это определение, чтобы определить fact, она увидит вызов fact, который ... еще не определен , Что ж, возможно, вы могли бы сделать это в специальном случае (и компиляторы CL могут это делать): предположим, что этот вызов, по сути, является вызовом определяемой вами функции.

Таким образом, вы можете использовать специальный случай функции, которые только рекурсивно вызывают сами . Но как только у вас есть две или более функции, которые рекурсивно вызывают друг друга , вы не можете избежать одной из них в точке, где она определена (не вызывается!), Ссылаясь на некоторые еще не -определенная функция. Так что проблема прямой ссылки во время определения практически неизбежна.

(Ну, на самом деле вы могли бы избежать этого: вы могли бы сделать всю свою рекурсию с помощью Y комбинатора или чего-то еще, но пока это интересно в теории (и дать непонятные ответы на домашние вопросы), никто не хочет делать это на практике.)

Answer 3

Common Lisp - ассемблер в глубине души. Это очень динамично c. Рассмотрим следующее взаимодействие в CLISP:

[1]> (defun foo (x) (defun bar (y) y) x)
FOO
[2]> (bar 4)

*** - EVAL: undefined function BAR
The following restarts are available:
USE-VALUE      :R1      You may input a value to be used instead of (FDEFINITION
 'BAR).
RETRY          :R2      Retry
STORE-VALUE    :R3      You may input a new value for (FDEFINITION 'BAR).
ABORT          :R4      ABORT
Break 1 [3]> :r4
[4]> (foo 3)
3
[5]> (bar 4)
4
[6]> (defun foo (x) (bar (+ 1 x)))
FOO
[7]> (foo 3)
4
[8]> (defun bar (x) (+ 2 x))
BAR
[9]> (foo 3)
6
[10]>

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

Схема / Ракетка - это совершенно другое. Это состояние c в глубине души. Любые ссылки на функции разрешаются с помощью сред . Если вы переопределите свою функцию во вложенной среде «позже» (если это даже разрешено), исходная версия будет по-прежнему вызываться, если на нее есть ссылка.

Функции верхнего уровня исходного файла ракетки принадлежат та же среда. Это на самом деле ошибка при попытке загрузить исходный файл, где определена одна функция для вызова другой, которая на самом деле не определена в той же области, далее в исходном файле где-то _{(если не в какой-то библиотеке)} .

Common Lisp рад загрузить такой файл, потому что пользователю всегда разрешается определять недостающие функции позже любым способом - и в их распоряжении есть множество .

Answer 4

Говоря о Common Lisp, если вы пытаетесь загрузить единственную форму верхнего уровня (например, в SLIME: C-c C-c), которая ссылается на функцию, которая, как известно, не определена, вы обычно получаете предупреждение.

Однако load файл (например, в SLIME: C-c C-k) с несколькими формами верхнего уровня сначала загружает их все, и только затем (обычно) проверяет их на отсутствие ссылок. В любом случае, пропущенные ссылки во время компиляции или загрузки не являются ошибками.

Это немного упрощено, но глава CLHS очень обобщенная c для размещения очень разных реализаций и предложений (на мой взгляд) небольшое руководство. Однако приведенное выше является базовым c ожиданием - нет необходимости в предварительном объявлении в одном файле.