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?

Improve this question
7
  • Probably better to ask or search at cstheory.stackexchange.com Commented Jan 3, 2012 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). Commented Jan 3, 2012 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. Commented Jan 3, 2012 at 16:55
  • 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. Commented Jan 3, 2012 at 17:04
  • 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 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)))). Commented Jan 3, 2012 at 18:48

3 Answers 3

Reset to default
7

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This seems like the best answer for this question. All the others are way above a beginner's head.
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.

Improve this answer

Comments

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.

Improve this answer

4 Comments

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: yes, but again, you wouldn't have a real Lisp since sexprs would be impossible to print.
you can define your own pretty-printer (and your own parser, to produce Church-encoded lists instead of the "native" Lisp lists).
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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.