Author: Anthony Cozzie
Date: 05:43:21 08/01/03
Go up one level in this thread
(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).
There are two really neat features of ML. First, the typesafing, and secondly
the fact that you can think onto the page.
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)
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
/* test code*/
val a = Char(#"a")
val b = Char(#"b")
val accept_aa = accept (Concat(a,a));
val accept_aorbstar = accept (Star(Union(a,b)));
val accept_aborastar = accept (Star(Union(Concat(a,b),a)));
val accept_xaay = accept
(Concat(Concat(Concat(Star(Union(a,b)),a),a),Star(Union(a,b))));
val test1 = accept_aorbstar "abababbbcaabaaba"
val accept_naa = accept (Concat(b,Not(Star(a))));
val test2 = accept (And(Concat(a,Top),Concat(Top,b))) "ajdsfsla"
val test3 = accept (Not(Top)) "b" (*match if a - not a*)
Problem 2: Trominoes
A Tromino is a block made of 3 blocks. Think of it as a square divided into
corners with one missing. The problem is to fill an arbitrarily large square
with trominoes. The amazing thing about this is how the translate function
matches the proof exactly.
Notes: ~1 is minus one. @ means concatenate the items into a list. :: means
split/join a list. nil is the empty
list.
Proof:
Base Case: A 2x2 square with one tromino will have one empty
square at an arbitrary corner.
Induction Case: Assume that a 2^n * 2^n square can be covered
with trominoes with one empty square remaining, and that
square can be placed at an arbitrary corner.
Suppose we have a 2^(n+1) * 2(n+1) square. This can be divided up
into 4 2^n * 2^n squares. Place them such that 3 of the squares
align their empty corners in the center, and one such that the
empty corner is at a corner of the larger square. Fill the three
corners in the center with another tromino. This new square is
now completely filled trominoes except for one corner, and can
be rotated/flipped to move that empty square to an arbitrary corner.
Done. *)
datatype orientation = NW | NE | SW | SE
type tromino = int * int * orientation -> this means a tromino is struct { int,
int, orientation }
fun translate nil (dx,dy) = nil
|translate ((a,b,c)::h) (dx,dy) = (a+dx,b+dy,c)::(translate h (dx,dy))
fun flip nil r = nil
|flip ((a,b,NE)::x) r = (a,~1*b+1+r,SE)::(flip x r)
|flip ((a,b,NW)::x) r = (a,~1*b+1+r,SW)::(flip x r)
|flip ((a,b,SE)::x) r = (a,~1*b+1+r,NE)::(flip x r)
|flip ((a,b,SW)::x) r = (a,~1*b+1+r,NW)::(flip x r)
fun invert nil r = nil
|invert ((a,b,NE)::x) r = (~1*a+1+r, b, NW)::(invert x r )
|invert ((a,b,NW)::x) r = (~1*a+1+r, b, NE)::(invert x r )
|invert ((a,b,SE)::x) r = (~1*a+1+r, b, SW)::(invert x r )
|invert ((a,b,SW)::x) r = (~1*a+1+r, b, SE)::(invert x r )
fun exp( a, 0 ) = 1
|exp( a, b ) = a * (exp ( a, b - 1 ))
fun tile( 1 ) = [(1,1,NE)]
|tile( n ) = let val r = exp( 2, n - 1) in
(translate (invert (tile (n-1)) r) (0,r))
@(translate (flip (tile (n-1)) r) (r,0))
@(translate (tile (n-1)) (r,r))
@(tile (n-1))
@[(r,r,NE)] end
This page took 0.01 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.