10 Lab The Mystery Languages of Variables

Note While we did not run this lab—replacing it with Lab Modeling Event Loops instead—we keep it with these notes for readers who wish to study different flavors of imperative languages.

One syntax may have many semantics. We will give you three mystery languages that have the same syntax but different semantics, and your task will be to find programs that tell them apart.

This lab’s mystery languages are called Variables1, Variables2, and Variables3. Run them with #lang RacketSchool/Variables1, etc. For your convenience, #lang RacketSchool/VariablesAll will run programs in all three languages. Here is the syntax for these languages:

(define-language basic-syntax

(p ::= (prog f ... e))

(f ::= (defun (x x) e))

(e ::=

; booleans

b

(if e e e)

; numbers

n

(zero? e)

(+ e e)

; strings

s

(empty? e)

(++ e e)

; functions & let

(function x)

(e e)

x

(let ((x e)) e))

(x ::= variable-not-otherwise-mentioned)

(b ::= true false)

(n ::= number)

(s ::= string)

(v ::= b n s (function x))

#:binding-forms

(let ((x e_1)) e_2 #:refers-to x))

(define-extended-language var-syntax basic-lang

(f ::= ....

(defvar x v))

(e ::= ....

(set! x e)

(begin e ...)))

Exercises

Exercise 20. Explore the differences between Variables1, Variables2, and Variables3. Explain their behaviors, and find programs that support your explanation. These mystery languages differ in how they treat variables and function calls, so focus on that when trying to tell them apart.

Exercise 21. Your task is to develop Redex models for these languages.

Begin with this basic Redex language. Extend it with the syntax to handle variables. Then add reduction rules to realize the behavior of Variables1.

Next, extend the basic language again to realize the behavior of Variables2.

Finally, if you have time, try Variables3.

Exercise 22. Now we will flip the process. Instead of asking you to analyze a language by writing programs, we would like you to study a model and predict differences to existing languages.

SPOILER ALERT: Do not click on link until you have finished the above two exercises.

Here is a Redex semantics that extends the basic language. Without running any programs, how does it differ from Variables1? What programs would you run to exhibit the differences?