Category Archives: Racket

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

ox_1hg-z

Continuo da qui con gli esercizi, qui.

Exercise 2.8: Using reasoning analogous to Alyssa’s [post precedente], describe how the difference of two intervals may be computed. Define a corresponding subtraction procedure, called sub-interval.

Semplicissimo, basta sostiuire il segno + con - in add-interval –ahemmm NO, l’intervallo massimo si ha, vedi Bill, [a,b] − [c,d] = [a − d, b − c], ecco:

(define (sub-interval x y)
  (make-interval (- (lower-bound x) 
                    (upper-bound y))
                 (- (upper-bound x) 
                    (lower-bound y))))

Aggiungo questa procedura al file apa.rkt e eseguo:

s161

Nota per me: nel file apa.rkt mancavano le procedure lower-bound e upper-bound; aggiunte.

A questo punto mi verrebbe quasi voglia di continuare con il prossimo ma il post diventerebbe troppo lungo, rimando alla prossima puntata 😜

I miei nerds di riferimento: Bill the Lizard, sicp-ex (interessante) e Drewiki.

:mrgreen:

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

nikon-small-world-air-bubbles-formed-from-melted-ascorbic-acid-crystals

Continuo da qui, oggi copio qui.

Esercizio esteso: intervallo aritmetico
Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measured parameters of physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision.
Alyssa è una lisp hacker 😜

Electrical engineers will be using Alyssa’s system to compute electrical quantities. It is sometimes necessary for them to compute the value of a parallel equivalent resistance Rp of two resistors R1 and R2 using the formula

s158

Resistance values are usually known only up to some tolerance guaranteed by the manufacturer of the resistor. For example, if you buy a resistor labeled “6.8 ohms with 10% tolerance” you can only be sure that the resistor has a resistance between 6.8 − 0.68 = 6.12 and 6.8 + 0.68 = 7.48 ohms. Thus, if you have a 6.8-ohm 10% resistor in parallel with a 4.7-ohm 5% resistor, the resistance of the combination can range from about 2.58 ohms (if the two resistors are at the lower bounds) to about 2.97 ohms (if the two resistors are at the upper bounds).

Alyssa’s idea is to implement “interval arithmetic” as a set of arithmetic operations for combining “intervals” (objects that represent the range of possible values of an inexact quantity). The result of adding, subtracting, multiplying, or dividing two intervals is itself an interval, representing the range of the result.

Alyssa postulates the existence of an abstract object called an “interval” that has two endpoints: a lower bound and an upper bound. She also presumes that, given the endpoints of an interval, she can construct the interval using the data constructor make-interval. Alyssa first writes a procedure for adding two intervals. She reasons that the minimum value the sum could be is the sum of the two lower bounds and the maximum value it could be is the sum of the two upper bounds:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) 
                    (lower-bound y))
                 (+ (upper-bound x) 
                    (upper-bound y))))

Alyssa also works out the product of two intervals by finding the minimum and the maximum of the products of the bounds and using them as the bounds of the resulting interval. (min and max are primitives that find the minimum or maximum of any number of arguments.)

(define (add-interval x y)
  (make-interval (+ (lower-bound x) 
                    (lower-bound y))
                 (+ (upper-bound x) 
                    (upper-bound y))))

To divide two intervals, Alyssa multiplies the first by the reciprocal of the second. Note that the bounds of the reciprocal interval are the reciprocal of the upper bound and the reciprocal of the lower bound, in that order.

(define (add-interval x y)
  (make-interval (+ (lower-bound x) 
                    (lower-bound y))
                 (+ (upper-bound x) 
                    (upper-bound y))))

OK, con questo ecco…

Exercise 2.7: Alyssa’s program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

(define (make-interval a b) (cons a b))

Define selectors upper-bound and lower-bound to complete the implementation.

Raccolgo per comodità nel file apa.rkt le 4 procedure che caricherò in Racket.

s159

A questo punto ecco i risultati

s160

AhemmmmBill the Lizard e sicp-ex.

Mi sa che si continuerà con questa roba, prossimamente 😳

:mrgreen:

SICP – cap. 2 – cosa s’intende per dati? – esercizi – 9

mib2

Oggi qui, continuando da qui.

Exercise 2.6: In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the λ-calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Devo confessare che non ci sono riuscito 👿
Ho provato per un po’ ma non sono andato oltre a questo:

