terça-feira, 31 de agosto de 2010

Bitvector genealogy update

In the past few days I have been fiddling with several possibilities
for the bitvector genealogy problem. I was aiming to solve the problem
with the root bitvector that my first solution had.

I have found different sources on the web and different ways of
dealing with the problem, but none matched the accuracy of the first
solution, although it did surpass it in speed.

Here you will find the latest racket code with a several different takes on
the solution. The main things to look for are the find-genealogy-*
functions.

For now I am done with this until I can come up with a different
strategy for approaching the problem.

domingo, 22 de agosto de 2010

Bitvector Genealogy


Introduction

Recently I have come across something that reminded me of a challenge
I tried some time ago, ITAs bitvector genealogy
challenge(1). Back in the day when I was first
learning scheme, I have tried to use this to build up my skills with
the help of a great tutorial(3).
Needless to say that I failed at that, both for my lack of scheme and
common lisp competence but also for my lack of aptitude as a
programmer.

The something was a thread in Hacker News where ITA was mentioned. I
became curious to see how much I had progressed since my last attempt,
so I grabbed DrRacket, Emacs and jumped into the fray one more time.

Again, most of the original hard work was done by Patrick May. What I
am showing here is a take on his work, translated to scheme
and modified to use different data structures and different points of
views on the same fundamental algorithm.

Ok, this is the description of the problem:

The BitVectors are an ancient and immortal race of 10,000, each with
a 10,000 bit genome. The race evolved from a single individual by
the following process: 9,999 times a BitVector chosen at random from
amongst the population was cloned using an error-prone process that
replicates each bit of the genome with 80% fidelity (any particular
bit is flipped from parent to child 20% of the time, independent of
other bits).

Write a program to guess the reproductive history of BitVectors from
their genetic material. The randomly-ordered file
bitvectors-genes.data.gz contains a 10,000 bit line for each
individual. Your program's output should be, for each input line,
the 0-based line number of that individual's parent, or -1 if it is
the progenitor. Balance performance against probability of mistakes
as you see fit.
(1)

The next step is really the crux of the problem. This is where a bit
of mathematics comes into play

The next step in developing a solution is to determine whether or not
a parent-child relationship exists between two bit vectors. According
to the problem definition, every bit vector other than the original is
created by randomly mutating the elements of an existing bit
vector. The probability of a particular bit changing is 20%. That
means that, on average, the children of a bit vector should be 80%
identical to their parent and the grandchildren should be 64%
similar. Of course, the random element means that some will have more
than 80% similarity and others less. Some children may be more
similar to each other than either is to their parent. The best result
any automated solution will be able to achieve is the most probable
relationship tree.

Assuming that a fair random number generator was used, the set
containing the number of bits different between a parent and each of
its children should follow a binomial distribution. The probability of
two vectors having a parent child relationship is related to how close
the difference between the two is to the expected value (20%, in this
case). In a binomial distribution (which approximates a continuous
normal distribution), 99.73% of the bit difference values will be
within three standard deviations of the expected value. The standard
deviation is computed by:


Body

First, I will define some globals that will be useful throughout the
source code, and the utilities to load the bitvectors data into a
vector of numbers:

(define ROOT-SYMBOL -1)

(define MUTATION-RATE 0.2)

;; http://mathworld.wolfram.com/BinomialDistribution.html
(define DEVIATION 3) ;; 3 = 99.73 percent


(define DNA-LENGTH 0)

(define (get-dna)
  DNA-LENGTH)

(define (set-dna! number)
  (set! DNA-LENGTH number))

