###### tags: `chalmers`
# Deep Turtle

### Task 1
>*What definition of time do you use (what can a turtle achieve in a single time unit)?*

We use the basic operations as a unit of time. That is, a turtle can move forward, turn, lower or raise the pen, do nothing, die or change color in a single unit of time.

### Task 2
>*What happens after a parallel composition finishes? Is your parallel composition commutative, is it associative? (To answer this question you must first define what it means for programs to be equal.) What happens if a turtle runs forever only turning left in parallel with another turtle running the spiral example? Does your textual interface handle this situation correctly, if not — how would you fix it?*

When a parallel composition finishes it will return a state (most often) composed of multiple turtles, meaning than any program applied after that point will be executed by all the turtles, according to their individual parameters.
In practice this is obtained by applying the second program to all the leafs of the tree data structure used to reppresent the abstract execution of the first program, as shown in the code snipped below:

-- | Abstract execution tree.
type Exec = (Turtle -> [TTree])

-- | Applies an abstract execution to all the turtle states contained
-- in the leaf nodes of an already computed execution tree and sets each
-- resulting list of trees as the children trees of that node.
after :: TTree -> Exec -> TTree
after (Node t tts) ex | not $ null tts = Node t [tt `after` ex | tt <- tts]
                      | not $ rip  t   = Node t (ex t)
                      | otherwise      = Node t []

-- | Sequential execution.
newtype Seq = Seq Exec

instance Semigroup Seq where
   (Seq ex1) <> (Seq ex2) = Seq $ -- (>*>)
      \t -> [ tt `after` ex2 | tt <- ex1 t ]

The parallel composition is both associative and commutative if we look at the execution tree computed from the same initial state.
If we run the following program:

example1 = forever (left 10) <|> spiral 0 115

- with `runGraphical`:


- with `runTextual` it prints forever the first turtle rotating, after the second one is done drawing the spiral.

> *How does parallel composition interact with lifespan and limited? (lifespan does not need to correspond realistically to actual life spans, just specify how it works.)*

If two turtles run in parallel and one finishes sooner because the program is shorter, the earlier turtle starts with whatever comes after the parallel block. If a turtle dies in parallel with another, that turtle does not do anything after the parallel block. For instance, the program

(lifespan 1 (forward 10) <|> limited 2 (forward 10)) >*> forward 50

will result in one turtle moving forward 10 units and then dying. The second turtle will move forward 10 units twice, after which it will take a leap 50 units forward.

### Task 3
From `Extras.hs`:

-- | Draws a regular polygon with n sides and of radius r so that
-- the initial turtle position is the center of the polygon.
-- At the end of the drawing the turtle returns to its initial position
-- and orientation.
polygon :: Int -> Double -> Program 
polygon n r = before >*> times n drawEdge >*> after
 where 
   before = penUp >*> forward r >*> right gamma >*> penDown
   drawEdge = forward l >*> right alpha2
   after  = penUp >*> right beta >*> forward r >*> right 180 >*> penDown
   l = 2 * sin (deg2rad alpha) * r
   gamma  = 90 + alpha
   beta   = 90 - alpha
   alpha  = alpha2 / 2
   alpha2 = 360 / n'
   n' = int2Double n

-- | Draw a triangle
triangle :: Double -> Program
triangle = polygon 3

-- | Draw a square
square :: Double -> Program
square = polygon 4

-- | Draw a pentagon
pentagon :: Double -> Program
pentagon = polygon 5

-- | Draw a hexagon
hexagon :: Double -> Program
hexagon = polygon 6

-- | Draw a heptagon
hexagon :: Double -> Program
hexagon = polygon 7

-- | Draw an octagon
hexagon :: Double -> Program
hexagon = polygon 8

-- | Draw a serpinsky triangle (infinitely).
serpinsky :: Double -> Program
serpinsky r = triangle r
            >*> penUp
            >*> ( left 120 <|> idle <|> right 120 )
            >*> forward r'
            >*> penDown
            >*> serpinsky r'
 where   r' = r / 2

### Task 4
> *Implement an example drawing something cool.*

We found this to be pretty cool:

module Main where

import Turtle
import Graphics.Gloss.Data.Color

main = runGraphical $ limited 500 $ double >*> serpinsky 100

double = (idle >*> idle <|> color yellow >*> right 180)

`runGraphical` output:


### Task 5
>*Did you use a shallow or a deep embedding, or a combination? Why? Discuss in a detailed manner (giving code) how you would have implemented the Program type if you had chosen the other approach. What would have been easier/more difficult?*