s155

che è solo la verifica che zero e add-1 sono procedure correttamente definite. In questi casi attivo il liz-segnale e arriva Bill the Lizard 😄 che risolve spiegando tutto.

È tutto di là, riporto solo il risultato, semplicissimo (una volta fatto 😜), questo

(define one
  (lambda (f) (lambda (x) (f x))))

s156

A questo punto diventa semplice definire two, basta chiamare una volta in più la f dentro lambda:

(define two
  (lambda (f) (lambda (x) (f (f x)))))

s157

Di lì Bill generalizza per i numeri successivi, Bill davvero über-rockz 😄.

Una cosa simile anche da sicp-ex e Spaceman Aki ma manca la spiegazione.

SICP a volte è troppo impegnativo per me. O dovrei essere più motivato, sapere di dover passare l’esame, senza l’aiuto di Bill &co.

:mrgreen:

SICP – cap. 2 – cosa s’intende per dati? – esercizi – 8

nikon-small-world-mouse-retinal-ganglion-cells

Continuo a copiare, oggi qui.

Exercise 2.5: Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. Give the corresponding definitions of the procedures cons, car, and cdr.

Panico! 👽  Mica sicuro di aver capito cosa si vuole che faccia 😯

La prima parte è semplice:

s152

Meno facile dal numero ottenuto ricavare i componenti a e b. Serve l’equivalente del comando di sistema factor:

s153

Devo determinare quante volte il numero è divisibile per 2 e 3, ahemmm, l’ha fatto uno dei miei nerds

(define (num-divs n d)
  (define (iter x result)
    (if (= 0 (remainder x d))
        (iter (/ x d) (+ 1 result))
        result))
  (iter n 0))

Applicando num-divs per 2 e 3 si ottiene la coppia –pair– di (a . b):

(define (pair num)
  (cons (num-divs num 2)
        (num-divs num 3)))

ho raccolto le due procedure nel file get-pair.rkt, ottengo:

s154

😄 Per avere a e b basta usare car e cdr della pair ottenuta, banale, non la riporto.

Da Bill the Lizard ho preso num-divs, più pulita della mia.
sicp-ex costruisce la funzione exp invece di usare expt built-in; poi diventa quasi normale.
La soluzione migliore è quella di Spaceman Aki, usa anche lui la funzione built-in remainder (ah! saperlo ricordarlo 💥).
Una soluzione simile anche da Drewiki.

:mrgreen:

SICP – cap. 2 – cosa s’intende per dati? – esercizi – 7

mib1

Continuando da qui oggi qui.

Exercise 2.4: Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

(define (cons x y) 
  (lambda (m) (m x y)))

(define (car z) 
  (z (lambda (p q) p)))

s150

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of 1.1.5.)

s151

Uhmmm… non ho seguito il suggerimento, anzi manco ci metto il link.
Meglio vedere i nerds di riferimento 😊
Bill the Lizard al solito spiega tutto bene.
sicp-ex è più sintetico ma OK.
Spaceman Aki mi ha precopiato.

Oggi era molto facile 😜 non è che i prof mi stanno tramando chissà cosa 👿 — OK, paranoia mode off 😄

:mrgreen:

SICP – cap. 2 – cosa s’intende per dati? – 6

Kazimir Majorinc

Kazimir Majorinc

Continuo da qui copiando qui.

We began the rational-number implementation in 2.1.1 [qui] by implementing the rational-number operations add-rat, sub-rat, and so on in terms of three unspecified procedures: make-rat, numer, and denom. At that point, we could think of the operations as being defined in terms of data objects—numerators, denominators, and rational numbers—whose behavior was specified by the latter three procedures.

But exactly what is meant by data? It is not enough to say “whatever is implemented by the given selectors and constructors.” Clearly, not every arbitrary set of three procedures can serve as an appropriate basis for the rational-number implementation. We need to guarantee that, if we construct a rational number x from a pair of integers n and d, then extracting the numer and the denom of x and dividing them should yield the same result as dividing n by d. In other words, make-rat, numer, and denom must satisfy the condition that, for any integer n and any non-zero integer d, if x is (make-rat n d), then

s149

In fact, this is the only condition make-rat, numer, and denom must fulfill in order to form a suitable basis for a rational-number representation. In general, we can think of data as defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfill in order to be a valid representation.

