7 Lab The Mystery Languages of Functions

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 Functions1, Functions2, and Functions3. Run them with #lang RacketSchool/Functions1, etc. For your convenience, #lang RacketSchool/FunctionsAll will run programs in all three languages. Here is the syntax for these languages (it is simply the syntax of the basic language; there are no syntactic extensions):

(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))

Exercises

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

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

Begin as before with the basic Redex language. Modify it as necessary to model the behavior of Functions1.

Next, modify the basic language to instead behave like Functions2.

Finally, if you have time, try Functions3. Hint For this last variant, you must extend the existing syntax so you can express the run-time states. Like evaluation contexts, for example, this extra syntax isn’t part of the surface syntax.

Exercise 17. 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 Functions1? What programs would you run to exhibit the differences?