The mysterious case of $ and $! in Haskell

Has anybody noticed the difference in Haskell between the operators ($) and ($!)?

($!) is strict function application. That is, it evaluates the argument before evaluating the function.

This is contrary to normal lazy function application in Haskell, e.g. f x or f $ x, which first start to evaluate the function f, and only compute the argument x if it is needed.

For example succ (1 + 2) will delay the addition 1 + 2 by creating a thunk, and start to evaluate succ first. Only if the argument to succ is needed, will 1 + 2 be evaluated.

However, if you know for sure that the argument to a function will always be needed, you can use ($!), which will first evaluate the argument to weak head normal form, and then enter the function. This way, you don't create a whole big pile of thunks and this can be more efficient. In this example, succ $! 1 + 2 would first compute 3 and then enter the function succ.

Note that it is not always safe to just replace normal function application with strict function application. For example:


ghci> const 1 (error "noo!")
1
ghci> const 1 $! (error "noo!")
*** Exception: noo!

Designing a Programming Language Can Be Fun

I recently stumbled upon a nice discussion started by Kanchi in the stacexchange forums. The discussion was if one were to design a programming language, how would one do it?



Such questions are too vague. Language features can't really be discussed until the purpose of the language is determined. Language design is a huge topic. If you're interested in designing a language, a good place to start is by thinking about what the deficiencies are in a language that you already know. Design decisions often arise from considering a design defect in another product.

Alternatively, consider a domain that you are interested in, and then design a domain-specific language (DSL) that specifies solutions to problems in that domain.

Once you have sketched out what you want your language to look like, try to write down precisely what the rules are for determining what is a legal and illegal program. Typically you'll want to do this at multiple levels:

• A reason for creating a new language
• A Philosophy
• A Semantic Definition
• A lexical description of your tokens
• A Syntax Analysis definition

How will your language be different? What is its mission? Is it functional? Is it object orientated? Is it a meta-language? What are its unique features? What will it give the world that doesn't exist (or exists in an ugly way)? How do you want to change things? Is it compiled or interpreted? A DSL or general purpose language? This is your philosophy and dictates alot about your language's design.

Next, work on scratching out rough syntax and semantics on paper. This will be your semantic definition ... writing fake code is a great way to develop your thoughts.

You will then need to define your tokens and syntax in some way. Programs then process these into automata capable of reading in strings and processing the syntax. Yacc and Bison use Regular Expressions and a BNF style syntax for lexical and syntax analysis respectively. There are also Yacc and Bison like tools in for other languages.

You will also need a grounding in language theory/compilers to know what NOT to do. Examples include ambiguous grammars, AST generation and manipulation problems and generally how to make life simple for yourself. Knowing the theory is very important.

This is how my dream programming language would look like:

• A powerful static type system with some support for dependent typing.
• Optional dynamic typing.
• Numeric Tower a la Lisp but statically typed.
• Macros a la Lisp.
• Primarily a Functional Programming language with basic support for imperative programming (like ML family).
• Garbage collection.
• Type inference.
• Continuations.
• Optional lazy semantics.
• All the control constructs would be provided in the form of library functions. (This can be made possible using last two features.)
• Minimal syntax (not as little as Lisps, but something of the sort of Ioke/Seph.)

Here are some good books that will help you out

Compilers: Principles, Techniques, and Tools
Modern Compiler Implementation in C

The Lazy Quantifier Bug

Try the following following expression to find a pattern of: "a" (optional) followed by up to two words, followed by "b", followed by "c".

The input is "x1 x2 x3 a b c" and therefore the match is "x3 a b c", since it satisfied the condition of up to two words before the "b".

Match match = Regex.Match("x1 x2 x3 a b c", @"((a\s+)?(\w+\s+){0,2}b\s+c)");


However,  turn the condition of up to two words to be lazy, and you get the match "x2 x3 a b c", which does not qualify the expression at all (lazy or not).

Match match = Regex.Match("x1 x2 x3 a b c", @"((a\s+)?(\w+\s+){0,2}?b\s+c)");


So why do we get "x2 x3 a b c" as a result of this regex?


This appears to be a Regex bug.  There are 2 groups in the match, this non-greedy pattern is producing.  The first group is the entire string "a x1 x2 x3 b c".  The second group is "x3".  But examine the second group's "Captures" collection and you will see 3 captures, namely x1, x2, x3.  Therefore, (\w+\s+){0,2}? captures 3 instead of at most two words.  Hence, I believe it's a bug.

Given the pattern, "a\s(\w+\s+){0,2}?b\s+c", the following strings should produce the following results

"a a b c" should match "a b c" at index=2 (but it matches "a a b c" instead)
"a x1 b c" should match "a x1 b c"
"a x1 x2 b c"  should match "a x1 x2 b c"
"a x1 x2 x3 b c" should not match (but it does)
"a a x1 b c" should match "a x1 b c" at Index=2  (but it matches "a a x1 b c" instead)
"a a a x1 b c" should match "a x1 b c" at index=4 (but it matches "a a a x1 b c" instead)
"a a x1 x2 b c"  should match "a x1 x2 b c" at index=2 (but it matches "a a x1 x2 b c" instead)
"a a a x1 x2 b c" should match "a x1 x2 b c" at index=4 (but it matches "a a x1 x2 b c" at index=2 instead)

The other pattern ("a\s(\w+\s+){0,2}b\s+c") works properly, i.e.,

"a a b c" should match "a a b c"
"a x1 b c" should match "a x1 b c"
"a x1 x2 b c"  should match "a x1 x2 b c"
"a x1 x2 x3 b c" should not match
"a a x1 b c" should match "a a x1 b c"
"a a a x1 b c" should match "a a x1 b c" at index=2
"a a x1 x2 b c"  should match "a x1 x2 b c" at index=2
"a a a x1 x2 b c" should match "a x1 x2 b c" at index=4

At first, I thought {0,2}? made no sense, but given the strings like "a a x1 b c", there is certainly a use for a non-greedy {n,m}.