aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/compiler.spad.pamphlet
blob: 49d87f8092de81558a6a58382394f1bc4a193924 (plain)
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
\documentclass{article}
\usepackage{open-axiom}

\author{Gabriel Dos~Reis}

\begin{document}

\begin{abstract}
\end{abstract}

\tableofcontents
\eject


\section{Compiler Intermediate Form}

<<domain IRFORM InternalRepresentationForm>>=
)abbrev domain IRFORM InternalRepresentationForm
++ Author: Gabriel Dos Reis
++ Date Created: March 12, 2010
++ Date Last Modified: March 12, 2010
++ Description:
++   This domain provides representations for the intermediate
++   form data structure used by the Spad elaborator.
InternalRepresentationForm(): Public == Private where
  Public == Join(SetCategory, HomotopicTo Syntax) with
     irVar: (Identifier, InternalTypeForm) -> %
       ++ \spad{irVar(x,t)} returns an IR for a variable reference
       ++ of type designated by the type form \spad{t}
     irCtor: (Identifier, InternalTypeForm) -> %
       ++ \spad{irCtor(n,t)} returns an IR for a constructor reference
       ++ of type designated by the type form \spad{t}
     irDef: (Identifier, InternalTypeForm, %) -> %
       ++ \spad{irDef(f,ts,e)} returns an IR representation for a definition
       ++ of a function named \spad{f}, with signature \spad{ts}
       ++ and body \spad{e}.
  Private == Syntax add
    coerce(x: %): Syntax == rep x

    coerce(x: Syntax): % == per x

    irVar(x,t) ==
      buildSyntax('%irVar,[x::Syntax,t::Syntax])::%

    irCtor(x,t) ==
      buildSyntax('%irCtor,[x::Syntax,t::Syntax])::%

    irDef(f,ts,e) ==
      buildSyntax('%irDef,[f::Syntax, ts::Syntax, e::Syntax])::%

@

<<domain ITFORM InternalTypeForm>>=
)abbrev domain ITFORM InternalTypeForm
++ Author: Gabriel Dos Reis
++ Date Created: March 12, 2010
++ Date Last Modified: March 12, 2010
++ Description:
++   This domain provides representations for internal type form.
InternalTypeForm(): Public == Private where
  Public == Join(SetCategory, HomotopicTo Syntax) with
    jokerMode: %
      ++ \spad{jokerMode} is a constant that stands for any mode
      ++ in a type inference context
    noValueMode: %
      ++ \spad{noValueMode} is a constant mode that indicates that
      ++ the value of an expression is to be ignored.
    voidMode: %
      ++ \spad{voidMode} is a constant mode denoting Void.
    categoryMode: %
      ++ \spad{categoryMode} is a constant mode denoting Category.
    mappingMode: (%, List %) -> %
      ++ \spad{mappingMode(r,ts)} returns a mapping mode with return
      ++ mode \spad{r}, and parameter modes \spad{ts}.
  Private == InternalRepresentationForm add
    jokerMode == _$EmptyMode$Foreign(Builtin)
    noValueMode == _$NoValueMode$Foreign(Builtin)
    voidMode == _$Void$Foreign(Builtin)

    mappingMode(r,ts) == 
      buildSyntax('Mapping,cons(r::Syntax, ts : List(Syntax)))::%

@

\section{Elaboration domain}
<<domain ELABOR Elaboration>>=
)abbrev domain ELABOR Elaboration
Elaboration(): Public == Private where
  Public == CoercibleTo OutputForm with
    elaboration: (InternalRepresentationForm, InternalTypeForm, Environment) -> %
      ++ \spad{elaboration(ir,ty,env)} construct an elaboration object for
      ++ for the internal representation form \spad{ir}, with type \spad{ty},
      ++ and environment \spad{env}.
    irForm: % -> InternalRepresentationForm
      ++ \spad{irForm(x)} returns the internal representation form of
      ++ the elaboration \spad{x}.
    typeForm: % -> InternalTypeForm
      ++ \spad{typeForm(x)} returns the type form of the elaboration \spad{x}.
    environment: % -> Environment
      ++ \spad{environment(x)} returns the environment of the
      ++ elaboration \spad{x}.
  Private == add
    Rep == Record(ir: InternalRepresentationForm,
              type: InternalTypeForm, env: Environment)
    irForm x == rep(x).ir
    typeForm x == rep(x).type
    environment x == rep(x).env
    coerce(x: %): OutputForm ==
      bracket([irForm(x)::OutputForm, typeForm(x)::OutputForm,
                  environment(x)::OutputForm])$OutputForm
@

\section{Compilation Context}

<<domain CMPCTXT CompilationContext>>=
)abbrev domain CMPCTXT CompilationContext
CompilationContext(): Public == Private where
  Public == SetCategory with
    getExitMode: (%,Integer) -> InternalTypeForm
    pushExitMode!: (%, InternalTypeForm) -> %
  Private == add
    Rep == Record(exitModes: List Integer)
@

\section{A Package for the Spad Compiler}

<<package COMPILER CompilerPackage>>=
)abbrev package COMPILER CompilerPackage
++ Author: Gabriel Dos Reis
++ Date Created: March 12, 2010
++ Date Last Modified: March 12, 2010
++ Description:
++   This package implements a Spad compiler.
CompilerPackage(): Public == Private where
  Public == Type with
     macroExpand: (SpadAst, Environment) -> SpadAst
       ++ \spad{macroExpand(s,e)} traverses the syntax object \spad{s}
       ++ replacing all (niladic) macro invokations with the
       ++ corresponding substitution.
     elaborate: SpadAst -> Maybe Elaboration
       ++ \spad{elaborate(s)} returns the elaboration of the syntax
       ++ object \spad{s} in the empty environement.
     elaborateFile: String -> List Maybe Elaboration
  Private == add
     macro IR == InternalRepresentationForm
     macro TFORM == InternalTypeForm
     macro RESULT == Maybe Elaboration
     macro ENV == Environment
     import ENV
     import IR
     import RESULT
     inline RESULT

     -- forward declaration
     doElaborate: (SpadAst,TFORM,ENV) -> RESULT

     macroExpand(s,e) ==
       -- FIXME: this is a short-term stopgap.
       macroExpand(s,e)$Foreign(Builtin)

     -- fecth the active definition of 'x', if any from environment `e'.
     getValue(x: Identifier, e: ENV): RESULT ==
       case getProperty(x,'value,e) is
         val@SExpression =>
           T := destruct(val)$SExpression
           just elaboration(first(T) : IR, second(T) : TFORM, e)
         otherwise => nothing                 -- not defined
 
     -- fetch the active declaration of 'x', if any from environment `e'.
     getMode(x: Identifier, e: ENV): Maybe TFORM ==
       val := getValue(x,e)
       val case nothing =>                    -- symbol is not defined
         decl := getProperty(x,'mode,e)
         decl case nothing => nothing         -- nor declared
         T := destruct(decl)$SExpression
         just(second(T) : TFORM)
       just typeForm(val@Elaboration)

     -- simply coerce the elaboration `T' to mode `m'.
     coerceSimply(T: RESULT, m: TFORM): RESULT ==
       T case nothing => T
       t := typeForm(T@Elaboration)
       m = jokerMode or t = m => T
       m = noValueMode or m = voidMode or t = jokerMode => 
          just elaboration(irForm T, m, environment T)
       nothing
    
     -- implicitly coerce the eloboration `T' to one that is
     -- valid in a mode context `m'.
     coerceTo(T: RESULT, m:TFORM): RESULT ==
       coerceSimply(T,m)

     -- elaborate an identifier in the current environment.
     elaborateIdentifier(x: Identifier, t: TFORM, e: ENV): RESULT ==
       r := 
         case getValue(x,e) is
           v@Elaboration => just v
           otherwise => 
             case getMode(x,e) is
               m@TFORM => just elaboration(irVar(x,m), m, e)
               otherwise => nothing$RESULT
       coerceTo(r, t)

     -- elaborate a form designating a mode
     elaborateMode(x: SpadAst, e: ENV): Maybe TFORM ==
       t := doElaborate(x,jokerMode,e)
       t case nothing => nothing
       just(t : TFORM) -- FIXME: use conversion.

     -- elaborate a definition.
     elaborateDefinition(x: DefinitionAst, m: TFORM, e: ENV): RESULT ==
       import HeadAst
       e' := e
       parms := parameters head x
       n := name head x
       srcSig := signature x
       irSig := nil$List(TFORM)
       -- elaborate parameters and push them in scope.
       for p in parms for t in source srcSig repeat
         nil? t => return nothing            -- FIXME: should infer first
         irT := elaborateMode(t::SpadAst,e)
         irT case nothing => return nothing
         irSig := cons(irT@TFORM,irSig)
       -- elaborate return type.
       ret := target srcSig
       nil? ret => nothing                   -- FIXME: should infer first
       irRet := elaborateMode(ret::SpadAst,e)
       irRet case nothing => nothing
       -- elaborate the body.
       b := doElaborate(body x, irRet@TFORM, e)
       b case nothing => nothing
       t := mappingMode(irRet@TFORM, reverse irSig)
       just elaboration(irDef(n,t,irForm b),t,e')

     -- elaborate a syntax `s' under context `m', in the envionment `e'.
     doElaborate(s: SpadAst, t: TFORM, e: ENV): RESULT ==
       case s is
         id@Identifier => elaborateIdentifier(id,t,e)
         otherwise => nothing

     elaborate s == 
       doElaborate(s,jokerMode,empty()$ENV)

     elaborateFile f ==
       [elaborate(s::SpadAst) for s in parse(f)$SpadParser]

@


\section{License}
<<license>>=
--Copyright (C) 2007-2010, Gabriel Dos Reis.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical Algorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@


<<*>>=
<<license>>

<<domain IRFORM InternalRepresentationForm>>
<<package COMPILER CompilerPackage>>

@