The Symbol Table Describes Itself

Wherein we revisit the past and describe what we can do with the things we find inside.

THE WEEKLY CHALLENGE – PERL & RAKU #107


episode one:
“Déjà Vu All Over Again”


Task 1

TASK #1 › Self-descriptive Numbers

Submitted by: Mohammad S Anwar

Write a script to display the first three self-descriptive numbers. As per wikipedia, the definition of Self-descriptive Number is

In mathematics, a self-descriptive number is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b−1) counts how many instances of digit n are in m.

For example:

 1210 is a four-digit self-descriptive number:

    position 0 has value 1 i.e. there is only one 0 in the number
    position 1 has value 2 i.e. there are two 1 in the number
    position 2 has value 1 i.e. there is only one 2 in the number
    position 3 has value 0 i.e. there is no 3 in the number
Output
    1210, 2020, 21200

Method

There are two basic ways to approach this problem:

  1. The formula: (b-4)b(b-1) + 2b(b-2) + b(b-3) + b3

This formula will generate a self-descriptive number for any base 7+. However the formula is in base10, so we will need to convert the base10 number to the relevant base to see its self-descriptive nature. Because the numbers get quite large, we will need to utilize the bigint pragma.

  1. Alternately, we could just assemble a number out of whole cloth, as the interesting qualities of the numbers are based on numeric position rather than mathematical quirks. Logic, more than math, defines whether numbers exist in the lower end of the range, and above 6, the numbers follow a set positional pattern.

Let’s expand on this second idea. A little logical excursion shows, for example, that for binary, with 1 and 0 available, no number can exist. No number can have a 0 in the 0th position, as its existence nullifies itself. In binary we have two positions available, so if the 0th is 1, the first must be 0, being the 0 counted in the 0th position, but that again leads to contradiction. So no binary. For ternary we get 100. For quartinary we can construct 1210 and 2200. For base 6 again we get
nothing, but after 6 things settle into a pattern:

    position    value
    0           (b-4)
    1           2
    2           1
    ...         0   in quantity (b-7)
    (b-3)       1
    (b-2)       0
    (b-1)       0
    b           0

so we can build arbitrarily large numbers for bases > 6 by assembling strings:

    "(base - 4) displayed in the base" + "21" 
                    + "(base -7) number of 0s" + "1000"

With comparison to the formulaic derivation we can see that the results are the same.

PERL 5 SOLUTION

It’s interesting to note that in the Perl versions, we have to hand-roll our own base conversion routines, allowing us to create numbers up to base-39, rather than 36, without resorting to special characters. You know, for all your base-39 needs. Or at least those needs that don’t need to write a digit above Z.

use warnings;
use strict;
use feature ":5.26";

use bigint;

## ## ## ## ## MAIN

my $base;

say "derived numbers:";
for $base (2..39){
    printf "%2d     %s\n", $base, self_descriptive($base);
}

say "";

say "assembled numbers:";
for $base (7..39){
    printf "%2d     %s\n", $base, self_descriptive_assembled($base);
}

sub self_descriptive {
## formula for creating self-descriptive numbers for a given base ( returns undef for 2, 3 and 6, which have no numbers )
    my $base = shift;
    return undef if $base == 2 or $base == 6;
    return 100   if $base == 3;
    my $dec = ($base-4)*($base**($base-1)) + 2*($base**($base-2)) + $base**($base-3) + $base**3;
    my @alphanum = (0..9, 'A'..'Z');
    my $out = "";
    my $rem;
    while ( $dec > 0 ) {
        ($dec, $rem) = (int( $dec/$base ), $dec % $base); 
        $out = $alphanum[$rem] . $out;
    }
    return $out;
}

sub self_descriptive_assembled {
## or we can just assemble a graphical representation of a number manually that will fit the bill
## only for b > 6;
    my $base = shift;
    my @alphanum = (0..9, 'A'..'Z');
    my $out = $alphanum[$base-4] . "21" . "0" x ($base-7) . "1000";
    return $out;
}
raku solution

We’ll just use the equation form for Raku. The string form is cool and all, but less robust.

unit sub MAIN () ;

sub sd (Int $base) {

    $base == any(2,3,6) and return -1;
    
    (($base-4)*($base**($base-1)) + 2*($base**($base-2)) + $base**($base-3) + $base**3)
        .base($base);

}


say sd($_) for 2..36;
Python solution
import numpy

def sd (b):
    if b in (2,3,6):
        return -1
    dec = ((b-4)*(b**(b-1)) + 2*(b**(b-2)) + b**(b-3) + b**3)
    return numpy.base_repr(dec, base=b)
    

