<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Demonstration of Pypi package OCaml for polyglot notebook
TL;DR
Step1:  Then you can use basic OCaml expressions and standard library... from IPython or Jupyter notebook with IPython kernel, without having to install OCaml yourself on your laptop!
It's pre-compiled. I don't know what version thought...
Step2:  It would be a great project to show to students studying Python and C and OCaml 
Step3:  A first example
As for other languages binding, we can have either a full cell, starting with %%ocaml 
Step4:  Natively, IPython/Jupyter supports lots of "magic commands", and especially %%bash, %%perl, %%javascript and %%ruby interface to famous scripting languages, and a generic %%script one.
Step5:  Not that it has been possible, since a long time, to call an OCaml toplevel like this!
Step6:  But it does nothing else than opening a sub-process, running ocaml command, feeding it the content of the cell, and then exiting.
Cons
Step7:  As I was saying, using %%script ocaml allows to quickly check things, like for instance the interface of a module!
Step8:  Using OCaml returned values from Python
This package allows to use dynamically defined OCaml functions from Python, the same way it can be done for other languages lke Julia or R (see this blog post if you never saw these possibilities, or this one).
For instance
Step9:  So booleans, strings, integers and floats get perfectly mapped from OCaml values to Python native values.
Step10:  So 'a list, 'a array and 'a * 'b * .. heterogeneous tuples get perfectly mapped from OCaml values to Python native values!
But it's not perfect, as for instance OCaml has a char type (similar to the one in C) but Python only has strings, so this'll fail
Step11:  And for functions
Step12:  Or simply
Step13:  What about user defined types?
Step14:  It fails
Step15:  Indeed the %ocam magic only works for expression, with no ;;.
More datatypes conversions to Python?
We can still explore
Step16:  Polymorphic function - works!
Step17:  Woooo, somehow OCaml accepted a polymorphic list at some point?
Step18:  Another example
Step19:  Option type
Step20:  Note that this limitation was explained
Step21:  Record - fail
Step22:  Of course it fails!
But it could be translated to Python dictionaries.
Exceptions - fail
Step23:  Polymorphic variants - fail
See documentation
Step24:  Optional arguments - fail
It would be difficult to implement them correctly along side the (awesome) partial application closure feature...
Step25:  Recursive list?
Step26:  It fails, but takes 100% CPU and freezes. But in Python we can do it
Step27:  From standard library
What about Sets, mapped to set?
What about HashTbl, mapped to dict?
And Stack, Queue, etc?
TODO
Step28:  Stack (or any module using a custom type) - fail
Step29:  😮 Curryed functions!
Imagine you define this function in math
Step30:  But you can't directly use it for partial application
Step31:  With the Python standard library, it's possible to use functools.partial to obtain partially evaluated functions, which can be viewed as a limited support of Curryed function.
Step32:  But in OCaml, the conventions is to directly write functions in Curry form, rather than tuple form
Step33:  Indeed, in most situations, the tuple form is just not "OCaml"esque, and tedious to use, and does not allow partial application!
Step34:  Well that was some long explanation, but now comes the magic!
If you use %ocaml to get in Python the values returned from OCaml, then functions are Curryed function!
Step35:  The only information we have on this function is the OCaml signature, in its docstring
Step36:  So we can't use it as a classical 3-arguments Python function
Step37:  But we CAN use it as a Curryed function!
Step38:  Which is awesome because now we can do partial evaluation as in OCaml!
Step39:  What's very cool is that these functions docstrings keep showing the signature of the underlying OCaml function, even if they were obtained from pure Python cells!
Step40:  That's it for this feature, it's cool and interesting.
Some questions
Can we share variables between two consecutive full cells?
In the %ocaml mode, nothing can be shared from the OCaml side, as it's just an expression, let's check
Step41:  But what about full cell mode, %%ocaml?
Step42:  ==> Answer
Step43:  Docstring
Step44:  Also note that the ocaml module is shipped with an example of a tiny module which was written in OCaml and compiled, being made available to Python directly
Step45:  Final note
Step46:  Now for a "large" array, let's use IPython %timeit magic for very quick benchmarking.
Science is about making hypotheses, designing experiments to check them, and conclude.
My hypothesis here is that the OCaml version will be between 10 to 50 slower than the Python one (and Numpy version is 50-200 faster than Python).
Step47:  Well that's better than what I expected!
It seems that the overhead is constant and not increasing when the size of the input is increasing!
It means that if the Python code runs in time $T_1(n)$ for inputs of size $n$, then then OCaml binding code runs in less than $T_2(n) \leq \alpha T_1(n) + \beta$, with two constants $\alpha, \beta$.
Step48:  Just to check the experimental values of $\alpha$ and $\beta$ in my claim above, let's use numpy.polyfit function
<ASSISTANT_TASK:>
Python Code:
!pip3 install ocaml
Explanation: Demonstration of Pypi package OCaml for polyglot notebook
TL;DR: this Pypi ocaml package allows to embed a real and complete OCaml runtime (with full standard library) in an IPython console or Jupyter notebook running IPython kernel (Python 3). OCaml functions and tiny programs can then be called directly from the IPython/Jupyter console, and results can be printed, or affected to Python variables! It even supports Currying multi-argument functions!
See also: note, if you really want to use OCaml in a Jupyter notebook, the best solution is OCaml-jupyter kernel!
(i opened an issue there to present this to the developer, just for his curiosity)
Author: Lilian Besson (@Naereen)
Date: 23/02/2021
License: MIT License
Introduction
See this issue I opened and assigned to myself.
If you run this:
End of explanation
import ocaml
answer_to_life = %ocaml 40 + 2
print(answer_to_life)
print(type(answer_to_life))  # a real integer!
Explanation: Then you can use basic OCaml expressions and standard library... from IPython or Jupyter notebook with IPython kernel, without having to install OCaml yourself on your laptop!
It's pre-compiled. I don't know what version thought...
End of explanation
%load_ext watermark
%watermark -v -p ocaml
Explanation: It would be a great project to show to students studying Python and C and OCaml : this tiny IPython magic makes the link between Python and OCaml (one way) using OCaml compiled as a dynamic extension to CPython 😍 !
Reference and missing documentation of ocaml Pypi package
This Jupyter notebook uses the ocaml v0.0.11 package from Pypi.
There is no documentation, I asked the author, who works at JaneStreet and he redirected me to this blog post by JaneStreet.
Apparently, being professional developers doesn't mean they restrain themselves from shipping unfinished and undocumented packages to Pypi. Okay... Why? It seems highly unprofessional! I understand being in a hurry, but then just don't publish to Pypi, and let user install it using pip but from a Git repository:
bash
$ pip install git+https://github.com/&lt;Username&gt;/&lt;Projects&gt;
Their blog post states
Note that this package is not currently very well polished but it should give some ideas of what can be done through this Python-OCaml integration.
But come on, writing a short README or description in the setup.py is the least that they should do...
Iframe showing the https://pypi.org/project/ocaml/ page:
<iframe src="http://pypi.org/project/ocaml/>
I don't do that!  See my Pypi packages on https://pypi.org/user/Naereen/:
lempel-ziv-complexity (Last released on Dec 19, 2019): Fast implementation of the Lempel-Ziv complexity function.
SMPyBandits (Last released on Oct 25, 2019): SMPyBandits: Open-Source Python package for Single- and Multi-Players multi-armed Bandits algorithms.
parcoursup (Last released on Nov 14, 2018): ParcourSup.py : un clone en Python 3 de ParcoursSup, écrit à but didactique.
generatewordcloud (Last released on Oct 16, 2016): A simple Python (2 or 3) script to generate a PNG word-cloud image from a bunch of text files. Based on word_cloud.
ansicolortags (Last released on Jul 2, 2016): ansicolortags brings a simple and powerful way to use colours in a terminal application with Python 2 and 3.
Let's show the current version of the package, just for reference:
End of explanation
%%ocaml
print_endline "Hello world from OCaml running in Jupyter (from IPython)!";;
Explanation: A first example
As for other languages binding, we can have either a full cell, starting with %%ocaml :
End of explanation
%%bash
echo "Hello world from Bash running in Jupyter (from IPython)"
%%script bash
echo "Hello world from Bash running in Jupyter (from IPython)"
Explanation: Natively, IPython/Jupyter supports lots of "magic commands", and especially %%bash, %%perl, %%javascript and %%ruby interface to famous scripting languages, and a generic %%script one.
End of explanation
%%script ocaml
print_endline "Hello world from OCaml running in Jupyter (from IPython)!";;
Explanation: Not that it has been possible, since a long time, to call an OCaml toplevel like this!
End of explanation
%%ocaml
let sum : (int list -> int) = List.fold_left (+) 0 in
let a_list (n:int) : int list = Array.to_list (Array.init n (fun i -> i*i+30)) in
for n = 300000 to 300010 do
    Format.printf "\nList of size %2.i had sum = %4.i.%!" n (sum (a_list n));