As the name of our executable may suggest, we started with a deep embedding approach. Throughout the process, we changed approach a couple of times and later realised that what we had done in practice was an almost purely shallow embedding in disguise. This was proven by our (more than successful) attempt to switch to an 100% shallow implementation, which we achieved by basically using a type we had already defined specifically for the run function as the `Program` type.

This was the deep embedding approach:

run' :: Program -> Run
run' Die  =      mempty :: Par
run' Idle = Par (mempty :: Seq)
run' (p1 `Fork` p2) =       par (run' p1) <> par (run' p2)
run' (p1 `Then` p2) = Par $ seq (run' p1) <> seq (run' p2)
run' (Limited n p) | n > 0 = Par $ Seq $ \t -> map (ttake n) (exec (run' p) t)
                   | n < 1 = run' Idle
run' action = Par ( Seq (run'' action))
 where
   run'' :: Program -> Turtle -> [TTree]
   run'' action ts = tpure $ f ts action
   f :: Turtle -> Program -> Turtle
   f (Turtle i (x,y) a d c r) (Forward n) = Turtle i (x+sin a*n, y+cos a*n) a d c r
   f (Turtle i (x,y) a d c r) (Right n)   = Turtle i (x, y) (a + deg2rad n) d c r
   f (Turtle i (x,y) a _ c r) (PenUp)     = Turtle i (x, y) a False c r
   f (Turtle i (x,y) a _ c r) (PenDown)   = Turtle i (x, y) a True c r
   f (Turtle i (x,y) a d _ r) (Color c)   = Turtle i (x, y) a d c r
   deg2rad :: Double -> Double
   deg2rad = (* (2 * pi)) . (/ 360)

This is the final (shallow) approach:

-- * Creation functions

-- | Move forward the given number of steps.
forward :: Double -> Program
forward n = Par $ Seq $
   \(Turtle i (x,y) a d c r) -> tpure $ Turtle i (x+sin a*n, y+cos a*n) a d c r

-- | Turn rightwards of n degrees.
right :: Double -> Program
right n = Par $ Seq $
   \(Turtle i (x,y) a d c r) -> tpure $ Turtle i (x, y) (a + deg2rad n) d c r
 where  
   deg2rad = (* (2 * pi)) . (/ 360)

-- | Set isDrawing to False.
penUp :: Program
penUp = Par $ Seq $
   \(Turtle i (x,y) a _ c r) -> tpure $ Turtle i (x, y) a False c r

-- | Set isDrawing to True.
penDown :: Program
penDown = Par $ Seq $
   \(Turtle i (x,y) a _ c r) -> tpure $ Turtle i (x, y) a True c r

-- | Set the color.
color :: Color -> Program
color c = Par $ Seq $ 
   \(Turtle i (x,y) a d _ r) -> tpure $  Turtle i (x, y) a d c r

-- | Program that "kills" the turtle 
-- (rendering it unable to perform any more actions).
die :: Program
die = mempty :: Par

-- | Program that does nothing.
idle :: Program
idle = Par (mempty :: Seq)

-- * Derived creation functions

-- | Move forward the given number of steps.
backward :: Double -> Program
backward n = forward (-n)

-- | Turn rightwards of n degrees.
left :: Double -> Program
left n = right (-n)

-- * Primitive combinators

-- | Program that makes the turtle stop what it is doing
-- after a specified period of time.
limited :: Int -> Program -> Program
limited n p | n > 0 = Par $ Seq $ \t -> [ ttake n tt | tt <- exec p t ]
            | n < 1 = idle

-- | Program sequential composition (associative).
(>*>) :: Program -> Program -> Program
(>*>) p1 p2 = Par $ seq p1 <> seq p2

infixr 7 >*>

-- | Program parallel composition (associative).
(<|>) :: Program -> Program -> Program
(<|>) p1 p2 = par p1 <> par p2

infixr 6 <|>

-- * Derived combinators

-- | Repeats a turtle program a certain number of times.
times :: Int -> Program -> Program
times 0 p = idle
times n p = p >*> times (n-1) p

-- | Repeats a turtle program forever.
forever :: Program -> Program
forever p = p >*> forever p

-- | Program that kills the turtle after a specified period of time.
lifespan :: Int -> Program -> Program
lifespan n p = limited n p >*> die

-- | List containing a single leaf tree.
tpure :: Turtle -> [TTree]
tpure = pure . tleaf

-- * Run function

run :: Program -> TTree
run = ttree

