Racket Functions As “Macros” For Interpreted Language

Loading...

From the course by University of Washington

Programming Languages, Part B

331 ratings

University of Washington

Programming Languages, Part B

331 ratings

[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.

From the lesson

Section 6 and Homework 5 (Second Module with Racket)

Welcome to the second week of Part B where we will focus on (a) building data structures in dynamically typed languages and (b) implementing programming languages with interpreters. Most of the programming assignment is focused on (b) -- implementing a small programming language that has function closures. As usual, start with the welcome message and enjoy!

Datatype-Programming in Racket Without Structs13:21

Datatype-Programming in Racket With Structs9:34

Advantages of Structs8:13

Implementing Programming Languages10:07

What Your Interpreter Can and Cannot Assume13:47

Implementing Variables and Environments6:29

Implementing Closures6:32

Optional: Are Closures Efficient?9:03

Racket Functions As “Macros” For Interpreted Language9:15

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

[MUSIC]

In this segment, I want to cover the last topic we should need for our homework

assignment where we're implementing a made up programming language inside of Racket.

And this is going to tie together our work on an interpreter with our

earlier brief study of Macros.

So here's what we know so far and I need to bring these two pieces together now for

us in this segment.

We are taking the following approach to implementing a programming langauge B

in language A.

All we're doing is we're skipping parsing and any notion of concrete syntax

by writing language B programs directly in terms of language A constructors.

And then our interpreter is simply written in language A by recursively

evaluating sub-expressions in order to get results for larger expressions.

Now, here's what we know about macros.

We learned earlier that a macro extends the syntax of a language.

And what happens is, you define a macro and then when you use a macro,

you expand the macro use using the macro definition before the program is run.

You rewrite the syntax the program in terms of the macro definition and this is

all before the rest of the implementation of the language sees anything.

So what we're going to do now is see how our approach to language implementation

is going to give us a way to write what are essentially macros

just as Racket functions.

So here's how this works, okay?

We are just going to write Racket functions that are going

to take in language B syntax and produce language B syntax.

And if we use those when writing our language B programs,

we will get the output of those Racket functions

put into our program before we call the interpreter.

So we're not going to make any changes to the interpreter,

we're not going to add any struct definitions.

This is just a programming idiom where we can act like

these Racket functions are a part of our programming language.

They're not, they're Racket functions that take in syntax and produce syntax and

then it's that result that then we end up thinking as part of our program.

Which is then fed to the interpreter.

This all happens before we ever call a function like eval-exp.

So, it'll be much easier to see once I show you the code and

everything I have here.

I've shown you before and then we're going to define a new some quote and

quote macros in this language.

So in an earlier segment, I showed you this little language that has constants,

negations, additions, multiplications, booleans true and false.

A test for whether the result of two sub-expressions are the same number and

an if then else.

And I showed you a function eval-exp,

this is the correct version that handles error messages properly.

And it's a big code that has one case for every kind of expression.

There's no environment here because the language doesn't have variables but

that's primarily a separate issue, okay?

So, we know if I just click run here that I could

define a racket variable x that holds a program

in this language, like add of const 3 and const 4.

And if I ask what x is, I see it's just a program.

And if I evaluate it, I pass to my interpreter, x.

And what I get back is const 7.

Now, let's define some Racket helper functions for

writing programs in this language.

And see how they kind of act like macros.

So suppose I wanted an andalso, an and in my language.

So this is a Racket function.

All it is, I'm going to put a function body here, it's plain old Racket function.

Just a Racket function that I'm going to call with two expressions in my language.

And what I'm going to return is if-then-else e1 e2 bool false.

So I take in syntax, I return syntax.

That's what macros do.

And now once I have this defined,

I could write a program like andalso

bool true eq-num const 3 const 4.

Okay, and what I get back is expanded version.

I call this Racket function with some syntax, I get back a program.

So if I held this program in a Racket variable,

y is the macro expanded version.

So when I call eval-exp with y, I pass the interpreter,

things the interpreter understands.

I end up getting back false because indeed I take this first branch

that I have a conditional where it's true, so

I go down here, but then 3 is not equal to 4, so I end up with false, okay?

So that is seeing how these Racket functions act like macros.

Let's do a couple more because they're interesting and

you need to do similar things on your assignment.

Here's another simple one.

Suppose I wanted to act like my function had double.

Okay, well then I could just macro expand in e and

to multiply e and the constant 2, all right?

Let's do one that's a little different because it mixes kind of Racket

constructs and the language we're interpreting a little bit more.

How about I have a macro that takes in a Racket list.

And returns the program in my language that would multiply all

the expressions in that list together.

So maybe es would be a better name for

this function than xs because it's a list of expressions.

All right, so if the list is empty then return the const 1.

I'm not evaluating anything, I'm not multiplying anything, I'm creating

a program that when run, will be the multiplication of everything in this list.

Otherwise I have a non-empty list, so

let's create multiply out of the first thing in that list.

And the syntax I get by calling list-product on the rest of the list.

Let's see a little bigger example of a program that we might write that would use

all of these macros we've defined.

Notice you can use them anywhere,

you don't have to use them at the top of your program.

Here I'm using andalso on, how about doubling 4, okay,

is that equal to the product of the Racket list,

because that's how I defined the list product macro, if you will.

How about const 2 and const 2 and

const 1 and const 2.

And this time I'll and that with just the constant true, okay.

And now if I run this, okay, test is just syntax,

I haven't interpreted anything yet.

And it's kind of big because it expanded everything out.

It's an if then else, because that's the expansion of and also,

eq-num of look the double of const 4 became this multiply of const 4 and

2 and the call to list product became a multiply of a const 2, a const 2, and

that's all nested multiplies all the way down.

And the reason why I didn't just do the multiplication is because first of all

that's not how macros work and

second of all if my language had things like variables.

Or functions, I can't do the multiplication yet,

I could have variables in some of these expressions.

The whole point is to produce syntax that represents the expanded thing so

that we can then evaluate it and get our results.

So again test is just that big piece of syntax and

then I could evaluate test and I would get true.

So that is the role of macros.

That is the sort of thing you will do on your homework assignment.

Let me just finish up with one thing for those who did

the optional material on macros where we looked at hygiene issues.

Earlier I really bragged that Racket's macro system is superior to the macro

systems in most languages, because of the way it handles variable shadowing.

And the way it's okay to use local variables,

even inside of macros in Racket, without things getting messed up.

Now, I've defined a different way to do macros for

this embedded interpreted language.

And this approach is not one of those good ones,

it does not handle variable shadow in the way you would expect.

So, if you want to define one of these macros via Racket functions and

you had a language that had variables in it, you would have to do things

like use strange variable names in your macro definitions and things to avoid

having sort of surprising semantics in the presence of variable shadowing.

Nonetheless, the general idea holds that we can think of a Racket function

that produces syntax for our language as a macro for that language.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play