done;;
Explanation: But it does nothing else than opening a sub-process, running ocaml command, feeding it the content of the cell, and then exiting.
Cons: It's not so pretty, as it prints all this startup messages. I thought we could silent them, like python -q (quiet) option... but we can't!
Pros: it shows the value of each line, so it can be used to quickly check something, if needed...
More full %%ocaml cells
End of explanation
%%script ocaml
#show Array;;
Explanation: As I was saying, using %%script ocaml allows to quickly check things, like for instance the interface of a module!
End of explanation
b = %ocaml true
print(type(b), b)
s = %ocaml "OK ?"
print(type(s), s)
i = %ocaml 2021
print(type(i), i)
f = %ocaml 2.99792458
print(type(f), f)
Explanation: Using OCaml returned values from Python
This package allows to use dynamically defined OCaml functions from Python, the same way it can be done for other languages lke Julia or R (see this blog post if you never saw these possibilities, or this one).
For instance:
End of explanation
l = %ocaml [1, 3, 5]
print(type(l), l)
a = %ocaml [|2; 4; 6|]
print(type(a), a)
t = %ocaml (23, 02, 2021)
print(type(t), t)
Explanation: So booleans, strings, integers and floats get perfectly mapped from OCaml values to Python native values.
End of explanation
c = %ocaml 'C'
print(type(c), c)
Explanation: So 'a list, 'a array and 'a * 'b * .. heterogeneous tuples get perfectly mapped from OCaml values to Python native values!
But it's not perfect, as for instance OCaml has a char type (similar to the one in C) but Python only has strings, so this'll fail:
ValueError: ocaml error (Failure"unknown type char")
End of explanation
sum_ocaml_1 = %ocaml let sum : (int list -> int) = List.fold_left (+) 0 in sum
print(sum_ocaml_1, type(sum_ocaml_1))
sum_ocaml_1 ([1, 2, 3, 4, 5])  # 15
Explanation: And for functions:
End of explanation
sum_ocaml_2 = %ocaml List.fold_left (+) 0
sum_ocaml_2 ([1, 2, 3, 4, 5])  # 15
Explanation: Or simply
End of explanation
%%ocaml
type state = TODO | DONE | Unknown of string;;
let print_state (s:state) =
    match s with
    | TODO -> Format.printf "TODO%!"
    | DONE -> Format.printf "DONE%!"
    | Unknown status -> Format.printf "%s%!" status
