On this page:

6 Lab The Mystery Languages of Records


analyzing semantic variations of a syntactic language

modeling the semantics

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.

To install the mystery languages, in DrRacket select File/InstallPackage, and enter racket-school-mystery-languages. Alternatively, you can run the following command from the terminal:

raco pkg install racket-school-mystery-languages

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
     (if e e e)
     ; numbers
     (zero? e)
     (+ e e)
     ; strings
     (empty? e)
     (++ e e)
     ; functions & let
     (function x)
     (e e)
     (let ((x e)) e))
  (x ::= variable-not-otherwise-mentioned)
  (b ::= true false)
  (n ::= number)
  (s ::= string)
  (v ::= b n s (function x))
  (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) ...)))

The #langs hide the (prog ...) part of the grammar, though, so your programs can simply have the form f ... e. For example, this program:

(defun (f rec)

  (@ rec "a_field"))

(f (record ("a_field" 1)))

produces the number 1 in all of the languages.


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. image

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. image

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? image