News

muvee Reveal - the latest incarnation of muvee's flagship product - has just been released on 11 June 2008! The behaviours of the 8 bundled styles are specified using muSE, in addition to all the styles developed for the now discontinued muvee autoProducer 6.1.
Showing posts with label Examples. Show all posts
Showing posts with label Examples. Show all posts

Wednesday, August 15, 2007

Curry Howard isomorphism

Curry Howard isomorphism states that every logical proposition corresponds to a type. (See also Curry-Howard-Lambek correspondence.) I've been fascinated by this recently, in the context of Haskell, 'cos it yields very interesting and powerful functions. Often you can just take the type expression in Haskell and write a function that has the type.

For example, consider the trivial logic "theorem" -

If it is true that proposition A implies proposition B, then A is provable implies B is provable.
If you notate provability by the symbol #, you can write that as -
(A => B) => (#A => #B)
If you consider => to be the function type constructor (in Haskell), this gives you the type of fmap where # is any functor. It looks like you can uniformly map "is provable" to some kind of containment - like a list or a set.

Here's a very interesting function derived from another logic proposition - From Löb's Theorem to Spreadsheet Evaluation.

Here's an implementation of the loeb function in muSE -

; Limitation - fmap over lists only
(define (fmap f x)
(if x
(lcons (f (first x))
(fmap f (rest x)))
()))
(define (loeb x) (fmap (fn (a) (a (loeb x))) x))


.. and a variant on the author's example -

(define test
(list (fn (x) 17)
(fn (x) (apply + (drop 3 x)))
(fn (x) (* 2 (nth 3 x)))
(fn (x) (+ (nth 4 x) (nth 5 x)))
(fn (x) 3)
(fn (x) (nth 0 x))))

The stair climbing robot

An interesting problem called "the stair climbing robot" was recently posted on LtU.

Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. Write a function "step_up" that climbs one step up (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?

I thought I'll try to solve it using muSE's lcons lazy function. Here's a solution -

; A step function which fails 50% of the time.
(define (step)
(if (= 0 (rand 2))
(do (print "DOWN") ())
(do (print "UP") T)))

; Gets the second element of a list s,
; forcing the value of the first element if
; the list happens to be lazy.

(define (forced-next s) (first s) (first (rest s)))

; (steps) generates a sequence of
; successful upward steps. To climb N steps,
; just take N elements from (steps).

(define (steps)
(lcons (if (step)
T
(forced-next (rest (steps))))
(steps)))

; Climb 1 step
(take 1 (steps))

Wednesday, May 23, 2007

Getting lazy

Recently, in v250 of the muSE core library, I added support for stack optimization of tail calls - finally!

muSE has been missing the ability to do tail recursion for ever and now its finally there. The absence of tail recursion support had a rather ugly but practical consequence for the language - the while and for looping constructs had a reason to exist because you couldn't loop otherwise without blowing the stack top. I'm glad to note that they can now be safely RIP-d.

Tail call optimization as implemented does not apply to tail calls of native functions. It only applies to applications of user defined functions that appear in the tail position in a block.

As a by-product of the tail call optimization, I was surprised to find it easy to implement lazy evaluation. There's an experimental primitive lcons which can be used to construct a list lazily. This operator is inspired by Dan Friedman's TR44: CONS should not evaluate its arguments technical report. Some classic examples can be found in examples/lcons-v238.scm in the source tree.