{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": "true" }, "source": [ "# Table of Contents\n", "

1  Exemple de notebook dans un autre langage interprété : OCaml
1.1  Une faiblesse d'OCaml ?
1.2  Notebooks Jupyter pour le langage OCaml
1.2.1  Un premier petit exemple : fonction factorielle
1.3  Mesure du temps d'exécution
1.4  Exemple : solveur de Sudoku en OCaml
1.5  Conclusion pour ce notebook
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Exemple de notebook dans un autre langage interprété : OCaml\n", "\n", "OCaml (https://www.ocaml.org/) est un langage de programmation fonctionnelle, statiquement typé, qui peut être utilisé en mode interprété (comme Python) ou compilé.\n", "Conçus par des chercheurs de l'INRIA, hériter de CAML puis caml_light, le langage utilisé pour l'enseignement de l'option informatique en classes préparatoires MPSI et MP en France.\n", "\n", "OCaml, et les langages fonctionnels en général, n'est pas un langage très populaire dans le monde, en comparaison de C/C++, Java, PHP, Python et Javascript (les cinq plus populaires), mais il a des avantages, et reste très utilisé pour l'enseignement de l'informatique théorique en France.\n", "\n", "> Liens :\n", "> - http://caml.inria.fr/ et https://www.ocaml.org/ sont les sites officiels du langage,\n", "> - http://try.ocamlpro.com/ pour essayer le langage depuis un navigateur,\n", "> - Par exemple http://www.janestreet.com/ est un groupe de trading, qui est connu pour utiliser des applications codées en OCaml,\n", "> - Un autre exemple, Facebook utilise OCaml pour ses outils d'analyse statique de code, comme [flow](https://github.com/facebook/flow) et [infer](https://github.com/facebook/infer), et pour son environnement [Reason](https://github.com/facebook/reason)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Une faiblesse d'OCaml ?\n", "OCaml est connu pour manquer d'environnement de développement moderne et \"séduisant\", et la plupart des enseigants utilisent Emacs et son mode Tuareg pour Caml/OCaml, qui manque de modernité.\n", "\n", "Les élèves habitués à des logiciels très modernes, faciles d'accès et très visuels, se retrouvent confrontés à un logiciel qui n'a guère évolué depuis les années 1980.\n", "\n", "Mon expérience montre que mêmes des élèves de niveau master, préparant l'agrégation de mathématiques option informatique à l'ENS de Rennes, ont un peu de mal à prendre correctement en main le logiciel Emacs et son mode Tuareg.\n", "A l'opposé, j'ai vu des élèves de première et deuxième années de prépa (MPSI et PSI) maîtriser très bien l'environnement Jupyter, qu'ils avaient appris à utiliser pour l'oral \"maths avec Python\" du concours CentraleSupélec.\n", "\n", "> Liens :\n", "> - https://opam.ocaml.org/packages/tuareg/\n", "> - https://pro.yannsalmon.fr/ide#opam_ocaml_emacs_tuareg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Notebooks Jupyter pour le langage OCaml\n", "Utiliser des notebooks Jupyter avec le *kernel* `ocaml-jupyter` (https://github.com/akabe/ocaml-jupyter) est une très bonne solution pour montrer du code, des commentaires, et les résultats d'évaluation des morceaux de code, pour des cours, TD ou TP d'informatique avec OCaml." ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val entier : int = 0\n", "val flottant : float = 1.\n", "val chaine : string = \"Superman\"\n", "val fonction : int -> int -> int = \n" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let entier = 0\n", "and flottant = 1.0\n", "and chaine = \"Superman\"\n", "and fonction = fun x -> fun y -> x + y\n", ";;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme pour Python, chaque cellule contient du texte (en Markdown), ou du code, et sa sortie une fois exécuté.\n", "Il est très facile d'écrire des sujets de TP ou d'examen, qui mélangent tous ces contenus, grâce à Jupyter.\n", "\n", "Les documents écrits avec Jupyter peuvent ensuite être convertis en PDF, en HTML, ou d'autres formats." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un premier petit exemple : fonction factorielle\n", "\n", "Exécuter une cellule donne la signature des objets définis dans la cellule, i.e., leurs valeurs et/ou leurs types.\n", "\n", "Par exemple, si on définit `fact(n) = n!` avec $n! = 1 \\times 2 \\times \\dots \\times n$, `fact : int -> int` est la signature de la fonction `fact`." ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val fact : int -> int = \n" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec fact = function\n", "| 0 -> 1\n", "| 1 -> 1\n", "| n -> n * (fact (n-1))\n", ";;" ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "fact(0) = 1\n", "fact(1) = 1\n", "fact(2) = 2\n", "fact(3) = 6\n", "fact(4) = 24\n", "fact(5) = 120\n", "fact(6) = 720\n", "fact(7) = 5040\n", "fact(8) = 40320\n", "fact(9) = 362880\n", "fact(10) = 3628800\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 61, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i = 0 to 10 do\n", " Printf.printf \"fact(%i) = %i\\n\" i (fact i);\n", "done;\n", "flush_all();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et par exemple pour la fonction calculant les termes positifs de la suite de Fibonacci :" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val fibo : int -> int = \n" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let rec fibo = function\n", "| 0 -> 1\n", "| 1 -> 1\n", "| n -> (fibo (n-1)) + (fibo (n-2))\n", ";;" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "fibo(10) = 89\n", "fibo(11) = 144\n", "fibo(12) = 233\n", "fibo(13) = 377\n", "fibo(14) = 610\n", "fibo(15) = 987\n", "fibo(16) = 1597\n", "fibo(17) = 2584\n", "fibo(18) = 4181\n", "fibo(19) = 6765\n", "fibo(20) = 10946\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for i = 10 to 20 do\n", " Printf.printf \"fibo(%i) = %i\\n\" i (fibo i);\n", "done;\n", "flush_all();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mesure du temps d'exécution" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val timeit : ('a -> 'b) -> 'a -> unit -> 'b = \n" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let timeit f x () =\n", " let debut = Sys.time () in\n", " let resultat = f x in\n", " let fin = Sys.time () in\n", " Printf.printf \"Calcul effectué en %.3g secondes.\\n\" (fin -. debut);\n", " flush_all();\n", " resultat\n", ";;" ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Calcul effectué en 0.276 secondes.\n" ] }, { "data": { "text/plain": [ "- : int = 9227465\n" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit fibo 34 ();;" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Calcul effectué en 0.712 secondes.\n" ] }, { "data": { "text/plain": [ "- : int = 24157817\n" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit fibo 36 ();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme avec Python, on peut utiliser `Tab` pour afficher de l'aide sur les fonctions de la librairie standard du langage (de l'introspection).\n", "C'est très pratique :\n", "![figs/introspection_in_ocaml.png](figs/introspection_in_ocaml.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exemple : solveur de Sudoku en OCaml\n", "\n", "Pour illustrer l'utilisation de ce langage, voyons un exemple issu du tutoriel officiel (https://ocaml.org/learn/tutorials/99problems.html#97-Sudoku-medium) : un solveur de Sudoku." ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "module Board :\n", " sig\n", " type t = int array\n", " val is_valid : int -> bool\n", " val get : t -> int * int -> int\n", " val get_as_string : t -> int * int -> string\n", " val with_val : t -> int * int -> int -> int array\n", " val of_list : int list list -> t\n", " val print : t -> unit\n", " val available : t -> int * int -> int list\n", " val next : int * int -> int * int\n", " val fill : t -> int * int -> t option\n", " val try_values : t -> int * int -> int list -> t option\n", " end\n" ] }, "execution_count": 65, "metadata": {}, "output_type": "execute_result" } ], "source": [ "open Printf\n", " \n", "module Board = struct\n", " type t = int array (* 9×9, row-major representation. A value of 0\n", " means undecided. *)\n", "\n", " let is_valid c = c >= 1;;\n", "\n", " let get (b: t) (x, y) = b.(x + y * 9);;\n", "\n", " let get_as_string (b: t) pos =\n", " let i = get b pos in\n", " if is_valid i then string_of_int i else \".\";;\n", "\n", " let with_val (b: t) (x, y) v =\n", " let b = Array.copy b in\n", " b.(x + y * 9) <- v;\n", " b;;\n", "\n", " let of_list l : t =\n", " let b = Array.make 81 0 in\n", " List.iteri (fun y r -> List.iteri (fun x e ->\n", " b.(x + y * 9) <- if e >= 0 && e <= 9 then e else 0) r) l;\n", " b;;\n", "\n", " let print b =\n", " for y = 0 to 8 do\n", " for x = 0 to 8 do\n", " printf (if x = 0 then \"%s\" else if x mod 3 = 0 then \" | %s\"\n", " else \" %s\") (get_as_string b (x, y))\n", " done;\n", " if y < 8 then\n", " if y mod 3 = 2 then printf \"\\n--------+---------+--------\\n\"\n", " else printf \"\\n | | \\n\"\n", " else printf \"\\n\"\n", " done;\n", " flush_all();;\n", "\n", " let available b (x, y) =\n", " let avail = Array.make 10 true in\n", " for i = 0 to 8 do\n", " avail.(get b (x, i)) <- false;\n", " avail.(get b (i, y)) <- false;\n", " done;\n", " let sq_x = x - x mod 3 and sq_y = y - y mod 3 in\n", " for x = sq_x to sq_x + 2 do\n", " for y = sq_y to sq_y + 2 do\n", " avail.(get b (x, y)) <- false;\n", " done;\n", " done;\n", " let av = ref [] in\n", " for i = 1 (* not 0 *) to 9 do if avail.(i) then av := i :: !av done;\n", " !av;;\n", "\n", " let next (x,y) = if x < 8 then (x+1, y) else (0, y+1);;\n", "\n", " (** Try to fill the undecided entries. *)\n", " let rec fill b ((_,y) as pos) =\n", " if y > 8 then Some b (* filled all entries *)\n", " else if is_valid(get b pos) then fill b (next pos)\n", " else match available b pos with\n", " | [] -> None (* no solution *)\n", " | l -> try_values b pos l\n", " and try_values b pos = function\n", " | v :: l ->\n", " (match fill (with_val b pos v) (next pos) with\n", " | Some _ as res -> res\n", " | None -> try_values b pos l)\n", " | [] -> None\n", " ;;\n", "end" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val sudoku : Board.t -> Board.t = \n" ] }, "execution_count": 66, "metadata": {}, "output_type": "execute_result" } ], "source": [ "let sudoku b = match Board.fill b (0,0) with\n", " | Some b -> b\n", " | None -> failwith \"sudoku: no solution\";;" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "val initial_board : Board.t =\n", " [|0; 0; 4; 8; 0; 0; 0; 1; 7; 6; 7; 0; 9; 0; 0; 0; 0; 0; 5; 0; 8; 0; 3; 0;\n", " 0; 0; 4; 3; 0; 0; 7; 4; 0; 1; 0; 0; 0; 6; 9; 0; 0; 0; 7; 8; 0; 0; 0; 1;\n", " 0; 6; 9; 0; 0; 5; 1; 0; 0; 0; 8; 0; 3; 0; 6; 0; 0; 0; 0; 0; 6; 0; 9; 1;\n", " 2; 4; 0; 0; 0; 1; 5; 0; 0|]\n" ] }, "execution_count": 67, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(* The board representation is not imposed. Here \"0\" stands for \".\" *)\n", " let initial_board =\n", " Board.of_list [[0; 0; 4; 8; 0; 0; 0; 1; 7];\n", " [6; 7; 0; 9; 0; 0; 0; 0; 0];\n", " [5; 0; 8; 0; 3; 0; 0; 0; 4];\n", " [3; 0; 0; 7; 4; 0; 1; 0; 0];\n", " [0; 6; 9; 0; 0; 0; 7; 8; 0];\n", " [0; 0; 1; 0; 6; 9; 0; 0; 5];\n", " [1; 0; 0; 0; 8; 0; 3; 0; 6];\n", " [0; 0; 0; 0; 0; 6; 0; 9; 1];\n", " [2; 4; 0; 0; 0; 1; 5; 0; 0]];;" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ ". . 4 | 8 . . | . 1 7\n", " | | \n", "6 7 . | 9 . . | . . .\n", " | | \n", "5 . 8 | . 3 . | . . 4\n", "--------+---------+--------\n", "3 . . | 7 4 . | 1 . .\n", " | | \n", ". 6 9 | . . . | 7 8 .\n", " | | \n", ". . 1 | . 6 9 | . . 5\n", "--------+---------+--------\n", "1 . . | . 8 . | 3 . 6\n", " | | \n", ". . . | . . 6 | . 9 1\n", " | | \n", "2 4 . | . . 1 | 5 . .\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 68, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Board.print initial_board;;" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "9 3 4 | 8 2 5 | 6 1 7\n", " | | \n", "6 7 2 | 9 1 4 | 8 5 3\n", " | | \n", "5 1 8 | 6 3 7 | 9 2 4\n", "--------+---------+--------\n", "3 2 5 | 7 4 8 | 1 6 9\n", " | | \n", "4 6 9 | 1 5 3 | 7 8 2\n", " | | \n", "7 8 1 | 2 6 9 | 4 3 5\n", "--------+---------+--------\n", "1 9 7 | 5 8 2 | 3 4 6\n", " | | \n", "8 5 3 | 4 7 6 | 2 9 1\n", " | | \n", "2 4 6 | 3 9 1 | 5 7 8\n" ] }, { "data": { "text/plain": [ "- : unit = ()\n" ] }, "execution_count": 69, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Board.print (sudoku initial_board);;" ] }, { "cell_type": "code", "execution_count": 87, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Calcul effectué en 0.000219 secondes.\n" ] }, { "data": { "text/plain": [ "- : Board.t =\n", "[|9; 3; 4; 8; 2; 5; 6; 1; 7; 6; 7; 2; 9; 1; 4; 8; 5; 3; 5; 1; 8; 6; 3; 7; 9;\n", " 2; 4; 3; 2; 5; 7; 4; 8; 1; 6; 9; 4; 6; 9; 1; 5; 3; 7; 8; 2; 7; 8; 1; 2; 6;\n", " 9; 4; 3; 5; 1; 9; 7; 5; 8; 2; 3; 4; 6; 8; 5; 3; 4; 7; 6; 2; 9; 1; 2; 4; 6;\n", " 3; 9; 1; 5; 7; 8|]\n" ] }, "execution_count": 87, "metadata": {}, "output_type": "execute_result" } ], "source": [ "timeit sudoku initial_board ();;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conclusion pour ce notebook\n", "\n", "Ce petit notebook montre que la même technologie (les notebooks Jupyter) peut être utilisée pour d'autres langages que Python.\n", "\n", "Une très longue liste de *kernel* existe, avec notamment :\n", "\n", "- https://github.com/jupyter-xeus/xeus-cling pour C++\n", "- https://github.com/JuliaLang/IJulia.jl pour Julia\n", "- https://github.com/jupyter/jupyter/wiki/Jupyter-kernels et https://jupyter.readthedocs.io/en/latest/projects/kernels.html pour la liste des kernels qui existent." ] } ], "metadata": { "kernelspec": { "display_name": "OCaml 4.04.2", "language": "OCaml", "name": "ocaml-jupyter" }, "language_info": { "codemirror_mode": "text/x-ocaml", "file_extension": ".ml", "mimetype": "text/x-ocaml", "name": "OCaml", "nbconverter_exporter": null, "pygments_lexer": "OCaml", "version": "4.04.2" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "184.117px", "width": "251.667px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "threshold": 4, "toc_cell": true, "toc_position": { "height": "685.317px", "left": "0px", "right": "1272.18px", "top": "121.683px", "width": "327.817px" }, "toc_section_display": "block", "toc_window_display": true }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }