?

Log in

No account? Create an account

t3knomanser's Fustian Deposits

My Evil Scheme, or (append '(my) (evil scheme))

How Random Babbling Becomes Corporate Policy

run the fuck away

Mad science gone horribly, horribly wrong(or right).

My Evil Scheme, or (append '(my) (evil scheme))

Previous Entry Share Next Entry
run the fuck away
I've been working on learning LISP, or more specifically, Scheme (or even more specifically mzScheme). For those unfamiliar, LISP is one of the oldest programming languages in use, as it was originally derived in the 50s. That's right, I'm learning a language that's over 50 years old. Why? Well, it's not for nostalgia's sake.

LISP started with a few core assumptions. First, it was derived from mathematics more directly than most languages. Second, since the best mathematical systems were the ones that have the fewest axioms (things held true just because) LISP has as few "givens" as possible (although various variants have added to that list for practical reasons). Finally, since a program is nothing more than data, LISP makes no distinction between executable code and data.

And really, really finally, (loves lisp parentheses). Er, LISP loves parentheses. And "prefix notation" (e.g., 2 + 4 + 8, in LISP is represented as (+ 2 4 8)- the operator goes in front- there are good reasons for this not worth going into now).

Programmers can be divided into 10 groups, people who get LISP, and people who don't. People who get LISP adore it. Everyone else thinks it's an affront to all that is holy and just and good in this world. When my Intro to Computer Science class in college abused me with Scheme, I joined the latter camp. I could see no reason to learn Scheme- I came to school to learn practical useful things.

In short, I was an arrogant idiot who thought he knew more than his professors. Fiveish years after graduation, I stand corrected. I've tried, a few times to pick up LISP. It's a unique language, although it's becoming less unique as time passes. That's right- new, cutting edge languages are trying to imitate LISP more and more. Believe it or not, JavaScript has more it common with LISP than it does with Java. Ruby, one of the attempted usurpers of PERL's throne, has much in common with LISP (it's been described as a way to trick people into programming LISP without their knowing).


Okay, so there's some interesting history. But why go out of my way to learn this ancient language. Well, it goes back to those core assumptions I was talking about. LISP, at its purest, can be condensed into a few, simple, core concepts. I'm going to oversimplify, and any purists that stumble across this will just have to bear with me.
  • Symbols
  • Lists
  • Functions

A symbol is just what you think it means: a string that represents something else. The word "chair" is nothing more than a symbol for the thing that keeps you posterior off the floor. In LISP, the symbol "+" represents addition. The symbol "car", in this context, represents a way to manipulate a list.

A list is just what you think it means. It's a series of symbols arranged in a sequence, like, "(a b c)". Pretty much everything in LISP is a list. And LISP lets you make lists of lists. For example, a list of people might look like: ((Joebob Bobsen) (Sallybob Bobsen) (Suebob Bobsen)). The list of students is a list of lists, and each sub-list is a list of names- (first-name last-name). Each name is a symbol.

So, a list is a collection of symbols, and all symbols are a placeholder for something else. A function then, would be a process that manipulates either symbols, lists, or both to generate some output. "+" is a symbol that represents the function "add". So, (+ 2 3 4): "+" tells you what to do, and "2 3 4" are the symbols to do it to. The expression, (+ 2 3 4) evaluates to 9 (2 + 3 + 4).

But hold on there! (+ 2 3 4) is a list! The first element is the function you want to perform (add), and all the other elements are the things you want to apply that function to. Remember what I said before: LISP makes no distinction between data and executable code. Everything is made up of symbols and lists. A function is just a special kind of list- one that does something. For example, the area of a circle. That's a mathematical function we all know- 2πr2. In LISP, I could do something like this:

(define circle-area (lambda (r) (* 2 3.14 (expt r 2))))

So there's a bunch of lists, symbols and functions. Let's work from the inside out.
(expt r 2): expt is a symbol for the function "exponent"- that's the r2 part. Raise "r" to the "2" power. So, if "r" is 10, that means (expt r 2) is 100 (102).

That means the next list out is actually (* 2 3.14 100), which evaluates to 628 when "r" is "10".
The next list out is the (lambda...) bit. Lambda is special, it's a function that makes a function. Remember: code and data are both stored in lists. And define is a function that assigns a value to a symbol- in this case, it assigns the result of lambda to the symbol circle-area. In short, I turned a mathematical expression into a list, then made up a symbol to represent that list: circle-area. So every time I say, (circle-area 10), the computer knows to spit out 628.

Okay... so, I've just turned some lists into computer code. It's a little weird. Why is this cool?

Well, with these basic concepts, I can do pretty much anything. Three core ideas let me do whatever I can think of.


What about speaking English? Computers are pretty bad at talking with you. You have to give them really clear commands written in a special syntax. Can I do better? Well, in the space of a singe LJ post, the answer is: "no". English is really complex and has a lot of weird rules. I can't easily make a computer speak English. But what I can do is make a computer program able to manipulate a few simple English sentences. For example, I'm going to make a program that can derive conclusions from simple English sentences.

I'm going to limit myself to sentences like this: x is y. "A sentence is a list of words." "The car is blue." "Socrates is a man." Real simple sentences. But given two sentences like this: "Socrates is a man", "A man is mortal", my program should spit out "Socrates is mortal".

The code for this is fairly compact, and I could make it more compact. But by being very explicit, I can make it a bit easier to understand.

;Given a fact containing an element in the verbs list, return the verb and all that follows
(define break-fact-on-verb (lambda (fact verbs)
 (if (pair? verbs) (if (pair? (member (car verbs) fact)) (member (car verbs) fact) (break-fact-on-verb fact (cdr verbs)))
     )))
;Return the verb contained in a fact
(define get-verb (lambda (fact verbs)
                  (if (null? verbs) #f
                      (if (member (car verbs) fact) (car verbs)
                          (get-verb fact (cdr verbs)))
                      )))
;Given a fact in the form: [subject] [verb] [predicate] convert it to: (verb (subject) (predicate))
(define parse-fact (lambda (fact verbs)
 (let ((pred (cdr (break-fact-on-verb fact verbs)))
       (subj (reverse (cdr (break-fact-on-verb (reverse fact) verbs))))
       (verb (get-verb fact verbs)))
   (list verb subj pred)
  )))
;Given two parsed facts, see if the subject of the first matches the predicate of the second
;return the conclusion, or #f
(define chain-rule (lambda (first second)
 (if (equal? (list-ref second 1) (list-ref first 2))
     `(,(car first) ',(list-ref first 1) ',(list-ref second 2))
     #f)))
;Given two facts, parse them and apply the chain rule
;if the chain rule returns true, execute and return the conclusion
(define simple-syllogism (lambda (first second verbs)
 (or (chain-rule (parse-fact  first verbs) (parse-fact second verbs)) #f)))
;Verbs must have a function defined to allow rendering
(define is (lambda (subject predicate . verb)
            (append subject (if (null? verb) '(is) verb) predicate)))
(define are (lambda (subject predicate) (is subject predicate 'are)))
;Here's our syllogism
(define verbs '(is are)) ;our barrier between a subject and predicate
(define fact-list '((a man is mortal) (socrates is a man))) ;subject verb predicate
(eval (simple-syllogism (list-ref fact-list 1) (list-ref fact-list 0) verbs)) ;ergo socrates is mortal

This program outputs "socrates is mortal". It converts a pair of lists of input into a single output list: a conclusion.

My simple (and probably clumsy, by an experienced LISPer's standards) program demonstates why LISP is beloved of AI researchers. A sentence is nothing more than a list of words, and a word is a symbol that has meaning. By establishing relationships between words and lists of words, I can build meaning and then manipulate it to derive conclusions.

There's much more, of course. LISP is also a "metalanguage", that is, a language to describe other languages. I can, using LISP, create new languages easily. One of my other learning projects is making an object oriented language all my own (derived from LISP). It's a great way to arrange and store data. Basically, I'm fascinating myself with the language. Cool, cool stuff. If anyone wants, I may build more formal tutorials as I learn.
  • I am intrigued. Confused, too, but I hope that's just the absynthe. It is still intriguing.
  • wow - I didn't realize LISP was quite that old - I had guessed early 70s.

    I would totally love to learn more about LISP - a coworker suggested I start by trying to do all my math in reverse polish notation for a few months. I may try teaching that notation to my 9 year old and see if we can play (possibly modified) some of his old adding and subtracting games with it from when he was in kindergarden and first grade.

    So yeah, I would be interested in more LISP tutorials - even though I really can't read the source of this one. More exposure and actually finding a "getting started" tutorial would probably remedy that. But now I have to go build a website...
    • One of the things that I've found fascinating is the way LISP is a meta-language. Various flavors have a macro architecture that turns LISP into a language to describe languages.

      But I think I will be putting together an into to LISP and tying it in with on of my long-held todo projects: "You can Program", an introduction to computer science for anyone.
  • A statically typed functional language with more readable syntax might be better suited to implementing a new language, or any other larger project. I do almost all of my coding in OCaml, and recommend it enthusiastically.
Powered by LiveJournal.com