Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!caen!uwm.edu!linac!att!ucbvax!dog.ee.lbl.gov!elf.ee.lbl.gov!torek From: torek@elf.ee.lbl.gov (Chris Torek) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <13189@dog.ee.lbl.gov> Date: 14 May 91 20:29:26 GMT References: <30275@dime.cs.umass.edu> <1991May14.054813.18427@sbcs.sunysb.edu> Reply-To: torek@elf.ee.lbl.gov (Chris Torek) Organization: Lawrence Berkeley Laboratory, Berkeley Lines: 28 X-Local-Date: Tue, 14 May 91 13:29:26 PDT >Joseph Allen: > No, it can be done! Really! Just don't allow loops, gotos or > recursion. Now who wants to write a compiler in a language with > these restrictions? In article rockwell@socrates.umd.edu (Raul Rockwell) writes: >Well, you can allow loops as long as they can guaranteed to be >bounded. ... > >I suppose such a thing could be quite instructive. Ask the question >"how useful is this language when I remove everything which >potentially prevents halting?". Languages without loops can indeed be useful. One such example is the interpreter inside BPF, the Berkeley Packet Filter. The `language' is in effect an accumulator machine with packet-memory operations and a small auxiliary memory. The compiler takes packet matching specifications (`tcp port 25') and emits load-and-compare operations to decide whether the packet should be copied. The interpreter allows only forward branches and has no call instruction, so it is not possible to create a loop. BPF is very useful in its particular problem domain. It is not much good as a general purpose programming language. :-) -- In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427) Berkeley, CA Domain: torek@ee.lbl.gov