CS320 Fall 2023 Project 1

Data Structure 数据结构代写, Functional programming 函数式编程代写, Programming Languages 编程语言代写 / OCaml 代写

1 Overview
CS320 Fall2023 Project Part 1
November 2023
Stack-oriented programming languages utilize one or more stack data structures which the programmer manip- ulates to perform computations. The specification below lays out the syntax and semantics of such a language which you will need to implement an evaluator for, taking a program and evaluating it into an OCaml value. You must implement a function:
interp : string -> string list option
Where the input string is some (possibly ill-formed) stack-language program and the result is a list of things “printed” by the program during its evaluation.
浙大学霸代写 加微信 cstutorcs
For part 1, you will need to support the following grammar. The grammar specifies the form of a valid program. Any invalid program, one which is not derivable from the grammar, cannot be given meaning and evaluted. In the case of an invalid program, interp should return None. ⟨prog⟩ is the starting symbol.
2.1 Constants
⟨digit⟩::= 0|1|2|3|4|5|6|7|8|9 ⟨nat⟩ ::= ⟨digit⟩ | ⟨digit⟩⟨nat⟩
⟨int⟩ ::= ⟨nat⟩ | -⟨nat⟩
⟨bool⟩ ::= True | False
⟨const⟩ ::= ⟨int⟩ | ⟨bool⟩ | Unit
2.2 Programs
⟨prog⟩ ::= ⟨coms⟩
⟨com⟩ ::= Push ⟨const⟩ | Pop | Trace | Add|Sub|Mul|Div
| And|Or|Not | Lt|Gt
⟨coms⟩ ::= ε | ⟨com⟩; ⟨coms⟩
Note: ε is the empty symbol. We use ε to refer to empty strings or empty lists depending on context.

3 Operational Semantics
For part 1, you will need to support the following operational semantics. The operational semantics specifies the meaning of a valid program. For the stack-language, a program is evaluated using a stack and it produces a trace. Once we have fully evaluated the program, we return the resulting trace from interp.
3.1 Configuration of Programs
A program configuration is of the following form.
• S: (Stack) stack of intermediate values
• T : (Trace) list of strings logging the program trace • P: (Program) program commands to be interpreted
[ε | ε] Push True;Not;Push 1;Lt;ε (1) [1 :: 2 :: ε | “True” :: “0” :: ε] Push True;Push 9;Pop;ε (2) [0 :: True :: ε | ε] Push 10;Push 9;Add;Trace;ε (3) [True :: False :: 321 :: ε | “123” :: “False” :: ε] Pop;Pop;Trace;Gt;ε (4)
3.2 Program Reduction
The operational semantics of the language is defined in terms of the following single step relation.
[S1 |T1]P1 ⇝[S2 |T2]P2
In one step, program configuration [ S1 | T1 ] P1 evaluates to [ S2 | T2 ] P2. For configurations where P = ε, we say that evaluation has terminated as there is no program left to interpret. In this case, return trace T as the final result of your interp function.
Given any constant c, the command Push c pushes c onto the current stack S. Push never fails. Push
[S|T]Pushc;P ⇝[c::S|T]P
• [1::True::ε|”Unit”::”False”::ε]Push2;ε⇝[2::1::True::ε|”Unit”::”False”::ε]ε • [1::True::ε|”5″::ε]PushTrue;ε⇝[True::1::True::ε|”5″::ε]ε
程序代写 CS代考 加微信: cstutorcs
Given a stack of the form c :: S (constant c is on top of S), the Pop command removes c and leaves the rest of stack S unmodified.
The Pop command has 1 fail state.
1. PopError: The stack is empty (S = ε).
When Pop fails, the string “Panic” is prepended to the trace and the program terminates. PopStack PopError
[c::S|T]Pop;P ⇝[S|T]P [ε|T]Pop;P ⇝[ε|”Panic”::T]ε
• [1::True::ε|”Unit”::”False”::ε]Pop;ε⇝[True::ε|”Unit”::”False”::ε]ε • [ε|”5″::ε]Pop;Push12;ε⇝[ε|”Panic”::”5″::ε]ε
Given a stack of the form c :: S where c is any valid constant, the Trace command removes c from the stack and puts a Unit constant onto the stack. The string representation of c as determined by the toString function to prepended to the trace.
The Trace command has 1 fail state.
1. TraceError: The stack is empty (S = ε).
When Trace fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates. TraceStack TraceError
[c::S|T]Trace;P ⇝[Unit::S|toString(c)::T]P [ε|T]Trace;P ⇝[ε|”Panic”::T]ε
The toString function is a special function which you must define to convert constant values into their string
representations. The following equations illustrate the strings expected for typical inputs.
toString(123) = “123” (1) toString(True) = “True” (2) toString(False) = “False” (3) toString(Unit) = “Unit” (4)
• [1::True::ε|”Unit”::”False”::ε]Trace;ε⇝[Unit::True::ε|”1″::”Unit”::”False”::ε]ε • [ε|”5″::ε]Trace;Push12;ε⇝[ε|”Panic”::”5″::ε]ε

