3

I read in the book Land of Lisp that the lambda function is the only built-in function. However I don't really understand how that is possible because I thought you would at least need one command for addition, one for comparing numbers, and one for moving data from one variable to another. I was wondering if someone could explain to me how lisp does it. I'm not a mathematician so if it is possible could you also explain it without a whole lot of complex math?

Joshua Taylor
  • 84,998
  • 9
  • 154
  • 353
Noah
  • 351
  • 2
  • 9
  • Probably better to ask or search at http://cstheory.stackexchange.com/ – zaf Jan 03 '12 at 16:51
  • 5
    'I read in the book "land of lisp" that the lambda function is the only built-in function.' Can you cite the whole sentence (or passage) that you think says that? That statement seems pretty strange to me. `lambda` is not a function, it's a special form. And there's certainly built-in functions in every lisp, that couldn't be defined by the user if they didn't exist (like for example the + function, as you mentioned). What I think the book might have said that lambda is the only way to **define** functions that is built into the language (e.g. `defun` is just a macro built on top of lambda). – sepp2k Jan 03 '12 at 16:54
  • 1
    Lambda calculus is a Turing-complete system, so yes, you can do everything with it. But not in Lisp with its eager evaluation semantics - there you'll need at least an `if` or something similar. – SK-logic Jan 03 '12 at 16:55
  • @zaf: I really don't see how this has anything to do with theoretical computer science (let alone research-level theoretical computer science). – sepp2k Jan 03 '12 at 16:57
  • 2
    @SK-logic Yes, but then we're talking about a different language. You can certainly write a function that adds two church-encoded numbers using lambdas only. But you couldn't write a function that adds two Clojure-numbers (or two Common Lisp-numbers, or two Scheme-numbers) if one weren't already built-in. – sepp2k Jan 03 '12 at 17:04
  • @zaf: cstheory is for *research-level* questions. – hugomg Jan 03 '12 at 18:19
  • 2
    @SK-logic I can't imagine why you'd *need* an `if`: you can use lambdas to delay evaluation. A lovely example of rebuilding a language with just lambdas is at http://experthuman.com/programming-with-nothing#booleans - basically define `true` as `(lambda (x y) x)` and `false` as `(lambda (x y) y)`. Then you can write a non-eager `if` as `(lambda (test then else) (funcall (funcall test then else)))` (or in Clojure, `(fn [test then else] ((test then else)))`). – amalloy Jan 03 '12 at 18:48

3 Answers3

6

What 'Land of Lisp' is saying here is not that lambda is the only Lisp primitive, but rather that (according to Alonzo Church's lambda calculus, which Lisp has theoretical underpinnings) one could implement the rest of Lisp with lambda, as the lambda calculus is equivalent to a Universal Turing Machine.

For most practical applications, lambda is used to define anonymous functions.

Cosman246
  • 881
  • 6
  • 5
5

That's a difference between theory and a real programming language.

Lisp took ideas from Lambda Calculus, but does not implement it. The lambda calculus describes a system to do calculation using functions. It is useful to understand Lambda Calculus, but you won't program in pure Lambda Calculus when you use Lisp.

As a programming language, Lisp has all kinds of data types and operations for those (numbers, strings, characters, cons cells, symbols, functions, ...).

Compare that to Turing Machines and something like the programming language C.

Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
3

You're confusing some things here. lambda is not a function. It's a construct built into the Lisp language.

Any practical Lisp will have lots of built-in functions; it needs at least car and cdr to pick lists apart and some primitive arithmetic functions cannot be defined in terms of other functions.(*) Also, the "non-functional" parts of Lisp such as setf need some primitives.

[*] You can do Church arithmetic in Lisp, but then you can't pretty-print the results due to Lisp's type system but whether you can properly print the result depends on the Lisp variant.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 2
    If you're using the Church encoding for everything, you won't need car and cdr (i.e., you can use Church pairs instead). – SK-logic Jan 03 '12 at 16:57
  • @SK-logic: yes, but again, you wouldn't have a real Lisp since sexprs would be impossible to print. – Fred Foo Jan 03 '12 at 17:00
  • 4
    you can define your own pretty-printer (and your own parser, to produce Church-encoded lists instead of the "native" Lisp lists). – SK-logic Jan 03 '12 at 17:04
  • 2
    Also it's well-known how to define `car`, `cdr`, and `cons` from pure lambda calculus - Lisp only provides them because they should be efficient. `(defn cons [x y] (fn [f] (f x y))) (defn car [x] (x (fn [x y] x))) (defn cdr [x] (x (fn [x y] y)))`. This satisfies the only requirement of cons/car/cdr: that `(eq (car (cons x y)) x)` and `(eq (cdr (cons x y)) y)`. – amalloy Jan 04 '12 at 09:38