Recursive Functions of Symbolic Expressions and Their Computation by Machine

In this article, we first describe a formalism for defining functions recursively. We believe this formalism has advantages both as a programming language and as a vehicle for developing a theory of computation. Next, we describe S-expressions and S-functions, give some examples, and then describe the universal S-function apply which plays the theoretical role of a universal Turing machine and the practical role of an interpreter. Then we describe the representation of S-expressions in the memory of the IBM 704 by list structures similar to those used by Newell, Shaw and Simon, and the representation of S-functions by program. Then we mention the main features of the LISP programming system for the IBM 704. Next comes another way of describing computations with symbolic expressions, and finally we give a recursive function interpretation of flow charts.

Mak Kolybabi is the founder of Papers We Love Winnipeg, co-founder of the SkullSpace Winnipeg hackerspace, and co-founder of the BSides Winnipeg conference. In the past few years, Mak has written multi-day workshops that teach threat modeling, cryptography, and secure coding practices to international audiences, and has delivered full-day training on SSL/TLS and Wireshark at SharkFest 2013 at Berkeley. He currently works full-time as a penetration tester while pursuing his M.Sc. in Computer Science. There’s always a plush squirrel in his pocket.