Lecture: Programming Language

Dear students:

Welcome to CS 430: Programming Languages. I have two primary computing interests: computer graphics and programming languages. They don't necessarily go together, but I like them both and I try to find ways to unite them so I can think about both of them.

I'm Chris, and you can call me Chris. Or Dr. Chris. Or Dr. Johnson. I'm still kind of new to this department and this part of the country. My family fled the Midwest because of the cold and other reasons that we can talk about some time. When I say family, I'm referring to my wife and four sons. I'll show you a picture so you know that you aren't the only thing I've got going on in my life.

Course Structure

My aim is for our weekly schedule to be predictable. On Tuesdays, we'll have lecture. I will talk. I will try to get you to talk. We'll write a fair bit of code together. On Thursdays we'll have a lab. Some labs will be on paper, some on a computer.

The textbook for our is course is one that I am working on. I have chosen to write it not because I think I can do it better than others. I have other reasons: so that I myself can better understand the material, so that I can give it to you for free, so that I can distill the book down to the material that we'll actually cover, so that I can integrate exercises directly into the reasons, and so that I can improve the writing and the exercises semester after semester. The book is a work-in-progress, and I welcome your constructive criticism and error reports.

Each week will look something like this: read → front quiz → lecture → middle quiz → lab. Readings will generally be assigned on Thursdays. You will take a front quiz that accompanies the reading, all before Tuesday's lecture. If you like your score, you can keep it. If not, you can take a middle quiz and replace it. You don't have as much time for that one; it's due before Thursday. Then on Thursday you'll work on a lab exercise in teams. These labs will generally be due by Monday noon. I will grade them almost immediately and move on with my life. I will not accept late labs. Please don't contribute to the unsustainability of my profession. Your late work hurts you, me, and the other people I am here to serve. The quizzes aren't timed because I want to eliminate panic where I can.

We'll be discussing three languages throughout the semester: Ruby, Haskell, and Rust. They are chosen for their differences from what what you are used to. For each of them, we will have a programming exam.

I don't technically take attendance because you are adults. However, if you don't attend, our whole mission seems sort of pointless. We're here to talk to each other about programming languages—together. So, while I'm not going to waste my time on attendance itself, I am going to assign in-class exercises each time we meet, both Tuesdays and Thursdays. These will be short and related to the course topics. Your participation will count toward your grade. If you complete the exercise correctly, you'll get four points.

We'll try one of these exercises on this first day using a semi-functional tool named Prompt that I built a couple of years ago. In the first round, you do not talk but think quietly to yourself. Once all have answered, you'll briefly confer with your neighbors. Then you'll answer again.

For programming assignments, we will have a single project with four milestones. You will build a coding challenge application that runs in the terminal. A challenge is presented to the user as a black box. They enter parameters and examine the return value. When they've formed a hypothesis, then reverse engineer the box by writing code in a language that you design. We'll talk more about this next week.

I push due dates right up to the point at which I'm going to start grading. There won't be extensions. I have a job that does not end and easily destroys relationships and physical and mental health. If you find that you don't have enough time to complete something, please just accept the very natural consequence of not receiving credit.

The four project milestones will not have exact due dates. Instead I have scheduled six ready dates. These are dates at which you may turn in your work for a milestone. I don't give out unit tests because testing your code is your responsibility. You aren't trying to satisfy some external machine. You are try to satisfy your own integrity for a job well done. To demonstrate that you are meeting the requirements, you record a video of you discussing your work and running it.

We live in a day where it's very easy to feign competency by generating code with AI. If you graduate from JMU with a degree in CS but can't develop software or reason about computation, you hurt yourself and everyone else associated with the department. So, new this semester are code reviews. I will watch your videos. If you appear to meet the requirements, I'll also give you 3 of the 7 points for the milestone. I'll also invite you to schedule a code review to take place within the week. We'll talk through your code, and I'll ask you questions and point out revisions that you'll need to make. Your job is to demonstrate that the code is yours. Once you make those revisions, you'll get the remaining 4 points. If you don't attend the review or make the revisions, then you roll over to the next ready date.

These ready dates are my scheme for accommodating emergencies, illness, breakups, breakdowns, and other trying times. I do not otherwise grant extensions because I'm a finite being.

You will turn in all your work on GitHub using a repository that I have made for you. I need to get you access to that repository. Also, we will use Discord for all communication. Please do not use email. If you send me an email, I will passive-aggressively wait one day before responding, and then my response will be, “Please ask on Discord.” Email is terrible because I cannot easily revisit the history of our conversation and because the university floods us with noise. Emoji is also easier on Discord.

Let's take a moment right now to make sure I have your GitHub and Discord usernames. Find the link on Canvas and submit these to me. Make accounts if you need to.

Language to Language

In this class, we approach our subject from two directions: we implement a programming language and we study several different mainstream languages. In implementing a language, we'll see how humans make choices about the programming experience. You may develop some empathy for the folks who wrote those error messages. In studying several languages, we'll see how many different choices there are and how our options can't be ranked in a simple manner from right to wrong. Each option has tradeoffs. Making some computation easy, fast, or safe generally makes something other computation hard, slow, or dangerous.

Today we begin work on both of these fronts. We're going to start implementing an interpreter for a fraction arithmetic language so we can compute values like \(\frac{1}{4} + \frac{5}{6}\) and keep the results as fractions. What should we call this language?

