1a
Lexical analysis identifies tokens using type 3 grammars (regular expressions) it can detect some types of errors, mostly error regarding tokens that do not belong to the language. It can also get rid of spaces and comments. Syntax analysis, on the other hand, takes those tokens as input and uses a type 2 grammar to discover the structure of the program that is being parsed according to the language definition.

2a i) A typed variable is a variable that has a defined type and cannot be assigned values of a different type. For example if variable a has type Int, we cannot assign a boolean value to it. On static type the type of a varaible is defined when the variable is declared. Under a dynamic type, the types of variables is assigned when a value is assigned to it (the first time a value is assigned). This means an id might have different types under different runs of the program, depending on the control flow.

2a ii) By using types all types are known at compile time which allows to better error detection. Also, it makes code more efficient since all memory required by variables can be pre-allocated when the program starts running. One disadvantage is that it can be harder to code (specially for beginners) since the programmer needs to understand how types work. For example, if we are assigning to a variable the result of a function, in a typeless language we could just write a = fun(x,y,z) without knowing what fun returns.

2b i) In call by value the actual parameters are evaluated when the function is called and then copied to the formal parameters. In the case of call by name, the actual parameter is copied as a thunk in the formal parameter, but it is not evaluated until it is used. If the formal parameter is used N times, the thunk will be evaluated N times, and it could have a different value every time.

2b ii)

call-by-value:
sum(calc(0),0) = We need to compute calc(0), but it would need calc(1), which need to compute calc(2), and so on having an infinite recursion.

In call-by-name we would have x=calc(0) (but it is not evaluated) and y = 0… so since y=0 the fuction returns 0 and calc(0) is never used

 

2c i) One way is through templates (C++ style) where there is real polymorphism, only different copies of the same function with different types of parameters. A different approach is have type classes where we can define what kind of operations need to be supported by types belonging to that class, and then we can define functions that can be applied to all types belonging to that class (Haskell style)

ii) A type constructor allows us to define an element of a type. For example we could have a binary tree of integers defined as:
data BinTree = Leaf Int | Node BinTree BinTree
(In this case the type constructors are Leaf and Node)

Another example, we could define different types of vehicles:
data Vehicle = Car String Int | Airplane String Int Float | Boat String Int Float

In this case Car, Airplane and Boat are type constructors

2 ciii)
1) zero :: Num b => a -> b
Since the parameter x is never user (it could be any type) and it returns 0 (a Num – could be an integer, a float, etc)
2) comp :: (a -> b) -> (c -> a) -> c -> b
Lets say the parameter f is a function a->b. Then since we are doing f (g x) we need g to return a (but we don’t have any restrictions on the parameter of g), so g :: c -> a. Now, since we are doing (g x) we need x to be of type c. Finally the return value of comp is the return value of f, so comp returns something of type b
3) func :: Tree a -> (a -> [a]) -> [a]
First we notice that g receives as parameter l which is of type a. Also we notice that there is a concatenation between the result of func, so func must return a list of a. And since func also return the result of g, g must be a function which returns a list of a. So the first parameter of func is a Tree of a (from the pattern in the function definition), and the second parameter is g :: a -> [a]

3ci)

compute(X,0)
First X=1, then X it tries to do X>1 but X is not unified.

compute(2, 0): It will do Z=X-1=1 and unify Y with (2*Z)+Z1=(2*1)+0=2, so it will fail.

compute(3,Y): X=3, X>1,Z is X-1, compute(Z,Z1), Y is (2*Z)+Z1
Z=2, compute(2,Z1), Y is (2*2)+Z1

Now compute(2,Z1) will unify Z1 with 2, so:
Y is 4+2 = 6

compute(0, Y): inifinite loop since it will keep doing Z is X – 1 and compute(Z,Z1)

compute(8, Y), Y = 16 + 14 + 12 + 10 + 8 + 6 + 4 + 2 = 72

3b)ii
1. It doesn’t unify
2. X=f(X) Y=c, W=c, H=1, T=[]
3. X=b, W=W, H=a, T=[b,c]
4. Doesn’t unify since a(b,c) cannot be unified with fb(G,H)
5. Doesn’t unify since [] cannot be unified with [H|T]

3cii)