tuebingen seminar nov 04

Information about tuebingen seminar nov 04

Published on June 17, 2007

Author: BAWare

Source: authorstream.com

Content

Mutually dependent objects“Value recursion in a strict language when initialization effects cannot be statically controlled”:  Mutually dependent objects 'Value recursion in a strict language when initialization effects cannot be statically controlled' Don Syme MSR Cambridge University of Tuebingen Nov 2004 (edited version) Recursive functions v. Mutually referential values:  Recursive functions v. Mutually referential values let rec f x = if x andlt; 2 then 1 else f (x-1) + f (x-2)  let rec f(x) = if x andlt; 2 then 1 else g(x-1) + g(x-2) and g(x) = if x andlt; 2 then 3 else f(x-1)  However we’re talking about mutually referential VALUES. I’ll call these objects, especially if they have internal state. Mutually referential non-stateful objects are not common. Mutually referential stateful objects are very common GUIs Automaton and other reactive machines Example: GUI elements are highly self-referential reactive machines:  Example: GUI elements are highly self-referential reactive machines form = Form(menu) menu = Menu(menuItemA,menuItemB) menuItemA = MenuItem('A', {menuItemB.Activate} ) menuItemB = MenuItem('B', {menuItemA.Activate} )  A specification: menu menuItemB menuItemA form This smells like a small 'knot'. However another huge source of self-referentiality is that messages from worker threads must be pumped via a message loop accessed via a reference to the form. workerThread Approaches to Describing Mutually Referential Objects:  Approaches to Describing Mutually Referential Objects Scripting forward references to undefined names OO null pointers, 'create and configure' Strict Functional explicit encodings of nulls, filled in later via mutation, also APIs use and configure' extensively Lazy Functional use 'bottom' as an initialization-hole “Create and configure” in C#:  'Create and configure' in C# class C { Form form; Menu menu; MenuItem menuItemA; MenuItem menuItemB; C() { // Create form = new Form(); menu = new Menu(); menuItemA = new MenuItem('A'); menuItemB = new MenuItem('B'); // Configure form.AddMenu(menu); menu.AddMenuItem(menuItemA); menu.AddMenuItem(menuItemB); menuItemA.OnClick += delegate(Sender object,EventArgs x) { … }; menuItemB.OnClick += … ; // etc. } } Rough C# code, if well written: menu menuItemB menuItemA form Null pointer exceptions possible (Some help from compiler) Lack of locality Need to use classes In reality a mishmash – some configuration mixed with creation. Easy to get lost in OO fairyland (e.g. virtuals, inheritance, mixins) Nb. Anonymous delegates really required Programmers understand null pointers  Programmers always have a path to work around problems. “Create and configure” in F#:  'Create and configure' in F# // Create let form = new Form() in let menu = new Menu() in let menuItemA = new MenuItem('A') in let menuItemB = new MenuItem('B') in ... // Configure form.AddMenu(menu); menu.AddMenuItem(menuItemA); menu.AddMenuItem(menuItemB); menuItemA.add_OnClick(new EventHandler(fun x y -andgt; …)) menuItemB.add_OnClick(new EventHandler(fun x y -andgt; …)) menu menuItemB menuItemA form  Lack of locality for large specifications In reality a mishmash – some configuration mixed with creation. “Create and configure” in F#:  'Create and configure' in F# // Create let form = new Form() in let menu = new Menu() in let menuItemB = ref None in let menuItemA = new MenuItem('A', (fun () -andgt; (the !menuItemB).Activate()) in menuItemB := Some(new MenuItem('B', ...)); … menu menuItemB menuItemA form Often library design permits/forces configuration to be mixed with creation. If so it ends up a mishmash. Programmers understand ref, Some, None.  Programmers normally hand-minimize the number of 'ref options', so the structure of their code depends on solving a recursive puzzle. We manually build 'holes' to fill in later to cope with the value-recursion Recap:  Recap Self/Mutual-referential objects are a real problem They are one of the real reasons for null pointers and create-and-mutate APIs and OO Every language has problems with this, and initialization failures are always possible. Initialization via Implicit Nulls (SpecifyOne)* No initialization errors possible Initialization via Explicit Holes C# SML/OCaml F#? The Ideal Complete, usable, simple type systems for safe recursion ??? Correspondence of code to spec Reactive v. Immediate Dependencies :  Reactive v. Immediate Dependencies menu menuItemB menuItemA form These are REACTIVE (delayed) references, hence OK form = Form(menu) menu = Menu(menuItemA,menuItemB) menuItemA = MenuItem('A', {menuItemB.Activate} ) menuItemB = MenuItem('B', {menuItemA.Activate} ) The goal: support value recursion for reactive machines !! But we cannot statically check this without knowing a lot about the MenuItem constructor code !! F#’s new mechanism:  F#’s new mechanism let rec form = new Form(menu) and menu = new Menu(menuItemA, menuItemB) and menuItemB = new MenuItem('B', (fun () -andgt; menuItemA.Activate()) and menuItemA = new MenuItem('A', (fun () -andgt; menuItemB.Activate()) in ... menu menuItemB menuItemA form A set of recursive value bindings specifies the EAGER evaluation of nodes in a graph of LAZY computations Runtime initialization errors will occur if the creating the objects causes a self-reference during initialization The solution: Runtime check these 'reactive' uses The initialization graph is NON-ESCAPING. No runtime checks can fail after this point. F#’s new mechanism:  F#’s new mechanism Most direct (eager) recursion loops are detected Optional warnings where runtime checks are used let rec x = y and y = x mistake.ml(3,8): error: Value ‘x’ will be evaluated as part of its own definition. Value 'x' will evaluate 'y' will evaluate 'x' let rec x = new MenuItem('X', new EventHandler(fun sender e -andgt; x.Enabled andlt;- false)) ok.ml(13,63): warning: This recursive use will be checked for initialization-soundness at runtime. Self-referential objects without “self”:  Self-referential objects without 'self' let rec obj = {new Object() with GetHashCode() = obj.ToString().Length } obj But reactive recursion means reactive uses of 'Self' drop out for free! (with a runtime check) This is an object expression, used to implement/extend .NET classes. Note: there is no this or self keyword. My belief is that this/self is an broken, limited form of recursive reference. Observations about the F# mechanism:  Observations about the F# mechanism It is incredibly useful Immediately helped me 'scale up' samples GUIs correspond to their specification Unsophisticated programmers appear able to use it It has its dangers Evaluation order is well-defined, but forward-references force evaluations earlier than expected Problem: how do we evaluate language features like this? It can be optimized Neither references nor laziness escape in any 'real' sense, hence scope for optimization Tweaks to the F# mechanism:  Tweaks to the F# mechanism Concurrency: Need to prevent leaks to other threads during initialization (or else lock) Raises broader issues for a language What to do to make things a bit more explicit? My thought: annotate each binding with 'lazy' One suggestion: annotate each binding with 'eager' Interesting, but too verbose let rec eager form = new Form(menu) and eager menu = new Menu(menuItemA, menuItemB) and eager menuItemB = new MenuItem('B', (fun () -andgt; menuItemA.Activate()) and eager menuItemA = new MenuItem('A', (fun () -andgt; menuItemB.Activate()) Observations about the F# mechanism:  Observations about the F# mechanism It works well as an augmentation of ML’s existing 'let rec' Each binding can be an arbitrary computation. This allows configuration to be co-located with creation. let rec form = new Form() and do form.Add(menu) and menu = new Menu() and do menu.Add(menuItemA) and do menu.Add(menuItemB) and menuItemB = ... and menuItemA = ... Finally the goal is reached! Localized codifications that match a semi-formal specification, despite using a creat-and-configure API! An area in flux:  An area in flux SML 97: recursive functions only OCaml 3.0X: recursive concrete data Moscow ML 2.0: recursive modules Haskell: recursion via laziness Various papers: e.g. 'a theory of well-founded recursion' Effectively you have to prove the recursion well-founded e.g. orderings Summary:  Summary F# is a real, viable, polished language that lets you use strict functional programming in the rich context of .NET F# experimentally adds mutually dependent reactive objects, which offer an alternative approach to the recurring problem of constructing mutual dependencies in reactive programming Questions? http://research.microsoft.com/projects/fsharp:  Questions? http://research.microsoft.com/projects/fsharp

