We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Lightning Talk - Quantum BogoSort

00:00

Formale Metadaten

Titel
Lightning Talk - Quantum BogoSort
Serientitel
Anzahl der Teile
12
Autor
Lizenz
CC-Namensnennung 3.0 Unported:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Ganze Zahl
Formale SpracheNummernsystemKünstliches LebenRechter WinkelVorlesung/Konferenz
ProgrammbibliothekProdukt <Mathematik>FunktionalGeradeObjektorientierte ProgrammierspracheZahlenbereichParametersystemNummernsystemDigitalisierungComputeranimation
AlgorithmusFolge <Mathematik>Formale SpracheQuantenmechanikProgrammierungAggregatzustandAnalytische FortsetzungBitBoolesche AlgebraFunktionalGrundraumInterpretiererLoopQuantisierung <Physik>ParametersystemFaktor <Algebra>ProgrammfehlerNummernsystemStrömungsrichtungMailing-ListeQuellcodeQuantencomputerMaskierung <Informatik>MultiplikationsoperatorKeller <Informatik>AlgorithmusFolge <Mathematik>Kategorie <Mathematik>Analytische FortsetzungDivisionGrundraumInterpretiererLoopQuantisierung <Physik>Radikal <Mathematik>Zellularer AutomatDatensichtgerätQuick-SortRandomisierungInteraktives FernsehenMailing-ListeCursorMotion CapturingMechanismus-Design-TheorieKoroutineComputeranimation
DatenstrukturProgrammierungInterpretiererNeuroinformatik
Vorlesung/Konferenz
Ganze Zahl
Transkript: Englisch(automatisch erzeugt)
So I wrote a scheme in Rust. I've never done a lightning talk with live coding in it before, so I'm just going to dive right into it. This is Scheme. It's a language that has lots of parentheses in it. And I have this file, amb.scheme, which is like ten lines of Scheme. And you call this function amb, and it's cut off,
so you can't see what that is doing. Oops. No. There we go. So you call amb and give it some arguments,
and as you can see, it just returns the first argument. So if I define a variable and call it with a bunch of arguments, then the value of the variable is whatever. And then there's another function in this library called require. So if I require x to be greater than two, then the value of x is three.
Got it? Okay. What? Yeah, okay. So I'll do one more example just to make sure everybody's got this concept. If I define a function called digit, like you call it with no arguments and it returns a digit, which is like this, then I could say, all right, make x a digit,
and make y be a digit, and then we've got these two numbers. And then if I require that the product of x and y be equal to like 24, then that happens, right? And then if I require x to be greater than y,
then that happens, right? You get the idea. Okay, cool. So to explain how this works, I need to talk a little bit about Quantum Bogosort, which is this algorithm. It's not an algorithm you would run on a quantum computer.
Instead, it uses the many worlds interpretation of quantum mechanics to make a better sorting algorithm. One, you take the list of values that you want to sort, and you just shuffle them randomly, which divides the universe into O of n factorial universes. That's just a thing that happens. And then if the list is not sorted, you destroy the universe.
And then if you survive, then your list is sorted. The other thing you need to understand is continuations. I think I have like two minutes left. Continuation is so scheme.
So when you capture the continuation of your program, it's like taking a snapshot of your stack. So you think of the stack as the call chain, like how did we get here? But what the stack really is, is it's the future of your program. It's what happens after the current function returns. Where is it going next?
And then after that, the continuation of your program. So the stack or the future, that's what a continuation is in scheme. And scheme just has a built-in function that grabs that. And it's useful for things like breaking out of a loop or implementing exceptions, because in a language that doesn't have syntax or keywords,
you have to do that somehow, and you can do it with continuations. This is too powerful to actually be useful in practice, because it's just like too mind-bending to use correctly. But coupled with the ability to destroy the universe, it is a lot of fun.
So now I have to explain in one minute how this actually works without speaker notes. So basically, the amp function splits the universe into many universes. It creates one universe for each argument that you pass to it. And then the require function, it just takes a boolean, any boolean value, right? And if that boolean is false, destroys the universe.
And it does that by invoking a previously captured continuation, which basically just like clobbers the current state of the program and replaces it with the previously captured continuation. You jump back in time and you redo it. And then the rest of it is just this crazily hairy custom hand-coded REPL
that uses stupid VT100 escape sequences to go back and erase everything that you did in the meantime. So if you have a terribly important practical use for this, please be careful, because if there's a bug
and there are actually no solutions to your problem, you will destroy all the universes. We don't want that. But here's where you can find the source code. And if you want to know more about AMP or more about schema in general, this is the book to grab. It gets kind of philosophical, nice that way. And it's got a lot of beautiful stuff in it that I had forgotten was there.
Okay. Phew.