# Implementing primitive recursive functions in a programming language

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.

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) 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? – Raphael Nov 8 '15 at 9:40
• See here for a draft of the book: web.eecs.umich.edu/~bchandra/courses/papers/Turbak_6.821/…. – Yuval Filmus Nov 8 '15 at 9:48
• @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. – meguli Nov 8 '15 at 10:09

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)