From 18bb31418fbd8341728c4ee68bc29a8c15c1874c Mon Sep 17 00:00:00 2001 From: rgrjr Date: Fri, 11 Apr 2008 03:16:10 +0000 Subject: [PATCH] * examples/pir/hanoi.pir: + Improve tower representation, add symbolic names, use lexical scoping more fully, update doc. This now serves as an example of stack ops, and is the only (so far) example of lexical scoping. git-svn-id: https://svn.perl.org/parrot/trunk@26925 d31e2699-5ff4-0310-a27c-f18f2fbe73fe --- examples/pir/hanoi.pir | 475 ++++++++++++++++++++++++------------------------- 1 file changed, 233 insertions(+), 242 deletions(-) rewrite examples/pir/hanoi.pir (70%) diff --git a/examples/pir/hanoi.pir b/examples/pir/hanoi.pir dissimilarity index 70% index dc91466440..0ce285ca9c 100644 --- a/examples/pir/hanoi.pir +++ b/examples/pir/hanoi.pir @@ -1,242 +1,233 @@ -# Copyright (C) 2001-2008, The Perl Foundation. -# $Id$ - -=head1 NAME - -examples/pir/hanoi.pir - Towers of hanoi - -=head1 SYNOPSIS - -You have to pass in the height of the tower: - - % ./parrot examples/pir/hanoi.pir 5 - -=head1 DESCRIPTION - -Towers of Hanoi (http://www.cut-the-knot.org/recurrence/hanoi.shtml) is -a combinatorial puzzle. The PIR shows manipulation of arrays of -integers. - -=head1 Data Structure - -C is a C PMC with three entries. Each entry is a -C PMC which represents a tower (column) of Hanoi. - -The towers are arrays of integers. 0 indicates no disk is present. A -positive integer indicates the diameter of the disk occupying the -indicated slot. - -So this setup - - || || || - ==== || || - ====== || == - -is represented as - - [[0, 2, 3], [0, 0, 0], [0, 0, 1]] - -In pseudocode: - - sub main() { - size = argv[0] - int towers[] = [[], [], []] - towers[0] = [1..size] - towers[1] = [(0) x size] - towers[2] = [(0) x size] - move_stack(towers, size, size, 0, 2, 1) - - sub move_stack(n_to_move, start, target, storage) { - if (n_to_move == 1) { - move(start, target) - } - else { - # Move all but the largest disk to storage. - move_stack(n_to_move-1, start, storage, target) - # Move the largest disk to target. - move(start, target) - # Move all but the largest disk from storage to target. - move_stack(n_to_move-1, storage, target, start) - } - } - - sub move(start, target) { - /* okay, so it's not pseudocode... */ - # find the first non-empty slot on the start column (smallest disk) - for(i=0; i 1 goto move_multiple - MOVE(start_col, target_col) - .return () -move_multiple: - dec n_to_move - MOVE_STACK(n_to_move, start_col, storage_col, target_col) - MOVE(start_col, target_col) - MOVE_STACK(n_to_move, storage_col, target_col, start_col) -.end - -# Local Variables: -# mode: pir -# fill-column: 100 -# End: -# vim: expandtab shiftwidth=4 ft=pir: +# Copyright (C) 2001-2008, The Perl Foundation. +# $Id$ + +=head1 NAME + +examples/pir/hanoi.pir - Towers of hanoi + +=head1 SYNOPSIS + +You may pass in the height of the tower: + + % ./parrot examples/pir/hanoi.pir 5 + +The default is 3. + +=head1 DESCRIPTION + +Towers of Hanoi (http://www.cut-the-knot.org/recurrence/hanoi.shtml) is +a combinatorial puzzle. The PIR shows manipulation of arrays of +integers. + +=head1 Data Structure + +C is a C PMC with three elements. Each element is a +C PMC which represents a tower (column) of Hanoi. +Each integer element of the array represents a single disk, where the +integer value is the size of the disk. The top of the tower is at the +highest index; since a larger disk cannot be placed on top of a smaller +one, it follows that the tower array must always be sorted in descending +order. This lends itself naturally to use of the C and C +operations for moving disks. + +So this situation (after the first move) + + | | + ==== | | + ====== | | == + +is represented as + + [[3, 2], [], [1]] + +In pseudocode: + + sub main() { + size = argv[0] || 3 + int towers[] = [[size..1], [], []] + move_stack(size, 0, 2, 1) + + sub move_stack(n_to_move, start, target, storage) { + if (n_to_move == 1) { + move_one(start, target) + } + else { + # Move all but the largest disk to storage. + move_stack(n_to_move-1, start, storage, target) + # Move the largest disk to the target. + move_one(start, target) + # Move all but the largest disk from storage to target. + move_stack(n_to_move-1, storage, target, start) + } + } + + sub move_one(start_col, dest_col) { + # Do the move + push(towers[dest_col], pop(towers[start_col])); + + # Print the results + print(towers); + } + } + +=head1 TODO + +Replace I6 etc. with mnemonic register names. + +=head1 HISTORY + + First version Tony Payne 2002-15-05 + Converted to PIR Bernhard Schmalhofer 2005-10-20 + Use PCC instead of bsr/ret Bob Rogers 2008-04-06 + +=cut + +# Towers of hanoi in Parrot Intermediate Representation +.sub "hanoi" :main + .param pmc argv + .local int size + + ## Create some lexical bindings. + .local pmc size_pmc, print_towers + .lex "size", size_pmc + ## Note that we don't need to do find_lex on the closures; functions are + ## sought using find_name, which looks at outer lexical scopes. + .lex "print_towers", print_towers + print_towers = get_hll_global 'print_towers' + print_towers = newclosure print_towers + .local pmc move_one, move_stack + .lex "move_one", move_one + move_one = get_hll_global 'MOVE' + move_one = newclosure move_one + .lex "move_stack", move_stack + move_stack = get_hll_global 'MOVE_STACK' + move_stack = newclosure move_stack + + # Check number of command line arguments + $I0 = argv + if $I0 < 2 goto USE_DEFAULT_SIZE + S5 = argv[1] + size = S5 + print "Building a tower of size " + print size + print ".\n" + goto SIZE_IS_NOW_KNOWN +USE_DEFAULT_SIZE: + print "Using default size 3 for tower.\n" + size = 3 +SIZE_IS_NOW_KNOWN: + size_pmc = new 'Integer' + size_pmc = size + print "\n" + + .local pmc towers + .lex "towers", towers + new towers, 'FixedPMCArray' + set towers, 3 + new P1, 'ResizableIntegerArray' + new P2, 'ResizableIntegerArray' + new P3, 'ResizableIntegerArray' + set towers[0], P1 + set towers[1], P2 + set towers[2], P3 + ## towers = [[],[],[]] + + .local int i + i = size +loop_populate: + push P1, i + dec i + if i > 0 goto loop_populate + ## towers = [[...,3,2,1],[],[]] + + ## Now solve it. + move_stack(size, 0, 2, 1) +.end + +## Print the current state of the towers array. +.sub print_towers :outer(hanoi) + .param pmc towers # an array + + ## Only PMCs can be stored as lexical variables, but we need an int. + .local pmc tower_size_pmc + tower_size_pmc = find_lex "size" + .local int tower_size + tower_size = tower_size_pmc + + .local pmc stack + .local int i, j, stack_size, tos + i = tower_size + dec i +loop_rows: + j = 0 +loop_cols: + .local int disk_size, n_spaces + stack = towers[j] + stack_size = stack + disk_size = 0 + if stack_size <= i goto print_it + disk_size = stack[i] # disk_size = towers[j][i] +print_it: + n_spaces = tower_size - disk_size + repeat S0, " ", n_spaces + print S0 + I6 = mul disk_size, 2 # I6 = disk_size * 2 + repeat S1, "=", I6 + print S1 + print S0 + + inc j + if j == 3 goto done_loop + print " | " + goto loop_cols +done_loop: + print "\n" + dec i + if i >= 0 goto loop_rows + print "\n" +.end + +## Take the topmost disk off the start_col stack, and put it on the dest_col +## stack. The way we've defined the data structures makes this trivial. +.sub MOVE :outer(hanoi) + .param int start_col + .param int dest_col + + .local pmc towers + towers = find_lex "towers" + + .local pmc start_stack, dest_stack + .local int disk + start_stack = towers[start_col] + disk = pop start_stack + dest_stack = towers[dest_col] + push dest_stack, disk + print_towers(towers) +.end + +## Move n_to_move disks from start_col to target_col, using storage_col +## for temporary storage if needed. +.sub MOVE_STACK :outer(hanoi) + .param int n_to_move + .param int start_col + .param int target_col + .param int storage_col + + if n_to_move > 1 goto move_multiple + move_one(start_col, target_col) + .return () +move_multiple: + dec n_to_move + ## Move all but the largest disk to storage. + move_stack(n_to_move, start_col, storage_col, target_col) + ## Move the largest disk to the target. + move_one(start_col, target_col) + ## Move all but the largest disk from storage to target. + move_stack(n_to_move, storage_col, target_col, start_col) +.end + +# Local Variables: +# mode: pir +# fill-column: 100 +# End: +# vim: expandtab shiftwidth=4 ft=pir: -- 2.11.4.GIT