I think i've understood more or less what a parsed Scheme program looks like (a binary tree with atomic values on the leaves, if i have understood correctly).  Can anybody please define to me, or give a reference, what a state (or a computation) of a Scheme program is?  Is it just the current binding plus a position, or a stack of positions, on the syntax tree?  (In such a case, i would appreciate a reference for a formal definition of Scheme binding as well :).)Is there some simple description, like the one for the Turing Machine (the program + the current content of the tape + the current position on the tape)?
In Scheme, what is formally a program's state?
binding;scheme;state
Both of the other answers look excellent to me.I would add the following: the state of a scheme program is... a scheme program!  That is, you can define a meaning function for scheme programs by showing how programs reduce to other programs. This is called a small-step semantics.  To show you what I mean: what are the steps--in a seventh grade sense--in evaluating 3 * (4 + 5)? According to the small-step rules provided by most teachers, the first step in evaluating this program is to reduce it to 3 * 20In exactly the same way, you can define a small-step semantics for Scheme that reduces a program to an answer by taking a series of reduction steps.