Sire, there is no Royal Road to Wisdom

Posts tagged papers

35 notes &

"The Essence of Functional Programming" Part 1: The Identity Monad


This is the first of a new series of posts that will take papers that I read and will explain them and attempt to make them more concrete (and less theoretical) by showing real world examples using more industry-standard languages. These papers will be tagged with theory-in-practice. For more information on the “Theory in Practice” series, read the introductory post.

Today’s paper is "The essence of functional programming" by Philip Wadler. This paper is widely known as the paper which popularized monads, and introduces them in a relatively elementary context with a focus on practical programming use.

This is part 1 of a multi-part series. In order to allow the information to soak in and to not consume too much of your time, I’ve decided to split this into multiple parts which I will publish over the coming weeks. These will all be tagged with essence-of-functional-programming.

Part 1 will cover the inspiration for monads as well as introduce the trivial monad.

Prior knowledge required: Basic programming experience with basic experience in functional programming (in any language, whether it be Ruby, Python, C, etc.). The examples will be given in Haskell and Scala.

Read More

Filed under Functional person papers links

10 notes &

CS Papers


  1. David R. Musser; Introspective Sorting and Selection Algorithms
  2. Laila Khreisat; QuickSort A Historical perspective and Emperical Study
  3. Bjorn Poonen; The worst case in Shellsort and related algorithms
  4. Falk Hueffner, Rolf Niedermeier and Sebastian Wernicke; Techniques for Practical Fixed-Parameter Algorithms
  5. Robert W. Irving, David F. Manlove and Gregg O’Malley; Stable marriage with ties and bounded lenght preference lists


  1.  Tony Hoare; The Verifying Compiler: A Grand Challenge for Computing Research
  2. C.A.R. Hoare; An Axiomatic Basis for Computer Programming
  3. Mike Barnett, K. Rustan M. Leino and Wolfram Schulte; The Spec# Programming System: An Overview
  4. Bertrand Meyer; Applying “Design by Contract”

Artifical Intelligence

  1. Jonathan Schaeffer, Neil Bruch, Yngvi Bjornsson, Ahikiro Kishimoto, Martin Mueller, Robert lake, Paul Lu and Steve Sutphen; Checkers is solved
  2. Ralph Gasser; Solving Nine Men’s Morris
  3. Gerald Tesauro; Programming backgammon using self-teaching neural nets
  4. Michael Genesereth, Nathaniel Love; General Game Playing: Overview of the AAAI Competition
  5. Sylvain Gelly, Levente Kocsis, Marc Schoenauer, Michele Sebag, David Silver, Csaba Szepesvari and Olivier Teytaud; The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions
  6. Huma Shah; Conversation, deception and intelligence: Turing’s question-answer game
  7. Stuart Shieber; Lessons from a Restricted Turing Test

Software Engineering

  1. Wil van der Aalst; Service Mining: Using Process Mining to Discover, Check, and Improve Service Behavior
  2. Joerg Becker, Michael Rosemann, Christoph von Uthmann; Guidelines of Business Process Modeling
  3. Inge van der weerd, Stefan de Weerd and Sjaak Brinkkemper; Developing a Reference Method for Game Production by Method Comparison

Operating Systems

  1. Tonya Gisselberg; The Trademark History of Linux, the Operating System
  2. Pawan Goyal, Xingang Guo and Harrick Vin; A Hierarchical CPU Scheduler for Multimedia Operating Systems
  3. S. Weiss; Introduction to Memory Management in GTK+


  1. Svante Carlsson; The deap- a double-ended heap to implement double-ended priority queues
  2. Atkinson, J.-R. Sack, N. Santoro and T. Strothotte; Min-Max Heaps and Generalized Priority Queues
  3. A. Arvind and C. Pandu Rangan; Symmetric Min-Max heap: A simpler datastructure for double-ended priority queues
  4. Robert W. Irving; Stable marriage and indifference
  5. R.Douglas Chatham, Gerd H. Fricke and R. Duarte Skaggs; The Queens Separation Problem
  6. Alvin E. Roth; What have we learned from market design?
  7. C. Bradley Wallis, Kannan P. Samy, Alvin E. Roth and Michael A. Rees; Kidney paired donation

