Code Checking Automation - Computerphile
ฝัง
- เผยแพร่เมื่อ 17 ม.ค. 2017
- The original version of text messaging had a flaw, but how can we investigate problems with software quickly and easily? Professor John Hughes shows us how a modern tool can automate the process of code checking.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
![เปิดบ้านสุดหรู "เเจ็ค the ghost" ลั่นถ้าป๋องกพลลำบากผมเลี้ยงเอง!! l [Nickynachat]](http://i.ytimg.com/vi/1xbW4vULqGc/mqdefault.jpg)
this guy has done a very good job with this demo!
This was great, I've been looking for "test mobile app" for a while now, and I think this has helped. Have you ever come across - Reyndrew Software saccular - (search on google ) ? Ive heard some interesting things about it and my colleague got amazing results with it.
@K.D.P. Ross Indeed he is!
I'm currently studying my final year of Computer Engineering at the Chalmers University of Technology in Sweden. I remember the first course I ever took was Functional Programming in Haskell with this awesome guy, John Hughes! Not only did he help invent the language Haskell but he is also the best teacher I've ever had and I got the pleasure learning and properly testing functional programming code with QuickCheck (demonstrated in the video) which he developed together with another guy!
I really enjoyed watching this clip as it brings back a lot of memories!
I wish him nothing but the best!
Honestly my favorite part is his reaction to it failing the tests lol
KnownNever lol. Same.
4:00
an IT engineer having an iPhone? you dont see that very often
Donald Trump oh boy... here we go again...
Don't see people doing actual work in Emacs much either
Where are the IBM / Lenovo Thinkpads for goodness sake! I'm shocked and dismayed! :-D
Not very often, except all the time...
Yep, sounds like something Trump would say
This is great! Can we have more videos on functional programming and testing?
I would like one on unit testing. I've been programming for three years coming on four and the only time I've used it is in interviews :/.
The main problem I have with testing is that you can just as easily write the tests incorrectly as you can the code incorrectly.This system seems to be much better as it limits the amount of code you are writing as a test, get thousands of test cases without having to manually write thousands of tests, and can easily be adjusted to see where exactly the error is rather than just saying there is an error.
The idea is that it's extremely unlikely that you will write a test case that passes when it shouldn't as that would require you to make a specific kind of mistake in two specific places at once. Auto generated tests are awesome for components that can be easily isolated and can have a very well defined set of rules like the one he was showing. For more complicated systems, they don't really work though.
+Trend House It really depends on your coding style. However, I found code that is easily testable to work better in general because the amount of things you have to emulate during testing is also the amount of things that can go wrong with your code
+Trend House I agree with your risk assessment, but "more complicated systems" don't have to exist (at the unit test level). Code that "isn't easily isolated" is too tightly coupled, and code that "doesn't have a very well defined set of rules" isn't documented. That is, as long as you're not connecting to other programs, quickcheck should be applicable, and if not, then something is architected badly.
Additionally to what +Trend House said, you create these tests once, verify them and if you are confident your code and tests are "bug free" you can continue to develop your main code, branches with new features, new versions and test them after each cycle with the already set-up tests.
Sometimes this approach just doesn't work. Sometimes you'll have systems with various cross cutting concerns (and I don't just mean logging). Quickcheck is a convenient example for unit testing, but it also doesn't do anything complicated.
4:15 You just blew Apple users minds. They have no idea what witchcraft that touch screen magic is.
Yeah well. As a software engineer I would much rather get something else for my money than a completely useless touchscreen. Be it Apple or not.
maybe you missed the iphone in his pocket
Sauron Iphone is different than a laptop. Additionally, it is funny that touchscreens will be useless until apple implements them, then all of a sudden they will belittle any laptop without it.
+Richard Smith I have a lenovo with a touchscreen, the touchscreen is rather useless to me. It's cool that you can use it sort of like a tablet, but I haven't done that since I bought it. Using it like that just mean that you have to clean your screen constantly.
There are times when touch screens come in handy, like demonstrated in this video. Having both tablets and laptops, I find touch screen critical, but not as a primary input device, but secondary.
Try signing your name with a mouse. Good luck!
This is one of the best Computerphile videos I've seen in a while! Excellent demo and explanation. More of him and Professor Brailsford!
Absolutely fantastic demonstration. More from this man is 100% welcome :D
one of the best explanations I have seen. perfect mix of theory and examples. thanks!
I don't know why but this is the most fascinating computerphile I've seen
There is a lot of buzz around PBT over various dev conferences. And this 10 minute talk is the best intro with a brilliant example.
Great video. A great example of deducing a problem and how to logically think through it.
You don't always find the minimal example; you're just doing a naive search, which usually finds a simplified case, and usually the same one. Love quickcheck, though. It's gold!
Professor Hughes, I sent a msg to Computerphile's Facebook page asking for a video on what is the "Absence of errors" fallacy in software testing, and also asking for some explanation of the concept of "Exhaustive testing is impossible" and why we can never guarantee that software will not have any errors, bugs, or defects in it. Essentially this is a QA software testing subject, but I would really love to see this topic discussed by Computerphile. You would be a great facilitator of this video due to your experience with quick test. Thank you.
Very nice. I'd love to see more videos about testing, especially in the context of OO-languages
I can't help but think that the nature of the problem would have been apparent more quickly if the failed tests had shown both the original and unpacked messages. Stating that a test failed only tells us that the unpacked message was different than the original, but it doesn't tell us what's different about it. I personally noticed the suspicious 0 at the end of the failed tests very early on, but couldn't really be sure if that was really the culprit or not, but had the failed test also shown that the unpacked message was simply missing the 0 at the end, then it would have been quite simple to figure out how/why the code was cutting off that 0 at the end.
Very interesting and entertaining video ! Thank you
That was a beautiful explanation. Thank you.
Excellent video! Please do one on unums and why they're better than IEEE 754 floats.
QVear Have not heard of these, shall Google, thanks!
Better = many, many times slower?
Emacs on windows? Never seen that before.
It's the ubuntu core displaying on an X server on the windows machine. It's quite fancy really.
I ran Emacs in Windows 20 years ago. I expect today's builds are even better. But I don't like it anymore.
John, What about running docker containers? I love those things, I just discovered docker and I'm running a bunch of Linux containers with my environments inside my mac, then I pack the image and take the magic with me to any platform.
Windows Subsystem for Linux
This emacs? I feel so dirty, I have notepad scent all over me.
I've admired quickcheck since I first learned of it. But I've always wondered, why not automatically include some obvious tests in the generated cases such as boundary values (for an unsigned integer, 0 and the maximum valid integer value)? I would also think that storing failed tests so that every future test run will always re-test those cases would be a good idea.
The things is that a tool like this will go beyond most developer's imagination. It helps to find those unique cases we all from time to time overlook -- especially in the daily crunch to meet deadlines.
That's what smallcheck does, but loses a lot of the benefit of being able to spam arbitrary tests.
As far as saving failed tests goes, that's actually possible if you run quickcheck verbosely, or with some options.
In either case, one can actually create their own quickcheck generator. In Haskell that's usually done via a newtype wrapper, and a new instance of arbitrary (type-dispatch is your friend here).
You can actually get the failed results from base quickcheck by setting an option with "quickcheckWith", iirc.
If run in terminal, it dumps to stdout. There are other options, which could allow you to directly save the results to a file within Haskell.
There are indeed terminal/shell libraries in Haskell, and a library which can consume IO printouts... "silently"? But that's off the top of my head.
As far as special values go, again, you can produce an arbitrary generator easier than you think, especially as shown above in the video.
Now, if only you could quickcheck complex interactions between thousands of servers....
Great demo!
Great video!!
Very very useful video. Thanks.
omg 7 bit shifting kills my soul.. it's also in other standards
Excellent demo
So in the case in the video, the testing found a mistake from the specification.
However, there is a high likelihood that flaws specific to the implementation may not be found, if they are caused by a misunderstanding of the specification. It is quite likely the same programmer who would make both the packing and unpacking code, so testing should preferably include running the code on known correct samples of input/output. Those are not easily auto-generated (at least not without a separate implementation, which is known to work correctly).
That would probably be part of the testing suite, but he was showing the bit which checks that the pack & unpack code works together correctly.
But you cannot create those known correct samples of io yourself, since you don't know the specification.
What I'm not understanding is this: Is this a different way of doing unit testing, or is it a different kind of testing altogether? Can I use this kind of testing in every scenario where I would normally write unit tests?
love computerphile
Very good video.
fantastic video
SMS messages do have a length field, which specifies the number of characters that have been encoded. While it's true that the encoding alone can't distinguish the extra zero, the SMS structure as a whole is clear.
So there's no problem sending nulls in an SMS text message. (Except, if you need that stuff it's probably better to use binary encoding.)
is it possible to share the Erlang code? Also any reference to a text that properly describes the pack and unpack bug with the text message?
May i ask, what programming language or markup language and what software is he using?
Thanks, this was something I was just wondering today; what the heck is property based testing? Now I have an idea :)
Great video
+Computerphile, where does the Erlang code come from this demo, and does Prof John have a sample for people to test/use?
He says at the beginning that the code came from a company in France that does SMS encoding/decoding. I couldn't find it on the internet anywhere, so it may be proprietary. But nothing stops you from typing it straight up from the video.
The funny thing is, on the very first test that failed, I noticed the "0" at the end and thought that was the problem.
It is a testing and it is automatic. But it is not usual automation people do.I can see how it can be useful during development of complex mathematical solutions. But I don't see how it can be used in continuous integration. For example user registration in portal, yes we can test if all the possible data can be stored and run million iterations. But can we run it after each commit to test if something is not broken? First of all it is not consistent, second it is slow. In project I work in we already have build process that lasts 30 mins and to increase it 100 times would be disaster.
Does this still test the code for excluded cases, i.e. if it is already found out that every 10th sample will cause a problem and you exclude this case in your test statement, when generating input does it then skip 10% of all possible input data where the input data meets the exclusion criteria and not test the code on that?
I'm not sure you can write such a statement, at least not in quickcheck. The predicates of the implications are function of the input, not the test, so to speak. So you can say stuff like "if the input is of this shape, then this property should hold", but not "if I test this more then x times, then the property does not hold". QuickCheck assumes that each test is independent of the last.
I wanted to write something like this - glad to see it's real
Erlang has bit strings which it probably didn't when GSM came about so is the problem re-inventing what the language can do for itself ? In this case it's interesting in that it's a spec problem
This guy is the bomb!
How can I reproduce the demo? Is there a repo when I can find source and setup?
That was cool!
TH-cam won't let me put 0 characters in my message either :(
And to be more specific, it's not about the symbol "0" like the one I wrote just there. It's about the symbol with data value of 0, which is often called NULL. It's pretty much an empty character (not the same as a whitespace)
DeJayHank Ironically it's most commonly used at the end of strings. :p
mother of all demos
I almost screamed to the phone "they all end in zero!!!"
So is this still a bug with TXT SMS messaging service?
Ascii NUL is a nasty and/or special character anway. Strings in C are NUL terminated. Luckily, it will fail safe (or rather not at all) when there is an extra Ascii NUL character at the end of the string. I would be much more interested, how various "higher level" libraries/software with Ascii NUL in the middle of the message.
Many high level string libraries track the string length together with the string and thus don't need a special terminator character at the end.
Why did this not generate any problems for other messages that ended in zero? Shouldn’t [a,b,c,d,e,f,0] be indistinguishable from [a,b,c,d,e,f] for any ASCII values a through f?
It did. We saw 6 or so errors of that kind during the video :)
Daniel Beecham What I said is length 7 ending in zero being misinterpreted. He showed that unless the original string is a multiple of eight long it works.
Daniel Houck because your second Example has 6 chars. 6x7=42. This fits in 6 bytes (6x8=48), however in your first array, 7x7=49. This is bigger than 48, and thus requires an extra byte. Multiples of 8 length and their n-1 lengths, can add an extra character without adding an extra byte. Other multiples force another byte to be added - and thus code can recognize whether it was a sent 0, or a fill.
Ah, that makes sense. I was imagining it was a fixed-length format, not that the length was sent separately.
Wasn't that video showed already?
Would this work for Java code in Android Studio
Yes.
Erlang, eh? What does the professor think of Perl 6?
Thanks it was interesting.
For those who don't know these techniques were used even right at the beginning of coding decades ago.
Pretty cool. I guess this is Haskell?
Friggin smart !
This is nice for simple functions, but what about image processing software? The space of possible images is so large it is intangible and sometimes error is caused by things like "white pixel is sorrounded by too many black pixels". Or the program fails only when one image dimension is divisible by 7 and the other is not. There just too many cases and the (human) tester still needs to be creative to think out what could go wrong and design the tests accordingly.
+Libor Tinka Quickcheck is best suited to unit testing. You can still apply it to image processing software, but you'd do so with the underlying functions rather than testing via the user interface.
Not sure the random testing is a great idea all time...
btw what language is that? looks similar to prolog!
I think it's Erlang. I saw the file extension is .erl.
It's probably the best starting test case. Sometimes it's enough to ensure that a lot of random test samples passed.
In more strict systems, you might have to generate every possible input to ensure correct output. That can take a lot of time, and is thus more expensive to perform.
It is, the window title says Erlang
Why not?
In general, random testing increases the chances of finding a bug. It's still better to check edge cases yourself, but random testing excels is in generating "ordinary" data, which is the largest subset of all possible data by definition. In other words, having it doesn't hurt, it only improves testing. Of course, you won't use it if you can write a reasonable test that covers all the possible cases, but that's too trivial to even talk about.
Get more of the haskellers in front of the camera!
Putting the science in computer science.
What if the program is non reversible?
There's usually some criteria you could use to check correctness. For example, if you were writing a sorting algorithm, your test can be whether the list is in sorted order or not.
What about something like a text parser? The only way to know that the output is correct is to have a definition to compare against, but that definition is what you're trying to code.
What I usually do in this case is that I write a very simple implementation, that is hard to screw up, then I write the real thing, which is more complex, but much more efficient, and then let the computer compare the results of the two algorithm.
Maybe you could write a function which converts the structure you parsed back into text, and make sure that when you apply that function to a structure, then the parser, you'd get the same structure back
You really should consider creating definition separately from parser (and think of parser as an implementation of your definition). For example you can use classical BNF notation or something newer. Then it's trivially simple to generate texts that conform to specification and should be successfully parsed.
If you are writing parser without specification, you risk getting into mediawiki problem: language of wiki is defined as "anything that can be parsed by our parser", so it's really hard to make alternative parsers (for example if you want to port it to something better than php) that could be proven compatible.
That laptop looks very familiar (I have the same model :D )
Is that Emacs? Respect
All these tests can ever hope to demonstrate is that packing and unpacking functions have symmetrical bugs. 😐
I'd like to see expected outputs of the function / system under test stipulated, not calculated. And especially not calculated by the very system that is being tested.
Testing is nice and all but you can never be sure you program is truly error free. Can you do a video formal code verification which actually tries to prove correctness?
Can you do a video on Ethereum and non-cryptocurrency applications of blockchain?
+
What language/interface is this?
The language is Erlang, and he is using the emacs editor.
I wish my GF was as dirty as this guy's screen
Brb testing all my code properly xD
If he suggests some sort of theme park of code errors or dinosaurs, we should say no.
I think I'm missing something. How does it guarantee its "the simplest case"?
It doesn't. For example if there are multiple bugs, each one might have a "simplest case". But finding simplified if not the simplest case(s) to cause bugs helps a lot with pinpointing them down.
I'd still have appreciated if they had detailed how the found failing test cases were simplified.
ah gotcha; thanks
Your windows key and notepad pro membership have been revoked, pls test this now, thx.
This reminds me of The Halting Problem.
Eh, kinda. The whole idea of the Halting Problem, though, is you can't really test if a program stops or not.
True. I haven't watched the video completely when I was writing this.
10:11 I thought you were going to say 8 or 7 characters.
Not putting ASCII NUL (or any "character" from 0 to 31 and 127) into a *text* message seems obvious.
yes and no - I mean: The specification of the code has to contain this edge case and higher level code has to check for non-character s contained in the "text message". (and the higher level code needs to be tested for really rejecting Acsii Nul) A lot of exploits are based on things like NUL terminated strings and/or unchecked data lengths. So either-way: The test is valuable and documents an edge case that has to be handled.
SMS doesn't use ASCII, they usually use a 7-bit character set called "GSM 03.38". In that standard the "@"-sign is the all 0:s character. However, when there are exactly 7 spare bits a carriage return (0x0D) is inserted instead of (0x00). This means that your SMS can't be a multiple of eight characters and end with a carriage return. Your point still stands but the specifics are different.
As for the program in the video, failing the test (decode(encode(text))==text) on a message of a multiple of eight characters ending with 0x00 is certainly an error. Failing on a message of a multiple of eight characters ending with 0x0D, however, would be understandable since that is arguably outside of the specification.
So no line feeds or tabulation then? Not going to be using your products that's for sure!
***** _This video has nothing to do with the erroneous code._
The meta-point is that a CS prof uses a bad example in his mini-lecture.
RonJohn63 I use LF in SMS messages all the time. Your argument has been rejected and your business model is failing.
A WINDOWS COMPUTER????
Well, you need some substratum on which to run the Emacs operating system.
Walther Stolzing Preach Brother!
Hey... I'm starting to think you knew there couldn't be a zero in the 8th character this whole time
See EMACS, I like!
Divine Evil But... Windows :(
Nooooo! Where's the vim team at?
Yeah :(, sometimes it's inevitable... I am developing a FPGA/CPLD sytem that will be controlled on Linux. But all XILINX and Lattice IDEs run on Windows :(. So running a Linux VM is the solution :(.
Vishal Biswas silenced... how it should be!
People working in functional languages seem to be drawn to Emacs.
Is there a similar way of checking games ?
Because they are in a way more chaotic.
TheNefari Absolutely not. Imagine how much work it would take to encode buggy vs correct performance in a big 3d game. It would completely dwarf the game in both effort and file size.
jakejakeboom There absolutely is. Tests like these can be useful to test individual components.
What programming language is this?
In the video, the speaker mentions it is Erlang.
Oh, must've missed that. I haven't worked directly with erlang a lot, but I am trying to learn Elixir, which is based off erlang (uses beam VM), but has, in my opinion, nicer syntax.
I don't think this is applicable to the monster production, business rule, many UIs, many client, backend system that we have out there. Trivial input output yes, other than that, questionable. We even have big chunks of machine learning subsystems now which continuously change all the time and don't have a 1:1 mapping of input output, this is also an issue which Peter Norvig recently talked about.
Jackson .. the key is to employ different tools for different tiers of testing, there's no one size fits all tool. What you can have is a symposium of different testing tools/frameworks/methodologies work at different tiers or stages of testing (unit, functional, performance, soak, interoperability, UI .. and also importantly manual) to give you a comprehensive view of quality.
Sure they can. Such systems are most likely broken down into smaller pieces anyway, and you can test individual units with property based testing. The biggest problem is probably I/O, though you can generate I/O actions as well to some extent. Machine learning systems are also pretty easy to test. I mean, the systems change, but they do so in a known manner, and you can test that change.
Feels more like debugging tool instead of test tool
Mostly used as a test tool, written alongside implementation or as TDD.
Aren't we basically writing predicates to hold true about our code and then trying to satisfy them? That's what prolog lets you do except the program tries to satisfy them automatically. So we should all just be writing prolog!
Wow, he uses Emacs with a touch screen.
I find that Haskal functional dialect for quicktest ugly (as goes for most functional languages) but the usability of this tool is quiet wonderful.
Haskell not Haskal try scalacheck
You could also have used the first bit to indicate if the last value is zero.
Then you'd have written the @ character at the end.
I do not mean for every character, but at the beginning of the "string".
But then you are no longer packing 8 characters in just 7 bytes, you're back to 8 for 8.
But you can pack 9 characters in 8 bytes.
it would not fit then. 8 characters would fit perfectly into 7 bytes using this compression technique. If you used the first bit on the first character you would need to add another byte at the end for that one extra bit at the beginning.
So you may as well not compress at all since 8 characters to 8 bytes is uncompressed.
random unit tests is a bad practice: especially if you reproduce the issue one time every year: Prefer static fixtures ;)
Constraint random is all the rage... and formal and some other stuff...
The idea is use issues AND property base testing
Next: unit-tests
How useful are generated tests when your I/O isn't text. If it is for instance a graph of certain properties, you will spend more time with the random generator that will then spit out hours upon hours of useless tests that tell you nothing.
IMO these are nice in theory, this example was pretty and all, but in real life is something else better option about 99% of the time.
Better options like what? Not testing your code? Using a limited set of hand-written tests?
Yes, hand written tests, or batch of real data you already have paired up with correct outputs. Writing a test to match most edge cases will take you much less time than writing generator to whole tested space, at least for more complex systems. Not to mention edge case you may need to test is only one input set in the whole domain, which makes it less likely to be covered by random test.
Also, what was not really addressed in the video, what do you do when you cannot chain inputs to outputs? (A == unpack(pack(A))) Write generator for valid outputs? At that point you are basically writing tested code second time. So at best you'll be able to test only some properties of output that can be easily guessed from input.
This method of testing seems more useless the more I think about it.
Vojtěch Kaiser Unit tests are useful everywhere. If you have a component that cannot be easily tested, it is probably too complex and you should decouple it.
Furthermore, testing doesn't have to match exactly if it's not feasible. You get simply test for a property the output must have.
They can be very useful indeed! Especially for a language with algebraic data types, you can *easily* generate an AST which represents graphs, user actions and inputs, practically anything really.
@Vojtěch Kaiser; Also, you can always chain inputs to outputs.
Creating a testing loop is not automatic code checking...
The video is showing off a form of quickchecking, which automatically looks for failing cases, and simplifies it down to the most basic failing case for easy diagnosis. That's the automatic part.
Erlang
Why test your code when you can proof its correctness?
"Beware of bugs in the above code; I have only proved it correct, not tried it." (Donald Knuth)
YouHolli with help of proof assistant and appropriate language it's doable.
With low- and middle-level code it is doable, but with upper layers of logic it gets tedious. I find that a mix of algorithm derivation, proofs and testing works best for my programming problems.
What you mean by algorithm derivation?
@isj4: Intel want you to work for them; they'd love for their CPU's to be proved correct. Thy spend a lot of money trying to prove smaller components correctness.
evolutionary test case generation is far more interesting
Never heard about that testing technique before! Could you provide some information or resources? I'd greatly appreciate it.
They could have just used the last bit as a parody and not deal with that BS. That way you at least get to make use of it.
Power Max it's spelled parity
Since I've received quite a lot of SMS messages and none of them were horribly garbled mess I assume there is some error-correcting code built into the standard. The whole 7-bit thing was created precisely to reduce the amount of data sent, so "to make use of it" was precisely their goal.
Also parity is a horrible thing, it would tell you only if your message is corrupted, but you will not be able to fix it. It would be better to save 128 bits per 128 character message and use 7 of those bits for something like Hamming code which can detect 1 or 2 and fix 1 bit errors.
They also had very little bandwidth to work with back then, and wanted to be able to cram as many characters as possible into as few bits as possible. Compression algorithms were also too expensive for this task (this is, of course, no longer the case).
Emacs gang.
first
haha
:(
:(
Very interesting video, but I don't really appreciate Professor Hughes constantly flipping me off.