Programming Throwdown - Lisp

Episode Date: February 26, 2012

This show covers Lisp, one of the first functional langauge that is often used for academic purposes, but also has a place in industry. The episode talks about Cuda, how to write a Roguelike, becoming a good programming, and DOS games on Chrome. The tools of the biweek are Google Native Client (NaCl), a way to run native C/C++ code in a browser, and Handbrake, a way to make copies of your video DVDs. ★ Support this podcast on Patreon ★

Hosting provided by Host Tornado. They offer website hosting packages, dedicated servers, and VPS solutions. HostT.net. Programming Throwdown, Episode 11, Lisp. So I started the new job out here in California, and people are so much healthier out here. It's a little depressing, I'm not going to lie. Yeah, you know, I think it's, I'm kind of trying to weigh you down, but it's only a matter of time before you'll be playing Ultimate Frisbee and uh cross-country running and all that stuff

so so the my cube mate the person who works in the cubicle with me has one of these standing desks so oh yeah mine does too so she actually stands up the entire day she i mean she has a chair but i've never i don't think i've ever seen her use it and oh really see the guy who sits next to me he has a weird chair like when he does have to sit or want to sit, his chair is such that he, like, sits on his shins, kind of. What? Yeah, because his desk is high, right? So, he can't use a regular chair. So, he has this weird chair where his knees bend, like, only a little bit. That's weird.

It's more of, like, a leaning than a sitting. Like a massage chair or something. I don't know. This sounds weird. Oh man. I don't know how to describe it, but yeah, he stands all day too. It's pretty nuts. Yeah.

So did you get a standing desk? No, I've actually been thinking about it because my desk is kind of low and I'm kind of tall. And so I was like, maybe I should get a standing desk and then like a chair that's just really high, like a, you know, like a bar chair or whatever. And I was thinking that'd be pretty nice because sometimes I would like to stand up and stretch while you know working so i've made a compromise and i got an exercise ball um you know like a big exercise ball and i sit on that and the idea being that you know you can kind of bounce around and you have to keep yourself stable but i'm having to work up to it so like you know the first time i like sat into it kind of too long and my back was killing me so now i had the same thing did you yeah i sat on it i sat

on it and i was like i'm gonna try this out because there's one in our in our cube and uh like after like about halfway through the day around like three or four in the afternoon like my back started really hurting and i couldn't figure out why i was like god i just back pain i understand and i was like wait a minute it's this freaking ball yeah i didn't even last a day so now i'm working my way up so i've slowly been sitting more and more so i think today i sat you know like probably three or four hours on it and uh did okay like i'm not tired or sore or anything i'm trying to so that's one of my things and i i work on the fourth floor so i've been taking the stairs up and down i think i've only ridden the elevator twice the whole time i've been there nice that's really good so that's part of my uh you know try to do better

routine because i'm not playing a super extreme exercise frisbee with you yes so i just uh i found uh you know um at our work they have uh like sort of like a jungle gym for adults that they had just built yeah this is pretty crazy so um they have like that climbing rope did you ever have that when you're in middle school it's just like a huge rope i know what you're talking about yeah yeah you have to kind of use your arms they have one of those but it's it's it's made of like plastic fiber instead of wool and so um it has it gives you like the worst rug burn so i tried it for the first time yeah and i got about halfway up the rope and i gave in and when i when i was coming down my hands they just got all tore up and then all the jocks laughed at you yeah that's right i

got beat up even at work it's sad high school memories all over again um yeah they stuffed me a trash can it wasn't pretty but they have like uh those things that have you seen these they're like platform like tables they look like tables but they're anchored into the ground and you have to sort of jump onto the table but it's really high it's like twice the height of a coffee table they actually have different sizes but the one i was on was like that and so just from standing still you have to jump onto this table and then jump off and then keep going back and forth and they had like a whole bunch of different like they had like a little demo day and i went to it and they had little routines that you should do to get you know more fit and stuff like that but being fit is definitely like huge over here in

california yes it is and i'm failing at it so my goal is to improve slightly so i can feel better about myself yeah it's like let's get all the nerds in one place and then try and get teach them to exercise yes they put like a few non-nerd people in just to make the nerds feel bad yeah that's right let me show you how it's really done if you weren't a nerd so well on to programming news yes speaking of exercising let's exercise our processors with uh with running cuda natively on the cpu yeah yeah so um i know you've been you've done this a little and i've done some of this but there's a uh you know the new one of the new things that's come out recently is the programming general purpose programming of graphics processing units so the things that are in your computers pretty much all the computers nowadays to some extent, to run your graphics and accelerate anything with drawing to the screen,

with 3D rendering like for games and all that's handled by these GPUs, which basically come down to many core, small, lightweight processing cores that are able to do tons of tasks in parallel for instance when you you know have to figure out where a triangle should show up on the screen there's maybe millions and millions of triangles on us in a given frame of a game and so you can do all of those calculations in parallel and so these graphics processing units have gotten really really good at doing things in parallel. And probably the most... So I don't know.

So ATI and NVIDIA are the two big graphics processing people. Well, ATI got bought by AMD. Okay. But yeah. So AMD and NVIDIA. And Intel's now starting to do... Well, both of them now are starting to even... Intel and AMD are starting to do interesting things with putting GPUs on the CPUs directly

and putting really high bandwidth connections between them. So that's kind of interesting. But NVIDIA has a language that you use to do this general purpose programming for GPUs. And AMD has their own as well. But Nvidia's is called CUDA. And it's a kind of a dialect of C, which is limited. You can't do a lot of the same things you might be able to do in regular C or C++.

But for the most part, it's just a C program. And it runs maybe thousands or hundreds of thousands of threads and each one just does a little task so massively parallel and that's really good for certain operations like image processing operations graphics operations certain kinds of like simulations like monte carlo simulations where you you know choose random numbers and you know run a little simulation based on that random number. Things like that can be really good. The problem is that the code between what you write for a CPU