Related presentations


Other presentations created by BAWare

Integration into the SDLC
30. 08. 2007
0 views

Integration into the SDLC

hot topic
28. 09. 2007
0 views

hot topic

hispanics
01. 10. 2007
0 views

hispanics

zhang
10. 10. 2007
0 views

zhang

schwa
30. 08. 2007
0 views

schwa

aocc
30. 08. 2007
0 views

aocc

Pedersen
30. 08. 2007
0 views

Pedersen

Mining Sciences
30. 08. 2007
0 views

Mining Sciences

Intelligence Gathering mallorca
30. 08. 2007
0 views

Intelligence Gathering mallorca

ppt00021
30. 08. 2007
0 views

ppt00021

hoe wat over adsl
30. 11. 2007
0 views

hoe wat over adsl

The Healthy Potato
04. 12. 2007
0 views

The Healthy Potato

KINDS OF NOUNS
05. 11. 2007
0 views

KINDS OF NOUNS

CUPA 2007 Adv HW part 3
07. 11. 2007
0 views

CUPA 2007 Adv HW part 3

p Javier Carrillo
14. 11. 2007
0 views

p Javier Carrillo

High Intensity Interval Training
13. 12. 2007
0 views

High Intensity Interval Training

measurement
17. 12. 2007
0 views

