Transcript Miranda A Functional Language

Miranda
A Functional Language
Dan Vasicek
March 16, 2008
References
• “Introduction to Functional Programming”
– Richard Bird, and Philip Wadler
– Prentice – Hall, 1988, 291 pages
• Structure and Interpretation of Computer
Programs
• Abelson and Sussman
• MIT Press 1985
Historical
• 1986 Study Scheme using Ableson and
Sussman, Structure and Interpretation of
Computer Programs
• 1988 Miranda using Bird and Wadler
• 1988 Study reservoir modeling problem
– 100 Man*year Amoco Effort
•
•
•
•
1990 Begin the Miranda Reservoir Model
Use Claris Works to organize the project
1992 AMOCO cancels the project
1992 Disk Crash destroys most records of the
project
Miranda
• Miranda concepts
– “Pure” functional language
– Lazy evaluation (allows infinite lists)
– Single assignment (Parallel Computation)
• Reservoir Models
– Darcy’s Law (Flow in porous media)
– Constitutive relationships (pv=nrT)
• Miranda Reservoir Experiment
Synthesis of Programs from
Specifications
• Equational reasoning used to derive a
program from a specification
• Building definitions
• Program Transformation
• Constructing a function to solve a given
problem
• Without specification the sequence of
steps in the process
Miranda = a pure functional
language
• All computations are done by applying functions
to data (purely functional)
• The top level program is a function call that
produces the desired result
• Characteristics of functional languages
– Order of execution is irrelevant
– Each function call encapsulates the relationship
between some inputs and outputs
– Higher level of abstraction is available
– Less development time
– Less code
Miranda does not
• Provide iterative constructs such as the
“for” or “do” loop
• Provide any way to change the value of a
“variable” (single assignment)
• Once a “variable” has a value, it cannot
change
Procedural vs. Functional
• Procedural Cake Recipe
– Specifies the process
– Specifies the sequence of steps for making a
cake
• Functional Cake Recipe
– Specifies the steps but not the sequence
– Abstract the steps from the sequence
Recipe – Bake a Cake
• Procedural Recipe (“Fortran” Program)
–
–
–
–
–
–
–
–
–
Buy cake mix, eggs, milk
Preheat oven to 350
Beat eggs until frothy
Add milk
Fold in mix
Grease pan
Put batter in pan
Put pan in oven
Bake 350 degrees for 30 minutes
Recipe – Bake a Cake
• Functional recipe
– Cake=Bake_a_cake(Cake_in_oven)
– Cake_in_oven=batter_in_oven(hot_oven,
b_in_pan)
– hot_oven=heat_oven( turn_on_oven())
– b_in_pan=mix_ingredients(eggs, milk, c_mix)
Recursion
• Mathematical theorems are frequently
proven using a recursive argument such
as “Proof by Induction”
• Recursion provides an alternative to
iteration in programs
• Factorial Example:
– F(0)=1
– F(n)=n*F(n-1)
List Processing
•
•
•
•
•
•
Miranda is a descendent of LISP
[1,2,3] :: [num]
[‘h’,’e’,’l’,’l’,’o’] :: [char]
[(+), (*)] ::[num  num  num]
[1,2,..4]=[1,2,3,4]
[1..] = infinite list of all positive digits
LaTeX In-Line Documentation
• Miranda allows one text file containing
both the program and the documentation
• Process the file with LaTeX  Document
• Process the file with Miranda compiler 
executable program
Reservoir Model Ideas
•
•
•
•
•
Darcy’s Law
Compositional Relationships
Finite Differences
Linear Algebra
Reference: Page, Sexton, and Wainwright
(1990 IEEE)
• http://ieeexplore.ieee.org/xpl/freeabs_all.js
p?arnumber=82145
Darcy’s Law for Flow in Porous
Media
• P=pressure, =permeability Tensor
• q= fluid flux, =fluid viscosity
Equations of State
•
•
•
•
•
•
Van der Waals
( P + a / Vm2 )( Vm - b ) = R T
P = pressure
Vm = molar volume
R = ideal gas constant
T = temperature
Discretization of the Reservoir
•
•
•
•
Continuous reservoir  Discrete 3 d grid
PDE  Linear Algebra
Derivatives  Finite differences
Large linear systems  sparse, iterative,
system solvers
• Conjugate gradient method
Oil Reservoir Characterization
• Seismic Data – location of layers
• Exploration wells – measure properties in
the layers (pressure, gas, oil, and water
concentration, rock properties…)
• Extrapolate between the wells using the
seismically derived layers
Oil Reservoir
Fluid Velocity in a Reservoir
Basic Ideas of the Model
• 100 man years of programming effort to
construct the Fortran version of the reservoir
model
• Many input data files existed for the Fortran
version of the model
• Difficult to achieve effective parallelism in the
code
• Huge effort in maintenance and development
• Documentation difficult
Miranda Reservoir Model
• 2 man years of effort
– Rex Page
– Roger Wainwright
– Julio Diaz
– Dan Vasicek
• LaTeX in-line documentation
• Accepts existing structures intended for
input to the Fortran reservoir model
Functional Languages
• “Pure” & Single Assignment constraints
– Make explicit the dependence of the functions
on the data
– Allow a simple operating system to take
advantage of the opportunities for parallel
computation
• High level language
– Decreases the programming effort