Given a stack of the form i :: j :: S where both i and j are integer values, the Add command removes i and j from the stack and puts their sum (i + j) onto the stack.
The Add command has 3 fail states.
1. AddError1: Either i or j is not an integer.
2. AddError2: The stack is empty (S = ε).
3. AddError3: The stack has only 1 element (S = c :: ε).
When Add fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
i and j are both integers [i::j::S|T]Add;P ⇝[(i+j)::S|T]P
[ε|T]Add;P ⇝[ε|”Panic”::T]ε
i or j is not an integer [i::j::S|T]Add;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Add;P ⇝[ε|”Panic”::T]ε
• [4::5::True::Unit::ε|”False”::ε]Add;ε⇝[9::True::Unit::ε|”False”::ε]ε • [4 :: True :: Unit :: ε | “False” :: ε] Add;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
• [4 :: ε | “False” :: ε] Add;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
Given a stack of the form i :: j :: S where both i and j are integer values, the Sub command removes i and j from the stack and puts their difference (i − j) onto the stack.
The Sub command has 3 fail states.
1. SubError1: Either i or j is not an integer.
2. SubError2: The stack is empty (S = ε).
3. SubError3: The stack has only 1 element (S = c :: ε).
When Sub fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
i and j are both integers [i::j::S|T]Sub;P ⇝[(i−j)::S|T]P
[ε|T]Sub;P ⇝[ε|”Panic”::T]ε
i or j is not an integer [i::j::S|T]Sub;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Sub;P ⇝[ε|”Panic”::T]ε
• [4::5::True::Unit::ε|”False”::ε]Sub;ε⇝[−1::True::Unit::ε|”False”::ε]ε • [4 :: True :: Unit :: ε | “False” :: ε] Sub;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
• [4 :: ε | “False” :: ε] Sub;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε

Given a stack of the form i :: j :: S where both i and j are integer values, the Mul command removes i and j from the stack and puts their product (i × j) onto the stack.
The Mul command has 3 fail states.
• MulError1: Either i or j is not an integer.
• MulError2: The stack is empty (S = ε).
• MulError3: The stack has only 1 element (S = c :: ε).
When Mul fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
i and j are both integers [i::j::S|T]Mul;P ⇝[(i×j)::S|T]P
[ε|T]Mul;P ⇝[ε|”Panic”::T]ε
i or j is not an integer [i::j::S|T]Mul;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Mul;P ⇝[ε|”Panic”::T]ε
• [4::5::True::Unit::ε|”False”::ε]Mul;ε⇝[20::True::Unit::ε|”False”::ε]ε • [4 :: True :: Unit :: ε | “False” :: ε] Mul;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
• [4 :: ε | “False” :: ε] Mul;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε

Given a stack of the form i :: j :: S where both i and j are integer values, the Div command removes i and j from the stack and puts their quotient (i ÷ j) onto the stack.
The Div command has 4 fail states.
1. DivError0: Both i and j are integers and j = 0.
2. DivError1: Either i or j is not an integer.
3. DivError2: The stack is empty (S = ε).
4. DivError3: The stack has only 1 element (S = c :: ε).
When Div fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
i and j are both integers, j ̸= 0 [i::j::S|T]Div;P ⇝[(i÷j)::S|T]P
i or j is not an integer [i::j::S|T]Div;P ⇝[ε|”Panic”::T]ε
i is an integer [i::0::S|T]Div;P ⇝[ε|”Panic”::T]ε
[ε|T]Div;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Div;P ⇝[ε|”Panic”::T]ε
• [16::8::True::Unit::ε|”False”::ε]Div;ε⇝[2::True::Unit::ε|”False”::ε]ε
• [16::0::True::Unit::ε|”False”::ε]Div;PushUnit;ε⇝[ε|”Panic”::”False”::ε]ε • [16 :: True :: Unit :: ε | “False” :: ε] Div;Add;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
• [4 :: ε | “False” :: ε] Div;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε

