(thoftware)

A common computer science exercise involves testing whether or not a given word is a palindrome; that is, whether it's the same word if the characters are printed in reverse order. Usually this involves some sort of loop through the characters of the word, while comparing each with the corresponding character starting at the end. Since I've been playing with Python recently, and since Python has such interesting tools for slicing up strings in different ways, I decided to write a program like this in Python to see what I'd come up with.

Of course there are other ways to do this, maybe better ways (see the end of this post); this was just a first attempt. It looks like this:

#! /usr/bin/python 

import sys
# test; is a word a palindrome?

str = sys.argv[1].lower()

if len(str)%2==0:
          if str[:len(str)/2]==str[len(str)/2:][::-1]:
                    print str,"is a palindrome"
          else: print str,"is not a palindrome"
else:
          if str[:len(str)/2]==str[len(str)/2+1:][::-1]:
                    print str,"is a palindrome"
          else: print str,"is not a palindrome"

This is a fairly elementary version of such a program; it will only test single words; that is, you could type a phrase in quotes as an argument, but unless it were character for character (including spaces and punctuation) a palindrome, it would come out false. It's made for nice, simple palindromes like radar, racecar, ogopogo, level, detartrated, or aoxomoxoa.

Looking through the code to see what it does is basically a crash course in how Python allows you to slice up strings. Like many languages, Python automatically indexes a string; so, "hello"[0] would be "h" -- "hello"[4] would be "o".

Slicing works like this:

>>>str="hello"
>>>str[:2]
"he"
>>>str[2:]
"llo"

The actual syntax is technically string[start:finish] -- leaving the start blank will start at 0, and leaving the finish blank will go to the end of the string.

Also, the [::-1] that you would have noticed in the code simply writes a given string in reverse. (Technically, the third value is the "step", so [::-1] is simply saying "step through the entire string backwards".) So in effect, what this program does is compare the first half of a string with the second half reversed, to see if they're the same.

Which brings us to the simpler way to do it: if we can simply reverse a string like that, this whole program could have been:

#! /usr/bin/python

import sys
# test; is a word a palindrome?

str = sys.argv[1].lower()

if str==str[::-1]:
          print str,"is a palindrome"
else:
          print str,"is not a palindrome"

Or, if you wanted to be very succinct:

#! /usr/bin/python

import sys; str=sys.argv[1].lower(); print str==str[::-1]

Okay then. That's enough Python geekery for one night. :-)

Note: the wise among you will chuckle when I admit that, yes, I really did write the longer, ridiculously more complicated version of the program first. I could use this to segue into how the simpler solution to any problem is rarely the first to occur to us, or how easy it is to get caught up in a "solution" (in this case, compare the first half to the reverse of the second half) and miss a simpler solution... but I'll save that for some other day.

Another note: in my defense, my first attempt was probably remembered from a time I solved a problem like this with a for loop... in which case it could actually be more efficient to compare the first half of the string with the second half, because it means you don't need to step through the whole thing.

Yet Another note: yes, this is crossposted from here.

last updated 3 years ago #

Well, obviously, I've been too busy to write much here. I do still like infogami; I should really check to see what new features have been added since I've posted last.

My CSCI 1901 final exam is tomorrow. Time to pull a few more hours of scheme refresher time....

last updated 3 years ago #

So you have your standard list; it looks something like (1 2 3 4 5). Sooner or later, you're going to have a list like (((1 2) ((3 4) 5) 6) 7), or maybe worse, and you're going to want to look through it for something(s). At first, it seems as though this might get very complicated. Can you write a simple procedure to search through it?

Of course you can. This scenario will come up a lot, probably, and of course there is more than one way to do it. This is the way I like to solve this sort of problem.

Let's say I have the list of lists I wrote in the first paragraph, and I want to check it to see if it has the number 3 in it. What should I do?

