As far as I have been able to find, the earliest use of the word “destructuring” in its current
meaning is in the release notes for Maclisp 1742, from September
 New autoloadable interpreter macros: backquote ("`") and LET.
The "backquote" macro and the LET macro will be autoloaded when used.
The backquote macro allows generation of quoted structure with
evaluated inserts, and is compatible with the LISP Machine's version.
A "," within a backquote indicates evaluation of the next s-expression,
and ",@" indicates not only evaluation but also that the resultant form is
"spliced" into the surrounding list.
`(A B ,(+ 1 2)) reads in like (CONS 'A (CONS 'B (CONS (+ 1 2) 'NIL)))
which when evaluated generates (A B 3)
`(A B ,@(LIST 1 2)) read in like
(CONS 'A (CONS 'B (APPEND (LIST 1 2) 'NIL)))
which when evaluated generates (A B 1 2)
One can imagine how especially helpful this will be in writing definitions
The LET macro provides a convenient way to lambda-bind variables to
values. Its usages is as follows:
(LET ((var1 val1) (var2 val2) . . . (varn valn))
. . .
One may substitute merely "var" in place of "(var NIL)"
(LET ((A 1) (B 2) C)
Binds A to 1, B to 2, and C to NIL and then evaluates <forms>.
An extension to the binding of one variable, is a "pattern" of
variables, which are bound to the corresponding subparts of the
"val"; e.g., (LET ( ((A . B) '(CONS 1 2)) ((C () D) (LIST 1 2 3)))
would bind A to "CONS", B to "(1 2)", C to "1", and D to "3".
There is an attempt by the LET macro code to optimize the destructuring
operations of CAR and CDR over the original value.
If that's too informal, the term also occurs in 1980, in MIT Laboratory for Computer
Science TM-169 (“LOOP Iteration Macro”),
Destructuring provides one with the ability to “simultaneously” assign or bind
multiple variables to components of some data structure.
A 1972 thesis about APL program verification (Susan Lucille Gerhart, “Verification of APL
“destructuring” to mean something unrelated, though still related to programming.