examples.ml 13.4 KB
Newer Older
1

2
3
4
let examples = [ "xml","(* Syntax for XML elements *)

type A = <a x=String y=?String>[ B* ]
5
6
7
8
9
10
11
12
13
type B = <b>[ PCDATA A? PCDATA ]

let x : A = 
 <a x=\"Bla\" y=\"Blo\">[ 
   <b>[ 'blabla' ]
   <b>[ 
     <a x=\"Foo\">[] 'bla' 'bla' 
   ] 
 ]
14
";"functions","(* Simple functions can be defined this way: *)
15
16
17
let f1 (x : Int) : Int = x + 3
;;
f1 5
18
19

(* With several arguments: *)
20
21
22
let f2 (x : Int, y : Int) : Int = x + y
;;
f2 (10,20)
23

24
25
26
27
28
(* Currified form *)
let add (x : Int) (y : Int) : Int = x + y
;;
add 10 20

29
(* You may directly deconstruct the arguments: *)
30
31
32
type A = <a href=String>String
let f3 (<a href=url>txt : A) : String = url @ \"=>\" @ txt
;;
33
34
35
36
37
38
f3 <a href=\"http://www.cduce.org\">\"CDuce homepage\";;

(* In general, if you want to specify several arrow types, or
   use several pattern matching branches, you have the general
   form: *)

39
let f4 (A -> String; ['0'--'9'+] -> Int)
40
| x & A -> f3 x
41
42
43
| x -> int_of x
;;
f4 \"123\"
44
";"mutrec","(* Adjacent type declarations are mutually recursive *)
45
46
47
type T = <t>S
type S = [ (Char | T)* ]
let x : S = [ 'abc' <t>['def'] 'ghi' ]
48

49
(* Similarly for toplevel function definitions *)
50

51
52
53
54
let f (x : Int) : Int = g x
let g (x : Int) : Int = 3
let a = 2
let h (x : Int) : Int = f x
55
   (* f and g are mutually recursive, but they cannot use h *)
56
";"sequence","(* Sequence are just defined with pairs and the atom `nil;
57
   the following notation are equivalent: *)
58
59
60
let l1 = (1,2,3,`nil)
let l2 = (1,(2,(3,`nil)))
let l3 = [ 1 2 3 ]
61
62

(* The [...] notation allow to specify a tail after a semi-colon : *)
63
64
let l4 = (10,20,l1)
let l5 = [ 10 20 ; l1 ]
65
66

(* Concatenation @ *)
67
let l6 = [ 1 2 3 ] @ [ 4 5 6 ]
68
69

(* Inside [...], it is possible to escape a subsequence with a ! *)
70
let l7 = [ 1 2 !l6 !l1 5 ]
71
";"seqtypes","(* Sequence types are defined with regular expression over types *)
72
73
74
type IntList = [ Int* ]
type IntStringList = [ (Int String)* ]
type IntNonEmptyList = [ Int+ ]
75

76
let l : IntList = [ 1 2 3 ]
77
";"integers","(* Yes, CDuce can handle large integers! *)
78
let facto (Int -> Int)
79
80
81
 | 0 | 1 -> 1
 | n -> n * (facto (n - 1))
in
82
facto 300
83
84

(* The tail-recursive way *)
85
let facto ((Int,Int) -> Int)
86
87
88
 | (x, 0 | 1) -> x
 | (x, n) -> facto (x * n, n - 1)
in
89
facto (1,10000)
90
";"sumtype","type Expr = 
91
92
93
94
    (`add, Expr, Expr)
  | (`mul, Expr, Expr)
  | (`sub, Expr, Expr)
  | (`div, Expr, Expr)
95
  | Int
96
 
97
let eval ( Expr -> Int )  
98
99
100
  | (`add,x,y) -> eval x + eval y
  | (`mul,x,y) -> eval x * eval y
  | (`sub,x,y) -> eval x - eval y
101
  | (`div,x,y) -> (eval x) div (eval y)
102
103
  | n -> n 
in
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
eval (`add, 10, (`mul, 20, 5))
";"ovfun","type Person = FPerson | MPerson 
type FPerson = <person gender = \"F\" >[ Name Children (Tel | Email)?] 
type MPerson = <person gender=\"M\">[ Name Children (Tel | Email)?] 
type Children = <children>[Person*] 
type Name = <name>[ PCDATA ]
type Tel = <tel kind=?\"home\"|\"work\">['0'--'9'+ '-' '0'--'9'+]
type Email = <email>[PCDATA '@' PCDATA]

type Man = <man name=String>[ Sons Daughters ]
type Woman = <woman name=String>[ Sons Daughters ]
type Sons = <sons>[ Man* ]
type Daughters = <daughters>[ Woman* ]

let split (MPerson -> Man ; FPerson -> Woman)
  <person gender=g>[ <name>n <children>[(mc::MPerson | fc::FPerson)*]; _] ->
     let tag = match g with \"F\" -> `woman | \"M\" -> `man in
     let s = map mc with x -> split x in
     let d = map fc with x -> split x in
     <(tag) name=n>[ <sons>s  <daughters>d ] 
 
125
126

let base : Person = 
127
128
<person gender=\"F\">[ 
  <name>\"Themis\"
129
  <children>[ 
130
131
    <person gender=\"M\">[
      <name>\"Prometheus\"
132
      <children>[
133
134
135
136
137
138
139
140
141
142
143
        <person gender=\"M\">[
          <name>\"Deucalion\"
          <children>[]
        ]
      ]
      <email>\"focifero@olympus.com\"
    ] 
    <person gender=\"M\">[
      <name>\"Epimetheus\"
      <children>[]
      <tel> \"314-1592654\"
144
145
146
147
    ]
  ] 
  <tel kind=\"home\"> \"271-828182\"
]
148
149
150
151
152
153
in
split base
";"note","type Doc = <doc>Text
type Text = [ (Char | (Letter+ ' '* Note))* ]
type Letter = 'a'--'z' | 'A'--'Z'
type Note = <note>[ PCDATA ]
154