This point of view can serve to define not only “high-level” data objects, such as rational numbers, but lower-level objects as well. Consider the notion of a pair, which we used in order to define our rational numbers. We never actually said what a pair was, only that the language supplied procedures cons, car, and cdr for operating on pairs. But the only thing we need to know about these three operations is that if we glue two objects together using cons we can retrieve the objects using car and cdr. That is, the operations satisfy the condition that, for any objects x and y, if z is (cons x y) then (car z) is x and (cdr z) is y. Indeed, we mentioned that these three procedures are included as primitives in our language. However, any triple of procedures that satisfies the above condition can be used as the basis for implementing pairs. This point is illustrated strikingly by the fact that we could implement cons, car, and cdr without using any data structures at all but only using procedures. Here are the definitions:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else 
           (error "Argument not 0 or 1:
                   CONS" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

This use of procedures corresponds to nothing like our intuitive notion of what data should be. Nevertheless, all we need to do to show that this is a valid way to represent pairs is to verify that these procedures satisfy the condition given above.

The subtle point to notice is that the value returned by (cons x y) is a procedure—namely the internally defined procedure dispatch, which takes one argument and returns either x or y depending on whether the argument is 0 or 1. Correspondingly, (car z) is defined to apply z to 0. Hence, if z is the procedure formed by (cons x y), then z applied to 0 will yield x. Thus, we have shown that (car (cons x y)) yields x, as desired. Similarly, (cdr (cons x y)) applies the procedure returned by (cons x y) to 1, which returns y. Therefore, this procedural implementation of pairs is a valid implementation, and if we access pairs using only cons, car, and cdr we cannot distinguish this implementation from one that uses “real” data structures.

s150

The point of exhibiting the procedural representation of pairs is not that our language works this way (Scheme, and Lisp systems in general, implement pairs directly, for efficiency reasons) but that it could work this way. The procedural representation, although obscure, is a perfectly adequate way to represent pairs, since it fulfills the only conditions that pairs need to fulfill. This example also demonstrates that the ability to manipulate procedures as objects automatically provides the ability to represent compound data. This may seem a curiosity now, but procedural representations of data will play a central role in our programming repertoire. This style of programming is often called message passing, and we will be using it as a basic tool in Chapter 3 [prossimamente, nel lontano futuro 😊] when we address the issues of modeling and simulation.

Uhmmmm… da pensarci su 😙 😜 🚀
:mrgreen:

SICP – cap. 2 – abstraction barriers – esercizi – 5

nikon-small-world-crystals-of-salicin-a-painkiller-extracted-from-willow-tree-bark

Continuo da qui con gli esercizi, sono qui.

Exercise 2.3.  Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2. [post precedente]) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

Può essere semplice o meno, è in qualche misura indefinito (ecco a cosa servono i prof, interagire e chiarire). Per esempio abbiamo le funzioni trigonometriche sin e cos oltre a quelle dell’esercizio precedente? Altrimenti diventa meno semplice fare cose così:

s148

I miei nerds di riferimento si sono limitati alla versione blu. Al solito über la pagina di Bill the Lizard, c’è tutto, spiegato come si deve. Prof fategli delle proposte ancora prima di promuoverlo 😜
sicp-ex è OK anche se meno spiegato di Bill.
OK anche Drewiki 😀

La mia versione non la metto (non aggiungerebbe niente), meglio seguire Bill 😄

:mrgreen:

SICP – cap. 2 – abstraction barriers – esercizi – 4

best

Da qui oggi un esercizio, copiando qui.

Exercise 2.2.  Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you’ll need a way to print points:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

<mode nostalgia on> quando ero piccolo cose simili ne ho fatte parecchie, sigh 😊 <mode nostalgia off>. OK, vado.

;; point
(define (make-point x y)
  (cons x y))

(define (x-point point)
  (car point))  
  
(define (y-point point)
  (cdr point))

;; segment
(define (make-segment p1 p2)
  (list p1 p2))

(define (start-segment segment)
  (car segment))

(define (end-segment segment)
  (car (cdr segment)))
  
;; midpoint
(define (midpoint segment)
  (cons 
    (/ ( + 
      (car (start-segment segment))
      (car (end-segment segment))) 2)
    (/ (+
      (cdr (start-segment segment))
      (cdr (end-segment segment))) 2)))

