Langages de Programmation, 22 mars 98.
  1. Quelle est la différence entre le scoping statique et dynamique? Donner un exemple d'un programme Lisp dont l'exécution serait différente si le scoping était statique.

    Le soping, c.-à-d. porté et visibilité d'objets, est statique s'il dépend de la structure syntaxique du programme (par exemple une variable n'est pas visible à l'extérieur du bloc où elle est déclarée).

    Le scoping est dynamique si la signification d'un identificateur dépend du flot d'exécution. Dans ce cas une occurrence d'une variable peut référer aux deux (ou plus) déclarations différentes.

    Programme Lisp dont l'exécution serait différente si le scoping était statique:

      (setq x 100)
      (defun f (y) (+ x y))
      (defun g (x) (f x))
      (g 10)
    
    En Lisp, le résultat de (g 10) est ``20''. Si le scoping statique était utilisé, le resultat serait ``110''.

  2. Programmer en Lisp les fonctions suivantes:
    1. enlever - fonction qui enlève d'une liste d'atomes toutes les occurrences d'un élément donné.

      Réponse:

      (defun enlever (e l)
        (cond
         ((null l) l)
         ((eq e (car l)) (enlever e (cdr l)))
         (t (cons (car l) (enlever e (cdr l))))
      ))
      

    2. enlever-rep - fonction qui transforme une liste d'atomes (avec des répétitions) en enlevant toutes les répétitions.

      Réponse:

      (defun enlever-rep (l) 
        (if l (cons (car l) (enlever-rep (enlever (car l) (cdr l))))))
      

    3. n-max - fonction qui recherche le n-ème plus grand élément dans une liste d'entiers.

      Réponse:

      (defun n-max (n l)
        (cond
         ((null l) nil)
         ((eq n 1) (max l))
         (t (n-max (- n 1) (enlever (max l) l)))))
      (defun max (l)
        (cond
         ((null (cdr l)) (car l))
         (( > (car l) (max (cdr l))) (car l))
         (t (max (cdr l)))))
      
  3. Calculer les types (et évaluer si possible) des expressions ML suivantes:
    1. function x -> x;;

      Réponse:

      - : 'a - > 'a =  <fun >
      

    2. function x -> function y -> if (x = y) then x else y;;

      Réponse:

      - : 'a - > 'a - > 'a =  <fun >
      

    3. function (f,g) ->
      function x -> if (f(x)) then g(x) else f(g(x));;

      Réponse:

      - : (bool - > bool) * (bool - > bool) - > bool - > bool =  <fun >
      

    4. let f = (prefix +) 2 in f(3);;

      Réponse:

      - : int = 5
      
  4. Trouver des expressions ML dont les types sont:

    1. int * int

      Réponse: (2,3) ;;

    2. 'a -> bool

      Réponse: function x -> true;;

    3. bool -> bool * bool

      Réponse: function x -> if x then (x,x) else (x, true);;

    4. ((int -> int) -> int) -> int

      Réponse: function x -> x (function x -> x + 1) + 1;;


File converted from TEX by TTH, version 0.8.