A recent c.l.l thread was talking about what maximum list size can be held
in a 32 bit lisp. The idea that lists have some relation with pointers or
machine words is very... C(asm even) oriented IMO.
Here is a rather cool way to define lists (from my fuzzy recollection of
calculability theory and in particular primitive recursive functions)
Basically you start with the five following functions: 0, +1, projection,
composition, recursion.
With those 5 functions you first define the basic math functions: add, sub,
mul, div, expt, etc.
For instance add would be recursively defined by:
add(0, y) = y
add(n+1, y) = add(n, y+1)
So in Lisp:
(defun add (x y)
(if (= x 0)
y
(add (1- x) (1+ y))))
> (add 5 6)
11
With add and the 5 primitive function, you can define mul then expt for
instance.
Then defining cons is rather easy. Just use 2^x*3^y for instance:
(defun make-cons (x y)
(* (expt 2 x)(expt 3 y)))
(defun get-car (list)
(multiple-value-bind (quotient remainder) (truncate list 2)
(if (= remainder 0)
(1+ (get-car quotient))
0)))
(defun get-cdr (list)
(multiple-value-bind (quotient remainder) (truncate list 3)
(if (= remainder 0)
(1+ (get-cdr quotient))
0)))
Let's test it:
CL-USER 26 > (make-cons 5 9)
629856 ; = (5 . 9)
CL-USER 27 > (get-car 629856)
5
CL-USER 28 > (get-cdr 629856)
9
CL-USER 31 > (make-cons (make-cons 1 2) 3)
7077888
CL-USER 32 > (get-cdr 7077888)
3
CL-USER 33 > (get-cdr (get-car 7077888))
2
Other prime numbers can be used to encode more types:
Rationals: p/q => 5^p*7^q
Characters: 11^char-code
Strings: 13^(list of chars)
...
Predicates: stringp => (= (mod x 13) 0)
...
etc.
In fact those 5 functions are equivalent to a Turing machine so it's
possible to make a full Common Lisp... ;-)
Anyway there is probably already a full version of this somewhere on the
Net.
Not very useful but fun anyway. :)
BTW Don't try this with too big numbers...
Marc
-- The Common Lisp Directory: www.cl-user.net
"Marc Battyani" <·············@fractalconcept.com> writes:
> Then defining cons is rather easy. Just use 2^x*3^y for instance:
>
> (defun make-cons (x y)
> (* (expt 2 x)(expt 3 y)))
The only problem is that to store the 2^32th cons (and just assuming
that all previous conses have values less than 2^32), you need to store:
(expt 2 (expt 2 32))
And obviously, this number fills up the whoe 32-bit address space
itself, so there's no space remaining for the (1- (expt 2 32))
previous conses in the 32-bit address space.
(Just to make sure Ron stays hopeless).
(And I don't see why anybody would want to fork the conversation to
infinite tape mathematically abstract Turing Machines, when the
discussion is about finite address spaces).
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
"Pascal Bourguignon" <···@informatimago.com> wrote
> "Marc Battyani" <·············@fractalconcept.com> writes:
>> Then defining cons is rather easy. Just use 2^x*3^y for instance:
>>
>> (defun make-cons (x y)
>> (* (expt 2 x)(expt 3 y)))
>
> The only problem is that to store the 2^32th cons (and just assuming
> that all previous conses have values less than 2^32), you need to store:
>
> (expt 2 (expt 2 32))
>
> And obviously, this number fills up the whoe 32-bit address space
> itself, so there's no space remaining for the (1- (expt 2 32))
> previous conses in the 32-bit address space.
Thank you for missing the point.
FYI it's called Mathematics and the basic processor to run math is called a
brain. Yours may be limited to 32 bits but for most people it's rather some
kind of biological processor.
> (Just to make sure Ron stays hopeless).
>
> (And I don't see why anybody would want to fork the conversation to
> infinite tape mathematically abstract Turing Machines, when the
> discussion is about finite address spaces).
Missing the point again. If I wanted to take position in that thread I would
have replied to it. So, as you failed infer it alone, let me add that the
recursive functions theory is a calculability theory and that it has little
use, if any, to make a Common Lisp implementation.
Marc
-- The Common Lisp Directory: www.cl-user.net
Marc Battyani wrote:
> BTW Don't try this with too big numbers...
This is what computing is all about.
My naive algorithms for basic math functions cause a stack overflow even
for '(make-cons (make-cons 1 2) 3).
Mark
"nvt" <···@nvt.nl> wrote in message
····················@mid.individual.net...
> Marc Battyani wrote:
>
>> BTW Don't try this with too big numbers...
>
> This is what computing is all about.
> My naive algorithms for basic math functions cause a stack overflow even
> for '(make-cons (make-cons 1 2) 3).
This reminds me of the old joke: What is the difference between theory and
practice? - In theory none. ;-)
Did you try to compile the functions? Extend the stack?
You can also define the basic math functions like mul, expt, etc. but not
use them in the next functions. for instance you write an add function but
to make the multiplication, you use the normal add function instead of the
one you defined.
Marc
-- The Common Lisp Directory: www.cl-user.net
Marc Battyani wrote:
> "nvt" <···@nvt.nl> wrote in message
>>Marc Battyani wrote:
>>>BTW Don't try this with too big numbers...
>>This is what computing is all about.
>>My naive algorithms for basic math functions cause a stack overflow even
>>for '(make-cons (make-cons 1 2) 3).
> This reminds me of the old joke: What is the difference between theory and
> practice? - In theory none. ;-)
>
> Did you try to compile the functions?
This helps. BTW I like these kind of experiments.
Mark
"nvt" <···@nvt.nl> wrote
> Marc Battyani wrote:
>> "nvt" <···@nvt.nl> wrote in message
>>>Marc Battyani wrote:
>
>>>>BTW Don't try this with too big numbers...
>
>>>This is what computing is all about.
>>>My naive algorithms for basic math functions cause a stack overflow even
>>>for '(make-cons (make-cons 1 2) 3).
>
>> This reminds me of the old joke: What is the difference between theory
>> and practice? - In theory none. ;-)
>>
>> Did you try to compile the functions?
>
> This helps. BTW I like these kind of experiments.
Great! So we are at least 2. :)
Marc
From: Pierre THIERRY
Subject: Re: A Gödel number Lisp (primitive recursive functions fun)
Date:
Message-ID: <enb9bs$dbn$1@biggoron.nerim.net>
Le Wed, 20 Dec 2006 10:20:04 +0100, Marc Battyani a écrit:
> This reminds me of the old joke: What is the difference between theory
> and practice? - In theory none. ;-)
In a classroom I once saw this:
- La théorie, c'est lorsque rien ne marche, et qu'on sait pourquoi rien
ne marche.
- La pratique, c'est lorsque ça marche, et qu'on ne sait pas pourquoi ça
marche.
- Ici, on allie la théorie et la pratique : rien ne marche et on ne sait
pas pourquoi.
Which should approximately translate to:
- Theory is when nothing works, and you know why nothing works.
- Practice is when it works, and you don't know why it works.
- Here theory and practice are joined: nothing works and we don't know
why.
Experimentally,
Pierre
--
···········@levallois.eu.org
OpenPGP 0xD9D50D8A
On 9693 day of my life Marc Battyani wrote:
> ... (... primitive recursive functions)
>
> Basically you start with the five following functions: 0, +1, projection,
> composition, recursion.
...
> In fact those 5 functions are equivalent to a Turing machine so it's
> possible to make a full Common Lisp... ;-)
They are not: you also need minimization (aka while loop). That's why
they are called *primitive* recursive functions -- functions built
with above 5 functions always terminate, while Turing machines
("unprimitive") do not.
--
Ivan Boldyrev
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
"Ivan Boldyrev" <···············@cgitftp.uiggm.nsc.ru> wrote
> On 9693 day of my life Marc Battyani wrote:
>> ... (... primitive recursive functions)
>>
>> Basically you start with the five following functions: 0, +1, projection,
>> composition, recursion.
> ...
>> In fact those 5 functions are equivalent to a Turing machine so it's
>> possible to make a full Common Lisp... ;-)
>
> They are not: you also need minimization (aka while loop). That's why
> they are called *primitive* recursive functions -- functions built
> with above 5 functions always terminate, while Turing machines
> ("unprimitive") do not.
Right, I forgot this one, which is indeed needed for while loops. Thanks for
the precision. So it's 6 functions.
Marc
-- The Common Lisp Directory: www.cl-user.net
Here you got a version which demonstrates that you can get a list of
any size on Lisp, without having to define any new function, but using
the CL ones:
(defparameter infinite-list (cons 'a nil))
(setf *print-circle* t)
(setf (cdr infinite-list) infinite-list)
CL-USER> (nth 9999999 infinite-list)
A
CL-USER> (nth 18446744073709551616 infinite-list)
A
CL-USER> (nth (expt 2 256) infinite-list)
A
"Javier" <·······@gmail.com> writes:
> Here you got a version which demonstrates that you can get a list of
> any size on Lisp, without having to define any new function, but using
> the CL ones:
>
> (defparameter infinite-list (cons 'a nil))
> (setf *print-circle* t)
> (setf (cdr infinite-list) infinite-list)
>
> CL-USER> (nth 9999999 infinite-list)
> A
> CL-USER> (nth 18446744073709551616 infinite-list)
> A
> CL-USER> (nth (expt 2 256) infinite-list)
> A
Nothing to say about it.
Notice that we were discussing proper lists, not circular lists.
A proper list of length n contains n different cons cells.
A circular list of "length" 1 contains only one cons cells.
(defun circular-list-length (cl)
(loop
:with cells = '()
:for i :from 0
:for current = cl :then (cdr current)
:until (member current cells)
:do (push current cells)
:finally (return i)))
C/USER[633]> (circular-list-length infinite-list)
1
C/USER[636]> (defparameter longer-infinite-list (list 'a 'b 'c 'd))
LONGER-INFINITE-LIST
C/USER[637]> (setf (cdr (last longer-infinite-list)) (cddr longer-infinite-list))
#1=(C D . #1#)
C/USER[638]> (circular-list-length longer-infinite-list)
4
(defun circular-list-handle-length (cl)
(loop
:with loop-entry = (nthcdr (circular-list-length cl) cl)
:for i :from 0
:for current = cl :then (cdr current)
:until (eq loop-entry current)
:finally (return i)))
C/USER[649]> (circular-list-handle-length infinite-list)
0
C/USER[650]> (circular-list-handle-length longer-infinite-list)
2
C/USER[651]> (circular-list-handle-length (cons 'z longer-infinite-list))
3
(defun circular-list-loop-length (cl)
(- (circular-list-length cl) (circular-list-handle-length cl)))
C/USER[653]> (CIRCULAR-LIST-LOOP-LENGTH infinite-list)
1
C/USER[654]> (CIRCULAR-LIST-LOOP-LENGTH longer-infinite-list)
2
C/USER[655]> (CIRCULAR-LIST-LOOP-LENGTH (cons 'z longer-infinite-list))
2
--
__Pascal Bourguignon__ http://www.informatimago.com/
"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
Javier wrote:
> Here you got a version which demonstrates that you can get a list of
> any size on Lisp, without having to define any new function, but using
> the CL ones:
>
> (defparameter infinite-list (cons 'a nil))
> (setf *print-circle* t)
> (setf (cdr infinite-list) infinite-list)
>
> CL-USER> (nth 9999999 infinite-list)
> A
> CL-USER> (nth 18446744073709551616 infinite-list)
> A
> CL-USER> (nth (expt 2 256) infinite-list)
> A
Does anyone here suppose this kind of (ab)use is
worth a compiler's time to notice and "optimize"?
I mean, in theory, it demonstrates that the "smart"
way to implement nth is to cdr down the list with
two locations, one moving twice as fast as the other,
checking for eq'ness of cons cells (and thus detecting
cycles). If eq cons cells are found at the Xth and 2*Xth
entry, we know that there is a cycle of length X or of
some length that divides X with no remainder. Thus we
can take (mod X (- N X)) and find how far past X we must
go to get to the Nth list element (in the above case 0)
without recursing (expt 2 256) times.
While preventing the user from accidentally falling into
a huge loop, this makes nth noticeably slow. Is it worth
it?
It's easy to say "no" because it slows the system down and
a knowledgeable coder would know not to do that. But not
all lisp code results from knowledgeable coding. Some
of it is from macro expansions, autogenerated code, and
other sources which may not be "smart."
And then there's the moral dilemma: if we provide the above
"padded room" definition of nth, are we then honor-bound
to provide unchecked-nth, a version with no safety net, for
coders who know exactly what they are doing, or for the
compiler to substitute in when it can *prove* that there
cannot be a cycle?
Bear
Ray Dillinger wrote:
> Does anyone here suppose this kind of (ab)use is
> worth a compiler's time to notice and "optimize"?
I want to do it all by myself on a real abstract machine.
Mark
Marc Battyani wrote:
> In fact those 5 functions are equivalent to a Turing machine so it's
> possible to make a full Common Lisp... ;-)
> Anyway there is probably already a full version of this somewhere on the
> Net.
If you find one please let us know.
Mark