Concepts in Programming Languages II

Do type inference (by hand or typesetter) for the following ML function:

fn f => fn g => fn x => f (g (f x))

This involves providing a derivation tree as well as the constraint generated and their unification.

This question is about ML module system.

1. Provide two implementations using SML module system for the following signature for stack abstract data type:

   signature STACK =
     sig
       type 'a t
       exception E;
   
       val empty : 'a t
       val push  : ('a t * 'a) -> 'a t
       val pop   : 'a t -> 'a t
       val top   : 'a t -> 'a
     end

   The first structure implementing the signature should use a list for its internal representation and the second one should use a new data type with constructors push and empty.

2. With a separate structure assignment create an abstract data type out of the second stack structure. This one must implement the signature opaquely. In comments explain what this means and what operation(s) is prohibited compared to transparent implementation.

3. Define a functor that takes a STACK and generates an EVALUATOR as defined below. Your functor should generate a reverse polish adder.

   datatype StackElement = OpPlus | OpInt of int;
   
   signature EVALUATOR =
     sig
       type t
       val empty   : t
       val push    : (t * StackElement) -> t
       val top     : t -> int
     end

What is the difference between parallelism and concurrency? Under which circumstances each of them improve performance benefits?

How a pthreads different from Erlang processes?

How are recent (last 15 years) advances in hardware have blurred the distinction between distributed systems and single machine parallelism? Give example technologies/language constructs from the course that illustrate your answer.

Please read Wadler (1995) up to and including Section 3. This is the paper I found most useful when I was first learning about monads.

If you don’t find this paper helpful, google “Monad tutorial” and you’ll be presented with hundreds of blog posts each often employs some form of an analogy to explain. Be warned, they might misrepresented the concept, or confuse you due to over simplification.

As many tripos questions as you’d like me to mark.