Want to twist your brain by sorting in a stack language? Ok. First we need to define a function to put the minimum value on top:

[ dup 'm ; [ at dup m < [ 'm ; ] if [ , ] else ] len 1 - times m ] 
'min ;

Next we need a secondary stack to hold the intermediate sorted values. Let us create a child virtual machine to keep track of the secondary stack, so that it can respond to a get message and push the sorted values back to the main stack:

{ >> dup 'get equals [ <<< ] when } 'sorted ;

We now have a function to find the minimum value on the stack and a virtual machine to keep track of the sorted elements, implementing the simple selection sort algorithm is just another one-liner:

[ [ , min dup sorted remove ] len 1 - times 'get sorted reverse , ]
'selsort ;

So there is our “stack sorter” in three lines!

Tests:

4 2 3 1 6 7 selsort .s
=> 1 2 3 5 6 7
20 100 45 selsort .s
=> 20 45 100 
1 2 3 4 5 selsort .s
=> 1 2 3 4 5

A finite automaton that recognizes the regular language of all strings (made of 0’s and 1’s) that contain the string 001 as a substring. For example, 001, 1001 and 1111001001 are valid in the language, but 11 and 010 are not.

(define (one? x)
  (= x 1))

;; State that skips all 1's.
;; When a 0 is encountered, state changes to q0.
(define (q x)
  (if (one? x)
      q
      q0))

;; If the pattern 00 is seen, moves to state q00.
;; Goes back to q if x = 1.
(define (q0 x)
  (if (one? x)
      q
      q00))

;; State is in the pattern 00.
;; If 1 is seen, move to the end state (e).
;; Otherwise, move back to q0.
(define (q00 x)
   (if (one? x)
       e
       q00))

;; Notifies the state machine that the pattern has been found.
(define (e)
  #t)

;; The state machine itself.
(define (m string)
  (let ((state q))
    (call/ec
      (lambda (k)
        (for x in string
            (set! state (state x))
            (if (eq? state e)
                (k (state))))
       #f))))

Tests:

> (m '(1 1 0 1 0))
#f
> (m '(1 1 0 0 1 0))
#t
> (m '(0 0 1))
#t
> (m '(1 1 1 1 1 1 1 0 0 1 1 1 1 1))
#t

A good article that discusses some cool graphics programming techniques.

Once Nicholas Negroponte was visiting the headquarters of a famous chip manufacturer. He was asked to sign in and declare the model and price of his laptop. He told the receptionist that the value of his laptop is “Roughly between 1 and 2 million dollars”. The aghast receptionist personally checked his old PowerBook and recorded its price as $2,000. The point is, some people values stuff by atoms while others by bits.

What is the value of your Laptop? :–)

A simple example that could be used to introduce symbolic programming in Lisp:

(define men '(socrates plato aristotle))

(define (man? x)
    (contains? men x))

(define (mortal? x)
    (man? x))

 ;; test

> (mortal? 'socrates)
=> #t

Conjured this up while answering a question at stackoverflow.