Re: Undefined in LISP

Daniel Cerqueira <dan.list@lispclub.com> writes:

Lawrence D'Oliveiro <ldo@nz.invalid> writes:
>

On Sat, 22 Mar 2025 12:07:14 +0000, Daniel Cerqueira wrote:
>

Lawrence D'Oliveiro <ldo@nz.invalid> writes:
 

On Fri, 21 Mar 2025 22:47:38 +0000, Daniel Cerqueira wrote:
>

I would like to know your thoughts, about what being undefined
actually is. Should an undefined expression be represented by a
symbol, or should an undefined expression be silent (without
returning a symbol)?

Should an attempt to evaluate such an expression even terminate?

 My opinion is that it should...

So undefined behaviour cannot be really undefined, it must return some
kind of value we are going to arbitrarily name as “undefined”?

>
Does every LISP S-expression need to have a value (need to be
evaluated)?  Is atributing a symbol to undefined behaviour needed?

In the context of the LISP 1.5 Programmer's Manual, "undefined" seems to
simply mean "has no value with respect to the semantics of the language
defined in the LISP 1.5 Programmer's Manual". As Kaz pointed out,
"undefined" occurs infrequently in the manual, but many of its usages
are strictly prescriptive or proscriptive: they state when function
calls and symbols are specified to have a return value or not, and many
of those usages appear in the language specification in Section I.

Things like `startread' which requires CURCHAR and CHARCOUNT to be
undefined under various conditions. `eq' yields always either *T* or
NIL, and must never be undefined, even if its arguments are bad. `cond'
must have an undefined value if no branch's predicate evaluates to *T*.

In Section I, 1.6, we get:

|1. In the pure theory of LISP.  all functions other than the five basic
|ones  need to  be  defined each  time  they  are to  be  used. This  is
|unworkable in  a practical  sense.  The LISP  programming system  has a
|larger  stock  of built-in  functions  known  to the  interpreter,  and
|provision for adding as many more as the programmer cares to define.

|2. The  basic functions. and cdr  were said to be  undefined for atomic
|arguments.  In  the system, they always  have a value, although  it may
|not always be meaningful.  Similarly, the basic predicate eq always has
|a  value. The  effects  of these  functions in  unusual  cases will  be
|understood  after  reading  the  chapter  on  list  structures  in  the
|computer.

Taken together with the above, what the relevant Section VII has to
indicate is that LISP expressions are semantically disjoint from the
computed internal structures the LISP programming system uses, and
that's the source of the ambiguity. LISP, the language, is not the same
as its machine implementation. LISP has some cases where its relevant
functions semantically mean nothing, in the same way that mathematical
functions can be locally undefined within their domain, like a function
f(x) := 1/x, for x = 0. `eq', in LISP 1.5, has the domain of atoms, and
so is undefined for non-atomic arguments, but is later explicitly
confirmed to actually just be one of *T* or NIL no matter if it is
passed bad arguments per se, presumably because this smooths over a
common source of programs halting and catching fire.

What this all means of course is that undefined basically stands in for
"implementation dependent". When the language formally has nothing to
say, the machine just keeps going. Programming languages don't extend
"all the way down". LISP (or Lisp (or Scheme (&c.))) the language is
made up partly of function definitions: like `car' and `cdr', whose
semantics define them for the domain of non-atomic arguments, but we're
explicitly told by the 1.5 PM that in the actual implementation they
always have a return value (even if it's not a value that means anything
where you'd be calling them), presumably also out of brute practicality.

Worth noting in the 1.5 PM is the "UNDEFINED SYMBOL" error emitted by
LAP that Kaz also pointed out. This error, we're told on page 75,
specifically indicates "assembly incomplete".  LISP, the programming
language, has no formal notion of assembly (or machine instructions) -
it's just a system for recursive function computation via a List
processing mechanism. But an actually machine-computable LISP must sit
upon such an implementation level. Alongside "UNDEFINED SYMBOL" we also
see LAP errors like "OUT OF BINARY PROGRAM SPACE". LISP also doesn't
have a semantics for memory; garbage collection is how we deal with the
emergence of this practicality on real hardware. "Undefined" funcall
values mean as much as return values on a call that blows up its stack.

LISP 1.5 is very old, there's sections in here about how the Overlord
manages tape ingestion. These are kept out of the language spec section
for good reason: they're implementational, and disjoint from the
language semantics too. We are responsible for ensuring Lisp code does
the right thing when exceptions occur, even when the language itself
specifically doesn't. More contemporary versions of Lisp have grown
condition handling systems specifically for this - to provide a place
within the language semantics to enable users to discretionally handle
various conditions, for when such behaviour properly resides within the
program's domain.

I'd say it's probably fruitless to try too hard to shoehorn "undefined"
into the semantics of the language, asking questions like when and where
it would be correct for Lisp to have a representation for states of
affairs which violate its semantics. Lisp also doesn't try to shoehorn
in a semantics of memory management (no malloc et al.) either. We just
want garbage collection so our code doesn't hang up and go out to lunch
when the unexpected happens.

Languages may introduce things like the Bottom type ⊥ because they
perform non-optional, non-trivial Type and Kind analysis as part of the
implementation of their type system. Rust does have a semantics of
memory management because one of its key design goals was to be like C
but not in the bad ways. Maybe Lisp, in the large sense, should or could
have use for these things (turnstile in Typed Racket comes to mind: a
metalanguage for Scheme-based type system computation at macroexpansion
time). But LISP, as specified by McCarthy et al. in the early days,
doesn't incorporate such things. Implementation dependent behaviour was
what you got.

--
;; Basically just a Boltzmann brain with extra steps.
;; -*- (rfc1924 "YiVsRYGrgTcVTuwaB^>SZ*Fa2X>2ZIXa") -*-