Say Hello to Sentient

Chris Patuzzo speaking at Ember London in February, 2017
98Views
 
Great talks, fired to your inbox 👌
No junk, no spam, just great talks. Unsubscribe any time.

About this talk

In this talk, Sentient’s creator, Chris Patuzzo, introducesthe language, its backstory, and the fascinating theory that lies below its friendly surface.


Transcript


This talk is going to be about my hobby project for the last kind of year to 18 months. I've been working on a programming language called "Sentient," which I'm going to give you an introduction to today. So, firstly, I'd like to say thank you to Jamie for inviting me here to speak. There won't actually be any Ember in this talk, but the language is written in Javascript, and you can integrate Sentient with your web applications if you would like. So, hopefully, that will be interesting to you. Okay, so, what is Sentient? Well, I'm not really sure how to define it but it's primarily a programming language that's particularly good at solving these kinds of combinatorial problems where there are lots of different combinations to try or kinds of problems where there are some complex rules to deal with. So here, for example, we have some simple puzzles like a Sudoku and a Rubik's Cube, some kind of graph problems, and this one in the bottom right-hand corner is called a magic square where the rows, columns, and diagonals all have to add up to the same number. This one in the middle is a particular favorite of mine. I can hopefully hit play. This is called the "Knight's Tour Problem" and the puzzle is to try and find a path around this chess board such that the knight visits every square exactly once. Almost there. It works, and this is one of the examples on the Sentient website which I'll show you in a bit. So, these are quite simple puzzles but Sentient is able to solve much more difficult puzzles as well. So, what's different about Sentient? Why not solve any of those problems in Javascript or Go or Elixir or Haskell or whatever programming languages already exist today? And you certainly could. Here's what that process might look like. Typically a developer would kind of look at one of these puzzles and they would go away and they would think about it for a while and they'd come back and come up with some kind of algorithm for solving it. So, here I've described what that might look like. So for example, you might go through each empty square in the Sudoku grid. You might try and find a number that fits in with the rules of Sudoku and then continue in that fashion until you kind of get yourself trapped in a corner. You get to a point where no numbers fit in a square and you have to backtrack, change some of those previous decisions and kind of try something else. And this would certainly work and there are lots of different Sudoku solvers online that will do exactly that but it kind of relies on the ingenuity of the developer to come up with a solution, that they have to think about this problem and come up with this algorithm. And this is where Sentient is fundamentally quite different. With Sentient, you'd assume someone had already given you this Sudoku puzzle and it's really your job to check, is this correct? You'd have to write this valid function that says is this a correct solution to the Sudoku puzzle or not? So perhaps they've put two numbers in the same column, that kind of thing. And so to illustrate this, I'm actually going to take a different example, this magic square one and just to remind you, the challenge here is to find a square of numbers such that all of the rows, columns, and diagonals add up to the same number. So in this case, that number is 15 and you can see the top row five plus one plus nine is 15 and any other combination in this square. You'd sometimes see this puzzle with the requirement that you must use unique numbers. People like to apply other rules as well, but we're going to keep it simple simple for now. So, here's what a Sentient workflow might look like. You'd kind of say to Sentient, here's how to check a magic square, which would be your Sentient program and then you'd ask it to go and find some for you. So you're not telling it how to actually solve this problem, you're just really telling it what it is. Like, what are the rules of this puzzle? Oh, it's cut off my slides. Okay, we'll just...we'll not worry about that. So here's the full Sentient program for finding magic squares. You can see the syntax is a bit strange. It's probably quite unfamiliar. [00:05:30] But I have tried to model this on...it's kind of a hybrid between Ruby and Javascript, a bit of a mishmash. Admittedly, it's not ECMA2015 Javascript, so this probably looks dated to you already. And here, I've annotated this source code with the different bits. So this section at the top is all about checking that the rule about the rows has been followed and then the columns and then the diagonals. So, let's take a few minutes to walk through this example and just kind of see how it works, see what it does. And, hopefully, this won't be cut off. It's not too bad. So the first thing we do is we declare a magic square. In this case, it's a two-dimensional array, like a grid, and it contains integers. We also declare a target at the same time and the key thing here is we don't actually know what the values of these things are at this point and we won't find out what those values are until we actually run the program. For now, we kind of have to assume these variables can take on any value, but what this does do is it gives us enough structure to be able to start expressing the rules of a magic square. We can kind of express the rules of a magic square on these hypothetical objects. And here's what that might look like pictorially. You can see this kind of three by three grid of integers and a single integer for the target. So now we're going to go through the rows. We're going to use this each method, and iterate through the rows in the magic square. [00:07:33] And then, we're going to use this keyword "invariant" to say the sum of numbers in that row must be equal to the target. So we're relying quite heavily on Sentient standard library here for things like "each" and "sum." And this keyword "invariant" is kind of like...it's a way of saying this is something that must be true, this is a rule of our problem that we're working on. [00:08:00] You can kind of think of this as like a constraint of the problem, some property that must hold. Moving on. So, again, we're now going to check the columns of this puzzle. We're using this method "transpose" which is something else coming from the standard library and that kind of has the effect of swapping rows for columns in a two-dimensional array. So that's exactly what we need here and then we can iterate through those columns and do the same thing again. We add up the numbers and check that they equal the target. And then finally, the slightly more complicated bit. This bit's all about the diagonals. I could've made this simpler by just individually picking out the elements in that array, but I wanted to make it a bit more general so that if we wanted to, we could find magic squares of different dimensions and we wouldn't need to change this code at all. So this is exploiting the property that this top left to bottom right diagonal contains elements where the row and column index are the same. So this is like zero zero, one one, two two. And then to get the other diagonal, we can just reverse the row first. So now our picture looks like this. We've got all of these kind of invariants in place and then the last step is to use another keyword called "expose." And the purpose of this is two-fold. When we run our program it means that these variables will be printed as standard output. These are kind of the things we're interested in. But additionally, Sentient will actually let us set those as input as well so we might want to find a magic square where the target is 15 or 25 and without changing any of the code we can do that. And in that regard, Sentient is quite unusual. When you think of a typical program, it would take some input, do something with it, and produce an output. Which is admittedly quite a simple picture of a program but hopefully you get the idea. Whereas Sentient has this fantastic bucket analogy. So, the idea here is that inputs and outputs are really the same thing. They're kind of in the same bucket, and you can give Sentient some of those values. So you can say the target is 15 and the top left number is three in my magic square and Sentient will try and fill up that bucket. It will try and give you the rest of those results based on those initial values. So, here I've recorded a little video of actually running this. You can install Sentient via the command line using Homebrew, Yarn, or NPM. And, this is it running. So you can see it gives you this command line utility which comes with lots of different options. In its simplest form, you can just give it your program and say "I want to assign some value to it," and Sentient will go off and it will print out some JSON and in this case, it's found a magic square represented in this way. And you can also say "Give me more that one solution. I want 10 magic squares that have this summation up to a target of 15. So that's one way to run Sentient programs but because the whole thing is written in Javascript, you can also run Sentient programs in a web browser, which I think is far more interesting. So I'm going to hit play. So here's the Sentient Lang website and down the left here are lots of different examples. We're going to go to the magic square one where I've made this little canvas Javascript enabled thing that lets you click through the different solutions. You can change the target here on the left and you can also... I'm not sure if I demonstrated it here, but you can click on values in the square, like this, and then find solutions that have that value fixed to six in this case. And that's kind of what I was saying about inputs and outputs really being the same thing in this language. So, some of you may be wondering, how does this thing work? Why is it that when I give it a target of 15 I get out this seemingly just arbitrary magic square. It doesn't even have sequential numbers in it. I don't have time to go into tons and tons of detail because it's fairly complicated, but I want to just give you a flavor of what this kind of process looks like. So, yeah, hold onto your hats. So, we take this puzzle, this program that we've written in Sentient programming language and the first thing we do is we kind of turn it into a digital circuit. So we turn it into this huge, huge circuit that kind of represents that problem. If you wanted, you could actually take that circuit away and you could synthesize it and you'd have a circuit that will tell you if something is genuinely a magic square or not. This circuit here is really just for illustrative purposes. In practice, it's much, much bigger than this. So the next step is we turn that into a fantastic Boolean equation. Again this would usually be really big, and this process is actually called a Tseitin Transform which is kind of how Sentient gets its name. It's almost an anagram of it but not quite. I mostly just really like the name of Sentient. And then the next step is to basically say that this equation needs to evaluate to true and now we're going to try and find solutions to this equation. So we're going to try and find things like this where we assign a true or false value to each of the variables in this equation such that this evaluates to true. And from this result, we can then reconstruct our magic squares. So sometimes we'll get lots and lots of different ways of satisfying this equation and what that means is that those solutions would relate to different magic squares. And in practice, I mentioned that these equations are much, much bigger. Here's one and this is about...this is actually the magic square of one but only about half of it as well. Luckily, I can offload this to...there are some very good solvers for dealing with these big Boolean equations, so I don't actually have to deal with that. I just have to integrate with them. So, I couldn't possibly do a Sentient talk and not mention my favorite puzzle. So here it is. This is a puzzle known as a self-enumerating pangram and it was actually the puzzle that inspired me to make this language in the first place. And the challenge here is to fill in these blanks and you try and fill those in with numbers except those numbers are written in English as English number words. So you can see four there has F-O-U-R and the challenge is to fill in all of these blanks and if the sentence is true after you've done that. So if you've filled in the sentence and it does indeed have four A's in it, then you've correctly found one of these sentences. Except this is really difficult because all of these words are...they themselves contain letters and as soon as you find a mistake and you go and change those mistakes, you've suddenly introduced more mistakes and it's this really tangled self-referential problem. I just really like it. It's interesting. It serves no practical purposes, but there you go. So you could take this away and in the same way as a Sudoku puzzle, you could just kind of try filling in these slots and if you get stuck, you backtrack, that kind of algorithm. And this is how many combinations there are to try, so a pretty big number and that's far too many to try even with a supercomputer by today's standards. This developer is going to struggle I think, but what they could do is write a Sentient program that says "Here's how to check a pangram." Of course, we need to kind of encode a look-up table for those English number words. You know, that's a challenge in itself but we can certainly do that and then we can ask Sentient go away and find some, tell me when you're done. And that takes about two minutes in the typical case. No supercomputers required and you'd end up with something that looks like this. So this is one dedicated to Ember London and you can see it does contain five A's, contains two B's, and I'm sure that's good enough to convince you. By all means, take a photo and you can check this yourselves. I also made one about broccoli funnels because I thought that was just a great term from the previous talks so thank you for that. Okay, so to wrap up, I hope I've given you a bit of an introduction to Sentient. It's quite a different way of thinking. There are lots of new concepts in there and I think you can almost be tricked into thinking it's like a regular programming language because it really does have a lot of the same constructs. It has iterators and functions and method...all of those kinds of things. So, hopefully, that's given you a bit more perspective which I think is really valuable as a developer to see how we can solve problems in different ways and the kind of tooling that's actually out there. So hopefully you'll be able to solve some problems for yourself in Sentient. Personally, I'm still exploring what it can do. It really...it baffles me sometimes. It's a great learning experience for me. If you do want to learn more about it, there's a website which you very briefly saw earlier, sentient-lang.org. I was on the Why Are Computers podcast with Tom Stuart who is here in the audience and we spoke in depth about kind of how this language came to be and some of the ideas behind it. Definitely worth checking out. And if you just want to look at the code and see how to write an abstract syntax tree parser and that kind of stuff, it's all on GitHub. If you'd like to get involved, that'd be amazing. Javascript isn't my first language. I've got about 38,000 lines of it now. It's all open source as well. It's under the MIT license and that's it for me. Thank you very much.