W B Langdon Non-GP 2022 Abstracts

W.B.Langdon . 7 Oct 2022 2017 papers , full list

Generating Random Infix Expressions for GNU coreutils expr

William B. Langdon, Dept of Computer Science, University College London, Technical Report 10157010, 25 August 2022, UCL Discovery. doi:10.14324/000.rp.10157010 PDF


We use the recent random_tree() addition to GPquick [arXiv:2001.04505] to uniformly sample in linear time the space of binary trees. A unix gawk script transforms these to uniform random infix expressions, as used by Free Software Foundation GNU core utility expr. It converts from Lisp s-expression like prefix representation used by GPquick to bracketed infix expressions, e.g. "(" 3050 "=" 5514 ")" "-" 3073. gawk randomly labels internal tree nodes with the 14 functions known to expr and replaces leafs with randomly chosen positive integers up to 32768. About 80 percent of random expressions are rejected, since they cause expr to fail, typically due to division by zero.