#!/usr/bin/perl -w # Author: Paul Fitzpatrick, paulfitz@ai.mit.edu # Copyright (c) 2003 Paul Fitzpatrick # # This file is part of CosmicOS. # # CosmicOS is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # CosmicOS is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with CosmicOS; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA # Using a generator program for the message rather than writing the # message directly doesn't save much in size, but it sure makes things # easier to change afterwards -- at least small niggly things, larger # structural changes can be tricky. # # This perl implementation is quite silly though and won't scale well. use strict; my %token; # library of tokens (symbol sequences) used for designer's convenience. # make sure names are uniquely decodable, or put in spaces! $token{" "} = ""; # whitespace is ignored - no translation $token{"\n"} = ""; $token{"\r"} = ""; $token{"\t"} = ""; $token{"."} = "0"; # digit zero $token{":"} = "1"; # digit one $token{"("} = "2"; # begin expression $token{")"} = "3"; # end expression $token{";"} = "4\n"; # end of line -- not strictly necessary sub irand { my $lim = shift; my $result = int(rand($lim)); return $result; }; sub prand { my $top = shift; my $crop = $top; if ($#_>=0) { $crop = shift; } my @lst = (0 .. ($top-1)); my @lst_out = (); for (my $i=$top; $i>0; $i--) { my $sel = irand($i); push(@lst_out,$lst[$sel]); if ($sel<$i-1) { $lst[$sel] = $lst[$i-1]; } } if ($crop<$top) { @lst_out = @lst_out[0 .. ($crop-1)]; } return @lst_out; }; sub Tokens2Msg { my $msg = ""; foreach my $t (@_) { if (!($t =~ /\[/)) { $msg .= $token{$t}; } } return $msg; }; my $first_high = 0; my %translate_high; my %translate_back; sub Text2Tokens { my $txt = shift; my $base = 0; my @tokens = (); $txt =~ s/\#.*//g; #$txt =~ s/\[[^\]]*\]//g; while ($txt =~ /(\[([^\[\]]*)\])/) { my $x = $1; my $lst = $2; my $qx = quotemeta($x); my $paren = 0; my $term = 0; my $gap = 1; for (my $i=0; $i>> $txt \n"; while ($txt =~ /([a-zA-Z_\+\*\-\/\=\>\<\?\^][a-zA-Z_\+\*\-\/\=\>\<\?\^\!0-9]*)/) { my $x = $1; my $qx = quotemeta($x); if (!defined($translate_high{$x})) { $translate_high{$x} = "$first_high"; $translate_back{$first_high} = $x; #print "DEFINE [$x] as [$first_high]\n"; $first_high++; } my $qy = $translate_high{$x}; $txt =~ s/$qx/$qy/; } while ($txt =~ /([0-9]+)/) { my $n = $1; my $t = ShowBinaryVerbose($n); $txt =~ s/$n/$t/; } while ($txt =~ /(\{\^([^\}]*)\})/) { my $x = $1; my $qy = $2; my $qx = quotemeta($x); $txt =~ s/$qx/$qy/g; # print "$qx -> $qy\n"; # die; } my $line = 0; #print "MESSAGE before tokenizing is:\n$txt\n"; for (my $i=0; $i $detoken{$ch}\n"; } } while ($src =~ /(\(([\:\.]+)\))/) { my $all = $1; my $num = $2; my $q = quotemeta($all); my $n = EvalBinary($num); $src =~ s/$q/$n /g; } while ($src =~ /((\() *([0-9]+)) /) { my $all = $1; my $pre = $2; my $num = $3; my $q = quotemeta($all); my $n = $num; my $id = $translate_back{$n}; if ($n>26) { $src =~ s/$q /$pre${id}_$n /g; } else { $src =~ s/$q /$pre${id} /g; } } $src =~ s/ +\)/\)/g; $src =~ s/\( +/\(/g; $src =~ s/ +/ /g; $src =~ s/\)([^ \;\n\)])/\) $1/g; return $src; }; sub ShowUnary { my $ct = shift; my $txt = ""; for (my $i=0; $i<$ct; $i++) { $txt .= "1 "; # $txt .= "(:)"; } $txt .= "0"; # necessary for unary to be a well-defined function # $txt .= "(.)"; # necessary for unary to be a well-defined function if ($txt ne "") { $txt = Paren("unary", $txt); } else { $txt = Paren("unary"); } return $txt; }; sub ShowBinary { my $txt = ""; my $i = shift; $txt .= "[$i]"; return $txt; }; sub ShowBinaryVerbose { my $txt = ""; my $i = shift; $txt = sprintf("%b",$i); $txt =~ s/0/\./g; $txt =~ s/1/\:/g; $txt = "($txt)"; return $txt; }; sub ShowTerm { return join(" ",@_); }; sub Paren { return "(" . ShowTerm(@_) . ")"; }; sub ShowLine { return ShowTerm(@_) . ";\n"; }; sub Op1 { if (!($#_==1)) { die "broken Op1 " . join(" ", @_) . "\n"; } my $cmp = shift; my $o1 = shift; return Paren($cmp, $o1); }; sub BareOp1 { my $cmp = shift; my $o1 = shift; return "$cmp$o1"; }; sub Op2 { if (!($#_==2)) { die "broken Op2 " . join(" ", @_) . "\n"; } my $cmp = shift; my $o1 = shift; my $o2 = shift; return Paren($cmp, $o1, $o2); }; sub Op { return Paren(@_); }; sub Lit { my $x = shift; return $x; }; sub Ref { my $x = shift; return Op($x); }; sub Tag { my $x = shift; return "{$x}"; }; sub Num { my $x = shift; return "$x"; }; sub Proc { return Paren("?", @_); }; sub ProcMultiple { my $plist = shift; my @args = @$plist; my $txt = ""; return Paren("lambda", Paren(@args), @_); }; sub Template { my $plist = shift; my @args = @$plist; my $txt = ""; return Paren("template", Paren(@args), @_); }; sub ProcTyped { my $plist = shift; my @args = @$plist; my $txt = ""; for (my $i=0; $i<=$#args; $i++) { if ($i%2==1) { if ($i>1) { $txt .= " "; } $txt .= "($args[$i-1] $args[$i])"; } } return Paren("lambda", Paren($txt), @_); }; sub Let { my $plist = shift; my @args = @$plist; my $txt = ""; for (my $i=0; $i<=$#args; $i++) { if ($i%2==1) { if ($i>1) { $txt .= " "; } $txt .= "($args[$i-1] $args[$i])"; } } return Paren("let", Paren($txt), @_); }; sub Apply { return Paren(@_); }; sub ShowUnaryLesson { my $txt = ""; $txt .= "# MATH introduce numbers (in unary notation)\n"; for (my $i=0; $i<=27; $i++) { $txt .= ShowLine(Op("intro",ShowUnary($i))); } for (my $i=27; $i>=0; $i--) { $txt .= ShowLine(Op("intro",ShowUnary($i))); } foreach my $i (0, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23) { $txt .= ShowLine(Op("intro",ShowUnary($i))); } foreach my $i (0, 1, 4, 9, 16, 25) { $txt .= ShowLine(Op("intro",ShowUnary($i))); } foreach my $i (0, 1, 8, 27) { $txt .= ShowLine(Op("intro",ShowUnary($i))); } $txt .= "# MATH now show equality\n"; $txt .= ShowLine(Op("intro","=")); my @examples = prand(10,5); for (my $i=0; $i<=$#examples; $i++) { my $r = $examples[$i]; $txt .= ShowLine(Op2("=",ShowUnary($r),ShowUnary($r))); } $txt .= "# MATH now show other relational operators\n"; $txt .= ShowLine(Op("intro",">")); for (my $i=0; $i<=10; $i++) { my $r = irand(6); my $r2 = irand($r); $txt .= ShowLine(Op2(">",ShowUnary($r+1),ShowUnary($r2))); } $txt .= ShowLine(Op("intro","<")); for (my $i=0; $i<=10; $i++) { my $r = irand(6); my $r2 = irand($r); $txt .= ShowLine(Op2("<",ShowUnary($r2),ShowUnary($r+1))); } for (my $i=0; $i<=10; $i++) { my $r = irand(6); my $r2 = irand(6); my $cmp = "="; if ($r>$r2) { $cmp = ">"; } elsif ($r<$r2) { $cmp = "<"; } $txt .= ShowLine(Op2($cmp,ShowUnary($r),ShowUnary($r2))); } return $txt; }; sub ShowNotLogicLesson { my $txt = ""; $txt .= "# MATH introduce the NOT logical operator\n"; $txt .= ShowLine(Op("intro","not")); for (my $i=0; $i<=5; $i++) { my $r = irand(6); $txt .= ShowLine(Op2("=",ShowUnary($r),ShowUnary($r))); $txt .= ShowLine(Op1("not",Op2("<",ShowUnary($r),ShowUnary($r)))); $txt .= ShowLine(Op1("not",Op2(">",ShowUnary($r),ShowUnary($r)))); } for (my $i=0; $i<=5; $i++) { my $r = irand(6); my $r2 = $r+1+irand(3); $txt .= ShowLine(Op1("not",Op2("=",ShowUnary($r),ShowUnary($r2)))); $txt .= ShowLine(Op2("<",ShowUnary($r),ShowUnary($r2))); $txt .= ShowLine(Op1("not",Op2(">",ShowUnary($r),ShowUnary($r2)))); } for (my $i=0; $i<=5; $i++) { my $r = irand(6); my $r2 = $r+1+irand(3); $txt .= ShowLine(Op1("not",Op2("=",ShowUnary($r2),ShowUnary($r)))); $txt .= ShowLine(Op2(">",ShowUnary($r2),ShowUnary($r))); $txt .= ShowLine(Op1("not",Op2("<",ShowUnary($r2),ShowUnary($r)))); } return $txt; }; sub ShowTrue { return Op("true"); }; sub ShowFalse { return Op("false"); }; sub ShowTrueComparison { my $txt = ""; my $c = irand(3); if ($c==0) { my $r = irand(6); $txt .= Op2("=",ShowUnary($r),ShowUnary($r)); } elsif ($c==1) { my $r = irand(6); my $r2 = $r+1+irand(3); $txt .= Op2("<",ShowUnary($r),ShowUnary($r2)); } else { my $r = irand(6); my $r2 = $r+1+irand(3); $txt .= Op2(">",ShowUnary($r2),ShowUnary($r)); } return $txt; } sub ShowFalseComparison { my $txt = ""; my $c = irand(3); if ($c==0) { my $r = irand(6); my $r2 = irand(6); if ($r == $r2) { if(irand(2)==1) { $r++; } else { $r2++; } } $txt .= Op2("=",ShowUnary($r),ShowUnary($r2)); } else { my $r = irand(7); my $r2 = irand(7); my $cmp = ">"; if ($r>$r2) { $cmp = "<"; } else { $cmp = ">"; } $txt .= Op2($cmp,ShowUnary($r),ShowUnary($r2)); } return $txt; } sub ShowAndLogicLesson { my $txt = ""; $txt .= "# MATH introduce the AND logical operator\n"; $txt .= ShowLine(Op("intro","and")); for (my $i=0; $i<10; $i++) { $txt .= ShowLine(Op2("and",ShowTrueComparison(),ShowTrueComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("and", ShowTrueComparison(), ShowFalseComparison()))); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("and", ShowFalseComparison(), ShowTrueComparison()))); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("and", ShowFalseComparison(), ShowFalseComparison()))); } for (my $i=0; $i<10; $i++) { my $t1 = irand(2); my $t2 = irand(2); my $c1 = ""; my $c2 = ""; if ($t1==1) { $c1 = ShowTrueComparison(); } else { $c1 = ShowFalseComparison(); } if ($t2==1) { $c2 = ShowTrueComparison(); } else { $c2 = ShowFalseComparison(); } my $c = Op2("and",$c1,$c2); if (!(($t1==1)&&($t2==1))) { $c = Op1("not",$c); } $txt .= ShowLine($c); } return $txt; } sub ShowOrLogicLesson { my $txt = ""; $txt .= "# MATH introduce the OR logical operator\n"; $txt .= ShowLine(Op("intro","or")); for (my $i=0; $i<10; $i++) { $txt .= ShowLine(Op2("or",ShowTrueComparison(),ShowTrueComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("or",ShowTrueComparison(),ShowFalseComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("or",ShowFalseComparison(),ShowTrueComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("or", ShowFalseComparison(), ShowFalseComparison()))); } for (my $i=0; $i<10; $i++) { my $t1 = irand(2); my $t2 = irand(2); my $c1 = ""; my $c2 = ""; if ($t1==1) { $c1 = ShowTrueComparison(); } else { $c1 = ShowFalseComparison(); } if ($t2==1) { $c2 = ShowTrueComparison(); } else { $c2 = ShowFalseComparison(); } my $c = Op2("or",$c1,$c2); if (!(($t1==1)||($t2==1))) { $c = Op1("not",$c); } $txt .= ShowLine($c); } return $txt; } sub ShowTrueFalseLesson { my $txt = ""; $txt .= "# MATH use equality for truth values\n"; for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowTrueComparison(),ShowTrueComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowFalseComparison(),ShowFalseComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("=", ShowFalseComparison(), ShowTrueComparison()))); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op1("not", Op2("=", ShowTrueComparison(), ShowFalseComparison()))); } $txt .= ShowLine(Op("intro","true")); $txt .= ShowLine(Op("intro","false")); for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowTrue(),ShowTrueComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowTrueComparison(),ShowTrue())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowFalse(),ShowFalseComparison())); } for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=",ShowFalseComparison(),ShowFalse())); } $txt .= ShowLine(Op2("=",ShowTrue(),ShowTrue())); $txt .= ShowLine(Op2("=",ShowFalse(),ShowFalse())); $txt .= ShowLine(Op1("not",Op2("=",ShowTrue(),ShowFalse()))); $txt .= ShowLine(Op1("not",Op2("=",ShowFalse(),ShowTrue()))); return $txt; }; sub ShowQuantifierLesson { my $txt = ""; $txt .= "# MATH introduce universal quantifier\n"; $txt .= "# really need to link with sets for true correctness\n"; $txt .= "# and the examples here are REALLY sparse, need much more\n"; $txt .= ShowLine(Op("intro","forall")); for (my $i=5; $i>=0; $i--) { $txt .= ShowLine(Op2("<", Num($i), Op2("+",Num($i),Num(1)))); } $txt .= ShowLine(Op("forall", Proc(Lit("x"), Op2("<", Ref("x"), Op2("+",Ref("x"),Num(1)))))); for (my $i=5; $i>=0; $i--) { my $txt0 = Op2("<", Num($i), Op2("*",Num($i),Num(2))); if (!($i<$i*2)) { $txt0 = Op1("not",$txt0); } $txt .= ShowLine($txt0); } $txt .= ShowLine(Op1("not", Op("forall", Proc(Lit("x"), Op2("<", Ref("x"), Op2("*",Ref("x"),Num(2))))))); $txt .= "# MATH introduce existential quantifier\n"; $txt .= "# really need to link with sets for true correctness\n"; $txt .= "# and the examples here are REALLY sparse, need much more\n"; for (my $i=5; $i>=0; $i--) { my $txt0 = Op2("=", Num($i), Op2("*",Num(2),Num(2))); if (!($i==2*2)) { $txt0 = Op1("not",$txt0); } $txt .= ShowLine($txt0); } $txt .= ShowLine(Op("intro","exists")); $txt .= ShowLine(Op("exists", Proc(Lit("x"), Op2("=", Ref("x"), Op2("*",Num(2),Num(2)))))); for (my $i=5; $i>=0; $i--) { my $txt0 = Op2("=", Num($i), Op2("+",Num($i),Num(2))); if (!($i==$i+1)) { $txt0 = Op1("not",$txt0); } $txt .= ShowLine($txt0); } $txt .= ShowLine(Op("not", Op("exists", Proc(Lit("x"), Op2("=", Ref("x"), Op2("+",Ref("x"),Num(2))))))); return $txt; }; sub ShowImplicationLesson { my $txt = ""; $txt .= "# MATH introduce logical implication\n"; $txt .= ShowLine(Op("intro","=>")); $txt .= ShowLine(Op("define", "=>", Proc("x", Proc("y", Op1("not", Op2("and", Ref("x"), Op1("not", Ref("y")))))))); $txt .= ShowLine(Op2("=>",ShowTrue(),ShowTrue())); $txt .= ShowLine(Op1("not",Op2("=>",ShowTrue(),ShowFalse()))); $txt .= ShowLine(Op2("=>",ShowFalse(),ShowTrue())); $txt .= ShowLine(Op2("=>",ShowFalse(),ShowFalse())); $txt .= ShowLine(Op("forall", Proc(Lit("x"), Op("forall", Proc(Lit("y"), Op2("=>", Op2("=>", Ref("x"), Ref("y")), Op2("=>", Op1("not",Ref("y")), Op1("not",Ref("x"))))))))); return $txt; }; sub ShowAdditionLesson { my $txt = ""; $txt .= "# MATH introduce addition\n"; $txt .= ShowLine(Op("intro","+")); for (my $i=0; $i<10; $i++) { my $r = irand(5); my $r2 = irand(5); $txt .= ShowLine(Op2("=", Op2("+", ShowUnary($r), ShowUnary($r2)), ShowUnary($r+$r2))); } return $txt; }; sub ShowSubtractionLesson { my $txt = ""; $txt .= "# MATH introduce subtraction\n"; $txt .= ShowLine(Op("intro","-")); for (my $i=0; $i<10; $i++) { my $r = irand(5); my $r2 = irand(5); $txt .= ShowLine(Op2("=", Op2("-", ShowUnary($r+$r2), ShowUnary($r2)), ShowUnary($r))); } return $txt; }; sub ShowMultiplicationLesson { my $txt = ""; $txt .= "# MATH introduce multiplication\n"; $txt .= ShowLine(Op("intro","*")); for (my $i=0; $i<=3; $i++) { for (my $j=0; $j<=3; $j++) { $txt .= ShowLine(Op2("=", Op2("*", ShowUnary($i), ShowUnary($j)), ShowUnary($i*$j))); } } for (my $i=0; $i<10; $i++) { my $r = irand(4); my $r2 = irand(4); $txt .= ShowLine(Op2("=", Op2("*", ShowUnary($r), ShowUnary($r2)), ShowUnary($r*$r2))); } return $txt; }; sub ShowDoubleLesson { my $txt = ""; $txt .= "# MATH introduce doubling as a special case of multiplication\n"; $txt .= "# as prelude to binary representation\n"; $txt .= ShowLine(Op("intro",":")); for (my $i=0; $i<=4; $i++) { $txt .= ShowLine(Op2("=",Op1(":",ShowUnary($i)),ShowUnary($i*2))); } for (my $i=0; $i<=4; $i++) { $txt .= ShowLine(Op2("=",ShowUnary($i*2),Op1(":",ShowUnary($i)))); } for (my $i=0; $i<=4; $i++) { $txt .= ShowLine(Op2("=", Op2("*",ShowUnary($i),ShowUnary(2)), Op1(":",ShowUnary($i)))); } for (my $i=0; $i<=4; $i++) { $txt .= ShowLine(Op2("=", BareOp1(":",ShowUnary($i)), Op1(":",ShowUnary($i)))); } return $txt; }; sub ShowBinaryLesson { my $txt = ""; $txt .= "# MATH introduce a simple form of binary notation\n"; $txt .= "# After this lesson, in the higher-level version of the message,\n"; $txt .= "# will expand decimal to stand for the binary notation given.\n"; for (my $i=0; $i<16; $i++) { $txt .= ShowLine(Op2("=",ShowUnary($i),ShowBinaryVerbose($i))); } for (my $i=0; $i<16; $i++) { my $j = irand(16); $txt .= ShowLine(Op2("=",ShowBinaryVerbose($j),ShowUnary($j))); } for (my $i=0; $i<8; $i++) { my $r = irand(16); my $r2 = irand(16); $txt .= ShowLine(Op2("=", Op2("+", ShowBinaryVerbose($r), ShowBinaryVerbose($r2)), ShowBinaryVerbose($r+$r2))); } for (my $i=0; $i<8; $i++) { my $r = irand(16); my $r2 = irand(16); $txt .= ShowLine(Op2("=", Op2("*", ShowBinaryVerbose($r), ShowBinaryVerbose($r2)), ShowBinaryVerbose($r*$r2))); } return $txt; }; sub ShowEvaluationLesson { my $txt = ""; $txt .= "# MATH demonstrate idea of leaving gaps in an expression\n"; $txt .= "# and then filling them in afterwards\n"; $txt .= "# the examples given leave a lot to be desired!\n"; for (my $i=0; $i<8; $i++) { my $r = irand(16); my $r2 = irand(16); $txt .= ShowLine(Apply(Proc(Lit("x"), Op2("=", Op2("+",Num($r),Ref("x")), Num($r+$r2))), Num($r2))); } for (my $i=0; $i<8; $i++) { my $r = irand(16); my $r2 = irand(16); $txt .= ShowLine(Apply(Apply(Proc(Lit("x"), Proc(Lit("y"), Op2("=", Op2("*", Ref("x"), Ref("y")), Num($r*$r2)))), Num($r)), Num($r2))); } for (my $i=0; $i<8; $i++) { my $r = irand(16); my $r2 = irand(16); $txt .= ShowLine(Apply(Apply(Apply(Proc(Lit("z"), Proc(Lit("x"), Proc(Lit("y"), Op2("=", Op2("*", Ref("x"), Ref("y")), Ref("z"))))), Num($r*$r2)), Num($r)), Num($r2))); } return $txt; }; sub ShowDefineFunctionLesson { my $txt = ""; $txt .= "# MATH show some simple function calls\n"; $txt .= "# and show a way to remember functions across statements\n"; for (my $i=0; $i<8; $i++) { my $r = irand(10); $txt .= ShowLine(Op2("=", Apply(Proc(Lit("square"), Apply(Lit("square"), Num($r))), Proc(Lit("x"), Op2("*", Ref("x"), Ref("x")))), Num($r*$r))); } $txt .= ShowLine(Op2("define", Lit("square"), Proc(Lit("x"), Op2("*", Ref("x"), Ref("x"))))); for (my $i=0; $i<4; $i++) { my $r = irand(10); $txt .= ShowLine(Op2("=", Apply(Lit("square"), Num($r)), Num($r*$r))); } $txt .= ShowLine(Op2("define", Lit("plusone"), Proc(Lit("x"), Op2("+", Ref("x"), Lit("1"))))); for (my $i=0; $i<4; $i++) { my $r = irand(10); $txt .= ShowLine(Op2("=", Apply(Lit("plusone"), Num($r)), Num($r+1))); } return $txt; }; sub ShowLetLesson { my $txt = ""; $txt .= "# MATH introduce sugar for let\n"; $txt .= "# if would be good to introduce desugarings more rigorously, but for now...\n"; $txt .= "# ... just a very vague sketch\n"; $txt .= ShowLine(Op1("intro", "let")); $txt .= ShowLine(Op2("=", Op("let", Paren(Paren("x",10)), Op2("+", Ref("x"), 5)), Apply(Proc("x", Op2("+", Ref("x"), 5)), 10))); $txt .= ShowLine(Op2("=", Op("let", Paren(Paren("x",10),Paren("y",5)), Op2("+", Ref("x"), Ref("y"))), Apply(Apply(Proc("x", Proc("y", Op2("+", Ref("x"), Ref("y")))), 10), 5))); return $txt; }; sub ShowIfLesson { my $txt = ""; $txt .= "# MATH show mechanisms for branching\n"; $txt .= ShowLine(Op("intro","if")); for (my $i=0; $i<16; $i++) { my $r1 = irand(2); my $r2 = irand(10); my $r3 = irand(10); my $cmp = ShowTrue(); my $out = ""; if ($r1) { $cmp = ShowTrue(); } else { $cmp = ShowFalse(); } if ($r1) { $out .= Num($r2); } else { $out = Num($r3); } $txt .= ShowLine(Op2("=", Op("if", $cmp, Num($r2), Num($r3)), $out)); } $txt .= "# MATH some pure lambda calculus definitions - optional\n"; $txt .= "# these definitions are not quite what we want\n"; $txt .= "# since thinking of everything as a function requires headscratching\n"; $txt .= "# it would be better to use these as a parallel means of evaluation\n"; $txt .= "# ... for expressions\n"; $txt .= ShowLine(Op2("define", "pure-if", Proc(Lit("x"), Proc(Lit("y"), Proc(Lit("z"), Apply("x", Ref("y"), Ref("z"))))))); $txt .= ShowLine(Op2("define", "pure-true", Proc(Lit("y"), Proc(Lit("z"), Apply("y"))))); $txt .= ShowLine(Op2("define", "pure-false", Proc(Lit("y"), Proc(Lit("z"), Apply("z"))))); $txt .= ShowLine(Op2("define", "pure-cons", Proc(Lit("x"), Proc(Lit("y"), Proc(Lit("z"), Op("pure-if", Ref("z"), Ref("x"), Ref("y"))))))); $txt .= ShowLine(Op2("define", "pure-car", Proc(Lit("x"), Apply(Lit("x"), Ref("pure-true"))))); $txt .= ShowLine(Op2("define", "pure-cdr", Proc(Lit("x"), Apply(Lit("x"), Ref("pure-false"))))); $txt .= ShowLine(Op2("define", "zero", Proc("f", Proc("x",Ref("x"))))); $txt .= ShowLine(Op2("define", "one", Proc("f", Proc("x", Apply("f", Ref("x")))))); $txt .= ShowLine(Op2("define", "two", Proc("f", Proc("x", Apply("f", Apply("f", Ref("x"))))))); $txt .= ShowLine(Op2("define", "succ", Proc(Lit("n"), Proc("f", Proc("x", Apply("f", Apply(Apply("n", Ref("f")), Ref("x")))))))); $txt .= ShowLine(Op2("define", "add", Proc("a", Proc("b", Apply(Apply("a", Ref("succ")), Ref("b")))))); $txt .= ShowLine(Op2("define", "mult", Proc("a", Proc("b", Apply(Apply("a", Op1("add", Ref("b"))), Ref("zero")))))); $txt .= ShowLine(Op2("define", "pred", Proc("n", Op1("pure-cdr", Apply(Apply("n", Proc("p", Op2("pure-cons", Op1("succ", Op1("pure-car", Ref("p"))), Op1("pure-car", Ref("p"))))), Op2("pure-cons", Ref("zero"), Ref("zero"))))))); $txt .= ShowLine(Op2("define", "is-zero", Proc("n", Apply(Apply("n", Proc("dummy", Ref("pure-false")), Ref("pure-true")))))); $txt .= ShowLine(Op2("define", "fixed-point", Proc("f", Apply(Proc(Lit("x"), Apply("f", Apply("x", Ref("x")))), Proc(Lit("x"), Apply("f", Apply("x", Ref("x")))))))); $txt .= "# .. but for rest of message will assume that define does fixed-point for us\n"; $txt .= "# now build a link between numbers and church number functions\n"; $txt .= ShowLine(Op2("define", "unchurch", Proc("c", Op("c", Proc("x", Op2("+", Ref("x"), 1)), 0)))); $txt .= ShowLine(Op2("=", 0, Op1("unchurch", Ref("zero")))); $txt .= ShowLine(Op2("=", 1, Op1("unchurch", Ref("one")))); $txt .= ShowLine(Op2("=", 2, Op1("unchurch", Ref("two")))); $txt .= ShowLine(Op2("define", "church", Proc("x", Op("if", Op2("=", 0, Ref("x")), Ref("zero"), Op1("succ", Op1("church", Op2("-", Ref("x"), 1))))))); return $txt; }; sub Factorial { my $r = 1; my $x = shift; if ($x>0) { $r = $x*Factorial($x-1); } return $r; }; sub ShowRecursionLesson { my $txt = ""; $txt .= "# MATH show an example of recursive evaluation\n"; $txt .= "# skipping over a lot of definitions and desugarings\n"; $txt .= ShowLine(Op2("define", Lit("easy-factorial"), Proc(Lit("f"), Proc(Lit("x"), (Op("if", Op2(">",Ref("x"),Num(0)), Op2("*", Ref("x"), Apply(Lit("f"), Ref("f"), Op2("-",Ref("x"),Num(1)))), 1)))))); $txt .= ShowLine(Op2("define", Lit("factorial"), Proc(Lit("x"), (Op("if", Op2(">",Ref("x"),Num(0)), Op2("*", Ref("x"), Apply(Lit("factorial"), Op2("-",Ref("x"),Num(1)))), 1))))); for (my $i=0; $i<=5; $i++) { $txt .= ShowLine(Op2("=", Apply("easy-factorial", Ref("easy-factorial"), Num($i)), Factorial($i))); } for (my $i=0; $i<=5; $i++) { $txt .= ShowLine(Op2("=", Apply("factorial", Num($i)), Factorial($i))); } # this unary function is broken - see fritz code for a good one # $txt .= "# show a definition for the unary function used early on\n"; # $txt .= ShowLine(Op2("define", # "unary", # Proc("x", # Op("if", # Op2("=",Ref("x"),0), # 0, # Op2("+",Ref("unary"),1))))); return $txt; }; sub ShowSetLesson { my $txt = ""; $txt .= "# MATH introduce sets and set membership\n"; $txt .= ShowLine(Op1("intro","element")); $txt .= ShowLine(Op2("define", "element", Proc("x", Proc("lst", Op1("not", Op2("=", Op("list-find", Ref("lst"), Ref("x"), Proc("y", Ref("false"))), Ref("false"))))))); for (my $i=0; $i<5; $i++) { my %hset; for (my $j=0; $j<6; $j++) { $hset{irand(10)} = 1; } my @set = keys %hset; for (my $j=0; $j<3; $j++) { my $mem = $set[irand($#set+1)]; $txt .= ShowLine(Op("element", Num($mem), ShowList(@set))); } } for (my $i=0; $i<5; $i++) { my %hset; for (my $j=0; $j<6; $j++) { $hset{irand(10)} = 1; } my @set = keys %hset; (my $mem, @set) = @set; $txt .= ShowLine(Op1("not", Op("element", Num($mem), ShowList(@set)))); } $txt .= "# rules for set equality\n"; $txt .= ShowLine(Op2("define", "set-subset", Proc("x", Proc("y", Op("if", Op2(">", Op1("list-length",Ref("x")), 0), Op2("and", Op2("element", Op1("head",Ref("x")), Ref("y")), Op2("set-subset", Op1("tail",Ref("x")), Ref("y"))), Op("true")))))); $txt .= ShowLine(Op2("define", "set=", Proc("x", Proc("y", Op2("and", Op2("set-subset", Ref("x"), Ref("y")), Op2("set-subset", Ref("y"), Ref("x"))))))); $txt .= ShowLine(Op2("set=", ShowList("1", "5", "9"), ShowList("5", "1", "9"))); $txt .= ShowLine(Op2("set=", ShowList("1", "5", "9"), ShowList("9", "1", "5"))); $txt .= ShowLine(Op1("not", Op2("set=", ShowList("1", "5", "9"), ShowList("1", "5")))); $txt .= "# let's go leave ourselves wide open to Russell's paradox\n"; $txt .= "# ... by using characteristic functions\n"; $txt .= "# ... since it doesn't really matter for communication purposes\n"; $txt .= "# ... and so far this is just used/tested with sets of integers really\n"; $txt .= ShowLine(Op2("element", Num(5), Op("all", Proc(Lit("x"), Op("=", Op2("+", Ref("x"), Num(10)), Num(15)))))); $txt .= ShowLine(Op2("element", Num(3), Op("all", Proc(Lit("x"), Op("=", Op2("*", Ref("x"), Num(3)), Op2("+", Ref("x"), Num(6))))))); $txt .= ShowLine(Op("define", Lit("empty-set"), ShowList())); $txt .= ShowLine(Op2("element", Num(0), Ref("natural-set"))); $txt .= ShowLine(Op("forall", Proc(Lit("x"), Op2("=>", Op2("element", Ref("x"), Ref("natural-set")), Op2("element", Op2("+", Ref("x"), Num(1)), Ref("natural-set")))))); for (my $i=1; $i<10; $i++) { $txt .= ShowLine(Op2("element", Num($i), Ref("natural-set"))); } $txt .= ShowLine(Op1("not", Op2("element", ShowTrue(), Ref("natural-set")))); $txt .= ShowLine(Op1("not", Op2("element", ShowFalse(), Ref("natural-set")))); $txt .= ShowLine(Op("define", Lit("boolean-set"), ShowList(ShowTrue(), ShowFalse()))); $txt .= ShowLine(Op2("element", Lit(ShowTrue()), Ref("boolean-set"))); $txt .= ShowLine(Op2("element", Lit(ShowFalse()), Ref("boolean-set"))); $txt .= ShowLine(Op1("not", Op2("element", "0", Ref("boolean-set")))); $txt .= ShowLine(Op("define", Lit("even-natural-set"), Op1("all", Proc(Lit("x"), Op1("exists", Proc(Lit("y"), Op2("and", Op2("element", Ref("y"), Ref("natural-set")), Op2("=", Op2("*",2,Ref("y")), Ref("x"))))))))); for (my $i=0; $i<=6; $i++) { my $txt0 = Op2("element", Num($i), Ref("even-natural-set")); if (($i%2)!=0) { $txt0 = Op1("not",$txt0); } $txt .= ShowLine(Op2("element", Num($i), Ref("natural-set"))); $txt .= ShowLine($txt0); } return $txt; }; sub ShowListVerbose { my $txt = ""; $txt .= Op(Op("list", ($#_+1)), @_); return $txt; }; sub ShowListOld { my $txt = ""; $txt .= "[" . join(" ",@_) . "]"; return $txt; }; sub ShowList { my $txt = ""; $txt .= "(" . join(" ",("vector", @_)) . ")"; return $txt; }; sub ShowTranslateLesson { my $txt = ""; $txt .= "# HACK describe changes to the implicit interpreter to allow new special forms\n"; $txt .= ShowLine(Op2("define", "base-translate", Ref("translate"))); $txt .= ShowLine(Op2("define", "translate", Proc("x", Op("if", Op2("=", Ref("x"), 10), 15, Op1("base-translate", Ref("x")))))); $txt .= ShowLine(Op2("=", 10, 15)); $txt .= ShowLine(Op2("=", Op2("+", 10, 15), 30)); $txt .= ShowLine(Op2("define", "translate", Ref("base-translate"))); $txt .= ShowLine(Op1("not",Op2("=", 10, 15))); $txt .= ShowLine(Op2("=", Op2("+", 10, 15), 25)); $txt .= "# now can create a special form for lists\n"; $txt .= ShowLine(Op2("define", "translate", Proc("x", Op("if", Op1("number?", Ref("x")), Op1("base-translate", Ref("x")), Op("if", Op2("=", Op1("head",Ref("x")), "vector"), Op1("translate", Op2("prepend", Op(Op("list", 2), "list", Op1("list-length", Op1("tail",Ref("x")))), Op1("tail",Ref("x")))), Op1("base-translate",Ref("x"))))))); $txt .= ShowLine(Op2("=", Op("vector", 1, 2, 3), Op(Op("list", 3), 1, 2, 3))); $txt .= "# now to desugar let expressions\n"; $txt .= ShowLine(Op2("define", "translate-with-vector", Ref("translate"))); $txt .= ShowLine(Op2("define", "translate-let-form", Proc("x", Proc("body", Op("if", Op2("=", Op1("list-length", Ref("x")), 0), Op1("translate",Ref("body")), Op("translate-let-form", Op1("tail",Ref("x")), Op("vector", Op("vector", "?", Op1("head",Op1("head",Ref("x"))), Ref("body")), Op1("head",Op1("tail",Op1("head",Ref("x"))))))))))); $txt .= ShowLine(Op2("define", "translate", Proc("x", Op("if", Op1("number?", Ref("x")), Op1("translate-with-vector", Ref("x")), Op("if", Op2("=", Op1("head",Ref("x")), "let"), Op("translate-let-form", Op1("head", Op1("tail",Ref("x"))), Op1("head", Op1("tail", Op1("tail",Ref("x"))))), Op1("translate-with-vector",Ref("x"))))))); $txt .= ShowLine(Op2("let", Paren(Paren("x",20)), Op2("=", Ref("x"), 20))); $txt .= ShowLine(Op2("let", Paren(Paren("x",50), Paren("y",20)), Op2("=", Op2("-",Ref("x"),Ref("y")), 30))); return $txt; }; sub ShowListLesson { my $txt = ""; $txt .= "# MATH illustrate lists and some list operators\n"; $txt .= "# to make list describable as a function, need to preceed lists\n"; $txt .= "# ... with an argument count\n"; $txt .= "# lists will be written as [1 2 1] = (list 3 1 2 1) after this lesson\n"; $txt .= "# it would be nice to include such syntactic sugar in the message but that\n"; $txt .= "# ... is a fight for another day\n"; $txt .= "# finally, lists keep an explicit record of their length\n"; $txt .= "# this is to avoid the need for using a special 'nil' symbol\n"; $txt .= "# ... which cannot itself be placed in the list.\n"; $txt .= "#\n"; $txt .= "# MISSING - intro to cons, car, cdr\n"; $txt .= "# used to be pure-cons pure-car pure-cdr but changed for better interface to scheme\n"; $txt .= "# also should introduce number? check function\n"; $txt .= "#\n"; $txt .= ShowLine(Op2("define", "list-helper", Proc("n", Proc("ret", Op("if", Op2(">", Ref("n"), 1), Proc("x", Apply("list-helper", Op2("-", Ref("n"), 1), Proc("y", Proc("z", Apply("ret", Op2("+", 1, Ref("y")), Op2("cons", Ref("x"), Ref("z"))))))), Proc("x", Apply("ret", 1, Ref("x")))))))); $txt .= ShowLine(Op2("define", "list", Proc("n", Op("if", Op2("=", Ref("n"), 0), Op2("cons", 0, 0), Op("list-helper", Ref("n"), Proc("y", Proc("z", Op2("cons", Ref("y"), Ref("z"))))))))); $txt .= ShowLine(Op2("define", "head", Proc("lst", Op("if", Op2("=", Op1("car", Ref("lst")), "0"), Ref("undefined"), Op("if", Op2("=", Op1("car", Ref("lst")), "1"), Op1("cdr", Ref("lst")), Op1("car", Op1("cdr",Ref("lst")))))))); $txt .= ShowLine(Op2("define", "tail", Proc("lst", Op("if", Op2("=", Op1("car", Ref("lst")), "0"), Ref("undefined"), Op("if", Op2("=", Op1("car", Ref("lst")), "1"), Op2("cons", 0, 0), Op2("cons", Op2("-", Op1("car", Ref("lst")), "1"), Op1("cdr",Op1("cdr",Ref("lst"))))))))); $txt .= ShowLine(Op2("define", "list-length", Proc("lst", Op1("car", Ref("lst"))))); $txt .= ShowLine(Op2("define", "list-ref", Proc("lst", Proc("n", Op("if", Op2("=", Op1("list-ref",Ref("lst")), 0), Ref("undefined"), Op("if", Op2("=",Ref("n"),0), Op1("head", Ref("lst")), Op2("list-ref", Op1("tail", Ref("lst")), Op2("-", Ref("n"), 1)))))))); $txt .= ShowLine(Op2("define", "prepend", Proc("x", Proc("lst", Op("if", Op2("=",Op1("list-length", Ref("lst")),0), Op2("cons", 1, Ref("x")), Op2("cons", Op2("+", Op1("list-length", Ref("lst")), 1), Op2("cons", Ref("x"), Op1("cdr",Ref("lst"))))))))); $txt .= ShowLine(Op2("define", "list=", Proc("x", Proc("y", Op("if", Op2("=", Op1("list-length", Ref("x")), Op1("list-length", Ref("y"))), Op("if", Op2(">", Op1("list-length", Ref("x")), 0), Op2("and", Op2("=", Op1("head",Ref("x")), Op1("head",Ref("y"))), Op2("list=", Op1("tail",Ref("x")), Op1("tail",Ref("y")))), Ref("true")), Ref("false")))))); my @examples = prand(10,5); for (my $i=0; $i<=$#examples; $i++) { my $r = $examples[$i]; $txt .= ShowLine(Op2("=", Op1("list-length", ShowListVerbose(prand(10,$r))), $r)); } for (my $i=0; $i<10; $i++) { my $len = irand(10)+1; my @lst = (); for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my ($head, @tail) = @lst; $txt .= ShowLine(Op2("=", Op1("head", ShowListVerbose(@lst)), $head)); $txt .= ShowLine(Op2("list=", Op1("tail", ShowListVerbose(@lst)), ShowListVerbose(@tail))); } for (my $i=0; $i<10; $i++) { my $len = irand(10)+1; my @lst = (); for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my $idx = irand($len); my $val = $lst[$idx]; $txt .= ShowLine(Op2("=", Op2("list-ref", ShowListVerbose(@lst), $idx), $val)); } for (my $i=0; $i<5; $i++) { my $len = $i; my @lst = (); my $cmp = "list="; for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my $idx = irand($len); my $val = $lst[$idx]; $txt .= ShowLine(Op2($cmp, ShowListVerbose(@lst), ShowListVerbose(@lst))); } $txt .= "# this next batch of examples are a bit misleading, should streamline\n"; for (my $i=0; $i<5; $i++) { my $len = $i; my @lst = (); my $cmp = "list="; for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my $idx = irand($len); my $val = $lst[$idx]; $txt .= ShowLine(Op1("not", Op2($cmp, ShowListVerbose(@lst), ShowListVerbose((irand(10), @lst))))); $txt .= ShowLine(Op1("not", Op2($cmp, ShowListVerbose(@lst), ShowListVerbose((@lst, irand(10)))))); } $txt .= "# some helpful functions\n"; for (my $i=0; $i<8; $i++) { my $len = $i; my @lst = (); my $cmp = "="; for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my $val = irand(20); $txt .= ShowLine(Op2("list=", Op("prepend", $val, ShowListVerbose(@lst)), ShowListVerbose($val, @lst))); } # $txt .= ShowLine(Op2("define", # "list-length", # Proc("x", # Op("if", # Op2("=", # Ref("x"), # ShowListVerbose()), # 0, # Op2("+", # 1, # Op1("list-length", # Op1("tail",Ref("x")))))))); $txt .= ShowLine(Op2("define", "pair", Proc("x", Proc("y", ShowListVerbose(Ref("x"), Ref("y")))))); $txt .= ShowLine(Op2("define", "first", Proc("lst", Op1("head",Ref("lst"))))); $txt .= ShowLine(Op2("define", "second", Proc("lst", Op1("head",Op1("tail",Ref("lst")))))); @examples = prand(10,3); my @examples2 = prand(10,$#examples+1); for (my $i=0; $i<=$#examples; $i++) { my $r = $examples[$i]; my $r2 = $examples2[$i]; $txt .= ShowLine(Op2("list=", Op2("pair", $r, $r2), ShowListVerbose($r, $r2))); $txt .= ShowLine(Op2("=", Op1("first",Op2("pair", $r, $r2)), $r)); $txt .= ShowLine(Op2("=", Op1("second",Op2("pair", $r, $r2)), $r2)); } $txt .= ShowLine(Op2("define", "list-find-helper", Proc("lst", Proc("key", Proc("fail", Proc("idx", Op("if", Op2("=", Op1("list-length", Ref("lst")), 0), Op1("fail", 0), Op("if", Op2("=", Op1("head",Ref("lst")), Ref("key")), Ref("idx"), Op("list-find-helper", Op1("tail",Ref("lst")), Ref("key"), Ref("fail"), Op2("+", Ref("idx"), 1)))))))))); $txt .= ShowLine(Op2("define", "list-find", Proc("lst", Proc("key", Proc("fail", Op("list-find-helper", Ref("lst"), Ref("key"), Ref("fail"), 0)))))); $txt .= ShowLine(Op2("define", "example-fail", Proc("x", 100))); for (my $i=0; $i<10; $i++) { my $len = irand(10)+1; my @lst = (); for (my $j=0; $j<$len; $j++) { push(@lst,irand(20)); } my $idx = irand($len); my $val = $lst[$idx]; my $idx2 = -1; for (my $j=0; $j<$len; $j++) { if ($lst[$j] == $val) { if ($idx2<0) { $idx2 = $j; } } } $txt .= ShowLine(Op2("=", Op("list-find", ShowListVerbose(@lst), $val, Ref("example-fail")), $idx2)); } for (my $i=0; $i<3; $i++) { (my $val, my @lst) = prand(20,5+$i*2); $txt .= ShowLine(Op2("=", Op("list-find", ShowListVerbose(@lst), $val, Ref("example-fail")), 100)); } $txt .= ShowTranslateLesson(); $txt .= "# the is-list function is now on dubious ground\n"; $txt .= "# this stuff will be replaced with typing ASAP\n"; $txt .= ShowLine(Op("define", "is-list", Proc("x", Op1("not", Op1("number?", Ref("x")))))); $txt .= ShowLine(Op1("is-list", ShowListVerbose(1, 3))); $txt .= ShowLine(Op1("is-list", ShowListVerbose())); $txt .= ShowLine(Op1("not", Op1("is-list", 23))); # $txt .= ShowLine(Op1("not", # Op1("is-list", # Proc("x", Op2("+", Ref("x"), 10))))); $txt .= ShowLine(Op1("is-list", ShowListVerbose(ShowListVerbose(2, 3), 1, Proc("x", Op2("+", Ref("x"), 10))))); return $txt; } sub ShowMapLesson { my $txt = ""; $txt .= "# MATH show map function for applying a function across the elements of a list\n"; $txt .= ShowLine(Op2("define", "map", ProcMultiple(["p", "lst"], Op("if", Op2(">", Op1("list-length", Ref("lst")), 0), Op2("prepend", Op("p",Op1("head",Ref("lst"))), Op("map", Ref("p"), Op1("tail",Ref("lst")))), ShowList())))); for (my $i=0; $i<4; $i++) { my @list = prand(20,$i+3); my @out = (); foreach my $n (@list) { push(@out,2*$n); } $txt .= ShowLine(Op2("=", Op("map", Proc("x", Op2("*",Ref("x"),2)), ShowList(@list)), ShowList(@out))); } for (my $i=0; $i<4; $i++) { my @list = prand(20,$i+3); my @out = (); foreach my $n (@list) { push(@out,42); } $txt .= ShowLine(Op2("=", Op("map", Proc("x", 42), ShowList(@list)), ShowList(@out))); } $txt .= ShowLine(Op2("define", "crunch", ProcMultiple(["p", "lst"], Op("if", Op2(">=", Op1("list-length", Ref("lst")), 2), Apply("p", Op1("head",Ref("lst")), Op("crunch", Ref("p"), Op1("tail",Ref("lst")))), Op("if", Op2("=", Op1("list-length", Ref("lst")), 1), Op1("head",Ref("lst")), Ref("undefined")))))); for (my $i=0; $i<4; $i++) { my @list = prand(20,$i+3); my @out = (); my $sum = 0; foreach my $n (@list) { $sum += $n; } $txt .= ShowLine(Op2("=", Op("crunch", Ref("+"), ShowList(@list)), $sum)); } return $txt; }; sub ShowMultipleParameterLesson { my $txt = ""; $txt .= "# MATH build up functions of several variables\n"; for (my $i=0; $i<5; $i++) { my $r2 = irand(10); my $r1 = irand(10)+$r2; $txt .= ShowLine(Op2("=", Apply(Proc("x", Proc("y", Op2("-",Ref("x"),Ref("y")))), $r1, $r2), Num($r1-$r2))); } $txt .= ShowLine(Op2("define", "last", Proc("x", Op2("list-ref", Ref("x"), Op2("-", Op1("list-length",Ref("x")), 1))))); $txt .= ShowLine(Op2("define", "except-last", Proc("x", Op("if", Op2(">", Op1("list-length",Ref("x")), 1), Op2("prepend", Op1("head", Ref("x")), Op1("except-last", Op1("tail", Ref("x")))), Op("vector"))))); $txt .= "# test last and except-last\n"; $txt .= ShowLine(Op2("=", 15, Op1("last", Op("vector", 4, 5, 15)))); $txt .= ShowLine(Op2("list=", Op("vector", 4, 5), Op1("except-last", Op("vector", 4, 5, 15)))); $txt .= ShowLine(Op1("intro", "lambda")); $txt .= ShowLine(Op2("define", "prev-translate", Ref("translate"))); $txt .= ShowLine(Op2("define", "translate", Op("let", Paren(Paren("prev",Ref("prev-translate"))), Proc("x", Op("if", Op1("number?", Ref("x")), Op1("prev", Ref("x")), Op("if", Op2("=", Op1("head",Ref("x")), "lambda"), Op("let", Paren(Paren("formals", Op1("head", Op1("tail", Ref("x")))), Paren("body", Op1("head", Op1("tail", Op1("tail", Ref("x")))))), Op("if", Op2(">", Op1("list-length", Ref("formals")), 0), Op("translate", Op("vector", "lambda", Op1("except-last", Ref("formals")), Op("vector", "?", Op1("last",Ref("formals")), Ref("body")))), Op("translate", Ref("body")))), Op1("prev", Ref("x")))))))); $txt .= "# test lambda\n"; $txt .= ShowLine(Op2("=", Proc("x", Op2("-",Ref("x"),5)), ProcMultiple(["x"], Op2("-",Ref("x"),5)))); $txt .= ShowLine(Op2("=", Proc("x", Proc("y", Op2("-",Ref("x"),Ref("y")))), ProcMultiple(["x", "y"], Op2("-",Ref("x"),Ref("y"))))); for (my $i=0; $i<5; $i++) { my $r2 = irand(10); my $r1 = irand(10)+$r2; $txt .= ShowLine(Op2("=", Apply(ProcMultiple(["x","y"], Op2("-",Ref("x"),Ref("y"))), $r1, $r2), Num($r1-$r2))); } $txt .= ShowLine(Op2("define", "apply", ProcMultiple(["x","y"], Op("if", Op2("list=", Ref("y"), Op("vector")), Ref("x"), Op2("apply", Apply(Ref("x"), Op1("head", Ref("y"))), Op1("tail", Ref("y"))))))); for (my $i=0; $i<5; $i++) { my $r2 = irand(10); my $r1 = irand(10)+$r2; $txt .= ShowLine(Op2("=", Op2("apply", ProcMultiple(["x","y"], Op2("-",Ref("x"),Ref("y"))), ShowList( $r1, $r2)), Num($r1-$r2))); } return $txt; }; sub ShowHashLesson { my $txt = ""; $txt .= "# MATH introduce environment/hashmap structure\n"; $txt .= "# this section needs a LOT more examples :-)\n"; $txt .= "# note that at the time of writing (h 1 2) is same as ((h) 1 2)\n"; $txt .= ShowLine(Op2("define", "hash-add", ProcMultiple(["h","x","y","z"], Op("if", Op2("=",Ref("z"),Ref("x")), Ref("y"), Op("h", Ref("z")))))); $txt .= ShowLine(Op2("define", "hash-ref", ProcMultiple(["h","x"], Op("h", Ref("x"))))); $txt .= ShowLine(Op2("define", "hash-null", Proc("x",Ref("undefined")))); $txt .= ShowLine(Op2("define", "test-hash", Op("hash-add", Op("hash-add", Ref("hash-null"), 3, 2), 4, 9))); $txt .= ShowLine(Op2("=", Op("hash-ref", Ref("test-hash"), 4), 9)); $txt .= ShowLine(Op2("=", Op("hash-ref", Ref("test-hash"), 3), 2)); $txt .= ShowLine(Op2("=", Op("hash-ref", Ref("test-hash"), 8), Ref("undefined"))); $txt .= ShowLine(Op2("=", Op("hash-ref", Ref("test-hash"), 15), Ref("undefined"))); $txt .= ShowLine(Op2("=", Op("hash-ref", Op("hash-add", Ref("test-hash"), 15, 33), 15), 33)); $txt .= ShowLine(Op2("=", Op("hash-ref", Ref("test-hash"), 15), Ref("undefined"))); $txt .= ShowLine(Op2("define", "make-hash", Proc("x", Op("if", Op2("list=",Ref("x"),Op("vector")), Ref("hash-null"), Op("hash-add", Op("make-hash", Op1("tail", Ref("x"))), Op1("first",Op1("head",Ref("x"))), Op1("second",Op1("head",Ref("x")))))))); $txt .= ShowLine(Op2("=", Op2("hash-ref", Op1("make-hash", Op("vector", Op2("pair", 3, 10), Op2("pair", 2, 20), Op2("pair", 1, 30))), 3), 10)); $txt .= ShowLine(Op2("=", Op2("hash-ref", Op1("make-hash", Op("vector", Op2("pair", 3, 10), Op2("pair", 2, 20), Op2("pair", 1, 30))), 1), 30)); return $txt; }; sub ShowMutableLesson { my $txt = ""; $txt .= "# MATH introduce mutable objects, and side-effects\n"; $txt .= ShowLine(Op("intro","make-cell")); $txt .= ShowLine(Op("intro","set!")); $txt .= ShowLine(Op("intro","get!")); $txt .= ShowLine(Op("define", "demo-mut1", Op("make-cell", 0))); $txt .= ShowLine(Op2("set!", Ref("demo-mut1"), 15)); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut1")), 15)); $txt .= ShowLine(Op2("set!", Ref("demo-mut1"), 5)); $txt .= ShowLine(Op2("set!", Ref("demo-mut1"), 7)); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut1")), 7)); $txt .= ShowLine(Op("define", "demo-mut2", Op("make-cell", 11))); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut2")), 11)); $txt .= ShowLine(Op2("set!", Ref("demo-mut2"), 22)); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut2")), 22)); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut1")), 7)); $txt .= ShowLine(Op2("=", Op2("+", Op1("get!", Ref("demo-mut1")), Op1("get!", Ref("demo-mut2"))), 29)); $txt .= ShowLine(Op("if", Op("=", Op1("get!", Ref("demo-mut1")), 7), Op2("set!", Ref("demo-mut1"), 88), Op2("set!", Ref("demo-mut1"), 99))); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut1")), 88)); $txt .= ShowLine(Op("if", Op("=", Op1("get!", Ref("demo-mut1")), 7), Op2("set!", Ref("demo-mut1"), 88), Op2("set!", Ref("demo-mut1"), 99))); $txt .= ShowLine(Op2("=", Op1("get!", Ref("demo-mut1")), 99)); $txt .= "# MATH show how to execute a sequence of instructions\n"; $txt .= ShowLine(Op1("intro","begin")); $txt .= ShowLine(Op2("define", "prev-translate", Ref("translate"))); $txt .= ShowLine(Op2("define", "reverse", Proc("x", Op("if", Op2(">=", Op1("list-length",Ref("x")),1), Op2("prepend", Op1("last",Ref("x")), Op1("reverse",Op1("except-last",Ref("x")))), Ref("x"))))); $txt .= "# test reverse\n"; $txt .= ShowLine(Op2("list=", ShowList(1,2,3), Op1("reverse", ShowList(3,2,1)))); $txt .= ShowLine(Op2("define", "translate", Op("let", Paren(Paren("prev",Ref("prev-translate"))), Proc("x", Op("if", Op1("number?", Ref("x")), Op1("prev", Ref("x")), Op("if", Op2("=", Op1("head",Ref("x")), "begin"), Op("translate", Op("vector", Op("vector", "?", "x", Op("vector", "head", Op("vector", "x"))), Op("prepend", "vector", Op1("reverse",Op1("tail",Ref("x")))))), Op1("prev", Ref("x")))))))); $txt .= ShowLine(Op2("=", Op("begin", 1, 7, 2, 4), 4)); $txt .= ShowLine(Op2("=", Op("begin", Op2("set!", Ref("demo-mut1"), 88), Op2("set!", Ref("demo-mut1"), 6), Op1("get!", Ref("demo-mut1"))), 6)); $txt .= ShowLine(Op2("=", Op("begin", Op2("set!", Ref("demo-mut2"), 88), Op2("set!", Ref("demo-mut1"), 6), Op1("get!", Ref("demo-mut2"))), 88)); $txt .= ShowLine(Op2("=", Op("begin", Op2("set!", Ref("demo-mut1"), 88), Op2("set!", Ref("demo-mut1"), 6), Op1("get!", Ref("demo-mut1")), 4), 4)); return $txt; }; sub ShowGraphLesson { my $txt = ""; $txt .= "# MATH introduce graph structures\n"; $txt .= ShowLine(Op2("define", "make-graph", ProcMultiple(["nodes", "links"], Op2("pair", Ref("nodes"), Ref("links"))))); $txt .= ShowLine(Op2("define", "test-graph", Op("make-graph", ShowList("1", "2", "3", "4"), ShowList(ShowList("1", "2"), ShowList("2", "3"), ShowList("1", "4"))))); $txt .= ShowLine(Op2("define", "graph-linked", ProcMultiple(["g", "n1", "n2"], Op1("exists", Proc("idx", Op("if", Op2("and", Op2(">=", Ref("idx"), 0), Op2("<", Ref("idx"), Op1("list-length", Op2("list-ref", Ref("g"), 1)))), Op2("list=", Op2("list-ref", Op2("list-ref", Ref("g"), 1), Ref("idx")), ShowList(Ref("n1"), Ref("n2"))), Ref("false"))))))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "1", "2"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "1", "3"), Op("false"))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "2", "4"), Op("false"))); $txt .= "# 'if' is used a lot in the next definition in place of and/or\n"; $txt .= "# this is because I haven't established lazy evaluation forms for and/or\n"; $txt .= "# so this very inefficient algorithm completely bogs down when combined\n"; $txt .= "# ... during testing with a dumb implementation for 'exists'.\n"; $txt .= ShowLine(Op2("define", "graph-linked*", ProcMultiple(["g", "n1", "n2"], Op("if", Op2("=", Ref("n1"), Ref("n2")), Ref("true"), Op("if", Op("graph-linked", Ref("g"), Ref("n1"), Ref("n2")), Ref("true"), Op("exists", Proc("n3", Op("if", Op("graph-linked", Ref("g"), Ref("n1"), Ref("n3")), Op("graph-linked*", Ref("g"), Ref("n3"), Ref("n2")), Ref("false"))))))))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "1", "2"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "1", "3"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "2", "4"), Op("false"))); return $txt; }; sub ShowTypedGraphLesson { my $txt = ""; $txt .= "# MATH introduce graph structures\n"; $txt .= "# really need some type templating - will define this later\n"; $txt .= "# type system needs a little bit of dis-ambiguating!\n"; $txt .= ShowLine(Op1("pending", "template")); $txt .= ShowLine(Op2("define", "tuple", Template(["T"], ProcTyped(["lst", Op("listof", Ref("T"))], Op("type", Op("tupleof", Ref("T"), Op1("list-length", Ref("lst"))), Ref("lst")))))); $txt .= ShowLine(Op2("define", "tuple-ref", Template(["T", "len"], ProcTyped(["x", Op("tupleof", Ref("T"), Ref("len")), "y", "integer"], Op("list-ref", Op("get-raw", Ref("x")), Op("get-raw", Ref("y"))))))); $txt .= ShowLine("define", "make-graph", ProcTyped(["nodes", Op("listof", "integer"), "links", Op("listof", Op("tupleof", "integer", 2))], Op2("type", "graph", Op1("tuple", Op("list", Ref("nodes"), Ref("links")))))); $txt .= ShowLine(Op2("define", "test-graph", Op("make-graph", ShowList("g1", "g2", "g3", "g4"), Op("list", Op("tuple", ShowList("g1", "g2")), Op("tuple", ShowList("g2", "g3")), Op("tuple", ShowList("g1", "g4")))))); $txt .= ShowLine(Op2("define", "graph-linked", ProcTyped(["g", "graph", "n1", "integer", "n2", "integer"], Op1("exists", Proc("idx", Op2("=", Op2("tuple-ref", Op2("tuple-ref", Ref("g"), 1), Ref("idx")), Op1("tuple", Op("list", Ref("n1"), Ref("n2"))))))))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "g1", "g2"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "g1", "g3"), Op("false"))); $txt .= ShowLine(Op2("=", Op("graph-linked", Ref("test-graph"), "g2", "g4"), Op("false"))); $txt .= ShowLine(Op2("define", "graph-linked*", ProcMultiple(["g", "n1", "n2"], Op2("or", Op2("=", Ref("n1"), Ref("n2")), Op2("or", Op("graph-linked", Ref("g"), Ref("n1"), Ref("n2")), Op("exists", Proc("n3", Op2("and", Op("graph-linked", Ref("g"), Ref("n1"), Ref("n3")), Op("graph-linked*", Ref("g"), Ref("n3"), Ref("n2")))))))))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "g1", "g2"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "g1", "g3"), Op("true"))); $txt .= ShowLine(Op2("=", Op("graph-linked*", Ref("test-graph"), "g2", "g4"), Op("false"))); return $txt; }; sub ShowTypeLesson { my $txt = ""; $txt .= "# MATH introduce a basic type system\n"; $txt .= "# not really sure how this is going to work out\n"; $txt .= "# need to implement domain constructors T+T / T*T / T->T / etc\n"; $txt .= ShowLine(Op1("intro", "type")); $txt .= ShowLine(Op2("define", "typed", Proc("x", Apply(Op("match", "e", Op("list", Op2("pair", Op2("element", Ref("e"), Ref("natural-set")), Op2("pair","integer",Ref("e"))), Op2("pair", Op2("element", Ref("e"), Ref("boolean-set")), Op2("pair","boolean",Ref("e"))), Proc("T", Op2("pair", Op2("=", Op1("first", Ref("e")), Op1("type", Ref("T"))), Op2("pair", Ref("T"), Op1("second",Ref("e"))))), Proc("T", Op2("pair", Op("crunch", "and", Op("prepend", Op1("is-list", Ref("e")), Op2("map", Proc("x", (Op2("=", Op1("first", Op1("typed", Ref("x"))), Ref("T")))), Ref("e")))), Op2("pair", Op("listof", Ref("T")), Ref("e")))), Op2("pair", Op1("is-list",Ref("e")), Op2("pair", Op("listof", "unknown"), Ref("e"))), Op2("pair", Ref("true"), Op2("pair", Ref("undefined"), Ref("e"))))), Ref("x"))))); $txt .= ShowLine(Op2("define", "get-type", Proc("x", Op1("first", Op1("typed",Ref("x")))))); $txt .= ShowLine(Op2("define", "get-raw", Proc("x", Op1("second", Op1("typed",Ref("x")))))); for (my $i=0; $i<5; $i++) { $txt .= ShowLine(Op2("=", Op1("get-type", irand(20)), "integer")); } $txt .= ShowLine(Op1("forall", Proc("x", Op2("=>", Op2("element", Ref("x"), Ref("natural-set")), Op2("=", Op1("get-type", Ref("x")), "integer"))))); $txt .= ShowLine(Op2("=", Op1("get-type",Ref("true")), "boolean")); $txt .= ShowLine(Op2("=", Op1("get-type",Ref("false")), "boolean")); $txt .= ShowLine(Op2("=", Op1("get-type",ShowList(1, 4, 5)), Op1("listof", "integer"))); $txt .= ShowLine(Op2("=", Op1("get-type",ShowList(Ref("true"), Ref("true"), Ref("false"))), Op1("listof", "boolean"))); $txt .= "# don't think I deal adequately with empty list at the moment\n"; for (my $i=0; $i<3; $i++) { my $r = irand(20); $txt .= ShowLine(Op2("=", Op1("typed", $r), Op2("type", "integer", $r))); } for (my $i=0; $i<3; $i++) { my $r = irand(20); $txt .= ShowLine(Op2("=", Op1("typed", Op2("type", "integer", $r)), Op2("type", "integer", $r))); } $txt .= ShowLine(Op1("forall", Proc("x", Op1("forall", Proc("y", Op2("=>", Op2("and", Op2("=", Op1("get-type",Ref("x")), "integer"), Op2("=", Op1("get-type",Ref("y")), "integer")), Op2("=", Op2("+", Ref("x"), Ref("y")), Op2("+", Op1("get-raw", Ref("x")), Op1("get-raw", Ref("y")))))))))); $txt .= ShowLine(Op2("=", Op2("+", Op2("type", "integer", 5), Op2("type", "integer", 10)), 15)); $txt .= ShowLine(Op2("define", "type-compatible-integer-primop", Proc("op", Op1("forall", Proc("x", Op1("forall", Proc("y", Op2("=>", Op2("and", Op2("=", Op1("get-type",Ref("x")), "integer"), Op2("=", Op1("get-type",Ref("y")), "integer")), Op2("=", Op2("op", Ref("x"), Ref("y")), Op2("op", Op1("get-raw", Ref("x")), Op1("get-raw", Ref("y")))))))))))); $txt .= ShowLine(Op1("type-compatible-integer-primop", "+")); $txt .= ShowLine(Op1("type-compatible-integer-primop", "*")); $txt .= ShowLine(Op1("type-compatible-integer-primop", "-")); $txt .= ShowLine(Op1("type-compatible-integer-primop", "=")); $txt .= "# note constraint to integers for now\n"; $txt .= ShowLine(Op2("=", Op2("type", "integer", 5), 5)); $txt .= "# There is a lot to add here to layer types over existing infrastructure.\n"; $txt .= "# Let's just pretend it is here and doesn't involve any serious contradictions!\n"; $txt .= "# give a typed version of lambda by example - really need to define this!\n"; $txt .= ShowLine(Op2("=", ProcTyped(["x", "integer", "y", "boolean"], Op("if", Ref("y"), Ref("x"), 0)), ProcMultiple(["x", "y"], Op("if", Op2("and", Op2("=", Op1("get-type", Ref("x")), "integer"), Op2("=", Op1("get-type", Ref("y")), "boolean")), Op("if", Ref("y"), Ref("x"), 0), Ref("undefined"))))); # (lambda ((x T1) (y T2)) (app T1 T2)) return $txt; }; sub ShowMutableStructureLesson { my $txt = ""; $txt .= "# OBJECT introduce simple mutable structures\n"; $txt .= ShowLine(Op2("define", "mutable-struct", Proc("lst", Op("let", Paren(Paren("data", Op2("map", Proc("x", Op1("make-cell", 0)), Ref("lst")))), Proc("key", Op("list-ref", Ref("data"), Op("list-find", Ref("lst"), Ref("key"), Proc("x", 0)))))))); $txt .= ShowLine(Op2("define", "test-struct1", Op1("mutable-struct", ShowList("item1", "item2", "item3")))); $txt .= ShowLine(Op2("set!", Op("test-struct1", "item1"), 15)); $txt .= ShowLine(Op2("=", Op1("get!", Op("test-struct1", "item1")), 15)); return $txt; }; sub ShowMethodLesson { my $txt = ""; $txt .= "# OBJECT introduce method handler wrappers\n"; $txt .= ShowLine(Op2("define", "add-method", ProcMultiple(["object","name","method"], Op("hash-add", Ref("object"), Ref("name"), Proc("dummy", Op1("method",Ref("object"))))))); $txt .= ShowLine(Op2("define", "call", Proc("x", Op("x", 0)))); # $txt .= ShowLine(Op2("define", # "mutable-struct", # Proc("lst", # Op("let", # Paren(Paren("data", # Op2("map", # Proc("x", # Op1("make-cell", 0)), # Ref("lst")))), # Proc("key", # Op("list-ref", # Ref("data"), # Op("find-list", # Ref("lst"), # Ref("key")))))))); $txt .= ShowLine(Op2("define", "test-struct2", Op1("mutable-struct", ShowList("x", "y")))); $txt .= ShowLine(Op2("set!", Op("test-struct2", "x"), 10)); $txt .= ShowLine(Op2("set!", Op("test-struct2", "y"), 20)); $txt .= ShowLine(Op2("=", Op1("get!", Op("test-struct2", "x")), 10)); $txt .= ShowLine(Op2("=", Op1("get!", Op("test-struct2", "y")), 20)); $txt .= ShowLine(Op2("define", "test-struct3", Op("add-method", Ref("test-struct2"), "sum", Proc("self", Op2("+", Op1("get!",Op("self","x")), Op1("get!",Op("self","y"))))))); $txt .= ShowLine(Op2("=", Op1("get!", Op("test-struct3", "x")), 10)); $txt .= ShowLine(Op2("=", Op1("get!", Op("test-struct3", "y")), 20)); $txt .= ShowLine(Op2("=", Op1("call",Op("test-struct3", "sum")), 30)); $txt .= ShowLine(Op2("set!", Op("test-struct3", "y"), 10)); $txt .= ShowLine(Op2("=", Op1("call",Op("test-struct3", "sum")), 20)); $txt .= ShowLine(Op2("set!", Op("test-struct2", "y"), 5)); $txt .= ShowLine(Op2("=", Op1("call",Op("test-struct3", "sum")), 15)); return $txt; } sub ShowTuringLesson { my $txt .= "# TURING introduce turing machine model\n"; $txt .= "# just for fun!\n"; $txt .= ShowLine(Op2("define", "safe-tail", Proc("x", Op("if", Op2(">", Op1("list-length",Ref("x")), 0), Op("if", Op2(">", Op1("list-length",Ref("x")), 1), Op1("tail",Ref("x")), Op1("vector",Ref("false"))), Proc("vector", Ref("false")))))); $txt .= ShowLine(Op2("define", "safe-head", Proc("x", Op("if", Op2(">", Op1("list-length",Ref("x")), 0), Op1("head",Ref("x")), Ref("false"))))); $txt .= ShowLine(Op2("define", "tape-read", Proc("tape", Op("let", Paren(Paren("x", Op1("second",Ref("tape")))), Op("if", Op2(">", Op1("list-length",Ref("x")), 0), Op1("head",Ref("x")), Ref("false")))))); $txt .= ShowLine(Op2("define", "tape-transition", ProcMultiple(["tape","shift","value"], Op("if", Op2("=", Ref("shift"), 1), Op2("pair", Op2("prepend", Ref("value"), Op1("first",Ref("tape"))), Op1("safe-tail", Op1("second",Ref("tape")))), Op("if", Op2("=", Ref("shift"), 0), Op2("pair", Op1("safe-tail", Op1("first",Ref("tape"))), Op2("prepend", Op1("safe-head", Op1("first", Ref("tape"))), Op2("prepend", Ref("value"), Op1("safe-tail", Op1("second", Ref("tape")))))), Op2("pair", Op1("first",Ref("tape")), Op2("prepend", Ref("value"), Op1("safe-tail", Op1("second", Ref("tape")))))))))); # $txt .= ShowLine(Op("tape-read", # Ref("test-tape"))); # $txt .= " #(tape-read (tape-transition (test-tape) 1 88)); #(tape-read (tape-transition (tape-transition (test-tape) 1 88) 0 44)); #(tape-read (tape-transition (tape-transition (tape-transition (test-tape) 1 88) 0 44) 1 16)); #"; # $txt .= "(garble)\n"; $txt .= ShowLine(Op2("define", "turing", ProcMultiple(["machine", "current", "last", "tape"], Op("if", Op2("=",Ref("current"),Ref("last")), Ref("tape"), Op("let", Paren(Paren("next", Op("machine", Ref("current"), Op1("tape-read", Ref("tape"))))), Op("turing", Ref("machine"), Op2("list-ref", Ref("next"), 0), Ref("last"), Op("tape-transition", Ref("tape"), Op2("list-ref", Ref("next"), 1), Op2("list-ref", Ref("next"), 2)))))))); $txt .= ShowLine(Op2("define", "make-tape", Proc("x", Op2("pair", Op("vector"), Ref("x"))))); $txt .= ShowLine(Op2("define", "remove-trail", Proc("x", Proc("lst", Op("if", Op2(">", Op1("list-length",Ref("lst")), 0), Op("if", Op2("=", Op1("last",Ref("lst")), Ref("x")), Op2("remove-trail", Ref("x"), Op1("except-last", Ref("lst"))), Ref("lst")), Ref("lst")))))); $txt .= ShowLine(Op2("define", "extract-tape", Proc("x", Op2("remove-trail", Ref("false"), Op1("second", Ref("x")))))); $txt .= ShowLine(Op2("define", "tm-binary-increment", Op1("make-hash", ShowList(Op2("pair", "right", Op1("make-hash", ShowList(Op2("pair", 0, ShowList("right",1,0)), Op2("pair", 1, ShowList("right",1,1)), Op2("pair", Ref("false"), ShowList("inc",0,Ref("false")))))), Op2("pair", "inc", Op1("make-hash", ShowList(Op2("pair", 0, ShowList("noinc",0,1)), Op2("pair", 1, ShowList("inc",0,0)), Op2("pair", Ref("false"), ShowList("halt",2,1))))), Op2("pair", "noinc", Op1("make-hash", ShowList(Op2("pair", 0, ShowList("noinc",0,0)), Op2("pair", 1, ShowList("noinc",0,1)), Op2("pair", Ref("false"), ShowList("halt",1,Ref("false")))))), Op2("pair", "halt", Op1("make-hash", ShowList())))))); $txt .= ShowLine(Op2("=", Op1("extract-tape", Op("turing", Ref("tm-binary-increment"), "right", "halt", Op1("make-tape", ShowList(1,0,0,1)))), ShowList(1,0,1,0))); $txt .= ShowLine(Op2("=", Op1("extract-tape", Op("turing", Ref("tm-binary-increment"), "right", "halt", Op1("make-tape", ShowList(1,1,1)))), ShowList(1,0,0,0))); $txt .= ShowLine(Op2("=", Op1("extract-tape", Op("turing", Ref("tm-binary-increment"), "right", "halt", Op1("make-tape", ShowList(1,1,1,0,0,0,1,1,1)))), ShowList(1,1,1,0,0,1,0,0,0))); return $txt; } sub ShowAssertLesson { my $txt .= ""; $txt .= "# LOGIC simple logical assertions\n"; $txt .= ShowLine(Op2("define", "assert", Proc("context", Proc("x", Op2("prepend", Ref("x"), Ref("context")))))); $txt .= ShowLine(Op2("define", "assert!", Proc("context", Proc("x", Op2("set!", Ref("context"), Op2("assert", Ref("context"), Ref("x"))))))); # $txt .= ShowLine(Op2("define", # "match-assert", # Proc("context", # Proc $txt .= ShowLine(Op2("define", "my-env", Op1("make-cell", Ref("empty-list")))); } sub ShowMatchLesson { my $txt .= ""; $txt .= "# MATH show a very very weak pattern matching mechanism\n"; $txt .= "# just by example, not definition, for now\n"; $txt .= "# it is a bit subtle to be relying on examples only.\n"; $txt .= "# especially as few as there are right now.\n"; $txt .= "# and really this isn't pattern matching at all yet...\n"; $txt .= "# ...basically this section is way underdeveloped\n"; $txt .= ShowLine(Op1("intro", "match")); # $txt .= ShowLine(Op2("define", # "match", # Proc( $txt .= ShowLine(Op2("=", Apply(Op("match", "x", Op2("pair", Op("true"), 2), Op2("pair", Op("false"), 3), Op2("pair", Op("true"), Ref("x"))), 42), 2)); $txt .= ShowLine(Op2("=", Apply(Op("match", "x", Op2("pair", Op("false"), 3), Op2("pair", Op("true"), Ref("x")), Op2("pair", Op("true"), 2)), 42), 42)); $txt .= ShowLine(Op2("=", Apply(Op("match", "x", Op2("pair", Op("true"), 2), Op2("pair", Op("false"), 3), Op2("pair", Op("true"), 4)), 42), 2)); $txt .= ShowLine(Op2("=", Apply(Op("match", "x", Op2("pair", Op("false"), 3), Op2("pair", Op("true"), 4), Op2("pair", Op("true"), 2)), 42), 4)); $txt .= ShowLine(Op2("define", "test-match1", Op("match", "x", Op2("pair", Op2("=", Ref("x"), 42), 10), Proc("y", Op2("pair", Op2("and", Op2("=", Ref("x"), Op2("*", Ref("y"), 2)), Op2("element", Ref("y"), Ref("natural-set"))), Ref("y"))), Op2("pair", Op("true"), 3)))); $txt .= ShowLine(Op2("=", Op("test-match1", 42), 10)); $txt .= ShowLine(Op2("=", Op("test-match1", 100), 50)); $txt .= ShowLine(Op2("=", Op("test-match1", 30), 15)); $txt .= ShowLine(Op2("=", Op("test-match1", 33), 3)); $txt .= ShowLine(Op2("=", Op("test-match1", 39), 3)); return $txt; }; sub ShowPlayLesson { my $txt = ""; $txt .= "# TEST try out new expressions -- development area\n"; $txt .= "# pending - need to build up a clear object model\n"; return $txt; }; sub Get { my $cell = shift; return Op1("get!",Ref($cell)); }; sub ShowMUDLesson { my $txt = ""; $txt .= "# MUD under development\n"; $txt .= "# currently just use this section to play around\n"; $txt .= ShowLine(Op1("pending", "thing")); $txt .= ShowLine(Op2("define", "make-mud", ProcTyped(["g", "graph", "t", "thing"], Let(["self", Op1("make-cell", Op1("mutable-struct", ShowList("map", "stuff")))], Op("begin", Op2("set!", Op(Get("self"), "map"), Ref("g")), Op2("set!", Op(Get("self"), "stuff"), Ref("t")), Op2("set!", Ref("self"), Op("add-method", Get("self"), "get42", Proc("this", 42))), Get("self")))))); $txt .= ShowLine(Op2("define", "tpair", ProcMultiple(["x","y"], Op("tuple", ShowList( Ref("x"), Ref("y")))))); $txt .= ShowLine(Op1("pending", "make-undirected-graph")); $txt .= "# the following map is not at all accurate!\n"; $txt .= "# just something arbitrary to play with\n"; $txt .= "# remember that none of the semantic info in names is captured in the message\n"; $txt .= ShowLine(Op2("define", "cambridge-map", Op("make-undirected-graph", ShowList( "mit-lobby-7", "mit-lobby-10", "mit-killian-court", "mit-student-center", "mit-26-100", "mit-stata", "mit-tech-square", "mit-ashdown", "mit-green", "mit-media", "mit-medical", "mit-kendall-tstop", "mit-coop", "central-tstop", "harvard-tstop", "harvard-coop"), Op("list", Op2("tpair", "mit-lobby-7", "mit-lobby-10"), Op2("tpair", "mit-lobby-7", "mit-student-center"), Op2("tpair", "mit-student-center", "mit-ashdown"), Op2("tpair", "mit-ashdown", "mit-lobby-7"), Op2("tpair", "mit-lobby-10", "mit-killian-court"), Op2("tpair", "mit-lobby-10", "mit-26-100"), Op2("tpair", "mit-26-100", "mit-green"), Op2("tpair", "mit-green", "mit-media"), Op2("tpair", "mit-media", "mit-medical"), Op2("tpair", "mit-medical", "mit-kendall-tstop"), Op2("tpair", "mit-kendall-tstop", "mit-coop"), Op2("tpair", "mit-kendall-tstop","central-tstop"), Op2("tpair", "central-tstop", "harvard-tstop"), Op2("tpair", "harvard-tstop", "harvard-coop"))))); $txt .= "# changed my mind, let us try a different approach\n"; return $txt; }; sub ReadLesson { my $fname = shift; my @lines = (); open (FIN,"<$fname"); while() { chomp; push(@lines,$_); } close(FIN); my $txt = "\n" . join("\n",@lines); while ($txt =~ /\n(\([^\;\n]*\n[^\;]*\;)/) { my $src = $1; # print $src, "\n"; my $qsrc = quotemeta($src); my $dest = $src; $dest =~ s/[\n\r]/ /g; $txt =~ s/\n$qsrc/\n$dest/; } return $txt; } sub ShowNewTypeLesson { my $txt = ReadLesson("lesson-type.scm"); return $txt; } # generate message # use consistent random choices # (really not acceptable to use random numbers, should use # look-up tables on a per lesson basis, to ensure stability # of sequences within lessons) srand(1); my $txt = ""; $txt .= "# Author: Paul Fitzpatrick, paulfitz\@ai.mit.edu # Copyright (c) 2003 Paul Fitzpatrick # # This file is part of CosmicOS. # # CosmicOS is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # CosmicOS is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with CosmicOS; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA # "; $txt .= ShowUnaryLesson(); $txt .= ShowNotLogicLesson(); $txt .= ShowAndLogicLesson(); $txt .= ShowOrLogicLesson(); $txt .= ShowTrueFalseLesson(); $txt .= ShowAdditionLesson(); $txt .= ShowSubtractionLesson(); $txt .= ShowMultiplicationLesson(); #$txt .= ShowDoubleLesson(); $txt .= ShowBinaryLesson(); $txt .= ShowEvaluationLesson(); $txt .= ShowDefineFunctionLesson(); $txt .= ShowIfLesson(); $txt .= ShowRecursionLesson(); $txt .= ShowQuantifierLesson(); $txt .= ShowImplicationLesson(); $txt .= ShowListLesson(); $txt .= ShowLetLesson(); $txt .= ShowMultipleParameterLesson(); $txt .= ShowMapLesson(); $txt .= ShowMutableLesson(); $txt .= ShowHashLesson(); $txt .= ShowMutableStructureLesson(); $txt .= ShowMethodLesson(); $txt .= ShowTuringLesson(); $txt .= ShowSetLesson(); $txt .= ShowGraphLesson(); $txt .= ShowNewTypeLesson(); #$txt .= ShowAssertLesson(); #$txt .= ShowMatchLesson(); #$txt .= ShowTypeLesson(); #$txt .= ShowPlayLesson(); #$txt .= ShowMUDLesson(); # Establish some terms which will have a fairly short representation. # Identifying numbers are allocated on a first come first served basis. Text2Tokens("? intro ref = < > not and or true false x y z => exists forall cell set get if <= >="); #$txt = "[5 6 7 [1 1] [2 2 2]]"; my @inter = Text2Tokens($txt); my $msg = Tokens2Msg(@inter); #$msg =~ s/\n//g; #$msg =~ s/([a-z0-9]{80})/$1\n*** /g; #print "*** $msg\n"; print "$txt\n\n"; #print join(" ",@inter); # can call Decompile to make sure everything is getting put in # the final message #print "\n***DECOMPILING***\n"; #print Decompile($msg);