File: unlambda.java

package info (click to toggle)
unlambda 2.0.0-5
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k, lenny, sarge
  • size: 2,136 kB
  • ctags: 408
  • sloc: ansic: 1,484; perl: 527; java: 408; lisp: 375; ml: 199; makefile: 46
file content (634 lines) | stat: -rw-r--r-- 21,469 bytes parent folder | download
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
// This is an implementation of the Unlambda programming language.
// This one is in Java (the Master One is in Scheme).
// $Id: unlambda.java,v 1.12 1999/11/03 21:05:47 madore Exp $

// Copyright (C) 1999 by David A. Madore <david.madore@ens.fr>

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version
// 2 of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty
// of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
// the GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

package unlambda;

// Beware!  You had probably best not try to understand how this works
// if you don't already know something about interpreters for
// functional languages and how to write in CPS.  I wrote this and
// already I find this somewhat obscure, so I suppose it is more or
// less unreadable for other people...

// If you really want to understand this, I suggest you use the RCS
// history to go through the previous versions to see how this program
// evolved.  Basically there are three levels: in the first level,
// there are only Functions and Expressions, and we have the classical
// eval/apply mutual recursiveness (here eval is a method of the class
// Expression and apply is a method of the class Function); this
// recursivity uses the Java stack in an ordinary way (you can have a
// stack overflow but only if your Unlambda program is really deeply
// recursive); all this works, but there is no call/cc.  So in level
// two, we rewrite the interpreter in Continuation Passing Style
// (CPS).  This introduces Continuations: the eval and apply functions
// take one more argument, the Continuation which should be invoked
// with the result of the computation.  The entire system is then
// tail-recursive (continuations never return - or only at the very
// end); but since Java is not properly tail-recursive, any
// computation of a certain length will cause a stack overflow.  So we
// move to level three: this time, Tasks are introduced.  Tasks do the
// actual computation (through the run() method).  Continuations only
// take their value and return the appropriate Task to carry the rest
// of the computation.  This time, the Java stack is no longer used
// (*at all* - in other words, its depth is bounded by a constant
// function of the program complexity), and the Unlambda ``stack'' (no
// longer a truly pertinent notion in the presence of first-class
// continuations) is part of the Java heap (as chains of
// Continuations), so that stack frames are no longer ``popped'', they
// are garbage-collected.

public class ProgramOverException extends Exception {
    // The ProgramOverException is raised (by the FinalTask) when the
    // execution of the Unlambda program is terminated.  We need an
    // Exception here, since FinalTask.run() does not have any Task
    // that it might return.
    public ProgramOverException () { super (); }
    public ProgramOverException (String s) { super (s); }
}

public abstract class Task {
    // A Task is a computation about to be performed.  The Task.run()
    // method does a little bit of that computation and returns
    // another Task that will continue the computation in question.
    // Note that this method is never called within itself, or, in
    // fact, anywhere else then in the main evaluation loop (which
    // does just that, iteratively calling run()): this is why (and
    // how) our (level 3, see above) interpreter is not recursive.
    public abstract Task run ()	throws ProgramOverException;
}

public class DummyTask extends Task {
    // This Task just runs stupidly in an idle loop.  It is not
    // (i.e. no longer) used.  Still, it is an example of what a Task
    // is, and how it is made.
    public Task run ()
    {
	return this;
    }
}

public abstract class Continuation {
    // A Continuation is a computation waiting for a value to start
    // with.  The Continuation.invoke() method passes this value to
    // the Continuation, so that it becomes a Task (the Continuation
    // itself performs nothing: only the Task will).  Generally this
    // just involves building a new Task with all the private data
    // already stored in the Continuation, plus val itself.
    public abstract Task invoke (Function val);
}

public abstract class Function {
    // A Function is the main Unlambda object.  Every (first-class)
    // object of Unlambda is a Function.  The main method is
    // Function.applyTo(), which applies the Function to another
    // Function (rand), and passes the result to a Continuation (cont)
    // that is waiting for it.  Note also that we have a slight
    // complication due to the d function, which is not really a
    // function: the d function should never be applied (rather, its
    // argument should be); so we declare the Function.isD() method
    // which returns true only for the d function.
    public boolean isD ()
    {
	return false;
    }
    public abstract Task applyTo (Function rand, Continuation cont);
}

public abstract class Expression {
    // An Expression is an Unlambda expression that has not yet been
    // evaluated.  This is what the Parser returns.  The method
    // Expression.eval() evaluates the Expression and passes the
    // result to a Continuation (cont) that is waiting for it.
    public abstract Task eval (Continuation cont);
}

