The navigation bar for a winning entry now has a "_Original C_" link
(between the ✅ and the Inventory on the right hand side) so that one
may easily view the original C code that was submitted for IOCCC judging.
Ran `make www timestamp` to perform the above.
806 lines
33 KiB
HTML
806 lines
33 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
||
<!-- START: two lines up starts content from: inc/top.default.html -->
|
||
|
||
<!-- END: this line ends content from: inc/top.default.html -->
|
||
<!-- START: this line starts content from: inc/head.default.html -->
|
||
|
||
<head>
|
||
<link rel="stylesheet" href="../../ioccc.css">
|
||
<link href="https://fonts.googleapis.com/css2?family=Outfit:wght@100..900&display=swap" rel="stylesheet">
|
||
<meta charset="utf-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
|
||
<title>2019/lynn - Most functional compiler</title>
|
||
<link rel="icon" type="image/x-icon" href="../../favicon.ico">
|
||
<meta name="description" content="2019 IOCCC entry lynn - Most functional compiler">
|
||
<meta name="keywords" content="IOCCC, 2019, IOCCC 2019, IOCCC entry, lynn, Most functional compiler">
|
||
</head>
|
||
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!! DO NOT MODIFY THIS FILE - This file is generated by a tool !!! -->
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
|
||
<!-- END: this line ends content from: inc/head.default.html -->
|
||
|
||
<!-- -->
|
||
<!-- This web page was formed via the tool: bin/readme2index.sh -->
|
||
<!-- The content of main section of this web page came from: 2019/lynn/README.md -->
|
||
<!-- -->
|
||
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2019/lynn/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2019/lynn/README.md !!! -->
|
||
<!-- !!! Do not modify this web page, instead modify the file: 2019/lynn/README.md !!! -->
|
||
<!-- !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! -->
|
||
|
||
<!-- Markdown content was converted into HTML via the tool: bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content from: inc/body.default.html -->
|
||
|
||
<body>
|
||
|
||
<!-- END: this line ends content from: inc/body.default.html -->
|
||
<!-- START: this line starts content from: inc/topbar.default.html -->
|
||
|
||
<div class="theader">
|
||
<nav class="topbar">
|
||
<div class="container">
|
||
<div class="logo">
|
||
<a href="../../index.html" class="logo-link">
|
||
IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="topbar-items">
|
||
<div class="item">
|
||
<span class="item-header">
|
||
Entries
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../years.html" class="sub-item-link">
|
||
Winning entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../authors.html" class="sub-item-link">
|
||
Winning authors
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../location.html" class="sub-item-link">
|
||
Location of authors
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../bugs.html" class="sub-item-link">
|
||
Bugs and (mis)features
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#fix_an_entry" class="sub-item-link">
|
||
Fixing entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#fix_author" class="sub-item-link">
|
||
Updating author info
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
Status
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../news.html" class="sub-item-link">
|
||
News
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../status.html" class="sub-item-link">
|
||
Contest status
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../next/rules.html" class="sub-item-link">
|
||
IOCCC rules
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../next/guidelines.html" class="sub-item-link">
|
||
IOCCC guidelines
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../markdown.html" class="sub-item-link">
|
||
Markdown guidelines
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../SECURITY.html" class="sub-item-link">
|
||
Security policy
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
FAQ
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html" class="sub-item-link">
|
||
Frequently asked questions
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../quick-start.html#enter" class="sub-item-link">
|
||
Enter the IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#compiling" class="sub-item-link">
|
||
Compiling entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#running_entries" class="sub-item-link">
|
||
Running entries
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../faq.html#help" class="sub-item-link">
|
||
How to help
|
||
</a>
|
||
</div>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="item">
|
||
<span class="item-header">
|
||
About
|
||
</span>
|
||
|
||
<div class="sub-item">
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../index.html" class="sub-item-link">
|
||
Home page
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../social.html" class="sub-item-link">
|
||
IOCCC social media
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../about.html" class="sub-item-link">
|
||
About the IOCCC
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../judges.html" class="sub-item-link">
|
||
The judges
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../thanks-for-help.html" class="sub-item-link">
|
||
Thanks for the help
|
||
</a>
|
||
</div>
|
||
|
||
<div class="outfit-font">
|
||
<a href="../../contact.html" class="sub-item-link">
|
||
Contact us
|
||
</a>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</nav>
|
||
|
||
<div class="header-mobile-menu">
|
||
<noscript>
|
||
<a href="../../nojs-menu.html" class="topbar-js-label">
|
||
Please Enable JavaScript
|
||
</a>
|
||
</noscript>
|
||
|
||
<button id="header-open-menu-button" class="topbar-mobile-menu">
|
||
<img
|
||
src="../../png/hamburger-icon-open.png"
|
||
alt="hamburger style menu icon - open state"
|
||
width=48
|
||
height=48>
|
||
</button>
|
||
|
||
<button id="header-close-menu-button" class="hide-content">
|
||
<img
|
||
src="../../png/hamburger-icon-closed.png"
|
||
alt="hamburger style menu icon - closed state"
|
||
width=48
|
||
height=48>
|
||
</button>
|
||
|
||
<div id="mobile-menu-panel" class="hide-content">
|
||
<div class="mobile-menu-container">
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
Entries
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../years.html">
|
||
Winning entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../authors.html">
|
||
Winning authors
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../location.html">
|
||
Location of authors
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../bugs.html">
|
||
Bugs and (mis)features
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#fix_an_entry">
|
||
Fixing entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#fix_author">
|
||
Updating author info
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../thanks-for-help.html">
|
||
Thanks for the help
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
|
||
<div class="mobile-menu-item">
|
||
Status
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../news.html">
|
||
News
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../status.html">
|
||
Contest status
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../next/rules.html">
|
||
IOCCC rules
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../next/guidelines.html">
|
||
IOCCC guidelines
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../markdown.html">
|
||
Markdown guidelines
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../SECURITY.html">
|
||
Security policy
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
FAQ
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html">
|
||
Frequently asked questions
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../quick-start.html#enter">
|
||
Enter the IOCCC
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#compiling">
|
||
Compiling entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#running_entries">
|
||
Running entries
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../faq.html#help">
|
||
How to help
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div class="mobile-menu-wrapper">
|
||
<div class="mobile-menu-item">
|
||
About
|
||
</div>
|
||
<div class="mobile-submenu-wrapper">
|
||
|
||
<a class="mobile-submenu-item" href="../../index.html">
|
||
Home page
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../social.html">
|
||
IOCCC social media
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../about.html">
|
||
About the IOCCC
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../judges.html">
|
||
The judges
|
||
</a>
|
||
|
||
<a class="mobile-submenu-item" href="../../contact.html">
|
||
Contact us
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<script>
|
||
var headerOpenMenuButton = document.getElementById("header-open-menu-button");
|
||
var headerCloseMenuButton = document.getElementById("header-close-menu-button");
|
||
var mobileMenuPanel = document.getElementById("mobile-menu-panel");
|
||
|
||
headerOpenMenuButton.addEventListener("click", () => {
|
||
headerOpenMenuButton.classList.remove("topbar-mobile-menu");
|
||
headerOpenMenuButton.classList.add("hide-content");
|
||
|
||
headerCloseMenuButton.classList.remove("hide-content");
|
||
headerCloseMenuButton.classList.add("topbar-mobile-menu");
|
||
|
||
mobileMenuPanel.classList.remove("hide-content");
|
||
mobileMenuPanel.classList.add("topbar-mobile-panel");
|
||
});
|
||
|
||
headerCloseMenuButton.addEventListener("click", () => {
|
||
headerCloseMenuButton.classList.remove("topbar-mobile-menu");
|
||
headerCloseMenuButton.classList.add("hide-content");
|
||
|
||
mobileMenuPanel.classList.add("hide-content");
|
||
mobileMenuPanel.classList.remove("topbar-mobile-panel");
|
||
|
||
headerOpenMenuButton.classList.add("topbar-mobile-menu");
|
||
headerOpenMenuButton.classList.remove("hide-content");
|
||
});
|
||
</script>
|
||
|
||
<!-- END: this line ends content from: inc/topbar.default.html -->
|
||
<!-- START: this line starts content from: inc/header.default.html -->
|
||
|
||
<div class="header">
|
||
<a href="../../2011/zucker/index.html">
|
||
<img src="../../png/ioccc.png"
|
||
alt="IOCCC image by Matt Zucker"
|
||
width=300
|
||
height=110>
|
||
</a>
|
||
<h1>The International Obfuscated C Code Contest</h1>
|
||
<h2>2019/lynn - Most functional compiler</h2>
|
||
<h3>Haskell compiler</h3>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/header.default.html -->
|
||
<!-- START: this line starts content from: inc/navbar.mid.html -->
|
||
|
||
<div class="navbar">
|
||
<a class="Left" href="../karns/index.html">← 2019/karns</a>
|
||
<a class="Left" href="../index.html">↑ 2019 ↑</a>
|
||
<a class="Left" href="../mills/index.html">2019/mills →</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/prog.c">C code</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/Makefile">Makefile</a>
|
||
<a class="Right" href="#inventory">Inventory</a>
|
||
<a class="Right" href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/prog.orig.c">Original C</a>
|
||
<a class="Right" href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2019%2Flynn%2Findex.html">✓</a>
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/navbar.mid.html -->
|
||
<!-- START: this line starts content from: inc/before-content.default.html -->
|
||
|
||
<div class="content" id="content">
|
||
|
||
<!-- END: this line ends content from: inc/before-content.default.html -->
|
||
<!-- START: this line starts content for HTML phase 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-author.sh -->
|
||
|
||
<h2 id="author">Author:</h2>
|
||
<ul>
|
||
<li>Name: <a href="../../authors.html#Ben_Lynn">Ben Lynn</a><br>
|
||
Location: <a href="../../location.html#US">US</a> - <em>United States of America</em> (<em>United States</em>)</li>
|
||
</ul>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-author.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 20 by: bin/output-index-author.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
|
||
<!-- BEFORE: 1st line of markdown file: 2019/lynn/README.md -->
|
||
<h2 id="to-build">To build:</h2>
|
||
<pre><code> make</code></pre>
|
||
<h3 id="bugs-and-misfeatures">Bugs and (Mis)features:</h3>
|
||
<p>The current status of this entry is:</p>
|
||
<blockquote>
|
||
<p><strong>STATUS: INABIAF - please DO NOT fix</strong></p>
|
||
</blockquote>
|
||
<p>For more detailed information see <a href="../../bugs.html#2019_lynn">2019/lynn in bugs.html</a>.</p>
|
||
<h2 id="to-use">To use:</h2>
|
||
<pre><code> ./prog</code></pre>
|
||
<h2 id="try">Try:</h2>
|
||
<pre><code> ./try.sh</code></pre>
|
||
<h2 id="judges-remarks">Judges’ remarks:</h2>
|
||
<p>A fully functional compiler. The example prints out the 30th <a href="https://en.wikipedia.org/wiki/Fibonacci_sequence">Fibonacci
|
||
number</a>.</p>
|
||
<h2 id="authors-remarks">Author’s remarks:</h2>
|
||
<h3 id="remarks">Remarks:</h3>
|
||
<p>A Haskell compiler. Supports a subset of Haskell more than large enough to
|
||
self-host. Like GHC with custom language extensions:</p>
|
||
<ul>
|
||
<li><p><code>WeDontServeYourType</code>: Compilation failing because of inscrutable type
|
||
checking rules? Confused by the ever-growing mire of extensions to the type
|
||
system? The solution is simple: no type checking. It also means no
|
||
typeclasses. Just pass dictionaries explicitly.</p></li>
|
||
<li><p><code>ZeroPauseGarbageCollection</code>: Instead of disruptive stop-the-world garbage
|
||
collection, we only tidy up when the world stops on its own accord, that is,
|
||
on program termination.</p></li>
|
||
<li><p><code>OneHundredPercentPure</code>: Gone is the catch-all lawless IO monad. And no
|
||
trace of those scary <code>unsafeThisAndThat</code> functions. All functions must be pure.</p></li>
|
||
<li><p><code>SyntaxForTheMasses</code>: See below.</p></li>
|
||
</ul>
|
||
<h3 id="building">Building:</h3>
|
||
<p>Build the compiler:</p>
|
||
<pre><code> cc -o prog prog.c</code></pre>
|
||
<h3 id="demos">Demos:</h3>
|
||
<h4 id="fibonacci-numbers">Fibonacci numbers:</h4>
|
||
<p>Test the compiler on <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/fib.hs">fib.hs</a>:</p>
|
||
<pre><code> (./prog < fib.hs ; cat prog.c) > fib.c</code></pre>
|
||
<p>Compiling the output produces a binary that prints the 30th Fibonacci number.</p>
|
||
<p>The file <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/ghcfib.hs">ghcfib.hs</a>
|
||
includes <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/fib.hs">fib.hs</a> with some glue code,
|
||
and shows GHC also accepts our subset of Haskell:</p>
|
||
<pre><code> ghc ghcfib.hs</code></pre>
|
||
<h4 id="self-hosting-compiler">Self-hosting compiler:</h4>
|
||
<p>To avoid revealing the original Haskell source, we
|
||
instead provide <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/hint.hs">hint.hs</a>, the output of a certain stage of the
|
||
compiler when run on itself. This intermediate output is hopefully difficult to
|
||
understand, yet is accepted by our compiler:</p>
|
||
<h3 id="notice-to-those-who-wish-for-a-greater-challenge">NOTICE to those who wish for a greater challenge:</h3>
|
||
<p><strong>If you want a greater challenge, don’t read any further</strong>:
|
||
just try to understand the program without running the command below.</p>
|
||
<p>If you get stuck, come back and run the following command:</p>
|
||
<pre><code> (./prog < hint.hs ; cat prog.c) > hint.c
|
||
make hint
|
||
./hint</code></pre>
|
||
<p>The output program behaves like the compiler itself.</p>
|
||
<p>Unlike the original source from which it is derived, GHC fails to compile
|
||
<a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/hint.hs">hint.hs</a>. This is because values have been replaced with their <a href="https://en.wikipedia.org/wiki/Mogensen-Scott_encoding">Scott
|
||
encodings</a>
|
||
by this stage, which messes up type-checks; we’d need <code>equirecursive</code> types for
|
||
it to work.</p>
|
||
<h4 id="regexes">Regexes:</h4>
|
||
<p>The file <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/lol.hs">lol.hs</a> contains an adaptation of <a href="https://www.cs.dartmouth.edu/~doug/nfa.pdf">Doug McIlroy’s elegant code from
|
||
“Enumerating the strings of regular
|
||
languages”</a>. We exercise it by
|
||
showing the first entries of the length-ordered list of all strings consisting
|
||
of the characters <code>a</code> and <code>b</code> that contain an even number of <code>a</code>s.</p>
|
||
<pre><code> (./prog < lol.hs ; cat prog.c) > lol.c
|
||
make lol
|
||
./lol</code></pre>
|
||
<p>A GHC wrapper is provided:</p>
|
||
<pre><code> ghc ghclol.hs</code></pre>
|
||
<h3 id="strongly-connected-components">Strongly-connected components:</h3>
|
||
<p>See <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/scc.hs">scc.hs</a>, and its GHC wrapper <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/ghcscc.hs">ghcscc.hs</a>,
|
||
for an elegant way to print the strongly-connected components of a graph in reverse topological
|
||
order.</p>
|
||
<pre><code> (./prog < scc.hs ; cat prog.c) > scc.c</code></pre>
|
||
<p>It expects the input to be in a similar format as a previous entry
|
||
(2018 vokes). For example:</p>
|
||
<pre><code> make scc
|
||
./scc < example-1.txt
|
||
./scc < example-2.txt</code></pre>
|
||
<p>The output should agree, though our program omits line numbers and does not
|
||
sort entries within a line. (Also, our program only treats spaces as
|
||
whitespace, and supports any non-space character in a vertex name.)</p>
|
||
<h3 id="syntax">Syntax</h3>
|
||
<p>Some claim Haskell syntax is frightening because braces and semicolons are
|
||
optional. Some complain about a zoo of twisty little operators, all alike. Our
|
||
compiler addresses such concerns by making braces and semicolons compulsory,
|
||
disabling layout-based rules, making every operator left-associative with same
|
||
precedence, and only defining 6 primitive functions:</p>
|
||
<pre><code> : + - * / <=</code></pre>
|
||
<p>The arithmetic operations behave as they do in C on <code>unsigned int</code>s, and <code>(:)</code> is
|
||
Haskell’s <code>cons</code> function. Like Haskell and unlike C, <code>(<=)</code> returns a <code>Bool</code>
|
||
(which are Church booleans behind the scenes) and not an <code>Int</code>.</p>
|
||
<p>No ifs, ands, or buts. Define them yourself. No tuples. Who needs them when
|
||
algebraic data types delivers a better product? There is no do. No where. No
|
||
list comprehensions. No unary operators.</p>
|
||
<p>Let expressions and operator sections are supported.</p>
|
||
<p>Within global scope or a let expression, each definition can only refer to
|
||
itself or previous definitions. This implies we can only achieve mutual
|
||
recursion by having one function pass itself to others.</p>
|
||
<h3 id="caveats">Caveats</h3>
|
||
<p>The only primitive type is <code>Int</code>. In particular, they represent characters. To
|
||
interoperate with GHC, our compiler treats any undefined functions as the
|
||
<code>identity</code> function, so that we may freely use <code>ord</code> and <code>chr</code> (or <code>fromEnum</code> and
|
||
<code>toEnum</code>) to make our code acceptable to both compilers.</p>
|
||
<p>The main function is the last function to successfully parse. It should have
|
||
type <code>[Int] -> [Int]</code>, and our compiler treats this like the function passed
|
||
into <code>Prelude.interact</code>, that is, the entire standard input is passed to this
|
||
function, and the result is printed to standard output.</p>
|
||
<p><code>Bool</code> must be defined as:</p>
|
||
<pre><code> data Bool = True | False;</code></pre>
|
||
<p>so that it matches the Scott-encoded booleans internally used by the primitive
|
||
function <code>(<=)</code>.</p>
|
||
<p>The alternatives in a <code>case</code> expressions must list every data constructor in
|
||
the order they are defined. For example, if we have:</p>
|
||
<pre><code> data Foo a b = Bar a | Baz | Qux Int [b]</code></pre>
|
||
<p>then a <code>case</code> expression that examines a term of this type must have the form:</p>
|
||
<pre><code> case x of
|
||
{ Bar a -> ...
|
||
; Baz -> ...
|
||
; Qux n bs -> ...
|
||
}</code></pre>
|
||
<p>We stress braces and semicolons are required. Our fussy parser treats
|
||
semicolons as separators, not terminators.</p>
|
||
<p>The effect of erroneous input is undefined. It may be best to develop with GHC,
|
||
but even then, be mindful of changes needed because of issues caused by the
|
||
uniform operator precedence and the touchy format of <code>case</code> alternatives.</p>
|
||
<h3 id="why">Why?</h3>
|
||
<p>One-letter variable names abound in IOCCC entries, and for good reason. These
|
||
tiny pieces of confetti are hard to read, and leave room for more code. Then
|
||
why not go further and use zero-letter variable names? That is, tacit
|
||
programming or point-free style.</p>
|
||
<p>I had been playing with an algorithm devised by Oleg Kiselyov that effortlessly
|
||
and efficiently eliminates those pesky variables, leaving behind terms composed
|
||
from a small set of combinators. No need for lambda lifting or supercombinators.</p>
|
||
<p>By adding a handful of lines of mostly parsing code, we get a Haskell compiler,
|
||
or rather, a compiler that accepts a subset of Haskell sufficiently large to
|
||
self-host. You might say I wrote a tool for this contest, then ran it on itself
|
||
to make an entry for it.</p>
|
||
<h3 id="obfuscation-techniques">Obfuscation techniques:</h3>
|
||
<p>Even with Kiselyov’s algorithm and some term rewriting, the compiler only fit
|
||
after compression, which naturally obfuscates the code. More tricks were needed
|
||
to fit within the size limits.</p>
|
||
<ul>
|
||
<li>One-letter variables, until enough is done to banish variables completely.</li>
|
||
<li>Ipse dixit. Near the end, the code declares itself to be an obfuscated
|
||
program. (There is also an exhortation intended for the judges in a similar
|
||
format earlier in the source.)</li>
|
||
<li>Typical C mischief: pre- and post-increment, commutative array indexing,
|
||
ternary operators, and so on.</li>
|
||
<li>Huffman coding.</li>
|
||
<li>Base-85 because high bits are frowned upon.</li>
|
||
<li>Mixed radix encoding to game iocccsize. From a past entry,
|
||
<a href="../../2018/bellard/index.html">2018/bellard</a>, it seems 9 11 12 32 are the only
|
||
whitespace octets that may appear verbatim in string literals.</li>
|
||
<li>Choosing what to encode in Huffman/base-85 and what to encode in mixed radix
|
||
was a delicate balancing act. In the end, I only had a few bytes to spare, which
|
||
I spent on gratuitous confusion.</li>
|
||
<li>The effects of some functions depend on the order their arguments are
|
||
evaluated, yet the program works either way. Why?</li>
|
||
<li>Ugly macros for the runtime system’s jump table for lazy reduction. A previous
|
||
entry, <a href="../../2013/endoh1/index.html">2013/endoh1</a>, has a cuter solution, which I
|
||
avoid because of originality concerns and also because my combinators are
|
||
compressed.</li>
|
||
<li>Relies on the inability of C comments to nest.</li>
|
||
<li>Cheaper and more complicated to print comma-separated <code>int</code>s (and header and
|
||
footer) in C.</li>
|
||
<li>Primitive functions use a trick described in depth by <a href="https://www.cs.york.ac.uk/fp/reduceron/jfp-reduceron.pdf">Naylor and Runciman,
|
||
“The Reduceron reconfigured and
|
||
re-evaluated”</a>. We
|
||
represent the integer <code>n</code> with a term equivalent to <code>Y(BT)n</code>; it works because
|
||
<code>Y(BT)ne = e(Y(BT)n)</code>.</li>
|
||
<li>A sentinel in the heap often confused me, so ought to confuse others.</li>
|
||
</ul>
|
||
<p>Other obfuscation techniques are better appreciated after decoding the
|
||
compiler. See <a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/hint.hs">hint.hs</a>.</p>
|
||
<ul>
|
||
<li>Mercilessly point-free. Everything is a combinator.</li>
|
||
<li>Scott encoding. Everything is a combinator.</li>
|
||
<li>Sum types are oddly ordered and may even contain unused data constructors to
|
||
reduce code duplication. (In C terms, <code>union</code>s may have extra fields, and they’re
|
||
ordered in such a way so we can reuse code to access certain fields.)</li>
|
||
<li>The <code>undefined</code> function compiles to the <code>(.)</code> function.</li>
|
||
<li>Replaced the only <code>(&&)</code> with <code>(||)</code> and <code>not</code> using De Morgan’s law, which
|
||
makes some comparisons less comprehensible.</li>
|
||
<li><a href="http://okmij.org/ftp/tagless-final/ski.pdf">Kiselyov only published “λ to SKI, Semantically” last
|
||
year</a>.</li>
|
||
<li>Recursion via the fixpoint (<code>Y</code>) combinator, which is represented by the
|
||
variable <code>""</code> during one stage of compilation.</li>
|
||
<li>Involves theory that may be less familiar to C programmers: maps, folds,
|
||
parser combinators, lambda calculus, bracket abstraction, denotational
|
||
semantics, etc.</li>
|
||
</ul>
|
||
<h3 id="warnings">Warnings:</h3>
|
||
<p>On my system, it compiles cleanly with <code>-Wall</code> with older standards, e.g.
|
||
<code>-std=c89</code>, but less cleanly if <code>-pedantic</code> is also supplied.</p>
|
||
<p>Compiling the compiler output with <code>-Wall</code> triggers a warning about a
|
||
strange-looking comment.</p>
|
||
<h3 id="behind-the-scenes-commentary">Behind-the-scenes commentary:</h3>
|
||
<p><a href="https://crypto.stanford.edu/~blynn/compiler/ioccc.html">My website reveals how this compiler
|
||
works</a>.</p>
|
||
<!--
|
||
|
||
Copyright © 1984-2024 by Landon Curt Noll. All Rights Reserved.
|
||
|
||
You are free to share and adapt this file under the terms of this license:
|
||
|
||
Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
|
||
|
||
For more information, see:
|
||
|
||
https://creativecommons.org/licenses/by-sa/4.0/
|
||
|
||
-->
|
||
<!-- AFTER: last line of markdown file: 2019/lynn/README.md -->
|
||
|
||
<!-- END: this line ends content for HTML phase 21 by: bin/pandoc-wrapper.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content for HTML phase 22 by: bin/output-index-inventory.sh via bin/md2html.sh -->
|
||
|
||
<!-- START: this line starts content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<div id="inventory">
|
||
<h1 id="inventory-for-2019lynn">Inventory for 2019/lynn</h1>
|
||
</div>
|
||
<h2 id="primary-files">Primary files</h2>
|
||
<ul>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/prog.c">prog.c</a> - entry source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/Makefile">Makefile</a> - entry Makefile</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/prog.orig.c">prog.orig.c</a> - original source code</li>
|
||
<li><a href="example-1.txt">example-1.txt</a> - sample input</li>
|
||
<li><a href="example-2.txt">example-2.txt</a> - sample input</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/try.sh">try.sh</a> - script to try entry</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/fib.hs">fib.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/ghcfib.hs">ghcfib.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/ghclol.hs">ghclol.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/ghcscc.hs">ghcscc.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/lol.hs">lol.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/scc.hs">scc.hs</a> - example Haskell input source code</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/hint.hs">hint.hs</a> - self-hosting compiler stage output</li>
|
||
</ul>
|
||
<h2 id="secondary-files">Secondary files</h2>
|
||
<ul>
|
||
<li><a href="2019_lynn.tar.bz2">2019_lynn.tar.bz2</a> - download entry tarball</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/README.md">README.md</a> - markdown source for this web page</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/.entry.json">.entry.json</a> - entry summary and manifest in JSON</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/.gitignore">.gitignore</a> - list of files that should not be committed under git</li>
|
||
<li><a href="https://github.com/ioccc-src/winner/blob/master/2019/lynn/.path">.path</a> - directory path from top level directory</li>
|
||
<li><a href="index.html">index.html</a> - this web page</li>
|
||
</ul>
|
||
<hr style="width:10%;text-align:left;margin-left:0">
|
||
<h4>
|
||
Jump to: <a href="#">top</a>
|
||
</h4>
|
||
|
||
<!-- END: next line ends content generated by: bin/output-index-inventory.sh -->
|
||
|
||
<!-- END: this line ends content for HTML phase 22 by: bin/output-index-inventory.sh via bin/md2html.sh -->
|
||
<!-- START: this line starts content from: inc/after-content.default.html -->
|
||
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/after-content.default.html -->
|
||
<!-- START: this line starts content from: inc/footer.inventory.html -->
|
||
|
||
<!--
|
||
|
||
Copyright © 1984-2025 by Landon Curt Noll. All Rights Reserved.
|
||
|
||
You are free to share and adapt this file under the terms of this license:
|
||
|
||
Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)
|
||
|
||
For more information, see:
|
||
|
||
https://creativecommons.org/licenses/by-sa/4.0/
|
||
|
||
-->
|
||
|
||
<div class="footer">
|
||
|
||
<div id="copyright"><h3>Copyright © 1984-2025 by Landon Curt Noll:
|
||
<a href="https://creativecommons.org/faq/#what-does-some-rights-reserved-mean"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">Some Rights Reserved</a></h3>
|
||
<p>
|
||
This work is <b>licensed by Landon Curt Noll</b> under
|
||
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/?ref=chooser-v1"
|
||
target="_blank"
|
||
rel="license noopener noreferrer"
|
||
style="display:inline-block;">CC BY-SA 4.0</a></b>.
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/cc.png"
|
||
alt="cc inside circle symbol">
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/by.png"
|
||
alt="person inside circle symbol">
|
||
<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;"
|
||
src="../../png/sa.png"
|
||
alt="arrow looping back on itself inside circle symbol"><br>
|
||
You should <b>carefully review</b> the
|
||
<b><a href="https://creativecommons.org/licenses/by-sa/4.0/legalcode.en"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">CC BY-SA 4.0 LEGAL CODE</a></b>
|
||
before using the licensed material.<br>
|
||
You may wish to review the
|
||
<b><a href="../../license.html"
|
||
target="_blank"
|
||
rel="license noopener noreferrer">highlights of some of the key features and terms</a></b>
|
||
of <b>CC BY-SA 4.0</b>.<br>
|
||
</p>
|
||
</div>
|
||
|
||
<div id="coda"><h3>Coda</h3>
|
||
<p>
|
||
<a href="https://validator.w3.org/nu/?doc=https%3A%2F%2Fwww.ioccc.org%2F2019%2Flynn%2Findex.html" rel="nofollow">Nu HTML check this web page</a><br>
|
||
<a href="#top">Jump to top</a> <a href="#content">Jump to Content</a> <a href="#inventory">Jump to Inventory</a><br>
|
||
</p>
|
||
</div>
|
||
|
||
</div>
|
||
|
||
<!-- END: this line ends content from: inc/footer.inventory.html -->
|
||
<!-- START: this line starts content from: inc/bottom.default.html -->
|
||
|
||
</body>
|
||
</html>
|
||
|
||
<!-- END: this line ends content from: inc/bottom.default.html -->
|