Atom
A simple taxonomy of programming languages
Someone asked me recently how I categorize different programming paradigms. I thought it was a very interesting question, so here's what I responded. Please bear in mind that this is very much the way I see things, and is neither an exhaustive nor a formally-ratified taxonomy.
One way to look at languages is whether they're declarative or imperative:
Declarative programming languages map the way things are by building up “truths”: this category includes functional programming languages (such as Miranda, Haskell and Erlang) which tend to be mathematical in nature (you define equations) and start with lambda calculus as a foundation. The other main set of declarative languages are logic programming languages (such as Prolog), which start with propositional calculus as a foundation (you declare axioms that build up to a system against which you can run queries). Declarative languages tend to focus on describing the problem to solve, rather than how to solve it.
Imperative programming languages, on the other hand, are lists of instructions of what to do: I tend to consider procedural programming languages (such as C, COBOL, Fortran and Pascal) as a sub-category which focus on the definition and execution of sub-routines, while some people treat the terms imperative and procedural as synonyms.
Considering these definitions, object-oriented programming languages (such as Smalltalk and Eiffel) should probably be considered declarative, as conceptually they map real-world objects, but the truth is that the most popular OO languages (such as C++) are impure, and so most OO systems combine big chunks of procedural (i.e. imperative) code. Many people who think they’re doing OOP are actually packaging up procedures.
Note that I've tried not to list multi-paradigm languages such as Ada, C++ and F# in the above categorisation. It's possible that some of the languages I've listed are also multi-paradigm, but anyway.
One other way to think about languages is whether they’re top-down or bottom-up:
Bottom-up languages are ultimately layered on how a processor works (from machine code to assembly language to C & C++), while top-down languages start from the world of mathematics and logic and add language features that allow them to be used for programming (i.e. declarative languages are therefore top-down). This latter set of languages are starting to see increased adoption, as they assume much less (even nothing) about the underlying machinery, in which big changes are occurring with multiple processing cores being introduced (which essentially invalidate the assumptions of previous generations of programmers, who have been conditioned to think in terms of the processor's ability to store and access state).
Many popular - or soon to be popular - programming environments are pragmatic in nature: C++ allows OOP but can also be used for procedural programming, VB.NET now allows you to define and access objects while coming from a long line of procedural languages, F# is multi-paradigm, combining OO with functional and imperative programming.
There are bound to be people with differing views on this subject (and many of them are no doubt more intelligent and experienced in these matters than I), but this is how I would answer the question of how to categorise programming languages.
For those of you with an interest in the future of programming languages, I can strongly recommend the following Channel 9 episodes. If you're not aware of Channel 9, then prepare to be impressed: Microsoft has given a fantastic gift to the development community with this resource.
Burton Smith: On General Purpose Super Computing and the History and Future of Parallelism
Erik Meijer: Functional Programming
Anders Hejlsberg, Herb Sutter, Erik Meijer, Brian Beckman: Software Composability and the Future of Languages
Brian Beckman: Don't fear the Monads
Joe Armstrong - On Erlang, OO, Concurrency, Shared State and the Future, Part 1
Joe Armstrong - On Erlang, OO, Concurrency, Shared State and the Future, Part 2
Enjoy! :-)
March 17, 2008 in Concurrent programming, F# | Permalink | Comments (2) | TrackBack
Parallelizing robotic AutoCAD hatching with F# and .NET
In the last post we saw some code combining F# with C# to create a random "hatch" - a polyline path that bounces around within a boundary.
This post extends the code to make use of Asynchronous Workflows in F# to parallelize the testing of points along a segment. In the initial design of the application I decided to test 10 points along each segment, to see whether it remained entirely within our boundary: the idea being that this granularity makes it very likely the segment will fail the test, should it happen to leave the boundary at any point. Not 100% guaranteed, but a high probability event. What this code does is take the 10 tests and queue them up for concurrent processing (where the system is capable of it).
Asynchronous Workflows - as suggested by the name - were intended to fire off and manage asynchronous tasks (ones that access network resources, for instance). The segment testing activity is actually very local and processor-bound, so it's not really what the mechanism was intended for, but I thought it would be interesting to try. One interesting point: while testing this code I noticed that it actually ran slower on a single processor machine, which is actually quite logical: only one core is available for processing, so the amount of sequential processing is not reduced but the overhead of synchronizing the various tasks is added. So it was fairly inevitable it would take longer. In the post I first talked about Asynchronous Workflows I showed a sample that queried multiple RSS sites for data: even on a single processor machine this was significantly quicker, as parallelizing the network latency led to a clear gain.
Anyway, as it was slower on this machine I decided only to enable the parallel version of the code in cases where the computer's NUMBER_OF_PROCESSORS environment variable is greater than 1. I checked quickly on a colleague's dual-core machine, and sure enough this variable is set to 2 on his system. I haven't, however, tested the code on a dual- or multi-core system, but I'll be getting a new system in a matter of weeks, which will give me the chance to test it out.
Here's the F# code, with the line numbers highlighting the changes in red:
1 // Use lightweight F# syntax
2
3 #light
4
5 // Declare a specific namespace and module name
6
7 module BounceHatchAsync.Commands
8
9 // Import managed assemblies
10
11 #I @"C:\Program Files\Autodesk\AutoCAD 2008"
12 #I @".\PointInCurve\bin\Debug"
13
14 #r "acdbmgd.dll"
15 #r "acmgd.dll"
16
17 #R "PointInCurve.dll" // R = CopyFile is true
18
19 open System
20 open Autodesk.AutoCAD.Runtime
21 open Autodesk.AutoCAD.ApplicationServices
22 open Autodesk.AutoCAD.DatabaseServices
23 open Autodesk.AutoCAD.EditorInput
24 open Autodesk.AutoCAD.Geometry
25 open PointInCurve
26
27 // Get a random vector on a plane
28
29 let randomUnitVector pl =
30
31 // Create our random number generator
32 let ran = new System.Random()
33
34 // First we get the absolute value
35 // of our x and y coordinates
36
37 let absx = ran.NextDouble()
38 let absy = ran.NextDouble()
39
40 // Then we negate them, half of the time
41
42 let x = if (ran.NextDouble() < 0.5) then -absx else absx
43 let y = if (ran.NextDouble() < 0.5) then -absy else absy
44
45 // Create a 2D vector and return it as
46 // 3D on our plane
47
48 let v2 = new Vector2d(x, y)
49 new Vector3d(pl, v2)
50
51 type traceType =
52 | Accepted
53 | Rejected
54 | Superseded
55
56 // Draw one of three types of trace vector
57
58 let traceSegment (start:Point3d) (endpt:Point3d) trace =
59
60 let ed =
61 Application.DocumentManager.MdiActiveDocument.Editor
62
63 let vecCol =
64 match trace with
65 | Accepted -> 3
66 | Rejected -> 1
67 | Superseded -> 2
68 let trans =
69 ed.CurrentUserCoordinateSystem.Inverse()
70 ed.DrawVector
71 (start.TransformBy(trans),
72 endpt.TransformBy(trans),
73 vecCol,
74 false)
75
76 // Test a segment to make sure it is within our boundary
77
78 let testSegment cur (start:Point3d) (vec:Vector3d) =
79
80 // (This is inefficient, but it's not a problem for
81 // this application. Some of the redundant overhead
82 // of firing rays for each iteration could be factored
83 // out, among other enhancements, I expect.)
84
85 let pts =
86 [for i in 1..10 -> start + (vec * 0.1 * Int32.to_float i)]
87
88 // Call into our IsInsideCurve library function,
89 // "and"-ing the results
90
91 let inside pt =
92 PointInCurve.Fns.IsInsideCurve(cur, pt)
93
94 List.for_all inside pts
95
96 // Test a segment to make sure it is within our boundary
97
98 let testSegmentAsync cur (start:Point3d) (vec:Vector3d) =
99
100 let pts =
101 [for i in 1..10 -> start + (vec * 0.1 * Int32.to_float i)]
102
103 // Call into our IsInsideCurve library function,
104 // "and"-ing the results
105
106 let inside pt =
107 async { return PointInCurve.Fns.IsInsideCurve(cur, pt) }
108
109 let tests =
110 Async.Run
111 (Async.Parallel
112 [for pt in pts -> inside pt])
113
114 Array.for_all (fun x -> x) tests
115
116 // For a particular boundary, get the next vertex on the
117 // curve, found by firing a ray in a random direction
118
119 let nextBoundaryPoint (cur:Curve)
120 (start:Point3d) trace runAsync =
121
122 // Get the intersection points until we
123 // have at least 2 returned
124 // (will usually happen straightaway)
125
126 let rec getIntersect (cur:Curve)
127 (start:Point3d) vec =
128
129 let plane = cur.GetPlane()
130
131 // Create and define our ray
132
133 let ray = new Ray()
134 ray.BasePoint <- start
135 ray.UnitDir <- vec
136
137 let pts = new Point3dCollection()
138 cur.IntersectWith
139 (ray,
140 Intersect.OnBothOperands,
141 pts,
142 0, 0)
143
144 ray.Dispose()
145
146 if (pts.Count < 2) then
147 let vec2 = randomUnitVector plane
148 getIntersect cur start vec2
149 else
150 pts
151
152 // For each of the intersection points - which
153 // are points elsewhere on the boundary - let's
154 // check to make sure we don't have to leave the
155 // area to reach them
156
157 let plane =
158 cur.GetPlane()
159 let pts =
160 randomUnitVector plane |> getIntersect cur start
161
162 // Get the distance between two points
163
164 let getDist fst snd =
165 let (vec:Vector3d) = fst - snd
166 vec.Length
167
168 // Compare two (dist, pt) tuples to allow sorting
169 // based on the distance parameter
170
171 let compDist fst snd =
172 let (dist1, pt1) = fst
173 let (dist2, pt2) = snd
174 if dist1 = dist2 then
175 0
176 else if dist1 < dist2 then
177 -1
178 else // dist1 > dist2
179 1
180
181 // From the list of points we create a list
182 // of (dist, pt) pairs, which we then sort
183
184 let sorted =
185 [ for pt in pts -> (getDist start pt, pt) ] |>
186 List.sort compDist
187
188 // A test function to check whether a segment
189 // is within our boundary. It draws the appropriate
190 // trace vectors, depending on success
191
192 let testItem dist =
193 let (distval, pt) = dist
194 let vec = pt - start
195 if (distval > Tolerance.Global.EqualVector) then
196 let res =
197 if runAsync then
198 testSegmentAsync cur start vec
199 else
200 testSegment cur start vec
201 if res then
202 if trace then
203 traceSegment start pt traceType.Accepted
204 Some(dist)
205 else
206 if trace then
207 traceSegment start pt traceType.Rejected
208 None
209 else
210 None
211
212 // Get the first item - which means the shortest
213 // non-zero segment, as the list is sorted on distance
214 // - that satisifies our condition of being inside
215 // the boundary
216
217 let ret = List.first testItem sorted
218 match ret with
219 | Some(d,p) -> p
220 | None -> failwith "Could not get point"
221
222 // We're using a different command name, so we can compare
223
224 [<CommandMethod("fba")>]
225 let bounceHatch() =
226 let doc =
227 Application.DocumentManager.MdiActiveDocument
228 let db = doc.Database
229 let ed = doc.Editor
230
231 // Get various bits of user input
232
233 let getInput =
234 let peo =
235 new PromptEntityOptions
236 ("\nSelect point on closed loop: ")
237 let per = ed.GetEntity(peo)
238 if per.Status <> PromptStatus.OK then
239 None
240 else
241 let pio =
242 new PromptIntegerOptions
243 ("\nEnter number of segments: ")
244 pio.DefaultValue <- 500
245 let pir = ed.GetInteger(pio)
246 if pir.Status <> PromptStatus.OK then
247 None
248 else
249 let pko =
250 new PromptKeywordOptions
251 ("\nDisplay segment trace: ")
252 pko.Keywords.Add("Yes")
253 pko.Keywords.Add("No")
254 pko.Keywords.Default <- "Yes"
255 let pkr = ed.GetKeywords(pko)
256 if pkr.Status <> PromptStatus.OK then
257 None
258 else
259 Some
260 (per.ObjectId,
261 per.PickedPoint,
262 pir.Value,
263 pkr.StringResult.Contains("Yes"))
264
265 match getInput with
266 | None -> ignore()
267 | Some(oid, picked, numBounces, doTrace) ->
268
269 // Capture the start time for performance
270 // measurement
271
272 let starttime = System.DateTime.Now
273
274 // We'll run asynchronously only when we have
275 // multiple processing cores
276
277 let runAsync =
278 (Int32.of_string
279 (Environment.GetEnvironmentVariable
280 ("NUMBER_OF_PROCESSORS")))
281 > 1
282
283 use tr =
284 db.TransactionManager.StartTransaction()
285
286 // Check the selected object - make sure it's
287 // a closed loop (could do some more checks here)
288
289 let obj =
290 tr.GetObject(oid, OpenMode.ForRead)
291
292 match obj with
293 | :? Curve ->
294 let cur = obj :?> Curve
295 if cur.Closed then
296 let latest =
297 picked.
298 TransformBy(ed.CurrentUserCoordinateSystem).
299 OrthoProject(cur.GetPlane())
300
301 // Create our polyline path, adding the
302 // initial vertex
303
304 let path = new Polyline()
305 path.Normal <- cur.GetPlane().Normal
306
307 path.AddVertexAt
308 (0,
309 latest.Convert2d(cur.GetPlane()),
310 0.0, 0.0, 0.0)
311
312 // A recursive function to get the points
313 // for our path
314
315 let rec definePath start times =
316 if times <= 0 then
317 []
318 else
319 try
320 let pt =
321 nextBoundaryPoint cur start doTrace runAsync
322 (pt :: definePath pt (times-1))
323 with exn ->
324 if exn.Message = "Could not get point" then
325 definePath start times
326 else
327 failwith exn.Message
328
329 // Another recursive function to add the vertices
330 // to the path
331
332 let rec addVertices (path:Polyline)
333 index (pts:Point3d list) =
334
335 match pts with
336 | [] -> []
337 | a::[] ->
338 path.AddVertexAt
339 (index,
340 a.Convert2d(cur.GetPlane()),
341 0.0, 0.0, 0.0)
342 []
343 | a::b ->
344 path.AddVertexAt
345 (index,
346 a.Convert2d(cur.GetPlane()),
347 0.0, 0.0, 0.0)
348 addVertices path (index+1) b
349
350 // Plug our two functions together, ignoring
351 // the results
352
353 definePath picked numBounces |>
354 addVertices path 1 |>
355 ignore
356
357 // Now we'll add our polyline to the drawing
358
359 let bt =
360 tr.GetObject
361 (db.BlockTableId,
362 OpenMode.ForRead) :?> BlockTable
363 let btr =
364 tr.GetObject
365 (bt.[BlockTableRecord.ModelSpace],
366 OpenMode.ForWrite) :?> BlockTableRecord
367
368 // We need to transform the path polyline so
369 // that it's over our boundary
370
371 path.TransformBy
372 (Matrix3d.Displacement
373 (cur.StartPoint - Point3d.Origin))
374
375 // Add our path to the modelspace
376
377 btr.AppendEntity(path) |> ignore
378 tr.AddNewlyCreatedDBObject(path, true)
379
380 // Commit, whether we added a path or not.
381
382 tr.Commit()
383
384 // Print how much time has elapsed
385
386 let elapsed =
387 System.DateTime.op_Subtraction
388 (System.DateTime.Now, starttime)
389
390 ed.WriteMessage
391 ("\nElapsed time: " + elapsed.ToString())
392
393 // If we're tracing, pause for user input
394 // before regenerating the graphics
395
396 if doTrace then
397 let pko =
398 new PromptKeywordOptions
399 ("\nPress return to clear trace vectors: ")
400 pko.AllowNone <- true
401 pko.AllowArbitraryInput <- true
402 let pkr = ed.GetKeywords(pko)
403 ed.Regen()
404
405 | _ ->
406 ed.WriteMessage("\nObject is not a curve.")
Here's the the complete project which defines both FB and FBA commands for simple side-by-side comparison.
February 21, 2008 in AutoCAD, AutoCAD .NET, Concurrent programming, F# | Permalink | Comments (2) | TrackBack
Using F# Asynchronous Workflows to simplify concurrent programming in AutoCAD
In the last post we saw some code that downloaded data - serially - from a number of websites via RSS and created AutoCAD entities linking to the various posts.
As promised, in today's post we take that code and enable it to query the same data in parallel by using Asynchronous Workflows in F#. Asynchronous Workflows are an easy-to-use yet powerful mechanism for enabling concurrent programming in F#.
Firstly, a little background as to why this type of technique is important. As many - if not all - of you are aware, the days of raw processor speed doubling every couple of years are over. The technical innovations that enabled Moore's Law to hold true for half a century are - at least in the area of silicon-based microprocessor design - hitting a wall (it's apparently called the Laws of Physics :-). Barring some disruptive technological development, the future gains in computing performance are to be found in the use of parallel processing, whether via multiple cores, processors or distributed clouds of computing resources.
Additionally, with an increasing focus on distributed computing and information resources, managing tasks asynchronously becomes more important, as information requests across a network inevitably introduce a latency that can be mitigated by the tasks being run in parallel.
The big problem is that concurrent programming is - for the most-part - extremely difficult to do, and even harder to retro-fit into existing applications. Traditional lock-based parallelism (where locks are used to control access to shared computing resources) is both unwieldy and prone to blocking. New technologies, such as Asynchronous Workflows and Software Transactional Memory, provide considerable hope (and this is a topic I have on my list to cover at some future point).
Today's post looks at a relatively simple scenario, in the sense that we want to perform a set of discrete tasks in parallel, harnessing those fancy multi-core systems for those of you lucky enough to have them (I'm hoping to get one when I next replace my notebook, sometime in March), but that these tasks are indeed independent: we want to wait until they are all complete, but we do not have the additional burden of them communicating amongst themselves or using shared resources (e.g. accessing shared memory) during their execution.
We are also going to be very careful only to run parallel tasks unrelated to AutoCAD. Any access made into AutoCAD's database, for instance, needs to be performed in series: AutoCAD is not thread-safe when it comes to the vast majority of its programmatically-accessible functionality. So we're going to run a set of asynchronous, parallel tasks to query our various RSS feeds, and combine the results before creating the corresponding geometry in AutoCAD. This all sounds very complex, but the good (actually great) news is that Asynchronous Workflows does all the heavy lifting. Phew.
Here's the modified F# code, with the modified/new lines coloured in red:
1 // Use lightweight F# syntax
2
3 #light
4
5 // Declare a specific namespace and module name
6
7 module MyNamespace.MyApplication
8
9 // Import managed assemblies
10
11 #I @"C:\Program Files\Autodesk\AutoCAD 2008"
12
13 #r "acdbmgd.dll"
14 #r "acmgd.dll"
15
16 open Autodesk.AutoCAD.Runtime
17 open Autodesk.AutoCAD.ApplicationServices
18 open Autodesk.AutoCAD.DatabaseServices
19 open Autodesk.AutoCAD.Geometry
20 open System.Xml
21 open System.Collections
22 open System.Collections.Generic
23 open System.IO
24 open System.Net
25 open Microsoft.FSharp.Control.CommonExtensions
26
27 // The RSS feeds we wish to get. The first two values are
28 // only used if our code is not able to parse the feed's XML
29
30 let feeds =
31 [ ("Through the Interface",
32 "http://blogs.autodesk.com/through-the-interface",
33 "http://through-the-interface.typepad.com/through_the_interface/rss.xml");
34
35 ("Don Syme's F# blog",
36 "http://blogs.msdn.com/dsyme/",
37 "http://blogs.msdn.com/dsyme/rss.xml");
38
39 ("Shaan Hurley's Between the Lines",
40 "http://autodesk.blogs.com/between_the_lines",
41 "http://autodesk.blogs.com/between_the_lines/rss.xml");
42
43 ("Scott Sheppard's It's Alive in the Lab",
44 "http://blogs.autodesk.com/labs",
45 "http://labs.blogs.com/its_alive_in_the_lab/rss.xml");
46
47 ("Lynn Allen's Blog",
48 "http://blogs.autodesk.com/lynn",
49 "http://lynn.blogs.com/lynn_allens_blog/index.rdf");
50
51 ("Heidi Hewett's AutoCAD Insider",
52 "http://blogs.autodesk.com/autocadinsider",
53 "http://heidihewett.blogs.com/my_weblog/index.rdf") ]
54
55 // Fetch the contents of a web page, asynchronously
56
57 let httpAsync(url:string) =
58 async { let req = WebRequest.Create(url)
59 use! resp = req.GetResponseAsync()
60 use stream = resp.GetResponseStream()
61 use reader = new StreamReader(stream)
62 return reader.ReadToEnd() }
63
64 // Load an RSS feed's contents into an XML document object
65 // and use it to extract the titles and their links
66 // Hopefully these always match (this could be coded more
67 // defensively)
68
69 let titlesAndLinks (name, url, xml) =
70 let xdoc = new XmlDocument()
71 xdoc.LoadXml(xml)
72
73 let titles =
74 [ for n in xdoc.SelectNodes("//*[name()='title']")
75 -> n.InnerText ]
76 let links =
77 [ for n in xdoc.SelectNodes("//*[name()='link']") ->
78 let inn = n.InnerText
79 if inn.Length > 0 then
80 inn
81 else
82 let href = n.Attributes.GetNamedItem("href").Value
83 let rel = n.Attributes.GetNamedItem("rel").Value
84 if href.Contains("feedburner") then
85 ""
86 else
87 href ]
88
89 let descs =
90 [ for n in xdoc.SelectNodes
91 ("//*[name()='description' or name()='content' or name()='subtitle']")
92 -> n.InnerText ]
93
94 // A local function to filter out duplicate entries in
95 // a list, maintaining their current order.
96 // Another way would be to use:
97 // Set.of_list lst |> Set.to_list
98 // but that results in a sorted (probably reordered) list.
99
100 let rec nub lst =
101 match lst with
102 | a::[] -> [a]
103 | a::b ->
104 if a = List.hd b then
105 nub b
106 else
107 a::nub b
108 | [] -> []
109
110 // Filter the links to get (hopefully) the same number
111 // and order as the titles and descriptions
112
113 let real = List.filter (fun (x:string) -> x.Length > 0)
114 let lnks = real links |> nub
115
116 // Return a link to the overall blog, if we don't have
117 // the same numbers of titles, links and descriptions
118
119 let lnum = List.length lnks
120 let tnum = List.length titles
121 let dnum = List.length descs
122
123 if tnum = 0 || lnum = 0 || lnum <> tnum || dnum <> tnum then
124 [(name,url,url)]
125 else
126 List.zip3 titles lnks descs
127
128 // For a particular (name,url) pair,
129 // create an AutoCAD HyperLink object
130
131 let hyperlink (name,url,desc) =
132 let hl = new HyperLink()
133 hl.Name <- url
134 hl.Description <- desc
135 (name, hl)
136
137 // Use asynchronous workflows in F# to download
138 // an RSS feed and return AutoCAD HyperLinks
139 // corresponding to its posts
140
141 let hyperlinksAsync (name, url, feed) =
142 async { let! xml = httpAsync feed
143 let tl = titlesAndLinks (name, url, xml)
144 return List.map hyperlink tl }
145
146 // Now we declare our command
147
148 [<CommandMethod("rss")>]
149 let createHyperlinksFromRss() =
150
151 // Let's get the usual helpful AutoCAD objects
152
153 let doc =
154 Application.DocumentManager.MdiActiveDocument
155 let db = doc.Database
156
157 // "use" has the same effect as "using" in C#
158
159 use tr =
160 db.TransactionManager.StartTransaction()
161
162 // Get appropriately-typed BlockTable and BTRs
163
164 let bt =
165 tr.GetObject
166 (db.BlockTableId,OpenMode.ForRead)
167 :?> BlockTable
168 let ms =
169 tr.GetObject
170 (bt.[BlockTableRecord.ModelSpace],
171 OpenMode.ForWrite)
172 :?> BlockTableRecord
173
174 // Add text objects linking to the provided list of
175 // Hyp