Meeting 01 - Welcome

Author

Bor-Yuh Evan Chang

\(\newcommand{\TirName}[1]{\text{#1}} \newcommand{\inferrule}[3][]{ \let\and\qquad \begin{array}{@{}l@{}} \TirName{#1} \\ \displaystyle \frac{#2}{#3} \end{array} } \newcommand{\infer}[3][]{\inferrule[#1]{#2}{#3}} \)

Principles of Programming Languages - CSCI 3155 - Fall 2024

Professor Bor-Yuh Evan Chang

In-Class Slides

Today

Bootstrapping
Introductions
Course Approach
Discuss Your Goals and Worries
Getting Your Money’s Worth
Syllabus Policies

Bootstrapping

A puzzle …

Suppose you want to run lots of JavaScript programs — all the cool kids are doing it, but unfortunately you have a computer that can only execute x86 assembly. So you decide to write a compiler from JavaScript to x86 assembly.

Furthermore, suppose that you think Scala is the best language for writing a compiler; you find the language has particularly effective constructs for implementing compilers. Unfortunately, your computer only has a C to x86 compiler. Having taken 3155, you know that you can write an awesome compiler in Scala that produces efficient x86 code, but you’re not so sure you can write an efficient compiler in C. What do you do?

Let’s back up!

Open an editor and write plusOne program.

function plusOne(n) {
  return n + 1;
}

Say, “Run!”, but nothing happens!

Back up. What is program?

A program is something that takes input data and produces output data.

program: Data → Data

How do you use a program?

You run it passing it input data.

How do you run a program?

(Possible Answer) You compile it.

What is compilation?

A program you use to produce assembly code.

compiler: Program[JS] → Program[x86]

compiler(plusOne)

Say, “Hey output program, run!” Nothing happens.

“Ah, we need an interpreter!”

What is an interpreter?

A program that runs other programs.

interpreter: Program × Data[Input] → Data[Output]

interpreter(plusOne, 3) -->* 4

interpreter: Program × Int → Int

But my compiler is a program, and I need to run it. How do that?

Uh oh …

I need an interpreter for the compiler. What’s the data for a compiler? A program!

interpreter(compiler, program) -->* program'

Program = Data!

But I forgot something. If the interpreter is a program, then how do I run it? I need run the interpreter on the interpreter.

interpreter(interpreter, (program, data)) -->* data'

Oh, but to run the interpreter, I need the interpret the interpreter-interpreter.

interpreter(interpreter, (interpreter, (program, data))) -->* data'

Uh oh …

Let’s Restart with Some PL Terminology

Idea: Bootstrapping

Key Terms: A meta language versus an object language.

Credit: Adapted from Olivier Danvy. Thanks!

Some Terminology

A programming language is

A program is

A programming language is a notation to express computations.

A program is something written according to this notation. It can be executed (i.e., interpreted) to carry out a computation. A computation is some kind of processing operation over some data. Data are representations of information.

An Analogy: Cooking

A cooking recipe is a notation that conveys how to cook something. It specifies data (the ingredients, e.g., eggs, butter, salt, pepper, thyme), resources and tools (e.g., a stove and a pan), and an algorithm (a method to operate on the data, e.g., to beat the eggs towards cooking an omelet). To make a dish, a cook can then operate over the ingredients according to the recipe.

recipe = program
cook = interpreter

Syntax and Semantics

Syntax is

Semantics is

An analogy with natural languages.

Syntax are what things you can write that are programs in the programming language.

Semantics are what programs mean — how they execute.

An analogy: A natural language (e.g., English) is a collection of words assembled into sentences. Words are composed of letters, and sentences are composed of words and punctuation marks. There is a common agreement about correct English words (spelling) and about correct English sentences (grammar). Spelling and grammar pertain to the syntax of English. Sentences are then communicated, either orally or in writing, from someone to someone else, to convey a meaning. Meaning pertains to the semantics of English.

Meta Language versus Object Language

An analogy with studying natural languages.

The object language is the language of study (e.g., the input and output data of the compiler).

The meta language is the language used to do the studying (e.g., the language the compiler is implemented in).

Let’s consider someone learning English as a second language, say a native Spanish speaker. They use a textbook written in Spanish. They are learning the English language through explanations written in Spanish. In this case, Spanish is the meta-language used to study the object-language English.

Interpreter

An interpreter is a program that executes other programs.

An interpreter is written in a meta language (also called an implementation language) that interprets programs in an object language (also called a source language).

interpreter : Program × Data → Data

An ‘I’ “interpreter” diagram:

 S-L
  |
 I-L

JavaScript
  |
 x86

Compiler

A compiler is a program from one object language (the source language) translating a program in another object language (the target language).

‘T’ “translator” diagram:

S-L ----- T-L
      |
     I-L

Combining

Let’s say I have a JavaScript interpreter in Java and a Java interpreter in x86. How do I get a JavaScript interpreter in x86?

Let’s say I have a JavaScript interpreter in Java and a compiler from Java to x86. How do I get a JavaScript interpreter in x86?

Back to the puzzle …

I can execute x86 assembly:

x86 assembly
    |
   x86

I have a compiler from C to x86 assembly:

C ----- x86 assembly
    |
   x86

Step 0

Write a “quick-and-dirty” compiler from Scala to x86 assembly in C. Compiler 0:

  Scala ----- x86 assembly
          |
          C

Step 1

Using the C compiler, compile “Compiler 0”. The result is “Compiler 1”:

  Scala ----- x86 assembly   Scala ----- x86 assembly
          |                          |
          C   C ----- x86 assembly  x86 assembly
                  |
                 x86

Compiler 1 is still “quick-and-dirty”.

Step 2

Write your awesome Scala compiler in Scala, “Compiler 2”:

  Scala --2-- x86 assembly
          |
        Scala

Step 3

Using “Compiler 1” and the assembly interpreter, compile “Compiler 2” to get “Compiler 3”:

Scala --2-- x86 assembly        Scala --3-- x86 assembly
        |                               |
      Scala  Scala --1-- x86 assembly  x86 assembly
                     |
                  x86 assembly
                     |
                  x86

We have a Scala compiler running on x86 that produces “awesome” code but is itself not fast because it was compiled with the “quick-and-dirty” compiler.

Step 4

Now with “Compiler 3”, compile “Compiler 2” to get “Compiler 4”.

Now you have an efficient Scala to x86 assembly compiler.

What happens if you use “Compiler 4” to compile “Compiler 2”?

Step 5

Now, you can write your JavaScript compiler in Scala with an efficient Scala to x86 compiler.

Meeting 01: Welcome

Principles of Programming Languages - CSCI 3155 - Fall 2024

Professor Bor-Yuh Evan Chang

Announcements

Today’s Homework: Post an introduction of yourself on Piazza
Today’s Reading from Schedule
- Syllabus: Coming next time means you have read and agreed
- PPPL Introduction: Course Approach, Getting Your Money’s Worth

Getting to Know You

“I, …, wonder …”

I’m going to do my best to learn all 150 of your names. Until I can call you by name, could you please help me by telling your name before you speak?

Distraction-Free Classroom

Let’s turn off our cell phones and laptops.

. . .

Just imagine that we have class in Rocky Mountain National Park.

. . .

If you have a need to use a laptop, please discuss with me after class.

I promise 100% of my attention and expect the same from you. In the modern world, that means turning off cell phones and wireless on our laptops.

Who is distracted by you browsing social media or shopping for shoes in class? Studies have shown that it is the person sitting next to you that does worse on exams.

Shopping for shoes doesn’t just distract yourself but the people next to you.

Your Guide this semester

Principles Exist: While everyday programming languages seem complex, underlying principles exist. They take work to uncover and see, but they can be understood. Knowing the underlying principles are there, you should not panic and always seek help from course guides. — PPPL 2.1: Expectations and Finding Success

I am not here to recite shallow facts to you. I am here guide and help you truly learn deep principles.

More Guides

Even More Guides

Introduce yourself to someone you haven’t met before.

Two minutes!

Credit: Boulder New Tech Meetup

Course Approach: Active Classroom

Build interpreters for mini-languages.
2-3 weeks of active discussion — in class and online (Piazza) — towards incrementally completing a lab! Do intermediate assignments along the way.
Recitation sections are lab sessions. Bring a laptop.
Assignments due Friday 6pm. Everyone gets an automatic “stuff happens” 24-hour grace period.
No late assignments but generous “redo” policy and lowest score dropped.

Course Approach: Active Classroom

Learn by Doing: Concepts may look simple when the course guides walk you through them. However, until you … get your hands dirty on code …, you will not own the knowledge. You will make mistakes and get confused along the way, but with hard work and help from your course guides, you will truly master the concepts. — PPPL 2.1: Expectations and Finding Success

Course Approach: Active Classroom

Please interrupt at any time!

It’s completely ok to say, “I don’t understand. Please say it another way. Slow down!”

Attempting assignments and reading before class prompts the discussion. There is an expectation on you to be active.

Learning Oath

I promise to support the learning of my fellow classmates, to not make any question feel unwelcome, to recognize our differing backgrounds to the best of my ability.

About You: Your Goals and Worries

What do you want to get out of this class?
What do you think this course is about?
What worries you about this class?

Ask students to answer these questions on an index card.

What worries you about this class?

Getting Your Money’s Worth

Why study PL?

Why study PL when we have ChatGPT?

Testimonials

Come on Thursday to hear from 3155 alumni!

Luis Olivas (Workday)
Andrew Arnopoulous (Fitbod)

Don’t we have enough PLs?

A Dismal View

. . .

This is not a history course.

This is not a trip to the zoo

This is more like a study of anatomy

Learn new languages

You will need to learn many languages during your careers.

You will learn concepts that make it easier for you to learn new languages in this class.

Improve background for selecting a suitable one for your task

Have you ever had to pick a language?

. . .

What criteria did you use?

. . .

How do you understand “about pages”?

Gain new ways of viewing computation and approaching algorithmic problems

Have you heard of Google MapReduce?

. . .

How about Meta React?

. . .

… inspired by ideas from PL theory

Gain new ways of viewing programs

What does it mean for two programs to “behave the same”?

You will be able to reason about computation.

Being able to compute versus being about to reason about computation is very different (analogy: arithmetic versus algebra).

Gain insight into avoiding mistakes for when (not if!) you design languages

Use AI assistants to accelerate your creative design

Other reasons?

Syllabus Policies

Requirements

Distinguishes between learning activities:

Reading
Quizzes and Exercises (25%)
Lab Assignments (30%)
Participation (5%)

And summative assessments:

In-Class Exams (20%)
Final Exam (20%)

Highlights

Integrity of the Course Materials
Collaboration Policy
Redo Policy
No late assignments but one drop
No make-up exams (unless emergency or special accommodation)
Special accommodation requests (religious observances) within first four weeks
Regrades/redo requests within one week