Optional: Tokenization, Parenthesization, and Scope
Programming Languages, Part B
Universidade de Washington
4.9 (498 classificações) | 13K alunos inscritos
[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language "fits together" to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module of Part A. Part B assumes successful completion of Part A. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
Habilidades que você aprenderá
Racket (Programming Language), Programming Language Concepts, Type System, Functional Programming
DO THIS COURSE. It brings together everything in part A. In particular, the final shorter week on the differences between Statically and dynamically typed languages is mind-bending and brilliant.
I took this course about 10 years off the college, and it was excellent refresher on the topics I don't use on a daily basis. Absolutely great lecturer, great videos and study materials!
Section 5 and Homework 4 (First Module with Racket)
Let's get started programming with Racket and then learning idioms related to delaying evaluation. The welcome message has a few additional comments about picking up a new language and how to approach the homework assignment, so let's get started...
Introduction to Racket8:23
Racket Definitions, Functions, Conditionals10:14
Racket Lists9:07
Syntax and Parentheses8:36
Parentheses Matter! (Debugging Practice)10:50
Dynamic Typing9:36
Cond8:52
Local Bindings13:11
Toplevel Bindings4:54
Mutation with set!8:28
The Truth About Cons7:46
mcons For Mutable Pairs7:38
Delayed Evaluation and Thunks10:12
Avoiding Unnecessary Computations6:48
Delay and Force9:18
Using Streams10:10
Defining Streams10:49
Memoization10:17
Macros: The Key Points8:52
Optional: Tokenization, Parenthesization, and Scope7:30
Optional: Racket Macros With define-syntax9:25
Optional: Variables, Macros, and Hygiene10:52
Optional: More Macro Examples9:12
Dan Grossman
Selecionar um idiomaInglês
[MUSIC]. This segment is not yet going to get into the details of how we can define our own macros in Racket because first I want to discuss three issues that come up in any macro system and discuss how macro systems in general and Racket in particular deal with them. I'll refer to these as how you break things into tokens, how you deal with parentheses, and how you deal with local variables and scope issues when you're interacting with macros. And we can just describe these one at a time. So the first question for a macro system is how does is it look for uses of the macro, how does it know what is a use of the macro that needs be expanded and what doesn't? And pretty much all macro systems take enough programming language details into account to work at the level of tokens instead of the level of characters. So tokens is just a programming language's word that just means words instead of letters. So a variable's a token, a keyword is a token, some arithmetic operator is a token. We're not looking at the individual letters. So an example will probably make this clear. Suppose you're programming in Racket and you really don't like car, so it seems like a bizarre word to use for accessing the first element of a list. Well, if that's how you feel I would recommend you define a helper function that would have a different name and have the same meaning or semantics as car. But suppose instead you did it with a macro. You define some macro that said, anywhere I write head, H-E-A-D, I mean car. And macro expansion will turn what I write as head back into car. Okay, that should work. And what macro systems do not do is take something like the variable headt and turn it into the variable cart. We don't want to turn headt into cart. That's not what we mean by replace head with car. And so we have to understand enough about our programming language to understand that we should not do this. Now you might think this is obvious or trivial, but you do need to know a few things about your language. So, in Racket, we also would not take a variable head-door, and replace it with car-door, all right? Because it's the same reason. But in C, the macro system for C would look at head-door and would understand that that's not a variable. That in C, or in Java or anything else, is a subtraction. It's the head variable minus the door variable. And just because we don't have spaces doesn't mean those are not three separate tokens, three separate words. And the macro system has to understand where one token ends and the next token begins. So, we'll assume that macro systems can do that. Now, the second question is, how does associativity work? What parentheses are implicit or not? So here I really get to pick on C/C++, if you've never seen them, don't worry about it. But in those languages you can define a macro like you see here at the top. Like that's ADD, so that's the name of my macro and says wherever you see ADD parenthesis something comma something else, replace it with x+y. And it turns out that if you do that in C or C++, if you call the macro here with two arguments 1 and 2/3. And you take the result of that macro and multiply it by 4. You would almost, when you read the code, I think you would agree with me that what you kind of see is this thing on the right. Then we take 1, we add to it 2/3 and then we multiply it by 4. And that is not what you get in C/C++'s macro system, you get the thing in the middle. It literally replaces the ADD macro, expands to 1 + 2 / 3, and then because the next token after that is a *, when we run this code, it ends up doing this thing on the right and then adding 1 to it. Which is very hard to see based on the code pre-macro expansion. This is why when you see macros in C and C++ you tend to see them defined like this, with lots and lots of parentheses, lots of extra ones, just to make sure this sort of thing doesn't happen. And that's what you need to do in a language with that kind of bizarre macro system. Racket doesn't have this problem. In Racket wherever we use a macro, it will always be right after a left parenthesis, so it's like its own special form. And so after expansion it's in that same position. And if the thing we have expand to has parentheses and we are parentheses, otherwise it's just going to be something like a number or a variable. And there's no issues of the parentheses getting shifted around on us. So, that's the good thing. And the third thing we need to deal with, with our macro system, is how it interacts with potential variables that might shadow a macro definition. This is something that doesn't work well in C and C++ and most macro systems. But the Racket macrosystem understands this issue, comes up with a more reasonable semantics. And that's one of the reasons why I like showing the Racket module system. So let's go back to our example of, we want to be able to write head and so we defined a macro where we're going to replace every use of head with car. So that macro has been defined somewhere, but maybe there's some code that doesn't know about it, or doesn't care about it. And just defines some local variables that happen to be named head and car. So I have this first let expression where I say let head be 0, car be 1, and return head. Of course, I would expect a more complicated expression in the let body that would use both head and car, but this is a nice short example and we know that this would evaluate to 0. And it would evaluate to the same thing if we use let* because let and let* are the same if you don't use any of the same variables over again and don't use any of them in the expressions in the bindings before you get to the body. Now, if we naively just replace very token head with car, then we were to replace both the variable uses and the variable definitions. So under the expansion down here, you just see I've replaced all four heads with cars and now all sorts of weird things happen. The let is now an error so we would do the macro expansion and then we will get an error because when we evaluate evaluated this code because you are not allowed to declare the same variable twice in the same let expression. In let* you are, it's shadowing like ML's let bindings but now we get a different answer. Because we replaced the head and the body with car but that's now going to refer to this shadowed car, this inner one and we're going to get 1 instead of 0. And so our macros are interfering with code that might not even know that the macro exists and the great news is this does not happen in Racket. Racket has a more sophisticated semantics for macro expansion. They get scope to work out correctly, and in Racket, head here, the local variable, would simply shadow the macro. So the macro would not apply in here and there would be no expansion, we would get 0 which is what you expect since this code is trying to use a local variable and it's not trying to use a macro. So hopefully that gives you a sense that macro expansion is not trivial. It has some rather subtle issues. It has to be defined carefully. And now we can move on and use Racket's module system, sorry, macro system, to define some of our own macros.