Search

Life and Computing Science

Invictus

Abstract :: This is a poem that was introduced to me by a dear friend in the fall of 2016, in my first year of my PhD.

Two tigers face one another

Out of the night that covers me,
Black as the pit from pole to pole
I thank whatever gods may be
For my unconquerable soul.

In the fell clutch of circumstance
I have not winced nor cried aloud
Under the bludgeoning of chance
My head is bloody, but unbowed.

Beyond this place of wrath and tears
Looms but the Horror of the shade
And yet the menace of the years
Finds and shall find me unafraid

It matters not how strait the gate
How charged with punishments the scroll,
I am the master of my fate:
I am the captain of my soul.

This poem is by William Henley and the title is Latin for unconquered. Its associated wikipedia page says that the poem’s message of displaying fortitude in the face of adversity evokes Victorian stoicism, which is

the path to happiness for humans is found in accepting this moment as it presents itself, by not allowing ourselves to be controlled by our desire for pleasure or our fear of pain, by using our minds to understand the world around us and to do our part in nature’s plan, and by working together and treating others in a fair and just manner.

This poem is alive as well with the Invictus games.


( Photo by Frida Bredesen on Unsplash )

Advertisements

RWH Abridged :: 2 Types and Functions

Abstract :: We discuss the importance of typing, side-effects whose absence give possible efficiency theorems, evaluation schemes allowing infinite structures, and functions that can act on arbitrary types. Occasionally making comparisons with the C# language.

Essentially​, we briefly summarise some parts of the second chapter of Real World Haskell.

Why care about types

Every expression and function in Haskell has a type. For example, True has type Bool while "foo" has type String. The type of a value indicates that it shares certain properties with other values of the same type. In particular, there are operations that only make sense for values of a certain type. For example, we can add a pair of numbers and or a pair of Booleans, but it makes no sense —that is, it is generally undefined— to or a number with a Boolean.

Whenever you have some items for which an operation is sensible only when they satisfy a property then you may benefit by introducing a new type consisting of those items that satisfy the necessary property.

For example, we can catenate paths in a graph if the source of one is the target of the other: If we have a path in a graph from a node x to a node y and another path from node y to node z we can catenate them to obtain a path from x to y. Rather than consider paths and check the compatibility condition to assert the result is a valid path, we can simply introduce paths between nodes and define catenation as an operation on such paths. ( This is the “Category of paths over a graph”. )

Type systems give us abstraction —this cannot be overstated! The benefit of introducing abstraction is that it lets us forget or ignore low-level details.

If I know that a value in my program is a string, I don’t have to know the intricate details of how strings are implemented —whether it be an array or a linked list of characters or what have you. I can just assume they my string is going to behave like all other strings I’ve worked before. So, a type is a simple form of interfacing.

At the lowest level, a computer is concerned with bytes, with barely any additional structure. A type system gives us abstraction so that we can forget about bytes and treat them as certain values. A type adds meaning to plain bytes: It lets us say that “these bytes are text and those bytes are an airline reservation.” A type system will not allow us to mix up those values.

Programming is a bit like putting pieces into a jigsaw puzzle. A good type system won’t let us put a piece of the wrong shape wherever we like. Conversely, the lack of a type system, or so called dynamic type system, means that all the pieces are 1-by-1 squares and always fit (!), so you have to constantly examine the resulting picture and check (through testing) whether it is correct.

Haskell is strongly typed

Haskell will not automatically coerce values from one type to another. Coercion is also known as type casting or type conversion. For example, a C compiler will automatically and silently (!) coerce a value of type int into a float in a context expecting a float, but a Haskell compiler will raise a compilation error in a such a scenario.

We must explicitly coerce types by applying coercion functions. If we want something done, we must say so. Unlike other languages, silence does not mean consent to coercion!

We will not “accidentally” use a string when a number is expected, since there is no default coercion. We side-step such silent dangers by being explicit about what we want to accomplish.

Haskell is statically typed

Having a static type system means that the compiler knows the type of every value and expression at compile time, before any code is executed. For example, True && 0 may be passable in a C-like language, but not for a Haskell compiler: Both arguments of conjunction && must be Boolean.