155
156
157
type Flow = [ (Char | <ref no=Int>[ PCDATA ])* ]
type Notes = [ <note no=Int>[ PCDATA ]* ]
type Result = <doc>[ <body>Flow <notes>Notes ]
158

159
let format (<doc>s : Doc) : Result = 
160
  let (body,notes) = text (s,1) in
161
  <doc>[ <body>body <notes>notes ]
162

163
let text ( (Text,Int) -> (Flow,Notes) )
164
165
166
167
 | ([ pre::Char*? (word::Letter+ ' '* <note>n); rem ], count) ->
      let (body,notes) = text (rem, count + 1) in
      (pre @ [<ref no=count>word] @ body, 
       [<note no=count>n] @ notes)
168
 | (body,_) -> (body, [])
169
170
171

let src : Doc = <doc>[ 'CDuce ' <note>\"Frisch, Castagna, Benzaken\"
		 ' is an XML ' <note>\"a W3C standard\"
172
173
174
175
176
177
178
179
180
181
		 '-friendly programming language.' ]
in
format src
";"biblio","type Biblio  = <bibliography>[Heading Paper*]
type Heading = <heading>[ PCDATA ]
type Paper   = <paper>[ Author+ Title Conference File ]
type Author  = <author>[ PCDATA ]
type Title   = <title>[ PCDATA ]
type Conference = <conference>[ PCDATA ]
type File    = <file>[ PCDATA ]
182
183

(* Simplified HTML *)
184
type Html  = <html>[ <head>[ <title>[ PCDATA ] ]  <body>Mix ]
185
type Mix   = [ ( <h1>Mix | <a href=String>Mix | <p>Mix | <em>Mix 
186
	       | <ul>[ <li>Mix +] | Char )* ]
187

188
let do_authors ([Author+] -> Mix)
189
190
 | [ <author>a ] -> a
 | [ <author>a <author>b ] -> a @ \" and, \" @ b
191
 | [ <author>a; x] -> a @ \", \" @ (do_authors x)
192

193
let do_paper (Paper -> <li>Mix)
194
  <paper>[ x::_* <title>t <conference>c <file>f ] ->
195
    <li>[ <a href=f>t !(do_authors x) '; in ' <em>c '.' ]
196

197
let do_biblio (Biblio -> Html)
198
199
200
201
202
  <bibliography>[ <heading>h; p ] ->
      let body = match p with
      | [] -> \"Empty bibliography\"
      | l -> [ <h1>h <ul>(map l with x -> do_paper x) ]
      in    
203
      <html>[ <head>[ <title>h ] <body>body ]
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

let bib : Biblio = 
  <bibliography>[
    <heading>\"Alain Frisch's bibliography\"
    <paper>[
      <author>\"Alain Frisch\"
      <author>\"Giuseppe Castagna\"
      <author>\"Vronique Benzaken\"
      <title>\"Semantic subtyping\"
      <conference>\"LICS 02\"
      <file>\"semsub.ps.gz\"
    ]
    <paper>[
      <author>\"Mariangiola Dezani-Ciancaglini\"
      <author>\"Alain Frisch\"
      <author>\"Elio Giovannetti\"
      <author>\"Yoko Motohama\"
      <title>\"The Relevance of Semantic Subtyping\"
      <conference>\"ITRS'02\"
      <file>\"itrs02.ps.gz\"
    ]
    <paper>[
      <author>\"Vronique Benzaken\"
      <author>\"Giuseppe Castagna\"
      <author>\"Alain Frisch\"
      <title>\"CDuce: a white-paper\"
      <conference>\"PLANX-02\"
      <file>\"planx.ps.gz\"
    ]
233
234
235
 ]