measurement

OWASP AppSecEU2006 AJAX Security
30. 08. 2007
0 views

OWASP AppSecEU2006 AJAX Security

Feb05Sepracor
29. 11. 2007
0 views

Feb05Sepracor

aula17
28. 12. 2007
0 views

aula17

lab 04
11. 12. 2007
0 views

lab 04

cattle2000
31. 12. 2007
0 views

cattle2000

Mechanized Logging
02. 01. 2008
0 views

Mechanized Logging

Lightning Safety
03. 01. 2008
0 views

Lightning Safety

water problems
21. 11. 2007
0 views

water problems

mideastmaps
07. 01. 2008
0 views

mideastmaps

schulze
12. 10. 2007
0 views

schulze

Sept 17 03B
19. 11. 2007
0 views

Sept 17 03B

Empowerment2
29. 10. 2007
0 views

Empowerment2

LIU MIT 2006
28. 11. 2007
0 views

LIU MIT 2006

USFS Tourism
22. 11. 2007
0 views

USFS Tourism

omni partner guide pps
02. 10. 2007
0 views

omni partner guide pps

convergence
28. 12. 2007
0 views

convergence

sal mauro 061128
28. 02. 2008
0 views

sal mauro 061128

lec05
29. 02. 2008
0 views

lec05

nypss nsta nov 2003
26. 06. 2007
0 views

nypss nsta nov 2003

Movies MC 061129 3
26. 06. 2007
0 views

Movies MC 061129 3

MOUG 08 2002
26. 06. 2007
0 views

MOUG 08 2002

mold
26. 06. 2007
0 views

mold

moilanen movies
26. 06. 2007
0 views

moilanen movies

MMC Bonato
26. 06. 2007
0 views

MMC Bonato

mm class 8
26. 06. 2007
0 views

mm class 8

Oceans 2005
26. 06. 2007
0 views

Oceans 2005

C3A6
04. 01. 2008
0 views

C3A6

Session8Massimiliano Claps
21. 03. 2008
0 views

Session8Massimiliano Claps

paper Columbia pipelines
30. 08. 2007
0 views

paper Columbia pipelines

CDW Ches99 Talk
05. 01. 2008
0 views

CDW Ches99 Talk