and what you write for a GPU are so very different from each other. It can almost make the expense of going through creating a separate code base for your CUDA programs. Unless you're one of these few cases that get you know a thousand x speed up from it it almost makes that not worth it and it's better just to buy or pay more to get the latest and greatest CPU so that you can just have one code base and yeah and the other part of it too is you know the GPU you have to communicate with it it's sort of like an external processor

you know whereas the cpu it's right on board and so because of that debugging is much easier on the cpu like you could take a program that's running and just stop it and say all right right now what's the state of the system now let's process one instruction now where are we at but you know because you have this this GPU on a completely different card, the debugging becomes much more difficult. You can't do the kind of cool, hacky things that you can do, that debuggers do for a CPU. Right. Oh, and the other thing is that the pipe between the CPU and GPU, the PCI Express bus, is limited in its speed.

You think it's really fast, but it's really not all that fast. So there's all this overhead of sending data to the GPU to get processed and getting your results back. And so there's a crossover point where when your data gets big enough and parallel enough, it's worth it to send it there and get it back, it's faster, but below that threshold and get it back it's faster but below that threshold

is better to do it on the cpu but if your program has dynamic you know size of data you kind of either have to have code in both and you know choose on your own which one to run or you just got to pick one or the other and suffer you know non-optimal. But what would be ideal is if you could write, for instance, just CUDA code. Well, ideal would be just write C or C++ code and have CUDA automagically do all of this for you. It would be awesome. But short of that, if you could write CUDA code that when you're below a certain size limit, you know the overhead's too much. And so you go ahead and just run that on your cpu or in some case where the gpu isn't available um so for portability reasons to be able to run

the cuda code native on you know just the regular processor the cpu would be a big advantage or when you're doing development you want to yeah run it on the on the cpu once and make sure it works and then run it on the gpu the rest of the works and then run it on the GPU the rest of the time. Yeah, so all those cases are really important cases. And it has not been something that was the first priority because they wanted to get this working right first. But now it looks like some other people are making progress in being able to compile CUDA code down to run on x86

to enable this kind of thing to take place. So it's kind of an interesting article. Hopefully we'll see more of this in the future because it could be a big boon to the widespread use of these GPU processing paradigms. Yeah, yeah, definitely. Yeah, I think it's awesome so uh a lot of people kind of write us and they say oh i really like making video games or i think somebody sent us an email a little while ago and they were using i think visual basic to to write video games and games seem to be it's you masquerading as somebody else oh but they um you know a lot of people get into computers because of games i mean i i love games that's one of the reasons why i got into computers a lot of

my friends have said oh the reason why i got into computer programming is because i want to make wanted to make games and uh you know of course making games is really really hard there's a lot to it and you know often it's done by teams of people. Back in the day, when the games were on Atari and there was 4-bit graphics, one guy would make a whole game. But nowadays, most games are made by teams of hundreds of people. However, there's still a community of people who are just single developers or small teams making games

and and one of the more popular communities is called the roguelike community so a roguelike is is essentially it's a game derived from rogue which is a ASCII game made I think in the 70s but the idea is it's ASCII art so you're a little at sign and uh you move around on the screen and the screen's made up of your little period signs for the floors and for the floor tiles and a little like the little pipe symbol and the minus sign for the walls and things like that and so you know the graphics are simple the gameplay is often quite simple uh sorry sorry the uh mechanic the mechanics and the visualization the gui is simple but the gameplay can become very complex and so people can

and it's typically really hard yeah there's often really hard or just you know the games are incredibly complex like dwarf fortress is is one of the more popular roguelikes and you actually you know you manage a civilization and this guy implemented an economy that kicks in. You have a king, and you have to have these nobles that have to be managed. There's an entire water system, which the creator of Minecraft kind of lifted, and so now you can find it in Minecraft. But at the time, Dwarf Fortress was the only game that had that kind of fluid dynamic system. It had the 3D, it has a 3D environment where you can destroy any of the blocks, kind of like Minecraft.

So Dwarf Fortress is and continues to be an inspiration for many other games. And Tarn Adams, the creator of Dwarf Fortress, received a ton of notoriety. And I know of several roguelike developers who got job offers from game companies just because of their involvement in roguelikes. So for people who want to make video games, this is a great way to get into it, is to make a roguelike. And for people who want to do that, there is this website, which is How to Write a roguelike in 15 steps at one point it was a while ago but i don't even remember when but at some point i went through this these 15 steps and made a roguelike and yeah and it's it's really rewarding because

at the end you have a finished product and you've also learned a ton um you've learned about when do i create new classes versus when do i make things data driven so for example when i started i had a sword class and then i had a flaming sword class and an ice sword class like they're all dot cpp files uh and i had all this code and no data and i realized you know i don't need all this code all i need is And I realized, you know, I don't need all this code. All I need is just a weapon class, and then I can have a little string which tells me if it's a sword or an axe or whatever. So, I mean, that was a valuable lesson as a programmer is how to make the code data-driven. And, you know, I could go on and on about all the things that I learned

from these 15 steps, but it's really useful. And for anyone, any kids out there who want to start making their own video games, it's a great way to start. Yeah, or adults. Yeah, now you're encouraging me that I feel like I should go do this in addition to sitting on my exercise ball all day.

Yeah, maybe you make a roguelike where the character's on an exercise ball. Or he's in an exercise ball, like a giant hamster ball. Oh, yeah. Like maybe if you go forward. Like, if you go to the left too many times, the momentum of the ball keeps moving forward. That could be tough. So, to tie in the steps, it takes you 15 steps to make a roguelike.

