Перевод псевдо кода из Haskell в STG

Week 12. Problem set

1. Translate the following Haskell program into the STG language [STG, Section 4] using the

notation that is supported by stgi tool1

. Make sure the translated program is correct by running

it with stgi and comparing it against the Haskell version. You must use standard constructors.

Each thunk that is computed at most once must be non-updatable.

2. For each non-updatable thunk (closure without arguments), leave a comment in the code with a

clear explanation of why it is marked as non-updatable.

3. How many objects are allocated in the heap at runtime after entering main?

How many of these objects are constructors (Int#, Lit, Var, etc.)?

1

data Int = Int# Int#

2

data VarId = VarId Int deriving (Eq)

3

data Expr

4

= Lit Int

5

| Var VarId

6

| Add Expr Expr

7

| Mul Expr Expr

8

| Let VarId Expr Expr

9

10

eval :: (VarId -> Int) -> Expr -> Int

11

eval valueOf = go

12

where

13

go (Lit n) = n

14

go (Var x) = valueOf x

15

go (Add l r) = go l + go r

16

go (Mul l r) = go l * go r

17

go (Let x e body) = eval (\y -> if x == y then go e else valueOf y) body

18

19

pow :: Expr -> Int -> Expr

20

pow e 0 = Lit 1

21

pow e n = Mul e (pow e (n - 1))

22

23

sop :: Expr -> Int -> Expr

24

sop e 0 = Lit 1

25

sop e n = Let z (pow e n) (Add (Var z) (sop e (n - 1)))

26

where z = VarId n

27

28

main :: Int

29

main = eval valueOf e

30

where

31

x = VarId 100

32

e = sop (Add (Var x) (Lit 1)) 2

33

valueOf (VarId i) =

34

case i of

35

100 -> 8

36

_ -> 0

1See https://github.com/quchen/stgi.