public class EvalTask extends Task {
    // The EvalTask performs the evaluation of an Unlambda Expression
    // and passes the result to a Continuation.  In other words (as
    // you can see below) it just calls the Expression.eval() method.
    // (Then why do we need a special class to do something so
    // trivial?  So we can return it as a first-class value.)  For
    // stupid historical reasons, EvalTask is here, whereas AppTask is
    // much further down in the program.
    private Expression expr;
    private Continuation cont;
    EvalTask (Expression expr, Continuation cont)
    {
	this.expr = expr;
	this.cont = cont;
    }
    public Task run ()
    {
	return expr.eval (cont);
    }
}

public class IFunction extends Function {
    // The IFunction is the identity Function ("i" in Unlambda).  It
    // just passes its operand to its Continuation.
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (rand);
    }
}

public class DotFunction extends Function {
    // DotFunction behaves as the identity but prints a character
    // first (".x" in Unlambda, where x is the character to be
    // printed).
    char ch;
    static java.io.PrintStream output;
    public DotFunction (char ch)
    {
	this.ch = ch;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	output.print (ch);
	output.flush ();
	return cont.invoke (rand);
    }
}

public class K1Function extends Function {
    // K1Function is a constant Function ("`kX" un Unlambda, where X
    // is the value of the constant function).  It has a private value
    // (val), namely X, and passes it to its Continuation.
    private Function val;
    K1Function (Function val)
    {
	this.val = val;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (val);
    }
}

public class KFunction extends Function {
    // KFunction is the Unlambda constant maker Function ("k").  It
    // takes a value (a Function), rand, and returns (i.e. passes to
    // its Continuation) the K1Function of this value.
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (new K1Function (rand));
    }
}

public class S2Function extends Function {
    // S2Function corresponds to an expression of the form "``sXY" in
    // Unlambda.  It takes a third argument (Function), rand, say, Z,
    // and returns a Task that will evaluate ``XZ`YZ and pass its
    // result to the Continuation cont.  Note that to form the Task in
    // question we really form the expression ``XZ`YZ and return an
    // EvalTask: we can't do just with AppTasks (as in other similar
    // calls) because we don't know whether `YZ actually will be
    // evaluated (if `XZ evaluates to d then `YZ will remain as a
    // promise - for example in "```s`kdri").
    private Function x, y;
    S2Function (Function x, Function y)
    {
	this.x = x;
	this.y = y;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	Expression rande = new FunctionExpression (rand);
	return new EvalTask
	    (new ApplicationExpression
	     (new ApplicationExpression
	      (new FunctionExpression (x),
	       rande),
	      new ApplicationExpression
	      (new FunctionExpression (y),
	       rande)), cont);
    }
}

public class S1Function extends Function {
    // S1Function corresponds to an expression of the form "`sX" in
    // Unlambda.  It takes a second argument (Function), rand, say, Y,
    // and returns (passes to its Continuation) the S2Function
    // representing "``sXY".
    private Function x;
    S1Function (Function x)
    {
	this.x = x;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (new S2Function (this.x, rand));
    }
}

public class SFunction extends Function {
    // SFunction represents the "s" builtin of Unlambda.  It returns
    // an S1Function.
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (new S1Function (rand));
    }
}

public class VFunction extends Function {
    // VFunction represents the "v" builtin of Unlambda.  It takes
    // whatever it is given, ignores it, and returns itself
    // (i.e. passes itself to its Continuation).
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (this);
    }
}

public class DelContinuation extends Continuation {
    // The DelContinuation is a Continuation that is invoked when a
    // promise is forced: so we are waiting for the result of this
    // promise (val), and we already have the operand to which it will
    // be applied (and the Continuation which follows).  So we will
    // return an AppTask, but here it is for the operator which we are
    // waiting (compare with AppContinuation).
    private Function rand;
    private Continuation cont;
    DelContinuation (Function rand, Continuation cont)
    {
	this.rand = rand;
	this.cont = cont;
    }
    public Task invoke (Function val)
    {
	return new AppTask (val, rand, cont);
	// Note that this (and similar AppTasks throughout the
	// program) is one of the cases where DFunction can be
	// actually applied.  We could eliminate this by using the
	// following instead:
	//   return new EvalTask
	//       (new ApplicationExpression
	//        (new FunctionExpression (val),
	//         new FunctionExpression (rand)),
	//        cont);
	// (There was a bug here in revisions 1.5 through 1.9 of this
	// file.)
    }
}

public class D1Function extends Function {
    // The D1Function represents a promise ("`dX" in Unlambda).  When
    // we apply it, we must evaluate the promise (through the
    // EvalTask) and wait for this result (through the
    // DelContinuation) to apply it to the operand.
    private Expression promise;
    D1Function (Expression promise)
    {
	this.promise = promise;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	Continuation ncont = new DelContinuation (rand, cont);
	return new EvalTask (promise, ncont);
    }
}

