Coding: Hacks and Snippets

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Mon Aug 01, 2011 11:57 pm UTC

Did the system not have dirname(1) ?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
thoughtfully
Posts: 2244
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Coding: Hacks and Snippets

Postby thoughtfully » Tue Aug 02, 2011 12:40 am UTC

Hmm, so this would work too:

Code: Select all

#!/bin/sh
cd `dirname $0`; python xyz123

But that's not hacky at all! Get out of the thread, party pooper :)
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Sat Jan 05, 2013 7:24 am UTC

I recently became addicted to KenKen puzzles, which led me to playing around with code to generate simple random Latin Squares. Considering the world-wide interest in Sudoku & similar puzzles in recent years, I was a bit surprised that it's not particularly easy to find simple Latin Square code or algorithms on the Net.

I have seen lots of references to Knuth's "Dancing Links" algorithm (aka DLX), which I understand is a very efficient way to attack NP-complete problems, but I want to generate Latin Squares of order 30 and larger, and DLX takes a lot of memory for problems of that size.

So here's my attempt, written in Python over the last couple of days. It can generate Latin Squares up to around order 50 quite rapidly; larger squares may take some time... It displays the results in a numeric or alphabetic grid, and it can also generate PPM graphic output using a "rainbow" palette.


Small Latin Squares are easy enough to generate with simple brute force. Hall's marriage theorem guarantees that it's always possible to complete a Latin rectangle into a Latin Square, so we can just proceed row by row, selecting a number that hasn't been used yet in the current column and row. If a row becomes impossible to complete, we can just restart that row.

This process works fine for the first half of the grid, but it gets progressively slower for the last rows. So the code below takes a slightly smarter approach with the bottom half of the square. To simplify the number selection process, we keep track of which numbers are still unused in each column, as a list of sets. When we get to the lower rows of the square, we proceed carefully, making sure when we append a number to the current row that none of the subsequent columns' unused sets is a subset of the new row. If we run out of choices at a particular column, then we're forced to restart the row.

This "careful" algorithm is much faster than the simple approach, especially for larger squares. Eg, when generating an order 42 square (using a randomizer seed of 13), the simple algorithm just took 26.344 seconds on this 2GHz machine, generating 71222 trial rows. In contrast, the careful algorithm took 1.783 seconds, and only needed to generate 1890 trial rows. Of course, this comparison isn't strictly fair, since the two algorithms generate different squares, but the speed-up is still impressive, IMHO. :)

Code: Select all

#!/usr/bin/env python

''' Build a random Latin Square
    With PPM output
Written by PM 2Ring, 2013.01.05
'''

import sys, getopt, random, colorsys

def putgrid_int(grid, width=1):
    ''' Simple 2D integer array display '''
    for row in grid:
        print " ".join("%*d" % (width, j) for j in row)
    print

orda = ord('a')
ordA = ord('A')
lowalpha = [chr(i+orda) for i in xrange(26)]
highalpha = [chr(i+ordA) for i in xrange(26)]
allalpha = [' '] + highalpha + lowalpha
def putgrid_alpha(grid, width=1):
    ''' Display grid using letters for the symbols '''
    for row in grid:
        print " ".join([allalpha[j] for j in row])
    print
   

def make_palette(m):
    #Create a rainbow palette
    sat = 0.875
    val = 0.75
    def hsv_to_rgb_chr(h, s, v):
        ''' Convert hsv color to RGB & then to byte, gamma corrected '''
        return ''.join(chr(int(255*x**0.4545)) for x in colorsys.hsv_to_rgb(h, s, v))
    return [hsv_to_rgb_chr(float(i) / m, sat, val) for i in xrange(m)]

def savepgm(grid, pal, fname):
    m = len(grid)
    data = ''.join(pal[pixel-1] for row in grid for pixel in row)
    f = open(fname, 'wb')
    f.write('P6\n%d %d\n255\n%s' % (m, m, data))
    f.close()

def LatinSquare(m):
    ''' Build a random latin square using integers from 1 to m '''
    # A range the length of a side, for general usage
    r = xrange(m)
   
    allnums = set(i+1 for i in r)

    #A list of sets containing numbers still available in each column
    columns = [allnums.copy() for i in r]
   
    #An empty grid for the Latin Square, which will eventually contain a list of rows,
    #with each row containing a list of ints
    grid = []

    #Trials progress counter
    def progress(delta=1, show=False, EOL=''):
        progress.current += delta
        if show or progress.current%100 == 0:
            sys.stderr.write('\r Row %2d, Trial %d %s' % (i+1, progress.current, EOL))
    progress.current = 0
   
    def fill_row():
        while True:
            row = []
            for j in r:
                nums = columns[j] - set(row)
                if not nums:
                    #restart row
                    break
                c = random.choice(list(nums))
                row.append(c)
            else:
                return row
            progress(1)
   
    def fill_row_carefully():
        while True:
            row = []
            for j in r:
                nums = columns[j] - set(row)
                while nums:
                    c = random.choice(list(nums))
                    testrow = row + [c]
                    s = set(testrow)
                    #Ensure that no subsequent column is a subset of testrow.
                    #We really only need to test subsets if row is long enough, but
                    #the slight time saving isn't worth the extra code complexity :)
                    for k in columns[j+1:]:
                        if k <= s:
                            break
                    else:
                        row = testrow
                        break
                    nums.remove(c)
                    #progress(1)
                else:
                    #No nums left, restart row
                    break
            else:
                return row
            progress(1)
   
    for i in r:
        if i < m//2:
            row = fill_row()
        else:
            row = fill_row_carefully()
        grid.append(row)
        for j in r:
            columns[j].remove(row[j])
        progress(0, show=True, EOL='\n') 
       
    sys.stderr.write('\n')
    return grid

def main():
    #Default commandline arguments
    orderstr = None
    seed = None
    imagename = None
    alphagrid = False
   
    def usage(msg=None):
        s = msg != None and '%s\n\n' % msg or ''
        s += '''Random Latin Square maker, with PPM output.
       
Usage:
python %s [-a] [-r randomizer seed] [-i imagename] [[-o] order]

By default, the Latin Square is printed to stdout using integers (starting at 1),
the -a option selects alphabetic output mode.
The randomizer seed can be a number or a string; if no seed is given,
an internal seed derived from the current system time is used.
If no imagename is given, PPM output is not generated.
The order is the length of a side of the Latin Square.
This program can generate an order 52 square in just under a minute on a 2GHz machine;
larger squares may take considerably longer.'''
        print >>sys.stderr, s % (sys.argv[0])
        raise SystemExit, msg != None

    try:
        opts, args = getopt.getopt(sys.argv[1:], "ahi:o:r:")
    except getopt.GetoptError, e:
        usage(e.msg)

    for o, a in opts:
        if o == '-h': usage(None)
        elif o == '-a': alphagrid = True
        elif o == '-i': imagename = a
        elif o == '-o': orderstr = a
        elif o == '-r': seed = a
   
    if orderstr == None:
        orderstr = len(args) > 0 and args[0] or '8'

    try:
        order = int(orderstr)
        if order <= 0:
            raise ValueError, 'Order must be a positive integer.'
        maxalphalen = len(allalpha) - 1
        if alphagrid and order > maxalphalen:
            raise ValueError, 'Order must be <= %d in alphabetic output mode.' % maxalphalen
    except ValueError, e:
        usage('Bad order argument: ' + str(e))
        raise

    random.seed(seed)

    grid = LatinSquare(order)
    if alphagrid:
        putgrid_alpha(grid)
    else:
        putgrid_int(grid, len(str(order)))

    if imagename:
        pal = make_palette(order)
        savepgm(grid, pal, imagename)

