Revision of 1.1.3 Evaluating Combinations from 1 July 2009 - 10:01pm

The revisions let you track differences between multiple versions of a post.

Printer-friendly versionPrinter-friendly version

One of our goals in this chapter is to isolate issues about thinking procedurally. As a case in point, let us consider that, in evaluating combinations, the interpreter is itself following a procedure.

  • To evaluate a combination, do the following:
    1. Evaluate the subexpressions of the combination.
    2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

Even this simple rule illustrates some important points about processes in general. First, observe that the first step dictates that in order to accomplish the evaluation process for a combination we must first perform the evaluation process on each element of the combination. Thus, the evaluation rule is recursive in nature; that is, it includes, as one of its steps, the need to invoke the rule itself.[10]

Notice how succinctly the idea of recursion can be used to express what, in the case of a deeply nested combination, would otherwise be viewed as a rather complicated process. For example, evaluating

(* (+ 2 (* 4 6))
   (+ 3 5 7))

requires that the evaluation rule be applied to four different combinations. We can obtain a picture of this process by representing the combination in the form of a tree, as shown in figure 1.1. Each combination is represented by a node with branches corresponding to the operator and the operands of the combination stemming from it. The terminal nodes (that is, nodes with no branches stemming from them) represent either operators or numbers. Viewing evaluation in terms of the tree, we can imagine that the values of the operands percolate upward, starting from the terminal nodes and then combining at higher and higher levels. In general, we shall see that recursion is a very powerful technique for dealing with hierarchical, treelike objects. In fact, the “percolate values upward” form of the evaluation rule is an example of a general kind of process known as tree accumulation.

Figure 1.1:  Tree representation, showing the value of each subcombination.

Next, observe that the repeated application of the first step brings us to the point where we need to evaluate, not combinations, but primitive expressions such as numerals, built-in operators, or other names. We take care of the primitive cases by stipulating that

  • the values of numerals are the numbers that they name,

  • the values of built-in operators are the machine instruction sequences that carry out the corresponding operations, and

  • the values of other names are the objects associated with those names in the environment.

We may regard the second rule as a special case of the third one by stipulating that symbols such as + and * are also included in the global environment, and are associated with the sequences of machine instructions that are their “values.” The key point to notice is the role of the environment in determining the meaning of the symbols in expressions. In an interactive language such as Lisp, it is meaningless to speak of the value of an expression such as (+ x 1) without specifying any information about the environment that would provide a meaning for the symbol x (or even for the symbol +). As we shall see in chapter 3, the general notion of the environment as providing a context in which evaluation takes place will play an important role in our understanding of program execution.

Notice that the evaluation rule given above does not handle definitions. For instance, evaluating (define x 3) does not apply define to two arguments, one of which is the value of the symbol x and the other of which is 3, since the purpose of the define is precisely to associate x with a value. (That is, (define x 3) is not a combination.)

Such exceptions to the general evaluation rule are called special forms. Define is the only example of a special form that we have seen so far, but we will meet others shortly. Each special form has its own evaluation rule. The various kinds of expressions (each with its associated evaluation rule) constitute the syntax of the programming language. In comparison with most other programming languages, Lisp has a very simple syntax; that is, the evaluation rule for expressions can be described by a simple general rule together with specialized rules for a small number of special forms.11

[10] It may seem strange that the evaluation rule says, as part of the first step, that we should evaluate the leftmost element of a combination, since at this point that can only be an operator such as + or * representing a built-in primitive procedure such as addition or multiplication. We will see later that it is useful to be able to work with combinations whose operators are themselves compound expressions. [back]



Yup, that’ll do it. You have my aprpeciation.

1.1.3 Evaluating Combinations | SICP in Clojure

I appreciate, cause I discovered exactly what I used to
be taking a look for. You’ve ended my 4 day long hunt! God Bless you man. Have a great day. Bye

Also visit my blog Elana

1.1.3 Evaluating Combinations | SICP in Clojure

I am no longer sure where you’re getting your info, however great topic. I must spend a while learning more or understanding more. Thanks for wonderful information I used to be in search of this information for my mission.

Here is my weblog; Etsuko

1.1.3 Evaluating Combinations | SICP in Clojure

I drop a leave a response when I like a post on a site or I have something to contribute to the discussion.
Usually it is a result of the sincerness communicated in the post I browsed.
And after this article 1.1.3 Evaluating Combinations | SICP in Clojure.
I was moved enough to leave a comment :-) I actually do
have a couple of questions for you if it’s okay. Is it just me or does it appear like some of the comments look like written by brain dead individuals? :-P And, if you are posting on additional online social sites, I would like to keep up with you. Would you list all of all your community pages like your twitter feed, Facebook page or linkedin profile?

Feel free to visit my blog post …

1.1.3 Evaluating Combinations | SICP in Clojure

I was pretty pleased to uncover this website. I wanted to thank
you for ones time due to this fantastic read!
! I definitely liked every part of it and i also have
you book marked to check out new information on your site.

my weblog … polycystic ovarian syndrome Diet

You need targeted visitors for your website so why not try some for free? There is a VERY POWERFUL and POPULAR company out there who now lets you try their website traffic service for 7 days free of charge. I am so glad they opened their traffic system back up to the public! Check it out here:

1.1.3 Evaluating Combinations | SICP in Clojure

I feel that is among the such a lot vital info for me.
And i’m glad reading your article. But should observation
on some basic issues, The web site taste is perfect,
the articles is in reality nice : D. Just right job, cheers

Here is my webpage :: viestint

1.1.3 Evaluating Combinations | SICP in Clojure

Hiya! I simply wish to give an enormous thumbs up for the good data you

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options