[squeak-dev] [Pharo-users] mentor question 4Trygve Reenskaug trygver at ifi.uio.noFri May 22 10:31:33 UTC 2020
Hi Richard, Many thanks for the copy of your question. Your problem fascinates me because it is an excellent example of an important class of problems: Translate an exact rendering of an algorithm in text form into the same algorithm in code form. I am using Squeak, but my code may also work in Pharo. The problem is: "/Given a number determine whether or not it is valid per the Luhn formula. The task is to check if a given string is valid/.". I like that you start with a precise rendering of the algorithm in an exact textual form, and also that you have augmented it with the intermediate results of an example execution. I lost you when you, in a later version, unnecessarily reversed the number. Maybe the reason for the reversal is that while you are aware of the/aString do: []/ method; you may have missed its companion: /aString reverseDo: []/. Luhn starts from the right and moves left, doubling the character every second digit. This part of the algorithm can be directly expressed in Squeak: /isSecond := false.// // Number reverseDo: [:char |// // isSecond // // ifTrue: [“double”]// // ifFalse: [“do not double”]// // isSecond := isSecond not]./ I have written 3 example methods where I first include the algorithm text as a comment. I then interlace the text with the corresponding Squeak statements to create an executable method that is an exact translation from text to Squeak. I have attached my program in /BabyExperiments.st /to this mail: /*LuhnTest>>luhnTest1: aNumber *// // " A method with a worked example inline. "// // " This method translates the problem text to Squeak and checks the given intermediate results."// // “ It only works for aNumber = '4539 1488 0343 6467' “/ /*LuhnTest>>luhnTest2: aNumber *// // " luhnTest1: with inline example removed. " // //" Validates aNumber and returns true or false.// //“ aNumber can be any String of characters. “// // " This method is identical to luhnTest1:, but without the intermediate specs and computations."/ /*LuhnTest>>luhnTest3: aNumber*// // “ The Squeak code from luhnTest2: now becomes a comment to be transformed into reasonable Squeak code./ I have no occasion to claim that my three methods are ‘obviously correct’. The writer of a text, be it a love letter or a piece of code, is notoriously bad at proofing their own text. An independent reviewer is therefore needed to check it. (I am a great believer in peer review as a tool for getting it right the first time). / //*LuhnTest>>testLuhnTest*// // “ This method runs luhnTest2: with 11 different numbers; some valid and some not. ”// // “ Some border cases are especially interesting because they can easily be validated mentally: '3', '34', '35', '356, '357'./ This experiment has been a learning experience for me. Again, thank you for sharing it, Richard --Trygve On 2020.05.06 06:36, Richard O'Keefe wrote: > I have forwarded a copy of the original message privately. > The problem is also described in RosettaCode. > One issue is that the input is described in the original message and > in the code I was responding to as "a number", but is in fact a string. > > > On Wed, 6 May 2020 at 04:04, Trygve Reenskaug<trygver at ifi.uio.no> wrote: >> Unfortunately, I have lost the original problem specification, so I have answered a different question. Could you please help me by repeating the original problem specification in full? >> >> I agree that my solution is not 'obviously correct' since it doesn't answer the right question. In one version of the solution, I had a prologue that catered for spaces, etc. Not having a textual form of the algorithm that provided for the extensions, I chose to omit them. >> >> >> >> On tirsdag.05.05.2020 15:20, Richard O'Keefe wrote: >> >> The irony is that the code I was responding to ISN'T obviously correct. >> Indeed, I found it rather puzzling. >> The problem specification says that the input string may contain digits >> AND SPACES. The original message includes this: >> >> Strings of length 1 or less are not valid. Spaces are allowed in the >> input, but they should be stripped before checking. All other >> non-digit characters are disallowed. >> >> Now it isn't clear what "disallowed" means. I took it to mean "may occur and >> should simply mean the input is rejected as invalid." Perhaps "may not occur" >> was the intention. So we shall not quibble about such characters. >> >> But I can't for the life of me figure out how Trygve's code checks for spaces. >> One reason this is an issue is that the behaviour of #digitValue is not >> consistent between systems. >> Character space digitValue >> does not exist in the ANSI standard >> answers -1 in many Smalltalks (which is a pain) >> answers a positive integer that can't be mistake for a digit in my Smalltalk >> raises an exception in some Smalltalks. >> >> This is a comment I now have in my Smalltalk library for #digitValue >> "This is in the Blue Book, but unspecified on non-digits. >> Squeak, Pharo, Dolphin, VW, VAST, and Apple Smalltalk-80 >> answer -1 for characters that are not digits (or ASCII letters), >> which is unfortunate but consistent with Inside Smalltalk >> which specifies this result for non-digits. >> ST/X and GST raise an exception which is worse. >> Digitalk ST/V documentation doesn't specify the result. >> This selector is *much* easier to use safely if it >> returns a 'large' (>= 36) value for non-digits." >> >> Let's compare three versions, the two I compared last time, >> and the "version A" code I discussed before, which to my mind >> is fairly readable. >> >> "Don't add slowness": 1 (normalised time) >> "Trygve's code": 6.5 >> "High level code": 30.6 (or 4.7 times slower than Trygve's) >> >> Here's the "High level code". >> ^(aString allSatisfy: [:each | each isSpace or: [each isDigit]]) and: [ >> |digitsReverse| >> digitsReverse := (aString select: [:each | each isDigit]) reverse. >> digitsReverse size > 1 and: [ >> |evens odds evenSum oddSum| >> odds := digitsReverse withIndexSelect: [:y :i | i odd]. >> evens := digitsReverse withIndexSelect: [:x :i | i even]. >> oddSum := odds detectSum: [:y | y digitValue]. >> evenSum := evens detectSum: [:x | >> #(0 2 4 6 8 1 3 5 7 9) at: x digitValue + 1]. >> (oddSum + evenSum) \\ 10 = 0]] >> >> This is the kind of code I was recommending that Roelof write. >> >> As a rough guide, by counting traversals (including ones inside existing >> methods), I'd expect the "high level" code to be at least 10 times slower >> than the "no added slowness" code. >> >> We are in vehement agreement that there is a time to write high level >> really obvious easily testable and debuggable code, and that's most >> of the time, especially with programming exercises. >> >> I hope that we are also in agreement that factors of 30 (or even 6) >> *can* be a serious problem. I mean, if I wanted something that slow, >> I'd use Ruby. >> >> I hope we are also agreed that (with the exception of investigations >> like this one) the time to hack on something to make it faster is AFTER >> you have profiled it and determined that you have a problem. >> >> But I respectfully suggest that there is a difference taking slowness OUT >> and simply not going out of your way to add slowness in the first place. >> >> I'd also like to remark that my preference for methods that traverse a >> sequence exactly once has more to do with Smalltalk protocols than >> with efficiency. If the only method I perform on an object is #do: >> the method will work just as well for readable streams as for >> collections. If the only method I perform on an object is #reverseDo: >> the method will work just as well for Read[Write]Streams as for >> SequenceReadableCollections, at least in my library. It's just like >> trying to write #mean so that it works for Durations as well as Numbers. >> >> Oh heck, I suppose I should point out that much of the overheads in >> this case could be eliminated by a Self-style compiler doing dynamic >> inlining + loop fusion. There's no reason *in principle*, given enough >> people, money, and time, that the differences couldn't be greatly >> reduced in Pharo. >> >> On Tue, 5 May 2020 at 21:50, Trygve Reenskaug<trygver at ifi.uio.no> wrote: >> >> Richard, >> >> Thank you for looking at the code. It is comforting to learn that the code has been executed for a large number of examples without breaking. The code is not primarily written for execution but for being read and checked by the human end user. It would be nice if we could also check that it gave the right answers, but I don't know how to do that. >> >> The first question is: Can a human domain expert read the code and sign their name for its correctness? >> >> >> When this is achieved, a programming expert will transcribe the first code to a professional quality program. This time, the second code should be reviewed by an independent programmer who signs their name for its correct transcription from the first version. >> >> --Trygve >> >> PS: In his 1991 Turing Award Lecture, Tony Hoare said: "There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." >> >> --Trygve >> >> On tirsdag.05.05.2020 04:41, Richard O'Keefe wrote: >> >> As a coding experiment, I adapted Trygve Reenskoug's code to my >> Smalltalk compiler, put in my code slightly tweaked, and benchmarked >> them on randomly generated data. >> >> Result: a factor of 6.3. >> >> In Squeak it was a factor of ten. >> >> I had not, in all honesty, expected it to to be so high. >> >> On Tue, 5 May 2020 at 02:00, Trygve Reenskaug<trygver at ifi.uio.no> wrote: >> >> A coding experiment. >> Consider a Scrum development environment. Every programming team has an end user as a member. >> The team's task is to code a credit card validity check. >> A first goal is that the user representative shall read the code and agree that it is a correct rendering of their code checker: >> >> luhnTest: trialNumber >> | s1 odd s2 even charValue reverse | >> ----------------------------------------------- >> " Luhn test according to Rosetta" >> "Reverse the order of the digits in the number." >> reverse := trialNumber reversed. >> "Take the first, third, ... and every other odd digit in the reversed digits and sum them to form the partial sum s1" >> s1 := 0. >> odd := true. >> reverse do: >> [:char | >> odd >> ifTrue: [ >> s1 := s1 + char digitValue. >> ]. >> odd := odd not >> ]. >> "Taking the second, fourth ... and every other even digit in the reversed digits: >> Multiply each digit by two and sum the digits if the answer is greater than nine to form partial sums for the even digits" >> "The subtracting 9 gives the same answer. " >> "Sum the partial sums of the even digits to form s2" >> s2 := 0. >> even := false. >> reverse do: >> [:char | >> even >> ifTrue: [ >> charValue := char digitValue * 2. >> charValue > 9 ifTrue: [charValue := charValue - 9]. >> s2 := s2 + charValue >> ]. >> even := even not >> ]. >> "If s1 + s2 ends in zero then the original number is in the form of a valid credit card number as verified by the Luhn test." >> ^(s1 + s2) asString last = $0 >> --------------------------------- >> Once this step is completed, the next step will be to make the code right without altering the algorithm (refactoring). The result should be readable and follow the team's conventions. >> >> >> P.S. code attached. >> >> >> -- >> >> The essence of object orientation is that objects collaborate to achieve a goal. >> Trygve Reenskaug mailto:trygver at ifi.uio.no >> Morgedalsvn. 5Ahttp://folk.uio.no/trygver/ >> N-0378 Oslohttp://fullOO.info >> Norway Tel: (+47) 468 58 625 >> >> >> -- >> >> The essence of object orientation is that objects collaborate to achieve a goal. >> Trygve Reenskaug mailto:trygver at ifi.uio.no >> Morgedalsvn. 5Ahttp://folk.uio.no/trygver/ >> N-0378 Oslohttp://fullOO.info >> Norway Tel: (+47) 468 58 625 -- /The essence of object orientation is that objects collaborateto achieve a goal. / Trygve Reenskaug mailto: trygver at ifi.uio.no <mailto:%20trygver at ifi.uio.no> Morgedalsvn. 5A http://folk.uio.no/trygver/ N-0378 Oslo http://fullOO.info Norway Tel: (+47) 468 58 625 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20200522/5a815508/attachment-0001.html> -------------- next part -------------- Object subclass: #LuhnTest instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'BabyExperiments'! !LuhnTest commentStamp: 'TRee 5/18/2020 17:21' prior: 0! The Luhn algorithm is a simple checksum algorithm used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. The given problem statement adds a preamble before the algorithm in text form. This class deals with the translation of the problem statement from English to Squeak language in three stages: luhnTest>>luhnTest1: translates the problem text statement to Squeak and checks the given intermediate results. luhnTest>>luhnTest2: translates the problem text statement without the intermediate results to Squeak. luhnTest>>luhnTest3: transforms the lunTest2: Squeak demo code into a reasonable Squeak code. It is the final result of this coding experiment. The result is tested against an number of examples in testing>>testLuhnTest. This test is of small value. As Esger Dijstra put it in 1969: Testing shows the presence, not the absence of bugs. Much better to aragne for an independent review the code and thereby also the execution of the infinite number of possible inputs.. The reader of this code is cordially invited to convice themself that assuming the problem stement is correct, the code has is bug free. (Or report the bug to trygver at ifi.uio.no) ! ]style[(385 90 23 81 23 272 52 135 179 1)c000117117,c000118118,c000117117,c000119119,c000117117,c000120120,,c000120120,cblack;,c000117117! !LuhnTest methodsFor: 'testing' stamp: 'TRee 5/18/2020 16:30'! testLuhnTest " LuhnTest new testLuhnTest " | testData testResult | testData := { #('4992 7398 716' true). #('4992 7398 715' false). #('49927398716' true). #('49927398716'.true). #('4916566735402340' false). #('5566157921842582' true). #('3' false). #('34' true). #('35' false). #('356' true). #('357' false). }. Transcript cr;cr;cr; show: 'luhnTest3';cr. testResult := true. testData do: [:arr | ((self luhnTest3: arr first) = arr last) ifTrue: [Transcript cr; show: arr first , ' validation gives ' , arr last printString , ' = OK'] ifFalse: [Transcript cr; show: arr first , ' GIVES PROGRAM BUG'. testResult := false]]. ^testResult ! ! !LuhnTest methodsFor: 'luhnTest' stamp: 'TRee 5/18/2020 15:31'! luhnTest1: aNumber " Program with inline example " " do it; LuhnTest new luhnTest1: '4539 1488 0343 6467'." " This method translates the problem text to Squeak and checks the given intermediate results." "Given a number determine whether or not it is valid per the Luhn formula. The Luhn algorithm is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. The task is to check if a given string is valid. Validating a Number Strings of length 1 or less are not valid. Spaces are allowed in the input, but they should be stripped before checking. All other non-digit characters are disallowed. " | isSecond strippedNumber sum toDouble withDoubledCharacters | strippedNumber := aNumber select: [:char | (char = Character space) not]. strippedNumber size <= 1 ifTrue: [^self error: ' invalid number.']. strippedNumber do: [:char | char isDigit ifFalse: [^self error: ' invalid number.']]. "luhnTest1: aNumber Program with inline example " " do it; LuhnTest new luhnTest1: '4539 1488 0343 6467'." " This method translates the problem text to Squeak and checks the given intermediate results." "Given a number determine whether or not it is valid per the Luhn formula. The Luhn algorithm is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. The task is to check if a given string is valid. Validating a Number Strings of length 1 or less are not valid. Spaces are allowed in the input, but they should be stripped before checking. All other non-digit characters are disallowed. " strippedNumber := aNumber select: [:char | (char = Character space) not]. strippedNumber size <= 1 ifTrue: [^self error: ' invalid number.']. strippedNumber do: [:char | char isDigit ifFalse: [^self error: ' invalid number.']]. " Example 1: valid credit card number 4539 1488 0343 6467 The first step of the Luhn algorithm is to double every second digit, starting from the right. We will be doubling 4_3_ 1_8_ 0_4_ 6_6_ Answer is wrong. There should not be any spaces here. " isSecond := false. toDouble := String new. strippedNumber reverseDo: [:char | isSecond ifTrue: [toDouble := char asString , toDouble] ifFalse: [toDouble := $_ asString , toDouble]. isSecond := isSecond not]. strippedNumber = '4539148803436467' ifFalse: [self error: 'A bug is found.']. " If doubling the number results in a number greater than 9 then subtract 9 from the product. The results of our doubling: 8569 2478 0383 3437 Answer is wrong. There should not be any spaces here. " isSecond := false. withDoubledCharacters := String new. strippedNumber reverseDo: [:char || charValue | isSecond ifTrue: [charValue := char digitValue * 2. charValue > 9 ifTrue: [charValue := charValue - 9]] ifFalse: [charValue := char digitValue]. withDoubledCharacters := charValue asString , withDoubledCharacters. isSecond := isSecond not]. withDoubledCharacters = '8569247803833437' ifFalse: [self error: 'A bug is found.']. " Then sum all of the digits: 8+5+6+9+2+4+7+8+0+3+8+3+3+4+3+7 = 80 " sum := 0. withDoubledCharacters do: [:char | sum := sum + char digitValue]. sum = 80 ifFalse: [self error: 'A bug is found.']. " If the sum is evenly divisible by 10, then the number is valid. This number is valid!! " sum \\ 10 = 0 ifTrue: [self inform: 'The program works OK!!'. ^true] ifFalse: [self error: 'A bug is found.'. ^false]. " my idea was to do these steps ..." ! ! !LuhnTest methodsFor: 'luhnTest' stamp: 'TRee 5/18/2020 15:53'! luhnTest2: aNumber " Program without inline example " " do it; LuhnTest new luhnTest2: '4539 1488 0343 6467'." " do it; LuhnTest new luhnTest2: '67'." " This method translates the problem text to Squeak. " "Given a number determine whether or not it is valid per the Luhn formula. The Luhn algorithm is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers and Canadian Social Insurance Numbers. The task is to check if a given string is valid. Validating a Number Strings of length 1 or less are not valid. Spaces are allowed in the input, but they should be stripped before checking. All other non-digit characters are disallowed. " | isSecond strippedNumber sum withDoubledCharacters | strippedNumber := aNumber select: [:char | (char = Character space) not]. strippedNumber size <= 1 ifTrue: [^self error: ' invalid number.']. strippedNumber do: [:char | char isDigit ifFalse: [^self error: ' invalid number.']]. " Example 1: valid credit card number 4539 1488 0343 6467 The first step of the Luhn algorithm is to double every second digit, starting from the right. If doubling the number results in a number greater than 9 then subtract 9 from the product. " isSecond := false. withDoubledCharacters := String new. strippedNumber reverseDo: [:char || charValue | isSecond ifTrue: [charValue := char digitValue * 2. charValue > 9 ifTrue: [charValue := charValue - 9]] ifFalse: [charValue := char digitValue]. withDoubledCharacters := charValue asString , withDoubledCharacters. isSecond := isSecond not]. " Then sum all of the digits " sum := 0. withDoubledCharacters do: [:char | sum := sum + char digitValue]. " If the sum is evenly divisible by 10, then the number is valid. This number is valid!! " sum \\ 10 = 0 ifTrue: [self inform: 'The Number is valid!!'. ^true] ifFalse: [self error: 'The Number is not valid!!'. ^false]. " my idea was to do these steps ..." ! ! !LuhnTest methodsFor: 'luhnTest' stamp: 'TRee 5/18/2020 16:22'! luhnTest3: aNumber " This validation method is a transformation the lunTest2 Squeak code into a reasonable Squeak code. " " I first removed al comments from the lunTest2 code and used it as a specification of lunTest3. " " The method returns true if aNumber is valid, otherwise false. " " print it; LuhnTest new luhnTest3: '4539 1488 0343 6467'." " print it; LuhnTest new luhnTest3: '67'." " | isSecond strippedNumber sum withDoubledCharacters | strippedNumber := aNumber select: [:char | (char = Character space) not]. strippedNumber size <= 1 ifTrue: [^self error: ' invalid number.']. " | strippedNumber isEven sum | strippedNumber := aNumber select: [:char | (char = Character space) not]. strippedNumber size <= 1 ifTrue: [^false]. " strippedNumber do: [:char | char isDigit ifFalse: [^self error: ' invalid number.']]. isSecond := false. withDoubledCharacters := String new. strippedNumber reverseDo: [:char || charValue | isSecond ifTrue: [charValue := char digitValue * 2. charValue > 9 ifTrue: [charValue := charValue - 9]] ifFalse: [charValue := char digitValue]. withDoubledCharacters := charValue asString , withDoubledCharacters. isSecond := isSecond not]. sum := 0. withDoubledCharacters do: [:char | sum := sum + char digitValue]. " " A design decision: Work with numbers rather than Characters. " sum := 0. isEven := false. strippedNumber reverseDo: [:char || charValue | charValue := char digitValue. isEven ifTrue: [charValue := char digitValue * 2. charValue > 9 ifTrue: [charValue := charValue - 9]]. sum := sum + charValue. isEven := isEven not]. " ^sum \\ 10 = 0 " ^sum \\ 10 = 0 ! !
More information about the Squeak-dev mailing list |