if __name__ == '__main__':
    main()


Any comments, suggestions, or improvements are welcome.

Edit

Oops! When I added the fancy command line argument handling I somehow deleted the line that seeds the randomizer. :oops:

I've just fixed that. And I'm now working on a new version that uses a smart algorithm to do the last two rows almost instantly.

Edit 2

OK, here's the new version. The smart algorithm was a little trickier than I expected. :) But it's definitely faster than the old algorithm for large squares, eg, it can do an order 60 square in 28.341 seconds (19809 trials), compared to 2 minutes, 25.093 seconds (108936 trials), (using a randomizer seed of 13).

Code: Select all

#!/usr/bin/env python

''' Build a random Latin Square
    With PPM output
'''

import sys, getopt, random, colorsys

def putgrid_int(grid, width=1):
    ''' Simple 2D integer array display '''
    for row in grid:
        print " ".join("%*d" % (width, j) for j in row)
    print

orda = ord('a')
ordA = ord('A')
lowalpha = [chr(i+orda) for i in xrange(26)]
highalpha = [chr(i+ordA) for i in xrange(26)]
allalpha = [' '] + highalpha + lowalpha
def putgrid_alpha(grid, width=1):
    ''' Display grid using letters for the symbols '''
    for row in grid:
        print " ".join([allalpha[j] for j in row])
    print

def make_palette(m):
    #Create a rainbow palette
    sat = 0.875
    val = 0.75
    def hsv_to_rgb_chr(h, s, v):
        ''' Convert hsv color to RGB & then to byte, gamma corrected '''
        return ''.join(chr(int(255*x**0.4545)) for x in colorsys.hsv_to_rgb(h, s, v))
    return [hsv_to_rgb_chr(float(i) / m, sat, val) for i in xrange(m)]

def savepgm(grid, pal, fname):
    m = len(grid)
    data = ''.join(pal[pixel-1] for row in grid for pixel in row)
    f = open(fname, 'wb')
    f.write('P6\n%d %d\n255\n%s' % (m, m, data))
    f.close()

def LatinSquare(m):
    ''' Build a random latin square using integers from 1 to m '''
    # A range the length of a side, for general usage
    r = xrange(m)

    allnums = set(i+1 for i in r)

    #A list of sets containing numbers still available in each column
    columns = [allnums.copy() for i in r]

    #An empty grid for the Latin Square, which will eventually contain a list of rows,
    #with each row containing a list of ints
    grid = []

    #Trials progress counter
    def progress(delta=1, show=False, EOL=''):
        progress.current += delta
        if show or progress.current%100 == 0:
            sys.stderr.write('\r Row %2d, Trial %d %s' % (i+1, progress.current, EOL))
    progress.current = 0

    def fill_row():
        while True:
            row = []
            for j in r:
                nums = columns[j] - set(row)
                if not nums:
                    #restart row
                    break
                c = random.choice(list(nums))
                row.append(c)
            else:
                return row
            progress(1)

    def fill_row_carefully():
        while True:
            row = []
            for j in r:
                nums = columns[j] - set(row)
                while nums:
                    c = random.choice(list(nums))
                    testrow = row + [c]
                    s = set(testrow)
                    #Ensure that no subsequent column is a subset of testrow.
                    #We really only need to test subsets if row is long enough, but
                    #the slight time saving isn't worth the extra code complexity :)
                    for k in columns[j+1:]:
                        if k <= s:
                            break
                    else:
                        row = testrow
                        break
                    nums.remove(c)
                    #progress(1)
                else:
                    #No nums left, restart row
                    break
            else:
                return row
            progress(1)

    for i in xrange(m-2):
        if i < m//2:
            row = fill_row()
        else:
            row = fill_row_carefully()
        grid.append(row)
        for j in r:
            columns[j].remove(row[j])
        progress(0, show=True, EOL='\n')

    #Do the last two rows
    #Find indices of remaining numbers
    table = [[] for j in xrange(m+1)]
    for j in r:
        u, v = columns[j]
        table[u] += [j]
        table[v] += [j]

    rows = [m*[0], m*[0]]
   
   
    i = m - 2
    while True:
        #Find first unfilled column
        for j in r:
            if rows[0][j] == 0:
                break
        else:   
            break

        #Fill column j
        c, d = columns[j]
        if random.random() < 0.5:
            c, d = d, c
        rows[0][j] = c
        rows[1][j] = d
        last = d

        #Now do the remaining columns in this circuit
        while True:
            #Get the other column containing c
            s = table[c]
            j = s[1] if s[0]==j else s[0]

            #Put the new c into the upper row and the old c into the lower row
            u, v = columns[j]
            c, d = (v, u) if u == c else (u, v)
            rows[0][j] = c
            rows[1][j] = d
            #print rows
            if c == last:
                #We've reached the end of this circuit
                break
        progress(1, show=True)
    grid += rows

    sys.stderr.write('\n')
    return grid

def main():
    #Default commandline arguments
    orderstr = None
    seed = None
    imagename = None
    alphagrid = False

    def usage(msg=None):
        s = msg != None and '%s\n\n' % msg or ''
        s += '''Random Latin Square maker, with PPM output.

Usage:
python %s [-a] [-r randomizer seed] [-i imagename] [[-o] order]

By default, the Latin Square is printed to stdout using integers (starting at 1),
the -a option selects alphabetic output mode.
The randomizer seed can be a number or a string; if no seed is given,
an internal seed derived from the current system time is used.
If no imagename is given, PPM output is not generated.
The order is the length of a side of the Latin Square.
This program can generate an order 52 square in under 7 seconds on a 2GHz machine,
and an order 60 square in around half a minute; larger squares may take considerably longer.'''
        print >>sys.stderr, s % (sys.argv[0])
        raise SystemExit, msg != None

    try:
        opts, args = getopt.getopt(sys.argv[1:], "ahi:o:r:")
    except getopt.GetoptError, e:
        usage(e.msg)

    for o, a in opts:
        if o == '-h': usage(None)
        elif o == '-a': alphagrid = True
        elif o == '-i': imagename = a
        elif o == '-o': orderstr = a
        elif o == '-r': seed = a

    if orderstr == None:
        orderstr = len(args) > 0 and args[0] or '8'

    try:
        order = int(orderstr)
        if order <= 0:
            raise ValueError, 'Order must be a positive integer.'
        maxalphalen = len(allalpha) - 1
        if alphagrid and order > maxalphalen:
            raise ValueError, 'Order must be <= %d in alphabetic output mode.' % maxalphalen
    except ValueError, e:
        usage('Bad order argument: ' + str(e))
        raise

    random.seed(seed)

    grid = LatinSquare(order)
    if alphagrid:
        putgrid_alpha(grid)
    else:
        putgrid_int(grid, len(str(order)))

    if imagename:
        pal = make_palette(order)
        savepgm(grid, pal, imagename)

if __name__ == '__main__':
    main()
Last edited by PM 2Ring on Wed Jan 18, 2017 7:29 am UTC, edited 1 time in total.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Thu Jan 10, 2013 3:05 am UTC

So my goal is to be able to deal with lists of ints in C++ template metaprogramming without having an insane recursion depth.

I want to be able to turn a flat list into a tree using O(lg n) recursions. Turning a tree into a list in O(lg n) recursions is extremely easy.

Code: Select all