in
do_biblio bib
236
";"projection","(* The projection  e/t   is translated to:
237
238
   transform e with [ (x::t|_)* ]  -> x *)

239
240
241
242
243
244
245
type Biblio  = <bibliography>[Heading Paper*]
type Heading = <heading>[ PCDATA ]
type Paper   = <paper>[ Author+ Title Conference File ]
type Author  = <author>[ PCDATA ]
type Title   = <title>[ PCDATA ]
type Conference = <conference>[ PCDATA ]
type File    = <file>[ PCDATA ]
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

let bib : Biblio = 
  <bibliography>[
    <heading>\"Alain Frisch's bibliography\"
    <paper>[
      <author>\"Alain Frisch\"
      <author>\"Giuseppe Castagna\"
      <author>\"Vronique Benzaken\"
      <title>\"Semantic subtyping\"
      <conference>\"LICS 02\"
      <file>\"semsub.ps.gz\"
    ]
    <paper>[
      <author>\"Mariangiola Dezani-Ciancaglini\"
      <author>\"Alain Frisch\"
      <author>\"Elio Giovannetti\"
      <author>\"Yoko Motohama\"
      <title>\"The Relevance of Semantic Subtyping\"
      <conference>\"ITRS'02\"
      <file>\"itrs02.ps.gz\"
    ]
    <paper>[
      <author>\"Vronique Benzaken\"
      <author>\"Giuseppe Castagna\"
      <author>\"Alain Frisch\"
      <title>\"CDuce: a white-paper\"
      <conference>\"PLANX-02\"
      <file>\"planx.ps.gz\"
    ]
275
 ]
276

277
278
279
let titles = [bib]/<paper>_/<title>_
let authors = [bib]/<paper>_/<author>_
let titles_concat = [bib]/<paper>_/<title>_/Char
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
";"xtransform","
(* For the purpose of the example we can consider this hugely
   simplified definition of Xhtml
*)

type Flow = Char | Block | Inline  ;;
type Block = P | Heading | Lists | Blocktext | Char
type Lists = Ul
type Blocktext = Pre |  Address | Center;;
type Inline = Char | A | Fontstyle
type Fontstyle = Tt | I | B | Big | Small;;

type Xhtml = <html>[ Head Body ];;
type Head = <head>[ Title <link>[ ]];;
type Title = <title>[ PCDATA ];;
type Body = <body bgcolor=?String>[ Block* ];;

type P = <p>[ Inline* ];;
type Heading = <(`h1 | `h2 | `h3 | `h4)>[ Inline* ];;

type Ul = <ul>[Li+];;
type Li = <li>[ Flow* ];;

type Address = <address>[ Inline* ];;
type Pre = <pre>[ (PCDATA | A | Fontstyle)* ];;
type Center = <center>[ Block* ];;

type A = <a ({ name = String } | { href = String })>[ (Inline \ A)* ];;
type Tt = <tt>[ Inline* ];;
type I = <i>[ Inline* ];;
type B = <b>[ Inline* ];;
type Big = <big>[ Inline* ];;
type Small = <small>[ Inline* ];;


(* xtransform matches the patterns against the root element of each
   XML tree and, if it fails, it recursively applies itself to the
   sequence of sons of the root.

   It can be used to put in boldface all the links of an XHTML
   document as follows
*)

let bold(x:[Xhtml]):[Xhtml]=xtransform x with <a (y)>t -> [ <a(y)>[<b>t] ]


(* let us apply the function to a document where links appear
   at different depths
*)


