Serge D. Mechveliani wrote:
>
> On Sun, Feb 05, 2012 at 01:56:20AM +0100, Ralf Hemmecke wrote:
> > On 02/04/2012 06:13 PM, Serge D. Mechveliani wrote:
> >> [..]
> >>>> dropWhile(p: Character -> Boolean, xs: List Character) :
> >>>> List Character ==
> >>>> empty? xs => xs
> >>>> p first(xs) => dropWhile(p, rest xs)
> >>>> xs
> >>>> Is this more efficient?
> >
> > In the list case I guess using a loop instead of recursive call is a
> > little more efficient.
> >
> > LC ==> List Character
> > dropWhile(p: Character -> Boolean, xs: LC): LC ==
> > while not empty? xs and p first xs repeat xs := rest xs
> > xs
> > [..]
>
> These all things looks rather unusual to me.
> Well, I knew that in C a recursion with a function call costs considerably
> more than an ordinary loop.
> But in Haskell, people do not think of such details. First, because
> there is no plain possibility to write a loop as above.
> Second -- for the sake of a plain style.
> Third -- because this is a matter of a compiler. Under -O, some compilers
> (like Glasgow Haskell) inline the body of each simple enough function
> and produce the optimized code. In particular, the library functions
> `head' and `tail' will be in-lined, and so on.
Spad compiler will inline "simple enough" functions. Unfortunately,
currently this means functions consisting of single operation.
Your version will generate the following Lisp code:
(DEFUN |TTT;dropWhile;M2L;1| (|p| |xs| $)
(COND ((OR (NULL |xs|) (NULL (SPADCALL (|SPADfirst| |xs|) |p|))) |xs|)
('T (SPADCALL |p| (CDR |xs|) (QREFELT $ 8)))))
This may look small and simple, but SPADCALL is an indirect call
and Lisp compiler has no chance to note that there is tail
recursion. In fact, 'QREFELT $ 8' which computes function to call, is
access to a table which is filled in at runtime by rather involved
process. By default in sbcl tail calls resuse stack frame,
so your code uses bounded amount of stack space, but may fail
when using different lisp (or different compiler settings).
Ralf code when compile gives much bigger result:
(DEFUN |TTT;dropWhile;M2L;1| (|p| |xs| $)
(SEQ
(SEQ G190
(COND
((NULL
(COND ((NULL |xs|) 'NIL) ('T (SPADCALL (|SPADfirst| |xs|) |p|))))
(GO G191)))
(SEQ (EXIT (LETT |xs| (CDR |xs|) |TTT;dropWhile;M2L;1|))) NIL (GO G190)
G191 (EXIT NIL))
(EXIT |xs|)))
however, it will probably generate less machine istructions and
run faster. Note that there is only single 'SPADCALL' is Ralf
version.
BTW: When using sbcl based FriCAS
)lisp (disassemble #'|TTT;dropWhile;M2L;1|)
will show you machine instructions generated for given function
(of course you need to replace |TTT;dropWhile;M2L;1| by name
of function you are interested in). Note that normally this
works only after you run the code (one can disassemble only
code that is in memory and after compilation result is on
disc and is loaded into memory when needed).
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
