S-expression

Une S Expression (ou Expression Symbolique) est une convention pour la représentation de données ou d'expressions d'un programme sous forme textuelle. Les s-expressions sont utilisées dans la famille de langages Lisp, incluant Scheme et DSSSL, ainsi que comme métalangage dans des protocoles de communication tels IMAP ou le langage CBCL (Common Business Communication Language) de John McCarthy. Les détails de la syntaxe et les types de données supportés diffèrent en fonction du langage, mais la propriété la plus commune est l'utilisation de la notation préfixée parenthésée (affectueusement connue sous le nom de Notation polonaise de Cambridge).

[modifier] Rapports avec Lisp

Dans Lisp, les s-expressions sont utilisées à la fois pour le code et les données. Les s-expressions ont été conçues à l'origine comme des représentations machine de M-expressions utilisées par les programmeurs (la syntaxe concrète) ; mais les programmeurs Lisp ont tout de suite utilisé les s-expressions comme notation par défaut.

Les s-expressions peuvent être des objets simples, comme des nombres, des atomes Lisp y compris nil et t, des paires notées (x . y). Des listes peuvent être formées avec des paires, par exemple (1 . (2 . (3 . nil))), qu'on peut écrire également (1 2 3).

Le code de programmes peut donc être écrit en s-expressions, avec la notation préfixée parenthésée.

Exemple en Lisp :

(defun factorial (x)
   (cond 
      ((eq x 1)  1)
      (t (* x (factorial (1- x))))))

Exemple en Scheme:

(define (factorial x)
    (if (= x 1)
        1
        (* x (factorial (- x 1)))))

Il est important de noter que le choix des s-expressions pour la syntaxe de Lisp permet à cette famille de langages de proposer des systèmes de macros puissants permettant d'étendre la sémantique du langage (ajout d'opérateurs spéciaux, analyseurs de code ...) sans toucher à sa spécification ou modifier le compilateur (ou interpréteur). Cela explique que les M-Expressions n'aient jamais été utilisées.

[modifier] Rapports avec XML

Les s-expressions résolvent le même problème qu'XML avec, disent certains, beaucoup plus de légèreté et quarante ans d'avance. Les S-expressions peuvent donc servir de format pour du code (comme en Lisp) mais aussi pour des données. Mais elles ne permettent pas d'étiqueter les différents éléments (contrairement à d'autres concurrents de XML comme JSON ou YAML). Le programme Lisp :

(lambda (x) (* 2 x))

pourrait s'écrire en XML comme suit (d'après http://homepages.inf.ed.ac.uk/wadler/language.pdf):

<?xml version="1.0"?>
<lambda-term>
    <variables-list>
      x
    </variables-list>
   <expr>
       <application>
           <expr><const>*</const></expr>
           <arguments-list>
               <expr><const>2</const></expr>
               <expr>x</expr>
           </arguments-list>
       </application>
   </expr>
</lambda-term>