;; print-point
(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

s147

La soluzione di Bill the Lizard è simile alla mia ma più sintetica, OK, lui è über.
Meno pulita quella di sicp-ex, usa variabili intermedie.
Bravo Spaceman Aki!

Solo io ho usato la procedura list, ma mi sembra che sia OK.

:mrgreen:

SICP – cap. 2 – abstraction barriers – 3

matticchio

Copiando qui proseguo da qui.

Oggi considerazioni molto generali; utili per chi comincia e chi non progetta con carta e matita, imho 😉

Before continuing with more examples of compound data and data abstraction, let us consider some of the issues raised by the rational-number example. We defined the rational-number operations in terms of a constructor make-rat and selectors numer and denom. In general, the underlying idea of data abstraction is to identify for each type of data object a basic set of operations in terms of which all manipulations of data objects of that type will be expressed, and then to use only those operations in manipulating the data.

We can envision the structure of the rational-number system as shown in figure. The horizontal lines represent abstraction barriers that isolate different “levels” of the system. At each level, the barrier separates the programs (above) that use the data abstraction from the programs (below) that implement the data abstraction. Programs that use rational numbers manipulate them solely in terms of the procedures supplied “for public use” by the rational-number package: add-rat, sub-rat, mul-rat, div-rat, and equal-rat?. These, in turn, are implemented solely in terms of the constructor and selectors make-rat, numer, and denom, which themselves are implemented in terms of pairs. The details of how pairs are implemented are irrelevant to the rest of the rational-number package so long as pairs can be manipulated by the use of cons, car, and cdr. In effect, procedures at each level are the interfaces that define the abstraction barriers and connect the different levels.

s145

This simple idea has many advantages. One advantage is that it makes programs much easier to maintain and to modify. Any complex data structure can be represented in a variety of ways with the primitive data structures provided by a programming language. Of course, the choice of representation influences the programs that operate on it; thus, if the representation were to be changed at some later time, all such programs might have to be modified accordingly. This task could be time-consuming and expensive in the case of large programs unless the dependence on the representation were to be confined by design to a very few program modules.

For example, an alternate way to address the problem of reducing rational numbers to lowest terms is to perform the reduction whenever we access the parts of a rational number, rather than when we construct it. This leads to different constructor and selector procedures:

(define (make-rat n d)
  (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

s146

The difference between this implementation and the previous one lies in when we compute the gcd. If in our typical use of rational numbers we access the numerators and denominators of the same rational numbers many times, it would be preferable to compute the gcd when the rational numbers are constructed. If not, we may be better off waiting until access time to compute the gcd. In any case, when we change from one representation to the other, the procedures add-rat, sub-rat, and so on do not have to be modified at all.

Constraining the dependence on the representation to a few interface procedures helps us design programs as well as modify them, because it allows us to maintain the flexibility to consider alternate implementations. To continue with our simple example, suppose we are designing a rational-number package and we can’t decide initially whether to perform the gcd at construction time or at selection time. The data-abstraction methodology gives us a way to defer that decision without losing the ability to make progress on the rest of the system.

Uhmmm… sì 😀

:mrgreen:

SICP – cap. 2 – introduzione a data abstaction -esercizi – 2

micmord

Continuo a copiare, qui.

Exercise 2.1.  Define a better version of make-rat that handles both positive and negative arguments. make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

s142

OK, adesso non va; ma è semplice, basta controllare il segno del denominatore: se negativo cambiare quello del numeratore.
Ecco il mio test per normalizzare il segno:

s143

OK, facile, adesso basta mettere il tutto dentro make-rat 😀
Però ho usato la procedura negative? di cui non si era mai parlato; bastava fare come Bill the Lizard, (< d 0):

(define (make-rat n d)
  (let ((g (gcd n d)))
    (if (< d 0)
        (cons (/ (* n -1) g) (/ (* d -1) g))
        (cons (/ n g) (/ d g)))))

s144

Diverso e più sintetico sicp-ex ma meno intuitivo, ci sarebbero problemi nell’eventuale manutenzione.

Perso: sono molto contento che –a parte l’uso del predicato non necessario– la mia soluzione sia uguale a quella di Bill, il mio lisper preferito (pari merito con tanti altri, nèh 😉 Ma –oggettivamente– non era difficile, anzi 😀

:mrgreen: