I am very facinated by the fact that lisp can generate functions on the
fly. But what facinates me even more is where is this chunk of code in
the form of a new function allocated? on the heap, or on the stack, ...
There is something I am missing here. Can someone please explain me
how this works?
<··········@gmail.com> wrote:
+---------------
| I am very facinated by the fact that lisp can generate functions on the
| fly. But what facinates me even more is where is this chunk of code in
| the form of a new function allocated? on the heap, or on the stack, ...
+---------------
On the heap.
Or rather, in one of the heaps, depending on how your specific
implementation's GC works. That is, there might be a heap for
code that is different for the heap used for conses, say.
Or code might go into a (sub)heap that uses mark-and-sweep GC
instead of 2-space-copying, to avoid the need for code
relocation at GC time. That sort of thing.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Thanks Rob. That makes sense. I am usually uncomfortable when
programming in lisp because I cannot tell what the code is going to
look like at run-time. Any suggestions for a book that explains the
compilation / interpretation of lisp code and the lisp runtime ?
sanket.
On Oct 7, 3:59 am, ····@rpw3.org (Rob Warnock) wrote:
> <··········@gmail.com> wrote:+---------------
> | I am very facinated by the fact that lisp can generate functions on the
> | fly. But what facinates me even more is where is this chunk of code in
> | the form of a new function allocated? on the heap, or on the stack, ...
> +---------------
>
> On the heap.
>
> Or rather, in one of the heaps, depending on how your specific
> implementation's GC works. That is, there might be a heap for
> code that is different for the heap used for conses, say.
> Or code might go into a (sub)heap that uses mark-and-sweep GC
> instead of 2-space-copying, to avoid the need for code
> relocation at GC time. That sort of thing.
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
In article <························@b28g2000cwb.googlegroups.com>,
··········@gmail.com wrote:
> Thanks Rob. That makes sense. I am usually uncomfortable when
> programming in lisp because I cannot tell what the code is going to
> look like at run-time. Any suggestions for a book that explains the
> compilation / interpretation of lisp code and the lisp runtime ?
Although you *can* generate code on the fly in Lisp, it's not a very
common thing to do.
The Lisp runtime accomplishes it basically by having a built-in compiler
and dynamic linker.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
<··········@gmail.com> wrote:
+---------------
| I am usually uncomfortable when programming in lisp because I
| cannot tell what the code is going to look like at run-time.
+---------------
Are you "uncomfortable when programming in C or C++ because you
cannot tell what the code is going to look like at run-time"?
If not, then why are you uncomfortable when programming in Lisp?
If so, then what do you do about it in C or C++? Answer: Probably
the same thing people do in Lisp, that is, write a small test case
and see what it compiles into:
> (defun +/2-arg/fast (a b)
(declare (fixnum a b)
(optimize (speed 3) (safety 0)))
(the fixnum (+ a b)))
+/2-ARG/FAST
> (compile *)
; Compiling LAMBDA (A B):
; Compiling Top-Level Form:
+/2-ARG/FAST
NIL
NIL
> (disassemble *)
4850A288: .ENTRY +/2-ARG/FAST(a b) ; (FUNCTION (FIXNUM FIXNUM) FIXNUM)
A0: POP DWORD PTR [EBP-8]
A3: LEA ESP, [EBP-32]
A6: ADD EDX, EDI ; No-arg-parsing entry point
A8: MOV ECX, [EBP-8]
AB: MOV EAX, [EBP-4]
AE: ADD ECX, 2
B1: MOV ESP, EBP
B3: MOV EBP, EAX
B5: JMP ECX
B7: NOP
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
When programming in C/C++, atleast I have a conceptual idea about how
function calls and stacks and heap etc. work.
Its just that I would like to know how things like passing and
returning functions as data, returning multiple values etc happen at
the low level.
But thanks for (disassemble *). I didn't know about it. will
definitely use it from now on.
sanket.
On Oct 8, 1:19 am, ····@rpw3.org (Rob Warnock) wrote:
> <··········@gmail.com> wrote:+---------------
> | I am usually uncomfortable when programming in lisp because I
> | cannot tell what the code is going to look like at run-time.
> +---------------
>
> Are you "uncomfortable when programming in C or C++ because you
> cannot tell what the code is going to look like at run-time"?
> If not, then why are you uncomfortable when programming in Lisp?
>
> If so, then what do you do about it in C or C++? Answer: Probably
> the same thing people do in Lisp, that is, write a small test case
> and see what it compiles into:
>
> > (defun +/2-arg/fast (a b)
> (declare (fixnum a b)
> (optimize (speed 3) (safety 0)))
> (the fixnum (+ a b)))
>
> +/2-ARG/FAST
> > (compile *)
> ; Compiling LAMBDA (A B):
> ; Compiling Top-Level Form:
>
> +/2-ARG/FAST
> NIL
> NIL
> > (disassemble *)
> 4850A288: .ENTRY +/2-ARG/FAST(a b) ; (FUNCTION (FIXNUM FIXNUM) FIXNUM)
> A0: POP DWORD PTR [EBP-8]
> A3: LEA ESP, [EBP-32]
> A6: ADD EDX, EDI ; No-arg-parsing entry point
> A8: MOV ECX, [EBP-8]
> AB: MOV EAX, [EBP-4]
> AE: ADD ECX, 2
> B1: MOV ESP, EBP
> B3: MOV EBP, EAX
> B5: JMP ECX
> B7: NOP
> >
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
On Sun, 08 Oct 2006 03:17:25 -0700, sankymoron wrote:
> When programming in C/C++, atleast I have a conceptual idea about how
> function calls and stacks and heap etc. work.
>
> Its just that I would like to know how things like passing and
> returning functions as data, returning multiple values etc happen at
> the low level.
>
> But thanks for (disassemble *). I didn't know about it. will
> definitely use it from now on.
>
> sanket.
You might find L.i.S.P. interesting:
http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/dp/0521545668
>
> On Oct 8, 1:19 am, ····@rpw3.org (Rob Warnock) wrote:
>> <··········@gmail.com> wrote:+---------------
>> | I am usually uncomfortable when programming in lisp because I
>> | cannot tell what the code is going to look like at run-time.
>> +---------------
>>
>> Are you "uncomfortable when programming in C or C++ because you
>> cannot tell what the code is going to look like at run-time"?
>> If not, then why are you uncomfortable when programming in Lisp?
>>
>> If so, then what do you do about it in C or C++? Answer: Probably
>> the same thing people do in Lisp, that is, write a small test case
>> and see what it compiles into:
>>
>> > (defun +/2-arg/fast (a b)
>> (declare (fixnum a b)
>> (optimize (speed 3) (safety 0)))
>> (the fixnum (+ a b)))
>>
>> +/2-ARG/FAST
>> > (compile *)
>> ; Compiling LAMBDA (A B):
>> ; Compiling Top-Level Form:
>>
>> +/2-ARG/FAST
>> NIL
>> NIL
>> > (disassemble *)
>> 4850A288: .ENTRY +/2-ARG/FAST(a b) ; (FUNCTION (FIXNUM FIXNUM) FIXNUM)
>> A0: POP DWORD PTR [EBP-8]
>> A3: LEA ESP, [EBP-32]
>> A6: ADD EDX, EDI ; No-arg-parsing entry point
>> A8: MOV ECX, [EBP-8]
>> AB: MOV EAX, [EBP-4]
>> AE: ADD ECX, 2
>> B1: MOV ESP, EBP
>> B3: MOV EBP, EAX
>> B5: JMP ECX
>> B7: NOP
>> >
>>
>> -Rob
>>
>> -----
>> Rob Warnock <····@rpw3.org>
>> 627 26th Avenue <URL:http://rpw3.org/>
>> San Mateo, CA 94403 (650)572-2607
--
Lars Rune Nøstdal
http://lars.nostdal.org/
> sanket.You might find L.i.S.P. interesting:http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/dp/0521545668
Thanks! Thats exactly what I was looking for.
sanket.
··········@gmail.com writes:
> When programming in C/C++, atleast I have a conceptual idea about how
> function calls and stacks and heap etc. work.
>
> Its just that I would like to know how things like passing and
> returning functions as data, returning multiple values etc happen at
> the low level.
How many programming languages do you know that provide their own one
page long interpreter? What better conceptual idea can you get than
reading the source of EVAL?
Read SICP!
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html
(cf Chapter 4)
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
<··········@gmail.com> wrote:
+---------------
| When programming in C/C++, atleast I have a conceptual
| idea about how function calls and stacks and heap etc. work.
+---------------
There's an old in-joke that goes: "C programmers know the cost
of everything and the value of nothing; Lisp programmers know
the value of everything and the cost of nothing."[1]
In the immortal words of Dennis Ritchie, "You are not expected
to understand this."[2] At least, not quite yet. ;-} ;-}
But if you keep going with Lisp, you will, eventually.
+---------------
| Its just that I would like to know how things like passing and
| returning functions as data, returning multiple values etc happen
| at the low level.
+---------------
As reasonable-sounding as that question may seem to you, the
reason you aren't going to get a simple answer to it is that
almost every Lisp system does it slightly (or *completely*!!)
differently, often (but not always) for completely valid reasons
having to do with tradeoffs the implementation has made between
performance, cross-platform portability, need (or not) for ease
of FFI with other languages, style of GC, and many, many other
design dimensions.
As others have advised, books such as Queinnec's "Lisp In Small
Pieces", or SICP, or Norvig's PAIP -- especially the chapters
in each on compiling and virtual machine design -- are well
worth the effort of studying if you're really serious about
the subject.
Object representations are one of the areas where various Lisp
implementations vary most widely. David Gudeman's 1993 (but still
very useful) survey of object representations & tagging is well
worth reading:
ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/typeinfo.ps.gz
"Representing Type Information in Dynamically Typed Languages"
But if you just want a rough mental performance model, you won't go
very wrong if you consider that each of these actions [at least, in
compiled code] has a roughly the same (small) cost:
- A function call.
- A dynamic (special) binding.
- Allocating a heap object ("consing"). [Number of allocations
is usually much more important than object size. Usually.]
- One iteration of a loop.
- The READ'ing of one token [if READ is used at run-time].
Of course, evaluating in-lined accessor functions [when the
compiler has been given enough information to do so] is cheaper
than full-calling a generic version, but you can/should ignore
that for now.
In fact, an even simpler approximation [still surprisingly
accurate] is:
- A function call has fixed cost.
- *Everything* is a function call. ;-}
And at this stage, you're probably better off using the built-in
TIME macro than DISASSEMBLE to figure out how long things take.
Probably the very first thing you're going to discover is that
in most implementations there's a *LOT* of difference between
running code interpreted and compiled:
> (defun delay (n)
(dotimes (i n)))
DELAY
> (time (delay 1000000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 3.97f0 seconds of real time
; 3.917419f0 seconds of user run time
; 0.00228f0 seconds of system run time
; 7,364,217,098 CPU cycles
; [Run times include 0.16f0 seconds GC run time]
; 0 page faults and
; 48,027,344 bytes consed.
;
NIL
>
Yikes! 7364 CPU clock cycles per iteration. Of course, compiling
makes things a *lot* better:
> (compile 'delay)
; Compiling LAMBDA (N):
; Compiling Top-Level Form:
DELAY
NIL
NIL
> (time (delay 1000000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.01f0 seconds of real time
; 0.012837f0 seconds of user run time
; 0.0f0 seconds of system run time
; 25,088,483 CPU cycles
; 0 page faults and
; 0 bytes consed.
;
NIL
>
Hmmm... That time's too small to be reliable, so crank up
the number of iterations:
> (time (delay 100000000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 1.22f0 seconds of real time
; 1.203355f0 seconds of user run time
; 0.0f0 seconds of system run time
; 2,258,783,996 CPU cycles
; 0 page faults and
; 0 bytes consed.
;
NIL
>
Just over 22 CPU cycles/step. Even this can be *substantially*
improved if the compiler can be told when it's safe to use
trickier/simpler code:
> (defun delay (n)
(if (fixnump n)
(locally
(declare (fixnum n) (optimize (speed 3) (safety 0)))
(dotimes (i n)))
(dotimes (i n))))
> (compile 'delay)
; Compiling LAMBDA (N):
; Compiling Top-Level Form:
DELAY
NIL
NIL
> (time (delay 500000000))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 0.56f0 seconds of real time
; 0.533203f0 seconds of user run time
; 0.006685f0 seconds of system run time
; 1,026,612,414 CPU cycles
; 0 page faults and
; 0 bytes consed.
;
NIL
>
Only a hair over 2 CPU cycles/step. Depending on the CPU,
even C might not be able to do better.
-Rob
[1] The second part is one of the famous Alan Perlis epigrams,
#55 at <http://www.cs.yale.edu/quotes.html>; the complementary
first half seems to have arisen spontaneously among the
collective consciousness of The Internet:
http://ars.userfriendly.org/users/read.cgi?id=23837&tid=110389
http://lambda-the-ultimate.org/node/663#comment-6205
http://groups.google.com/group/comp.lang.lisp/msg/8f0854e6cf820d33
http://developers.slashdot.org/comments.pl?sid=50632&cid=5082205
http://www.j-bradford-delong.net/movable_type/2004_archives/000941.html
http://ll2.ai.mit.edu/talks/proebsting.ppt
http://www.info.ucl.ac.be/~pvr/potpourri.html
http://www.c2i.ntu.edu.sg/AI+CI/Humor/aiquotes_L.html
A related popular quote states:
C is the high-level language that combines the power
of assembler with the ease of use of assembler.
[2] http://cm.bell-labs.com/cm/cs/who/dmr/odd.html
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
··········@gmail.com writes:
> Thanks Rob. That makes sense. I am usually uncomfortable when
> programming in lisp because I cannot tell what the code is going to
> look like at run-time. Any suggestions for a book that explains the
> compilation / interpretation of lisp code and the lisp runtime ?
I think this is the wrong approach. What you need to do is understand
the conceptual model of what the lisp semantics imply. In essence you
need to understand the virtual machine that lisp and its sementics
provide. Understanding the implementation details is generally
unnecessary and often counter-productive, especially since the actual
implementation can vary depending on the lisp vendor and even the
underlying architecture.
For example, the way to understand cons cells and lists is at the level
of the box-and-pointer diagrams, not in terms of the layout of a cons
cell in memory. The latter can be done in one of several ways, and
depending on OS and hardware, has not always been done the same way.
Sometimes an entire cons cell fits into a single machine word, sometimes
it takes two such words. Sometimes the type information is encoded in
the lower order bits, other times not. But knowing that doesn't help
you understand the important notions of structure sharing and other list
properties the way the box-and-pointer view does.
So, to answer the original question: It doesn't matter where lisp
allocates the function code's storage. All you need to know is that the
code is sufficiently persistent that it can be used when in-scope and
accessible. It may be on the heap, it may be on the stack (given
appropriate declarations), it may be in some other data structure.
--
Thomas A. Russ, USC/Information Sciences Institute
Thank you all for the informative replies!
I will try to concentrate more on the conceptual model of lisp, and not
the low level details.
And will definitely check out (time) and (disassemble) to understand
performance of my code.
One question though: I have heard that lisp code can be compiled into
a stand-alone x86 executable. But how does the GC work then? In C# or
Java for example, code is compiled to the language of the underlying
runtime (bytecodes). And the runtime takes care of GC. So does a lisp
stand-alone executable need any run-time, or does it have GC code
built-in?
...off to becoming a lisp fan.
sanket.
··········@gmail.com writes:
> Thank you all for the informative replies!
>
> I will try to concentrate more on the conceptual model of lisp, and not
> the low level details.
>
> And will definitely check out (time) and (disassemble) to understand
> performance of my code.
>
> One question though: I have heard that lisp code can be compiled into
> a stand-alone x86 executable. But how does the GC work then? In C# or
> Java for example, code is compiled to the language of the underlying
> runtime (bytecodes). And the runtime takes care of GC. So does a lisp
> stand-alone executable need any run-time, or does it have GC code
> built-in?
You are still worrying about low level stuff. It just happens!
Now, the short answer is that yes, there's a run-time library, like in
C or any other programming language (but possibly barebones
assembler).
A slightly longer answer would be that there are broadly two kinds of
garbage collectors: precise garbage collectors and conservative
garbage collectors.
Conservatives garbage collectors scan the memory and whatever bit
pattern that looks like a pointer is considered to be a pointer to
some live memory block. These GC don't need to know anything about
the program or the type of the data, but some memory might not be
collected just because there's some random bit pattern in the memory
that looks like a pointer to it. See for example BoehmGC.
Precise garbage collectors on the other hand need to know the type of
the data to be able to locate precisely the pointers. This can be
done statically or dynamically, both with the help of the compiler.
Dynamically, the type of the data is recorded along with the data: we
have type tags.
For the long answer, read the sources of various implementations.
--
__Pascal Bourguignon__ http://www.informatimago.com/
CONSUMER NOTICE: Because of the "uncertainty principle," it is
impossible for the consumer to simultaneously know both the precise
location and velocity of this product.
In article <·······················@b28g2000cwb.googlegroups.com>,
··········@gmail.com wrote:
> So does a lisp
> stand-alone executable need any run-time, or does it have GC code
> built-in?
Of course it needs a run-time library. Forget about GC, where do you
think all the built-in functions like OPEN, MEMBER, etc. live?
The CONS function is also in the runtime library (just as malloc() is in
the C runtime library), and GC is just part of the implementation of
that function (as well as other object allocators like MAKE-ARRAY,
MAKE-INSTANCE, etc.).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin <······@alum.mit.edu> writes:
> > So does a lisp
> > stand-alone executable need any run-time, or does it have GC code
> > built-in?
>
> Of course it needs a run-time library.
But (of course, again) this library doesn't necessarily have to be
installed as a separate component, but can be part of the executable
(I think this might have been the OPs concern).
--
(espen)
In article <··············@vestre.net>, Espen Vestre <·····@vestre.net>
wrote:
> Barry Margolin <······@alum.mit.edu> writes:
>
> > > So does a lisp
> > > stand-alone executable need any run-time, or does it have GC code
> > > built-in?
> >
> > Of course it needs a run-time library.
>
> But (of course, again) this library doesn't necessarily have to be
> installed as a separate component, but can be part of the executable
> (I think this might have been the OPs concern).
Just like statically-linked executables in other languages.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***