public class DFunction extends Function {
    // This is the d function, or special form.  Its applyTo() method
    // can be called, but only indirectly (for example, from a
    // call/cc, or from another d, as in "`cd" or in "`dd`ri").
    public boolean isD ()
    {
	return true;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	return cont.invoke (new D1Function (new FunctionExpression (rand)));
    }
}

public class ContFunction extends Function {
    // This is a Function representing a reified Continuation.
    // Applying it invokes the Continuation.
    private Continuation cont;
    ContFunction (Continuation cont)
    {
	this.cont = cont;
    }
    public Task applyTo (Function val, Continuation cont)
    {
	// Note that we invoke this.cont and not cont: this is how the
	// non-local effect of invoking a (reified) Continuation
	// appears.
	return this.cont.invoke (val);
    }
}

public class CFunction extends Function {
    // CFunction is call/cc ("c" in Unlambda).
    public Task applyTo (Function rand, Continuation cont)
    {
	return new AppTask (rand, new ContFunction (cont), cont);
    }
}

public class AtFunction extends Function {
    // AtFunction is "@" (input function) in Unlambda.  This uses a
    // class variable (ch) to store the character read.
    static int ch = -1;
    static java.io.InputStream input;
    public Task applyTo (Function rand, Continuation cont)
    {
	try ch = input.read ();
	catch ( java.io.IOException e ) { ch = -1; }
	Function bval =
	    (ch != -1 ? new IFunction () : new VFunction ());
	return new AppTask (rand, bval, cont);
    }
}

public class QuesFunction extends Function {
    // QuesFunction is "?x" in Unlambda (where "x" is ch below).
    private char ch;
    QuesFunction (char ch)
    {
	this.ch = ch;
    }
    public Task applyTo (Function rand, Continuation cont)
    {
	Function bval =
	    (this.ch == AtFunction.ch ? new IFunction () : new VFunction ());
	return new AppTask (rand, bval, cont);
    }
}

public class PipeFunction extends Function {
    // PipeFunction is "|" in Unlambda.
    public Task applyTo (Function rand, Continuation cont)
    {
	Function bval =
	    (AtFunction.ch != -1 ? new DotFunction ((char) AtFunction.ch)
	     : new VFunction ());
	return new AppTask (rand, bval, cont);
    }
}

public class EFunction extends Function {
    // EFunction is "e" un Unlambda: it ignores its continuation and
    // returns the FinalTask (that which declares the program
    // finished).
    public Task applyTo (Function rand, Continuation cont)
    {
	return new FinalTask ();
    }
}

public class FunctionExpression extends Expression {
    // A FunctionExpression is an Expression which directly represents
    // an Unlambda Function (already evaluated).
    private Function fun;
    public FunctionExpression (Function fun)
    {
	this.fun = fun;
    }
    public Task eval (Continuation cont)
    {
	return cont.invoke (fun);
    }
}

class AppTask extends Task {
    // AppTask has the evaluated operator and operand, and is ready to
    // apply the one to the other.
    private Function erator;
    private Function erand;
    private Continuation cont;
    AppTask (Function erator, Function erand, Continuation cont)
    {
	this.erator = erator;
	this.erand = erand;
	this.cont = cont;
    }
    public Task run ()
    {
	return erator.applyTo (erand, cont);
    }
}

class AppContinuation extends Continuation {
    // AppContinuation has the evaluated operator and is waiting for
    // the operand to be evaluated so as to apply the one to the
    // other.
    private Function erator;
    private Continuation cont;
    AppContinuation (Function erator, Continuation cont)
    {
	this.erator = erator;
	this.cont = cont;
    }
    public Task invoke (Function val)
    {
	return new AppTask (erator, val, cont);
    }
}

class App1Task extends Task {
    // App1Task has the evaluated operator, and evaluates the operand
    // (unless the operator is "d" in which case a promise is built)
    // so as to apply the one to the other.
    private Function erator;
    private Expression rand;
    private Continuation cont;
    App1Task (Function erator, Expression rand, Continuation cont)
    {
	this.erator = erator;
	this.rand = rand;
	this.cont = cont;
    }
    public Task run ()
    {
	if ( erator.isD () )
	    return cont.invoke (new D1Function (rand));
	else {
	    Continuation ncont = new AppContinuation (erator, cont);
	    return rand.eval (ncont);
	}
    }
}

class App1Continuation extends Continuation {
    // App1Continuation is waiting for the operator to be valuated, so
    // as to proceed with evaluation of the operand (unless the
    // operator is "d") through App1Task.
    private Expression rand;
    private Continuation cont;
    App1Continuation (Expression rand, Continuation cont)
    {
	this.rand = rand;
	this.cont = cont;
    }
    public Task invoke (Function val)
    {
	return new App1Task (val, rand, cont);
    }
}