But I can have you become a good programmer in just six. Wow, six. They must be pretty tough steps. So the title of this article is actually become a good programmer in six really hard steps. And it's kind of funny because the author of the article actually says that the six steps should take about 10 years or more. Oh, I'm sorry. Actually, I think the first five steps take 10 years and then step six begins at the 10th year and can take possibly forever and it's a little tongue-in-cheek but it's kind of good to go through and it really does in the same line that you're talking about you know learning to program games and teaching you

programming because of that this guy just kind of goes through the phases that people tend to go through and therefore if you're trying to go through it or wanting to go through it, understanding what it's going to take to get there and what it involves and kind of how you grow and what kinds first game or doing something that inspires you to want to get into programming to becoming a you know software developer at a company as your job that's a pretty similar path amongst a lot of people they have small variations but it tends to be almost the same for many people and so this guy's defined that pretty well and given some guidance and some help for people who are on that path yeah yeah i read it uh and uh you know i thought it was i thought it was like you said very tongue-in-cheek but is uh a lot of it is really true i mean some of it like writing your own programming language creating your own language

really kind of puts things in perspective i mean i feel like i agree that kind of everyone should do that at some point just make some simple language that um you know all it does is let's say it you can uh pass it some new operations like you make a you know plus plus so one plus plus two is is is something else like i don't know maybe it adds two twice i don't know, maybe it adds two twice. I don't know. It doesn't have to be useful, but just the experience of going through and writing a parser and an Alexa and then actually writing the interpreter and things like that is extremely useful.

Definitely, definitely. So, yeah, part of becoming a good programmer is being able to sort of work magic. Take things that were meant to be in one environment and bring them to a completely different environment. And Google Native Client kind of does this, where it can take programs that were meant to be on your desktop and bring them to the web. Actually put them inside of a browser. And it's quite amazing how it works. But this news article kind of talks about one specific application where this guy has taken DOSBox, which is a DOS emulator, and ported it to Google Native Client. So what

you end up with is if you're using a recent enough version of Chrome, you can actually have a DOS operating system in your browser. And he uses this to actually let you play DOS games in the browser. So he's created this MS-DOS file system on his server, I guess. And you can load up different games. So he's got Falcon 3.0 and TIE Fighter and X-Wing. Yeah, he's got all these awesome old school DOS games. And you just literally just go to the website, as long as you're using Chrome, and it's right there. And you just start playing.

It's pretty amazing. And it really kind of showcases the power of Google Native Client. I want to do this right now since i'm in chrome yeah it's totally awesome i played a little bit of tie fighter uh you know to be to be to not get in trouble or anything like that he only has the demo i don't even know how he got his hands on the demo of tie fighter um he must have just had it from way back but um so you only can play the first level but it's still pretty amazing and i think you know as part of the port i mean you should be able to just run anything you want like i don't

know the details but it's a complete dos operating system so if you have your own tie fighter you should be able to bring it to the table i think but either way it's really freaking cool. It sounds awesome. And yeah, you guys should check it out. Is it that time? I think it's time for Tool of the Bi-Week. All right. What do you got? Let me guess. Hang on.

Is it related to what we just talked about? It's no. It's actually Google Native Client. What a twist. Yeah. So my Tool of the Bi-Week actually Google Native Client. What a twist. Yeah, so my tool of the bye week is Google Native Client. I've been messing around with this. And some of you might know I do a lot of work on MAME. I'm the creator of MAME Hub, which is, well, for people who don't know, MAME is an acronym, and it stands for Multiple Arcade Machine Emulator. But now it's grown to cover almost every arcade machine ever made

and many modern consoles, or not modern, many retro consoles, like NES, SNES, and all that. So this is sort of like the one emulator to rule them all. I've been doing a lot of development on MAME, and I'm the creator of MAME Hub, which lets you play MAME games online. So you could play Super Mario Bros. online with someone in England. You legally own it. That's right, as long as you legally own the cartridge in your house.

And if you want, if you're in the Bay Area, you can borrow one from me. I think I still have all my Nintendo games somewhere. Anyway, so I've been using Native Client for, you know, I've been porting MAME to it and things like that. I've been really into it, and it's just, you know, creating some sample apps, and then I can really see there's tremendous potential in this tool chain. It's just amazing.

I mean, imagine you take something that you wrote, maybe in high school or in college, or maybe it's an open source app that you really like. And, you know, as long as you can get it to compile in using this native client, it runs in the browser. I mean, it's a website. And so you can, you know, make changes and, you know, anyone who visits your website automatically gets the latest version. You don't have to worry about deployment or anything like that anymore. It lets you do awesome stuff like immediately get people signed in. It has a JavaScript wrapper around your code. So you can do cool things like make AJAX requests to some web server.

And so you could do all the cool web things like, you know, tap into different web services like the weather and things like that. And tie all that into your desktop application really easily. So it's awesome. It's getting more and more popular. Like I mentioned in the news section, there's some really cool demos. And, yeah, I'm a big fan. So I like to see what kind of cool stuff people make with it. Very cool.

Patrick, what's your tool of the bye week? My tool of the bye week is Handbrake, which is an open-source transcoding application. It's available for Mac, Windows, and I think Linux as well. But the big one is originally it was for the Mac OS, and then they've come out with versions for the Linux as well. But the big one is originally it was for the Mac OS and then they've come out with versions for the others as well. And what this allows you to do is it's really easy for putting videos that you have permission to on your transcoding them

so that they will play on your iPhone, iPad, Android device. Oh, interesting. So you can take a DVD, like you can take your wedding DVD or something and port it to your phone? Yeah, yeah. So if you had a DVD of your wedding and you wanted to watch that on your tablet, then you would use this to convert it because the tablets and phones, although they will often play different videos, like many different kinds of videos,

