430 Lecture 01-28-16

cs.umd.edu/class/spring2016/cmsc430

Syllabus – Please read
Computing resources, office hours, grades, projects

Schedule
Most important things
Midterms, written down in bold
Two midterms and final exam
Dates are right on front page as well

6 projects
The first one is up now
Due on Tuesday
Very simple
Just do a little bit of research about a programming language

Ways things submitted through the submit server

Primary way communicate announcements is through Piazza. Please sign up for that.

Other things I want to mention
This is my e-mail address
Best way to get in touch with me
Send me email or stop by my office

Name of course called Intro to Compilers. What really about is Programming Design and Implementation. Writing Compiler one aspect of that.

More generally, how do you make a programming language? Might be seems like sort of a weird thing to consider. But if you haven't thought aout it, that's what this course is about.

Why take this course?

One reason. You've probably used a number of programming languages already.

What's it like to use different programming languages.

How they are built, and differences in way they are constructed.

Understanding differences in which way built, let you be a better user of programming languages.

A program that takes in a program. Not a spreadsheet, or a comma list of values. It takes in as its input. The textual description of a program. Skips translation and just does it.

Give it a program and carries out what said for program to do.

An interpreter consumes description of another program and carries out actions of running that program.

One way of understanding programming languages. Write interpreters for them.

Concrete with 330. Write an interpreter for the Scheme programming language in Scheme.

Good reasons for this. One reason why you might do this. Understand what's going on when you run Scheme programs.

Experience. Something describe something on the board, you got it. Mergesort, you got it. Go and write it. And you're like oh crap… how did that go again? Write some code that crashes and finally stumble upon the right thing. At that point you really understand mergesort. If you can convince these idiotic machines what mergesort is, you understand what it is.

Figure out what's really going on when you're running your scheme interpreter.

Bootstrap problem. If you understand recursion, easy to understand recursion.

You can do useful things. And we'll see that. We'll see the purpose of writing a metacircular interpreter. Write an interpreter in the language for the language that you're writing in.

You could write an interpreter for C. You had a job. You worked in a C shop. All of our code has to be C. I hate C. All those array out of bounds errors. Security bugs. Scheme. That's a nice language. All those parentheses. Lambdas. I'm being serious. I love that stuff.

If I'm stuck programming in C, going to have a miserable existence. Too bad for me. Write a scheme interpreter. Program in the world that you want to program in. You're technically still programming in C. C program starts with define a string. At the end call my program. Tell me that's not C programming.

Look at my beautiful C program. What's with all these parentheses? You get fired. Then you can find a Scheme job. Knowing how to write an interpreter. Never stuck in language that's in front of you. All languages in front of you are Turign complete. Next version of Python. “Now with more computable functions”

One of the computable functions that you can write is an interpreter. You can move around through different langauges by writing interpreters.

Low-level programming, C is better than scheme. Memory safety and lack of security bugs, Scheme is probably better. Being able to choose the language that's best suited for the problem in front of you and make it. Make it if it doesn't exist already is good.

Haskell ultimate college student language. It's a lazy language. It doesn't do work until you force it to.

A language is just a set of symbols. Has a grammar. Ocaml is set of all strings you can write down, parsed and fit the grammar of what Ocaml is defined to me. HTML is a language. Is it a programming language? Answer is no. It doesn't really compute. It's just this static markup language. How a document is structured. No real computation going on.

Prolog, Javascript, we can think about their computatonal content.

Fortran model is a different kind of programming language from prolog. Prolog doesn't act at all like Java.

The course goals. At the end of course you should the design and implementation of existing langauges. Design and implement a small programming language. Extend an existing language. Another empowering aspect. Something. When I first started learning CS and learning how to program, it was like. If you were talking about a graph algorithm, I can understand that. If someone showed me code, I can make some changes to this. Javac. That's just magic. I have no chance at understanding that.