Given a stack of the form a :: b :: S where both a and b are boolean values, the And command removes a and b from the stack and puts their conjunction (a ∧ b) onto the stack.
The And command has 3 fail states.
1. AndError1: Either a or b is not a boolean.
2. AndError2: The stack is empty (S = ε).
3. AndError3: The stack has only 1 element (S = c :: ε).
When And fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
a and b are both booleans [a::b::S|T]And;P ⇝[(a∧b)::S|T]P
[ε|T]And;P ⇝[ε|”Panic”::T]ε
a or b is not a boolean [a::b::S|T]And;P ⇝[ε|”Panic”::T]ε
[c::ε|T]And;P ⇝[ε|”Panic”::T]ε
• [True::True::Unit::ε|”False”::ε]And;ε⇝[True::Unit::ε|”False”::ε]ε
• [False :: True :: Unit :: ε | “False” :: ε] And;Trace;ε ⇝ [False :: Unit :: ε | “False” :: ε] Trace;ε • [True::4::Unit::ε|”False”::ε]And;Pop;ε⇝[ε|”Panic”::”False”::ε]ε
Given a stack of the form a :: b :: S where both a and b are boolean values, the Or command removes a and b from the stack and puts their disjunction (a ∨ b) onto the stack.
The Or command has 3 fail states.
1. OrError1: Either a or b is not a boolean.
2. OrError2: The stack is empty (S = ε).
3. OrError3: The stack has only 1 element (S = c :: ε).
When Or fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
a and b are both booleans [a::b::S|T]Or;P ⇝[(a∨b)::S|T]P
[ε|T]Or;P ⇝[ε|”Panic”::T]ε
a or b is not a boolean [a::b::S|T]Or;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Or;P ⇝[ε|”Panic”::T]ε
• [True::True::Unit::ε|”False”::ε]Or;ε⇝[True::Unit::ε|”False”::ε]ε
• [False :: True :: Unit :: ε | “False” :: ε] Or;Trace;ε ⇝ [True :: Unit :: ε | “False” :: ε] Trace;ε • [True::4::Unit::ε|”False”::ε]Or;Pop;ε⇝[ε|”Panic”::”False”::ε]ε

Given a stack of the form a :: S where a is a boolean values, the Not command removes a from the stack and puts its negation (¬a) onto the stack.
The Not command has 2 fail states.
1. NotError1: a is not a boolean.
2. NotError2: The stack is empty (S = ε).
When Not fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
a is a boolean [a::S|T]Not;P ⇝[(¬a)::S|T]P
a is not a boolean [a::S|T]Not;P ⇝[ε|”Panic”::T]ε
[ε|T]Not;P ⇝[ε|”Panic”::T]ε
• [True::Unit::ε|”False”::ε]Not;ε⇝[False::Unit::ε|”False”::ε]ε • [4 :: Unit :: ε | “False” :: ε] Not;Pop;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
• [ε | “False” :: ε] Not;Add;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
Given a stack of the form i :: j :: S where both i and j are integer values, the Lt command removes i and j from the stack and puts the boolean result of their comparison (i < j) onto the stack. The Lt command has 3 fail states. 1. LtError1: Either i or j is not an integer. 2. LtError2: The stack is empty (S = ε). 3. LtError3: The stack has only 1 element (S = c :: ε). When Lt fails, the stack is cleared, the string "Panic" is prepended to the trace and the program terminates. i and j are both integers [i::j::S|T]Lt;P ⇝[(i j) onto the stack.
The Gt command has 3 fail states.
1. GtError1: Either i or j is not an integer.
2. GtError2: The stack is empty (S = ε).
3. GtError3: The stack has only 1 element (S = c :: ε).
When Gt fails, the stack is cleared, the string “Panic” is prepended to the trace and the program terminates.
i and j are both integers [i::j::S|T]Gt;P ⇝[(i>j)::S|T]P
[ε|T]Gt;P ⇝[ε|”Panic”::T]ε
i or j is not an integer [i::j::S|T]Gt;P ⇝[ε|”Panic”::T]ε
[c::ε|T]Gt;P ⇝[ε|”Panic”::T]ε
• [4::5::True::Unit::ε|”False”::ε]Gt;ε⇝[False::True::Unit::ε|”False”::ε]ε • [10::5::True::Unit::ε|”False”::ε]Gt;ε⇝[True::True::Unit::ε|”False”::ε]ε • [5::5::True::Unit::ε|”False”::ε]Gt;ε⇝[False::True::Unit::ε|”False”::ε]ε • [4 :: True :: Unit :: ε | “False” :: ε] Gt;Trace;ε ⇝ [ε | “Panic” :: “False” :: ε] ε
程序代写 CS代考 加QQ: 749389476
Full Examples
• Compute the polynomial x2 − 4x + 7 at 3:
Result: Some [“4”] • De Morgan’s Law:
Push False;
Push False;
Push False;
Push False;
Result: Some [“True”; “True”] • x2 is monotonic:
Result: Some