{
"cells": [
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"from buffaloparse import parse, parses\n",
"from IPython.display import Image\n",
"from IPython.core.display import HTML\n",
"from programmachine import Register, Instructions\n",
"from buffalotoprogrammachine import interpret"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" > whoami"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" Chigozie Nri\n",
" Scientific Software Developer at Enthought\n",
" Bovine Esoteric Computational Syntactician"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## \"Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo\"\n",
"\n",
" — Dmitri Borgmann\n",
"\n",
" — William Rapaport (independently)\n",
"\n",
" — Annie Senghas (independently)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"slideshow": {
"slide_type": "fragment"
},
"tags": [
"to_remove"
]
},
"outputs": [
{
"data": {
"text/html": [
"
"
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"HTML(\"\")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"https://buffalofishpolice.tumblr.com/"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
" grammar_string = \"\"\"\n",
" S -> V | VP\n",
" NP -> NP NP V | A N | N\n",
" VP -> NP V NP | NP V\n",
" V -> 'buffalo'\n",
" N -> 'buffalo'\n",
" A -> 'Buffalo'\n",
" \"\"\""
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "fragment"
},
"tags": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" S \n",
" | \n",
" VP \n",
" ___________|_____________________________ \n",
" NP | | \n",
" _____________|___________________ | | \n",
" NP NP | | NP \n",
" _____|_____ _____|_____ | | _____|_____ \n",
" A N A N V V A N \n",
" | | | | | | | | \n",
"Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo\n",
"\n"
]
}
],
"source": [
"parsed = parse('Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo')\n",
"for tree in parsed:\n",
" tree.pretty_print()"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"# The Program Machine program we are aiming for\n",
"src = \"\"\"\n",
"buffalo 2\n",
"Buffalo 0\n",
"\n",
"JZ buffalo 4\n",
"DEC buffalo\n",
"INC Buffalo\n",
"JZ buffalo 0\n",
"\"\"\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"How do we represent this with only buffaloes?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Each sentence will represent one line"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"The first two lines are special, as they represent the initial state of the registers."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
" # The register \"buffalo\" contains the value 2:\n",
" Buffalo buffalo buffalo buffalo Buffalo buffalo buffalo.\n",
" xxxxxxxxxxxxxxx ------- xxxxxxx ------- xxxxxxx -------\n",
" variable variable variable\n",
" 1s place 2s place 4s place\n",
" 1 x 0 + 2 x 1 + 4 x 0 = 2\n",
"\n",
"\n",
" # The register \"Buffalo\" contains the value 0:\n",
" Buffalo buffalo buffalo buffalo.\n",
" xxxxxxxxxxxxxxx ------- xxxxxxx\n",
" variable\n",
" 1s place\n",
" 1 x 0 = 0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Notice: Little-endian. What is 4 x 0 doing at the end of value 2? Why are we bothering with fixed values?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"After the initial state of the registers comes the instructions. Remember, there are 3 possible instructions: JZ, DEC and INC"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"\n",
"\n",
" # DEC buffalo\n",
" Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo.\n",
" xxxxxxxxxxxxxxx ------- xxxxxxx ------- xxxxxxx ------- xxxxxxx\n",
" variable variable variable\n",
" DEC/INC DEC buffalo\n",
"\n",
" # INC Buffalo\n",
" Buffalo buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo.\n",
" xxxxxxxxxxxxxxx ------- xxxxxxx ------- xxxxxxx ------- xxxxxxx\n",
" variable variable variable\n",
" DEC/INC INC Buffalo\n",
"\n",
" # JZ buffalo 0\n",
" Buffalo buffalo Buffalo buffalo buffalo buffalo buffalo buffalo.\n",
" xxxxxxxxxxxxxxx ------- xxxxxxx ------- xxxxxxx ------- xxxxxxx\n",
" variable variable variable \n",
" JZ buffalo 1 x 0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Will every possible buffaloscript instruction be valid English? Eh, probably."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"I checked the first 10000, every one worked with a sufficient number of trailing buffaloes. At most, sentence 8191 needed 14 trailing buffaloes to parse."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"program = \"Buffalo buffalo buffalo buffalo Buffalo buffalo buffalo. 🐃Swamp buffalo enjoy wallowing in mudholes they make with their horns🐃 Buffalo buffalo buffalo buffalo. Buffalo buffalo Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo Buffalo buffalo. Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo. Buffalo buffalo buffalo buffalo Buffalo buffalo Buffalo buffalo buffalo buffalo 🐃It's true!🐃. Buffalo buffalo Buffalo buffalo buffalo buffalo buffalo buffalo.\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Convert to Minsky Program Machine"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "slide"
},
"tags": [
"to_remove"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Initial Register Values\n",
"-----------------------\n",
"buffalo: 2\n",
"Buffalo: 0\n",
"\n",
"Instructions\n",
"------------\n",
"1: JZ buffalo 4\n",
"2: DEC buffalo\n",
"3: INC Buffalo\n",
"4: JZ buffalo 0\n",
"\n",
"Run program\n",
"-----------\n",
"line 1: register buffalo is not empty, doing nothing\n",
"line 2: decreasing register buffalo from 2 to 1\n",
"line 3: increasing register Buffalo from 0 to 1\n",
"line 4: register buffalo is not empty, doing nothing\n",
"line number out of range, halting\n",
"\n",
"Final Register Values on Halt\n",
"-----------------------------\n",
"buffalo: 1\n",
"Buffalo: 1\n"
]
}
],
"source": [
"src = interpret(program)\n",
"instructions = Instructions(src)\n",
"print(f'Initial Register Values\\n-----------------------')\n",
"registers = instructions.registers\n",
"for key, val in zip(registers.keys(),\n",
" [str(register.value) for register in registers.values()]):\n",
" print(f'{key}: {val}')\n",
"print()\n",
"instructions_with_linenumbers = [f'{i+1}: {\" \".join(instructions.instruction_list[i])}' for i in range(len((instructions.instruction_list)))]\n",
"instruction_print = '\\n'.join(instructions_with_linenumbers)\n",
"print(f\"\"\"Instructions\n",
"------------\n",
"{instruction_print}\n",
"\"\"\")\n",
"print(\"Run program\\n-----------\")\n",
"instructions.interpret()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Further reading\n",
"- This repo: https://github.com/chigozienri/buffaloscript/\n",
"- Another python implementation of a silly Minsky register machine with fractions (FRACTRAN, by John Conway): https://github.com/chigozienri/fractran\n",
"- History of the buffalo sentence: https://cse.buffalo.edu/~rapaport/buffalobuffalo.html\n",
"- Graphical illustration: https://buffalofishpolice.tumblr.com/\n",
" "
]
}
],
"metadata": {
"celltoolbar": "Slideshow",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}