The computer doesn't know this language. Our job as language designers is to translate the language it doesn't know into a language it does know. For now, our target language is Ruby, the first language we will discuss. The computer does know Ruby because someone taught it how to translate Ruby into machine code.

What we talk about today is meant to mirror some of what you will need to do for milestone 1 in the project. You should take copious notes. Translating a program is a bit of work, and we'll spend several lectures talking about it.

Abstract Syntax Tree

Language tools first translate a program from an unknown language into a tree in a known language. Specifically an abstract syntax tree (AST). We'll draw a tree for this fraction program:

1/4 + 5/6

1/4 + 5/6

An AST is syntactic in the sense that represents the structure of the original program—before anything has been evaluated. It is abstract in the sense that not every single syntactic detail is represented. For instance, an AST likely doesn't have nodes for whitespace, semi-colons, or parentheses.

A tree is made of nodes. In an object-oriented language, each node is an instance of a class in a hierarchy of program anatomy. From this tree, I see the following node types:

• Fraction
• Add

These classes form the model of the translated program. We will implement them in Ruby. Here's how we might implement Fraction:

class Fraction
  def initialize(top, bottom)
    @top = top
    @bottom = bottom
  end
end

f = Fraction.new(1, 4)

class Fraction
  def initialize(top, bottom)
    @top = top
    @bottom = bottom
  end
end

f = Fraction.new(1, 4)

This program makes a node. Let's try printing it:

puts node

puts node

The output is not helpful. If we call inspect on the node, we'll get a debugging form of the object:

puts node.inspect

puts node.inspect

In fact, we might want to write a function that printed a debugging view of an object automatically. But this function has already been written. It's called p. The puts statement above is written in this shorthand:

p node

p node

Suppose we want to print just the top value. We might write this:

puts f.top

puts f.top

The Ruby interpreter gives an error about top being an undefined method. Why a method? Because Ruby doesn't allow direct access to instance variables. It thinks we are trying to call a method named top, but it doesn't exist. We could write it:

class Fraction
  # ...

  def top
    @top
  end
end

class Fraction
  # ...

  def top
    @top
  end
end

But writing getters like this is a waste of time and space. It's also common in Java. Ruby offers a shortcut with attr_reader:

class Fraction
  attr_reader :top, :bottom

  # ...
end

class Fraction
  attr_reader :top, :bottom

  # ...
end

The nodes of our tree can be categorized in several different ways. Nodes that aren't built out of other nodes are primitives. Nodes that yield a value consumed by other nodes are expressions. Primitives are expressions, but so are the arithmetic operations. Nodes that don't yield a value but do achieve some effect—like printing or assigning memory—are statements. Thinking about these terms will help us implement the rest of our model classes.

Let's write an Add class. It is not primitive, as it accepts two nodes as parameters:

class Add
  def initialize(left, right)
    @left = left
    @right = right
  end
end

class Add
  def initialize(left, right)
    @left = left
    @right = right
  end
end

Now we can represent more sophisticated fraction programs, like this one:

f = Fraction.new(1, 4)
g = Fraction.new(5, 6)
sum = Add.new(f, g)

f = Fraction.new(1, 4)
g = Fraction.new(5, 6)
sum = Add.new(f, g)

Okay, so we have a way to represent a program from an unknown language as a tree in a known language. That's great, but I'm feeling disappointed in two ways. First, making the tree by hand is tedious. We'll fix that next week. Second, trees represent programs, but we can't yet run the tree. We'll fix that next class.

In the time we have left, let's just grow our language. We can add some of the following node types:

• Subtract
• Multiply
• Divide
• Print
• Assignment
• Block

The first three look a lot like Add. Maybe we could capitalize on that similarity somehow?

Print, Assignment, and Block are statement nodes. They have side effects rather produce values. Print has a child node for its parameter. Assignment has an identifier and a node for its right-hand side. Block has an array of child nodes.

Note on AI

Let's take a quick moment to discuss AI. It has some benefits: it can eliminate drudgery, it can give you ideas, it has entered the lexicon of modern society, and it is disrupting a world that probably needed disrupting. Knowing something about it is like knowing about Minecraft and Beyoncé. You can participate in more conversations. However, it also has costs. Not just the environmental ones, but also the opportunity ones. You are in school to develop yourself, not produce right answers. The activities in this class are designed for you to learn, and it's very easy to lose that opportunity by using AI in the wrong way. I think AI can help you learn if you use it in the following manner:

• Disable ghost text—the suggestions that appear automatically. In Visual Studio Code, click on the Copilot icon in the status bar and uncheck Inline Suggestions.
• Hamstring it by not giving assignment details. Ask “How do I add getters in Ruby?” Don't say “I need a Fraction class.”
• Reject code that you don't understand.

There's a lot of pressure from industry to use AI. That doesn't mean it wants to hire fresh graduates who got through a CS degree by having AI doing their work.

The exams we complete in this course will be completed in-class through the LockDown browser. In the past I allowed folks to use any browser and IDE but not AI. They used AI anyway, and they ruined it for everyone else.

TODO

Here's your list of things to do before we meet next:

See you next time, when we start looking at how to represent a program written in a language we don't know in a language that we do know.

P.S. It's time for a haiku!