This feature allows Haskell to use the surrounding code to infer, deduce, the type of a variable. In other languages, the type system is a burden serving the compiler; in Haskell, it serves you. I can open a script and write f x = x + 1 and a Haskell compiler can accurate deduce that f takes numeric types to numeric types; which we can indicate explicitly as well by, say, f :: Int -> Int before the definition of f. We read x :: T as “x is of type T“; the arrow -> is read “to”.

In languages such as Python, duck typing is common, where an object acts enough like another to be used as a substitute for it: If it walks like a duck, and quacks like a duck, then let’s call it a duck.

It is the combination of strong and static typing that results in Haskell code often having fewer trivial bugs than that of another language. Indeed such systems help to ensure the absence of runtime type errors.

Purity : the case for being explicit yet again

A side effect introduces a dependency between the global state of the system and the behaviour of a function. For example, in an imperative language, consider a method that reads and returns the value of a global variable. If some other code can modify that global variable, then the result of a particular application of that method depends on the current value of the global variable. The method has a side effect, even though it never modifies the variable itself.

Side effects are essentially invisible inputs to, or outputs from, methods. In Haskell, the default is for functions to not have side effects: The result of a function depends only on the inputs that we explicitly provide. Such functions are called pure; methods with side effects are impure.

In imperative language, such as C#, one may explicitly mark a function as Pure, otherwise it is assumed impure and this is the case in a usual imperative language. Incidentally, pure functions are less common and so not the default. Whereas in Haskell, it is the other way around: All functions are by-default pure since they are the more common utility and impure functions are indicated by their type, say by the words IO appearing in the type somewhere.

Variables: names versus references

In an imperative setting, a variable identifies a memory location and so its contents can be altered with time. In a functional setting, a variable is an alias for an expression and serves as an abbreviation for the sake of clarity and to avoid having to write out the entire expression in full each time it is used. In Haskell, a function is also a variable and so it is treated similarly. Such an alias, or naming, can only be bound to one expression.

In a functional setting, once we’ve bound a variable to an expression, we know that we can always substitute it for that expression, because it will not change. This notion of substitutability does not hold in general in imperative programs since, for example, the code g( f(), f() ) cannot be replaced with let x = f() in g(x, x) since the two calls to f may have side-effects such as altering global state or printing output, which may not be the same as if doing f once.

Conditionals : the necessity of else is only sensible

Suppose you wish to define a notion of conditional expressions for any type. In pseudo-Haskell notation, in-fact this is close to Agda notation,

if_then_else_ :: ∀{type a} → Bool → a → a → a
if True  then t else f = t
if False then t else f = f

Functional programs are expression-oriented and so the branches of the conditional must have the same type for the conditional to be sensible. Indeed, what sensible type does one assign to something like if b then 1 else "apple"? If b is true this is a number, otherwise it is a string. Hence, we cannot statically assign it a type and as such any context in which it appears would also need to consider the cases of the result being a number or a string —even though it may always be one and not the other! ( That is, when b is constant. )

In an imperative language, it can make sense to omit the else branch from a conditional, since there one is working with statements, or commands. In such a case, the “missing else” is implicitly defined to be the empty statement, called skip or simply ; in most C-based languages.