From http://www.liacs.nl/~graaf/STUDENTENSEMINARIUM/


How to share a secret

Filed under papers computer science algorithms sorting complexity compiler people os

2 notes &

B-trees, Shadowing, and Clones

** Stand on the shoulders of giants!

From: Ohad Rodeh of IBM Haifa Research Labs

 B-trees are used by many file-systems to represent files and directories. They provide guarantied
logarithmic time key-search, insert, and remove. File systems like WAFL and ZFS use shadowing,
or copy-on-write, to implement snapshots, crash-recovery, write-batching and RAID. Serious
difficulties arise when trying to use b-trees and shadowing in a single system.


B-trees [R. Bayer and E. McCreight 1972],
Deletion Without Rebalancing in Multiway Search Trees,
and more,
The Ubiquitous B-Tree by Douglas Comer,
B+ Trees and Indexed Sequential Files: A Performance Comparison by D.S. Batory
The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes by John T. Robinson,
Efficient Locking for Concurrent Operations on B-Trees by PHILIP L. LEHMAN
) are used by
several file systems 
[A. Sweeny et al. 1996; S. Best 2002; J. Menon et al. 2003; H.Reiser ] to represent files and directories.
Compared to
(traditional indirect blocks [M. McKusick et al. 1984: A Fast File System for UNIX:: A reimplementation of the UNIX file system is described.],
Mechanics of Disk Access, Design and Implementation of the Second Extended Filesystem
b-trees offer guaranteed logarithmic time key-search, insert and remove. Furthermore, b-trees can represent sparse files well.


Shadowing is a technique used by file systems like WAFL [D. Hitz et al. 1994] and
ZFS [V. Henson et al. 2003] to ensure atomic update to persistent data-structures.
It is a powerful mechanism that has been used to implement snapshots, crashrecovery, write-batching, and RAID. The basic scheme is to look at the file system as a large tree made up of fixed-sized pages. Shadowing means that to update an on-disk page, the entire page is read into memory, modified, and later written to disk at an alternate location.

When a page is shadowed its location on disk changes, this creates a need to update (and shadow) the immediate ancestor of the page with the new address. Shadowing propagates up to the file system root. We call this kind of shadowing strict to distinguish it from other forms of shadowing [J. Gray and A. Reuter 1993].
Figure 1 shows an initial file system with root A that contains seven nodes. After leaf node C is modified a complete path to the root is
shadowed creating a new tree rooted at A’. Nodes A, B, and C become unreachable and will later on be deallocated.

Filed under papers important data structures reference people cite definition file organization unix

64 notes &

What are some classic papers in linguistics that a beginner should read?

From the enlightening answer of Marc Ettlinger on Quora: http://www.quora.com/Linguistics/What-are-some-classic-papers-in-linguistics-that-a-beginner-should-read

Now i’m sure that i was interested in Computational Linguistics indeed.

The answer contains links to materials; it’s a real gem.

Anyway, here is the important lines from the answer(Emphasis belongs to me.)


Linguistics sits somewhere between sciences like

  • neuroscience,
  • computer science
  • and psychology and humanities,
  • including modern languages
  • and philology.

What this means for your question is that

whereas knowledge of the former is often encapsulated in papers, knowledge about the latter is captured in books,

so this list will include both.

Linguistics is vast (or half-vast) so it isn’t practical to try to cover the whole field in one answer. (Computational Linguistics alone deserves its own answer: What are the most important research papers which all NLP students should definitely read?)  However, I’ll highlight a few classic books and articles with the idea that there are many that I’m leaving out.


In another answer, I also pinpointed some books for beginners: What are the best books to read on linguistics?Those are more general ed books though and less cited and less of use to researchers.


Filed under linguistics best vocabulary review reference links list person papers

0 notes &

Pushing an Idea - How many pages? How long…?

Marathon how long it’s been done and still
not yet set foot upon you - from the lyrics of Marathon by Tennis

Pushing an idea - http://www.johndcook.com/blog/2012/08/26/pushing-an-idea/

…Leibniz published the first article on calculus in 1684, an essay that was a mere 6 pages long. Newton and Leibniz would surely be astounded to learn that today’s introductory calculus textbook contains over 1,300 pages. …



with other names Ficlet, Fan Fiction, Microstories and Ultra-Shorts[Below 300 words length]:

  • Vignette,
  • Drabble[100 words length],
  • Double Drabble[200 words length],
  • Minisaga[short piece of writing containing exactly 50 words, plus a title of up to 15 words], …

Length of a Novel: http://en.wikipedia.org/wiki/Length_of_a_novel
List of Longest Novels: http://en.wikipedia.org/wiki/List_of_longest_novels

Flash fiction is a style of fictional literature or fiction of extreme brevity - http://en.wikipedia.org/wiki/Microfiction 

Other definitions place the maximum word count of the short story at anywhere from 1,000 to 9,000 words. In contemporary usage, the term short story most often refers to a work of fiction no longer than 20,000 words and no shorter than 1,000, or 5 to 20 pages. Stories of fewer than 1,000 words are sometimes referred to as “short short stories”,[5] or “flash fiction.” - http://en.wikipedia.org/wiki/Short_story


Flash What? A Quick Look at Flash Fiction - http://www.writing-world.com/fiction/flash.shtml

Short History of the Short Story: http://www.prospectmagazine.co.uk/magazine/william-boyd-short-history-of-the-short-story/

Flash Fiction: A List of Resources: http://www.thereviewreview.net/publishing-tips/flash-fiction-list-resources

Flash Fiction Chronicles: http://www.everydayfiction.com/flashfictionblog/tag/word-count/




Fiction and Word Counts: http://bardicblogger.wordpress.com/2011/09/19/fiction-and-word-counts/

Word Counts - http://en.wikipedia.org/wiki/Word_count
"Smiley lists novels as typically being between 100,000 and 175,000 words

     Under 1000      :     Flash fiction, or “short short” stories
     1,000-7,500     :     Short story
     7,500-20,000   :     Novelette
     20,000-50,000  :     Novella
     Over 50,000     :     Novel


and now…!:

  1. http://mathoverflow.net/questions/7330/which-math-paper-maximizes-the-ratio-importance-length
  2. "On the Number of Primes Less Than a Given Magnitude") is a seminal 10-page paper by Bernhard Riemann published in the November 1859 - http://en.wikipedia.org/wiki/On_the_Number_of_Primes_Less_Than_a_Given_Magnitude
  3. John Nash’s “Equilibrium Points in n-Person Games” is only about a page and is one of the most important papers in game theory.
  4. E. Nelson, “A Proof of Liouville’s Theorem”, 9 lines long.
  5. Paul Cohen’s paper “The independence of the continuum hypothesis” in which he introduced forcing. Six pages long (and another six in the second paper, a year later) that completely changed logic and set theory.
  6. Zermelo’s paper introducing the axiom of choice, a three pages long paper proving the well ordering theorem.
  7. The one-page paper - Golay, Marcel J. E.: “Notes on Digital Coding”, Proc. IRE 37, p. 657, 1949, which introduces the Golay code.
  8. The 1958 paper of Kolmogorov entitled “A new metric invariant of transient dynamical systems and automorphisms in Lebesgue spaces” is four pages long. This is the paper in which he defines the entropy of a dynamical system.
  9. Leonid Levin (1986), Average-Case Complete Problems, SIAM Journal of Computing 15: 285-286? Quite important in complexity theory, and only two pages long, although very, very dense.

Filed under literature literary technique best important math papers computer science