I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input language. This one also has a conditional command and a subroutine-like struct. So, it seemed like it could implement a looping construct like while. But later, the book gives proof that POSTFIX is not able to encode infinite loops, programs always terminate.
In an exercise, the book wants me to implement a factorial program in POSTFIX, if possible. I tried and failed miserably for hours. I looked up on primitive recursive functions, which factorial is one. Found a language called LOOP, designed by Uwe Schöning that can compute only the primitive recursive functions. I tried implementing in POSTFIX a looping construct that always terminates but could not do it. Because the language does not have any naming or abstraction facilities, I could not see how I can do it.
What I ask is this:
Using the POSTFIX definition given on the below link, can someone implement a language construct that can be used to implement primitive recursive functions, like implementing a looping construct that always terminates? Or give a proof that it is not possible maybe.
Note: There is a draft of the book (thanks @YuvalFilmus) where you can find the description of POSTFIX language (section 1.4, pp5).
-
1$\begingroup$ 1) Please give a full reference of the book you are reading (at least title, authors, year, publisher). 2) How long is the definition of POSTFIX? Can you give it here? $\endgroup$Raphael– Raphael2015年11月08日 09:40:32 +00:00Commented Nov 8, 2015 at 9:40
-
1$\begingroup$ See here for a draft of the book: web.eecs.umich.edu/~bchandra/courses/papers/Turbak_6.821/…. $\endgroup$Yuval Filmus– Yuval Filmus2015年11月08日 09:48:59 +00:00Commented Nov 8, 2015 at 9:48
-
$\begingroup$ @Raphael POSTFIX is a very small language but still can be long to fit in a stackexchange question. So the question has a link to online draft version of the book now. Section 1.4 talks about the POSTFIX. $\endgroup$meguli– meguli2015年11月08日 10:09:29 +00:00Commented Nov 8, 2015 at 10:09
1 Answer 1
You can prove by induction that the number of instructions executed by any given program is bounded (essentially since no command can create instructions). In particular, the number of arithmetic instructions executed by a program is bounded. This means that the output of a univariate function is polynomially bounded. Since the factorial function is not polynomially bounded, you cannot compute factorial.
If, however, we add a pget instruction which is similar to nget but gets a subroutine rather than a number then we can compute factorial, for example with the following program:
(postfix 1 1 (3 nget 3 nget mul 4 nget 1 sub swap 2 nget (3 pget 1 pget exec) () sel exec) 1 pget exec)
-
$\begingroup$ By "bounded" you mean by a constant in the program length? $\endgroup$Raphael– Raphael2015年11月08日 12:10:19 +00:00Commented Nov 8, 2015 at 12:10
-
$\begingroup$ I just mean bounded. For every program it is bounded by a constant. By taking a maximum over all programs of some length, you can get a constant depending only on the length. $\endgroup$Yuval Filmus– Yuval Filmus2015年11月08日 12:25:46 +00:00Commented Nov 8, 2015 at 12:25
-
$\begingroup$ I can understand that without pget, I always end up with constant number of arithmetic operations, so the output always will be polynomially bounded. This does not mean we can compute all polynomially bounded functions, right? I can't see how we can do sorting, for example, without pget and sorting is polynomially bounded. $\endgroup$meguli– meguli2015年11月08日 12:52:55 +00:00Commented Nov 8, 2015 at 12:52
-
$\begingroup$ I never said you can compute all polynomially bounded functions. Indeed, some of them are not computable at all! $\endgroup$Yuval Filmus– Yuval Filmus2015年11月08日 12:55:42 +00:00Commented Nov 8, 2015 at 12:55
Explore related questions
See similar questions with these tags.