%% IRCAM Presentation %%%%%%%%%%%

% Demonstration code

% Peter Van Roy
% May 12, 2006

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Symbolic data structures

% Lists
declare L1 L2 L3 L4 in
L1=nil
L2=john|nil
L3=john|(paul|nil)
L4=john|(paul|(george|(ringo|nil)))

{Browse L2}

declare L1 L2 in
L1=john|paul|george|ringo|nil
L2=[john paul george ringo]

{Browse L1==L2}

% Records
declare
R=suit(shirt:beige pants:ochre socks:coral)

{Browse R.shirt}
{Browse {Label R}}
{Browse {Arity R}}
{Browse {Width R}}

declare
R2={AdjoinAt R shirt mauve}
{Browse R2}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Functional programming

% Simple factorial function
declare
fun {Fact N}
   if N==0 then 1 else N*{Fact N-1} end
end

% Combinations: "N choose K"
% Number of combinations of N objects
% chosen K at a time
declare
fun {Comb N K}
   {Fact N} div ({Fact K} * {Fact N-K})
end

% Number of different poker hands:
{Browse {Comb 52 5}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Pattern matching

declare
fun {SumList L}
   case L
   of nil then 0
   [] H|T then H+{SumList T}
   end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Higher-order programming

declare
Add=fun{$ X Y} X+Y end

declare
fun {MakeAdder N}
   fun {$ X} N+X end
end
Add1={MakeAdder 1}

declare
fun {MakeOneArg F N}
   fun {$ X} {F N X} end
end
Add1={MakeOneArg fun {$ X Y} X+Y end 1}

{Browse {Add1 100}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Generic programming

declare
fun {SumList L}
   case L of nil then 0
   [] H|T then H+{SumList T} end
end

declare
fun {FoldR L F U}
   case L of nil then U
   [] H|T then {F H {FoldR T F U}} end
end

declare
fun {SumList2 L} {FoldR L fun {$ X Y} X+Y end 0} end
fun {ProdList L} {FoldR L fun {$ X Y} X*Y end 1} end
fun {Some L}
   {FoldR L fun {$ X Y} X orelse Y end false} end
fun {All L}
   {FoldR L fun {$ X Y} X andthen Y end true} end

{Browse {Some [false true false]}}
{Browse {All  [false true false]}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Dataflow variables

declare X in
{Browse X}

X=100

% Data structures with holes
declare X K V L R in
X=tree(K V L R)
{Browse X}

K=dog V=chien
L=tree(cat chat leaf leaf)
R=tree(mouse souris leaf leaf)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Dataflow computation

declare X Y Z in
{Browse start}
thread Z=X+Y {Browse Z} end
thread {Delay 1000} X=25 end
thread {Delay 2000} Y=144 end

declare
fun {Ints N Max}
   if N<Max then
	  {Delay 1000}
	  N|{Ints N+1 Max}
   else nil end
end
fun {Sum S Xs}
   case Xs of X|Xr then
	  S|{Sum S+X Xr}
   [] nil then nil end
end

local Xs Ys in
   thread Xs={Ints 1 1000} end
   thread Ys={Sum 0 Xs} end
   {Browse Ys}
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Concurrency can be cheap

declare
fun {Fibo N}
   {Delay 100}
   if N=<2 then 1
   else thread {Fibo N-1} end + {Fibo N-2}
   end
end

% Open the Oz Panel when executing
{Browse start}
{Browse {Fibo 25}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Sieve of Eratosthenes

declare
fun {Sieve Xs}
   case Xs of nil then nil
   [] X|Xr then Ys in
	  thread Ys={Filter Xr
				 fun {$ Y} Y mod X \= 0 end} end
	  X|{Sieve Ys}
   end
end

% Attention: to get results right away,
% Ints and Sieve must be inside their
% own threads!
local Xs Ys in
   thread Xs={Ints 2 1000} end
   thread Ys={Sieve Xs} end
   {Browse Ys}
end

declare
fun {Sieve2 Xs}
   case Xs of nil then nil
   [] X|Xr then
	  X|{Sieve2
		 thread {Filter Xr
				 fun {$ Y} Y mod X \= 0 end} end}
   end
end

declare
fun {Sieve3 Xs M}
   case Xs of nil then nil
   [] X|Xr then
	  if X=<M then Ys in
		 thread Ys={Filter Xr
					fun {$ Y} Y mod X \= 0 end} end
		 X|{Sieve3 Ys M}
	  else
		 Xs
	  end
   end
end

local Xs Ys in
   thread Xs={Ints 2 1000} end
   thread Ys={Sieve3 Xs 32} end
   {Browse Ys}
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Lazy functions

% Defining a lazy function
declare
fun lazy {Fact N}
   if N==0 then 1 else N*{Fact N-1} end
end

% The 'lazy' annotation is syntactic sugar for this:
declare
proc {Fact N F}
   thread
	  {WaitNeeded F}
	  F=(if N==0 then 1 else N*{Fact N-1} end)
   end
end

declare
F={Fact 100}
{Browse F}

% Trigger the evaluation (F is needed)
declare
Y=F+1

% Lazy stream of factorials
% Each element is calculated just once
declare
fun lazy {Facts F N}
   F|{Facts F*N N+1}
end
FL={Facts 1 2}
{Browse FL}

{Browse {Nth FL 69}} % Get 69th factorial
{Browse {Nth FL 52}} % Get 52nd factorial

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Lazy producer/consumer

declare
fun lazy {Ints N}
   {Delay 1000}
   N|{Ints N+1}
end
fun lazy {Sum S Xs}
   case Xs of X|Xr then
	  S|{Sum S+X Xr}
   [] nil then nil end
end

local Xs Ys in
   thread Xs={Ints 1} end
   thread Ys={Sum 0 Xs} end
   {Browse Ys}
   {Browse {Nth Ys 10}}
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Hamming problem

declare
fun lazy {Times N H}
   case H of X|H2 then
	  N*X|{Times N H2}
   end
end
fun lazy {Merge Xs Ys}
   case Xs#Ys of (X|Xr)#(Y|Yr) then
	  if X<Y then X|{Merge Xr Ys}
	  elseif X>Y then Y|{Merge Xs Yr}
	  else X|{Merge Xr Yr} end
   end
end

% Trace through the execution!
declare
H=1|{Merge {Times 2 H}
	 {Merge {Times 3 H}
	  {Times 5 H}}}

{Browse H}
{Browse {Nth H 10}}
{Browse {Nth H 100}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Message-passing concurrency

% A communication channel
declare S P in
{NewPort S P}
{Browse S}

{Send P alpha}
{Send P beta}

% Defining an agent
declare
fun {NewAgent Init Fun}
   proc {AgentLoop State Msgs}
	  case Msgs of M|Msgs2 then
		 {AgentLoop {Fun State M} Msgs2}
	  [] nil then skip end
   end
   Msgs
in
   thread {AgentLoop Init Msgs} end
   {NewPort Msgs}
end

% Simpler version with FoldL
declare
fun {NewAgent2 Init Fun}
Msgs Out in
   thread {FoldL Msgs Fun Init Out} end
   {NewPort Msgs}
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Multiagent programming

% A player in a ballgame
declare
fun {Player Others}
   {NewAgent state(0 0)
	fun {$ state(M B) Msg}
	   case Msg
	   of ball(N) then
		  Ran={OS.rand} mod {Width Others} + 1
	   in
		  {Send Others.Ran ball(N+1)}
		  state(M+1 N)
	   [] getstate(S) then S=state(M B)
		  state(M B)
	   end
	end}
end

% Define a game with three players
declare P1 P2 P3 in
P1={Player others(P2 P3)}
P2={Player others(P1 P3)}
P3={Player others(P1 P2)}

% Start the game
{Send P1 ball(0)}

% Keep tabs on a player's state
{Browse {Send P1 getstate($)}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Contract net protocol

% Create four sellers for the demonstration
declare
Sellers=[_ _ _ _] % Four sellers
for P in Sellers I in 1..{Length Sellers} do S in
   P={NewPort S}
   thread
	  for M in S do
		 case M of query(Pr) then Pr=I*I-4*I
		 [] accept then {Browse accept(I)}
		 [] cancel then {Browse cancel(I)} end
	  end
   end
end

% The contract net protocol
declare
% Send queries and collect seller/price responses
Rs={Map Sellers fun {$ S} S#{Send S query($)} end}

declare
% Find seller/price pair with lowest price
S1#R1={FoldL Rs.2
	   fun {$ S1#R1 S#R}
		  if R<R1 then S#R else S1#R1 end end Rs.1}

declare
% Send accept to best seller, cancel to others
for S#R in Rs do
   {Send S if S==S1 then accept else cancel end} end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%