[project @ 1997-03-14 08:02:40 by simonpj]
[nofib.git] / real / hpg / Env.lhs
1 % Env.lhs - environment for the Haskell Program Generator
2
3 % @(#)Env.lhs   1.20 dated 92/07/20 at 17:30:47
4
5 % Crown Copyright 1992
6
7 \section{Environment}
8
9 The environment module implements the environment used in generating Haskell
10 programs.
11 It is the repository of such useful data as random numbers, type and constructor
12 names, and information about types and values already generated.
13
14 This environment is changed as the \HPG\ progresses and is passed along
15 as a parameter to the functions comprising the \HPG; it does not appear
16 explicitly as a parameter due to the use of continuations.
17
18 This module
19 also defines the various types of continuation used and the result type
20 of the \prog{hpg} function itself.
21
22 The interface is as follows:
23 \begin{haskell}
24
25 > module Env (
26 >     Cont, Ncont, Econt, Vcont, Xcont, Xscont,
27 >     Answer,
28 >     Env, make_Env,
29 >     upto, choose, choosew,
30 >     Output, default_output,
31 >     get_constructors, get_val_names, get_type_names, get_all_type_names,
32 >     get_all_type_decls, get_all_val_decls, get_all_lambdas, get_type,
33 >     get_output,
34 >     push_lambda, pop_lambda, extend_type_env, extend_val_env, set_output
35 >     ) where
36
37 > import Config
38 > import Types
39 > import IO -- 1.3
40
41 \end{haskell}
42
43 \subsection{Types}
44 This module defines various sorts of continuation:
45 \begin{description}
46 \item[\prog{Cont}] the standard continuation --- takes an \prog{Env} and
47     returns an \prog{Answer}.
48 \item[\prog{Xcont}] a continuation which takes an element of some type,
49     \prog{x}, and returns a \prog{Cont}.
50     The type \prog{Xcont} is parametrised by the type \prog{x}.
51 \item[\prog{Xscont}] a continuation which takes a list of elements of some type,
52     \prog{x}, and returns a \prog{Cont}.
53     The type \prog{Xscont} is parametrised by the type \prog{x}.
54 \item[\prog{Ncont}, \prog{Econt}, \prog{Vcont}] particular types of
55     \prog{Xcont}, where the type \prog{x}
56     is instantiated to \prog{Int}, \prog{Expression} and \prog{Value}
57     respectively.
58 \end{description}
59 \begin{haskell}
60
61 > type Cont      =  Env -> Answer
62
63 > type Xcont x   =  x -> Cont
64 > type Xscont x  =  [x] -> Cont
65
66 > type Ncont     =  Xcont Int
67 > type Econt     =  Xcont Expression
68 > type Vcont     =  Xcont Value
69
70 \end{haskell}
71
72 As the Haskell Program Generator produces output, its result must be of
73 type \prog{Dialogue}, so \prog{Answer} is just a type synonym:
74 \begin{haskell}
75
76 > type Answer    =  IO () --Dialogue
77
78 \end{haskell}
79
80 \subsection{Random numbers}
81 This section gives a source of random numbers, to be carried around
82 in the environment, and some interface functions for accessing the
83 random numbers.
84
85 The random number generator is taken from Wichmann and Hill's
86 paper~\cite{wichmann.random}.
87 It requires three seeds to initialise it, which must be supplied to the
88 initial environment, and it gives an infinite list of pseudo-random
89 numbers.
90 These numbers are then removed from the list as required by the interface
91 functions below.
92
93 The \prog{fromIntegral}s in \prog{combine} ensure that the \prog{Int}s are
94 converted to \prog{Floats} before calculation.
95 \begin{haskell}
96
97 > random_numbers :: (Int, Int, Int) -> [Float]
98 > random_numbers (s1,s2,s3)
99 >     =  map (snd . properFraction . combine) (iterate f (s1,s2,s3))
100 >        where
101 >        combine :: (Int,Int,Int) -> Float
102 >        combine (a,b,c)  =
103 >             fromIntegral(a)/30269 + fromIntegral(b)/30307
104 >             + fromIntegral(c)/30323
105 >        f (a,b,c)  =
106 >            ((171*a) `mod` 30269, (172*b) `mod` 30307, (170*c) `mod` 30323)
107
108 \end{haskell}
109
110 \prog{upto n nc} applies \prog{nc} to an integer in the range
111 $0 \ldots n$ inclusive.
112 The convoluted definition of \prog{x} does a floating point multiplication of
113 \prog{r} by \prog{n+1}, takes the \prog{Integer} part and converts it to an
114 \prog{Int}.
115
116 The random number used is printed on the standard output, partly to aid in
117 debugging, and partly because the printing prevents the manifestation of
118 a bug in one of the current Haskell compilers.
119 If the \prog{appendChan} line is replaced by the one above it, the printing
120 will not occur.
121 % NB - mkTEnv relies on the layout of upto, so be careful in changing it.
122 \begin{haskell} 
123  
124 > upto :: Int -> Ncont -> Cont
125 > upto n nc (MkEnv (r:rs) cs ts vs te ve le op)
126 >     =  hPutStr stderr (show x ++ " ") >> nc x (MkEnv rs cs ts vs te ve le op)
127 > --  =  appendChan stderr (show x ++ " ") exit ((nc x) (MkEnv rs cs ts vs te ve le op))
128 >        where
129 >        x :: Int
130 >        x  =  fromIntegral (fst (properFraction (r * (fromIntegral (n+one)))))
131  
132 \end{haskell}
133  
134 \prog{choose xs xc} applies \prog{xc} to a random element of the list
135 \prog{xs}.
136 \begin{haskell}
137  
138 > choose :: [x] -> (Xcont x) -> Cont
139 > choose xs xc  =  upto (length xs - one) (\n -> xc (xs !! n))
140
141 \end{haskell}
142
143 \prog{choosew ps xc} applies \prog{xc} to an item chosen from the list
144 \prog{ps} as follows: each element of \prog{ps} is a pair of an integer
145 and an item; the integer determines the probability of choosing the item
146 as the integer divided by the sum of the integers in the list.
147 (\prog{choosew} means ``weighted choice''.)
148 \begin{haskell}
149
150 > choosew :: [(Int,x)] -> (Xcont x) -> Cont
151 > choosew ps xc
152 >     =  upto (sum [i | (i,x) <- ps] - one) (f ps)
153 >        where
154 >        f ((i,x):ps') n | n < i  =  xc x
155 >                        | True   =  f ps' (n-i)
156
157 \end{haskell}
158
159 \subsection{Names}
160 The \HPG\ requires sources of names for types, values and constructors.
161 These are stored in the environment and are just a string consisting
162 of an identifying name and a number:
163 \begin{haskell}
164
165 > idnum :: String -> [String]
166 > idnum id  =  [id ++ show n | n <- [one..]]
167
168 > constructors :: [Constructor]
169 > constructors  =  idnum constructor_name
170
171 > type_names :: [Type_name]
172 > type_names    =  idnum type_name
173
174 > val_names :: [Val_name]
175 > val_names     =  idnum val_name
176
177 \end{haskell}
178
179 \subsection{Type, value and lambda environments}
180 The type and value environments are used to store declarations of previously
181 generated types and values respectively.
182 The lambda environment stores the names and values of lambda-bound variables.
183 \begin{haskell}
184
185 > type Type_env  =  [Type_decl]
186
187 > initial_type_env :: Type_env
188 > initial_type_env  =  []
189
190 > type Val_env  =  [Val_decl]
191
192 > initial_val_env :: Val_env
193 > initial_val_env  =  []
194
195 > type Lambda_env  =  [(Val_name, Value)]
196
197 > initial_lambda_env :: Lambda_env
198 > initial_lambda_env  =  []
199
200 \end{haskell}
201
202 \subsection{The output stream}
203 The \HPG\ writes its output program to the standard output by default, but
204 it can be given a file name to which output is written instead.
205 The output stream is carried as part of the environment as an element of
206 type \prog{Output}, defined as:
207 \begin{haskell}
208
209 > --type Output  =  String -> FailCont -> SuccCont -> Dialogue
210 > type Output  =  String -> IO ()
211
212 \end{haskell}
213 The default value is:
214 \begin{haskell}
215
216 > default_output :: Output
217 > default_output  str =  putStr str
218
219 \end{haskell}
220
221 \prog{set\_output str} returns a value of \prog{Output} in which the
222 output stream is the file whose name is \prog{str}.
223 \begin{haskell}
224
225 > set_output :: String -> Output
226 > set_output str  =  appendFile str
227
228 \end{haskell}
229
230 \subsection{Environment construction}
231 The \prog{Env} type is just a collection of all the environment information,
232 bound together with a constructor.
233 \begin{haskell}
234
235 > data Env  =  MkEnv [Float] [Constructor] [Type_name] [Val_name]
236 >                    Type_env Val_env Lambda_env Output
237
238 \end{haskell}
239
240 \prog{make\_Env} returns an environment, constructed from its parameters.
241 % NB - mkTEnv relies on the layout of make_Env, so be careful in changing it.
242 \begin{haskell}
243
244 > make_Env :: (Int,Int,Int) -> Output -> Env
245 > make_Env (s1,s2,s3) op  =  MkEnv (random_numbers (s1,s2,s3)) 
246 >                               constructors type_names val_names
247 >                               initial_type_env initial_val_env
248 >                               initial_lambda_env op
249
250 \end{haskell}
251
252 \subsection{Environment extraction functions}
253 These functions use the environment as a source of random numbers or
254 names, applying their continuation to the data extracted and
255 an altered environment from which the data has been removed, if necessary.
256 \begin{haskell}
257
258 > get_constructors :: Int -> (Xscont Constructor) -> Cont
259 > get_constructors n csc (MkEnv rs cs tns vns te ve le op)
260 >     =  csc (take n cs) (MkEnv rs (drop n cs) tns vns te ve le op)
261
262 > get_val_names :: Int -> (Xscont Val_name) -> Cont
263 > get_val_names n vnsc (MkEnv rs cs tns vns te ve le op)
264 >     =  vnsc (take n vns) (MkEnv rs cs tns (drop n vns) te ve le op)
265
266 > get_type_names :: Int -> (Xscont Type_name) -> Cont
267 > get_type_names n tnsc (MkEnv rs cs tns vns te ve le op)
268 >     =  tnsc (take n tns) (MkEnv rs cs (drop n tns) vns te ve le op)
269
270 > get_all_type_names :: (Xscont Type_name) -> Cont
271 > get_all_type_names tnsc e@(MkEnv _ _ _ _ te _ _ _)
272 >     =  tnsc [tn | (tn,t) <- te] e
273
274 > get_all_type_decls :: (Xscont Type_decl) -> Cont
275 > get_all_type_decls tdsc e@(MkEnv _ _ _ _ te _ _ _)
276 >     = tdsc te e
277
278 > get_all_val_decls :: (Xscont Val_decl) -> Cont
279 > get_all_val_decls vdsc e@(MkEnv _ _ _ _ _ ve _ _)
280 >     = vdsc ve e
281
282 > get_all_lambdas :: (Xcont Lambda_env) -> Cont
283 > get_all_lambdas lec e@(MkEnv _ _ _ _ _ _ le _)
284 >     =  lec le e
285
286 > get_type :: Type_name -> (Xcont Htype) -> Cont
287 > get_type tn tc e@(MkEnv _ _ _ _ te _ _ _)
288 >     =  tc (head [t | (tn',t) <- te , tn == tn']) e
289
290 > get_output :: (Xcont Output) -> Cont
291 > get_output oc e@(MkEnv _ _ _ _ _ _ _ op)  =  oc op e
292
293 \end{haskell}
294
295 \subsection{Extension functions}
296 \prog{extend\_type\_env tds c} applies \prog{c} to an environment extended
297 with the list of type declarations \prog{tds}.
298 \begin{haskell}
299  
300 > extend_type_env :: [Type_decl] -> Cont -> Cont
301 > extend_type_env tds c (MkEnv rs cs tns vns te ve le op)
302 >     =  c (MkEnv rs cs tns vns (tds++te) ve le op)
303  
304 \end{haskell}
305  
306 \prog{extend\_val\_env vds c} applies \prog{c} to an environment extended
307 with the list of value declarations \prog{vds}.
308 \begin{haskell}
309  
310 > extend_val_env :: [Val_decl] -> Cont -> Cont
311 > extend_val_env vds c (MkEnv rs cs tns vns te ve le op)
312 >     =  c (MkEnv rs cs tns vns te (vds++ve) le op)
313  
314 \end{haskell}
315
316 \subsection{Lambda environment functions}
317 \prog{push\_lambda (vn,v) c} adds the \prog{Val\_name}, \prog{Value} pair
318 \prog{(vn,v)} to the front of the lambda environment list and applies
319 \prog{c} to the resulting environment.
320 \begin{haskell}
321
322 > push_lambda :: (Val_name, Value) -> Cont -> Cont
323 > push_lambda (vn,v) c (MkEnv rs cs tns vns te ve le op)
324 >     =  c (MkEnv rs cs tns vns te ve ((vn,v):le) op)
325
326 \end{haskell}
327
328 \prog{pop\_lambda lc} removes the front item from the lambda environment
329 list and applies \prog{lc} to this and resulting environment.
330 It is an error for the lambda environment to be empty.
331 \begin{haskell}
332
333 > pop_lambda :: Xcont (Val_name,Value) -> Cont
334 > pop_lambda lc (MkEnv rs cs tns vns te ve ((vn,v):le) op)
335 >     =  lc (vn,v) (MkEnv rs cs tns vns te ve le op)
336
337 \end{haskell}