Instructions
Objective
Write a Racket assignment program that allows users to to Interpret expressions in BSL format.
Requirements and Specification
It should be with "BSL" with an amateur language. We run the Programming on Dr. Racket with the beginner setting.
Use functions like "(check-expect...)" I am also adding the script for the programming language. I added the translated ones and the original one. "Important: This time, the homework will only be processed on paper. Give your solution to your tutor at the beginning of your next tutorial, or send your tutor a digitised version (photo / scan) via the forum.
Source Code
Aufgabe 1: Grammatiken und Ableitungsbäume
--------------------------------------------------------------------------------
1)
Example 1:
(+ (* 3 4) (- 9 2))
Derivation tree:
(+
(*
3
4
)
(-
9
2
)
)
Example 2:
(/ (* (+ 1 2) (- 4 3)) 2)
(/
(*
(+
1
2
)
(-
4
3
)
)
2
)
2)
Example 1:
(+ (- 2 3) (* 4 "a"))
This expression doesn't conform to the grammar since the
second expression in "(* )" must be either
another expression or a and "a" is neither.
Example 2:
(- (+ (/ 24 2) (* 4 1)) (- 8))
This expression doesn't conform to the grammar since the expression
that starts with "(-" must be followed by two expressions and (- 8)
has only one: the 8.
Aufgabe 2: Struktur von Ausdrücken
--------------------------------------------------------------------------------
1)
a) x
Is syntactically correct from the derivation tree:
x
b) (= (= y z) 0)
Is syntactically correct from the derivation tree:
(
=
(
=
y
z
)
0
)
2)
a) (3 + 4)
Is not syntactically correct because the first symbol in a
expression with parentheses must be one of: , and, or, cond, if, but 3 is a .
b) number?(1)
Is not syntactically correct. The text doesn't start with
parenthesis so it must be an , but it's not a ,
, , or ![]()
so it could only be
a , however a must not contain parentheses so the
text is not syntactically correct.
3)
a) (define (f x) x) Is syntactically correct from the derivation tree:
(
define
(
f
x
)
x
)
b) (define (f x y z) y)
Is syntactically correct from the derivation tree:
(
define
(
f
x
y
z
)
y
)
4)
a) (define (f "x") "x")
Is not syntactically correct since the second symbol inside the
parentheses in a define must be a +, that is one or more
symbols, however "x" is a which can't be
derived from .
b) (define (f) 10)
Is not syntactically correct since the parentheses after define
must have an initial and after that there must be one or
more and (f) has only the initial .
5)
a) (+ 1 (not x))
Using the derivation tree we get:
(
+
1
(
not
x
)
)
So the text is syntactically correct.
b) ("x")
Using the derivation tree we get:
(
"x" <- this is not a name
It's not syntactically correct since "x" is not a .
Aufgabe 3: Bedeutung von Ausdrücken
--------------------------------------------------------------------------------
(* 1 (- 11 4) (+ 190 1))
Since the first expression is a value 1, we use the next position
for the hole. Thus, we start with the evaluation context:
e = (* 1 (- 11 4) (+ 190 1))
E = (* 1 [] (+ 190 1))
e_1 = (- 11 4)
e_1 reduces as:
(- 11 4) -> 7
with (KONG) we get:
E[e_1] -> E[7]
so
e -> (* 1 7 (+ 190 1))
Now 1 and 7 are values so we use next position for the hole.
Thus the new evaluation context is:
e = (* 1 7 (+ 190 1))
E = (* 1 7 [])
e_1 = (+ 190 1)
e_1 reduces as:
(+ 190 1) -> 191
with (KONG) we get:
E[e_1] -> E[191]
so
e -> (* 1 7 191)
Since the expression has only values after the name, it can be evaluated:
(* 1 7 191) -> 1337
Aufgabe 4: Bedeutung von Programmen mit algebraischen Datentypen
--------------------------------------------------------------------------------
Start in (PROG) with env = empty
The first element of the program is a structure definition so it's added to env:
env = (define-struct order (item quantity))
Tne next element is a function definition so it's added to the env:
env = (define-struct order (item quantity))
(define (item-price item)
(cond
([string=? "sugar" item] 1)
([string=? "milk" item] 2)))
Tne next element is a function definition so it's added to the env:
env = (define-struct order (item quantity))
(define (item-price item)
(cond
([string=? "sugar" item] 1)
([string=? "milk" item] 2)))
(define (order-price order)
(* (item-price (order-item order))
(order-quantity order)))
The next element is a constant definition, according to (PROG) we need to
evaluate first (make-order "milk" 2):
e = (make-order "milk" 2), the expression has only values so it can be evaluated:
e -> according to (STRUCT-make)
The env is now:
env = (define-struct order (item quantity))
(define (item-price item)
(cond
([string=? "sugar" item] 1)
([string=? "milk" item] 2)))
(define (order-price order)
(* (item-price (order-item order))
(order-quantity order)))
(define MILK-ORDER )
The next program element is an expression so we evaluate it according to (PROG)
using the current environment:
e = (order-price MILK-ORDER) breaks down to:
E = (order-price []) and
e_1 = MILK-ORDER.
According to (CONST) it follows that
MILK-ORDER ->
and following (KONG) we get:
e -> (order-price )
Following (FUN) we get:
(order-price ) ->
(* (item-price (order-item )) (order-quantity ))
Breaking down the expression:
e = (* (item-price (order-item )) (order-quantity ))
E = (* [] (order-quantity ))
and e_1 = (item-price (order-item ))
Using again the evaluation context with e_1 we get:
e = (item-price (order-item ))
E = (item-price [])
and e_1 = (order-item )
Following (STRUCT-select) we get:
e_1 -> "milk"
Then using (KONG) we get
e -> (item-price "milk")
Using (FUN) we get:
(item-price "milk") -> (cond ([string=? "sugar" "milk"] 1) ([string=? "milk" "milk"] 2))
Using the eval context:
e = (cond ([string=? "sugar" "milk"] 1) ([string=? "milk" "milk"] 2))
E = (cond ([] 1) ([string=? "milk" "milk"] 2))
with
e_1 = (string=? "sugar" "milk")
Using (PRIM) we get e_1 -> #false
Using (KONG) we get
e -> (cond (#false 1) ([string=? "milk" "milk"] 2))
Using (COND-False) we get
(cond (#false 1) ([string=? "milk" "milk"] 2)) -> (cond ([string=? "milk" "milk"] 2))
Using the eval context:
e = (cond ([string=? "milk" "milk"] 2))
E = (cond ([] 2))
e_1 -> (string=? "milk" "milk")
Using (PRIM) we get e_1 -> #true
Using (KONG) we get
e -> (cond (#true 2))
Using (COND-True) we get
(cond (#true 2)) -> 2
Using (PRIM)
(item-price "milk") -> 2
Using (KONG) we get
e -> (* 2 (order-quantity ))
Evaluating the expression again using the evaluation context:
e = (* 2 (order-quantity ))
E = (* 2 [])
and e_1 = (order-quantity )
Following (STRUCT-select) we get:
e_1 -> 2
Using (KONG) we get:
e -> (* 2 2)
Using (PRIM) we get:
(* 2 2) -> 4
Using (PRIM) we get
(order-price ) -> 4
The environment at the end is:
env = (define-struct order (item quantity))
(define (item-price item)
(cond
([string=? "sugar" item] 1)
([string=? "milk" item] 2)))
(define (order-price order)
(* (item-price (order-item order))
(order-quantity order)))
(define MILK-ORDER )
Aufgabe 5: Bedeutung von Datendefinitionen
--------------------------------------------------------------------------------
1)
"yes"
"no"
2)
(make-pair "yes" "yes")
(make-pair "yes" "no")
(make-pair "no" "yes")
(make-pair "no" "no")
3)
"yes"
"No"
#false
4)
(make-pair "yes" "yes")
(make-pair "yes" "no")
(make-pair "yes" #false)
(make-pair "no" "yes")
(make-pair "no" "no")
(make-pair "no" #false)
(make-pair #false "yes")
(make-pair #false "no")
(make-pair #false #false)
5)
(make-pair "yes" "yes")
(make-pair "yes" "no")
(make-pair "no" "yes")
(make-pair "no" "no")
#false