Monads for functional programming

 

Philip Wadler, University of Glasgow

 

Department of Computing Science, University of Glasgow, G12 8QQ, Scotland

([e-mail])

 

Abstract. The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.

 

 

Introduction

 

Shall I be pure or impure?

The functional programming community divides into two camps. Pure languages, such as Miranda and Haskell, are lambda calculus pure and simple. Impure languages, such as Scheme and Standard ML, augment lambda calculus with a number of possible effects, such as assignment, exceptions, or continuations. Pure languages are easier to reason about and may benefit from lazy evaluation, while impure languages offer efficiency benefits and sometimes make possible a more compact mode of expression.

Recent advances in theoretical computing science, notably in the areas of type theory and category theory, have suggested new approaches that may integrate the benefits of the pure and impure schools. These notes describe one, the use of monads to integrate impure effects into pure functional languages.

The concept of a monad, which arises from category theory, has been applied by Moggi to structure the denotational semantics of programming languages. The same technique can be applied to structure functional programs.

The applications of monads will be illustrated with three case studies. Section 2 introduces monads by showing how they can be used to structure a simple evaluator so that it is easy to modify. Section 3 describes the laws satisfied by monads. Section 4 shows how monads provide a new solution to the old problem of providing updatable state in pure functional languages. Section 5 applies monads to the problem of building recursive descent parsers; this is of interest in its own right, and because it provides a paradigm for sequencing and alternation, two of the central concepts of computing.

It is doubtful that the structuring methods presented here would have been discovered without the insight afforded by category theory. But once discovered they are easily expressed without any reference to things categorical. No knowledge of category theory is required to read these notes.

The examples will be given in Haskell, but no knowledge of that is required either. What is required is a passing familiarity with the basics of pure and impure functional programming. The languages referred to are Haskell, Miranda, Standard ML, and Scheme.

 

Evaluating monads

 

Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit.

A program in a pure functional language is written as a set of equations. Explicit data flow ensures that the value of an expression depends only on its free variables. Hence substitution of equals for equals is always valid, making such programs especially easy to reason about. Explicit data flow also ensures that the order of computation is irrelevant, making such programs susceptible to lazy evaluation.

It is with regard to modularity that explicit data flow becomes both a blessing and a curse. On the one hand, it is the ultimate in modularity. All data in and all data out are rendered manifest and accessible, providing a maximum of flexibility. On the other hand, it is the nadir of modularity. The essence of an algorithm can become buried under the plumbing required to carry data from its point of creation to its point of use.

Say I write an evaluator in a pure functional language.

- To add an error handling to it, I need to modify each recursive call to check for and handle errors appropriately. Had I used an impure language with exceptions, no such restructuring would be needed.

- To add a count of operations performed to it, I need to modify each recursive call to pass around such counts appropriately. Had I used an impure language with a global variable that could be incremented, no such restructuring would be needed…

Задание 2: Подберите соответствия для следующих сокращений. Проанализируйте, по каким правилам может осуществляться перевод сокращений.

 

1) USSR 2) USA 3) EC 4) EU 5) EEC

6) CIS 7) UK 8) GB 9) FBI 10) CIA

11) CID 12) UN 13) TASS 14) BBC 15) KGB

16) NASA 17) NATO 18) NHS 19) PR 20) ELT

21) SEPA 22) CPSU 23) SAS 24) GI 25) RAF

26) RN 27) MOT 28) PM 29) MP 30) BW

31) PC 32) WPC 33) LAPD 34) NYPD 35) JP

36) VIP 37) ITV 38) POW 39) OAP 40) BST

41) EMS 42) a/c 43) VAT 44) GDP 45) BSc

46) BA 47) Ph.D. 48) GCSE 49) MA 50) MD

51) MSc 52) SOS 53) DNA 54) HIV 55) MS

56) VD 57) GP 58) AIDS 59) DC 60) AC

