2008-01-02

Emacs lisp Lesson: Hash Table

Emacs lisp Lesson: Hash Table

Xah Lee, 2008-01

This page shows you how to use hash table in emacs lisp. If you don't know elisp, first take a gander at Emacs Lisp Basics.

(for HTML version with colors and links, see:
http://xahlee.org/emacs/elisp_hash_table.html
)

---------------------------------------------
What Are Hash Tables

Often, you need to have a list with elements being key-value pairs. For example, the key may be a person's name, and the value can be their age. Or, in a more complex case, the key can be the person's ID number, and the value can be a data of name, age, sex, phone number, address, etc. You might have thousands of such entries, and you want to be able to know that, given a ID, find out whether it exists in your data. You also want to be able to add or delete, modify entries in the data.

From a interface point of view, such a keyed list looks like this: “((key1 value1) (key2 value2) (key3 value3) ...)”. If you want to know a particular key exist, you can write a loop thru the list to test if any first element of a element matches your given key. Similarly, you can add a entry by appending to the list, or delete and modify the list using your language's list-manipulation operators or functions. All this functionality is provided in elisp, called Association List.

Reference: Elisp Manual: Association-Lists.

However, this method will be too slow to the point of unusable if your have thousands of entries and frequently need to check, add, delete, or modify the data. This is because most languages are not smart enough to analyze your use of list to determine how best to compile it in the language. The solution provided in most high-level languages of today is to provide a particular data type (called a hash table), so that when you want to use a list of huge number of pairs with fast lookup, you use that data type.

For example, here's how hash table looks like in some high-level languages:

# perl
%mydata = ("mary"=> 4, "jane"=> 5, "vicky"=>7);

# PHP
$mydata = array("mary"=> 4, "jane"=> 5, "vicky"=> 7);

# Python
mydata = {"mary":4, "jane":5, "vicky":7}

(see Keyed List in Python and Perl, PHP: Keyed List) Similarly, elisp provides a hash table datatype.

Note: Hash table is also known as hash, keyed-list, dictionary, map. It's called hash table for historical reasons. Basically, a technique to create fast-lookup of a data, is by using a so-called hash-function, that converts the key into a unique (randomish) number. So that, instead of going thru the huge list to check every item, you just check one particular memory address to see it exists. Such a function is called “hash-function” because its key-conversion operation is analogous to processing a type of food dish made by disorderly and irreversibly chopping up and mixing up veggies or meat. (See Hash function↗, Hash (food)↗, Hash browns↗. )

(If your data needs more entries than that, the proper solution is to use a Relational Database↗.)

---------------------------------------------
Hash Table In Elisp

To create a hash table, use “(make-hash-table :test 'equal)”.

Here's a complete code that shows how to creat a hash table, then add, change, remove, entries:

(let (myhash val)

;; create a hash table
(setq myhash (make-hash-table :test 'equal))

;; add entries
(puthash "mary" "19" myhash)
(puthash "jane" "20" myhash)
(puthash "carrie" "17" myhash)
(puthash "liz" "21" myhash)

;; modify a entry's value
(puthash "jane" "16" myhash)

;; remove a entry
(remhash "liz" myhash)

;; get a entry's value
(setq val (gethash "jane" myhash))

(message val) ; print it
)

In the above example, both the entry's keys are datatype “strings”. However, elisp's hash table can have any lisp object as the key or value. When we create a hash table, we used “:test 'equal” to let elisp know that the function “equal” should be used when testing whether a key exists. If your keys are other lisp data type, you need to specify which equality functon emacs should use to test if a key exist. The available value for “:test” are “'eql”, “'eq”, “'equal”. (You can also define your own equality test. See elisp manual for detail. (linked at bottom of this page))

To clear all entries in a hash table, use “(clrhash «myhash»)”.

-------------------
Check If A Key Exists

To check if a key exists, use the “(gethash «mykey» «myhash»)”. If it exists, its value is returned, else “nil” is returned. Example:

(let (myhash)
(setq myhash (make-hash-table :test 'equal))
(puthash 'mary "19" myhash)

(gethash 'vicky myhash) ; returns nil
)

“gethash” has a optional third parameter “default”. If the key does not exist, “default” is returned.

-------------------
Apply A Function To All Key-Value Pairs

To apply a function to all entries in a hash table, use “(maphash «myfun» «myhashtable»)”. The function “myfun” must take 2 arguments, key and value. For example, if you want a list of all keys, you can write a function that puts the key into a list, then print out the list. We show several examples below.

-------------------
Get All Keys

To get all keys into a list, we can use a maphash with a function that pulls the keys into a list. Here's a example:

;; example of getting all keys from a hash table
(let (myhash allkeys)

;; add items to the hash
(setq myhash (make-hash-table :test 'equal))
(puthash "mary" "19" myhash)
(puthash "jane" "20" myhash)
(puthash "carrie" "17" myhash)
(puthash "liz" "21" myhash)

;; set to a empty list
(setq allkeys '())

(defun pullkeys (kk vv)
"prepend the key “kk” to the list “allkeys”"
(setq allkeys (cons kk allkeys))
)

;; get all the keys
(maphash 'pullkeys myhash)

;; sort and print it out
(sort allkeys 'string<)
)

In the above example, “pullkeys” is used only once. Since it is used only once, we don't need to define it separately, but just use lambda construct. So, the maphash line can be just like this: “(maphash (lambda (kk vv) (setq allkeys (cons kk allkeys))) myhash)”.

You can define a “keys” function that returns all keys of a given hash table. Like this:

(defun keys (hashtable)
"Return all keys in hashtable."
(let (allkeys)
(maphash (lambda (kk vv) (setq allkeys (cons kk allkeys))) hashtable)
allkeys
)
)

With this function, you can use it like this: “(keys myhash)”.

-------------------
Get All Values

Getting all values is just like getting all keys above. Here's a function that does it.

(defun hash-values (hashtable)
"Return all keys in hashtable."
(let (allvals)
(maphash (lambda (kk vv) (setq allvals (cons vv allvals))) hashtable)
allvals
)
)

-------------------
Print All Entries Sorted By Key

Here's a example how you can print out all entries in a hash table by sorted key.

First, we define a function that turns a hash table into a list.

(defun hash-to-list (hashtable)
"Return a list that represent the hashtable."
(let (mylist)
(maphash (lambda (kk vv) (setq mylist (cons (list kk vv) mylist))) hashtable)
mylist
)
)

;; example of turning a hash table into list then sort it
(let (myhash mylist)

;; add items to the hash
(setq myhash (make-hash-table :test 'equal))
(puthash "mary" "19" myhash)
(puthash "jane" "20" myhash)
(puthash "carrie" "17" myhash)
(puthash "liz" "21" myhash)

;; get the hash table into a list
(setq mylist (hash-to-list myhash))

;; sort and print it out
(sort mylist (lambda (a b) (string< (car a) (car b))))
)

;; prints (("carrie" "17") ("jane" "20") ("liz" "21") ("mary" "19"))


-------------------
Hash Table With Lisp Objects

Elisp's hash table's key or value can be any lisp object. Also, you can define your own equality test, as well as providing few other parameters when creating a hash table. For detail, see elisp manual.

Reference: Elisp Manual: Hash-Tables.

Emacs is beautiful!

Xah
xah@xahlee.org
∑ http://xahlee.org/

2007-12-30

Lispers and Wikipedia

Lispers and Wikipedia

2007-12-27

[The following is posted to comp.lang.lisp newsgroup in a thread's tangent discussion on contributing to Wikipedia]

permanent link: http://xahlee.org/Periodic_dosage_dir/encyclopedia.html

Please people, by all means, add and edit to Wikipedia lisp related info!

I've been reading and editing Wikipedia like for 2 to 8 hours every damn day since about 2003-11. (mostly just reading in the past year) My website has over 3786 links to Wikipedia, and i basically read every article i've linked to. For each article i have linked, there are about 10 more articles i've read.

I read encyclopedias with greed like a leech sucking on blood since ~1992. And i can tell you, with my life's saving on the table, that Wikipedia today as it is in terms of quality and quantity, in depth and in breadth, and all things considered, is FAR beyond any 10 professional encyclopedias and or specialized encyclopedias and references and compendiums and annals COMBINED! (this includes, for example, Encyclopedia Britanica, and any specialized math encyclopedia or computing encyclopedia) (take a minute to ponder the gravity of this claim. And, if you like, try to spend few hours verify it) (i'd write more detail to back up this claim but that's be adding another thousand words to this already long post.)

And when i read computing related articles in Wikipedia, i see motherfucking Perl this and Python that and Ruby this and Java that and how versatile they are fucking shit everywhere inappropriately, but which you can't touch because anytime you try to correct, the motherfuckers that are these (innocently or otherwise) ignorant yet fanatical tech geekers ARMY of them revert it back. While, in places i see where lisp info is appropriate, it's not there! And on occasion in recent months i mentioned particular pages in lisp or scheme groups, these fucking aloof shitheads think they all above it and do nothing. (especially the Schemers. Fuck them. Die!)

Although personally i too have gripes and political issues with Wikipedia, or some of its policies, and sour grape syndrome on how it should be or should not be, but overall i have the highest esteem for Wikipedia, and Wikipedia considered in social framework in my opinion is changing the world in a global scale, far more powerful than any organized religion or political group (such as the George Bush motherfucker). If a calamity by Zeus is to fall upon this earth and wipe out all websites for good except one, that one should be Wikipedia.

Wikipedia is not only the supreme force in changing us human animal's social structure and outlook, it is also leading many good technology in many ways. For example, it is a prime (and perhaps effectively the ONLY) force in pushing svg, ogg formats, and due to Wikipedia's immense popularity, its force is so powerful in a practical way that even the combined commercial mega corporations with their proprietary formats will fear (you name it: Apple's music/video formats, Microsoft's, Adobe's PDF and Flash stuff...etc). (Note: i'm not against proprietary formats.) And, it is just about the ONLY high-trafficked website that produces valid HTML. Imagine that, folks. (in various language and tech groups, such as python, perl, lisp etc all claim superiority, but one look at the html docs they produced, all are motherfucking invalid html with errors lighting up like a Xmas tree.) (Wikipedia's traffic is ranked within top 10 or so in Alexa.com for the past 2 or more years. (my website is ranked ~80k and every single 3400+ HTML pages on my website is correct (aka valid) HTML too))

Sure, Wikipedia is getting big now and fat, with big power, but let's not all be too tech geeking cynical about corruption. FSF/OpenSource is pretty big now like a juggernaut too. (In fact, you can consider Wikipedia as rather a _direct_ product of FSF's ideals. (further, i'd argue that the primary force of FSF, lies in its GPL, and the power that drove GPL, is its cruel, unforgiving, “fuck you” nature of its “fight fire with fire” aspect, eagerly operated and cultivated by the cruel, unforgiving, aggressive, males (mostly young) specie of the human animals society.))

So, lispers, go read and edit Wikipedia! You don't have to devote your precious time and knowledge to do edit-wars with Perl or Python army of morons on board, but when at leisure or chance upon, do try to correct or add info as you see fit.

Graphics Programing Pains

Perm url with updates: http://xahlee.org/3d/graphics_programing_pain.html

Graphics Programing Pains

Xah Lee, 2007-12-29, 2009-06

[this essay is a rambling about programing GUI app and 3D geometry]

I have a problem. I want to do 3D geometry visualization programing, but there is no appropriate tools. (see Requirements For A Visualization Software System For 2020) O, fuck the industry.

GUI Programing Pain

I never had any experience writing a GUI application. (except web/HTML form based ones, which doesn't really count.) About 3 times in different years since 1997, i tried to learn GUI programing thru Java's Swing (Java). But each time i aborted rather even before getting a basic understanding of how to create a menu. Today is another try, and perhaps the furthest i've made. To make a empty window with a menu with no actions attached, requires some fucking 170 lines of java code, and tens of classes and objects with complex relationships. (sample code here:MenuLookDemo.java)

So, i am wondering, is this the general state of affairs for GUI programing, or is it just Java? I asked a bit on freenode irc, and it seems to be java, although i guess programing GUI using any widget toolkits is not gonna be a walk in the park.

I like to work on software projects that are mission critical, or backend engines, so i don't regard GUI apps that much important. Nevertheless, GUI, as its name implies, provides a graphical user interface, and is in fact a element most software needs. In particular, one of my hobby is programing geometric visualization. Imagine viewing and rotating a molecule structure in 3D. Such a software requires a GUI.

So, even knowing it's gonna be a pain, and at this point i'm gonna abandon Java's Swing again because it is intolerable, but i did half-heartedly looked into alternatives of GUI widgets, in part to acquaint myself what's out there, and maybe pave the road to learn a thing or two about how to actually use a widget toolkit to create a menu or button.

It seems to me, the most popular free GUI widget out there are: GTK, Qt (toolkit), Tk (framework).

Each has various language bindings. I think i might want to start to tinkle with PyGTK.

One thing interesting is that Cairo (graphics) is a recently developed library for drawing vector graphics, and recent version of GTK+ uses it.

The following apps i'm familiar with uses Qt: KDE (linux desktop), Linux version of Mathematica, Google Earth, Opera (web browser), Skype, TeamSpeak.

3D Programing Pain

Ok, that's about the GUI bit. But what about geometry visualization programing bit? The answer, is pretty much OpenGL (Mesa 3D), Direct3D.

Direct3D is Windows only. Since my professional expertise all lies in unix, and basically don't know much about Windows's technologies, so Direct3D is out for me.

Now, i have read about OpenGL a lot since 1994... but basically it is more low-level pain, perhaps a order of magnitude more painful than doing Java Swing. However, if you really want to get down to creating a geometry visualization software that is good quality (namely, fast), OpenGL or similar is a inevitability. (the alternative, of doing projections yourself and paint them to screen, is hackish and way slower)

Given my problem and persistent infatuation with visualization of geometry, i think going down getting familiar with OpenGL stuff is necessary, or strongly advisable. So, i started to read many articles on Wikipedia related to computer graphics, in particular the low level stuff. Here's some random articles or terms i'm learning or read.

Graphics pipeline. This is the most important concept. Basically, a 3D scene is passed to the graphics card, and processed in various stages, to produce a 2D bitmap for the screen.

Here are some general important concepts.

Some concepts at the bitmap stage.

  • Z-buffering A method to determine which pixel (of objec) is visible. This approach basically outdates the Painter's algorithm
  • Anti-aliasing Woot! all i know about anti-aliasing is in the context of fonts and line drawing. Didn't explicitly know the implementation is so deep.
  • Alpha compositing basically for handling transparencies.
  • Mipmap basically reducing the computation time by pre-storage of scaled-down bitmaps for surface texture rendering purposes.
  • Texture mapping Applying a bitmap to surface, either for the purpose of creating a image on the surface (say a pict on cereal box), but usually for the purpose of faking surface qualities (i.e. a tree bark, fresco wall).
  • Bump mapping. A specialized texture mapping technique to simulate uneven surfaces. (say, on a orange)

3D Engines

... it seems to me that there are no high-level graphics engines. Fahrenheit graphics API and QuickDraw3D are supposed to be the one but went no where.

Some of the free game engines:

This seems to be the best: O3D for my needs. It uses a highlevel lang JavaScript, so i don't have to worry about low-level graphics fuck. It accesses GPU transparently, so i don't have to worry about it. It runs in browser, which is what i need for my visualization apps. And it is in the position to be standardized as web 3D tech. The downside is that this will be few years to come.

Some free physics engines:

Game Development

Here's some articles related to game development.

wikipedia readings on evolutionary biology

2007-12-30


Excursion into evolutionary biology:





A quote from the Sexual Selection article:



«Sexual selection is the theory proposed by Charles Darwin that states that the frequency of traits can increase or decrease depending on the attractiveness of the bearer. Biologists today distinguish between “male to male combat” (it is usually males who fight), “mate choice” (usually female choice of male mates) and “mate coercion” (forced mating). Traits selected for by male combat are called “weapons”, and traits selected by mate choice are called “ornaments”.»