[SOLVED] CS代考计算机代写 Java Haskell module StackLang where

module StackLang where

import Prelude hiding (Num)

—
— * Syntax of StackLang
—

— Grammar for StackLang:
—
—int ::= (any integer)
— bool ::= `true`|`false`
— prog ::= cmd*
—cmd ::= int push a number on the stack
— |boolpush a boolean on the stack
— |`+` add the top two integers on the stack
— |`*` multiply the top two integers on the stack
— |`<=`is the top integer LEQ the second integer on the stack– |`if` prog if the value on the top is true, then run–`else` prog the first program, else run the second–`end`– Examples of real world stack-based languages:–* Forth–* Postscript–* HP programmable calculators–* Java Virtual Machine– 1. Encode the above grammar as a set of Haskell data typestype Prog = [Cmd]data Cmd = PushI Int | PushB Bool | Add | Mul | LEq | IfElse Prog Progderiving (Eq,Show)– 2. Write the following StackLang program as a Haskell value:—- 3 4 + 5 <=–ex1 :: Progex1 = [PushI 3, PushI 4, Add, PushI 5, LEq]– 3. Write a StackLang program that:– * checks whether 3 is less than or equal to 4– * if so, returns the result of adding 5 and 6– * if not, returns the value false–First write it in concrete syntax, then in abstract syntax as a Haskell value.—-3 4 <= if 5 6 + else false end–ex2 :: Progex2 = [PushI 3, PushI 4, LEq, IfElse [PushI 5, PushI 6, Add] [PushB False]]– 4. Write a Haskell function that takes two arguments x and y–and generates a StackLang program that adds both x and y to–the number on the top of the stack.genAdd2 :: Int -> Int -> Prog
genAdd2 x y = [PushI x, Add, PushI y, Add]
— genAdd2 x y = [PushI x, PushI y, Add, Add]

— 5. Write a Haskell function that takes a list of integers and
—generates a StackLang program that sums them all up.
genSum :: [Int] -> Prog
genSum [] = [PushI 0]
genSum (i:is) = genSum is ++ [PushI i, Add]

— This also works, but our stack gets big!
—
— genSum (i:is) = PushI i : genSum is ++ [Add]

—
— * Semantics of StackLang (now!)
—

— 6. Identify/define a semantics domain for Cmd and for Prog.

— Concepts that we need for our semantics
—* We need a Stack with these kinds of elements
—* Int
—* Bool
—* Our stack will change as we execute commands
—* Only things commands do is change the stack: Stack -> Stack
—* Errors:
—* type errors
—* not enough things on the stack

type Stack = [Either Bool Int]

type Domain = Stack -> Maybe Stack

— 7. Define the semantics of a StackLang command (ignore if-else at first).
cmd :: Cmd -> Stack -> Maybe Stack
cmd (PushI i)s = Just (Right i : s)
cmd (PushB b)s = Just (Left b : s)
cmd Add(Right i : Right j : s) = Just (Right (i + j) : s)
cmd Mul(Right i : Right j : s) = Just (Right (i * j) : s)
cmd LEq(Right i : Right j : s) = Just (Left (j <= i) : s)cmd (IfElse t _) (Left True : s) = prog t scmd (IfElse _ e) (Left False : s)= prog e scmd __ = Nothing– 8. Define the semantics of a StackLang program.prog :: Prog -> Stack -> Maybe Stack
prog [] s = Just s
prog (c:cs) s = case cmd c s of
Just s’ -> prog cs s’
Nothing -> Nothing

— | Run a program on an initially empty stack.
—
— >>> run ex2
— Just [Right 11]
—
— >>> run (genSum [1..10])
— Just [Right 55]
—
— >>> run [PushN 3, Add, PushN 4]
— Nothing
—
run = undefined