Posts tagged papers
Posts tagged papers
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.
** Stand on the shoulders of giants!
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],
Prefix B-Trees by RUDOLF BAYER and KARL UNTERAUER,
Deletion Without Rebalancing in Multiway Search Trees,
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.
(traditional indirect blocks [M. McKusick et al. 1984: A Fast File System for UNIX:: A reimplementation of the UNIX file system is described.],
more, 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.
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
- 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: However, I’ll highlight a few classic books and articles with the idea that there are many that I’m leaving out.
- Broca (1865)- Pioneering study of neurolinguistics, identifying Broca’s area
- Saussure (1916).- Introduced a number of ideas fundamental to the study of modern linguistics including the arbitrariness of the sign and the importance of studying linguistics synchronically
- Sapir (1921)
- - Revealed striking patterns of regularity across languages
- Chomsky & Halle (1968)- Treatise on generative phonology
- Geschwind (1970).- Key state-of-the-art on language and the brain
- Ladefoged (1975)- The textbook on phonetics, to this day
- Lakoff & Johnson (1980)- One of the touchstones in the emerging Cognitive Linguistics
- Fodor (1983)- The clearest argument for encapsulation and modularity of the language faculty
- Werker & Tees (1984)- Helped establish the processes involved in the earliest stages of language understanding.
- Prince & Smolensky (1993)- Transformed phonology and persists as the dominant paradigm
- Nunberg, Sag & Wasow (1994)- A really nice example of a clear, interesting paper that I keep returning to over and over - more of a sentimental favorite on my part, plus Nunberg. Yes, that , before he was famous.
- Chomsky (1995)- The current paradigm for studying syntax
- Saffran, Aslin & Newport (1996)- Re-introduced the idea that language acquisition may depend on domain-general mechanisms
- Kuhl (2000)
- Hauser, Chomsky & Fitch (2002)- Pushed all the generative linguistics chips onto the notion of recursions
- Response: Pinker & Jackendoff (2004)- The counter-bet
- Everett (2005)- Made lots of headlines and inspired lots of research and debate.
- Hickok & Poeppel (2007).- An update on the state of the art in terms of the neuroscience of language.
In another answer, I also pinpointed some books for beginners:Those are more general ed books though and less cited and less of use to researchers.
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]:
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”, or “flash fiction.” - http://en.wikipedia.org/wiki/Short_story
FLASH FICTION RESOURCES
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/
• 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