they're typically optimized for a certain resolution, you know, the screen size, and then also for a certain set of encoding parameters because of the fact that, you know, they have hardware acceleration to do, for instance, H.264 decoding. So if you put it in that format format it's going to perform a lot better or maybe not perform at all if it's not right and what the nice thing about handbrake is is that it has all of those presets in there so you can just say i want this file encoded as for an ipod touch 3g or third gen and so it'll do that or an iPhone 4 and it'll know I did or I want it for an iPad and it'll go ahead and and choose the right width or height

then ratio for you and also what encoding parameters to use what bit rates to use those things that whenever you open up a video encoding thing and go I don't even know what to choose here can I please get some like auto button it kind of has for you and so you can just say what device you want to encode for and it'll just kind of uh already have the presets in there oh that's really awesome that is a fantastic tool i've never seen this tool before oh no i'm definitely gonna use it yeah and it has it supports a wide range of inputs um so it's pretty nice it's just one of those things where it almost always works, and that's nice.

It's nice to have a tool where it's not like you've got to have 15 different things to be able to do one task. Yeah, and you know, this really sort of sets a precedent now that you've used an open source tool as your tool of the bye week. Yeah, this is the first time in a while I've been doing closed source tools for the last uh few episodes and uh yeah i'm back on the try to do open source not just free we haven't done any paid tools yet though so yeah i don't think so i think i think you're right we've never done a paid tool that's because there's no paid tools that are any good i won't say that you may say that sir i won't say that there are certain people who want to charge for their applications often have very good reasons for doing so and they are more than entitled to try that fair enough so okay enough philosophy time for the

discussion of our programming language of the week lisp that. That's right. Lisp is the language we're going to be talking about. It's really interesting. It's definitely, if you're into computer science and sort of the understanding, like, the history and sort of the more, I guess, the less hands-on, the more kind of pie-in-the-sky theory and things like that, this is a good language to know. It was actually invented

before it was implemented so someone and do we have the person's name let me see john mccarthy uh back in 1958 so this was a very old language he um he kind of formalized this idea of lisp and sort of the the core functions um that constitute the Lisp language and sort of prove that Lisp is Turing complete and things like that before there was even an implementation. I mean this was just all done in paper. It was a thought experiment, right? It wasn't until much later, actually, I guess a few years later, that Steve Russell created the first Lisp implementation. So, yeah, so Lisp has a wide history. Because Lisp is so tied to computer science, there's just tons of different dialects of Lisp.

You know, there's scheme and things like that it seems to be probably the how do you say it's like the most well-known least used programming language like people use it but not every day like people don't use in their everyday jobs but it seems like everybody who goes through computer science learns it or even people who are just interested in computer programming will pick it up and they'll at least play with it. If not learn to be experts in it, you know, at least know it, but then not use it. Yeah, that's right. Yeah. And I think, you know, part of the problems with Lisp and we'll talk about this more in the weaknesses, but is that it's just it's so fragmented right i mean this isn't really a problem with lisp as much as just the just i guess the social sort of just the events that transpired but lisp is so fragmented there's many different compilers for lisp or interpreters i should say and uh you know there's

so many different dialects and for a long time none of the interpreters were open source so um you know each one sort of had its own nuances and and so this is i feel like this is really kind of plagued lisp but um the two things that are sort of critical to lisp are um car and cooter so car and cdr and the way this works is uh think of everything in Lisp as being a pair. And the pair is actually called cons, C-O-N-S. So you have a pair of objects, but the objects themselves, they could be anything. And to go from a pair to the specific elements in the pair, like the first and the second, you would call car to get at the first, or you'd call cooter to get at the second. And so just with cons, char,

and cooter, that forms the basis for the entire Lisp language. A lot of it's based on lambda calculus, which gets into some pretty heavy stuff. Basically, lambda calculus is sort of a formalism. We talked about first-order predicate calculus. We're talking about Prolog and this is just another way of sort of representing numbers and the computations on those numbers and you can read about it more Wikipedia but but understand that similar to Prolog Lisp is sort of based on

on calculus. And so because of that, you can imagine it's not something you're going to write device drivers for, right? So this is something that's kind of very theoretical. However, there have been Lisp machines. Have you heard anything about this? Yeah. Well, it was a little bit before my time, I guess, although maybe I was still quite

young when some of it was going on. But the Lisp machines was kind of an effort when the personal computers were first coming out to have a machine that was for individual users, which although didn't directly implement Lisp, so there weren't assembly level commands that said, you know, the parts of the lisp language directly what it did was provide a really simple stack-based processor as opposed to a register-based processor which is gets pretty in-depth and probably outside the scope for this discussion but instead of register-based it was stack-based and the commands themselves were meant to be very easily derived by LISP code. So LISP code would translate into very few instructions, as opposed to on a normal register-based CPU, for instance. A single LISP command may take many, many machine instructions to implement and so these this processor architecture was put together in something called a list machine that was

meant to be easily programmed and efficient at writing and using and running lisp programs right so I mean you know I think about the difference between say C and lisp so in C C, just from a data perspective, in C you're dealing with arrays and pointers that point to different spots of memory. And so you do pointer arithmetic. So, for example, if you have an array and you want to loop through the array, you would have a pointer at the beginning of the array and then you sort of increment it's very numerical you just say I want to push my pointer a little bit further and read the data over here and then push it further kind of like you'd read off a tape or a record or something like that

in lisp you don't have arrays what you have are as I mentioned these pairs yeah so you have pairs so if you want to have say a list if you want to have an array let's say in lisp then what you would have is you'd have a pair the left the first element in the pair would have some item in your list let's say it's a list of numbers so the first element in your pair would have the number say four and the second element of your pair would have a pair in it and then that pair the first element would have a number let's say two and the second element would have another pair

so you see everything is done in pairs and any of the out the two elements in the pair can be either an atom which is you know a number or a word or you word or something that's immutable, something that can't change, like a constant. Or it's either a constant or it's another pair or it's nil. Those are the only three things that can exist. So as we mentioned in JavaScript where there was only four things, in JavaScript there's nil, array, object, and literal. In Lisp, there's only atom, which is the same as literal, pair, and nil. There's only three. So you would think that because it's so simple that, oh, you must be really low level.

