After looking into Alonzo Church's The calculi of lambda-conversion, and thinking a bit about rewriting systems, different definitions of algorithms, and about Lisp, I have come to mostly agree with John Clements' answer: that the state of a Scheme program is a "reduced" Scheme program.
I would like however to formulate my own version of it (which i can edit or improve if I learn more).
In my opinion, a state of a Scheme program can be viewed as a sort of a Scheme program, where instead of constant literals, arbitrary constant data values are allowed (they have to be allowed because I am not sure if, for example, an arbitrary float value can be written as a float literal).
For example, a program can execute as follows (the sequence of states):
The program:
(define x 0)
(set! x (lambda (x) (+ x 1)))
(define y 2)
(x y)
Program state after step 1:
(define x (lambda (x) (+ x 1)))
(define y 2)
(x y)
Program state after step 2:
(define y 2)
((lambda (x) (+ x 1)) y)
Program state after step 3:
((lambda (x) (+ x 1)) 2)
Program state after step 4:
(+ 2 1)
Program state after step 5:
3
Update. To confirm this point of view, here are quotes from Racket reference:
1.1 Evaluation Model
Racket evaluation can be viewed as the simplification of expressions to obtain values. For example, just as an elementary-school student simplifies
1 + 1 = 2
Racket evaluation simplifies
(+ 1 1) → 2
The arrow → above replaces the more traditional = to emphasize that evaluation proceeds in a particular direction towards simpler expressions. In particular, a value is an expression that evaluation simplifies no further, such as the number 2.
[...]
1.1.4 Top-Level Variables
Given
x = 10
then an algebra student simplifies x + 1 as follows:
x + 1 = 10 + 1 = 11
Racket works much the same way, in that a set of top-level variables are available for substitutions on demand during evaluation. [...]
Each evaluation step, then, takes the current set of definitions and program to a new set of definitions and program. Before a define can be moved into the set of definitions, its right-hand expression must be reduced to a value.
defined:
evaluate: (begin (define x (+ 9 1)) (+ x 1))
→ defined:
evaluate: (begin (define x 10) (+ x 1))
→ defined: (define x 10)
evaluate: (begin (void) (+ x 1))
→ defined: (define x 10)
evaluate: (+ x 1)
→ defined: (define x 10)
evaluate: (+ 10 1)
→ defined: (define x 10)
evaluate: 11
Using set!, a program can change the value associated with an existing top-level variable:
defined: (define x 10)
evaluate: (begin (set! x 8) x)
→ defined: (define x 8)
evaluate: (begin (void) x)
→ defined: (define x 8)
evaluate: x
→ defined: (define x 8)
evaluate: 8
I have also read about the SECD machine, closures, and environments, but they look to me like just a peculiar implementation method.