;; filename->bitvector : input-port -> (vectorof binary-number)
;; read everything from a given file and returns a 
;; vector containing binary numbers. 
(define (filename->bitvector file-path (radix 2))
  (local [(define (read-accumulative bitvector)
            (let ([line-read (read-line file-path 'any)])
              (if (eof-object? line-read)
                  bitvector
                  (let ([possible-number (string->number line-read radix)])
                    (read-accumulative
                     (if (number? possible-number)
                         (vector-append bitvector (vector possible-number))
                         bitvector))))))]
    (cond
      [(equal? "" file-path)]
      [else
       (read-accumulative (vector))])))

The next part is really the crux of the problem. This is where a bit
of mathematics comes into play (2)
and the most complex part of the problem in my view:

The next step in developing a solution is to determine whether or not
a parent-child relationship exists between two bit vectors. According
to the problem definition, every bit vector other than the original is
created by randomly mutating the elements of an existing bit
vector. The probability of a particular bit changing is 20%. That
means that, on average, the children of a bit vector should be 80%
identical to their parent and the grandchildren should be 64%
similar. Of course, the random element means that some will have more
than 80% similarity and others less. Some children may be more
similar to each other than either is to their parent. The best result
any automated solution will be able to achieve is the most probable
relationship tree.

Assuming that a fair random number generator was used, the set
containing the number of bits different between a parent and each of
its children should follow a binomial distribution. The probability of
two vectors having a parent child relationship is related to how close
the difference between the two is to the expected value (20%, in this
case). In a binomial distribution (which approximates a continuous
normal distribution), 99.73% of the bit difference values will be
within three standard deviations of the expected value.
(3)

Taking that, we can establish the existence of a relationship (with
some degree of confidence) with the following code:

;;  binary-difference : binary-number binary-number -> integer
;; returns the number of bits that are different between 2 binary numbers.
(define (binary-difference bits1 bits2)
  (let ([differences 0])
    (for ((i (in-string (number->string (bitwise-xor bits1 bits2) 2))))
      (when (equal? i #\1)
        (set! differences (add1 differences))))
    differences))

;; binomial-standard-deviation : number -> number
;; Compute the expected binomial standard deviation for N events of probability P.
(define (binomial-standard-deviation n p)
  (sqrt (* n p (- 1 p))))

;; has-kinship? : integer integer -> boolean
;; verify if 2 individuals share a kinship. 
;; The relationship is assumed if the bit difference between the two is
;; less than DEVIATIONS standard deviations from the expected average for
;; the MUTATION-RATE.
(define (has-kinship? individual-1
                      individual-2
                      (mutation-rate MUTATION-RATE)
                      (deviations DEVIATION)
                      (dna-length (get-dna)))
  (let* ([expected-difference (* dna-length mutation-rate)]
         [standard-deviation
          (binomial-standard-deviation dna-length
                                       mutation-rate)]
         [max-difference (+ expected-difference
                            (* deviations standard-deviation))])
    (< (binary-difference individual-1
                          individual-2)
       max-difference)))



The code above shows in some ways where I deviated from Patrick's
example. I used a number instead of a bit array (which does not exist in
Racket, the language I'm using, as far as I know). In the following
code, this difference deepens, with the construction of a hash map
instead of a vector to get the relationship matrix:

;; create-relationship-hash : (vectorof number) -> hash
;; creates a hash mapping an individual to it's list of relationships.
;; Both parents and children are mapped to an individual.
(define (make-relationship-hash bitvector)
  (let ([relationship-hash (make-hash)]
        [dna-range (in-range 0 (vector-length bitvector))])
    (for* ((individual-1-index dna-range)
           (individual-2-index dna-range))
      (begin (unless (hash-has-key? relationship-hash individual-1-index)
               (hash-set! relationship-hash individual-1-index empty))
             (let ([individual-1 (vector-ref bitvector
                                             individual-1-index)]
                   [individual-2 (vector-ref bitvector
                                             individual-2-index)])
               (when (and (has-kinship? individual-1
                                        individual-2)
                          (not (= individual-1 individual-2)))
                 (hash-update! relationship-hash
                               individual-1-index
                               (λ (relationships)
                                 (cons individual-2-index relationships)))))))
    relationship-hash))

This almost closes the issue, but I must figure out the directions of
the relationships(who is who's father and son). To establish that I
should have to:

  • Find all the bit vectors with only a single parent-child relationship
  • Assume that those vectors are the child nodes
  • Record that information
  • Remove the child node from the parent's list of relationships
  • Repeat

(3)

That is accomplished in the longest and most complex code in the solution:

;; make-kinship-hash : hash -> hash
;; creates a hash mapping an individual only to it's parent.
(define (make-kinship-hash relationship-hash-initial)
  (local [(define (make-kinships kinship-hash
                                 relationship-hash)
            (local [(define (process-possible-kinship individual-index
                                                      relationships-indexes)
                      (let ([number-of-relationships
                             (length relationships-indexes)])
                        (unless (> number-of-relationships 1)
                          (begin
                            (hash-remove! relationship-hash
                                          individual-index)
                            (if (= number-of-relationships 1)
                                ; leaf node
                                (begin
                                  (hash-set! kinship-hash
                                             individual-index
                                             (first relationships-indexes))
                                  (hash-update! relationship-hash
                                                (first relationships-indexes)
                                                (λ (relationships)
                                                  (remove individual-index
                                                          relationships))))
                                ; root node
                                (begin (hash-remove! relationship-hash
                                                     individual-index)
                                       (hash-set! kinship-hash
                                                  individual-index
                                                  ROOT-SYMBOL)))))))]
              (if (false? (hash-iterate-first relationship-hash))
                  kinship-hash
                  (begin
                    (hash-for-each relationship-hash
                                   process-possible-kinship)
                    (make-kinships kinship-hash
                                   relationship-hash)))))]
    (make-kinships (make-hash) relationship-hash-initial)))

And that is the end of the solution! I am still facing the same issues
as Patrick, specially in regard to the root individual, but
reimplementing his solution and trying to achieve a better result by
the use of different data structures led me to understand the problem
more deeply, and it was loads of fun!

PS: There is more code in
this
repository, specially regarding testing and comparison.


Bibliography

1

ITA.

Bitvector genealogy.

URL
http://www.itasoftware.com/careers/work-at-ita/hiring-puzzles.html.




2

MathWorld.

Binomial distribution.

URL http://mathworld.wolfram.com/BinomialDistribution.html.




3

Patrick May.

Bitvector genealogy.

URL http://www.softwarematters.org/bitvector-genealogy.html.



terça-feira, 17 de agosto de 2010

Developing a programming design taste

Abstract:


A latent potential for emergent education in programming exists, but most
of the widely available material focus on wasteful details and does not help
the learner develop mental techniques to judge what is a beautiful program
and how to manage its own thinking patterns.
In this article I try to present a way that would address this issue, by
providing the tools for a person to become aesthetically proficient in
programming, and through that develop administrative thinking patterns.





Introduction

The problem that I will cover in this article is the one of learning how to
think programmatically, that is, to program.

What I will focus is specially the demonstration of paths and technique's
a single aspirant programmer would use to grasp not only the minor surface
details of the craft, but its meaning and consequences, so that it could have a
chance at approaching complex and dynamic problems. The same holds true for a
teacher who wants to build a class for novice programmers.

There is a latent potential for an increase in the depth of the knowledge about
computation in the general population. You can observe for instance it by the
appreciation of computer games and graphics. Sure, not every gamer or graphic
designer has a desire for becoming a programmer, not even the majority. But one
can assume that from the enormous pool of people involved in those activities
there could be an significant category interested in computing itself.

Besides this, a lot of benefits comes from learning to program, even if we
ignore the monetary incentive. Sussman (2005)
Not only that, but this mastery could lead to an increase in critical thinking
and multiple levels of abstraction, teaching analytical skills in an active and
concrete way. Felleisen et al. (2001)

The contributions I try to accomplish here are:


  1. A central and coherent roadmap one can use to become a competent
    programmer by developing a taste for good programs

  2. A review of the literature involved in the roadmap, pointing out their
    perceived strengths and weakness

  3. Some indications on where to go after the way is walked



The Problem

With the advent of the Internet, the potential to learn the necessary skills of
a good programmer is present for a motivated student or a community of
colleagues, mostly because top notch material is freely and widely available.

But in the sea of information a lot of pitfalls await, and possibilities for lost
time and motivation are plenty. What can remedy that is that the individual
has some taste to be able to differentiate a bad source from a good source.

But what kind of taste should people have? I find myself agreeing with
Graham (2002), because it is a consistent
and detailed list, and the author is a know software designer, who is famous for
prizing beauty, both technical and aesthetical.



The road map

Where do I plan to guide the reader? The shangri-la of this map is
Papert's Principle:

Some of the most crucial steps in mental growth are based
not simply on acquiring new skills, but on acquiring new administrative ways to
use what one already knows. Minsky (1988)

This principle is the objective because I consider the fundamental aspect of
taste as the ability to organize current knowledge in efficient and beautiful
ways.

More specifically, I'll point to sources that present techniques to reach the
same goals of Chakravarty and
Keller (2004)


  1. Convey the elementary techniques of programming (the practical aspect).
  2. Introduce the essential concepts of computing (the theoretical aspect).
  3. Foster the development of analytic thinking and problem solving skills (the methodological aspect).



Styles and Stances

What language to begin the journey? This is at the same time an important and a
meaningless question.

It is important because all languages are designed with certain goals. My
recommendation could not be stated better than
Norvig (2001) does:

  • Use your friends. When asked "what operating system should I use,
    Windows, Unix, or Mac?", my answer is usually: "use whatever your friends
    use." The advantage you get from learning from your friends will offset any
    intrinsic difference between OS, or between programming languages. Also
    consider your future friends: the community of programmers that you will be
    a part of if you continue. Does your chosen language have a large growing
    community or a small dying one? Are there books, web sites, and online
    forums to get answers from? Do you like the people in those forums?

  • Keep it simple. Programming languages such as C++ and Java are designed for
    professional development by large teams of experienced programmers who are
    concerned about the run-time efficiency of their code. As a result, these
    languages have complicated parts designed for these circumstances. You're
    concerned with learning to program. You don't need that complication. You
    want a language that was designed to be easy to learn and remember by a
    single new programmer.
  • Play. Which way would you rather learn to play
    the piano: the normal, interactive way, in which you hear each note as soon
    as you hit a key, or "batch" mode, in which you only hear the notes after
    you finish a whole song? Clearly, interactive mode makes learning easier for
    the piano, and also for programming. Insist on a language with an
    interactive mode and use it.

Given these criteria, my recommendations for a first programming language
would be Python or Scheme. But your circumstances may vary, and there are
other good choices. If your age is a single-digit, you might prefer Alice or
Squeak (older learners might also enjoy these). The important thing is that
you choose and get started.

But why it is a meaningless choice? Because the true skill of a programmer is
not to understand one language or another. As Papert (1981)
puts it (he uses children, but they are just special example case):

By deliberately learning to imitate mechanical thinking, the learner becomes
able to articulate what mechanical thinking is and what it is not. The
exercise can lead to greater confidence about the ability to choose a
cognitive style that suits the problem. Analysis of "mechanical thinking"
and how it is different from other kinds and practice with problem analysis
can result in a new degree of intellectual sophistication. By providing a
very concrete, down-to-earth model of a particular style of thinking, work
with the computer can make it easier to understand that there is such a
thing as a "style of thinking." And giving children the opportunity to
choose one style or another provides an opportunity to develop the skill
necessary to choose between styles. Thus instead of inducing mechanical
thinking, contact with computers could turn out to be the best conceivable
antidote to it. And for me what is most important in this is that through
these experiences these children would be serving their apprenticeships as
epistemologists, that is to say learning to think articulately about
thinking.

Let me be more clear. The most important skill a great programmer possess is the
capacity to think at different levels, and to think about thinking, because this
develops the crucial mental flexibility of a good designer.
Spolsky (2005)


The texts



How to design programs

This is the first text I'll recommend. The reasons are 2. First, they get the
epistemological approach, as shown by statements as

Learning to design programs is like learning to play soccer. A player must learn
to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the
player knows those basic skills, the next goals are to learn to play a position,
to play certain strategies, to choose among feasible strategies, and, on
occasion, to create variations of a strategy because none of the existing
strategies fits.

A programmer is also very much like an architect, a composer, or a writer. They
are creative people who start with ideas in their heads and blank pieces of
paper. They conceive of an idea, form a mental outline, and refine it on paper
until their writings reflect their mental image as much as possible. As they
bring their ideas to paper, they employ basic drawing, writing, and instrumental
skills to express certain style elements of a building, to describe a person's
character, or to formulate portions of a melody. They can practice their trade
because they have honed their basic skills for a long time and can use them on
an instinctive level.
Felleisen et al. (2001)

But the main reason is that they place an emphasis on a design recipe.

Design recipes are the equivalent of soccer ball handling techniques, writing
techniques, techniques of arrangements, and drawing skills. A single design
recipe represents a point of the program design space. We have studied this
space and have identified many important categories. This book selects the most
fundamental and the most practical recipes and presents them in increasing order
of difficulty.
Felleisen et al. (2001)

Not only the book provides all that, they also couple it with its program
environment and editor, a tool know as DrScheme. It is a professional as well as
an educational leverage, and its use along with the text is imperative for
getting the full experience.Findler et al. (2001)


The structure and interpretation of computer programs

This book is chosen because the authors clearly understand Papert's principle
(they were both his students) by several comments as:

Our design of this introductory computer-science subject reflects two major
concerns. First, we want to establish the idea that a computer language is not
just a way of getting a computer to perform operations but rather that it is a
novel formal medium for expressing ideas about methodology. Thus, programs must
be written for people to read, and only incidentally for machines to execute.
Second, we believe that the essential material to be addressed by a subject at
this level is not the syntax of particular programming- language constructs, nor
clever algorithms for computing particular functions efficiently, nor even the
mathematical analysis of algorithms and the foundations of computing, but rather
the techniques used to control the intellectual complexity of large software
systems.
Sussman and Abelson (1996)

Underlying our approach to this subject is our conviction that ``computer science'' is not a science and that
its significance has little to do with computers. The computer revolution is a revolution in the way we
think and in the way we express what we think. The essence of this change is the emergence of what might
best be called procedural epistemology - the study of the structure of knowledge from an imperative point
of view, as opposed to the more declarative point of view taken by classical mathematical subjects.
Mathematics provides a framework for dealing precisely with notions of ``what is.'' Computation provides
a framework for dealing precisely with notions of ``how to.''
Sussman and Abelson (1996)

Marvin Minsky and Seymour Papert formed many of our attitudes about programming and its place in our
intellectual lives. To them we owe the understanding that computation provides a means of expression for
exploring ideas that would otherwise be too complex to deal with precisely. They emphasize that a
student's ability to write and modify programs provides a powerful medium in which exploring becomes a
natural activity.
Sussman and Abelson (1996)

Even the critics of the approach this text takes recognize its value and
depth:

Abelson and Sussman have written an excellent textbook which may start a
revolution in the way programming is taught.
Instead of emphasizing a particular programming language, they emphasize standard
engineering techniques as they apply to programming.
Wadler (1987)

But not all is swell with this classic text. SICP does suffer from some
major deficiencies. Those are 2 according to Felleisen et al. (2002):

  1. ... sicp doesn’t state how to program and how to manage the design
    of a program. It leaves these things implicit and implies that students
    can discover a discipline of design and programming on their own

  2. SICP’s second major problem concerns its selection of examples and
    exercises. All of these use complex domain knowledge.

Given those problems, I think it is best, specially for those without access to
an experienced tutor/colleague, to leave SICP for a later visit, armed with the
design tools that HTDP provides. Not only it will stress and test these tools,
but it will make the road more bearable and enjoyable.


Further readings or The path to objects



Concrete Abstractions

This work is aimed at the same audience as HTDP and SICP, but with a different
emphasis. It still uses the scheme language, which allows the
use of DrScheme
, a fact
that gives it the same benefits as HTDP in this aspect.

It is also a textbook that gets the epistemological importance of the teaching,
as this small description by its authors shows:

  1. The book features thorough integration of theory and practice,
    and presents theory as an essential component of practice, rather than
    in contrast to it. Thus, students are introduced to the analytic tools
    they need to write effective and efficient programs, in the context of
    practical and concrete applications.

  2. Significant programming projects are included that actively
    involve students in applying concepts. Each chapter ends with an
    application section, in which the concepts from that chapter are applied
    to a significant, interesting problem that involves both program design
    and modifying existing code.

  3. The authors present development of object-oriented programming,
    one concept at a time. Each of the component concepts that constitute
    object-oriented programming (OOP) is introduced independently; they are
    then incrementally blended together.

  4. In keeping with modern curricular recommendations, this book
    presents multiple programming paradigms: functional programming,
    assembly-language programming, and object-oriented programming-enabling
    the student to transition easily from Scheme to other programming
    languages.

The use of a different mix of exercises, a different philosophy and the explicit
tackling of object orientation and a transition path from scheme to another
language makes this an choice to check instead or along SICP. Again, the
application of the design recipes is something that enriches the experience in
my opinion.



Smalltalk, Objects and Design

I present this book as the best source to learn object orientation that I have
ever found. Considering that objects play such a huge importance on the software
industry in our times, I think a suggestion focused on that would be reasonable.

I think this book is very good because it also gets the epistemological stance
of Papert (1981), as the following extracts from
Liu (1996) show:

The goal is to design more like veteran software do. They choose among
alternatives quickly and subconsciously, drawing upon years of experience,
something like chess grandmasters choosing among moves. Lacking this experience,
novices have a hard time discovering plausible alternatives, and an impossible
time discovering subtle ones. For their sake then, I often argue alternatives
and the trade-offs between them, so that they will have an outside chance of
considering the same design the veterans do.



Conclusion

I've tried to convey an adequate way that if followed would benefit a person and
prepare it to became a competent programmer, not only in the sense of being able
to dish out code, but to think at several abstraction levels simultaneously.

What I wish to stress is that the mastery of this concepts takes
time and practice Liu (1996), as much as a decade according to
Norvig (2001). But to maintain a steady
progression one needs to develop a design taste. That is what I hope the
path outlined here would provide.

To wrap the article, I wish to cite Graham (2002) words on taste:

Mathematicians call good work ``beautiful'', and so, either now or in the
past, have scientists, engineers, musicians, architects, designers, writers,
and painters. Is it just a coincidence that they used the same word, or is
there some overlap in what they meant? If there is an overlap, can we use
one field's discoveries about beauty to help us in another?

For those of us who design things, these are not just theoretical questions.
If there is such a thing as beauty, we need to be able to recognize it. We
need good taste to make good things. Instead of treating beauty as an airy
abstraction, to be either blathered about or avoided depending on how one
feels about airy abstractions, let's try considering it as a practical
question: how do you make good stuff?



Bibliography


Manuel M. T. Chakravarty and Gabriele Keller.

The risks and benefits of teaching purely functional programming in
first year.

J. Funct. Program., 14 (1): 113-123, 2004.

ISSN 0956-7968.

URL http://dx.doi.org/10.1017/S0956796803004805.





Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram
Krishnamurthi.

How to Design Programs. An Introduction to Computing and
Programming
.

The MIT Press, Cambridge, Massachusetts London, England, 2001.

MIT - Massachusetts Institute of Technology - Online version
edition 22. September 2002:
http://htdp.org/2003-09-26/Book/curriculum.html - last visited
 Oct 2009.





Matthias Felleisen, Robert B. Findler, Matthew Flatt, and Shriram
Krishnamurthi.

The structure and interpretation of the computer science curriculum,
2002.





Robert Bruce Findler, John Clements, Cormac Flanagan, Matthew Flatt, Shriram
Krishnamurthi, Paul Steckler, and Matthias Felleisen.

Drscheme: A programming environment for scheme.

Journal of Functional Programming, 12: 369-388,
2001.





Paul Graham.

A taste for makers.

February 2002.

URL http://www.paulgraham.com/taste.html.





Chamond Liu.

Smalltalk, objects, and design.

Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1996.

ISBN 0-13-268335-0.





Marvin Minsky.

Society of Mind.

Touchstone Pr, touchstone. edition, 1988.

ISBN 0671657135.

URL
http://www.amazon.com/Society-Mind-Marvin-Minsky/dp/0671657135/.





Peter Norvig.

Teach yourself programming in ten years.

2001.

URL http://norvig.com/21-days.html.





Seymour Papert.

Mindstorms: Children, computers, and powerful ideas.

Basic Books, January 1981.

ISBN 0465046274.





Joel Spolsky.

The perils of javaschools.

2005.

URL http://
www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
.





Gerald Sussman and Harold Abelson.

Structure and Interpretation of Computer Programs - 2nd Edition
(MIT Electrical Engineering and Computer Science)
.

The MIT Press, July 1996.

ISBN 0262011530.

URL http://mitpress.mit.edu/sicp/full-text/book/book.html.





Gerald Jay Sussman.

Why programming is a good medium for expressing poorly understood and
sloppily formulated ideas.

In OOPSLA '05: Companion to the 20th annual ACM SIGPLAN
conference on Object-oriented programming, systems, languages, and
applications
, pages 6-6, New York, NY, USA, 2005. ACM.

ISBN 1-59593-193-7.

URL http://doi.acm.org/10.1145/1094855.1094860.





P. Wadler.

A critique of abelson and sussman or why calculating is better than
scheming.

SIGPLAN Not., 22 (3): 83-94, March 1987.

ISSN 0362-1340.

URL http://dx.doi.org/10.1145/24697.24706.



My emacs init.el file



(defvar my-default-lib "~/.emacs.d/lib")

(add-to-list 'load-path my-default-lib)

;; vimpulse, because I really like vim's key-bindings
(require 'vimpulse)
(require 'redo)

;; automatically sets the global mode for all buffers
(global-linum-mode 1)

;; styling. Check if not in terminal to set the nice colors and fonts.
(unless (string= 'nil window-system)
    (progn
      (set-face-attribute 'default nil :font "Liberation Mono 10")
      (require 'color-theme)
      (color-theme-initialize)
      (load-file (concat my-default-lib "/color-theme-twilight.el"))
      ;; (color-theme-billw)
      (color-theme-twilight)))

;;Setting up tabbar
(require 'tabbar)
(tabbar-mode 1)

;; define C-u and C-d to be like vim (equal pgup pgdown)
;; for some reason C-u was not working
(define-key viper-vi-basic-map "\C-u" 'scroll-down)

;; C-\ adds a lambda symbol, as DrRacket
(define-key viper-insert-global-user-map "\C-\\"
    (lambda () (interactive)
      (insert "λ"))) 

(setq-default viper-electric-mode 1)

;; set the viper >> and << keys to represent increase and decrease left margins
;;(define-key viper-vi-basic-map ">" 'increase-left-margin)

;; set the default spacing for ruby editing
(setq viper-shift-width 2)

;; sets C-[ to also mean C-g

;; page-up and page-down scroll bars for the tabs
;; basically modify the keys of tabbar
(global-set-key [C-home] 'tabbar-press-home)

(global-set-key [S-next] 'tabbar-forward-group)
(global-set-key [S-prior] 'tabbar-backward-group)

(global-set-key [C-prior]  'tabbar-backward)
(global-set-key [C-next] 'tabbar-forward)

;; newline also indents
(global-set-key "\r" 'newline-and-indent)

;; hide menus
(menu-bar-mode 0)
(tool-bar-mode 0)

;; some of the information below was lifted from
;; http://pintucoperu.wordpress.com/2010/03/04/utilizando-emacs-como-editor-de-texto-para-cc-python-y-vhdl-y-conociendo-el-modo-cua/

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; uniquify!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(require 'uniquify)
(setq uniquify-buffer-name-style 'reverse)
(setq uniquify-separator "|")
(setq uniquify-after-kill-buffer-p 1)
(setq uniquify-ignore-buffers-re "^\\*")

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Keep session
(desktop-save-mode 1)

;; disable the save mode
(global-set-key [f5] 'desktop-save-mode)

;; Inhibit startup window, very annoying
(setq inhibit-startup-message 1)

;; Makes final line always be a return
(setq require-final-newline 1)

;; Avoid to make a separate frame
(setq display-buffer nil)
(setq display-buffer-reuse-frames 1)
(setq pop-up-frames nil)

;; Put scrollbar on the right
(set-scroll-bar-mode 'right)

;; Disable tooltips
;; (tooltip-mode nil)

;; Make copy and paste to work with other programs
(setq x-select-enable-clipboard 1)
(setq interprogram-paste-function 'x-cut-buffer-or-selection-value)

;; we want fontification in all modes
(global-font-lock-mode t t)

;; maximum possible fontification
(setq font-lock-maximum-decoration t)

;; Provide templates for new files
(auto-insert-mode t)

;; put something different in the scratch buffer
(setq initial-scratch-message
      ";; scratch buffer created -- start typing...\n")

;; Automatically reload files after they've been modified
(global-auto-revert-mode 1)

;; When in text (or related mode) break the lines at 80 chars
(setq fill-column 80)

;; In every buffer, the line which contains the cursor will be fully
;; highlighted
(global-hl-line-mode 1)

;; Highlight search object
(setq search-highlight           t)

;; Highlight query object
(setq query-replace-highlight    t)

(setq standard-indent 2)

;; Use spaces instead of tab
(setq-default indent-tabs-mode nil)

;; Line by line scrolling
(setq scroll-step 1)

;; Mouse wheel scroll support
(mouse-wheel-mode t)

;; redefining the make-backup-file-name function in order to get
;; backup files in ~/.backups/ rather than scattered around all over
;; the filesystem. Note that you must have a directory ~/.backups/
;; made. This function looks first to see if that folder exists. If
;; it does not the standard backup copy is made.
(defun make-backup-file-name (file-name)
  "Create the non-numeric backup file name for `file-name'."
  (require 'dired)
  (let ((backup-location "~/.emacs.d/backups/"))
    (if (file-exists-p backup-location)
        (concat (expand-file-name backup-location)
                (replace-regexp-in-string "/" "!" file-name))
      (concat file-name "~"))))

;; redefining the make-auto-save-file-name function in order to get
;; autosave files sent to a single directory. Note that this function
;; looks first to determine if you have a ~/.emacs.d/autosaves/ directory. If
;; you do not it proceeds with the standard auto-save procedure.
(defun make-auto-save-file-name ()
  "Return file name to use for auto-saves of current buffer.."
  (if buffer-file-name
      (let ((save-location "~/.emacs.d/autosaves/"))
        (if (file-exists-p save-location)
            (concat (expand-file-name save-location) "#"
                    (replace-regexp-in-string "/" "!" buffer-file-name)
                    "#")
          (concat
           (file-name-directory buffer-file-name)
           "#"
           (file-name-nondirectory buffer-file-name)
           "#")))
    (expand-file-name
     (concat "#%" (buffer-name) "#"))))

;; Preserve the owner and group of the file you're editing
(setq backup-by-copying-when-mismatch t)

;; Show line-number in the mode line
(line-number-mode 1)

;; Show column-number in the mode line
(column-number-mode 1)

;; Remember the position where we closed a file
(setq save-place-file "~/.emacs.d/saveplace") ;; keep my ~/ clean

(setq-default save-place t) ;; activate it for all buffers
(require 'saveplace) ;; get the package

;; Ignore case when looking for a file
(setq read-file-name-completion-ignore-case t)

;; Full-screen mode
(defun djcb-full-screen-toggle ()
  "toggle full-screen mode"
  (interactive)
  (shell-command "wmctrl -r :ACTIVE: -btoggle,fullscreen"))

;; set key for the function above
(global-set-key (kbd "<f11>") 'djcb-full-screen-toggle)

;; autocomplete
(add-to-list 'load-path (concat my-default-lib "/auto-complete"))

(require 'auto-complete-config)
(add-to-list 'ac-dictionary-directories (concat my-default-lib "/auto-complete/ac-dict"))
(ac-config-default)


;; dirty fix for having AC everywhere
(define-globalized-minor-mode real-global-auto-complete-mode
  auto-complete-mode (lambda ()
                       (if (not (minibufferp (current-buffer)))
                           (auto-complete-mode 1))))

;; tab in insert mode calls autocomplete
(ac-set-trigger-key "TAB")
;; (define-key viper-insert-global-user-map (kbd "<tab>") 'auto-complete)

(real-global-auto-complete-mode 1)

;; quack configuration
(require 'quack)

;;slime configuration
(setq inferior-lisp-program "sbcl")
(add-to-list 'load-path (concat my-default-lib "/slime"))
(require 'slime)
(add-hook 'lisp-mode-hook (lambda () (slime-mode 1)))
(add-hook 'inferior-lisp-mode-hook (lambda () (inferior-slime-mode 1)))

;; spell-checking flyspell

;; must have this attribute set or else will complain about missing
;; -l parameter.
;; http://www.emacswiki.org/emacs/InteractiveSpell
(setq ispell-program-name "aspell")
(setq ispell-list-command "list")

(autoload 'flyspell-mode "flyspell" "On-the-fly spelling checker." 1)

(autoload 'flyspell-delay-command "flyspell" "Delay on command." 1)
(autoload 'tex-mode-flyspell-verify "flyspell" "" 1)

(dolist (hook '(lisp-mode-hook
                elisp-mode-hook
                ruby-mode-hook
                c-mode-common-hook))
  (add-hook hook (lambda () (flyspell-prog-mode 1))))

;; automatic line breaks and spelling check
(dolist (hook '(text-mode-hook TeX-mode-hook latex-mode-hook))
  (add-hook hook (lambda ()
                   (flyspell-mode 1)
                   (auto-fill-mode 1))))

(dolist (hook '(change-log-mode-hook log-edit-mode-hook))
  (add-hook hook (lambda () (flyspell-mode -1))))

(ispell-change-dictionary "american")

(defun fd-switch-dictionary()
  (interactive)
  (let* ((dic ispell-current-dictionary)
         (change (if (string= dic "brasileiro")
                     "american"
                     "brasileiro")))
    (ispell-change-dictionary change)
    (message "Dictionary switched from %s to %s" dic change)))

(global-set-key (kbd "<f8>") 'fd-switch-dictionary)


(dolist (hook '(lisp-mode-hook
                elisp-mode-hook
                ruby-mode-hook
                c-mode-common-hook))
  (add-hook hook (lambda () (flyspell-prog-mode 1))))


;; C style
(add-hook 'c-mode-hook
          '(lambda () (c-set-style "k&r")))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Maps swaps [ for ( and vice versa                   ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(keyboard-translate ?\( ?\[)
(keyboard-translate ?\[ ?\()
(keyboard-translate ?\) ?\])
(keyboard-translate ?\] ?\))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Paredit, a mode for editing S-expr based languages  ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(autoload 'paredit-mode "paredit"
  "Minor mode for pseudo-structurally editing Lisp code." 1)

(dolist (hook '(lisp-mode-hook
                emacs-lisp-mode-hook
                scheme-mode-hook
                ruby-mode-hook
                lisp-interaction-mode-hook))
  (add-hook hook (lambda () (paredit-mode 1))))


;; http://iinari.rubyforge.org/Basic-Setup.html#Basic-Setup
(require 'ido)
(ido-mode 1)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; rinari, a mode for rails, ruby and rhtml
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(add-to-list 'load-path (concat my-default-lib "/rinari"))
(require 'rinari)

(defun my-insert-erb-skeleton ()
  (interactive)
  (rinari-insert-erb-skeleton 1))

(define-key rinari-minor-mode-map "\C-c;a" 'my-insert-erb-skeleton)

;; add newline and indent to enter
(define-key rinari-minor-mode-map "\r" 'newline-and-indent)

;;; rhtml-mode
(add-to-list 'load-path (concat my-default-lib "/rhtml"))
(require 'rhtml-mode)
(add-hook 'rhtml-mode-hook
          (lambda ()
            (rinari-launch)))

(setq savehist-file "~/.emacs.d/tmp/savehist")
;; save history in minibuffer
(savehist-mode 1)

;; buffer to html
(require 'htmlize)

;; ecmascript mode
(require 'ecmascript-mode)

;; yasnippet, loads of emacs snippets
;; http://code.google.com/p/yasnippet/
(add-to-list 'load-path (concat my-default-lib "/yasnippet"))
(require 'yasnippet)
(yas/initialize)
(yas/load-directory (concat my-default-lib "/yasnippet/snippets"))

;; undo-tree
;; treats undo as a tree
(require 'undo-tree)
(global-undo-tree-mode)


(custom-set-variables
 ;; custom-set-variables was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 '(quack-fontify-style (quote emacs))
 '(ruby-indent-level 2))

(custom-set-faces
 ;; custom-set-faces was added by Custom.
 ;; If you edit it by hand, you could mess it up, so be careful.
 ;; Your init file should contain only one such instance.
 ;; If there is more than one, they won't work right.
 )