#include <type_traits>

    template<int... s>
    struct seq {
      enum { count = sizeof...(s) };
    };

    template<typename s1, typename s2>
    struct append;
    template<int... s1, int... s2>
    struct append< seq<s1...>, seq<s2...> > {
      typedef seq<s1..., s2...> type;
    };

    template<int n, typename seq, typename=void>
    struct partition;

    template<int n, int... s>
    struct partition< n, seq<s...>, typename std::enable_if< (n>1) >::type > {
      enum { total = sizeof...(s) };
      typedef partition<n/2, seq<s...>> first;
      typedef partition<n/2, typename first::right> second;
      typedef typename append< typename first::left, typename second::left >::type left;
      typedef typename second::right right;
      enum { error = left::count + right::count != total };
    };

    template<int s0, int... s>
    struct partition< 1, seq<s0, s...>, void > {
      typedef seq<s0> left;
      typedef seq<s...> right;
      enum { total = left::count + right::count };
      enum { error = false };
    };

    template<int... s>
    struct partition< 0, seq<s...>, void > {
      typedef seq<> left;
      typedef seq<s...> right;
      enum { total = left::count + right::count };
      enum { error = false };
    };

    template<typename seq, typename=void>
    struct tree;

    template<>
    struct tree<seq<>> {
      typedef seq<> type;
      enum {is_leaf = true};
    };

    template<int s0, int s1, int... s>
    struct tree<seq<s0, s1, s...>> {
      typedef partition< (sizeof...(s)+2)/2, seq<s0, s1, s...> > part;
      typedef tree< typename part::left > left;
      typedef tree< typename part::right > right;
      enum {is_leaf = false};
      enum {error = part::error};
    };

    template<int s0>
    struct tree<seq<s0>> {
      typedef seq<s0> type;
      enum {is_leaf = true};
    };

    template<typename tree, typename=void>
    struct flatten;

    template<typename tree>
    struct flatten<tree, typename std::enable_if< tree::is_leaf >::type> {
      typedef typename tree::type type;
    };

    template<typename tree>
    struct flatten<tree, typename std::enable_if< !tree::is_leaf >::type> {
      typedef typename flatten< typename tree::left >::type left;
      typedef typename flatten< typename tree::right >::type right;
      typedef typename append< left, right >::type type;
    };


    // remap takes a pred:seq<s1...>->seq<s2...> and applies it to a tree directly, or to a sequence by working through a balanced binary tree.
    template<template<typename s_in>class pred, typename seq,typename=void>
    struct remap;

    template<template<typename s_in>class pred, int... s>
    struct remap<pred, seq<s...>,void> {
      typedef typename flatten< remap< pred, tree<seq<s...>> > >::type type;
    };

    template<template<typename s_in>class pred, typename tree>
    struct remap<pred, tree, typename std::enable_if<tree::is_leaf>::type> {
      typedef typename pred<typename tree::type>::type type;
      enum{is_leaf = true};
    };

    template<template<typename s_in>class pred, typename tree>
    struct remap<pred, tree, typename std::enable_if<!tree::is_leaf>::type> {
      typedef remap<pred, typename tree::left> left;
      typedef remap<pred, typename tree::right> right;
      enum{is_leaf = false};
    };

    template<typename seq, template<int>class op>
    struct do_op;
    template<template<int>class op>
    struct do_op<seq<>, op> {
      typedef seq<> type;
    };
    template<int s0, int... s, template<int>class op>
    struct do_op<seq<s0, s...>, op> {
       typedef typename append< seq<op<s0>::value>, typename do_op<seq<s...>,op>::type>::type type;
    };
    template<typename seq, template<int>class op, typename=void>
    struct filter_seq;
    template<template<int>class op>
    struct filter_seq<seq<>, op, void> {
       typedef seq<> type;
    };
    template<int s0, int... s, template<int>class op >
    struct filter_seq<seq<s0,s...>, op, typename std::enable_if< op<s0>::value >::type> {
       typedef typename append< seq<s0>, typename filter_seq<seq<s...>,op>::type>::type type;
    };
    template<int s0, int... s, template<int>class op >
    struct filter_seq<seq<s0,s...>, op, typename std::enable_if< !op<s0>::value >::type> {
       typedef typename filter_seq<seq<s...>,op>::type type;
    };
   
    template<template<int>class op>
    struct remap_values {
      template<typename seq>
      struct plate {
         typedef typename do_op<seq, op>::type type;
      };
    };
    template<template<int>class op>
    struct filter_values {
      template<typename seq>
      struct plate {
        typedef typename filter_seq<seq, op>::type type;
      };
    };
    template<int n>
    struct square {
      enum { value = n*n };
    };
    template<int n>
    struct is_even {
      enum { value = !(n&1) };
    };

    template<int max, int min=0>
    struct gen_seq2 {
       enum { mid = ((max-1)+min)/2 };
       typedef typename gen_seq2< max-1, mid >::type big;
       typedef typename gen_seq2< mid, min >::type small;
       typedef typename append<small, big>::type most;
       typedef typename append< most, seq<max-1> >::type type;
    };
    template<int n>
    struct gen_seq2<n,n> {
       typedef seq<> type;
    };
    template<int n, int... s>
    struct gen_seq:gen_seq<n-1, n-1, s...> {};
    template<int... s>
    struct gen_seq<0, s...> {
       typedef seq<s...> type;
    };
   
    template<typename seq, typename=void>
    struct print_seq;
   
    template<>
    struct print_seq<seq<>, void> {};
   
    #include <iostream>
    template<int s0>
    struct print_seq<seq<s0>, void> {
      print_seq() {
        std::cout << s0 << "\n";
      }
    };
    template<int... s>
    struct print_seq<seq<s...>, typename std::enable_if<(sizeof...(s)>1)>::type>:print_seq< tree<seq<s...>> > {};

    template<typename tree>
    struct print_seq<tree, typename std::enable_if< tree::is_leaf >::type>:print_seq<typename tree::type> {};

    template<typename tree>
    struct print_seq<tree, typename std::enable_if< !tree::is_leaf >::type>:
      print_seq<typename tree::left>, print_seq<typename tree::right>
   {};
   
   int main() {
      typedef tree<seq<1,2,3>> tree1;
      print_seq<seq<1,2,3>> test0;
      typedef filter_seq< gen_seq<10>::type, is_even >::type even1;
      print_seq<even1> test1;
      typedef do_op< gen_seq<10>::type, square >::type square1;
      print_seq<square1> test2;
     
      typedef remap_values<square>::plate<gen_seq<5>::type>::type square2;
      print_seq<square2> test3;
     
      typedef remap< remap_values<square>::plate, seq<10,100,1000> >::type square3;
      print_seq<square3> test4;
     
      typedef gen_seq2<500>::type big;
      print_seq<big> test5;
   }

I have a tree-based (log recursion depth) sequence generator above, as well as a tree-based template functor applicator on arbitrary compile time int sequences.

I've enabled "filter" and "remap values" for now.

A "tree" is a category of types such that for each tree type, they have an "::is_leaf" bool such that "::is_leaf" is true means "::type" is a sequence, and if false it means "::left" and "::right" are tree types. Remap instead of returning a tree type becomes a tree type, which saved some boilerplate.

tree<seq<...>> builds a balanced binary tree out of the sequence.

Most of the above algorithms limit recursion depth by specializing for sequences, then turning it into a call on the tree case followed by a flatten, then specializing on leaves and non-leaves.

Maybe I should unify it, and instead of having some cases where passing in a tree makes the type you pass it to a tree, have it return a tree. That would require rewriting `tree` to a certain extent -- have a `make_tree` that builds the tree, and `tree` becomes a template on left and right child? Dunno.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

mr-mitch
Posts: 477
Joined: Sun Jul 05, 2009 6:56 pm UTC

Re: Coding: Hacks and Snippets

Postby mr-mitch » Thu Jan 10, 2013 9:40 am UTC

