-
Notifications
You must be signed in to change notification settings - Fork 19
/
Expressions-example.html
1104 lines (1103 loc) · 57.4 KB
/
Expressions-example.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
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
233
234
235
236
237
238
239
240
241
242
243
244
245
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
275
276
277
278
279
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
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
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
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" >
<title>An Expression Language</title>
<link href="book.css" rel="stylesheet" type="text/css">
<link href="code.css" rel="stylesheet" type="text/css">
<link rel="home" href="00-Main.html" title="">
</head>
<body>
<a name="Expressions"></a>
<h1>An Expression Language</h1>
<p>
Let us consider this Xtext implementation of an Expressions language
(similar to the <em>Arithmetic</em> example shipped with Xtext)
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">grammar</span> org.eclipse.xsemantics.example.expressions.Expressions <br/>
<span class="keyword">with</span> org.eclipse.xtext.common.Terminals<br/>
<br/>
<span class="keyword">generate</span> expressions <span class="string">"http://xsemantics.sf.net/example/expressions/Expressions"</span><br/>
<br/>
Model:<br/>
(variables+=Variable)*<br/>
;<br/>
<br/>
Variable:<br/>
name=ID <span class="string">'='</span> expression=Expression<br/>
;<br/>
<br/>
Expression:<br/>
BooleanExpression;<br/>
<br/>
BooleanExpression <span class="keyword">returns</span> Expression:<br/>
Comparison <br/>
(({AndOrExpression.left=<span class="keyword">current</span>} op=(<span class="string">"||"</span>|<span class="string">"&&"</span>)) right=Comparison)*;<br/>
<br/>
Comparison <span class="keyword">returns</span> Expression:<br/>
Equals<br/>
(({Comparison.left=<span class="keyword">current</span>} op=(<span class="string">"<"</span>) ) right=Equals)*;<br/>
<br/>
Equals <span class="keyword">returns</span> Expression:<br/>
Addition <br/>
(({Equals.left=<span class="keyword">current</span>} op=(<span class="string">"=="</span>) ) right=Addition)*;<br/>
<br/>
Addition <span class="keyword">returns</span> Expression:<br/>
Multiplication<br/>
(({Plus.left=<span class="keyword">current</span>} <span class="string">'+'</span> | {Minus.left=<span class="keyword">current</span>} <span class="string">'-'</span>)<br/>
right=Multiplication)*; <br/>
<br/>
Multiplication <span class="keyword">returns</span> Expression:<br/>
Prefixed (({MultiOrDiv.left=<span class="keyword">current</span>} op=(<span class="string">"*"</span>|<span class="string">"/"</span>)) right=Prefixed)*;<br/>
<br/>
Prefixed <span class="keyword">returns</span> Expression:<br/>
{BooleanNegation} =><span class="string">"!"</span> expression=Atomic | <span class="comment">/* right associativity */</span><br/>
{ArithmeticSigned} =><span class="string">"-"</span> expression=Atomic | <span class="comment">/* right associativity */</span><br/>
Atomic;<br/>
<br/>
Atomic <span class="keyword">returns</span> Expression:<br/>
<span class="string">'('</span> Expression <span class="string">')'</span> |<br/>
{NumberLiteral} value=INT |<br/>
{StringLiteral} value=STRING |<br/>
{BooleanLiteral} value=(<span class="string">'true'</span>|<span class="string">'false'</span>) |<br/>
{VariableReference} ref=[Variable]<br/>
;<br/>
<br/>
<span class="comment">// the types will be used only internally by the type system<br/>
</span>Type:<br/>
{IntType} <span class="string">'int'</span> |<br/>
{StringType} <span class="string">'string'</span> |<br/>
{BooleanType} <span class="string">'boolean'</span><br/>
;<br/>
</p>
</div>
</div>
</p>
<p>
With this language you can write variable declarations assigning an
expression (you don't declare variable types); expressions can refer to
variables declared before the current variable (the scoping will take care of
this).
</p>
<p>
Note that, for the sake of simplicity, we do not consider a full
expression grammar, for instance, we only consider <span class="inlinecode"><</span> as a comparison
operator. This is just to keep this example simple and concentrate
on writing a type system and an interpreter with Xsemantics.
</p>
<p>
Now we would like to implement these checks:
</p>
<p>
<ul>
<li>
<span class="inlinecode">- / *</span> binary operators and <span class="inlinecode">-</span> unary operator
act only on numeric expressions
</li>
<li>
<span class="inlinecode">+</span> can act both on numeric expressions and on strings; if one
of the operand is a string the whole expression will be a string
</li>
<li>
<span class="inlinecode">==</span> operator acts only on expressions of the same type
</li>
<li>
<span class="inlinecode"><</span> operator acts only on numeric and string expressions,
and the two subexpressions must be of the same type
</li>
<li>
<span class="inlinecode">&& ||</span> binary operators and <span class="inlinecode">!</span> unary operator
act only on boolean expressions
</li>
</ul>
</p>
<p>
So let's start writing the static semantics for the expressions language,
i.e., the type system.
</p>
<p>
Note that in the grammar we also have a definition for <span class="inlinecode">Type</span>, though
that rule will never be used in the grammar; we chose this way so that
we will have also the EClass definitions for the types that will be used
by the type system. Of course, you could have simply define the hierarchy
for types using plain Java.
</p>
<a name="ExpressionsTS"></a>
<h2>Expressions Type System</h2>
<p>
Since we will extend the semantics of this language, we will start with
a first implementation.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">system</span> org.eclipse.xsemantics.example.expressions.typing.ExpressionsSemantics<br/>
<br/>
<span class="keyword">validatorExtends</span> org.eclipse.xsemantics.example.expressions.validation.AbstractExpressionsJavaValidator<br/>
<br/>
<span class="keyword">import</span> org.eclipse.xsemantics.example.expressions.expressions.*<br/>
<br/>
<span class="keyword">judgments</span> {<br/>
type |- Expression expression : <span class="keyword">output</span> Type<br/>
<span class="keyword">error</span> <span class="string">"cannot type "</span> + stringRep(expression)<br/>
<span class="keyword">source</span> expression<br/>
<span class="comment">// more judgments later<br/>
</span>}<br/>
</p>
</div>
</div>
</p>
<p>
So we define a judgment that we call <span class="inlinecode">type</span> which takes an
<span class="inlinecode">Expression</span> as input parameter and provides a <span class="inlinecode">Type</span> as
output.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">axiom</span> NumeralLiteral<br/>
G |- NumberLiteral num : <br/>
ExpressionsFactory::eINSTANCE.createIntType<br/>
<br/>
<span class="keyword">axiom</span> BooleanLiteral<br/>
G |- BooleanLiteral bool : <br/>
ExpressionsFactory::eINSTANCE.createBooleanType<br/>
<br/>
<span class="keyword">axiom</span> StringLiteral<br/>
G |- StringLiteral str : <br/>
ExpressionsFactory::eINSTANCE.createStringType<br/>
</p>
</div>
</div>
</p>
<p>
For the constants, we can write axioms, which will simply return
an instance of the corresponding type.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> MultiOrDiv<br/>
G |- MultiOrDiv multiOrDiv : IntType intType<br/>
<span class="keyword">from</span> {<br/>
G |- multiOrDiv.left : intType<br/>
G |- multiOrDiv.right : intType<br/>
}<br/>
<br/>
<span class="keyword">rule</span> Minus<br/>
G |- Minus minus : <br/>
ExpressionsFactory::eINSTANCE.createIntType<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">var</span> IntType intType<br/>
G |- minus.left : intType<br/>
G |- minus.right : intType<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
The rules for multiplication, division and minus are similar (we do not
have a base class for them all, so we need two rules); they both state
that the result type is an <span class="inlinecode">IntType</span>, provided that the subexpressions
have themselves an an <span class="inlinecode">IntType</span>. They do this in two different
(equivalent) ways.
</p>
<p>
The first one states that the result is an <span class="inlinecode">IntType</span> which is the
result of the typing of the left and right subexpressions. Remember
that for this judgment, the second parameter is an output parameter.
Basically, the second rule does the same, in a more explicit way, and
it does not bind the output result (which is created on the fly) to
the result of typing of the subexpressions (which, however, are
still required to have integer type, since we pass to the rule invocation
an <span class="inlinecode">IntType</span> as output argument).
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> Plus<br/>
G |- Plus plus : Type type<br/>
<span class="keyword">from</span> {<br/>
G |- plus.left : <span class="keyword">var</span> Type leftType<br/>
G |- plus.right : <span class="keyword">var</span> Type rightType<br/>
<br/>
{<br/>
(leftType <span class="keyword">instanceof</span> StringType || rightType <span class="keyword">instanceof</span> StringType)<br/>
type = ExpressionsFactory::eINSTANCE.createStringType<br/>
}<br/>
<span class="keyword">or</span><br/>
{<br/>
(leftType <span class="keyword">instanceof</span> IntType && rightType <span class="keyword">instanceof</span> IntType)<br/>
type = leftType <span class="comment">// i.e., IntType<br/>
</span> }<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Remember that for the + operator we are willing to deal both
with strings (string concatenation) and with integers (standard arithmetic
sum); but, if one of the two subexpressions has <span class="inlinecode">StringType</span>
then we consider the whole plus expression as a string concatenation
and we give it type string. From the premises, it should be clear
that, in case one of the subexpressions has boolean type, the
rule will fail.
</p>
<p>
Note that we use the operator <span class="inlinecode">or</span>, <a href="XsemanticsSyntax.html#Premises" title="Go to "Premises"">Section about premises</a>.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> Comparison<br/>
G |- Comparison comparison : ExpressionsFactory::eINSTANCE.createBooleanType<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">empty</span> |- comparison.left : <span class="keyword">var</span> Type leftType<br/>
<span class="keyword">empty</span> |- comparison.right : <span class="keyword">var</span> Type rightType<br/>
<br/>
<span class="comment">// cannot compare booleans<br/>
</span> (leftType <span class="keyword">instanceof</span> IntType && rightType <span class="keyword">instanceof</span> IntType) ||<br/>
(leftType <span class="keyword">instanceof</span> StringType && rightType <span class="keyword">instanceof</span> StringType)<br/>
}<br/>
<br/>
<span class="keyword">rule</span> Equals<br/>
G |- Equals comparison : ExpressionsFactory::eINSTANCE.createBooleanType<br/>
<span class="keyword">from</span> {<br/>
G |- comparison.left : <span class="keyword">var</span> Type leftType<br/>
G |- comparison.right : <span class="keyword">var</span> Type rightType<br/>
<br/>
<span class="comment">// can compare only if they have the same type<br/>
</span> (leftType.eClass == rightType.eClass)<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
The code for <span class="inlinecode">Comparison</span> and <span class="inlinecode">Equals</span> are similar: they both
return a boolean type as a result; but while equality can be checked
with any type of expressions (provided the subexpressions have the
same type), the comparison (which, in our example, limits to
<span class="inlinecode"><</span>) does not consider boolean subexpressions.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> BooleanNegation<br/>
G |- BooleanNegation negation : BooleanType boolType<br/>
<span class="keyword">from</span> {<br/>
G |- negation.expression : boolType<br/>
}<br/>
<br/>
<span class="keyword">rule</span> AndOr<br/>
G |- AndOrExpression andOr : BooleanType boolType<br/>
<span class="keyword">from</span> {<br/>
G |- andOr.left : boolType<br/>
G |- andOr.right : boolType<br/>
}<br/>
<br/>
<span class="keyword">rule</span> ArithmeticSigned<br/>
G |- ArithmeticSigned signed : ExpressionsFactory::eINSTANCE.createIntType<br/>
<span class="keyword">from</span> {<br/>
G |- signed.expression : <span class="keyword">var</span> IntType intType<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Now the rules for boolean negation, logical <span class="inlinecode">&&</span> and <span class="inlinecode">||</span> and the unary
arithmetic signed operations should be clear.
</p>
<a name="ExpressionsInfer"></a>
<h3>Type Inference for Variables</h3>
<p>
We need one more rule for typing expressions, in particular the one
for <span class="inlinecode">VariableReference</span>, whose type is the type of the referred variable.
But what is the type of a variable? The idea is that we infer the type of
a variable from the type of its expression.
</p>
<p>
Since <span class="inlinecode">Variable</span> is not an <span class="inlinecode">Expression</span> in our grammar, we need
to introduce another judgment in our type system (an alternative would have
been to introduce in the grammar a rule introducing a common superclass
for both <span class="inlinecode">Variable</span> and <span class="inlinecode">Expression</span>, e.g., <span class="inlinecode">Typable</span>,
and write the <span class="inlinecode">type</span> judgment with the first parameter of type <span class="inlinecode">Typable</span>).
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">judgments</span> {<br/>
... <span class="comment">// as above...<br/>
</span> vartype ||- Variable variable : <span class="keyword">output</span> Type<br/>
<span class="keyword">error</span> <span class="string">"cannot type "</span> + stringRep(variable)<br/>
<span class="keyword">source</span> variable<br/>
<span class="keyword">feature</span> ExpressionsPackage::eINSTANCE.variable_Expression<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Note that the new judgment has a different symbol w.r.t. the <span class="inlinecode">type</span>
judgment. Moreover, when specifying the error for such judgments
we specify that the EObject for the error marker is the variable,
but the feature for the error marker is the variable's expression.
This will generate a better error marker.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> VariableReference<br/>
G |- VariableReference varRef : Type type<br/>
<span class="keyword">from</span> {<br/>
G ||- varRef.ref : type<br/>
}<br/>
<br/>
<span class="keyword">rule</span> Variable<br/>
G ||- Variable variable : Type type<br/>
<span class="keyword">from</span> {<br/>
variable.expression != <span class="keyword">null</span><br/>
G |- variable.expression : type<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Now, the type rule for <span class="inlinecode">VariableReference</span> relies on the judgment
<span class="inlinecode">vartype</span>, which states that the type of a variable is the type
of its expression.
</p>
<p>
IMPORTANT: note that expressions can refer to other variables, and in
case of mutual dependencies like
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
i = j + 10<br/>
j = i *5<br/>
</p>
</div>
</div>
</p>
<p>
the typing would enter an infinite loop! For this reason, for this example
language we limited the scope of variables: expressions can refer only
to variables defined before the current expression.
</p>
<a name="ExpressionsValidation"></a>
<h2>Expressions Validation</h2>
<p>
Now that we have our type system for expressions we can write
validation rules (<a href="XsemanticsSyntax.html#CheckRules" title="Go to "Rules for Validator: checkrule"" >section CheckRules</a>):
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">checkrule</span> CheckVariable <span class="keyword">for</span><br/>
Variable variable<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">empty</span> ||- variable : <span class="keyword">var</span> Type type<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
This simply checks that we can give a <span class="inlinecode">Variable</span> a type
(in an empty environment).
</p>
<p>
Please refer to <a href="XsemanticsSyntax.html#GeneratedValidator" title="Go to "The Generated Java Validator"" >section GeneratedValidator</a>, in particular,
<a href="XsemanticsSyntax.html#validatorExtends" title="Go to "The validatorExtends clause"" >section validatorExtends</a>, to see how to use the generated
Java validator (which we also followed in the implementation of this
Expressions example language).
</p>
<a name="ExpressionsInterpreter"></a>
<h2>Interpreter for Expressions</h2>
<p>
Xsemantics can be used also to write interpreter rules (which can be
seen also as the operational semantics of the language).
</p>
<p>
For the Expressions language we thus introduce another judgment kind:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">judgments</span> {<br/>
... <span class="comment">// as above...<br/>
</span> interpret |- Expression expression ~> <span class="keyword">output</span> Object<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Note that we assume that we will run the interpreter ONLY on well-typed
Expressions program.
</p>
<p>
We then start writing the rules for this new judgment
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">axiom</span> InterpretNumberLiteral<br/>
G |- NumberLiteral number ~> number.value<br/>
<br/>
<span class="keyword">axiom</span> InterpretStringLiteral<br/>
G |- StringLiteral string ~> string.value<br/>
<br/>
<span class="keyword">axiom</span> InterpretBooleanLiteral<br/>
G |- BooleanLiteral bool ~> Boolean::valueOf(bool.value)<br/>
</p>
</div>
</div>
</p>
<p>
The rules for literals are pretty straightforward; note only the case for
boolean literals: since the <span class="inlinecode">value</span> feature is a string, we need to
convert it to an actual boolean.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> InterpretMinus<br/>
G |- Minus plus ~> Integer result<br/>
<span class="keyword">from</span> {<br/>
G |- plus.left ~> <span class="keyword">var</span> Integer leftResult<br/>
G |- plus.right ~> <span class="keyword">var</span> Integer rightResult<br/>
result = leftResult.intValue - rightResult.intValue<br/>
}<br/>
<br/>
<span class="keyword">rule</span> InterpretMultiOrDiv<br/>
G |- MultiOrDiv multiOrDiv ~> Integer result<br/>
<span class="keyword">from</span> {<br/>
G |- multiOrDiv.left ~> <span class="keyword">var</span> Integer leftResult<br/>
G |- multiOrDiv.right ~> <span class="keyword">var</span> Integer rightResult<br/>
<span class="keyword">if</span> (multiOrDiv.op == <span class="string">'*'</span>)<br/>
result = leftResult.intValue * rightResult.intValue<br/>
<span class="keyword">else</span><br/>
result = leftResult.intValue / rightResult.intValue<br/>
}<br/>
<br/>
<span class="keyword">rule</span> InterpretArithmeticSigned<br/>
G |- ArithmeticSigned signed ~> Integer result<br/>
<span class="keyword">from</span> {<br/>
G |- signed.expression ~> <span class="keyword">var</span> Integer expResult<br/>
result = -(expResult)<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
The above rules rely on the fact that the result of subexpression is
an <span class="inlinecode">Integer</span>.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> InterpretAndOr<br/>
G |- AndOrExpression andOr ~> Boolean result<br/>
<span class="keyword">from</span> {<br/>
G |- andOr.left ~> <span class="keyword">var</span> Boolean leftResult<br/>
G |- andOr.right ~> <span class="keyword">var</span> Boolean rightResult<br/>
<br/>
<span class="keyword">if</span> (andOr.op == <span class="string">"&&"</span>)<br/>
result = leftResult.booleanValue && rightResult.booleanValue<br/>
<span class="keyword">else</span><br/>
result = leftResult.booleanValue || rightResult.booleanValue<br/>
}<br/>
<br/>
<span class="keyword">rule</span> InterpretBooleanNegation<br/>
G |- BooleanNegation neg ~> Boolean result<br/>
<span class="keyword">from</span> {<br/>
G |- neg.expression ~> <span class="keyword">var</span> Boolean expResult<br/>
result = !expResult<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Similarly in case of boolean expressions the result of subexpressions is
assumed to be a <span class="inlinecode">Boolean</span>.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> InterpretComparison<br/>
G |- Comparison comparison ~> Boolean result<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">empty</span> |- comparison.left ~> <span class="keyword">var</span> Object leftResult<br/>
<span class="keyword">empty</span> |- comparison.right ~> <span class="keyword">var</span> Object rightResult<br/>
<br/>
<span class="keyword">if</span> (leftResult <span class="keyword">instanceof</span> String && rightResult <span class="keyword">instanceof</span> String) {<br/>
result = leftResult.toString < rightResult.toString<br/>
} <span class="keyword">else</span> {<br/>
<span class="comment">// both are int if the expression is well-typed<br/>
</span> result = (leftResult <span class="keyword">as</span> Integer) < (rightResult <span class="keyword">as</span> Integer)<br/>
}<br/>
}<br/>
<br/>
<span class="keyword">rule</span> InterpretEquals<br/>
G |- Equals comparison ~> Boolean result<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">empty</span> |- comparison.left ~> <span class="keyword">var</span> Object leftResult<br/>
<span class="keyword">empty</span> |- comparison.right ~> <span class="keyword">var</span> Object rightResult<br/>
<br/>
result = leftResult.toString == rightResult.toString<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
For comparison, the result will be a <span class="inlinecode">Boolean</span>; note that we check
whether the subexpressions are strings to convert them to a string representation
and compare such representation; the only other possible case is that they are
both integer (remember that we will call the interpreter only on well-typed
programs). Note that for equality we simply convert the result of
subexpressions to string and compare the resulting string representation.
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> InterpretPlus<br/>
G |- Plus plus ~> Object result<br/>
<span class="keyword">from</span> {<br/>
G |- plus.left ~> <span class="keyword">var</span> Object leftResult<br/>
G |- plus.right ~> <span class="keyword">var</span> Object rightResult<br/>
<br/>
<span class="keyword">if</span> (leftResult <span class="keyword">instanceof</span> String || rightResult <span class="keyword">instanceof</span> String) {<br/>
<span class="keyword">var</span> leftString = leftResult.toString<br/>
<span class="keyword">var</span> rightString = rightResult.toString<br/>
result = leftString + rightString<br/>
} <span class="keyword">else</span> {<br/>
<span class="comment">// both are int if the expression is well-typed<br/>
</span> <span class="keyword">var</span> leftInt = leftResult <span class="keyword">as</span> Integer<br/>
<span class="keyword">var</span> rightInt = rightResult <span class="keyword">as</span> Integer<br/>
result = leftInt + rightInt<br/>
}<br/>
}<br/>
<br/>
<span class="keyword">rule</span> InterpretVariableRefenrence<br/>
G |- VariableReference varRef ~> Object result<br/>
<span class="keyword">from</span> {<br/>
G |- varRef.ref.expression ~> result<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
At this point, the remaining above interpreter rules should be
straightforward.
</p>
<a name="ExpressionsCustomization"></a>
<h2>Customizations for Expressions</h2>
<p>
For the Expressions language we provide a custom implementation of
<a class="jdoc" href="http://help.eclipse.org/helios/topic/org.eclipse.platform.doc.isv/reference/api/org/eclipse/xsemantics/runtime/StringRepresentation.html" title="View JavaDoc"><abbr title="org.eclipse.xsemantics.runtime.StringRepresentation" >StringRepresentation</abbr></a> (see also
<a href="XsemanticsSyntax.html#StringRepresentation" title="Go to "String Representation"" >section StringRepresentation</a>):
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">public</span> <span class="keyword">class</span> ExpressionsStringRepresentation <span class="keyword">extends</span> StringRepresentation {<br/>
<span class="keyword">protected</span> String stringRep(String s) {<br/>
<span class="keyword">return</span> <span class="string">"'"</span> + s + <span class="string">"'"</span>;<br/>
}<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
This way when a <a class="jdoc" href="http://docs.oracle.com/javase/8/docs/api/java/lang/String.html" title="View JavaDoc"><abbr title="java.lang.String" >String</abbr></a> has to be represented by Xsemantics
generated code, it will add quotes around it; this way we are sure that we
are dealing with an actual string.
</p>
<p>
Of course, we provide the guice binding for this:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">public</span> <span class="keyword">class</span> ExpressionsRuntimeModule <span class="keyword">extends</span><br/>
org.eclipse.xsemantics.example.expressions.AbstractExpressionsRuntimeModule {<br/>
<br/>
<span class="keyword">public</span> Class<? <span class="keyword">extends</span> StringRepresentation> bindStringRepresentation() {<br/>
<span class="keyword">return</span> ExpressionsStringRepresentation.<span class="keyword">class</span>;<br/>
}<br/>
...<br/>
}<br/>
</p>
</div>
</div>
</p>
<a name="MoreInvolvedExpressionsSystem"></a>
<h2>A more involved Expressions System</h2>
<p>
Now, let's complicate things a bit, and make the system for our
Expressions language more powerful, with this new requirement:
we want to be able to implicitly convert string literals to numbers
and booleans when this is possible. This way, if an expression requires
the subexpressions to be numbers or booleans we can also accept string literals
if they can be convertible.
(Note that we intentionally avoided to consider the number literal
<span class="inlinecode">0</span> as <span class="inlinecode">false</span> and a number literal different from <span class="inlinecode">0</span>
as <span class="inlinecode">true</span>, but you can extend the system further if you want).
Thus, we want the following expressions to be
valid (and interpreted accordingly with an implicit conversion):
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
i = 20 - <span class="string">'5'</span> <span class="comment">// OK! can be given int type and evaluates to 15<br/>
</span>b = (i > 20) || <span class="string">'true'</span> <span class="comment">// OK! can be given boolean type<br/>
</span><span class="comment">// and evaluates to true <br/>
</span>
</p>
</div>
</div>
</p>
<p>
Note that in case no expectation on types is expressed, the system
will be behave as before:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
i = 20 + <span class="string">'5'</span> <span class="comment">// has string type and evaluates to '205'<br/>
</span>j = (20 * 1) + <span class="string">'5'</span> <span class="comment">// has string type again<br/>
</span>k = 20 * (1 + <span class="string">'5'</span>) <span class="comment">// has int type, since * requires int types<br/>
</span><span class="comment">// on subexpressions<br/>
</span>
</p>
</div>
</div>
</p>
<p>
Since this more involved system will have most rules in common with
the first system we presented, we will write this new system as
an extended system (<a href="XsemanticsSyntax.html#SystemExtension" title="Go to "Extend another System"" >section SystemExtension</a>), starting from the previous one:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">system</span> org.eclipse.xsemantics.example.expressions.typing.ExtendedExpressionsSemantics<br/>
<span class="keyword">extends</span> org.eclipse.xsemantics.example.expressions.typing.ExpressionsSemantics<br/>
</p>
</div>
</div>
</p>
<p>
Thus, we introduce a new judgment in our system (the other ones are simply
inherited from the super system):
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">judgments</span>{<br/>
coerce |~ Expression expression |> Type expectedType<br/>
<span class="keyword">error</span> <span class="string">"cannot convert "</span> + stringRep(expression) +<br/>
<span class="string">" to type "</span> + stringRep(expectedType)<br/>
<span class="keyword">source</span> expression<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
We then have to define the rules for this new judgment:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">rule</span> StringToInt<br/>
G |~ StringLiteral string |> IntType type<br/>
<span class="keyword">from</span> {<br/>
Integer::parseInt(string.value)<br/>
}<br/>
<br/>
<span class="keyword">rule</span> StringToBool<br/>
G |~ StringLiteral string |> BooleanType type<br/>
<span class="keyword">from</span> {<br/>
string.value.equalsIgnoreCase(<span class="string">"true"</span>) ||<br/>
string.value.equalsIgnoreCase(<span class="string">"false"</span>)<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Then, this judgment will be used by the other rules; in particular, we need to
modify some rules we have seen so far.
</p>
<p>
The idea is that, as hinted above, that rules that expect a subexpression to
be of a specific type should "communicate" this expectation through the
rule environment (refer to <a href="XsemanticsSyntax.html#Environment" title="Go to "Rule Environment"" >section Environment</a>), by mapping the string
<span class="inlinecode"><span class="string">'expected'</span></span> to the expected type.
</p>
<p>
We will need then to override some rules of the previous system:
the rule for <span class="inlinecode">StringLiteral</span>, since its
type now depends on the above expectation:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">override</span> <span class="keyword">rule</span> StringLiteral<br/>
G |- StringLiteral str : Type resultType<br/>
<span class="keyword">from</span> {<br/>
{<br/>
<span class="keyword">val</span> expected = <span class="keyword">env</span>(G, <span class="string">'expected'</span>, Type)<br/>
G |~ str |> expected<br/>
resultType = expected<br/>
}<br/>
<span class="keyword">or</span><br/>
resultType = ExpressionsFactory::eINSTANCE.createStringType<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
The first block of the <span class="inlinecode">or</span> can fail due to the fact that
</p>
<p>
<ul>
<li>
No expectation was requested or
</li>
<li>
the expectation cannot be satisfied
</li>
</ul>
</p>
<p>
In any other case the type will be <span class="inlinecode">string</span> (which might make invoking
rules fail).
</p>
<p>
Now we need to override those rules that have expectations on subexpressions,
in order to pass to rule invocation an appropriate environment:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">override</span> <span class="keyword">rule</span> MultiOrDiv<br/>
G |- MultiOrDiv multiOrDiv : IntType intType<br/>
<span class="keyword">from</span> {<br/>
intType = ExpressionsFactory::eINSTANCE.createIntType<br/>
G, <span class="string">'expected'</span> <- intType |- multiOrDiv.left : intType<br/>
G, <span class="string">'expected'</span> <- intType |- multiOrDiv.right : intType<br/>
}<br/>
<br/>
<span class="keyword">override</span> <span class="keyword">rule</span> AndOr<br/>
G |- AndOrExpression andOr : BooleanType boolType<br/>
<span class="keyword">from</span> {<br/>
boolType = ExpressionsFactory::eINSTANCE.createBooleanType<br/>
G, <span class="string">'expected'</span> <- boolType |- andOr.left : boolType<br/>
G, <span class="string">'expected'</span> <- boolType |- andOr.right : boolType<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
We only showed two examples (the other rules for expected int and boolean
types are updated accordingly).
</p>
<p>
Note that in cases where no expectation is required, we now need to
pass an empty environment when typing subexpressions, otherwise we might
reject well-typed expressions due to expectations that were passed to the
current rule upon invocation. This however was already implemented
in the super system, so we don't need to override those rules.
</p>
<p>
The rule for Plus now is a little bit more complex, since it
has to take care of possible expectations:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">override</span> <span class="keyword">rule</span> Plus<br/>
G |- Plus plus : Type type<br/>
<span class="keyword">from</span> {<br/>
G |- plus.left : <span class="keyword">var</span> Type leftType<br/>
G |- plus.right : <span class="keyword">var</span> TyThe -e option is not standard. A POSIX-compliant echo does not accept any options:pe rightType<br/>
<br/>
{ <br/>
<span class="keyword">val</span> expected = <span class="keyword">env</span>(G, <span class="string">'expected'</span>, Type)<br/>
G |~ plus.left |> expected<br/>
G |~ plus.right |> expected<br/>
type = expected<br/>
}<br/>
<span class="keyword">or</span><br/>
{<br/>
(leftType <span class="keyword">instanceof</span> StringType || rightType <span class="keyword">instanceof</span> StringType)<br/>
type = ExpressionsFactory::eINSTANCE.createStringType<br/>
}<br/>
<span class="keyword">or</span><br/>
{<br/>
(leftType <span class="keyword">instanceof</span> IntType && rightType <span class="keyword">instanceof</span> IntType)<br/>
type = leftType <span class="comment">// i.e., IntType<br/>
</span> }<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Now we need to adapt also some interpretation rules to take into
consideration expectations:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">override</span> <span class="keyword">rule</span> InterpretStringLiteral<br/>
G |- StringLiteral string ~> Object result<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">var</span> Type expected<br/>
{<br/>
expected = <span class="keyword">env</span>(G, <span class="string">'expected'</span>, IntType)<br/>
result = Integer::parseInt(string.value)<br/>
}<br/>
<span class="keyword">or</span><br/>
{<br/>
expected = <span class="keyword">env</span>(G, <span class="string">'expected'</span>, BooleanType)<br/>
result = Boolean::parseBoolean(string.value)<br/>
}<br/>
<span class="keyword">or</span><br/>
result = string.value<br/>
}<br/>
<br/>
<span class="keyword">override</span> <span class="keyword">rule</span> InterpretMultiOrDiv<br/>
G |- MultiOrDiv multiOrDiv ~> Integer result<br/>
<span class="keyword">from</span> {<br/>
<span class="keyword">var</span> IntType intType = ExpressionsFactory::eINSTANCE.createIntType<br/>
G, <span class="string">'expected'</span> <- intType |- multiOrDiv.left ~> <span class="keyword">var</span> Integer leftResult<br/>
G, <span class="string">'expected'</span> <- intType |- multiOrDiv.right ~> <span class="keyword">var</span> Integer rightResult<br/>
<span class="keyword">if</span> (multiOrDiv.op == <span class="string">'*'</span>)<br/>
result = leftResult.intValue * rightResult.intValue<br/>
<span class="keyword">else</span><br/>
result = leftResult.intValue / rightResult.intValue<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
Again, we only showed some modified rules; now it should be clear what
other rules need to be adapted and how.
</p>
<p>
All the other rules which do not require adaption will be simply
inherited from the super system.
</p>
<a name="ExpressionsCodeGeneration"></a>
<h2>Generation for Expressions</h2>
<p>
The Expressions language we used in this example does not implement any
real code generation. However, we implemented a generation strategy just
for the sake of demonstration on how to use the generated Java code
and the trace utilities.
</p>
<p>
The generator will generate an <span class="inlinecode">.output</span> file which shows
the type for each variable, the interpretation of its expression, together
with the application traces (as strings) both for the type and the interpretation.
The relevant part of the generator (written in Xtend2) is shown:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">class</span> ExpressionsGenerator <span class="keyword">implements</span> IGenerator {<br/>
<br/>
@Inject ExpressionsSemantics semantics<br/>
@Inject <span class="keyword">extension</span> TraceUtils<br/>
@Inject <span class="keyword">extension</span> StringRepresentation<br/>
<br/>
<span class="comment">// skipped some code<br/>
</span> <br/>
<span class="keyword">def</span> compileExpression(Expression exp) {<br/>
<span class="keyword">val</span> typeTrace = <span class="keyword">new</span> RuleApplicationTrace()<br/>
<span class="keyword">val</span> interpreterTrace = <span class="keyword">new</span> RuleApplicationTrace()<br/>
<span class="keyword">val</span> type = semantics.type(null, typeTrace, exp)<br/>
<span class="keyword">val</span> result = semantics.interpret(null, interpreterTrace, exp)<br/>
<span class="string">'''<br/>
type: «</span>type.value.string<span class="string">»<br/>
type trace: «</span>typeTrace.traceAsString<span class="string">»<br/>
<br/>
interpretation: «</span>result.value.string<span class="string">»<br/>
interpretation trace: «</span>interpreterTrace.traceAsString<span class="string">»<br/>
'''</span><br/>
}<br/>
}<br/>
</p>
</div>
</div>
</p>
<p>
<span class="inlinecode">ExpressionsSemantics</span> is the Java class generated by Xsemantics from
the system we wrote for the Expressions language.
</p>
<p>
Actually, we want to use the extended system (<a href="Expressions-example.html#MoreInvolvedExpressionsSystem" title="Go to "A more involved Expressions System"" >section MoreInvolvedExpressionsSystem</a>),
thus we will bind <span class="inlinecode">ExpressionsSemantics</span> to <span class="inlinecode">ExtendedExpressionsSemantics</span>
in the runtime module:
</p>
<p>
<div class="literallayout">
<div class="incode">
<p class="code">
<span class="keyword">public</span> <span class="keyword">class</span> ExpressionsRuntimeModule <span class="keyword">extends</span><br/>
org.eclipse.xsemantics.example.expressions.AbstractExpressionsRuntimeModule {<br/>
...<br/>
<span class="keyword">public</span> Class<? <span class="keyword">extends</span> ExpressionsSemantics> bindExpressionsSemantics() {<br/>
<span class="keyword">return</span> ExtendedExpressionsSemantics.<span class="keyword">class</span>;<br/>