>*Compare the usability of your embedding against a custom-made implementation of a turtle language with dedicated syntax and interpreters. How easy is it to write programs in your embedded language compared to a dedicated language? What are the advantages and disadvantages of your embedding?*

We think it works fairly well. Most programs are fairly straightforward to write within our embedded language. The one pain point is functions that take multiple arguments. For someone used to Haskell, it is ok, but for someone not used to haskell the need for adding multiple levels of parenthesis or using . or $ operators may be a bit daunting. This could be alleviated a bit by more carefully defining the fixity and binding precedence of each operator and word in the embedded language.

>*Compare the ease of implementation of your embedding against a custom-made implementation. How easy was it to implement the language and extensions in your embedded language compared to a dedicated language? What are the advantages/disadvantages of your embedding?*

Looking back at the Programming Language Technology course, it was a lot faster to create an embedded language than create a custom-made implementation of a language. The main advantage as we see it is the speed of prototyping, you can try new things out very fast and change things quickly. The main drawback is that you are limited to the confines of the language (your embedded language has to be a superset of the original language).

>*In what way have you used the following programming language features: higher-order functions, laziness, polymorphism?*

We have used higher-order functions to make working with lists more convenient and when we defined the sequential operator:

instance Semigroup Seq where
   (Seq ex1) <> (Seq ex2) = Seq $ -- (>*>)
      \t -> map (f ex2) (ex1 t)
    where 
      f :: Exec -> TTree -> TTree
      f ex (Node t []) | (not.rip) t = Node t (ex t)
                       | otherwise   = Node t []
      f ex (Node t tts) = Node t (map (f ex) tts)

Both the graphical and the textual run are lazy, which lets us run infinite programs. We also used laziness when implementing limited:

run' (Limited n p) | n > 0  = Par $ Seq $ \t -> map (ttake n) (exec (run' p) t)
                   | otherwise = run' Idle

and we depend on laziness for forever:

-- | Repeats a turtle program forever.
forever :: Program -> Program
forever p = p >*> forever p

There was an earlier version of our ESDL in which our state tree was polymorphic. As we refactored the code to better define how some operators worked with each other, we decided to not make it polymorphic to make our code overall simpler since there was no need within the scope of our language to make it polymorphic.

> *Is your program data type a monoid? Under which operations? There may be several possible monoid instances. Would it be a monoid if some small change was made to your operators?*

Although there are similarities, our program is not technically a monoid. In order to make working with parallel and sequential operations easier, we defined them as monoids.

-- | Sequential execution.
newtype Seq = Seq Exec

instance Semigroup Seq where
   (Seq ex1) <> (Seq ex2) = Seq $ -- (>*>)
      \t -> map (f ex2) (ex1 t)
    where 
      f :: Exec -> TTree -> TTree
      f ex (Node t []) | (not.rip) t = Node t (ex t)
                       | otherwise   = Node t []
      f ex (Node t tts) = Node t (map (f ex) tts)
instance Monoid Seq where
   mempty = Seq $ \t -> [Node t []] -- idle

-- | Parallel execution.
newtype Par = Par Seq

instance Semigroup Par where
   (Par (Seq ex1)) <> (Par (Seq ex2)) = Par $ Seq $ -- (<|>)
      \t -> let (t1,t2) = mitosis t in (ex1 t1) ++ (ex2 t2)

instance Monoid Par where
   mempty = Par $ Seq $  -- die
      \(Turtle i p a d c _) -> [Node (Turtle i p a d c True) []]
      
-- | Runnable execution.
type Run = Par

If we were to use shallow instead of deep embedding, it would have been natural to implement program as a monoid either under the then operator (`>*>`) operator, or under the Fork operator (`<|>`) and construct the program before passing it to our run function. We went for a deep embedding however, and instead defined a type `Run` that is a monoid for the then and fork operators.

### Algebraic rules of our language

p1 <|> p2 === p2 <|> p1
(p1 <|> p2) >*> p3 === p1 >*> p3 <|> p2 >*> p3
How do (<|>) and (>*>) interact?
(p1 <|> p2) >*> (p3 <|> p4) === p1 >*> p3 <|> p1 >*> p4 <|> p2 >*> p3 <|> p2 >*> p4
die >*> p1 === die
(die <|> p1) >*> p2 === die <|> p1 >*> p2
(idle <|> p1) >*> p2 === idle >*> p2 <|> p1 >*> p2
forever p1 >*> p2 === forever p1
times 0 p1 === idle