6 Lab The Mystery Languages of Records

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.

The three languages are called Records1, Records2, and Records3. Once you have installed them, you can run them in DrRacket with #lang RacketSchool/Records1, etc. For your convenience, #lang RacketSchool/RecordsAll 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 record-syntax basic-lang

(e ::= ....

(record (s e) ...)

(@ e e))

(v ::= ....

(record (s v) ...)))

Exercises

Exercise 12. Explore the differences between Records1, Records2, and Records3. Explain their behaviors, and find programs that support your explanation. These mystery languages differ in how they treat records, so focus on that when trying to tell them apart.

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

Begin with this basic Redex language, and extend it with the syntax above to handle records, with the behavior of Records1. Instead of producing ’stuck, however, your language can just get stuck. For example, (prog (+ 1)) should evaluate to (prog (+ 1)), rather than to ’stuck.

Next, extend the basic language again to instead behave like Records2.

Finally, if you have time, try to model Records3.

Exercise 14. 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 are two Redex semantics that extends the basic language. Without running any programs, how do they differ from Records1? What programs would you run to exhibit the differences?