Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Who's a thief? -- the follow up

by sleepingsquirrel (Hermit)
on Jan 14, 2005 at 17:09 UTC ( #422321=note: print w/replies, xml ) Need Help??


in reply to Who's a thief? -- the follow up

For inspiration on prolog in perl, you might want to take a look at chapter 24 of Paul Graham's On Lisp. He creates an embedded prolog-like language in about 200 lines of Common Lisp. I'd be willing to bet that a Perl implementation wouldn't be too much longer.


-- All code is 100% tested and functional unless otherwise noted.

Replies are listed 'Best First'.
Re^2: Who's a thief? -- the follow up
by Ovid (Cardinal) on Jan 14, 2005 at 17:15 UTC

    He does that in Chapter 15 of ANSI Common Lisp, but I never checked it out. Thanks for the pointer. I tried working through the implementation in Structure and Interpretation of Computer Programs, but it quickly got a bit too hairy for me. I'll look at Paul Graham's version more closely, but one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/ Lisp and Scheme don't have this problem.

    Cheers,
    Ovid

    New address of my CGI Course.

      ...one problem that happens with larger systems like this is the systems tend to rely heavily on recursion and this is not Perl's strength :/
      You're not giving perl enought credit for what it can do. The following program executes in under 9 seconds on my (1GB) machine.
      #!/usr/bin/perl -w print deep(2_500_000); sub deep { $_[0]>0 ? deep($_[0]-1) : "done\n"; }
      ...and I can calculate the 36th fibonacci number using the simplistic algorithm below in about a minute. It ends up calling "fib" over 48 million times.
      #!/usr/bin/perl -w $count = 0; my $n = ($ARGV[0] < 1) ? 1 : $ARGV[0]; print fib($n)."\ncount = $count\n"; sub fib { $count++; $_[0]<2 ? 1 : fib($_[0]-2) + fib($_[0]-1) }


      -- All code is 100% tested and functional unless otherwise noted.

        As soon as I tried your "deep" program, I immediately got a "deep recursion" error. I've a 1.6 GHz machine with 640 megs of RAM. I don't know how you could have run that. Every time Perl enters a sub (normally), it creates a new stack frame and this quickly eats memory.

        On my machine, it pretty much ground the box to a halt after about 1.5 million iterations.

        Cheers,
        Ovid

        New address of my CGI Course.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://422321]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (10)
As of 2019-10-21 21:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Notices?