for b in range(2,36):
    print(sd(b))

episode two:
“Crack It Open Like an Egg And Look Inside”


task 2

List Methods

Submitted by: Mohammad S Anwar

Write a script to list methods of a package/class.

Example
package Calc;

use strict;
use warnings;

sub new { bless {}, shift; }
sub add { }
sub mul { }
sub div { }

1;
Output
BEGIN
mul
div
new
add

Method

There are scenarios that could arise where you have an object and want your code to be able to know what it can do and react accordingly without hard-coding the result. Maybe not everyday, mind you, but I could arise. Perhaps the object is one of several options that can arrive at a place in our code, but only one can do a thing, and if it can we want to do it. To do this we’ll need to ask the object what it can do.

Ok, perhaps this scenario is a little contrived, as with an object it would be better to use the UNIVERSAL:: method can() to see whether a method exists, and that’s not what we’re here to talk about today. Today we’re going to discuss the symbol table.

In Perl the names for the things — arrays, scalars, subroutines, filehandles — all the names are stored in a hash-like structure known the symbol table. We can query the symbol table directly in a manner akin to that of the hash it’s very much like but isn’t quite. The symbol table itself has the symbol for the package it’s in, like main::, or Calc:: Note the double colons are part of the name, so they’re not really the separator you always assumed they were, are they? Sneaky. But there’s more.

If we run {say $_ for keys %Calc::} treating the symbol table like the hash it isn’t, we get something like the result from the example. But what’s this BEGIN that shows up out of nowhere? Well the BEGIN blocks get called and executed immediately, as soon as it gets compiled. There are reasons Perl has put the BEGIN block we are seeing, and you can even put your own BEGIN blocks in your modules. You can even put more than one, which should pique your interest, as they’re all called BEGIN. This has its uses, surely, generally to make sure everything is in order before a script is run or such, but the thing is, is that it’s not really a subroutine.

perlmod even says as much:

One should note that these code blocks don’t really exist as named subroutines (despite their appearance). 

So I’d argue the example is wrong, and that shouldn’t be there. You can’t call a BEGIN block. It just exists, and gets called automatically when it’s first seen. After that, it not only can’t be called, but it no longer even exists:

Once a BEGIN has run, it is immediately undefined and any code it used is returned to Perl’s memory pool.

Another problem with this simple approach is that any package variable will also show up. If we have a variable our $foo in the class, then foo will be in the symbol table alongside the subroutine names.

What to do? Well the names returned by the hash lookup part of the symbol table aren’t the variables themselves. That’s where things get a little weird, and why we said the structure isn’t quite a hash. It’s like a hash in front of another data structure known as a typeglob, which has slots for pointers, and these pointers point to the instances of the variables. There’s a whole other level of indirection on the second part of the table.

Typeglobs, however, aren’t hashes and we can’t just look at the pointers through them. Well not like a hash at least. What we can do is indirectly look, though, and check whether the subroutine with a certain name is defined, using a symbolic reference through an interpolated variable name:

defined &{"Calc::$_"}

This does what you think it might, and what we want. And that’s the right way to do it. Which is a bit odd, because of the whole fundamental iffiness of the symbolic referencing.

PERL 5 SOLUTION

We added a few package variables to show they won’t be reported.

use warnings;
use strict;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


package Calc;

use strict;
use warnings;

our $foo;
our @bar;
our %baz;

sub new { bless {}, shift; }
sub add { }
sub mul { }
sub div { }

1;

package main;

say " $_" for sort grep { defined &{"Calc::$_"} } keys %Calc::;

This produces the output

 add
 div
 mul
 new
RAKU SOLUTION

In Raku we can directly query the object with .^methods()

class Calc {

    has $foo;

    method add ($a, $b) {}
    method sub ($a, $b) {}
    method mul ($a, $b) {}
    method div ($a, $b) {}

}


package main {

    my @m = Calc.^methods();
    .say for @m;
}
PYTHON SOLUTION

In Python we can get a list of callable attributes, but well further filter that list to weed out the under methods, which are probably not what we’re looking for.

class Calc(object):

    def add(self, val):
        return 1;
        
    def sub(self, val):
        return 1;
        
    def mul(self, val):
        return 1;
        
    def div(self, val):
        return 1;
        
    


methods = [attr for attr in dir(Calc) if callable(getattr(Calc, attr)) and attr.startswith('__') is False]

print(methods)



The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://perlweeklychallenge.org