Rules for top-level function definitions order in Racket and Common Lisp

Question

I found out that top-level declarations order does not seems to matter. Is there any documentation about that topic? I don't quite understand it.

Examples showing that a function can be called without being defined

#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

For Common Lisp it's a bit complicated, since implementations can use interpreted code, compiled code and heavily optimized compiled code.

Function calling in simple compiled code

For example SBCL by default compiles all code. Even the code entered via a read-eval-print-loop:

* (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

Since the function gets compiled immediately, the compiler sees that there is an undefined function. But it's just a warning and not an error. The generated code will call the function bar, even if it is defined later.

Symbols have a function value

In Common Lisp the function objects for global functions are registered as symbols.

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

bar has no function definition. If we later define a function for bar, then the code of our earlier defined function foo will call this new function.

How does it work? The code in foo does a lookup at runtime to get the function value of the symbol bar and calls that function.

Thus we can also redefine bar and foo will call the new function.

Late Binding

The concept of doing runtime lookup of functions is often called late binding. This was described for Lisp in the 1960s.

Thus a call of a global function

(bar 1 a)

is conceptionally basically the same as

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

Keep in mind that this is a simplistic model and in reality a Common Lisp file compiler may use more aggressive optimizations (like inlining), where there is no runtime lookup.

The evaluation of function forms

The Common Lisp standard says in Conses as Forms:

If the operator is neither a special operator nor a macro name, it is assumed to be a function name (even if there is no definition for such a function).