Subject: Re: how does recursion work?
From: Erik Naggum <>
Date: 16 Oct 2000 00:18:03 +0000
Newsgroups: comp.lang.lisp
Message-ID: <>

* "Cadwallader" <>
| now how does interpreter program execute this?

  A recursive function call is just a function call.

| wouldnt it have to get caught in an infinite loop to execute it?  to
| define recur-expt you need the definition for recure-expt, to define
| that recure-expt you need the defintion for recure-expt etc.

  You're actually asking about the way Lisp code is represented in
  memory more than how the interpreter (or even compiled code)
  executes the code.  The function call (recur-expt m (- n 1)) is
  represented as a list with three elements: the symbol recur-expt,
  the symbol m, and the list of three elements: the symbol -, the
  symbol n, and the integer 1.  But how did we get to the symbols?

  When you type in expression to the Lisp, they function read is
  called upon to turn your textual representation into an in-memory
  structure that consists mostly of pointers to objects.  One of
  Lisp's great and lasting ideas is that of having an external format
  for its internal memory structures and having reader and writer
  functions that convert between the two.

  I'm sure you know how lists are represented in memory, so let's
  consider how symbols are read and represented.  First, the reader
  collects all the characters that make up the name of the symbol.
  Then it looks up the symbol in the package (a named symbol table),
  or creates it there if it didn't already exist, and returns a
  pointer to the (new) symbol.  This pointer is stuffed in the list.

  The symbol itself has pointers to quite a number of things, among
  them the variable value and the functional value.  When you define a
  function, you set the functional value slot of the symbol structure,
  but the neat thing is that the pointer to the symbol remains the
  same.  The symbol also prints the same as before: with its name.

  Through this indirection at two different times, we avoid the whole
  issue of referring directly to the function.  The Lisp reader makes
  the list element refer to the symbol and when the interpreter needs
  to call the function, it looks up the functional value slot of the
  symbol and calls that value.

  It's all exceptionally elegant and simple, and doesn't need any of
  the abstract syntax tree nonsense needed in other languages that
  haven't figured out that it's pretty damn smart to represent your
  code as a data structure from the get-go (I hope you ignored that
  elaborate explanation because it made no sense in a Lisp context).

  I agree with everything you say, but I would
  attack to death your right to say it.
				-- Tom Stoppard