Recursive Functions of Symbolic Expressions and Their Computation by Machine

Title: Recursive Functions of Symbolic Expressions and Their Computation by Machine

Summary: The original Lisp paper

Field: Programming Language Theory

Author: John McCarthy

Published: April 1960

Abstract:

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.

Presenter Bio:

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.