Posted on April 29, 2018

Concepts in Programming Languages II

  1. 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.

  2. 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 =
          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

      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 =
          type t
          val empty   : t
          val push    : (t * StackElement) -> t
          val top     : t -> int
  3. What is the difference between parallelism and concurrency? Under which circumstances each of them improve performance benefits?

    How a pthreads different from Erlang processes?

  4. 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.

  5. 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.

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

Wadler, P., 1995. Monads for functional programming, in: International School on Advanced Functional Programming. Springer, pp. 24–52.