2008-10-26

Парадокс Монти Холла

Пример того, как программистский подход к решению проблемы может сделать даже парадокс тривиально понятным.
(defun monty-hall (n)
"Возвращает отношение доли успешных и неуспешных розыгрышей
игры Монти Холла при выборе стратегии всегда менять изначально
выбранную дверь"
(let ((succ 0.0)
(fail 0.0))
(dotimes (i n)
(let ((choice (random 3))
(prize (random 3)))
(if (= choice prize)
(incf fail) ; мы выбрали правильную дверь, но придется поменять
(incf succ)))) ; мы выбрали неправильную дверь, значит, после смены -- правильную
(/ succ fail)))

И статистика:
CL-USER> (monty-hall 100)
1.5641025
CL-USER> (monty-hall 1000)
1.6455027
CL-USER> (monty-hall 10000)
1.9958059
CL-USER> (monty-hall 100000)
2.0147724
CL-USER> (monty-hall 1000000)
1.9966408
CL-USER> (monty-hall 10000000)
1.9986455

Monty Hall Paradox

The example of how tackling a problem in a "hacker's hat" can make a paradox trivial to understand.
(defun monty-hall (n)
"Returns a ratio of success rate to failure rate, if we follow
the strategy of always switching the initially selected door in
the Monty Hall Problem"
(let ((succ 0.0)
(fail 0.0))
(dotimes (i n)
(let ((choice (random 3))
(prize (random 3)))
(if (= choice prize)
(incf fail) ; we've chosen the right door, but will need to switch
(incf succ)))) ; we've chosen the wrong door and after switching -- the right
(/ succ fail)))

And the statistics:
CL-USER> (monty-hall 100)
1.5641025
CL-USER> (monty-hall 1000)
1.6455027
CL-USER> (monty-hall 10000)
1.9958059
CL-USER> (monty-hall 100000)
2.0147724
CL-USER> (monty-hall 1000000)
1.9966408
CL-USER> (monty-hall 10000000)
1.9986455

2008-10-23

"Clojure for Lisp Programmers" Talk Summary

In his talk Rich Hickey made an overview of the major features of Clojure and the design rationale behind them. Except for being Lisp-1, as far as I understand, Clojure is mostly based in and inspired by Common Lisp. Moreover, it tries to push some of the CL technologies to even purer abstraction and generality.

I've tried to categorize the discussed features in their relation to Common Lisp:
  1. Taken from CL and stretched/modified
    • destructuring
    • nil behavior in conditionals
    • defmacro
    • multimethods with dispatch by an arbitrary function of arguments
      Obviously is more general, than the CL variant, although Rich failed to mention, that CL's generic functions have also dispatch by EQL, which is enough for, I think, 95% of the situations.

    • first-class immutable & persistent data-types: list, vector, hash-map and set
    • seq(uence) protocol
      I consider the last 2 a very important idea and a good candidate for implementation as a CL library.

  2. Intentionally different from CL
    • Side-effect free reader & separate symbol resolution for macros
      This is also a well thought-out choice, which gives a lot of food for thought.

    • Lisp-1. Symbols and vars separated (in Lisp-2 vars are symbol-value or symbol-function)
      In my opinion, not the best option. But it's, obviously, the simpler one to implement

    • egal equality

  3. Additional technologies
    • STM (MVCC), agents & refs, commute
      A full-fledged innovative concurrent infrastructure.

    • Call-ability of data-structures as vars
      A controversial choice, which may lead to a lot of confusion.

    • Metadata
      In some sense, a substitute for lack of multiple-values. Besides, a partial introduction of support for the prototype pattern (although lacking inheritance).

  4. Different from CL because of the need for JVM integration (CL solution being superior)
    • no multiple-values
    • namespaces instead of packages
    • boolean true/false

  5. Arbitrary choices inferior to CL solutions (because too much work needed to implement & some infrastructure already available)
    • exception handling
    • debugging & profiling tools
    • boxed integers instead of numeric tower