I was thinking of doing something like that in order to store numbers of variable precision (and do stuff like karatsuba multiplication), but I've little idea about C++ templates.

How'd you learn your fu and can you recommend resources?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Thu Jan 10, 2013 10:23 am UTC

Write stuff. Start with basic stuff, like compile time fibbonaci. Then I wrote a merge sort. C++ templates are abtruse, so writing is about the only way to figure out what works and what does not.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

ralight
Posts: 6
Joined: Tue Jan 29, 2013 9:46 am UTC

Re: Coding: Hacks and Snippets

Postby ralight » Tue Jan 29, 2013 10:56 am UTC

Not so much real coding, but it always amused me. The below is a regular expression substitution, suitable for sed, vim or similar for removing the first space character on a line.

Code: Select all

s \   


It assumes that your regex engine takes the first character after the "s" as the character for separating the regex and replacement fields. It would more usually (and boringly) be represented as:

Code: Select all

s/ //

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: Coding: Hacks and Snippets

Postby Cosmologicon » Tue Jan 29, 2013 3:55 pm UTC

While your example is not super practical, it is pretty handy to know that you can use other characters than /, especially if what you're replacing is slashes. I like pipes, they look like separators:

Code: Select all

s|\\|/|
is a bit easier to read than

Code: Select all

s/\\/\//

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Tue Jan 29, 2013 4:57 pm UTC

Code: Select all

s   ^       \      

(replace starting 4 spaces with a tab)

Code: Select all

s   \          \   \      

(replace tab followed by 4 spaces with a tab)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
You, sir, name?
Posts: 6974
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Hacks and Snippets

Postby You, sir, name? » Thu Jan 31, 2013 7:38 pm UTC

Code: Select all

$ find -type f -name \*foobar  | cut -d/ -f2 | uniq -c


Count number of files with extension foobar, by subdirectory.

Also had use of

Code: Select all

(foobar; echo "default") | head -n1


today, where I wanted the single line output of "foobar" if it printed anything, or "default" if it didn't.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Fri Mar 15, 2013 1:27 am UTC

My next bit of toy metaprogramming: attributes and reflection in C++.

The goal syntax is something like:

Code: Select all

typedef Aggregate<
    Field< std::string, Name >,
    Field< int, Age >,
    Field< double, Weight >,
    Field< Bar, Special >
  >  FooAggregate;
struct Foo:
 FooAggregate
{
  Foo():
    FooAggregate(
      name  |"name"   ( "Unknown" ),
      age   |"age"    ( -1 ),
      weight|"weight" ( -1.0 ),
      bar   |"bar"    ( Special() )
    )
  {}
};

int main() {
  Foo foo;
  foo^name = "Bob";
  foo^age = 17;
  foo^weight = 118;
  foo^bar = Special( pi );
}

I know how to get the above working, with full compile time and run time reflection and property-type syntax on assignment and reading, but I have one remaining puzzle:

Can I get rid of the requirement to pass the stringized name of the field to the constructor, without resorting to macros or ugly syntax somewhere?

That would let me upgrade the constructor syntax to:

Code: Select all

  Foo():
    FooAggregate(
      name( "Unknown" ),
      age( -1 ),
      weight( -1.0 ),
      bar( Special() )
    )
  {}

which would be sweet.

(How, you might ask? Well, the trick is to introduce new type and non-type names via something like this:
Spoiler:

Code: Select all

struct Name: FieldTag<Name> {} name;

where FieldTag<Name> has various operators overloaded on it, such as operator() from which it returns a perfect-forwarded tuple containing the arguments in the () plus itself as argument 1.

Aggregate looks something like this:

Code: Select all

template<typename T, typename FieldTag>
struct Field {
  typedef T value_type;
  typedef FieldTag field_tag;
};
template<typename... Fields>
struct Aggregate: Base, Property< Aggregate<Fields...>, Fields >... { /* details */ };

And finally, Property uses CRTP to get expose itself to runtime reflection inside Base, and overloads operator^ on its particular Field::field_tag type to generate a pseudo-reference to the stored Field::value_type. This gives us the foo^name syntax.

Aggrigate has a variardic constructor that takes the FieldTag<T>::operator() produced tuples, and one by one uses them to construct the Properties via perfect forwarding. We also search this list for the missing FieldTag<T> entries, and trivially construct them.

The result is a mirror of the C++ structure syntax produced in metaprogramming, but we have full compile time and runtime reflection, and we can access the fields via either raw references or pseudo-references allowing arbitrary code to run when they are read or written.

Thoughts? Am I doing something that some obscure boost sub-library has already done better?
Last edited by Yakk on Wed Mar 20, 2013 10:22 pm UTC, edited 2 times in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Jplus
Posts: 1692
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

Re: Coding: Hacks and Snippets

Postby Jplus » Wed Mar 20, 2013 6:51 pm UTC

I don't think it's exactly the same functionality, but your metaprogramming hacks always remind me a lot of Boost.Proto and the way Eric Niebler talked about it at C++Next (website seems to be down, unfortunately). Take that as a compliment. :)
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Thu May 02, 2013 10:29 pm UTC

So there was a neat question on stack exchange -- creating a type-safe AST (abstract syntax tree) transformer.

I've been playing with actually implementing my solution one step at a time, and it is stretching my skills at TMP (template meta programming) nicely.

We have the standard sequence stuff:

Code: Select all

// sequences of offsets:
template<std::size_t...>
struct seq {};
template<std::size_t Min, std::size_t Max, std::size_t... s>
struct make_seq:make_seq<Min, Max-1, Max-1, s...> {};
template<std::size_t Min, std::size_t... s>
struct make_seq<Min, Min, s...> {
    typedef seq<Min, s...> type;
};
template<std::size_t Max, std::size_t Min=0>
using MakeSeq = typename make_seq<Min, Max>::type;

for compile time sequences of indexes, my do_in_order trick:

Code: Select all

// utility function to do a sequence of tasks in a particular order:
void do_in_order() {}
template<typename F0, typename... Fs>
void do_in_order( F0&& f0, Fs&&... fs ) {
    std::forward<F0>(f0)();
    do_in_order( std::forward<Fs>(fs)... );
}

which sadly doesn't seem to work in gcc 4.8.0 :(.

This EnableIf:

Code: Select all

// Enable If helper:
template<std::size_t>
struct secret_enum { enum class type {}; };
template<std::size_t n>
using SecretEnum = typename secret_enum<n>::type;

template<bool b, std::size_t n = 0>
using EnableIf = typename std::enable_if< b, SecretEnum<n> >::type;

can be used to create multiple otherwise identical signature functions, and pick which one is valid based on TMP, with a nice syntax. Sadly, this trick doesn't work on Clang 3.2.

I introduced a type_list, but I'm getting tempted by the idea of using pure-tuples as types to represent clumps of types. So I wrote the worker functions that operate on it to support any type_list:

Code: Select all

// stores a bundle of types:
template<typename...>
struct type_list {};

// Copies types from one template<typename...> to another:
template<typename L, template<typename...>class Targ>
struct copy_types;
template<template<typename...>class L, typename... Ts, template<typename...>class Targ>
struct copy_types< L<Ts...>, Targ > {
    typedef Targ<Ts...> type;
};
template<typename L, template<typename...>class Targ>
using CopyTypes = typename copy_types<L, Targ>::type;

in particular, CopyTypes lets you take a type_list<a,b,c> and apply it to a template like variant<Ts...> without having to step down a level.

I wrote up a quick value-semantics pointer class, but there must be one in boost I just don't know about, right?

Code: Select all

