Author: Heiner Marxen
Date: 08:00:05 08/01/03
Go up one level in this thread
On August 01, 2003 at 08:43:21, Anthony Cozzie wrote: >(some stuff snipped) > >>And don't derive cat and dog from animal ;-) >>It depends, you can teach procedural things first, algorithms and data >>structures. Control flow etc. Why not Pascal or Delphi? > >But most intro courses, sadly, focus on the Language first. At CMU, students >don't do any algorithms until 2nd semester (15-211). > >>>P.S. my favorite language is ML, but Zappa is in a mixture of C, C++, and >>>assembly. >> >>never heard about ML, can you give me a glue? > >ML was developed to write compliers in. Ocaml is the french version; Ocaml is >generally considered to be about 1.5x as slow as 'C' code (do a search on >"programming languages shootout"). My examples are written in SML (standard >ML). AFAIK, ML stands for "meta language", since the intended application was a proof system. >There are two really neat features of ML. First, the typesafing, and secondly >the fact that you can think onto the page. There are many interesting features of ML. It is a "functional" language. Functions are a first class datatype. You cannot only pass functions as arguments, you also can build them on the fly, and return them as you like. You have "higher order functions", transforming functions into functions. ML is garbage collected: you never have pointers, let alone bad ones. Still, it is really fast. >In 'C', you declare your functions with types: >int foot(int r, char *s, ...); > >In ML, you just write the function: >fun exp(a, b, c) = BLAH > |exp(0, b, c) = FOO > >etc. > >Now, the marvel of all this, is that the ML compiler is given this huge mess of >stuff, and it has to figure out what type everything is (because ML is a >strongly typed language). Now, if BLAH evaluates to an int, and FOO evaluates >to a char, you have some sort of a problem. This doesn't sound that helpful, >but ML allows you to build up crazy types. Here are two sample ML programs from >my stay in 15212. > >Problem 3: Regular Expressions > >This problem does regular expression matching: does string aaabba match a*b*a >etc. In 'C', this would be several hundred lines. This program is very >complicated because it uses continuations. The basic idea is that K (the >continuation) is a function that matches "the rest". > >P.S. I didn't get full points for this problem. Find the error if you can. >(sadly, my TA could) Hmm... I couldn't spot it. I thought about your Star-rule, but it looks ok. Then, I did not understand your Not-rule, mostly because I'm unsure what it should do exactly. >structure Regex :> REGEX = >struct > datatype regExp = > Char of char > | Concat of regExp * regExp > | Epsilon > | Union of regExp * regExp > | Empty > | Star of regExp > | Underscore (matches anything) > | And of regExp * regExp > | Top > | Not of regExp > > fun acc (Char(a)) (nil) k = false > |acc (Char(a)) (b::s) k = if a = b then k s else false > |acc (Epsilon) s k = k s > |acc (Empty) s k = false > |acc (Union(r1,r2)) s k = acc r1 s k orelse acc r2 s k > |acc (Concat(r1,r2)) s k = acc r1 s (fn s' => acc r2 s' k) > |acc (r as Star(r1)) s k = k s orelse acc r1 s (fn s' => if s = s' then fal >se else acc r s' k) > |acc (Underscore) (nil) k = false > |acc (Underscore) (b::s) k = k s > |acc (And(r1,r2)) s k = acc r1 s k andalso acc r2 s k > |acc (Top) s k = acc (Star(Underscore)) s k > |acc (Not(r)) s k = if (acc r s (fn s' => if (k s) then false else true) th >en false else true > > fun accept r s = acc r (String.explode s) (fn nil => true | x => false) >end Nice! [rest snipped] I have used SML for one of the most complicated programs I've ever written (about "busy beaver"). Before using SML, I failed (!) to do it in C++. Somehow the virtual destructors managed to be wrong, sometimes. Here garbage collection was a _huge_ plus. OTOH, I wouldn't use ML for a chess program. Maybe when I become more experienced with it... Cheers, Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.