61) PVC 62) PS 63) PO 64) p. 65) i.e.

66) a.o.b. 67) a.s.a.p. 68) PTO 69) NB 70) s.a.e.

71) RSVP 72) ibid 73) F 74) C 75) ID

74) Bros 75) UFO 76) AWOL 77) CD 80) PC

81) VDU 82) CD-ROM 83) RAM 84) L-plate 85) RV

86) No 87) B.Y.O.B. 88) a.m. 89) p.m. 90) PE

91) B&B 92) blvd 93) Rd. 94) Av, Ave 95) RE

96) RIP 97) St 98) RC 99) PA 100) IQ

101) OPEC 102) ISO 103) BP 104) MBA 105) m

106) mph 107) mpg 108) k 109) g 110) mg

111) kg 112) l 113) oz 114) рt 115) lb

 

 

Задание 3: Дайте определение контекстуального сокращения. Подберите эквиваленты для следующих контекстуальных сокращений.

 

1. US DV (Diversity Immigrant Visa) program

2. UBD (underbalanced drilling)

3. ALARA (as low as reasonably achievable) principle

4. wRLS (weighted recursive least-squares) method

5. TS (Takagi-Sugeno) fuzzy models

6. VES (viscoelastic surfactant) fracturing liquid

МОДУЛЬ 6

Научно-популярный текст

Лексические замены

Задание 1: Выполните предпереводческий анализ следующего текста. Переведите текст и произведите анализ примененных трансформаций.

 

 

Oil’s origin

Crude oil – properly called petroleum – includes natural gas, a flammable fluid usually found with oil. Petroleum is the remains of organic material that was deposited, usually in marine environments, millions of years ago. One seep – a place where oil oozes naturally from the ground – which is located in Michigan’s Upper Peninsula, comes from billion-year-old rocks, although most commercial petroleum was generated from rocks that are between 656 million and 213 million years old.

Plants use photosynthesis to fix carbon dioxide from the atmosphere into organic forms of carbon – carbon bonded with hydrogen and other elements. This carbon becomes the basis for our biosphere – everything living. The details are not all worked out, but here is a Why Files oversimplification of how oil forms from organic carbon.

Die. First you live, and then you …? Right. You die. If you are a marine organism, you drop to the ocean floor. If you are not eaten, you may start to…

Rot. It is the fate of all – or most – flesh. Bacteria decompose you, and you become mere organic gunk on the ocean floor. But before bacteria completely devour you, the mass of sediment piling on top establishes a…

Quarantine. Bacteria need oxygen, sulfur or certain other chemicals to do their eating, and the rain of organic matter – or other forces like thermal or chemical stratification – eventually cuts off the supply of these elements, halting the bacteria in mid-rot. By now, chemical reactions have trimmed off most elements except for carbon and hydrogen – the major components of petroleum. Finally, a small percentage of you becomes a fluid, and you start to…

Go trucking. Oil being lighter than water, you float from the «source rock» into porous «reservoir rock». You may reach the surface and become one of the oil seeps ancient people used to caulk their boats and preserve their dead. But sometimes you…

Jam. Floating upward, you bang your head against an impermeable «cap rock». The cap restrains the oil, making you fair game for wildcatter – an oil driller working unproven fields.

To distill our discussion, oil starts forming when organic junk accumulates and gets covered quickly enough to shut off the supply of chemicals that bacteria need to oxidize the carbon. Otherwise, they will burn it and form carbon dioxide.

Microbes, explains Richard Kettler of the department of geological sciences at the University of Nebraska at Lincoln, are ubiquitous. «If there is something to eat, if there is a chemical reaction they can run at a reasonable temperature and pressure, you can almost guarantee there will be a life form that will be using that reaction». And living, he stresses, means devouring the organic matter that would otherwise become oil.

We should mention that while a few renegade scientists claim that petroleum has an inorganic origin, the conventional wisdom, as presented above, is pretty convincing:

We can watch organic sediments accumulating at the bottom of the ocean.

Many chemicals in crude oil have a structure characteristic of molecules with organic origins.

Hopanes, a group of hydrocarbon molecules found in petroleum, are made by bacteria, Kettler notes.

Petroleum may also contain molecules of waxes that land plants use to prevent drying, and many markers of its biological origin.

Finally, there is the linguistic argument: Tack an «e» onto that organic crud drifting down to the sea floor, and you got crude!

 

 

Задание 2: Какие лексические замены переводчики применили в следующих случаях?

 

1) Such knowledge is the fruit of selfless action. – Такое знание обретается в результате бескорыстной деятельности.

2) Do you take me for a fool? – Что я маленькая, что ли?

3) She turned her nose up in the air. – Она смерила его презрительным взглядом.

4) I thought of a better use for you. – Тебе найдется предназначение получше.

5) It is clearly overreacting. – Ты близко к сердцу все воспринимаешь.

6) I’ve got a strange feeling. – У меня дурное предчувствие.

7) My intuition is usually right. – Меня редко подводит интуиция.

8) I never thought of myself as your daughter. – Я никогда не думала о тебе как об отце.

9) Will we see the sunrise? – Доживем ли мы до рассвета?

10) I’m out. – У меня кончились патроны.

11) We are exhausting every option. – Мы делаем всё возможное.

12) Starving Marvin – Кошмарный Марвин

13) Fossil fuel. Use us and nobody gets hurt. – Природные ископаемые. Используйте нас, и никому не будет больно.

14) I didn’t do it. – Я нечаянно.

15) Poohsticks – игра в пустяки

16) Woozle – Бука, Wizzle – Бяка, Heffalump – Слонопотам, Tigger – Тигра, Jagular – Ягуляр

17) It’s time for a little something. – Пора перекусить.

18) The boat «The Brain of Pooh» – корабль «Мудрость Пуха»

19) To explain the remote history of the book – излагать древнюю историю книги

20) This is confidential knowledge. – Это сокровенное знание.

21) This is the only way to reach his abode. – Только этим путем вы сможете попасть в его обитель.

22) Old soldiers don’t die, they simply fade away. (Песня) – Старые солдаты не умирают, они просто уходят в тень.

23) «A Few Good Men» – «Пара неплохих ребят»

24) «A Knight’s Tale» – «Рыцарская сага»

25) «A League of Their Own» – «Женская лига»

26) «A.W.O.L.» – «Самоволка»

27) «People Under the Stairs» – «Люди из мрака»

28) «Rich Girl» – «Богатая девка»

29) «The Arm of God» – «Доспехи Бога»

30) «Singles» – «Холостые»

31) «The Interpreter» – «Переводчица»

32) «The Perfect Husband» – «Идеальный убийца»

33) «The Prince of Tides» – «Повелитель приливов»

34) «Thought Crimes» – «Человек-радар»

35) «No Way Up» – «Ядерный форсаж»

36) «Sum of All Fears» – «Цена страха»

37) «Last Man Standing» – «Последний оставшийся в живых»

38) «Malice» – «Готовая на всё»

39) «The Dark» – «Темные силы»

40) «Who Framed Roger Rabbit?» – «Кто подставил кролика Роджера?»

41) «Click» – «Пульт управления»

42) «Thumbsucker» – «Дурная привычка»

43) «RV» – «Дурдом на колесах»

44) «The Day I Got Married» – «Почему я женат»

45) «Over the Hedge» – «Лесная братва»

46) «The Wild» – «Большое путешествие»

47) «The Warriors» – «Кровавые братья»

48) «Hero» – «Победитель»

49) «Disaster!» – «Всем хана!»

50) «Be Kind Rewind» – «Перемотка»

51) «Over Her Dead Body» – «Невеста с того света»

52) «Jumper» – «Телепорт»

МОДУЛЬ 7