template<typename T, typename=void>
struct do_clone {
    template<typename U>
    T* operator()( U&& u ) const {
        return std::forward<U>(u)->clone();
    }
};
#define RETURNS(X) ->decltype(X) { return (X); }
template<typename T>
struct value_ptr;
template<typename T> struct is_value_ptr: std::false_type {};
template<typename T> struct is_value_ptr< value_ptr<T> >: std::true_type {};
template<typename T> struct is_value_ptr< value_ptr<T>& >: std::true_type {};
template<typename T> struct is_value_ptr< value_ptr<T>const& >: std::true_type {};
template<typename T> struct is_value_ptr< value_ptr<T>&& >: std::true_type {};

template<typename T>
struct value_ptr {
    std::unique_ptr<T> val;

    explicit value_ptr( T* ptr ):val(ptr) {};
    explicit value_ptr( std::nullptr_t ):val() {};
    explicit value_ptr():val() {};
   
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr( value_ptr<U>&& o ): val(std::move(o.val)) {}
    value_ptr( value_ptr<T>&& o ): val(std::move(o.val)) {}
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr( value_ptr<U> const& o ): val(o.val?do_clone<U>()(o.val.get()):nullptr) {}
    value_ptr( value_ptr<T> const& o ): val(o.val?do_clone<T>()(o.val.get()):nullptr) {}
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr( value_ptr<U>& o ): val(o.val?do_clone<U>()(o.val.get()):nullptr) {}
    value_ptr( value_ptr<T>& o ): val(o.val?do_clone<T>()(o.val.get()):nullptr) {}
   
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr<T>& operator=( value_ptr<U>&& o ) {
        val = std::move(o.val);
        return *this;
    }
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr<T>& operator=( value_ptr<U> const& o ) {
        val = (o.val?do_clone<U>()(o.val.get()):nullptr);
        return *this;
    }
    template<typename U, typename=typename std::enable_if< std::is_base_of< T, U >::value>::type>
    value_ptr<T>& operator=( value_ptr<U>& o ) {
        val = (o.val?do_clone<U>()(o.val.get()):nullptr);
        return *this;
    }
   
    ~value_ptr() {}
   
    T* operator->() { return val.operator->(); }
    T const* operator->() const { return val.operator->(); }
    T& operator*() { return val.operator*(); }
    T const& operator*() const { return val.operator*(); }
    T* get() { return val.get(); }
    T const* get() const { return val.get(); }
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator==(RHS&& rhs) const RETURNS ( val == std::forward<RHS>(rhs) );
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator!=(RHS&& rhs) const RETURNS ( val != std::forward<RHS>(rhs) );
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator<=(RHS&& rhs) const RETURNS ( val <= std::forward<RHS>(rhs) );
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator>=(RHS&& rhs) const RETURNS ( val >= std::forward<RHS>(rhs) );
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator< (RHS&& rhs) const RETURNS ( val <  std::forward<RHS>(rhs) );
    template<typename RHS, EnableIf< !is_value_ptr<RHS>::value, 0 >...> auto operator> (RHS&& rhs) const RETURNS ( val >  std::forward<RHS>(rhs) );
   
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator==(U&& o) const RETURNS ( val == o.val )
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator!=(U&& o) const RETURNS ( val != o.val )
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator<=(U&& o) const RETURNS ( val <= o.val )
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator>=(U&& o) const RETURNS ( val >= o.val )
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator< (U&& o) const RETURNS ( val <  o.val )
    template<typename U, EnableIf< is_value_ptr<U>::value, 1 >...> auto operator> (U&& o) const RETURNS ( val >  o.val )
};
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator==( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs == rhs.val )
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator!=( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs != rhs.val )
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator<=( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs <= rhs.val )
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator>=( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs >= rhs.val )
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator< ( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs <  rhs.val )
template<typename LHS, typename T, EnableIf< !is_value_ptr<LHS>::value>...> auto operator> ( LHS&& lhs, value_ptr<T> const& rhs ) RETURNS ( lhs >  rhs.val )

the idea is you can create a value_ptr<T> and treat it much like an instance of T -- if you copy it, it calls "->clone()", but it has O(1) move, occupies the free store, can be a nullptr, and can be .reset().

There is also a multi-std::function wrapper that "overloads" the `std::function`s used to create it, and returns a `boost::variant` of the return types (whose type it constructs out of the std::function signatures), which is also a valid visitor for a `boost::variant` (it has a result_type typedef).

I then build a tree with typed nodes, the type of the node determining the type of the data, the types of the children, and the container used to hold the children.

The goal is to use the above to build type safe tree transformations. The next step will be to write non-structural transformations, transformations just on the data, and be able to type-safe transform an entire AST. Ie, imagine if pass 1 has identifiers and constansts stored in string form -- after the transformation, identifiers may have guids that take into account scope, and constants may be turned from strings to binary data, etc.

After that, structure-changing transformations.

Gonna be a lot of work, but I'm having fun!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Sat Jul 19, 2014 11:35 am UTC

dd with periodic progress report

I've been using dd a bit lately, so I decided to write this wrapper for it, which automates the process of telling dd to give a regular progress report.

It takes a time delay arg (which it passes to the sleep command), followed by the normal dd args. Call it with no args, or a leading arg of -h, to get a brief help message.

It prints the time delay value, followed by the dd command line, and asks for confirmation before it actually executes the dd command line.

dd-prog.bsh

Code: Select all

#!/bin/bash

# dd with progress indicator
# Written by PM 2Ring, 2014.07.19

Usage()
{
    echo "dd with progress indicator"
    echo "Usage:" 
    echo 
"$(basename $0) [-h] sleep_delay dd_args"
    exit 1
}

#Print Usage if called with no args, 
# or with something that matches -h as the 1st arg.
[[ -$@ || $=~ -]] && Usage >&2

#Get delay and build dd command line
delay=$1
shift 1
cmd
="dd $@"

echo "delay=[$delay]"
echo "cmd=[$cmd]"

read >&-"Ok to proceed? (Y/n) " -n1
[[ $REPLY = "n" ]] && { echo >&2; exit 1; }
echo >&2

#Run the dd command line in the background, saving its process ID
$cmd & pid=$!

#Set up a trap for ^C
trap "kill $pid; echo -e \"\nAborted\" >&2; exit 1" SIGINT
echo 
>&-"pid=$pid; press ^C to abort.\n"

while sleep $delay
do
    #Check that dd is still running
    if kill -0 $pid 2>/dev/null 
        then
            
#Send signal to dd, asking it to print I/O statistics
            kill -USR1 $pid
        else
            
#dd has finished
            break
    fi
    
#Allow dd to print its stuff before adding a newline
    sleep 0
    echo 
>&2
done

echo 
>&-"\nFinished."
 


Any questions, or constructive comments or suggestions are welcome.

Rysto
Posts: 1459
Joined: Wed Mar 21, 2007 4:07 am UTC

Re: Coding: Hacks and Snippets

Postby Rysto » Sat Jul 19, 2014 2:23 pm UTC

If you used FreeBSD, you could get a status update from from dd (and a number of other standard utilities) just by sending it a <Ctrl>-T (SIGINFO) signal. I don't know how you Linux users survive without SIGINFO.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Coding: Hacks and Snippets

Postby troyp » Sat Jul 19, 2014 5:27 pm UTC

You can pipe something through pv to get progress information on it. Or you can just use a command with progress info. ddrescue is supposed to be a good alternative to dd. If you need progress for an already running process, cv can do that.

As far as dd goes specifically, I've heard that you can actually get progress from it by sending USR1:

Code: Select all

pkill -USR1 dd

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Sun Jul 20, 2014 4:24 am UTC