let doc : Xhtml =
  <html>[
    <head>[<title>\"Example\" <link>[]]
    <body>[
      <h2>['You can have links ' <a href=\"here\">\"here\"]
      <pre>['Or they can be down']
      <ul>[
        <li>['In ' <a name=\"list\">\"lists\" ' for instance']
	<li>['or you oddly decided to ' 
             <center>[<p>[<a href=\"what?\">\"center\"]] 
             ' them '
            ]
      ]
      <address>[
        'and even if they are in fancy ' <a name=\"address\">\"address boxes\"
      ]
      <p>[
          'nevertheless ' <a href=\"http://www.cduce.org\">\"Cduce\" ' and '
          <a href=\"xtransform\">[<tt>\"xtransform\"] 
          ' will put all links in bold so that when'
          ' you program your transformation you '
          <big>[<a name=\"\">\" don\'t \" ] ' have to worry about it'
     ]
   ]
  ];;

bold [doc];;

let [x] = bold [doc] in print_xml x;;
360
361
362
363
364
365
366
367
368
369
";"reference","(* In CDuce the expression  \"ref T exp\" returns a reference  *)
(* to the result of \"exp\" and has type \"ref T\" provided that *)
(* \"exp\" is of type \"T\". References come equipped with three *)
(* operators: \":=\" (assignment), \"!\" (dereferencing), and \";\"*) 
(* (sequencing).                                             *)


let stack = ref [Int*] []

let fun push(x : Int) : []  = 
370
  stack := [x; !stack]
371
372

let fun pop ([] : []) : Int = 
373
  match !stack with [x; y] -> stack := y; x | _ -> raise \"Empty stack\"
374

375
376
377
378
379

(* In a pattern [ ... ; y] the variable y captures the tail  *)
(* of the sequence. It is equivalent to [ ... y::_*].        *)
(* In an expression [ ... ; e ] the expression e denotes the *)
(* tail of the sequence. It is equivalent to [ ... ] @ e     *)
380

381

382
383
384
385
386
387
388
389
390
;;

push 1;;
push 2;;
push 3;;
pop [];;
pop [];;
pop [];;
pop [];;
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
";"pm_compil","(* This example demonstrates the efficient compilation of pattern
   matching. *)

type A = <a>[ Int* ]
type B = <b>[ Char* ]

(* Imagine we want to compile the following function:
   fun ([A+|B+] -> Bool) [A+] -> 0 | [B+] -> 1

   For an arbitrary value, it is expensive to check whether it has
   type [A+] or not. But if we know statically that it has type [A+|B+],
   we just have to check the tag of the first element !

   This is demonstrated by the following internal debugging feature.
   The syntax is:  

   debug compile T P1 ... Pn

   where T is the input type (static information about the matched
   value) and P1,...,Pn are the patterns to compile (simultaneously).

   The \"debug compile\" instruction displays an human-readable
   representation of the automaton corresponding to the pattern
   matching. Note: in actual evaluation, this automaton is build
   lazily (= on-the-fly, = JIT).
*)

debug compile [A+|B+] [A+] [B+]


(* You can see on the output that the pattern matching is actually
   compiled as:

   fun ([A+|B+] -> Int) [ <a>_ ; _ ] -> 0 | _ -> 1
*)
426
"; ]
427
428
429
let present = "<ul><li><a href=\"/cgi-bin/cduce?example=xml\">XML elements.</a> 
XML elements.
</li><li><a href=\"/cgi-bin/cduce?example=functions\">Functions.</a> 
430
Several syntaxes to define functions.
431
</li><li><a href=\"/cgi-bin/cduce?example=mutrec\">Mutual recursion.</a> 
432
Mutual toplevel definition for types and functions.
433
</li><li><a href=\"/cgi-bin/cduce?example=sequence\">Sequence literals.</a> 
434
How to write sequences.
435
</li><li><a href=\"/cgi-bin/cduce?example=seqtypes\">Sequence types.</a> 
436
Types for sequences.
437
</li><li><a href=\"/cgi-bin/cduce?example=integers\">The factorial function.</a> 
438
What about computing 10000! ?
439
</li><li><a href=\"/cgi-bin/cduce?example=sumtype\">Sum types.</a> 
440
How to simulate ML sum types.
441
</li><li><a href=\"/cgi-bin/cduce?example=ovfun\">Overloaded functions.</a> 
442
This examples demonstrates the use of overloaded functions.
443
</li><li><a href=\"/cgi-bin/cduce?example=note\">Footnotes.</a> 
444
 This example shows how to bind an XML element with surrounding text.
445
</li><li><a href=\"/cgi-bin/cduce?example=biblio\">Bibliography.</a> 
446
The good old XML bibliography example.
447
</li><li><a href=\"/cgi-bin/cduce?example=projection\">Projection.</a> 
448
Syntactic sugar for projection.
449
450
</li><li><a href=\"/cgi-bin/cduce?example=xtransform\">Tree transformations.</a> 
How to perform XSLT-like transformations.
451
452
</li><li><a href=\"/cgi-bin/cduce?example=reference\">References.</a> 
Mutable values.
453
454
455
</li><li><a href=\"/cgi-bin/cduce?example=pm_compil\">Compilation of pattern matching.</a> 
This example demonstrates the efficient compilation of pattern
matching.
456
</li></ul>"