Département d'Informatique
Licence Informatique 2001-2002
Programmation Fonctionnelle
12 novembre



Introduction au λ-calcul
(où l'on se familiarise avec la syntaxe et la réduction des λ-expressions)



I   Syntaxe

Pour chacune des λ-expressions suivantes :
  1. Déterminer s'il s'agit d'un terme, d'une abstraction ou d'une application, et faire de même pour toutes les sous-expressions.
  2. Indiquer s'il est possible d'en donner une interprétation simple en terme de fonction. Si oui, laquelle ?
  3. Oter les parenthèses inutiles, puis parenthèser complètement.
    1. λ x . (x   3)

    2. λ x . (λ y . (+   x   3))

    3. λ x . λ y . λ z . ((*   (+   3   x)   y)   z)   5   π
    4. λ f . (*   (+   3   2)   5)
    5. λ a . (a   λ b . (b   a))
    6. λ x . λ y . λ z . ((z   x)   (z   y))
    7. (λ f . λ g . (λ h . (g   h)   f)   λ p . λ q . p)
    8. λ e . λ i . λ o . λ u . (u   (o   (i   e)))
    9. (λ p . (λ q . p   λ x . (x   p))   λ i . λ j . (j   i))

II   Réduction

  1. Réduire les λ-expressions suivantes en utilisant la b-conversion généralisée:

    1. λ a . λ b . (+   a   b)   5

    2. λ x. (+   x   x)   (λ y . y   z)

    3. λ c . λ v . λ f . ((c   v)   f)  λ x . λ y . x

    4. (λ x . λ y . (y   x)   λ p . λ q . p)   λ i . i

    5. ((λ x . λ y . λ z . ((x   y)   z)   λ f . λ a . (f   a))   λ i . i)   λ j . j

    6. λ h .((λ a . λ f. (f   a)   h)   h)   λ g . (g   g)

    7. (λ p . λ q . (p   q)   (λ x . x   λ a . λ b . a))   λ k . k

    8. ((λ f. λ g .λ x .(f   (g   x))   λ s . (s   s))   λ a . λ b . b)   λ x . λ y . x

    9. λ n . λ f . λ x . (f   (n   f  x))   λ f . λ x . (f   x)

  2. On donne les noms ID (identity), AP (apply) et APS (self-apply) aux λ-expressions, respectivement, λ x . x, λ f . λ a . (f   a) et λ s . (s   s). Réduire les λ-expressions suivantes:

    1. AP   f   a

    2. AP   a   f

    3. AP   ID   ID

    4. APS   ID

    5. APS   APS
This document was translated from LATEX by HEVEA.