Plt2013 10

(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau

Logistics

Assignment

Resources

Check out the directory.

See the main module for running the semantics.

You are well advised not to try understanding other modules. (They are complicated.)

To run the main module, be in the right directory:

$ pwd
/Users/laemmel/projects/slps/topics/NielsonN07/Haskell/src
$ ghci While/DenotationalSemantics/SimpleMain0.hs 
GHCi, version 42: http://www.haskell.org/ghc/  :? for help
[1 of 3] Compiling While.SimpleAbstractSyntax
[2 of 3] Compiling While.DenotationalSemantics.SimpleDirectStyle
[3 of 3] Compiling While.DenotationalSemantics.SimpleMain0
> main
120

1st option

Revise the abstract syntax so that binary arithmetic expressions are no longer supported, but instead assignments generalized as follows:

  • "y = 1" is Ok
  • "y = y * x" becomes "y *= x"
  • "x = x - 1" becomes "x -= 1"

That is, you need to eradicate binary forms of arithmetic expressions and you need to add new forms of assignments. Please revise syntax, semantics, and the factorial function.

For illustration, consider again the factorial function:

  Seq
    (Assign "y" (Num 1))
    (While
     (Not (Leq (Var "x") (Num 1)))
     (Seq
      (Assign "y" (Mul (Var "y") (Var "x")))
      (Assign "x" (Sub (Var "x") (Num 1)))))

Now, let's assume some abstract syntax for the new assignment forms:

  Seq
    (Assign "y" (Num 1))
    (While
     (Not (Leq (Var "x") (Num 1)))
     (Seq
      (AssignMul "y" (Var "x"))
      (AssignSub "x" (Num 1))))

2nd option

Extend the abstract syntax with a type for programs such that programs consists of a list of procedures and some statements. For simplicity, there are really only top-level procedures. That is, you do not need to consider nested blocks with procedures. You also need to add a statement form for procedure calls. Implement the semantics of programs with procedures in Haskell.

For illustration, consider again the factorial function:

  Seq
    (Assign "y" (Num 1))
    (While
     (Not (Leq (Var "x") (Num 1)))
     (Seq
      (Assign "y" (Mul (Var "y") (Var "x")))
      (Assign "x" (Sub (Var "x") (Num 1)))))

Now, let's assume some abstract syntax for programs and procedures. Thus, the program may factor out the body of the while loop as follows:

Program
  [Proc "p" (Seq
                  (Assign "y" (Mul (Var "y") (Var "x")))
                  (Assign "x" (Sub (Var "x") (Num 1))))]
  (Seq
    (Assign "y" (Num 1))
    (While
     (Not (Leq (Var "x") (Num 1)))
     (Call "p")))