Subject: Re: how does recursion work? From: Erik Naggum <erik@naggum.net> Date: 16 Oct 2000 00:18:03 +0000 Newsgroups: comp.lang.lisp Message-ID: <3180644283298512@naggum.net> * "Cadwallader" <ccadwal1@tampabay.rr.com> | 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). #:Erik -- I agree with everything you say, but I would attack to death your right to say it. -- Tom Stoppard