You must use this for drivers because it's such a simple language. But actually making the language very simple is really what gives it the power and gives it the ability to represent incredibly complex things. And we'll talk about this a little more when we get to the strengths. But understand that, you know, a machine, a regular machine that just has a bank of memory where you can just do malloc and get arrays, that kind of machine doesn't run Lisp very efficiently, especially 30 years ago, 40 years ago. So the idea of the Lisp machine was let's make a machine

with the constraints of Lisp in mind. Let's make a machine that deals with things in terms of pairs. Right. And I mean, it seems like they were fairly successful at doing that. It was just of lisp in mind let's make a machine that deals with things in terms of pairs right and i i i mean it seems like they were fairly successful at doing that it was just that the competition in the market was somewhere else it was in the traditional register based machines running c and yeah so it seems like there have been many of these instances in the even short-lived software world where even if something made sense or was technically superior, something else won out because of just market inertia or happenstance or various other things. And the Lisp machine kind of fits in that category.

Yeah, I'd like to think that being an AI person and being sympathetic to Lisp, I like to think that it's sort of the grandfather of many other languages. Other languages like Python, JavaScript, which is based on... JavaScript was based on Scheme, right? It was inspired by Scheme.

Yeah, and Scheme is a dialect of lisp so there you go and and you know even matlab which is now very popular uh you know you know lisp is sort of the grandfather of all interpreted languages and is is a good source of sort of inspiration for for languages that came after and offered you know much uh more uh boosts and productivity, you know, without all the hindrances that Lisp has. Yeah. Yeah. So, yes, as we mentioned, it has many dialects. But one of the reasons why there's so many dialects is because it's really easy to write

an interpreter or a compiler for Lisp. In fact, as we mentioned with the, you know, become a good programmer in six really hard steps, the author even mentions that, hey, you should write a Lisp interpreter as your language, you know, because it's a good start. Yeah, there's so few things you actually, well, I mean, it seems tricky. At the start, it seems so easy to get started because there's so few things you have to implement.

Yeah, and keep in mind that, and this is true for all languages. I don't know if we've mentioned this before, but most languages are written in themselves. So we have talked about this where, you know, we talked about Python being batteries included where there's a huge corpus of of tools that you have that are available to you when you start programming the vast majority of those tools are written in python this is true even of you know c and lisp and other languages just to a lesser extent so you know 99 of lisp is written in lisp. And, you know, if you could take, like, the common Lisp libraries and, you know, use your own interpreter, you could really have your own Lisp, like, fully featured interpreter in a day. I mean, of course, it wouldn't be fast.

It would be nothing like C Lisp. But, you know, it still would be fun. You know, it's a toy to play with. And it seems like the other thing is that there are a lot of people who take Lisp and use it as kind of an intermediate language where you write something in Lisp and then you compile it. We talked about people doing this to JavaScript before,

but people kind of use Lisp as an input language to the compiler, I guess, and then compile it to some other form of a language so um there's closure which is c l o j u r e as opposed to we talked a little bit about the closure kit tools uh last week or last episode um and that is uh implementing lisp on top of java so using the java virtual machine and using lisp as kind of i guess what is at the front end to it and saying yeah nice how do we how do we do that and it's it's got a lot of popularity um and there's also the everybody kind of has their own little

ways about some of the finer nuances of the language. And so each of those tends to kind of get its own spin out dialect, which initially starts out really close to the one it started from, but then slowly drifts away over time. Yep. Yeah, so some of the strengths of Lisp. One of the strengths is that it has very, very efficient hash tables. And this is tied directly to the fact that there's so few data types. You know, it does a lot of sort of like clever tricks with the pairs.

And it can actually store a ton of data in a hash table very efficiently by sort of reusing the same data. Lisp is amazing at this. We should explain what a hash table is. Oh, yeah. You've probably never done that. So, yeah. So, a hash table is something that essentially maps one data type to another. One value?

Yeah, I guess one value. Maybe that's a better way of saying it. Essentially maps one value to another. So, for example, let's say you wanted to store the days of the week. So if you put in zero, you got Monday. If you put in one, you got Tuesday, right? So in C, you could just have an array. And at the array index zero, you would just hold the string,

a pointer to the string Monday. And one, you'd hold Tuesday, so on and so forth. And you'd say, you know, days, open bracket, you know, two to get Wednesday, right? What if you wanted to go backwards? Like what if someone gave you the string and you wanted to return what day of the week it was in numbers So if someone gave you Monday you wanted to return zero So in this case you'd have to use you'd have to use essentially a map and the map would have to map strings to numbers See an array you can think of an array as a map which maps numbers to something else whatever is in the array

But whenever you need a map Something that isn't the number let's say you need a map You know a floating point number or as I mentioned a string or maybe you need a map a chess board like the entire board like a whole class with the pieces and where they are. You need to map that to a number. To do something like that, you have to use a map. And one very common map, implementation of a map, is a hash table. What a hash table does is it takes, it basically is based on the principle that you don't actually need the key so in other words I don't actually need to store the string Monday

in this table you know what what I need is when I get the string Monday I need to know to return zero but it doesn't necessarily mean that I need to hold Monday in the table so that sounds a little confusing, but take, for example, let's say that your hash table, instead of storing the whole string, it just stored the first two letters. So that would be sufficient, right? If someone passed in Monday, then I would just take the first two letters, MO, and just look for that in the table.

And that would return zero. And I've saved some data. I didn't have to store all of Monday. Now, you know, I couldn't use one letter because if I did, then Tuesday and Thursday would both map to the same location. That's called a collision. Right.