;;
print_state TODO;;
Explanation: What about user defined types?
End of explanation
t = %ocaml type TODO | DONE
Explanation: It fails:
```
SyntaxError: ocaml evaluation error on lines 1:11 to 1:15
Error: 
1: let out = (type TODO | DONE);;
Syntax error: operator expected.
```
End of explanation
xref = %ocaml ref 1
Explanation: Indeed the %ocam magic only works for expression, with no ;;.
More datatypes conversions to Python?
We can still explore:
- references, let x = ref 1
- polymorphic functions like let smaller (x: 'a) (y: 'a) : true = x &lt; y 
- 'a option type
- functions with labels
- records
- polymorphic variants ?
Fore reference, see https://github.com/janestreet/ppx_python#conversions
References - fail
End of explanation
cons = %ocaml fun hd tl -> hd :: tl
print(cons, type(cons))
cons(10)([20, 30])
cons(1.0)([2.0, 30])
Explanation: Polymorphic function - works!
End of explanation
head, tail = %ocaml List.hd, List.tl
a_list = [1, 2, 3]
a_list.append(a_list)
head(a_list), tail(a_list)
Explanation: Woooo, somehow OCaml accepted a polymorphic list at some point?
End of explanation
smaller = %ocaml fun (x: int) (y: int) -> x < y
print(smaller)
help(smaller)
smaller_poly = %ocaml fun (x: 'a) (y: 'a) -> x < y
print(smaller_poly)
help(smaller_poly)
Explanation: Another example:
End of explanation
none = %ocaml None
print(none, type(none))
some_int = %ocaml Some 42
print(some_int, type(some_int))
# instinguishable from None, so that's weird!
some_None = %ocaml Some None
print(some_None, type(some_None))
Explanation: Option type
End of explanation
# val fold_left : f:('a -> 'b -> 'a) -> init:'a -> 'b list -> 'a
fold_left = %ocaml ListLabels.fold_left
print(fold_left, type(fold_left))
help(fold_left:)
fold_left(lambda x: lambda y: x + y)(0)([1, 2, 3, 4, 5])
Explanation: Note that this limitation was explained:
Note that this makes the two OCaml values [Some None] and [None] indistinguishable on the Python side as both are represented using None.
Functions with labels - labels get erased
End of explanation
%%ocaml
type ratio = {num: int; denom: int};;
let add_ratio r1 r2 =
   {num = r1.num * r2.denom + r2.num * r1.denom;
    denom = r1.denom * r2.denom};;