Rysto wrote:If you used FreeBSD, you could get a status update from from dd (and a number of other standard utilities) just by sending it a <Ctrl>-T (SIGINFO) signal. I don't know how you Linux users survive without SIGINFO.

Interesting!

FWIW, an older version of KDE's Konsole allowed you to send some extra signals (eg SIGHUP) from a menu, but that functionality doesn't exist in the current version (as far as I can see).


troyp wrote:You can pipe something through pv to get progress information on it. Or you can just use a command with progress info. ddrescue is supposed to be a good alternative to dd. If you need progress for an already running process, cv can do that.


ddrescue is wonderful when you need to rescue stuff, but I prefer to use plain old dd when I don't need the advanced functionality of ddrescue, eg if I'm backing up an MBR, making an image of a healthy partition, or zeroing out a disk.

That cv program sounds rather interesting; I may investigate it further. The pv program sounds vaguely familiar. But I think my script is a bit more straightforward (and possibly slightly more efficient) than setting up a pipeline with 2 instances of dd.

troyp wrote:As far as dd goes specifically, I've heard that you can actually get progress from it by sending USR1:

Code: Select all

pkill -USR1 dd


As you might notice, my script uses kill -USR1 to do its thing. :) I suppose pkill would be ok, unless you happen to be running multiple instances of dd simultaneously...

FWIW, dd --help tells you all about the USR1 signal stuff.

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Coding: Hacks and Snippets

Postby troyp » Sun Jul 20, 2014 5:54 am UTC

PM 2Ring wrote:As you might notice, my script uses kill -USR1 to do its thing. :)

Oh, so it does :oops: I didn't read it carefully.

I suppose pkill would be ok, unless you happen to be running multiple instances of dd simultaneously...

Then you get their status as a bonus! More seriously, I think kill -USR1 $pid is the right way for a script. pkill is a handy shortcut for interactive use, when you know it's only going to match one process.

Btw, I just noticed this part:

Code: Select all

    #Check that dd is still running
    if kill -0 $pid 2>/dev/null

A null signal to check if a process is running and receiving signals. That's really cool. I didn't know about that.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Sun Jul 20, 2014 6:45 am UTC

I should probably hang onto that script... usually whenever I'm doing a big dd, I'll run this in another window:

Code: Select all

while killall -USR1 dd && sleep 1m; do true; done

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
PM 2Ring
Posts: 3620
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Coding: Hacks and Snippets

Postby PM 2Ring » Sun Jul 20, 2014 7:15 am UTC

troyp wrote:
I suppose pkill would be ok, unless you happen to be running multiple instances of dd simultaneously...

Then you get their status as a bonus!

:)

troyp wrote:More seriously, I think kill -USR1 $pid is the right way for a script. pkill is a handy shortcut for interactive use, when you know it's only going to match one process.

Agreed.

troyp wrote:Btw, I just noticed this part:

Code: Select all

    #Check that dd is still running
    if kill -0 $pid 2>/dev/null

A null signal to check if a process is running and receiving signals. That's really cool. I didn't know about that.

Yeah, I just noticed that myself yesterday. An earlier version of my script didn't do that, so it printed a "No such process" message after dd terminated normally. I guess that's only a minor annoyance, OTOH, programs shouldn't print out scary-looking diagnostics when nothing bad has happened.


phlip wrote:I should probably hang onto that script... usually whenever I'm doing a big dd, I'll run this in another window:

Code: Select all

while killall -USR1 dd && sleep 1m; do true; done


I used to do something similar, although I'd either run dd in the background so I could easily gets its PID, or grab it from ps or top. But then I thought, "Hey, I'm a programmer, I should automate this!" :)

Maelstrom.
Posts: 76
Joined: Tue Oct 21, 2008 12:18 pm UTC

Re: Coding: Hacks and Snippets

Postby Maelstrom. » Sun Jul 20, 2014 8:52 pm UTC

PM 2Ring wrote:
troyp wrote:Btw, I just noticed this part:

Code: Select all

    #Check that dd is still running
    if kill -0 $pid 2>/dev/null

A null signal to check if a process is running and receiving signals. That's really cool. I didn't know about that.

Yeah, I just noticed that myself yesterday. An earlier version of my script didn't do that, so it printed a "No such process" message after dd terminated normally. I guess that's only a minor annoyance, OTOH, programs shouldn't print out scary-looking diagnostics when nothing bad has happened


This does create a (small) race condition though. The dd process could finish after the kill -0, but before the kill -HUP. Unlikely, but possible. The way to avoid that is:

Code: Select all

while kill -HUP $pid 2> /dev/null ; do sleep 1m ; done

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Wed Aug 06, 2014 8:49 pm UTC

So C++ lambdas have a slight flaw. You cannot access their this pointer, nor invoke their operator() from within themselves.

This gets in the way of recursive lambdas.

The easy way to do this is to create a type erasure (std::function), then capture it by reference, then create the lambda assigning it to the std::function. Inside the lambda, you invoke the std::function when you want to recurse.