And so there's ways to deal with that even. So it's not the end of the world. But, you know, I could store two letters and save a lot of data. And so hash tables, you know, there's a lot to it. You know, if you're really good at hash tables, hash tables are sort of the backbone of just about everything in computer science, especially distributed processing or, you know, web and stuff like that. So it would take a whole show, but in a nutshell, Lisp and the way Lisp works, the objects in Lisp are very hash friendly. And on top of that, Lisp can do a lot of object reuse.

So it can implement hash tables very efficiently, very quickly. It can implement them without using a lot of memory. And this is really important for the applications, which we'll talk about later. So do you have any other strengths for LISP? So one thing that, well, I guess this is one of those, it could be a strength and could be a weakness, is that you can use LISPs to parse itself. So the difference between data and instructions in a C++, Java, Python program is very clear.

It's very much here's my code and here's the data I'm storing. I'm assigning this data to this variable. And only in a few kind of edge cases where you might talk about function pointers or you know some kind of obscure things where your variable stores a pointer to code or code somewhere but that isn't the usual case it doesn't normally happen but in list you can have your your program is represented as one as these pairs so you can this there's very easy to intermix both the data and the program and that

means that you can manipulate the program so that's known as self-modification so when the code as it's running changes the code that's running and in lisp this is easy to do because the like i said there's no real distinction between data and the program and yeah that's a strength that gives you there's some really powerful techniques that you can do and that make really efficient code um it also happens to be something that can be very hard to understand um but it it's one of those with great power comes great responsibility. If you use it wisely, it can be very powerful. And if you use it poorly, it can cause problems.

But Lisp is really good at doing that. Look at the roguelike, for example. So let's say you're making a simple roguelike game following the 15 steps and uh you know you make a sword uh and uh you have this sword class and you have some data like you have the great sword where the name is great and um it does like 10 damage and then you have like the awesome sword so you have some text file and the text file just has, you know, great sword, comma, 10, awesome sword, comma, 20, you know, light sword, comma, 30. And so, like, then you write some C program that looks at your text file and then says, okay, create, you know, create a great sword, create an awesome sword, and then put these in somewhere in memory so that I can fill my world full of great and awesome swords but

what if i wanted a flaming sword and when you hit somebody with it um they caught on fire and there was all this code and stuff like that well you know that can't really go in the text file you know i mean you can't describe the flames yeah you can't describe the flames and the effect and the person catching on fire and what that means all that logic you can't just the flames. Yeah, you can't describe the flames and the effect and the person catching on fire and what that means, all that logic. You can't just put that in the text file. I mean, you'd have to put it in the C file and then know that, oh, a flaming sword has this, right? But with Lisp, your data and your code is the same thing. So in Lisp, you'd have in lisp you would have you know a pair and the pair the first element would

be the name and the second element would be a pair which would have the you know damage and then you know the third element there could be an entire list program which is what happens when you hit someone with the sword and you don't have to worry about reading your data from the text file like you do in C and, like, you know, creating sort objects based on the data in the text file. You just load that Lisp file and it's done. So, yeah, you could do some awesome stuff with it. But, yeah, I mean, it makes it very difficult to debug and things like that. So, yeah. It's kind of a wild thing that you have at your fingertips.

So with all of the, these things are nice features. Everything's a pair. And the language provides some abstraction. So I guess we should say that even though everything under the hood is a pair, the languages allow you to not have to literally, if you want to make a list, have a pair where the second element is another pair and the second element is another pair.

They give you the power to just make one long list and do that pairing for you. Yeah, that's a good point. So yeah, I was just thinking about that because one of the weaknesses though, even with that that, Lisp tends to have a ton of parentheses and parentheses are what are used to kind of wrap each pair. Yeah. I mean, it's, you know, they've done a lot to make it less painful. So as Patrick mentioned, if you have 10 items, you can just put a single parentheses around them and lisp under

the hood knows that it's like a bunch of pairs that are all chained together but the fact is yeah i mean there's just you're dealing with pairs and and uh as you might imagine there's as a lot of there's a lot of data a lot of variables you might have in your code, you're going to have a ton of parentheses. That's kind of endemic of Lisp programs. So fortunately, if you use Emacs, it'll match up. Or actually, I guess most modern, or not even modern, most editors will do this for you. But it'll help you match up the parentheses. But yeah, it still can make things

a little cumbersome yeah it's not really a weakness but it is something when people look at lisp code some languages you don't exactly know at first like c++ and java sometimes you have to kind of look at certain lines of code to kind of understand what it is when you look at lisp code it's really easy to tell because you just look for all the parentheses. Yeah, I mean, think about this. As we mentioned, again, everything's a pair. So if you want to add two numbers, what you really want, you want a pair of a plus sign and a pair of a 2 and a 3 underneath it. So you have now with C Lisp and more advanced Lisp,

you can take away the parentheses around the 2 and the 3. But you're going to have a parentheses and away the parentheses around the 2 and the 3. But you're going to have a parentheses and then the plus sign and then 2 and 3. That's another thing about Lisp is that everything is in prefix notation. So if you want to do 2 plus 3, you actually want to do plus 2, 3. And so because it's in prefix, let's say you wanted to do 2 plus 3 minus 4. It would actually be plus minus 2, 3, 4. So now that doesn't make any sense, right?

Because the order of operations, you don't really know. Prefix notation doesn't really give you order of operations. So to deal with all that that you specify the order explicitly. So to do 2 plus 3 minus 4 you'd actually do open parentheses open parentheses minus sign or yeah minus sign open parentheses plus sign 2 3 close parentheses 4 close parentheses. So just to do something that simple you already needed four parentheses like two opening and two closing. So it can get pretty cumbersome. But one of the other, you know, weaknesses of Lisp beyond just the syntax is that it doesn't have direct memory access and doesn't really have much in the way of hardware access. So people have written extensions, but for the most part, it's not really designed to fit the model of a computer. And this is one of the things that

