[Solved]: Implementing primitive recursive functions in a programming language

Problem Detail: 

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).

Asked By : meguli

Answered By : Yuval Filmus

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)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49213

3.2K people like this

 Download Related Notes/Documents