This has pointless overhead, and it prevents you from returning from the current scope (as the captured reference's lifetime ends).

Here is my C++1y attempt to make a reasonably efficient recursive lambda:

Code: Select all

#include <functional>
#include <memory>
#include <iostream>
#include <type_traits>
#include <utility>


template<class F>
struct recursive {
private:
  F base;
public:

  template<class... Ts>
  auto operator()(Ts&&... ts) const
  {
    return base(base, std::forward<Ts>(ts)...);
  }

  recursive(recursive const&)=default;
  recursive(recursive&&)=default;
  recursive& operator=(recursive const&)=default;
  recursive& operator=(recursive &&)=default;
  recursive() = delete;
  template<typename L,typename=typename std::enable_if< std::is_convertible<L, F>::value>::type>
  recursive( L&& f ):
    base( std::forward<L>(f) )
  {}
};

template<class T>using decay_t = typename std::decay<T>::type;

template<class F>
recursive<decay_t<F>> recurse( F&& f ) { return std::forward<F>(f); }

auto get_recursive_function(int amt) {
  return recurse( [amt] (auto&& self, int count)->void {
    std::cout << count << std::endl;
    if (count > 0)
      self(self, count - amt);
  });
};

int main() {
  auto f = get_recursive_function(2);
  f(10);
}

We take a lambda: F: (F,X)->R
where X is the arguments, R the return type, and F the type of the lambda itself. As we don't have access to that type when we define F, we use auto&& to defer the binding.

Then, we have the function recurse: F->(X->R), which creates an object holding a copy of the lambda, and exposes an overridden operator() that invokes the lambda while passing it a copy of itself as its first argument. (I could equivalently pass it a copy of the recursion wrapper, and change the body of the lambda's recursive calls to self(count-amt) instead of self(self, count-amt)).

I'm guessing that there are patterns in more functional languages that I'm poorly replicating. Anyone have thoughts?

Compiled code: http://goo.gl/r6ddzI
Live example: http://coliru.stacked-crooked.com/a/4ba95aac15acde25
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Hacks and Snippets

Postby phlip » Wed Aug 06, 2014 11:26 pm UTC

Yakk wrote:I'm guessing that there are patterns in more functional languages that I'm poorly replicating. Anyone have thoughts?

It's called the fixed-point combinator, and it's useful for exactly the situation you describe - making recursive functions in an environment where a function is not allowed to explicitly refer to itself.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Coding: Hacks and Snippets

Postby Breakfast » Thu Aug 07, 2014 11:40 am UTC

phlip wrote:
Yakk wrote:I'm guessing that there are patterns in more functional languages that I'm poorly replicating. Anyone have thoughts?

It's called the fixed-point combinator, and it's useful for exactly the situation you describe - making recursive functions in an environment where a function is not allowed to explicitly refer to itself.


It's also how Scheme's define makes the named function recursive. I posted a C# version in the FT thread but no one seemed to notice.

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq;

namespace Scheme
{
    class Program
    {
        delegate T SelfApplicable<T>(SelfApplicable<T> self);

        static void Main(string[] args)
        {
            SelfApplicable<Func<Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>>, Func<dynamic, dynamic>>> Y = y => f => x => f(y(y)(f))(x);

            Func<Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>>, Func<dynamic, dynamic>> _define = Y(Y);

            List<int> _xs = new List<int>() { 1, 2, 3 };
            Func<dynamic, dynamic> _length = _define(length => xs =>
                !(xs as IEnumerable<int>).Any()
                    ? 0
                    : 1 + length((xs as IEnumerable<int>).Skip(1)));

            Console.WriteLine(_length(_xs));
            Console.ReadKey();
        }
    }
}

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Thu Aug 07, 2014 1:53 pm UTC

I blame your lack of typedefs.

Code: Select all

typedef Func<dynamic, dynamic> UnaryFunc;
typedef Func<Func<UnaryFunc, UnaryFunc>, UnaryFunc> MetaFunc;

SelfApplicable<MetaFunc> Y = y => f => x => f(y(y)(f))(x);

UnaryFunc _define = Y(Y);

List<int> _xs = new List<int>() { 1, 2, 3 };

UnaryFunc _length = _define(length => xs =>
         !(xs as IEnumerable<int>).Any()
              ? 0
              : 1 + length((xs as IEnumerable<int>).Skip(1)));

I am not happy with the name of MetaFunc but...

Are dynamic values in C# determined at runtime or compile time? (the auto in the C++ code above are typed at compile time).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Coding: Hacks and Snippets

Postby Breakfast » Thu Aug 07, 2014 2:24 pm UTC

Yakk wrote:Are dynamic values in C# determined at runtime or compile time? (the auto in the C++ code above are typed at compile time).

Runtime. Dynamic was introduced so that C# could interact with dynamically typed languages. The the compiler encounters the dynamic keyword it will emit IL for a variable of type object (everything in C# inherits from object) and mark it with an attribute specifying it as dynamic. The dynamic language runtime (DLR) will then handle things at runtime.

I personally don't think dynamic really fits into the C# mentality but it lets you do cool things that the somewhat limiting type inference of the regular language doesn't.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Thu Aug 07, 2014 3:41 pm UTC

Ah, so unavoidable overhead for no good reason. Sad that.

I'm annoyed that my implementation makes it tricky for the compiler to figure out that it is a recursive method, and reduce tail-call recursion into a loop. I think it might be possible with my newest version (posted above), but figuring out that the captured `amt` value is the same for every iteration might be tricky for the compiler.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Coding: Hacks and Snippets

Postby Breakfast » Thu Aug 07, 2014 4:46 pm UTC

yakk wrote:I'm annoyed that my implementation makes it tricky for the compiler to figure out that it is a recursive method, and reduce tail-call recursion into a loop. I think it might be possible with my newest version (posted above), but figuring out that the captured `amt` value is the same for every iteration might be tricky for the compiler.

Honestly, I learned C++ in college. Which means I didn't actually learn real C++ idioms, just some C with classes. Every time I see your code my mind boggles at your ability to seemingly just come up with things like Y Combinators. All of that is to say, I can't really make any contributions or intelligent suggestions to this particular problem. Having said that, do you have any recommendations for a C++ resource? I love to learn and I'd like to be able to be more useful in my contributions.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: Coding: Hacks and Snippets

Postby KnightExemplar » Thu Aug 07, 2014 8:41 pm UTC

Breakfast wrote:
yakk wrote:I'm annoyed that my implementation makes it tricky for the compiler to figure out that it is a recursive method, and reduce tail-call recursion into a loop. I think it might be possible with my newest version (posted above), but figuring out that the captured `amt` value is the same for every iteration might be tricky for the compiler.

Honestly, I learned C++ in college. Which means I didn't actually learn real C++ idioms, just some C with classes. Every time I see your code my mind boggles at your ability to seemingly just come up with things like Y Combinators. All of that is to say, I can't really make any contributions or intelligent suggestions to this particular problem. Having said that, do you have any recommendations for a C++ resource? I love to learn and I'd like to be able to be more useful in my contributions.


The YCombinator was created in Scheme and other functional languages. Its a multi-language trick that C++ sorta-learned how to do when it was updated in C++11. You don't "create" the YCombinator, you learn it in another language that it is native to and then try to apply it to other languages you know.

I can do currying in C++11 for example, but you shouldn't learn currying in C++11. It should be learned in Haskell or OCaml... languages much closer to the mathematical form of Lambda Calculus that invented the technique a hundred years ago.

A lot of coding tricks are just hacks that we've learned from the giants that came before us.
First Strike +1/+1 and Indestructible.

Breakfast
Posts: 117
Joined: Tue Jun 16, 2009 7:34 pm UTC
Location: Coming to a table near you

Re: Coding: Hacks and Snippets

Postby Breakfast » Thu Aug 07, 2014 8:50 pm UTC

KnightExemplar wrote:
Breakfast wrote:
yakk wrote:I'm annoyed that my implementation makes it tricky for the compiler to figure out that it is a recursive method, and reduce tail-call recursion into a loop. I think it might be possible with my newest version (posted above), but figuring out that the captured `amt` value is the same for every iteration might be tricky for the compiler.

Honestly, I learned C++ in college. Which means I didn't actually learn real C++ idioms, just some C with classes. Every time I see your code my mind boggles at your ability to seemingly just come up with things like Y Combinators. All of that is to say, I can't really make any contributions or intelligent suggestions to this particular problem. Having said that, do you have any recommendations for a C++ resource? I love to learn and I'd like to be able to be more useful in my contributions.


The YCombinator was created in Scheme and other functional languages. Its a multi-language trick that C++ sorta-learned how to do when it was updated in C++11. You don't "create" the YCombinator, you learn it in another language that it is native to and then try to apply it to other languages you know.

I can do currying in C++11 for example, but you shouldn't learn currying in C++11. It should be learned in Haskell or OCaml. Its much easier to understand certain concepts in different languages.


Sorry if I wasn't clear. I wasn't claiming that yakk "created" the Y Combinator. I know it can be done in multiple languages and I know what currying is. What I was mystified by was what yakk seems to be able to do with the C++ language and the fact that he presented us with some code, which to my knowledge, had made no previous reference to knowing what the Y Combinator was. Hence, me adding to phlip's comment:
phlip wrote:It's called the fixed-point combinator, and it's useful for exactly the situation you describe - making recursive functions in an environment where a function is not allowed to explicitly refer to itself.

I was assuming, maybe entirely incorrectly, that yakk had hit on the concept without having prior knowledge that it was a known thing.

KnightExemplar
Posts: 5489
Joined: Sun Dec 26, 2010 1:58 pm UTC

Re: Coding: Hacks and Snippets

Postby KnightExemplar » Thu Aug 07, 2014 9:05 pm UTC

I see... a lot of what I've been learning about with regards to this is just looking up C++11 features.

I personally read the draft standard (which was easy, as the committee was only cranking out parts of it every couple of weeks. So just reading the mailing list from 2008 onwards kept me up to date to the latest features), which is probably the most complete way to know all the new features. I skimmed through the draft standard when it finally came out.

Today, I'd say go through easier documents like from MSDN, Dr. Dobbs

http://msdn.microsoft.com/en-us/library/hh567368.aspx

http://www.drdobbs.com/cpp/lambdas-in-c11/240168241

http://www.artima.com/cppsource
First Strike +1/+1 and Indestructible.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Fri Aug 08, 2014 2:15 pm UTC

I have seen things like what I wrote in other languages. I was asking, basically, if I got the signatures right -- should it be F:= (F,X)->Y, or should it be F:= ((X->Y), X)->Y for my R : F->(X->Y), as I could implement either, and I figured more functional languages and programmers would know which one of these was a wiser choice. (The first has the type defined recursively, the second does not)

I have seen the Y-Combinator described in the lambda calculus, but I don't understand the lambda calculus, so that wasn't useful.

Reading standard proposals, boost code, solving problems in less than conventional ways (can I do it at compile time? Can I implement it as efficiently as if I hand-crafted the C equivalent but with type safety?), thinking of "how can I implement that neat python/haskell/scheme/C/Java/C# construct in C++ with far less overhead", etc.

Then do it for a few decades.

Oh, and there are some really top-notch presentations, like that one where in 25 minutes they build a type erased document with undo using relatively modern C++. The first time I saw it, I was boggled -- the latest, it made sense.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

jareds
Posts: 436
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Coding: Hacks and Snippets

Postby jareds » Mon Aug 11, 2014 6:33 am UTC

Yakk wrote:I have seen things like what I wrote in other languages. I was asking, basically, if I got the signatures right -- should it be F:= (F,X)->Y, or should it be F:= ((X->Y), X)->Y for my R : F->(X->Y), as I could implement either, and I figured more functional languages and programmers would know which one of these was a wiser choice. (The first has the type defined recursively, the second does not)

I have seen the Y-Combinator described in the lambda calculus, but I don't understand the lambda calculus, so that wasn't useful.

Your second variant, with F := ((X->Y, X)->Y, is basically a fixed-point combinator (it's just that F is uncurried), while the first is not.

With a fixed-point combinator, you have a function of type F that maps functions to functions: F:= (X->Y)->(X->Y).
The combinator, Y, maps such functions to their fixed-point: Y : F->(X->Y). The phrase "fixed-point" is being used in its normal way: if a fixed-point of f is g, then f(g)=g. So, f(Y(f))=Y(f), which is to say Y(f)=f(Y(f)).

On the one hand, this has a certain mathematical elegance and avoids the boilerplate argument passing of "self" to "self". On the other hand, your first variant looks kind of like a work-around for the lack of the language feature from functional languages that would typically be used for a locally-defined recursive function: a recursive binding construct.

Brief digression:
Spoiler:
Of course, all C++ declarations are recursively scoped: the initializer is in the scope of the declarator. But "auto" declarations don't allow reference to the declarator within its initializer, and thus, as you implied, the "easy way" to do this is something like:

Code: Select all

std::function<int(int)> f([&f] (int n)->int { return n <= 0 ? 1 : n * f(n-1); });
std::cout << f(10) << std::endl;
and accordingly I view your code as a work-around that improves on that (avoiding std::function and the capture of a local variable by reference) by making the captured variable a function argument.
Recall that functional languages generally do not have the statement/expression distinction that imperative languages do, and almost invariably have a variable-binding construct that is syntactically an expression. For example, "let" in Scheme:

Code: Select all

(map (let ((a 77))
       (lambda (x) (+ x a)))
     '(1 2 3))
;Value: (78 79 80)

But "let" initializers are not in the scope of the "let". The following "let" is well-defined and equals 6:

Code: Select all

(define a 1)
(define b 2)
(let ((a 5)
      (b a))
  (+ a b))

Thus, there is "letrec", where the initializers are in the scope of the "letrec" (but it is illegal for evaluation of the initializer to read one of the bound variables):

Code: Select all

(map (letrec ((fact (lambda (n) 
                      (if (<= n 0) 1 (* n (fact (- n 1)))))))
       fact)
     '(0 5 10))
;Value: (1 120 3628800)

You can see that "(recurse (lambda (self n) [...]))" is only slightly shorter than "(letrec ((self (lambda (n) [...]))) self)", so neither the first variant of your construct (nor the fixed-point combinator, in practice), gain much over built-in language constructs in most functional languages. But when "letrec" is too verbose, there already is a standard shorter form for this situation, rec, which is just syntactic sugar for that letrec:

Code: Select all

(rec (func args) body) => (letrec ((func (lambda (args) body))) func)
(Note that SRFI's example implementation of "rec" is a "hygenic macro", not a function, which means that if you want to ignore Scheme's macro system, it makes more sense to think of "rec" as a language construct than as a function.)

Hopefully, it is now clear why I said that your first variant resembles the sort of recursive binding construct used in practice for local recursive functions. Just don't call it a "fixed-point" anything.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11048
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Coding: Hacks and Snippets

Postby Yakk » Wed Aug 13, 2014 7:07 pm UTC

Ah yes, you can rework it as:

Code: Select all

   template<class F>
   struct recursive_call
   {
      F f;
      // uncurried version:
      template<class...Ts>
      auto operator()(Ts&&...ts)
      -> typename std::result_of< F( recursive_call )( Ts... ) >::type
      {
         return f( *this )( std::forward<Ts>(ts)...);
      }
       recursive_call(recursive_call const&) = default;
       recursive_call& operator=(recursive_call const&)=default;
       recursive_call( F f_in ):f(std::forward<F>(f_in)) {}
       explicit operator bool() const { bool retval(f); return retval; } // if `f` supports it
    };

   // Pass recurse a F: (A->B)->(A->B) lambda
    // and it will generate an A->B recursive closure of it
    template<class T>
   recursive_call<decay_t<T>> recurse( T&& t )
   {
      return { std::forward<T>(t) };
   }

        std::function<void(int)> count_down( int step ) {
          return recurse( [step]( std::function<void(int x)> self ) {
            return [step, self](int x) {
              if (max < 0) return;
              std::cout << x << "\n";
              self( x-step );
            };
          });
        }

which involves a double-lambda instead of an extra argument in the lambda.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Sizik
Posts: 1159
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Coding: Hacks and Snippets

Postby Sizik » Tue Oct 14, 2014 9:15 pm UTC

Forgot about this thread, so reposting this here instead:
Just for kicks, I wanted to try to generate doubles from a uniform distribution over the entire range of double values.

(Java)

Code: Select all

public static void main(String[] args) {

   Random rand = new Random();
   byte[] exp_b = new byte[256]; // for exponent generation
   while(true)
   {
      // Random significand
      long sig = rand.nextLong();
      sig &= 0xFFFFFFFFFFFFFL;

      // Generate random exponent such that
      // exponent e is twice as likely as e-1.
      rand.nextBytes(exp_b);
      long exp = 2047;
      for(int i = 2047; i >= 0; i--)
      {
         int index = i / 8;
         int rel = 1 << (i % 8);
         int bit = exp_b[index] & rel;
         
         if(bit == 1)
            break;
         else
            exp--;
      }

      // Random sign bit
      long sign = rand.nextBoolean() ? Long.MIN_VALUE : 0;

      // Put it together
      long l = sign | (exp << 52) | sig;

      // print for debugging
      System.out.println("Sign: " + Long.toBinaryString(sign));
      System.out.println("Exp: " + Long.toBinaryString(exp << 52));
      System.out.println("Sig: " + Long.toBinaryString(sig));
      System.out.println("Double: " + Long.toBinaryString(l));

      // Convert to double
      double d = Double.longBitsToDouble(l);
      System.out.println("d:" + d);

      // wait and loop until stopped
      try {
         Thread.sleep(1000);
      } catch (InterruptedException e) {
         break;
      }
   }
}   


Predictably, most of the values fall in the 10^300 range.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 7 guests