really hurt Lisp. And that's what inspired people to make the Lisp machines that they did 20, 30 years ago. Yeah. And that's really fundamental, being able to manipulate specific memory locations, because that's, you know, for people who have never done it before, it may not be obvious, but that's how at the lowest level all the drivers work. So the things that control hardware all come down to basically putting certain values at certain memory locations. And doing that causes something to happen electrically on that peripheral device and that's how device drivers are written and so if you don't have the ability to control exactly what the contents of a certain memory location are then you're not going to be able to control that device and you can't write device drivers and that's what a lot of low-level code is working with those kinds of things yeah i mean's what a lot of low-level code is working with, those kinds of things.

Yeah, I mean, you know, a lot of people are probably too young. A lot of people listening to the show are too young to have serial mouse. But when I started learning about computers, I had a serial mouse. And what that was was the plug for the mouse had, how much does a serial port have? Like eight pins, I think? Nine. Or 16? Nine. Nine pins? Yeah. Really, nine Like 8 pins, I think? Or 9 pins?

Really? 9? Or a mouse? Or just a regular serial port? No, this isn't a PS2. This is like an old serial mouse. I think it was even before my time. But then that was 9 pins. Okay. So just think of that.

It has 9 pins and it naturally fits an array. You know, if you want the eighth pin, then you call array index seven, right? So, I mean, the way that computers are architected and built, you know, the way memory is laid out, all of these things sort of fit the linear, you know, C model. And, you know, back when it was really important, when speed was really important before computers got as fast as they were, and when, you know, storage is really important for hard drives got as cheap as they are now. The languages like C just completely dominated. And only now are people starting to leverage more like productivity focused languages like Python. But Lisp was

really sort of only, you know, useful to academics at the time when it was most popular. So you already kind of mentioned that Lisp is used a lot in the artificial intelligence community. What kinds of things do you guys use it for yeah so um so this was very was used a lot in planning and so let me explain a little bit of what planning is planning is basically uh searching through like a particular space and figuring out sort of what are the optimal actions to take so for example uh path planning is you know let's say you have again let's say you're making a roguelike game and you have this grid world uh you know sort of like a where the whole world is just a grid of numbers you're at coordinate x you're at you're at you know coordinate three comma five and you take a step to the left now

you're at coordinate four comma five it's very discreet right and so you know, coordinate 3, 5, and then you take a step to the left. Now you're at coordinate 4, 5. It's very discreet, right? And so, you know, you want to navigate through some maze in this grid world. What you want to do is to plan. You want to sort of try all the possible moves you can make and then see where you are. Are you closer to the goal? Are you further away from the goal? Like what's the state of the world after after these different actions i could take so again going back to list strengths right

let's you can create a hash table where the key is the entire world um the state of the world as it is so so in this grid world the key might be just your position and the value would be you know how close you are to the goal or maybe even just you want the hash table to store as a key the state of the world and as a value whether you've seen this state or not so if i take a step to the left that's a new state so i'll put that in the hash table and then let's say i try take a step to the left, that's a new state. So I'll put that in the hash table. And then let's say I try taking a step to the right. Well, that puts me in the same state I started at. So I go to my hash table.

I say, hey, here's some new world I discovered. This is the world where I'm at coordinate 4, 5. And the hash table says, no, you've already been here before. Like, don't bother trying to go further like you've already tried all the actions when you're at four comma five and so doing this will keep you from just going left right left right left right you know so eventually you'll explore all of the possible game states um all the possible world states until you get to the state where you're at the goal um now to take it to the next level,

the hash table could not only say whether you've been at that state before, but it could say how you got there. So, you know, once you get to the goal, you can say, okay, this state of the world that I visited or that I'm at now, how did I get here? Check the hash table. The hash table will say, oh, you got here

by making a move to the right so you could do the opposite backtrack right make a move to the left and say this state of the world how did I get here it could say oh you got here by moving down so on and so forth so this is planning and to do effective planning you need good heuristics which that's just simple algebra so you can do heuristics in any language. But you need an awesome hash table, and Lisp definitely gives you that. So it's very useful for planning. Expert systems is also good at this.

This is kind of a buzzword. Expert systems is basically planning, but instead of planning over something very discreet like as we mentioned planning through a grid world or something like that in the case of expert systems you're planning over rules so this is similar to prologue actually this is almost exactly prologue but at a lower level yeah so you know in the case of prologue it's this really high level abstract language where you're specifying these rules in the case of lisp sort of you would be creating the prologue interpreter essentially in lisp but you could also do other low level things like you

could have rules that were mathematically based you do things like that. And so a mathematically based rule system which parsed natural language, it basically tokenized the languages, the natural, tokenized the text into syllables. And then based on the syllables, tried to get an understanding for the language, like where the noun is in the sentence, where the verb is. There's a system that did this called SHRDLU, S-H-R-D-L-U, and it really made Lisp famous. So what this guy did, he was able to scan an entire encyclopedia, and then for each sentence he was able to figure out where the noun,

the verb, the object of the preposition, all the different parts of speech for that sentence. And then he created a hash table for each sentence where the key was the, I believe the key was the verb and the value was the noun, something like that. But basically, because he scanned the entire encyclopedia, you could ask it questions like, how many toes or how many legs does a zebra have? And it actually could tell you answers in English. So you would literally type in how many legs does a zebra have? And it would answer you a zebra has four legs in English. And this, this blew people's mind, right? When this program came out, people thought, okay, you you know we're going to get a human robot in the next five years now this program came out like in the 60s right uh or maybe not that late maybe like the