(define (look-for-three tree)
  (cond ((null? tree) #f)
        ((not (pair? tree)) (if (= tree 3) #t #f))
        (else (or (look-for-three (car tree)) 
                  (look-for-three (cdr tree))))))

A little explanation; even if you don't write Scheme, the define and procedure definition probably seem sensible enough. cond is not too difficult, either; each line is an expression, followed by another which is evaluated iff the first one is true, and concluding with an else. The first case looks to see if our list is empty; if so, it can't possibly have a three in it, so it returns false (#f). The next two lines do all the real work.

The second case checks to see if the tree is not a pair. Since lists in Scheme are what you might call linked lists, each element is a pair, the second part of which simply points to the next element. So if this line is true, we've reached what Scheme calls and atom, roughly analogous to a scalar in Perl. It's a single element, in other words. Now we check to see if it's a three or not; return true if it is, false if it isn't.

Finally, we just have the case where we are looking at a list: now we just make a recursive called to search the first element ( the car which could be a list, or not) and the rest of the tree (the cdr). If either portion has a three, ever, we want to return #t, which is why we used or at the beginning.

There are other ways to do this; I'd suggest finding whichever way makes the most sense to you and using it consistently. Have fun.

last updated 3 years ago #

So we were talking about set!, which will re-assign a variable (or... anything) without having to just define it over again. Naturally, this led to talk about pointers, and that there was not a native implementation of pointers (like C) in Scheme.

This was interesting. I decided to check it out.

So, I tried the simplest example possible:

>(define b 100)
b

>(define (foo n) (set! n (1+ n)))
foo

>(foo b)

>b
100

Sure enough, as expected, b does not change.

I recalled that (lambda () b) should return the memory address of b... what about that?

>(foo (lambda () b))

>b
100

Nope; still didn't change b. Hmm.

Then, as a weird experiment, I thought, what if I tried to actually assign something to a memory address? Like...

>(define (lambda () q) 100)

Some of you are already laughing at me. Yes, I actually typed that into the interpreter... If you take another look at it, what I actually just did was redefine lambda.

It is amazing the things that stop working when you redefine lambda.

quit no longer worked, for example... ;-)

Moral: Watch what you type, and don't mess with lambda.

last updated 3 years ago #

You could say that if you have to ask why Scheme is fun, you probably won't care much for the answer; but hopefully that's not the case, or else a post like this is in vain.

You could also accuse that if I'm writing about Scheme at all, it's probable that I'm just a student, who is only using Scheme because the instructor, cluefully, chose a book like the Structure and Interpretation of Computer Programs by Abelson, Sussman and Sussman. That would be more or less correct; albeit, I'd venture to guess that a lot of Scheme fans were introduced to it by a similar class using that work, so I don't think that disqualifies.

More to the point: Why is Scheme fun?

In particular, one might ask, if you consider programming to be "fun", wouldn't it be fun in any language? The answer to that has a great deal to do with both your attitude, and what exactly it is that you're trying to accomplish... in any case, writing a simple program to accept command-line input in Java is not fun by most definitions of the word. Sure, if you enjoy solving problems, you might enjoy solving them in any computer programming language. If you're an artist, you might also enjoy creating pictures by stacking enormous multi-colored boulders into a configuration on a hillside and then flying a helicopter over it so you can observe what you've created... but most likely you'd prefer a pencil, or a crow quill pen, or a Winsor-Newton #2 brush and ink. If you're a musician, you may be able to appreciate the sounds you can make with a kazoo... but given half a chance, chances are you'd go to a guitar, or a piano, or the instrument of your choice, instead.

That is to say, Scheme is fun because of what you are able to articulate with it; things you would have a difficult time articulating in, say, Java (not that there's anything wrong with that) -- similar to how you can "say" more with a sharp pencil than with a stack of boulders; it's more expressive (unless the boulders are marble and you are skilled with a hammer and chisel, I suppose).

Scheme is, of course, a Lisp dialect, and I'll freely admit that I haven't (yet) used Lisp itself; however, I imagine that this quality of how much you can express, how flexible the language is, is a quality they share -- rather, probably it's a quality which was inherited by Scheme, more than simply "shared".

And that's it... that's why. Because you get to draw with a sharp pencil on Bristol board instead of throwing rocks at a wall. For examples, you can scour the web, or I suppose you can just check back here later.

last updated 3 years ago #

Well, it's the first post.

last updated 3 years ago #