( In an imperative program, commands can be composed by sequencing which has the empty statement as unit and so form a monoid. For a monoid (M, ⊕, e), we can define an else-less conditional:

if_then_ :: ∀{monoid (m, ⊕, e) } → Bool → m → m
if b then t = if b then t else e

The monoid structure ensures we have a default element of our type, namely e, to use when the condition does not hold. In-fact the monoid structure is a bit overkill, it suffice to just request a function default :: ∀{nonempty type a} → a and we can use that in-place of e. Such a function is used in C# for whenever one wants a default value for a type. )

Lazy Evaluation

In most languages, the arguments to a method are evaluated first and then the method is applied; this is strict evaluation. Haskell, on the other hand, is non-strict: It evaluates arguments on a need-by-basis, possibly never evaluating them at all! For example, defining the function f b n = if b then 0 else n and then calling it with arguments 0 < 1 and the length of the infinite list [1..] we have

  f (0 < 1) (length [1..])
=   { rewrite via definition }
  if (0 < 1) then 0 else length [1..]
=   { conditional can only be simplified further if we simplify the guard }
  if True then 0 else length [1..]
=   { conditional with True guard selects then-branch }
  0

Notice that we never evaluated length [1..] since it was never needed! Which is great, since we can never computer the length of an infinite list in finite time anyways!

Haskell creates a “promise” that when the value of a sub-expression is needed, it can compute it. The record type that is used to track an un-evaluated expression is known as a thunk.

However, such a lazy evaluation scheme has some surprises when working with IO. For example, suppose you request input and bind it to some variable, then if you never use that variable for anything, it is never actually evaluated and so the actual request never occurs! More on this later.

Polymorphism

When a function’s signature has variables in its signature, indicating that some of its arguments can be of any type, we call the function polymorphic. The prefix poly means many and morph means form; so such functions have many-forms of usage.

In Haskell, (type) variables always start with a lowercase letter, whereas concrete types are distinguished by having their names start with a capital case letter.

Haskell supports parametric polymorphism: Types may have parameters that we can later bind to concrete types. Not only does the implementing code not care what the concrete type is, but it has no way to find out what the real type is, or manipulate a value of that type. It cannot create a value; nor can it inspect one. All it can do is treat is as a fully abstract black-box.

For example, consider a function that takes a list of any type, denoted [a], and returns an element of that type a. Such a function has type [a] -> a. If the list is empty, then we can not do anything to obtain a value of type a and so such a function cannot be defined on empty lists —we have no default as in C# to obtain a value of the type parameter. If the list is non-empty, then it is of the form x : xs, that is an element of type a followed by another list of type [a]. At this point we can simply return x or continue to look at xs and pick an element from there. Hence, the only functions of type [a] -> a are the array indexing functions [x₀, x₁, …, xₙ₋₁] ↦ xᵢ for some i.

As seen, parametric polymorphism means that the implementation of a function can only have a particular form due to the typing.

In contrast, other languages such as C# provide subtype polymorphism and allow one to inspect the abstract type. For example, using the is and as keywords in C# we can check if the type a is a subtype of a numeric type, or if it implements a particular interface, and if so cast the elements to be such and then after indexing to obtain an element from the list, we can perform any numeric operation or by-pass the indexing altogether and simply perform some numeric computation fully unrelated to the abstract type.

This latter kind of polymorphism scheme promises less about the implementation than the previous parametric scheme. Furthermore, the previous kind of polymorphism gives us theorems for free that allow us to replace code segments with possibly more efficient versions! For example, from the type p :: [a] -> [b] we know that p . map f = map f . p: We may relabel the elements of a list via a given function f :: a -> b by the call map f then run our computation p, or equivalently run p first and then relabel. In some circumstances it is preferable to do one over the other. All parametric polymorphic functions come with similar assurances! How cool is that!

Such free theorems reflect the idea that the definition of a polymorphic function is natural in that relabelling elements before or after the natural computation does not matter since the operation makes no inspection of the element-type in question and so can only duplicate, index, or rearrange elements —in the case of lists, that is.

Of-course this is only guaranteed since we only allow pure functions!

Independent Will

Abstract :: This is a passage I like, from First Things First by Covey and friends.

From page 59,

Between stimulus and response, there is a space.
In that space is our power to choose our response.
In our response lies our growth and our freedom.

Then page 60,

Independent will is our capacity to act. It gives us the power to transcend our paradigms, to swim upstream, to rewrite our scripts, to act based on principle rather than reacting based on emotion or circumstance. While environmental or genetic influences may be very powerful, they do not control us. We’re not victims. We’re not the product of our past. We are the product of our choices. We are “response-able” —able to respond, to choose beyond our moods and tendencies. We have will power to act on self-awareness, consciences, and vision.

RWH Abridged :: 1 Getting Started

Abstract :: We present a “Hello World” program for Haskell, followed by some technical facts about the Haskell language. Essentially​, we briefly summarise some parts of the first chapter of Real World Haskell.


a first program

Make a file named myprog.hs with contents

main = putStrLn "Hello World"

Now, runghc myprog.hs in a command line to execute this program.

runghc is a program for running Haskell programs as scripts, without needing to compile them first. In contrast, ghci is an interactive interpreter and debugger.

Try Haskell online in your browser at this link 😉

The rest of this page consists of tidbits on numbers, lists, operators and interactive​ debugging of Haskell programs.

the wonders of ghci

ghci is a Haskell interpreter and run from a console by running ghci myprog.lhs. Entering :? at the ghci prompt yields a collection of helpful commands to run. For example, :module + Data.Ratio loads the Data.Ratio module into the current session.

Other tidbits

  • :t identifier to obtain type information for identifier; use :i for all information.
  • At the ghci prompt, the variable it refers to the previously evaluated expression. This makes it easier to work with previous expressions.
  • :r to reload your file after you’ve made some changes

I personally use ghci as an overglorified calculator XD

operators in Haskell

Operator symbols appear infix as in most other languages, eg 3 + 4, but can also appear in prefix form by parenthesising them: (+) 3 4.

Haskell uses nearly the same names for the common arithmetical and logical operators with notable exceptions being ^ and ** for exponentiation, /= for non-equality, and not for Boolean negation. The ^ has an integer as the exponent but ** allows the exponent to be fractional.

At a ghci prompt, we can run :info (op) to see the precedence level of op, with 9 being the highest level and 1 the lowest. For example, infixl 6 means that the operator has level 6 precedence and is by default left-associative; the alternatives are infixr, infix for infix with default right-associative parsing, and for infix with no specified parsing order. The associativity determines whether an expression containing multiple uses of an operator is evaluated from left to right or right to left; eg how do you normally parse repeated fractions 6/2/3? Run :info (/) to find out what Haskell does! 😛

negation and parenthesisation

The usual notion of subtraction and negation is to use the same overloaded symbol - and Haskell accepts this and so the former is a binary operation whereas the latter is unary. In particular, if we wish to negate a number enclosed in some expression f, we must write f (-3) rather than f -3 since the latter is ambiguous and may be parsed as the subtraction of f with 3.

Note that function calls in Haskell do not require superfluous enclosing parenthesis as in other languages, unless there would be ambiguity otherwise. Function application has the highest binding: It is done first.

Moreover, Haskell allows us to define our own operators! More on this later. Hence, spacing about operators is important! 😮

In doubt, parenthesis your expressions.

lists, the bread and butter of Haskell programmers

A list is surrounded by square brackets and its elements are separted by commas as in [1,2,4,8,16,32,64] for the list of a few powers of 2. The empty list is denoted [].

enumerated lists

If the elements belong to an enumerable type, such as the numbers or characters, then we can write [x..y] to obtain the list starting at x and enumerating upto y. For numbers, we can specify the increment for each step by including the first two elements of the resulting list: [x,y..z] produces the list [x, x+d, x+2*d, ..., x+n*d] where d = y – x and x + n*dz. For example, [1.0, 0.75..0] == [1.0, 0.75, 0.50, 0.25, 0]. Moreover, [x..] produces the infinite list enumerated from x onwards —infinite lists are very useful and implemented very simply and efficiently! Press Ctrl C to stop a ghci computation, such as that of evaluating [1..]! Unless giving a step size, there are dangers with using enumerations with fractional endpoints.

Lists can be catenated together to form longer lists using ++ and we can construct a new list given an element x and a list xs by the operation : as in x:xs.

Strings —formed by enclosing text in double quotes— are synonyms for lists of characters —which are formed by enclosing a symbol by single quotes. Eg “Hello” == [‘H’, ‘e’, ‘l’, ‘l’, ‘o’]. As such usual list operations work on Strings.

be rational; we’re nearly done

A rational number is a number expressible as a fraction of two integer numbers; for example, a third is rational since it equals 1/3 whereas the square root of two is not rational and this drove a few fanatical mathematicians too keep it secret… o_O

Anyhow, Haskell treats rational numbers exactly in this form and one can construct them via the operator %: the fraction with integer numerator n and integer denominator d is named n % d. This way we can do very “precise” arithmetic since we do not express the rationals in floating-point form. Eg which is better 1 % 3 or 0.333, no matter how many trailing 3’s the latter will always be worse than the former; incidentally, three times the former is 1 but three times the latter is close to 1, but is not 1! :mrgreen:

Powered by WordPress.com.

Up ↑