70s but i mean you know it shocked like it rocked the ai community and uh and it was done by lisp and it really made lisp uh very popular at the time another thing that people use list for and you you talked about a little before but uh emacs yeah you mentioned that it'll help you do the parentheses matching which a lot of editors will do but emacs um uses a version of lisp as a way to do its extending the emacs editor so the emacs is one of the uh i don't even want to say anything because it'll just start a flame war but uh emacs is one of the editors that is popular on the linux platform and i'll say it is a emacs is the best editor um for the linux platform and also all right the only thing that might be better is xemax i'm not going to say anything because i i want to not have my email inbox completely filled with

people writing in about this yeah i have a feeling the guy who sits at the stand-up desk will be kicking my ass tomorrow oh and he has a very strong leg because he's been standing on it all day he's standing the whole time well no he'll rest on the chair first the leaning chair yeah for a few minutes that's right and then he'll and then he'll rest on the chair first, the leaning chair for a few minutes. That's right. And then he'll kick me down. So Emacs allows you the option to add functionality and increase its abilities by writing in a form of Lisp in one of the Lisp dialects. Right.

And that's a very popular use of the Lisp language. Yeah, definitely. Also, I guess it's the what's the ita stand for is like international traffic it stands for but google now owns them but they were kind of yeah like the big back-end infrastructure servers for they're like all of the major internet travel websites like orbit traveloc, that went and queried a system for tickets, information, flight paths, times, on-time percentages, those kinds of things, these people, like, tracked all of that data. They were, like, the people who all these websites used to get that information from.

And all of their software was written in Lisp. Yeah, that's right. So I think, you know, they've probably been around for a long time. Yes. And they, you know, probably when they were around, other languages like Python and things like that probably weren't that popular or maybe even didn't exist. And so they were, you know, had the foresight to jump on a productivity based you know productivity focused language like lists and so it's carried them all the way to today so definitely lists have been using in enterprise solutions another more academic

application of lists that was very popular again at the time was maxima which is a computer algebra system so you know algebra really is a planning problem you know especially at a higher level like you think about it you you have an equation let's say you have uh like let's say a simple equation like you have uh you know four divided by two plus three and you just want to know the answer to that so you know that's that. So you have to do planning. In this case, you only have one thing you can do, which is a division because of order of operations. So you divide the 4 by the 2.

That's your one action. Now you're into a new state where you have 2 plus 3. Then you take another action where you combine those and you get 5. But as you get to more advanced things, especially like integrals where there's many different rules you can use or derivatives or you get to differential equations where there's 10 if not 15 or 20 different ways you can solve a particular ODE, particular differential equation. So this thing does planning and says all right again let's here's the state of the world it's this differential equation let's put it in a hash table and then let's start trying different rules different ODE different

differential equation solvers and it can it can sort of try these rules, and by enacting these rules on the equation, it creates a new equation. And that's a new entry in the hash table. And the hope is eventually it can reduce some really complex differential equation into something much simpler. Or it can reduce some integral using some trig identity into something much simpler. So Maxima used planning to solve many computer algebra problems. All right, well, I think that wraps it up. Yeah, so yeah, the uses were pretty cool. The Maxima computer algebra system, the ITA software, Emacs, AI,

this has been used for some pretty awesome things. And it's also very interesting to learn so uh definitely take a look at it and uh stay tuned yeah i've said that before said this before but uh lisp is one of those languages where learning it even if you don't use it in your day-to-day job or don't ever become super amazingly proficient at it uh it's one of those things that'll help you become a better programmer. Yeah, definitely. So, you know, if a couple of people have been adding us on Google+, that's awesome. Definitely add us.

We actually invited anyone I knew from my programming throwdown circle, we invited to the Hangout. So definitely, you know, can take some of your questions and your feedback directly when we do the shows and things like that, which would be awesome. So... Try that out, see how that goes.

Yeah, yeah. But shoot us an email. So add my name on plus is jgmath2000 at gmail.com. And I think you're P. Wheeler, right? Patrick LW. Oh, sorry. Patrick LW at gmail.com is Patrick.

Shoot us an email before you add us to your circles so that we know that you're in Programming Throwdown and we know that you're not some spam bot or something like that although you know spam really has been brought to quite a minimum on g plus i haven't seen too much of it but yeah just in case shoot us an email let us know uh you know give us some love yeah for all of you who have added me i know some people have and i haven't added you back i'm working out a system i'm trying to keep my stream with people that like I'm really trying to pay attention to and I still haven't figured out how to add people and then not you know have

them flood out my normal stream but I have been looking at what you write on my incoming stream so don't feel like uh that I'm just I'm being mean to you yeah definitely I'm gonna keep uh inviting anyone in my programming throwdown circle to the hangout before you record um so if you have any feedback you want to add or if you have any questions or if you have a language we'll do a we'll do an impromptu language i'll throw down the gauntlet right now and say that if someone has the right timing to jump into our hangout while we're recording the podcast we will do whatever language they want well i will i will make it that if they are willing to come on the podcast if we don't know anything about it and and do at least part of this spiel of it yeah that's

true we we need somehow if someone comes in and says oh i want you to do Motorola assembly at buy, you know, I mean, then we can't, we're kind of stuck. Right. Um, or I want you to do M 68 K you know, Donkey Kong assembly or something, but, but, um, you know, yeah, you definitely have to be willing to help out, help us out. Cause we're going to be floundering a little bit, but I will throw down the gauntlet now and say, we'll do any language someone wants. If they jump in the hang us. Jason might be doing it by himself. But yeah, shoot us an email, let us know so that we know who you are. And yes, that would be awesome. And definitely check out the blog, programmingthrowdown.blogspot.com. And our email address is programmingthrowdown at gmail.com. Yeah, that's right. So I guess until two weeks from now, have a good one, stay safe, and learn you some Lisp for great good.

All right, take care. See you. The intro music is Axo by Binar Pilot. Programming Throwdown is distributed under a Creative Commons Attribution Sharealike 2.0 license. You're free to share, copy, distribute, transmit the work, to remix, adapt the work, but you must provide attribution to Patrick and I and sharealike in kind.