If Perl is your first programming language, you should probably start with Learning Perl, published by O'Reilly & Associates. Frankly, I would probably suggest following that up with a book specifically on Computer Science. I wish I could recommend one, but I was in your shoes back in about 1981, and my 'upbringing' included high-school Computer Science classes (Apple II Basic, and then Pascal), Byte magazine, 1980's programming books, and later on, college Computer Science classes. So I really don't know what book to recommend anymore for Comp Sci. Knuth is going to be too deep for most mortals just starting out (and mostly even for professionals). ;)

I do believe that after learning the basics of a specific language, learning the basic fundamentals of computer science is more important as a 'next step' than learning more advanced syntactical rules and tricks in said language.

Once you get a bit of of the foundation laid in Computer Science, you can go back to the Perl books, such as Intermediate Perl (O'Reilly), as well as Mastering Algorithms with Perl (O'Reilly). That last book is pretty old (1999), but good algorithms don't change as quickly as languages themselves, so I feel it is still a valuable book to work through.

One should never overlook the value of the Perl POD. perlintro, perlsyn, perlsub, perlreftut, perlretut, and so on. It's free, and it's great.

After that, decide what it is that interests you and dig in! My home node contains a list of books that I have found useful over the years. Most of them are not read-once types of books. After an initial reading, I find them to be helpful when I need to dive back into a topic after some time has passed as well.

Oh, and in case nobody else mentions it to you: Congratulations on asking a fantastic question. Welcome back to the Monastery any time.