Erlang exercises

The solutions to these exercises can be found here.

General syntax

• Implement reverse
  reverse([1,2,3]) = [3,2,1]

• Implement a function that finds and returns an element in a list
  find(4, [1,2,3,4,5,6]) = {found, 4}
find(10, [1,2,3,4,5,6]) = not_found

• Implement a function that deletes the first occurrence of an element from a list
  delete(4, [1,2,3,4,5,6]) = [1,2,3,5,6]
delete(10, [1,2,3,4,5,6]) = [1,2,3,4,5,6]

• Implement flatten using append (flatten exists as lists:flatten/1)
  flatten([[1,2], [3,4,5], [6]]) = [1,2,3,4,5,6]

• Implement a function which squares every number in a list. Do this first using tail recursion, then using a list comprehension, then using lists:map/2
square([1,2,3]) = [1,4,9]

• Implement filter: given a predicate (Boolean function) and a list, return the sublist containing only elements for which the predicate holds.
  filter(fun(X) -> X rem 2 =:= 0 end, [1,2,3,4,5,6]) = [2,4,6]

Simple message passing

• Write a server which receives numbers and with each request prints out the current average. Here is an example of how it should work:

  > Pid = spawn(foo, avg_server, [0]).
  Current average is 0
  > Pid ! 10.
  Current average is 5.0
  > Pid ! 10.
  Current average is 7.5
  > Pid ! 10.
  Current average is 8.75

• Update your server to record and display all the input numbers. Unlike above, it shouldn't start from any initial value. It should behave like so:

  > Pid = spawn(foo, avg_server, []).
  > Pid ! 5.
  The average of [5] is 5.0
  > Pid ! 10.
  The average of [5,10] is 7.5
  > Pid ! 20.
  The average of [5,10,20] is 11.666666666666666
  > Pid ! 50.
  The average of [5,10,20,50] is 21.25

• Implement a server which maintains a simple FIFO queue. You should write helper functions to create an API for the user, which hides how the queue is implemented:

  new_queue()      % returns a process ID to a queue server
  push(Pid, Value) % add Value to end of queue
  pop(Pid)         % pop first item from front of queue. If queue is empty, this should block@

  Here is an example of these functions in use:

  > Pid = new_queue().
  > push(Pid, "hello").
  > push(Pid, {tuple}).
  > pop(Pid).
  "hello"
  > push(Pid, 333).
  > pop(Pid).
  {tuple}
  > pop(Pid).
  333
  > spawn(fun() -> X = pop(Pid), io:fwrite("I finally got: ~p~n", [X]) end).
  % ... pause ...
  > push([4,4]).
  I finally got: [4,4]

Semaphores in Erlang (from exam 2015-10)

During the course, we have seen different kind of primitives for concurrent programming: semaphores, monitors, message passing, etc. In fact, we mentioned that these primitives are equally expressive, i.e., what you can do with semaphores, you can do with monitors, what you can do with monitors, you can do with semaphores, and so on. In this exercise, we are going to show that message passing is able to encode semaphores.

Q1

Implement the following Erlang module.

-module(sem).
-export([createSem/1, acquire/1, release/1]).

createSem(InitialValue) -> ...
acquire(Semaphore) -> ...
release(Semaphore) -> ...

Erlang’s processes can, for instance, use this module in the following manner:

Mutex = createSem(0),
acquire(Mutex),
%% critical section
release(Mutex),
%% rest of the program
.

Acquiring or releasing a semaphore should not delay acquiring or releasing another one—every semaphore minds its own business.

Q2

Write some code to test your implementation. It should spawn a bunch of processes, each of which uses the semaphore to control access to some shared resource. Use it to convince yourself that two processes are not able to obtain the semaphone simultaneously.

Elevator (from exam 2016-03)

You are developing a networking module for an application. The main operation of the module is send(H, Msg), which takes a handle and a message, and sends them over the network. Here is the code of the module, which implements this operaion.

-module(network).

-export([start/0, send/2]).

start() -> spawn(fun () -> loop () end).

request(Pid, Data) ->
  Ref = make_ref(),
  Pid!{request, self(), Ref, Data},
  receive
    {result, Ref, Result} -> Result
  end.

send(Pid, Msg) ->
  request(Pid, {send, Msg}).

loop() ->
  receive
    {request, Pid, Ref, {send, Msg}} ->
      net_io:transmit([Msg]),
      Pid ! {result, Ref, ok},
      loop()
  end.

The function start() starts a new instance of the service and returns a handle to it. The function send(H, Msg) sends a message using the low-level net_io:transmit() function and returns ok. The net_io:transmit() function takes a list of messages to send at once. For simpicity we assume that net_io:transmit() does not take any additional argument to specify the end point.

Q1

Since sending a single message at a time has a large overhead, your team decides that calling send() should not send each message at once, but wait until ten messages are accumulated and send all of them with a single call to net_io:transmit(). Change the network module to provide the described behaviour.

Q2

Buffering of messages comes with its own disadvantages. In the scheme implemented in the previous task a single message might be delayed for an arbitrary amount of time if requests to send further messages arrive much later. To mitigate that, the network module should be modified so that no message is kept in the buffer for more than 100 ms. Thus, whenever the buffer contains a message that is 100 ms old all messages should be sent off without waiting for the remaining messages to fill the buffer. Implement the behaviour described above by modifying the network module.