add_ratio {num=1; denom=3} {num=2; denom=5};;
%ocaml {num=1; denom=3}
Explanation: Record - fail
End of explanation
exc = %ocaml exception Empty_list
Explanation: Of course it fails!
But it could be translated to Python dictionaries.
Exceptions - fail
End of explanation
%%ocaml
Format.printf "%i%!" (let value `float = 0 in value `float);;
zero = %ocaml let value `float = 0 in value `float
print(zero, type(zero))
variant = %ocaml `float
print(variant, type(variant))
Explanation: Polymorphic variants - fail
See documentation
End of explanation
%%ocaml
let bump ?(step = 1) x = x + step;;
Format.printf "\n%i%!" (bump 41);;
Format.printf "\n%i%!" (bump ~step:12 30);;
bump = %ocaml let bump ?(step = 1) x = x + step in bump
Explanation: Optional arguments - fail
It would be difficult to implement them correctly along side the (awesome) partial application closure feature...
End of explanation
%%ocaml
let rec list1 = 0 :: list2
and list2 = 1 :: list1
in
Format.printf "%i -> %i -> %i -> %i ...%!" (List.hd list1) (List.hd list2) (List.hd (List.tl list2)) (List.hd (List.tl list1));;
# don't run
if False:
    list1, list2 = %ocaml let rec list1 = 0 :: list2 and list2 = 1 :: list1 in (list1, list2)
Explanation: Recursive list?
End of explanation
list1 = [0]
list2 = [1]
list1.append(list2)
list2.append(list1)
print(list1)
print(list2)
Explanation: It fails, but takes 100% CPU and freezes. But in Python we can do it:
End of explanation
%%ocaml
module IntPairs = struct
    type t = int * int
    let compare (x0,y0) (x1,y1) =
        match Stdlib.compare x0 x1 with
        0 -> Stdlib.compare y0 y1
        | c -> c
end
module PairsMap = Map.Make(IntPairs)
let m = PairsMap.(empty |> add (0,1) "hello" |> add (1,0) "world")
(* not an expression, not usable in %ocaml magic *)
Explanation: From standard library
What about Sets, mapped to set?
What about HashTbl, mapped to dict?
And Stack, Queue, etc?
TODO: left as an exercise for the reader.
Map - fail
End of explanation
stack = %ocaml Stack.create()
Explanation: Stack (or any module using a custom type) - fail
End of explanation
def product3values(x, y, z):
    return x * y * z
Explanation: 😮 Curryed functions!
Imagine you define this function in math:
$p : (x,y,z) \mapsto x * y * z$, on $\mathbb{N}^3 \to \mathbb{N}$.
Then the Curryed form states that it is equivalent to
$p' : x \mapsto y \mapsto z \mapsto x * y * z$, informally defined on $\mathbb{N} \to \mathbb{N} \to \mathbb{N} \to \mathbb{N}$.
So for instance if $x=1$ and $y=2$, $p'(x)(y)$ is $z \mapsto 1 * 2 * z$, which is also $z \mapsto p(1, 2, z)$.
In Python function, that would be this function:
End of explanation
x = 1
y = 2
partial_product = product3values(x, y)
z = 10
print(f"With x = {x}, y = {y}, and {partial_product} applied to z = {z}, we got {partial_product(z)}")
Explanation: But you can't directly use it for partial application:
End of explanation
import functools
partial_product = functools.partial(product3values, 1, 2)
z = 10
print(f"With x = {x}, y = {y}, and {partial_product} applied to z = {z}, we got {partial_product(z)}")
Explanation: With the Python standard library, it's possible to use functools.partial to obtain partially evaluated functions, which can be viewed as a limited support of Curryed function.
End of explanation
%%ocaml
(* this is advised *)
let product_curry (x:int) (y:int) (z:int) : int = x * y * z in
let x = 1 and y = 2 in
let partial_product = product_curry x y in
let z = 10 in
Format.printf "With x = %i, y = %i, and partial_product applied to z = %i, we got %i." x y z (partial_product z);;
Explanation: But in OCaml, the conventions is to directly write functions in Curry form, rather than tuple form:
End of explanation
%%ocaml
(* this is NOT advised *)
let product_curry (xyz : (int * int * int)) : int =
    let x, y, z = xyz in
    x * y * z
in
let x = 1 and y = 2 in
let partial_product = product_curry x y in
let z = 10 in
Format.printf "With x = %i, y = %i, and partial_product applied to z = %i, we got %i." x y z (partial_product z);;
Explanation: Indeed, in most situations, the tuple form is just not "OCaml"esque, and tedious to use, and does not allow partial application!
End of explanation
product_curry = %ocaml let product_curry (x:int) (y:int) (z:int) : int = x * y * z in product_curry
Explanation: Well that was some long explanation, but now comes the magic!
If you use %ocaml to get in Python the values returned from OCaml, then functions are Curryed function!
End of explanation
help(product_curry)
Explanation: The only information we have on this function is the OCaml signature, in its docstring:
End of explanation
product_curry(1, 2, 10)
Explanation: So we can't use it as a classical 3-arguments Python function:
End of explanation
product_curry(1)(2)(10)
Explanation: But we CAN use it as a Curryed function!
End of explanation
partial_product_1 = product_curry(1)
partial_product_1(2)(10)
partial_product_2 = product_curry(1)(2)
partial_product_2_too = partial_product_1(2)
partial_product_2(10), partial_product_2_too(10)
Explanation: Which is awesome because now we can do partial evaluation as in OCaml!
End of explanation
help(partial_product_1)
help(partial_product_2)
help(partial_product_2_too)
Explanation: What's very cool is that these functions docstrings keep showing the signature of the underlying OCaml function, even if they were obtained from pure Python cells!
End of explanation
%ocaml let x = 1 in x
%ocaml x
Explanation: That's it for this feature, it's cool and interesting.
Some questions
Can we share variables between two consecutive full cells?
In the %ocaml mode, nothing can be shared from the OCaml side, as it's just an expression, let's check:
End of explanation
%%ocaml
(* See https://en.wikipedia.org/wiki/42_(number) *)
let answer_to_life = 42 in
Format.printf "\n... « The answer to life, the universe, and everything is %i »%!" answer_to_life;;
%%ocaml
Format.printf "\n... « The answer to life, the universe, and everything is %i »%!" answer_to_life;;
Explanation: But what about full cell mode, %%ocaml?
End of explanation
?%ocaml
Explanation: ==> Answer: no, we cannot share any memory between two consecutive cells.
Well, too bad, but it's not so important.
Is there any documentation of the magic or commands?
No.
End of explanation
"opttoploop" in dir(ocaml)
Explanation: Docstring: &lt;no docstring&gt;
File:      /usr/local/lib/python3.6/dist-packages/ocaml/__init__.py
More remarks
Note that there blog post says that using the opttoploop could be used to compile the OCaml to a faster version (native code), but do not document about this.
Note that with the toploop module, the OCaml code is evaluated by compiling to bytecode which is not optimal, switching to the opttoploop module that generates native code should make it even faster.
End of explanation
# it doesn't have a docstring, don't try help(<...>) or <...>?
ocaml.ocaml.example_module.approx_pi
ocaml.ocaml.example_module.approx_pi(1000000)
Explanation: Also note that the ocaml module is shipped with an example of a tiny module which was written in OCaml and compiled, being made available to Python directly:
End of explanation
import ocaml
import numpy as np
python_sum = sum
ocaml_sum = %ocaml List.fold_left (+.) 0.
numpy_sum = np.sum
print(python_sum( [1.0, 2.0, 3.0, 4.0, 5.0] ))
print(ocaml_sum(  [1.0, 2.0, 3.0, 4.0, 5.0] ))
print(numpy_sum(  [1.0, 2.0, 3.0, 4.0, 5.0] ))
Explanation: Final note: a tiny benchmark
Let's compare the speed of naive Python and naive OCaml sum of a list/array of floats, for various input size.
End of explanation
sizes = [100, 1000, 10000, 100000, 1000000, 10000000]
print(f"Comparing time of python_sum and ocaml_sun :")
for size in sizes:
    print(f"\n- For size = {size}:")
    X = list(np.random.randn(size))
    
    print("\tFor python sum: ", end='')
    %timeit python_sum(X)
    
    assert np.isclose(python_sum(X), ocaml_sum(X))
    print("\tFor OCaml sum: ", end='')
    %timeit ocaml_sum(X)
    assert np.isclose(python_sum(X), numpy_sum(X))
    print("\tFor numpy.sum: ", end='')
    %timeit numpy_sum(X)
Explanation: Now for a "large" array, let's use IPython %timeit magic for very quick benchmarking.
Science is about making hypotheses, designing experiments to check them, and conclude.
My hypothesis here is that the OCaml version will be between 10 to 50 slower than the Python one (and Numpy version is 50-200 faster than Python).
End of explanation
import matplotlib.pyplot as plt
µs = 1
ms = 1000*µs
s  = 1000*ms
X = sizes
# TODO: get this automatically?
    
Y_python = [ 7.27*µs, 72.1*µs, 786*µs, 7.55*ms, 68.2*ms, 677*ms ]
Y_ocaml  = [ 16*µs, 157*µs, 1.8*ms, 24.2*ms, 286*ms, 2.92*s ]
Y_numpy  = [ 12*µs, 67.7*µs, 615*µs, 6.25*ms, 62.6*ms, 632*ms ]
fig = plt.figure(figsize=(14, 10), dpi=300)
plt.loglog(X, Y_python, color="blue", marker="o", label="naive Python", lw=4, ms=15)
plt.loglog(X, Y_ocaml,  color="green", marker="d", label="using OCaml", lw=4, ms=15)
plt.loglog(X, Y_numpy,  color="orange", marker="s", label="using Numpy", lw=4, ms=15)
plt.ylabel("Time in micro-seconds")
plt.xlabel("Size of input list")
plt.legend()
plt.title("Tiny benchmark comparing OCaml binding to Python")
plt.show()
Explanation: Well that's better than what I expected!
It seems that the overhead is constant and not increasing when the size of the input is increasing!
It means that if the Python code runs in time $T_1(n)$ for inputs of size $n$, then then OCaml binding code runs in less than $T_2(n) \leq \alpha T_1(n) + \beta$, with two constants $\alpha, \beta$.
End of explanation
np.polyfit(Y_python, Y_ocaml, deg=1)
Explanation: Just to check the experimental values of $\alpha$ and $\beta$ in my claim above, let's use numpy.polyfit function:
End of explanation
<END_TASK>