Turns out java compiler written all other programs are written. Operates on some tree like data structures. At the end of this course, understand what goes on in a program like that. Submit patches for an open source java compiler, you would be able to do that.

Even though a bunch of new languages coming out. Thought I want to make a new programming language. Next thought should be “No.” This is how really bad programming languages get out there in the world. Javascript is a good example. Javascript was designed and implemented by this guy who went to the university of indiana. I used to make fun of colleagues. Made a scheme interpreter. Working at Netscape. Need some langauge to script webpages in web browser. I know i'll just do it with scheme. Curly braces lot faster than parentheses. Notation that C programmers will lkie and call it Java-something for marketing purposes. In a week, came up with first Javascript implementation. No going back. On every computer and phone. Can't make any changes, so many JS programs in the world. Argubaly the most widely used programming language.

When you think about designing a new language, think about something already out there does what you want. Chances are, there is. Try to start there.

Topics in this course that we're going to cover. Cover lexing and parsing.

Tom said, what interpreter is that takes in text. Text that represents a program. First step have to do turn that text into something that your interpreter can understand. Write an interpreter that operates over strings, you've gone horribly wong. Design better data structures. Tree like data structure. How do I go from strings (structureless text) into data structures I want to operate on? That is lexing and parsing.

That's what it is. Take a big blob of string and turn it into an expression in your language.

Talk about operational semantics. Semantics fancy word figuring out what do programs mean. Operational part what do they mean when we run them. When we execute a program, what happens?

Think about it as a specification for the program that you're going to write which is an interpreter. Most of the programming languages, they don't have operational semantics. It does whatever the PHP compiler says it does. Or the Javascript interpreter.

Some languages have operational semantics. The interpreter is just going to implement the operational semantics.

We'll talk about.

Really, that's like how you build a new programming language. You define semantics. You write a program that implements it. You might call it a day at that point. You might go further and write a compiler for the language.

A compiler just takes in a program and transforms it into some lower level representation that's going to be easier to run.

Coming back to the 330 Scheme example. You could write a Scheme compiler, and transform it into C, and run it through a C interpreter. There's always interpreters underneath you. You bottom out with an interpreter in hardware. That's what's going on at the X86 level.

Next thing going into lower level things. Programs and program states. How to generate code. Type systems. And different kinds of program analysis. How do you discover facts about your program. Looks at forms of that. Data flow analysis. Little low level thing. Allocate registers.

6 projects. Project 0, so 7.

And the project really oriented around building a small compiler for a language. Minimized core version of Ruby, called Rub. Object oriented features. Build a Rub interpreter, then a compiler, implement type systems, etc.

Instituting a rule. That you can't meet me this week or next. I just get a flood of people. Let me get that point. And they're out. At some point, you see something in that class. That's interesting. I thought that was cool. Can you tell me about that. 1%.

Projects 40%
Midterms 35%
Final 24%

No textbook. There are slides that I'm going to be using. That's the lecture notes use as your reference, and take your own notes.

Ocaml turns out to be really. Some languages are better at some things. Really good language for writing compilers in. Hopefully you'll see some of that. I can just tell you some of the features. IT's garbage collected. Dont deal with manual memory management. It's got a type system. A good type system, like C's type system, which isn't a type system. The types help us know that our program is at least not wrong. Doesn't tell you right, but at least not wrong. Gonna help structure think about how we write programs in language. It's a crutch. It helps. When we make changes to our language that need to be propagated through the interpreter. The type system's going to be really useful for that. It's a fast language. Good documentation. Pleasant language. I could go back and pick an unpleasant language for writing compilers, if you want.

Multiple programming languages that we're talking about. Rub, in Ocaml. Call one the object language. Object of our study. Meta-language, language used to implement object language. Ocaml descendant of ML family of languages, Meta-language family of languages. Well-suited for we're about to do.

In Ocaml, there are records which are like tuples, but you specify a type to each part of the tuple. In this example, we have a course record with a title part and a num part.