COP4020 Final Study Guide (Based on HW4 / HW5)

_______________________________________________

Does Erlang use static scoping?
    Yes, because it makes closures*.

What kind of type checking does Erlang use?
    It uses dynamic type checking.



HW4: concat
Write a function 'concat/1' whose type is given:

    -spec concat(Lists :: [[T]]) -> [T].

which takes a list of lists, Lists, and returns a
list that contains all of the inner lists concatenated
together, in order.

%start%
-module(concat).
-export([concat/1]).

concat([]) -> [].
concat([Head|Rest]) -> Head ++ concat(Rest).
%end%



HW4: salesdata/substaddr
Given two record types, defined in salesdata.hrl:

-record(store, {address :: string(), amounts :: [integer()]}).
-record(group, {gname :: string(), members :: [salesdata:salesdata()]}).

where the type salesdata() is defined:

%start%
-module(salesdata).
-include(salesdata.hrl").
-export_type([salesdata/0]).

-type salesdata() :: #store{} | #group{}.
%end%

write a function:

-spec substaddr(SD :: salesdata:salesdata(), New :: string(), Old :: string()) -> salesdata:salesdata().

that takes a sales data record 'SD',
two strings 'New' and 'Old', and returns a sales
data record who's identical to SD except that all
addresses with the value 'Old' are replaced with 'New'

For this problem, since Erlang does not currently
permit type imports, you pattern match for record data
when defining the functions for substaddr:

%start%
-module(substaddr).
-export([substaddr/3]).
-include("salesdata.hrl").
-import(salesdata, [store/2, group/2]).

-spec substaddr(SD :: salesdata:salesdata(), New :: string(), Old :: string()) -> salesdata:salesdata().

substaddr(#store{address = Addr, amounts = Amts}, New, Old) ->
  #store{address = if Addr =:= Old -> New;
                        true -> Addr
                   end,
        amounts = Amts};
substaddr(#group{gname = Name, members = Mems}, New, Old) ->
    #group{gname = Name,
        members = lists:map(fun (SD) -> substaddr(SD, New, Old) end, Mems)}.
%end%

Assign each field to a variable, then return a record,
assign each field in the new record according to the
proper logic



HW4: count_matching
Write a tail-recursive function:

-spec count_matching (Pred::fun((T) -> boolean()), Lst::list(T)) -> non_neg_integer().

that takes a predicate, Pred, and a list, Lst, and
returns the number of elements in Lst that satisfy
Pred.

%start%
-module(count_matching).
-export([count_matching/2,loop/3]).
-spec count_matching (Pred::fun((T) -> boolean()), Lst::list(T)) -> non_neg_integer().

count_matching(Pred, Lst) ->
    loop(Pred,Lst,0).
-spec loop(Pred :: fun((T) -> boolean()), Lst :: list(T), Acc :: non_neg_integer()) -> integer().
loop(_P,[],Acc) ->
    Acc;
loop(P, [X|Xs], Acc) ->
    loop(P, Xs, Acc + (case P(X) of
                        true -> 1;
                        false -> 0
                       end)).
%end%

_________________________________________________

HW5: mapInside
Correctly implement the following function:

-spec mapInside(F::fun((T) -> R), Llt::list(list(T))) -> list(list(R)).

which for all types T & R, takes a function F from
T to R, and a list of lists, Llt, who consist of lists
of type T... and returns a list of lists whose
elements are the lists that come from mapping F over
lists of type T inside Llt in order

mapInside(F, Llt) -> foldr(fun(Ls, Res) -> [map(F,Ls)|Res] end, [], Llt).



HW5: FREE AND BOUND IDENTIFIERS
Considering the following expression:

H(fun(X,Y) -> K(foo(bar({the_fun, fun(A,H) -> minus (A,4020) end}))) end; K)

List the set of all identifiers that occur free
{H,K,foo,bar,minus}.

NOTE: 'the_fun' is an atom, not an identifier. ALSO,
X & Y are not used, only declared. They do not occur
either free or bound.

List the set of all identifiers that occur bound
{A}.

NOTE: minus, foo, bar are not declared in the
expression, and are thus free and not bound.
X & Y are not used, only declared. They do not occur
either free or bound.
While H is used in the expression, the use is not in
the scope of the declaration of H as a formal param,
thus the use of H is a free (not bound) occurance.



HW5: MORE ON FREE AND BOUND IDENTIFIERS
Consider the following expression:

P(foo(Q(map(fun (E) -> bar(P, Q, P(Q(E)), F) end,
            [zero, false, 1, fun(F,G) -> fun(X) -> F(F(X)) end end]))))

List the set of all identifiers that occur free
{P,Q,foo,map,bar,F}.

NOTE: zero and false are atoms, not identifiers. G
is not used at all, only declared. It does not occur
free or bound.

List the set of all identifiers that occur bound
{E,F,X}.

NOTE: zero and false are atoms, not identifiers. G
is not used at all, only declared. It does not occur
free or bound.



HW5: Scope rules & concepts
Suppose a programming language has a way to create
function values at runtime, like Erlang does. Explain
how the semantics of function values can tell you
about whether that language has static or dynamic
scoping for variable names?

Answer: If the language makes closures when it
creates function values at runtime, then it has static
scoping, because closures are designed to record
the surrounding environment of a function value for
static scoping.

**What is a closure?


If a language makes closures for function values that
are created at runtime, then with respect to the
closure expression itself, what kind of identifiers
that occur within the text of the function closure
expression's code does it need to remember values for:
Free identifiers or bound identifiers?

Answer: Free identifiers, as those are not defined by
declarations within the code.


Is static scoping more useful for variables than
dynamic scoping? Explain why (or why not)

Answer: Yes, static scoping is more useful, because
it allows you to understand a functional abstraction
locally, where it is written, and to have that
understanding be valid throughought the execution of
the program (unlike with dynamic scoping). Static
scoping also supports techniques like currying
functions and static type checking.

How are exception handlers in Java (or C# or C++)
scoped? Statically or dynamically?

Answer: They are scoped dynamically, because when an
exception is thrown, the most recent active handler
for that exception is executed.



HW5: TYPE CHECKING
An example of an expression in Erlang that generates
a type error:

Answer: 3 + atom.

Which type of type checking allowers the programmer
more flexibility? Static or Dynamic?

Answer: Dynamic type checking. Static checking, due
to it's conservative nature, will prevent some
programs that would not (dynamically) encounter a
type error from executing, such as the one below.

Give an example of an expression (in Erlang) or
program that will run without a type error that
would not type check if it were translated into
Haskell

Answer:

One: Haskell doesn't allow heterogeneous lists, while
Erlang does.

(Okay) in Erlang: [1, true, fun(X) -> X+4020 end]
(Not Okay) Haskell equivalent: [1, True, (\x->x+4020])]
    - is a type error

Two: Haskell comparisons using are restricted to work
with the same type on both sides. But not in Erlang.

(Okay) in Erlang: (atom == 3) andalso ("string" < 5)
    - which evaluates to false
(Not Okay) Haskell equivalent: ("atom" == 3) && ("string" < 5)
    - is a type error

Three: Haskell function arguments are monomorphic,
a restriction of the Hindley-Milner type system it
uses. Since Erlang is dynamically typed, this is fine,
as the identity function can be applied to arguments
of different types:

(Okay) in Erlang: (fun(F) -> {F(3), F(atom)} end)(fun(X) -> X end)
(Not Okay) Haskell equivalent: (\f -> (f 3, f "atom)) (\x -> x)
    - is a type error

**What does monomorphic mean?

In Erlang, does the representation of every value need
to be encoded in a way that the runtime system can
tell what its type is during each program's exe?

Answer: Yes, that is needed for dynamic type checking
and for the execution of the BIFs that do type tests
at runtime, like is_number, is_atom, and is_pid

**What are BIFs?
BIFs are the functions in Erlang that do tasks which
are impossible to program (in Erlang) such as turning
a list into a tuple.


In Haskell, does the representation of every value
need to be encoded in a way that the runtime system
can tell what its type is during each program's exe?

Answer: No, type checking is all done before runtime,
and there is no way to get the runtime type of a
value at runtime. Type dictionaries are passed at
runtime for code whose type needs values of a
particular type class, but this does not apply generally.


What kind of problems can be solved using a stateless
server in Erlang?

Answer: A stateless server can be used when the
responses to messages do not depend on earlier
messages or responses; that is when no history
is needed to respond to messages.

HW5: MODULES, DATA ABSTRACTION, ENCAPSULATION (info hiding)


*