Category Archives: SICP

SICP – cap. 2 – Mappare liste – 25

Continuo da qui, copiando qui.

One extremely useful operation is to apply some transformation to each element in a list and generate the list of results. For instance, the following procedure scales each number in a list by a given factor:

nil l’ho definito, non c’è in Racket.

We can abstract this general idea and capture it as a common pattern expressed as a higher-order procedure, just as in 1.3 [qui]. The higher-order procedure here is called map. map takes as arguments a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list (Scheme standardly provides a map procedure that is more general than the one described here):

Now we can give a new definition of scale-list in terms of map:

map is an important construct, not only because it captures a common pattern, but because it establishes a higher level of abstraction in dealing with lists. In the original definition of scale-list, the recursive structure of the program draws attention to the element-by-element processing of the list. Defining scale-list in terms of map suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results.
The difference between the two definitions is not that the computer is performing a different process (it isn’t) but that we think about the process differently.
In effect, map helps establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined. Like the barriers shown in Figure 2.1, this abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences. Section 2.2.3 [prossimamente] expands on this use of sequences as a framework for organizing programs.

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – esercizi – 24

Continuo da qui, sono qui.

Exercise 2.20: The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter’s value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) ⟨body⟩)

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) ⟨body⟩)

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).

Note:  To define f and g using lambda we would write
(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

Forse SICP è troppo impegnativo per me; o forse devo sviscerare il senso del testo. Ho provato a vedere se Racket (nella REPL) ha la dot-tail notation  e pare di no  NO, c’è, vedi più avanti. Allora cosa devo fare? Chissà se Bill the Lizard

OK, devo costruire la procedeura same-parity come se la notazione ci fosse.

Ma aspetta: la cosa non mi convince, provo a indagare

o, meglio ancora

e ovviamente

L’esercizio non era comunque semplice, vedi sicp-ex e Drewiki.

OK, adesso lo pubblico? devo essere onesto e raccontare quello che faccio o riportare la ricostruzione finale? Siccome il blog è mio e lo leggo solo io (kwasy) la prima opzione mi sembra quella giusta 😜

Ovviamente devo impegnarmi di più: i post di SICP sono impegnativi. Molto 👽

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – esercizi – 23

Continuando da qui ecco un altro esercizio, qui.

Exercise 2.19: Consider the change-counting program of 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:

(define us-coins 
  (list 50 25 10 5 1))

(define uk-coins 
  (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:

(cc 100 us-coins)
292

To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:

(define (cc amount coin-values)
  (cond ((= amount 0) 
         1)
        ((or (< amount 0) 
             (no-more? coin-values)) 
         0)
        (else
         (+ (cc 
             amount
             (except-first-denomination 
              coin-values))
            (cc 
             (- amount
                (first-denomination 
                 coin-values))
             coin-values)))))

Define the procedures first-denomination, except-first-denomination and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

Uh! la prima parte è davvero immediata:

(define (no-more? coin-values)
  (if (null? coin-values) true false))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (first-denomination coin-values)
  (car coin-values))

Metto tutto nel file coins.rkt per comodità:

Poi la seconda parte 👿 non ci provo perché poi mi deprimo 👿 passo subito a Bill the Lizard 🚀 , il mio nerd di riferimento 😉

OOPS! 😳 dubbio atroce, forse ho frainteso –niente dimostrazione matematica– devo stare più attento; vista fatta sembra banale: Finally, we’re asked if the order of the list coin-values affects the answer produced by cc. We can find out quickly enough by experiment.

We can see that the order doesn’t matter. This is because the procedure recursively evaluates every sub-list after subtracting the value of the first coin from the target amount. It doesn’t matter if that value is the smallest, largest, or even if the values are shuffled.

Interessanti le osservazioni di sicp-ex 🚀

Devo affrontare in modo diverso questi esercizi; questo è alla terza modifica con riscrittura parziale 😯

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – esercizi – 22


Continuo da qui, un esercizio, qui.

Exercise 2.18: Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

Non ci sono riuscito, provo a giustificarmi 😯

La mia idea è di usare last-pair definita nell’esercizio precedente … c’è però il problema … non ho idea come farlo … mi sa che sbircio Bill the Lizard 😊

Arghhh!!! 👿
Come ho fatto a non pensarci! Bisogna ragionare ricorsivamente e basta appendere il car della lista al reverse del cdr della lista 😊

See how easy it is to start thinking in Scheme? dice Bill, rockz! 🚀
La mia stessa difficoltà la trovo in sicp-ex, non sono solo io 😙

OK 😡 sono troppo condizionato all’abitudine di ragionare à la Algol 🐙

Ma forse il problema (mio) è un altro: l’esercizio è semplicissimo, basta applicare quello detto “a lezione”; il guaio (mio) è che sono solo, non sono a lezione, non ho qualcuno cui confrontarmi.
E così ci ho ripensato parecchio, troppo, anche non volendo 😯

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – esercizi – 21

Continuo da qui copiando qui.

Exercise 2.17: Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

(last-pair (list 23 72 149 34))
(34)

Sarebbe molto facile se si potesse usare tutto Scheme (cioè Racket) ma non vale; non sono ancora stati annunciati. E allora… 👿
Dalle lezioni precedenti, tutta la storia di box-and-arrow e il cdr finale che contiene nil 💡

Molto simile alla soluzione di Bill the Lizard che spiega in dettaglio.
sicp-ex ha diverse soluzioni; non tutte valide (usa rest). Sconsigliata la versione che usa length, perché onerosa. Ripensandoci: rest è solo un sinonimo di cdr.

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – 20

Continuo da qui, copio qui.

Operazioni sulle liste
The use of pairs to represent sequences of elements as lists is accompanied by conventional programming techniques for manipulating lists by successively “cdring down” the lists. For example, the procedure list-ref takes as arguments a list and a number n and returns the nth item of the list. It is customary to number the elements of the list beginning with 0. The method for computing list-ref is the following:

  • For n = 0 , list-ref should return the car of the list.
  • Otherwise, list-ref should return the (n − 1)-st item of the cdr of the list.

Often we cdr down the whole list. To aid in this, Scheme includes a primitive predicate null?, which tests whether its argument is the empty list. The procedure length, which returns the number of items in a list, illustrates this typical pattern of use:

The length procedure implements a simple recursive plan. The reduction step is:

  • The length of any list is 1 plus the length of the cdr of the list. This is applied successively until we reach the base case:
  • The length of the empty list is 0.

We could also compute length in an iterative style:

Another conventional programming technique is to “cons up” an answer list while cdring down a list, as in the procedure append, which takes two lists as arguments and combines their elements to make a new list:

append is also implemented using a recursive plan. To append lists list1 and list2, do the following:

  • If list1 is the empty list, then the result is just list2.
  • Otherwise, append the cdr of list1 and list2, and cons the car of list1 onto the result:

Sì ho barato, di quote non si è ancora parlato 😊

:mrgreen:

SICP – cap. 2 – Dati gerarchici e closure – 19

Continuo da qui, oggi capitolo nuovo, qui.

Chissà se si può dire chiusura invece di closure? Dubbio 😯

Dati gerarchici e la proprietà closure
As we have seen, pairs provide a primitive “glue” that we can use to construct compound data objects. Figure 2.2 shows a standard way to visualize a pair—in this case, the pair formed by (cons 1 2). In this representation, which is called box-and-pointer notation, each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a numeral. The box for a pair is actually a double box, the left part containing (a pointer to) the car of the pair and the right part containing the cdr.

We have already seen that cons can be used to combine not only numbers but pairs as well. (You made use of this fact, or should have, in doing Exercise 2.2 and Exercise 2.3.) As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures. Figure 2.3 shows two ways to use pairs to combine the numbers 1, 2, 3, and 4.

The ability to create pairs whose elements are pairs is the essence of list structure’s importance as a representational tool. We refer to this ability as the closure property of cons. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Closure is the key to power in any means of combination because it permits us to create hierarchical structures—structures made up of parts, which themselves are made up of parts, and so on.

Nota: The use of the word “closure” here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word “closure” to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free variables. We do not use the word “closure” in this second sense.

From the outset of Chapter 1, we’ve made essential use of closure in dealing with procedures, because all but the very simplest programs rely on the fact that the elements of a combination can themselves be combinations. In this section, we take up the consequences of closure for compound data. We describe some conventional techniques for using pairs to represent sequences and trees, and we exhibit a graphics language that illustrates closure in a vivid way.

Nota: The notion that a means of combination should satisfy closure is a straightforward idea. Unfortunately, the data combiners provided in many popular programming languages do not satisfy closure, or make closure cumbersome to exploit. In Fortran or Basic, one typically combines data elements by assembling them into arrays—but one cannot form arrays whose elements are themselves arrays. Pascal and C admit structures whose elements are structures. However, this requires that the programmer manipulate pointers explicitly, and adhere to the restriction that each field of a structure can contain only elements of a prespecified form. Unlike Lisp with its pairs, these languages have no built-in general-purpose glue that makes it easy to manipulate compound data in a uniform way. This limitation lies behind Alan Perlis’s comment in his foreword to this book: “In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.”

Rappresentare sequenze
One of the useful structures we can build with pairs is a sequence—an ordered collection of data objects. There are, of course, many ways to represent sequences in terms of pairs. One particularly straightforward representation is illustrated in Figure 2.4, where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The car of each pair is the corresponding item in the chain, and the cdr of the pair is the next pair in the chain. The cdr of the final pair signals the end of the sequence by pointing to a distinguished value that is not a pair, represented in box-and-pointer diagrams as a diagonal line and in programs as the value of the variable nil. The entire sequence is constructed by nested cons operations:

Such a sequence of pairs, formed by nested conses, is called a list, and Scheme provides a primitive called list to help in constructing lists. The above sequence could be produced by (list 1 2 3 4). In general,

(list ⟨a₁⟩ ⟨a₂⟩ ... ⟨aₙ⟩)

is equivalent to

Lisp systems conventionally print lists by printing the sequence of elements, enclosed in parentheses. Thus, the data object in Figure 2.4 is printed as (1 2 3 4):

Be careful not to confuse the expression (list 1 2 3 4) with the list (1 2 3 4), which is the result obtained when the expression is evaluated. Attempting to evaluate the expression (1 2 3 4) will signal an error when the interpreter tries to apply the procedure 1 to arguments 2, 3, 4.

We can think of car as selecting the first item in the list, and of cdr as selecting the sublist consisting of all but the first item. Nested applications of car and cdr can be used to extract the second, third, and subsequent items in the list. The constructor cons makes a list like the original one, but with an additional item at the beginning.

The value of nil, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list. The word nil is a contraction of the Latin word nihil, which means “nothing.

Nota: It’s remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair? In Scheme, nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker (just as true is an ordinary variable that has a true value). Other dialects of Lisp, including Common Lisp, treat nil as a special symbol. The authors of this book, who have endured too many language standardization brawls, would like to avoid the entire issue. Once we have introduced quotation [prossimamente], we will denote the empty list as '() and dispense with the variable nil entirely.

:mrgreen:

SICP – cap. 2 – Esercizi: intervallo aritmetico – 18


Continuo da qui con gli esercizi, qui.

Exercise 2.15: Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa’s system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a “better” program for parallel resistances than par1. Is she right? Why?

Siamo alle solite 😡
Siccome non sono così bravo come vorrei cedo la parola ai nerds di riferimento.
Bill the Lizard dimostra matematicamente dov’è l’errore.
OK anche Drewiki.

C’è un ulteriore esercizio, l’ultimo della serie, questo:

Exercise 2.16: Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Al solito 😙

Mette in difficoltà anche Bill (stesso URL già linkato) che ricorre alla Wiki –come faremmo senza la Wiki? (auto-cit.). sicp-ex quasi si arrabbia, capiche?
Bravo Drewiki che svolge l’esercizio, indicando anche approfondimenti 🚀

:mrgreen:

SICP – cap. 2 – Esercizi: intervallo aritmetico – 17


Continuo da qui gli esercizi, oggi qui.

Exercise 2.14: Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals A and B, and use them in computing the expressions A / A and A / B. You will get the most insight by using intervals whose width is a small percentage of the center value. Examine the results of the computation in center-percent form (see Exercise 2.12 [qui]).

Ci ho girato attorno un po’ giungendo alla conclusione che sì, danno risultati diversi, effetto che aumenta all’approssimarsi dell’intervallo a 1. Non so quale sia il metodo migliore.
Cosa fanno i miei über-nerds di riferimento?

Bill the Lizard mi ha pre-copiato 😄 cosa che reputo di buon segno.
sicp-ex dice la stessa cosa. Bello il commento di voom4000. Rimanda a Drewiki che è più approfondito.

OK, post corto, senza codice, c’è tutto di là 😙
Spero che le cose cambino in futuro, davvero o mi deprimo 😡

:mrgreen:

SICP – cap. 2 – Esercizi: intervallo aritmetico – 16

agates

Continuo con gli esercizi, oggi qui.

Exercise 2.13: Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

s163

and

s164

He has written the following two programs, each of which computes the parallel-resistors formula differently:

(define (par1 r1 r2)
  (div-interval 
   (mul-interval r1 r2)
   (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval 
     one
     (add-interval 
      (div-interval one r1) 
      (div-interval one r2)))))

Lem complains that Alyssa’s program gives different answers for the two ways of computing. This is a serious complaint.

 Lem appartiene a una classe di cui conosco molti membri, bisogna imparare a conviverci 😉
L’esercizio è di matematica, niente codice ma sviluppo con carta e matita (o lavagna e gesso), ecco Bill the Lizard 😄
In alternativa c’è sicp-ex con de soluzioni, sempre mate.
I miei tentativi non sono sufficienti; questa è roba da über-nerds 😊

:mrgreen: