risorse | 99 bottiglie di... c++
“99 bottles of beer” è un brano musicale tradizionale degli Stati Uniti, caratterizzato da un testo molto lungo e ripetitivo. Per questa ragione viene a volte usato per valutare l'espressività di un linguaggio di programmazione verificando la comprensibilità del codice sorgente che genera il testo dell'intera canzone.
Il sito 99-bottles-of-beer.net raccoglie più di 1500 soluzioni diverse al problema, ma in questi giorni (agosto 2020) non è raggiungibile. In compenso, diverse realizzazioni alternative sono disponibili su Rosetta Code. Una curiosità: Donald Knuth ha dimostrato che la complessità della canzone è O(logN)!
Recentemente è uscita la seconda edizione di un libro che affronta il problema nel dettaglio: si intitola 99 bottles of OO, a cura di Sandi Metz, Katrina Owen e TJ Stankus.
Nell'articolo The Beginning of Extreme Programming Chet Hendrickson ricorda che Extreme Programming ebbe origine quando Kent Beck affrontò quasi per scherzo il problema delle 99 bottiglie di birra:
Kent Beck's Smalltalk implementation of '99 Bottles of Beer On The Wall' was the spark that launched Extreme Programming.
As a member of the Chrysler C3 team, I was challenged to learn how to build systems using Object Oriented techniques. One of the tools I and others on the team used was the comp.lang.smalltalk discussion group. Late in 1995, someone posted a message to most of the comp.lang groups asking the a program be posted in the group's language showing how the lyrics to the song '99 Bottles of Beer on the Wall' should be generated. There were several postings in the Smalltalk group, most of which were not too inspiring. I then saw the code listed below. A little while later, we decided we needed help performance tuning our application, and I suggested we talk to this Beck guy.
It turns out that our code was too much like that that did not impress me and with Kent's (,and Ron Jeffries's, Martin Fowler's, Jim Huangs's, and Ken Auer's) we built a system that looked much more like this one.
Riprecorro le tracce di Kent Beck utilizzando il linguaggio C++.
Subject: Re: 99 bottles of beer, auf Smalltalk Date: 1996/01/26 Author: Kent Beck There has been a discussion recently on comp.lang.smalltalk about how best to represent the song "99 Bottles of Beer on the Wall" in Smalltalk. Apparently, there has been some use of this song as a way of benchmarking various programming languages. I found the Smalltalk implementations appalling in their lack of use of the facilities that make Smalltalk so powerful. In particular, the previously published solutions all made heavy use of iteration and conditional logic. In my quest for intellectual purity, the limits of absurdity, and a decent distraction from this nasty cold, I have undertaken to write the one true definitive Smalltalk version. I hereby place the following code, written in literate program form, into the public domain, to stand as a monument for the ages, or until my hard disk crashes again, whichever comes first. Specification We need a program which takes as input, N, a number of bottles of beer and produces as output a string containing the N+l verses of the bottles of beer song. For N=3, the expected output is: 3 bottles of beer on the wall 3 bottles of beer Take one down and pass it around 2 bottles of beer on the wall 2 bottles of beer on the wall 2 bottles of beer Take one down and pass it around 1 bottle of beer on the wall 1 bottle of beer on the wall 1 bottle of beer Take it down and pass it around No bottles of beer on the wall No bottles of beer on the wall No bottles of beer There are no more to pass around No bottles of beer on the wall Note the subtle changes, verse to verse, that will necessitate the application of powerful object-oriented techniques. The third line changes, as does the plurality of the number of bottles. Verse The fundamental question in any object oriented development is "what is my first object?" Until this question is answered aright, nothing else the developer does will be of much use. Fortunately, we have in "song" a natural unit of computation, the Verse. Introducing varying kinds of Verses will allow us to capture with polymorphic messages logic that must be expressed as explicit conditionals in procedural languages. Such future flexibility is of uncertain use with a problem like BOB (Bottles of Beer song), but that's the thing about future requirements, you don't know what they're going to be. Object subclass: #Verse instanceVariableNames: 'stream' classVariableNames: '' poolDictionaries: ''
Immagino Beck si riferisca alle strofe (in grassetto le differenze dalla strofa precedente):
| N>2 | N bottles of beer on the wall N bottles of beer Take one down and pass it around N-1 bottles of beer on the wall |
| N=2 | 2 bottles of beer on the wall 2 bottles of beer Take one down and pass it around 1 bottle of beer on the wall |
| N=1 | 1 bottle of beer on the wall 1 bottle of beer Take it down and pass it around No bottles of beer on the wall |
| N=0 | No bottles of beer on the wall No bottles of beer There are no more to pass around No bottles of beer on the wall |
La serializzazione delle differenti strofe avverrà per via polimorfica a partire dalla classe base Verse. Questa contiene una referenza allo stream ove verrà serializzato il testo:
#include <iostream>
class Verse {
protected:
std::ostream& stream_;
public:
Verse(std::ostream& stream) : stream_{stream} {}
};
Each Verse will sing itself onto a Stream by singing its verse, then asking the next verse to sing itself. Verse>>sing self singVerse. stream cr. self nextVerse sing
In C++ il metodo diventa:
class Verse {
protected:
std::ostream& stream_;
public:
Verse(std::ostream& stream) : stream_{stream} {}
virtual void sing() {
sing_verse();
stream_ << "\n";
next_verse()->sing();
}
};
The recursion ends when you get to a Verse which represents a negative number of bottles of beer, the NegativeVerse. Many developers would have subclassed Verse to define NegativeVerse, but since it need only implement a single message, sing, and since there is no code sharing involved, I chose to subclass directly from object. This leaves me the option to factor Verse inheritance some other way, should that prove important in the future. Object subclass: #NegativeVerse instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' NegativeVerse >>sing "Do nothing"
Interessante questa osservazione di Beck: poiché l'oggetto NegativeVerse non condivide alcun codice con la classe base Verse non c'è ragione che derivi da essa... se non che in C++ è indispensabile, a meno di non ricorrere a qualche tecnica di type erasure — la cosa sarebbe invece possibile per esempio in Python. Procedo dunque con la specializzazione:
class NegativeVerse : public Verse {
public:
NegativeVerse(std::ostream& stream) : Verse{stream} {}
void sing() override {};
};
We will use other variations on Verse to capture the special cases in the song. PrecedingVerse will sing the Nth to second verse. PenultimateVerse will sing the verse in which there is one lonely bottle left, and UltimateVerse will sing that sad sad verse in which all the bottle are gone and their contents drained.
Per Beck le tipologie di strofe sono tre, non quattro come pensavo; accomuna infatti il caso N=2 al caso N>2. La ragione di ciò diventerà evidente più avanti.
The Verse instance creation method is a Factory Method, returning a Verse of the correct subclass depending on the bottle count. Verse class>>Count: aninteger stream: aStream aninteger < 0 ifTrue: ^NegativeVerse new aninteger = 0 ifTrue: ^UltimateVerse stream: aStream. aninteger = 1 ifTrue: ^PenultimateVerse stream: aStream. ^(PrecedingVerse stream: aStream) setCount: aninteger
Segue la definizione del factory method in C++:
#include <iostream>
#include <memory>
class Verse {
protected:
std::ostream& stream_;
public:
Verse(std::ostream& stream) : stream_{stream} {}
virtual void sing() ...
static std::unique_ptr<Verse> verse(int i, std::ostream& stream);
};
std::unique_ptr<Verse> Verse::verse(int i, std::ostream& stream)
{
if (i < 0) return std::make_unique<NegativeVerse>(stream);
if (i == 0) return std::make_unique<UltimateVerse>(stream);
if (i == 1) return std::make_unique<PenultimateVerse>(stream);
return std::make_unique<PrecedingVerse>(i, stream);
}
Singing a Verse
The singing of a Verse is represented by a method, each line of which causes the singing of one line of the song. In the future, it may be wise to further objectify the solution by creating a family of Line objects which sing individual lines. At this time, however, the solution does not seem to require this flexibility.
Verse> >singVerse
self
bottlesOfBeerOnTheWall;
bottlesOfBeer;
takeOneDown;
nextVerseBottlesOfBeerOnTheWall
Cantare una strofa vuol dire cantarne i versi in sequenza:
class Verse {
...
static std::unique_ptr<Verse> verse(int i, std::ostream& stream);
void sing_verse() {
bottles_of_beer_on_the_wall();
bottles_of_beer();
take_one_down();
next_verse_bottles_of_beer_on_the_wall();
}
};
The First Line The first line is sung by singing the number of bottles, followed by "of bottles of beer on the wall". Verse>>bottlesOfBeerOnTheWall self countBottles. stream nextPutAll: ' of beer on the wall'; cr
Il primo verso canta il numero di bottiglie seguito da “of beer on the wall”:
class Verse {
...
void sing_verse() ...
void bottles_of_beer_on_the_wall() {
count_bottles();
stream_ << " of beer on the wall\n";
}
};
The count of bottles of beer is sung by singing the number of bottles, followed by a space and the word "bottle", appropriately pluralized:
Verse>>countBottles
stream
nextPutAll: self bottleCountString;
space;
nextPutAll: self bottlesString
L'implementazione del metodo count_bottles deve consentire di coprire le tre casistiche:
Per questo si ricorre a due metodi virtuali:
class Verse {
...
void bottles_of_beer_on_the_wall() ...
void count_bottles() {
stream_ << bottle_count_string(); // virtual call!
stream_ << " ";
stream_ << bottle_string(); // virtual call!
}
};
The default implementation of bottleCountString prints the number of bottles in the receiver: Verse>>bottleCountString ^self count printString On the last verse, however, the word "No" is printed, rather than a number. This is represented by overriding bottleCountString in UltimateVerse: UltimateVerse>>bottleCountString ^'No' The pluralization of the word "bottle" is handled by implementing the default plural version in Verse, and overriding in PenultimateVerse: Verse>>bottlesString ^'bottles' PenultimateVerse>>bottlesString ^'bottle'
I metodi bottle_count_string e bottle_string vanno opportunamente definiti nella classe base. Il primo si appoggia ad un ulteriore metodo virtuale count che ritorna il numero iniziale delle bottiglie della strofa; il secondo emette la parola “bottles” che può essere considerato a buon titolo il comportamento di default:
class Verse {
...
void count_bottles()...
virtual int count() = 0;
virtual std::string bottle_count_string() {
return std::to_string(count()); // virtual call!
}
virtual std::string bottle_string() { return "bottles"; }
};
Counting and the Various Verses The count of bottles is explicitly represented by an instance variable in PrecedingVerse: Verse subclass: #PrecedingVerse instanceVariableNames: 'count' classVariableNames: poolDictionaries: '' PrecedingVerse>>setCount: aninteger count := aninteger PrecedingVerse>>count ^count The other verses, subclasses of Verse with no additional instance variables, represent their counts implicitly in the accessing method for "count": PenultimateVerse>>count ^1 UltimateVerse>>count ^0
Il numero delle bottiglie è memorizzato nel membro count_ in PrecedingVerse (versi con N>1), mentre è cablato in PenultimateVerse (N=1) e UltimateVerse (N=0). Già che ci siamo conviene specializzare i metodi virtuali ove necessario:
class PrecedingVerse : public Verse {
int count_;
public:
PrecedingVerse(int count, std::ostream& stream) : Verse{stream}, count_{count} {}
int count() override { return count_; }
};
class PenultimateVerse : public Verse {
public:
PenultimateVerse(std::ostream& stream) : Verse{stream} {}
int count() override { return 1; }
std::string bottle_string() override { return "bottle"; }
};
class UltimateVerse : public Verse {
public:
UltimateVerse(std::ostream& stream) : Verse{stream} {}
int count() override { return 0; }
std::string bottle_count_string() override { return "No"; }
};
Succeeding Lines
The second line is computed in much the same way as the first.
Verse>>bottlesOfBeer
self countBottles.
stream
nextPutAll: ' of beer';
cr
The third line shows variation in both the last and second to last verses. All the other verses sing it with:
PrecedingVerse>>takeOneDown
stream
nextPutAll: 'Take one down and pass it around';
cr
PenultimateVerse>>takeOneDown
stream
nextPutAll: 'Take it down and pass it around';
cr
UltimateVerse>>takeOneDown
stream
nextPutAll: 'There are no more to pass
around';
cr
Il secondo verso si ottiene facilmente dal primo omettendo il finale:
class Verse {
...
virtual std::string bottle_string() ...
virtual void bottles_of_beer() {
count_bottles();
stream_ << " of beer\n";
}
};
Il terzo verso va invece reso nelle varie declinazioni:
class Verse {
...
virtual void bottles_of_beer()...
virtual void take_one_down() = 0;
};
class PrecedingVerse : public Verse {
...
int count() override { return count_; }
void take_one_down() override {
stream_ << "Take one down and pass it around\n";
}
};
class PenultimateVerse : public Verse {
...
std::string bottle_string() override ...
void take_one_down() override {
stream_ << "Take it down and pass it around\n";
}
};
class UltimateVerse : public Verse {
...
std::string bottle_count_string() override ...
void take_one_down() override {
stream_ << "There are no more to pass around\n";
}
};
The final line is a bit strange. The last line of one verse is the same as the first line of the next, so the obvious implementation is to send "self nextVerse bottlesOfBeerOnTheWall".
Ecco l'osservazione chiave per cui la terz'ultima strofa, quella con N=2 può essere trattata come una di quelle che la precedono: non è lei a doversi preoccupare di emettere l'ultimo suo verso, se ne occuperà la strofa successiva!
However, the result of sending nextVerse to an UltimateVerse is a NegativeVerse, which doesn't know how to bottlesOfBeerOnTheWall. We would either have to duplicate the code from UltimateVerse in NegativeVerse or somehow send a message back to the UltimateVerse. Instead, we explicitly encode the fact that the final two verses have the same last line by hiding it behind a concatenated message, nextVerseBottlesOfBeerOnTheWall. The default implementation is simple: Verse>>nextVerseBottlesOfBeerOnTheWall self nextVerse bottlesOfBeerOnTheWall UltimateVerse overrides this to send itself the message bottlesOfBeerOnTheWall: UltimateVerse>>nextVerseBottlesOfBeerOnTheWall self bottlesOfBeerOnTheWall
L'ultimo verso della una strofa viene ottenuto richiedendo il primo verso alla strofa che segue tranne che per l'ultima che lo emette autonomamente, identico al primo verso:
class Verse {
...
virtual void take_one_down() = 0;
virtual void next_verse_bottles_of_beer_on_the_wall() {
next_verse()->bottles_of_beer_on_the_wall();
}
};
class UltimateVerse : public Verse {
...
void take_one_down() override ...
virtual void next_verse_bottles_of_beer_on_the_wall() {
bottles_of_beer_on_the_wall();
}
};
Utilities
Instances of the subclasses of Verse are created by passing along the Stream to be sung on. This is not public protocol, however, and is intended to be used only by the Verse class>>count:on: method.
Verse class>>Stream: aStream
^self new setStream: aStream
Verse>>SetStream: aStream
stream:= aStream
The next verse is computed by decrementing the count by one and sending it to the FactoryMethod in Verse:
Verse>>nextVerse
^verse
count: self count - 1
stream: stream
Finally, Verse provides a convenient Facade to sing any number of verses:
Verse class>>sing: aninteger
|writer|
writer := WriteStream on: String new.
(self
count: aninteger
stream: writer) sing.
^writer contents
Mancano pochi dettagli: la generazione della strofa successiva, l'implementazione dei metodi virtuali puri in NegativeVerse per renderla compilabile ed un metodo di utilità per ottenere il testo della canzone con un numero arbitrario di strofe:
#include <iostream>
#include <memory>
#include <sstream>
class Verse {
...
virtual void next_verse_bottles_of_beer_on_the_wall() ...
std::unique_ptr<Verse> next_verse() {
return verse(count() - 1, stream_);
}
static std::string sing(int n) {
std::ostringstream oss;
verse(n, oss)->sing();
return oss.str();
}
};
class NegativeVerse : public Verse {
public:
NegativeVerse(std::ostream& stream) : Verse{stream} {}
void sing() override {};
int count() override { return -1; }
void take_one_down() override {}
};
...
int main() {
std::cout << Verse::sing(99);
}
Il codice sorgente C++ è scaricabile da qui.
Beck prosegue con alcune considerazioni sulle prestazioni e una simpatica nota finale:
Performance This program's use of a Stream for concatenation makes it generally efficient. Here is a performance profile run with Profile/V (you were just waiting for the commercial plug, weren't you) and gathered on the recursive call to Verse>>sing. 100% (177) Verse>>sing ... 88% (155) Verse>>SingVerse ... :31% (54) Verse>>nextVerseBottlesOfBeerOnTheWall ... : :25% (44) Verse>>bottlesOfBeerOnTheWall ... : : :20% (35) Verse>>CountBottles ... : : : :14% (25) Verse>>bottleCountString ... : :5% (8) Verse>>nextVerse :26% (46) Verse>>bottlesOfBeerOnTheWall ... : :20% (35) Verse>>countBottles ... : : :15% (26) Verse>>bottleCountString ... :22% (39) Verse>>bottlesOfBeer .. . : :18% (31) Verse>>countBottles .. . : : :10% (18) Verse>>bottleCountString ... :8% (15) Verse>>takeOneDown .. . 10% (17) Verse>>nextVerse .. . NextVerse is redundantly computed twice, so its total of 15% could be cut in half. BottleCountString is computed three times, so its total could be cut from 39% to 13%. This could be further reduced by printing the bottle count directly on the stream, without creating an intermediate String. Final Comments With a bit of work, this program could be expanded to encompass a framework for singing repetitive songs of all kinds. At present, however, it stands as a monument to that sense of the ridiculous that is all that gets us through some times. Long may it wave. Kent Beck
L'introduzione dell'oggetto-sentinella NegativeVerse mi ha lasciato un po' perplesso, non facendo parte del dominio del problema. Potrebbe essere interessante verificare l'effetto che la sua eliminazione ha sul codice.
Pagina modificata il 30/08/2020