Codage

Les programmes sont écrits dans un langage de programmation et comme tels se doivent de respecter les usages de ce langage. Le MOOC Programmation récursive utilise Scheme comme langage de programmation (norme IEEE 1178-1990). Ce langage, ayant plus de 35 ans d'existence, successeur de Lisp (Lisp est né en 1958 et est ainsi le second plus ancien langage de programmation de tous les temps après Fortran) et pour lequel de nombreuses conventions existent qu'il faut respecter.

Ce document décrit les conventions qu'il vous est demandé de respecter.

Renfoncement gauche: Les programmes sont présentés avec les bons alignements afin de permettre une lecture et relecture aisées.

Passage à la ligne: pour les expressions figurant dans les formes spéciales if, cond, begin, let, let*, and, or.

Commentaires: les commentaires sont préfixés par des points-virgules dont le nombre indique la portée du commentaire. Trois points-virgules en tête de ligne indiquent un commentaire global. Deux points-virgules qualifient les expressions suivantes (c'est notamment utilisé pour la spécification de fonctions internes). Un point-virgule en fin de ligne qualifie l'expression précédente. Attention un commentaire ne commente pas ce qui est effectué mais pourquoi c'est effectué ainsi!

Blancs et passages à la ligne: Ne pas mettre de blanc entre une parenthèse ouvrante et le premier mot d'une liste. Ne pas passer à la ligne quand on ferme une parenthèse (les parenthèses fermantes ne se lisent pas, on les tape mais on ne les regarde jamais, les renfoncements gauches (ou indentations en jargon) suffisent à appréhender la structure des programmes. Ne pas non plus écrire une définition sur une seule ligne même si la définition est très courte!

Chaque programme sera suivi de ses tests. Ces tests seront exécutables et se présenteront sous la forme d'une expression (verifier fonction ...) où fonction est le nom de la fonction qui est testée. Les tests généraux de bon emploi seront complétés de tests aux limites (sur la liste vide, sur zéro, etc.)

Ce qui suit n'est qu'un exemple!

;;; Exercice 1: la factorielle
;;; fact: int -> nat
;;; (fact n) calcule la factorielle de n.
;;; HYPOTHÈSE: n >= 0

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1))) ) )

;;; Les tests associés à la factorielle.

(verifier fact
  (fact 1) -> 1
  (fact 2) -> 2
  (fact 4) -> 24 )

;;; DIFFICULTÉS RENCONTRÉES
;;; écrire - n et non -n
;;; écrire (- n 1) et non (- 1 n) ni (-1 n)

;;; Exercice 2: l'itérateur map

;;; map: (alpha -> beta) * LISTE[alpha] -> LISTE[beta]
;;; (map f l) rend la liste dont les termes sont les images
;;; par f des termes de la liste l.

(define (map f liste)
  ;; reduce: (alpha * beta -> beta) * beta * LISTE[alpha] -> beta
  ;; reduce(f, fin, l) = f(e1, f(e2, ... f(en, fin) ...)) avec l = (e1 e2 ... en)
  (define (reduce f fin liste)
    (if (pair? liste)
        (f (car liste)                   ; f est binaire
           (reduce f fin (cdr liste)) )
        fin ) )
  ;; composer: alpha * LISTE[beta] -> LISTE[beta]
  ;; (composer e r) ajoute l'image de e par f à r
  (define (composer element resultat)
    (cons (f element) resultat) )
  (reduce composer (list) liste) )

;;; Tests pour map:

;;; identite: alpha -> alpha
;;; la fonction identité
(define (identite x)
  x )

(verifier map
  (map identite '(a b c d)) -> (a b c d))
  (map car '((a 1)(b 2)(c 3)(d 4))) -> (a b c d) )