Marketing Mix IPG Presentation
26. 03. 2008
0 views

Marketing Mix IPG Presentation

Moab Marketing
27. 03. 2008
0 views

Moab Marketing

0Kim
30. 08. 2007
0 views

0Kim

Coglx to cultlx
22. 11. 2007
0 views

Coglx to cultlx

12 Igra 4pm
06. 12. 2007
0 views

12 Igra 4pm

Rao
28. 03. 2008
0 views

Rao

Goorevich Richard
30. 03. 2008
0 views

Goorevich Richard

06MYMRes2
09. 04. 2008
0 views

06MYMRes2

quickreview
10. 04. 2008
0 views

quickreview

MontanaDDpresentatio n060105a
13. 04. 2008
0 views

MontanaDDpresentatio n060105a

The Happy Monkey
29. 11. 2007
0 views

The Happy Monkey

cnea 376
20. 11. 2007
0 views

cnea 376

e know GV Presentation
17. 04. 2008
0 views

e know GV Presentation

SustainabilityCaseSt udies
22. 04. 2008
0 views

SustainabilityCaseSt udies

mark
30. 08. 2007
0 views

mark

Dialectal Differentiation
24. 11. 2007
0 views

Dialectal Differentiation

Chapter01
30. 08. 2007
0 views

Chapter01

n0102 SPIE1
26. 06. 2007
0 views

n0102 SPIE1

tues RMI cloonan
07. 12. 2007
0 views

tues RMI cloonan

Modi
26. 06. 2007
0 views

Modi

mne tools scripts kskassam
26. 06. 2007
0 views

mne tools scripts kskassam

hausmesse vortrag meyer
16. 11. 2007
0 views

hausmesse vortrag meyer

sjw
21. 12. 2007
0 views

sjw

stew cartons
17. 06. 2007
0 views

stew cartons

stellmach tim
17. 06. 2007
0 views

stellmach tim

Twelfth Night 2
17. 06. 2007
0 views

Twelfth Night 2

TNG Presentation1
17. 06. 2007
0 views

TNG Presentation1

THE SCIENCE OF LOVE
17. 06. 2007
0 views

THE SCIENCE OF LOVE

t06B Functions Examples
17. 06. 2007
0 views

t06B Functions Examples

Sunny
17. 06. 2007
0 views

Sunny

28 1330 HARP rohacs hideg
18. 03. 2008
0 views

28 1330 HARP rohacs hideg

Water way Awareness
17. 06. 2007
0 views

Water way Awareness

Watergate Political Cartoons
17. 06. 2007
0 views

Watergate Political Cartoons

Valentine s PPT
17. 06. 2007
0 views

Valentine s PPT

USB FunctionDrv
17. 06. 2007
0 views

USB FunctionDrv

urban legends
17. 06. 2007
0 views

urban legends

unti 17Le 1 Funny stories
17. 06. 2007
0 views

unti 17Le 1 Funny stories

Understanding Political Cartoons
17. 06. 2007
0 views

Understanding Political Cartoons

Week2 Augustineandhisera
17. 06. 2007
0 views

Week2 Augustineandhisera

Tee
09. 10. 2007
0 views

Tee

seshun
13. 11. 2007
0 views

seshun

Locke 1 07
30. 08. 2007
0 views

Locke 1 07

ames tornado
05. 10. 2007
0 views

ames tornado

TEAM 9
08. 11. 2007
0 views

TEAM 9

Ferragina
23. 11. 2007
0 views

Ferragina

robo wk 4 controls
07. 01. 2008
0 views

robo wk 4 controls

ScottStroup
02. 11. 2007
0 views

ScottStroup

dyer w ref
04. 03. 2008
0 views

dyer w ref

act31sld
30. 08. 2007
0 views

act31sld

WA Final
17. 06. 2007
0 views

WA Final

EnB presentatie Fischbacher
30. 08. 2007
0 views

EnB presentatie Fischbacher

What to do in Harrisonburg
17. 06. 2007
0 views

What to do in Harrisonburg