CODEWITHSUNDEEP
schemesicp
Leonard
Leonard

Reputation: 13747

How do i invoke Scheme number functions from SICP

In SICP, (ex 2.6) the following functions are described as ways of 'getting by without numbers'. I'm scratching trying to understand this. As a starting point, how do these functions get invoked? Can I actually apply them in some way where the output will be 1? (Or any other number?)

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

My initial attempts haven't been successful: 

Welcome to DrScheme, version 4.1.5 [3m].
Language: Simply Scheme; memory limit: 128 megabytes.
> (add-1 (zero))
. . procedure zero: expects 1 argument, given 0
> (add-1 zero)
#<procedure>
> (add-1 1)
#<procedure>
> ((add-1 1))
. . #<procedure>: expects 1 argument, given 0
>

Upvotes: 1

Views: 680

Answers (3)

user1651640
user1651640

Reputation: 181

(define (as-primitive-num church-num)
    (define (inc a) (+ a 1))
    ((church-num inc) 0))

;testing:
(define one (add-1 zero))
(define two (add-1 one))

(display (as-primitive-num one)) (newline)
(display (as-primitive-num two)) (newline)

and the output:

    1
    2

Upvotes: 0

Nathan Kitchen
Nathan Kitchen

Reputation: 4867

These functions that represent numbers are called Church numerals (as SICP states). Their existence means that you can define a system of computation (such as the lambda calculus) without having numbers as first-class objects--you can use functions as the primitive objects instead. This fact is mainly of theoretical interest; Church numerals are not a good choice for practical computation.

You can see the correctness of your definitions of Church numerals by applying them with other objects as arguments. When you apply a Church numeral representing n to a function f, you get another function that applies f to its argument n times, e.g., f(f(f(x))) for n=3.

> (define (double x) (* 2 x))
> (zero double)
#<procedure>
> ((zero double) 1)
1
> ((zero double) 100)
100
> (define one (add-1 zero))
> ((one double) 1)
2
> ((one double) 100)
200
> (define (cons-a x) (cons 'a x))
> ((zero cons-a) '())
()
> (((add-1 one) cons-a) '(1 2 3))
(a a 1 2 3)

Upvotes: 9

Javier
Javier

Reputation: 62583

this is the original lambda calculus it doesn't produce numbers, it totally replaces the number type with functions.

so, you have a 'zero' function, and if you call add-1 to it, you won't get 1, you get another function that represents 1. the point is that the functions produced comply with the basic arithmetic axioms, so they're equivalent to natural numbers

Upvotes: 3

Related Questions