"""
BEGIN 16_11_29_Referential_Transparency.lhs

REFERENTIAL TRANSPARENCY and PROGRAMMING WITHOUT SIDE-EFFECTS
------------------------------------------------------------------------
(This handout is simultaneously written in Python and literate Haskell.)

For a good discussion of Referential Transparency, consult:

http://stackoverflow.com/questions/210835/what-is-referential-transparency
https://en.wikipedia.org/wiki/Referential_transparency

as well as Section 3.2 ("Purity") in:

https://wiki.haskell.org/Functional_programming

For a good discussion of Side Effects, consult:

https://en.wikipedia.org/wiki/Side_effect_(computer_science)
-----------------------------------------------------------------------

Execute this handout as a script in Python by issuing one of the 
two following commands, at the Python interpreter's prompt '>>>' :
      execfile ('16_11_29_Referential_Transparency.lhs')   or
      execfile ("16_11_29_Referential_Transparency.lhs")

Execute this script in Haskell by issuing the following command
at the Haskell interpreter's prompt '>' :
      :load 16_11_29_Referential_Transparency.lhs

SOME TERMINOLOGY:
----------------
 
REFERENTIAL TRANSPARENCY is the ability to replace a well-formed expression
(or program phrase) with its value without changing the behavior of the
program.

REFERENTIAL OPACITY (or OPAQUENESS) is the opposite of referential transparency.

REFERENTIALLY TRANSPARENT qualifies a program that satisfies the conditions
of referential transparency .

REFERENTIALLY OPAQUE is the opposite of referentially transparent.

SIDE EFFECT is the result of a program expression whose execution modifies 
some state (typically the store/memory configuration) or has an observable 
interaction with calling functions or the outside world. 

REFERENTIAL TRANSPARENCY is more restrictive than absence of SIDE EFFECTS, i.e.
the latter is a necessary but not sufficient condition for the former.

"""

## BEGIN EXAMPLE 1 (in Python)

globalValue = 0;

def ref_opac (x):
    global globalValue
    globalValue = globalValue + 1 ;
    return x + globalValue

def ref_trans (x):
    return x + 1

## The function ref_trans is referentially transparent, because if e1 = e2
## for any two expressions e1 and e2, then ref_trans(e1) = ref_trans(e2). 
## Another way of saying this: ref_trans is referentially transparent because
## its execution involves no SIDE-EFFECTS.
##
## By contrast, the function ref_opac is referentially opaque, because if 
## e1 = e2, it does not necessarily follow that ref_opac(e1) = ref_opac(e2).  
## Indeed, even if the execution of e1 and the execution of e2 return the same
## value, if the execution e1 (but not that of e2) has the side-effect of 
## changing the value of the global variable globalValue, then ref_opac(e1) 
## and ref_opac(e2) will evaluate to different values.
##
## To be more specific, the referential opacity of ref_opac makes it difficult
## to reason about its behavior. For example, say we wish to reason about 
## the following statement:
##
##  p = ref_opac(x) + ref_opac(y) * (ref_opac(x) - ref_opac(x));
##
## We may be tempted to simplify this statement to:
##
##  p = ref_opac(x) + ref_opac(y) * (0);
##  p = ref_opac(x) + 0;
##  p = ref_opac(x);
##
## However, this will not work for ref_opac, because each occurrence of 
## ref_opac(x) evaluates to a different value. Remember that the return 
## value of ref_opac is based on a global value that is not passed in and 
## which gets modified on each call to ref_opac. This means that mathematical
## identities such as "x-x=0" no longer hold.
##
## Question 1: 
## ===========
## Should not the two following Python expressions return the same value?
##
##           ref_opac  (ref_opac  (ref_opac  (3)))
##           ref_trans (ref_trans (ref_trans (3)))
##           
## They do not return the same value. Explain why.

## END EXAMPLE 1

"""

BEGIN EXAMPLE 2 (in C)

The Python code in Example 1 can be translated into the following C code:

     int globalValue = 0;

     int ref_opac (int x)
     {
       globalValue++;
       return x + globalValue;
     }

     int ref_trans (int x)
     {
       return x + 1;
     }

Question 2:
===========
Compare the Python code in Example 1 and the C code in this example.

(a) Consider the pros and cons of including type information (as in 
the C code above) and excluding type information (as in the Python code
in Example 1).

(b) The Python code in Example 1 requires that variable globalValue be
declared 'global' within the scope of the function ref_opac. The C code
omits this requirement. Explain the reasons for this requirement, its
inclusion (in Python) and its omission (in C).

END EXAMPLE 2

BEGIN EXAMPLE 3 (in Haskell)

We may try to translate the Python code in Example 1 (or equivalently the 
C code in Example 2) into Haskell code as follows:

> globalValue :: Int
> globalValue = 0
>
> ref_opac :: Int -> Int
> ref_opac x = x + globalValue
>              where
>              globalValue = globalValue + 1
>
> ref_trans :: Int -> Int
> ref_trans x = x + 1

However, although this Haskell code can be interpreted without a problem,
you will not be able to execute ref_opac, say, ref_opac(3). If you try, 
you will get an error message like "ERROR - Control stack overflow".

Question 3: 
==========
Why do you get "ERROR - Control stack overflow"? Explain.

Question 4: 
==========  
Explain the difference between 
       "globalValue = globalValue + 1" in Python 
       and  "globalValue = globalValue + 1" in Haskell

Question 5: 
==========  
The code in Python and the code in Haskell include an identical piece of
syntax, namely, the expression "globalValue = globalValue + 1". 

(a) Does the two occurrences of "globalValue" in this expression have
the same meaning in Python? Explain.  

Hint: NO. Search on the Web the difference between L-values (or Left values)
and R-values (or Right values).

(b) Does the two occurrences of "globalValue" in this expression have
the same meaning in Haskell? Explain.

Hint: YES.

END EXAMPLE 3

---------------------------------------------------------------------
FINAL COMMENT:

Programming imperatively (as in Python or in C) does not necessarily
MEAN that we have to deal with referential opacity. We can perfectly
write referentially transparent code in Haskell and its equivalent
referentially transparent code in Python -- as in the following:

> compose f g = \ x -> f (g x)
> square x = x * x
> successor x = x + 1
> square_successor = compose square successor
> result = square_successor 8

The following is the equivalent Python code:

""" 

def compose (f, g):
    def h(x):
        return f(g(x))
    return h
def square(x):
    return x * x
def successor(x):
    return x + 1
square_successor = compose (square, successor)
result = square_successor(8)

# 'compose' can be defined more directly by using anonymous functions

def composeB (f, g):
    return lambda x: f(g(x))

"""
END 16_11_29_Referential_Transparency.lhs
"""