public class ApplicationExpression extends Expression {
    // ApplicationExpression is an expression that represents an
    // application of two Unlambda Functions.
    private Expression rator, rand;
    public ApplicationExpression (Expression rator, Expression rand)
    {
	this.rator = rator;
	this.rand = rand;
    }
    public Task eval (Continuation cont)
    {
	Continuation ncont = new App1Continuation (rand, cont);
	return new EvalTask (rator, ncont);
    }
}

public class ParseException extends Exception {
    // This is thrown by the Parser when it doesn't understand
    // something.
    public ParseException () { super (); }
    public ParseException (String s) { super (s); }
}

public class Parser {
    // The Parser's main method, Parser.parse(), reads characters
    // (from the specified InputStream) and returns the Unlambda
    // expression they represent.
    java.io.InputStream input;
    public Parser (java.io.InputStream input)
    {
	this.input = input;
    }
    public Expression parse ()
	throws java.io.IOException, ParseException
    {
	int ch;
	do {
	    ch = input.read ();
	    if ( ch == '#' )
		while ( ch != '\n' && ch != -1 )
		    ch = input.read ();
	} while ( ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t' );
	if ( ch == '`' )
	    {
		Expression rator, rand;
		rator = parse ();
		rand = parse ();
		return new ApplicationExpression (rator, rand);
	    }
	else if ( ch == 'i' || ch == 'I' )
	    return new FunctionExpression (new IFunction ());
	else if ( ch == 'k' || ch == 'K' )
	    return new FunctionExpression (new KFunction ());
	else if ( ch == 's' || ch == 'S' )
	    return new FunctionExpression (new SFunction ());
	else if ( ch == 'v' || ch == 'V' )
	    return new FunctionExpression (new VFunction ());
	else if ( ch == 'd' || ch == 'D' )
	    return new FunctionExpression (new DFunction ());
	else if ( ch == 'c' || ch == 'C' )
	    return new FunctionExpression (new CFunction ());
	else if ( ch == 'e' || ch == 'E' )
	    return new FunctionExpression (new EFunction ());
	else if ( ch == 'r' || ch == 'R' )
	    return new FunctionExpression (new DotFunction ('\n'));
	else if ( ch == '.' )
	    {
		int ch2 = input.read ();
		if ( ch2 == -1 )
		    throw new ParseException ("Unexpected end of file");
		return new FunctionExpression
		    (new DotFunction ((char) ch2));
	    }
	else if ( ch == '@' )
	    return new FunctionExpression (new AtFunction ());
	else if ( ch == '?' )
	    {
		int ch2 = input.read ();
		if ( ch2 == -1 )
		    throw new ParseException ("Unexpected end of file");
		return new FunctionExpression
		    (new QuesFunction ((char) ch2));
	    }
	else if ( ch == '|' )
	    return new FunctionExpression (new PipeFunction ());
	else if ( ch == -1 )
	    throw new ParseException ("Unexpected end of file");
	else
	    throw new ParseException ("Character not recognized");
    }
}

class FinalTask extends Task {
    // FinalTask throws the ProgramOverException so as to signify the
    // end of the execution of the Unlambda program.  This Task is
    // produced by the FinalContinuation.
    public Task run ()
	throws ProgramOverException
    {
	throw new ProgramOverException ("Execution terminated.");
    }
}

class FinalContinuation extends Continuation {
    // FinalContinuation waits for the completion of the entire
    // execution of an Unlambda program.  val is the final value of
    // the evaluation (this value is ignored).
    public Task invoke (Function val)
    {
	return new FinalTask ();
    }
}

public class UsageException extends Exception {
    // This is thrown when the command lines argument don't make
    // sense.
    public UsageException () { super (); }
    public UsageException (String s) { super (s); }
}

public class Execute {
    // Execute.main() is the evaluator's main entry point.
    public static void main (String[] args)
	throws java.io.IOException, java.io.FileNotFoundException,
	       ParseException, UsageException
    {
	Parser parser;
	if ( args.length == 0 )
	    parser = new Parser (java.lang.System.in);
	else if ( args.length == 1 )
	    parser = new Parser
		(new java.io.FileInputStream (args[0]));
	else throw new UsageException ("Expected zero or one argument");
	AtFunction.input = java.lang.System.in;
	DotFunction.output = java.lang.System.out;
	Expression expr = parser.parse ();
	Continuation finis = new FinalContinuation ();
	Task task = new EvalTask (expr, finis);
	try {
	    // This is the main evaluation loop.
	    while ( true )
		task = task.run ();
	}
	catch ( ProgramOverException e ) {
	    // So what?
	}
    }
}