Shameless Promotion of LISP - FOR KIDS!
-
@flabdablet said in Shameless Promotion of LISP - FOR KIDS!:
If it means not-proven then fair enough.
I'm intending it to mean “this software has no idea” and nothing more. “Not provable” is at least as hard as proving termination.
-
@dkf There are certain cases for which
not-provable
should be fairly easy to demonstrate. For example, the canonical this-only-terminates-if-it-doesn't quine should be possible to analyze for.Programs that only terminate if P != NP would be harder.
-
@flabdablet said in Shameless Promotion of LISP - FOR KIDS!:
Programs that only terminate if P != NP would be harder.
I was actually thinking about the Riemann Hypothesis as a “fun” thing to depend on. ;)
-
@masonwheeler said in Shameless Promotion of LISP - FOR KIDS!:
asking it to perform an operation equivalent to computing the truth value of
this sentence is false
.This is why we shouldn't pass by reference, right?
-
@dkf My recollection is that the rightmost columns of the card were reserved for a sequence number. That way, if you dropped the stack on the floor you could put them through a sorter and put things to rights.
Not that I bothered with sequence numbers or had access to a sorter. Boy, was that a pain.
-
@dkf Those programs were just recently written.
Today, I’m proud to announce that Adam Yedidia, a PhD student at MIT (but an MEng student when he did most of this work), has explicitly constructed a one-tape, two-symbol Turing machine with 7,918 states, whose behavior (when run on a blank tape) can never be proven from the usual axioms of set theory, under reasonable consistency hypotheses. Adam has also constructed a 4,888-state Turing machine that halts iff there’s a counterexample to Goldbach’s Conjecture, and a 5,372-state machine that halts iff there’s a counterexample to the Riemann Hypothesis.
In a followup post, http://www.scottaaronson.com/blog/?p=2741, they (including the commenters), improved these to:
- Halt if ZFC is inconsistent: 1919 states
- Halt if there is a counterexample to the Riemann hypothesis: 744 states
- Halt if there is a counterexample to the Goldbach conjecture: 43 states (27 unverified)
-
@Greybeard By the time I was using computers, terminals were a thing and were evolving towards PCs and workstations.
-
@dkf said in Shameless Promotion of LISP - FOR KIDS!:
@groo said in Shameless Promotion of LISP - FOR KIDS!:
"C strings" may be the worst thing ever on the story of computing
The original Pascal strings were contenders for that too. Having the length and the string together is great, but only using one byte for it?
You know not whereof you speak. Wirth's original Pascal strings were 'packed array[1..N] of char', where N is a compile-time constant (more or less, with some exceptions for the so-called "conformant" arrays), that is, they were fixed-length. The ones with a pre-posed length byte were introduced by UCSD Pascal and given widespread use by Turbo Pascal, especially 3.0.
-
@Steve_The_Cynic Crap, I'd forgotten about that; that was still the case in the version of Turbo Pascal (2.3, I think) I first learned in college, and everyone bitched about it. The
Text
type was so ubiquitous later that it was easy to forget that it wasn't in the original language itself.Which also means my whole argument earlier was a lot of crap, since that wasn't introduced until much later. Fuck.
-
@Steve_The_Cynic said in Shameless Promotion of LISP - FOR KIDS!:
Wirth's original Pascal strings were 'packed array[1..N] of char'
OK, that's definitely worse. Suddenly the way C does strings doesn't look quite so miserably terrible. Of course, you do something else than either of the above if you're serious about strings — C++ gets much closer with
std::string
— but C was always pretty cool about people going off and doing their own thing; the language pretty much encourages it.
-
@dkf I quite liked Applesoft BASIC's approach to strings.
The value of a string variable was just a 3 byte descriptor, consisting of a 1 byte length and a 2 byte pointer into a text pool. This made all the substring operators super-cheap, though concatenation was still relatively expensive - as was garbage-collecting the pool, which happened whenever the initial attempt to allocate a new string at the free end failed. You could also trigger garbage collection explicitly, giving you some control over when your code would hiccup.
The 255-character maximum string length wasn't super-awful given that the whole of free RAM was typically well under 32K.
-
@flabdablet That was probably what I was thinking of, rather than Pascal. I don't know about @dkf.
-
@ScholRLEA I've dealt with various string implementations over the years, and it wasn't until I dealt with systems that had lots of memory and used separate 4-byte measures for the length and the size of the buffer that they didn't suck. These days, I'd look for 8-byte measures :) but otherwise it's the same idea.
The single-byte-length strings were very limiting once you got into doing real text processing work. Especially if a brainiac decided to use the upper bit of the byte for something else “since who would want a string longer than 127 characters?” C strings were just slow an unsafe, but at least didn't limit you to piddly small sizes. (I don't think I ever used anything quite like the Applesoft Basic, or if I did, I didn't know.)
-
@flabdablet said in Shameless Promotion of LISP - FOR KIDS!:
@dkf I quite liked Applesoft BASIC's approach to strings.
The value of a string variable was just a 3 byte descriptor, consisting of a 1 byte length and a 2 byte pointer into a text pool. This made all the substring operators super-cheap, though concatenation was still relatively expensive - as was garbage-collecting the pool, which happened whenever the initial attempt to allocate a new string at the free end failed. You could also trigger garbage collection explicitly, giving you some control over when your code would hiccup.
The 255-character maximum string length wasn't super-awful given that the whole of free RAM was typically well under 32K.
That was typical of 8-bit micro Basic interpreters, although it was also the case in the Basic provided for the original IBM PC. (I'm making a possibly artificial distinction between micros like the 6502, 6809, and Z-80 and the 16-bit-ish 8088 on the PC.)
I read somewhere about a program that someone wrote for the Commodore 64 which would trigger the string garbage collector, and get it to run a cycle of garbage collection that lasted ten minutes. It was mentioned in the context of the Commodore 128, which had that behaviour in its C64 mode, but in its native mode, would happily run the same source code with no garbage collection at all.
EDIT: the program was something about concatenating empty strings, producing many thousands of pieces of "garbage" that the GC would collect one at a time. The process is at least as slow as O(n**2) where n is the number of pieces of garbage, and possibly slower, more like O(m*(n**2)) where n is as before and m is the number of string variables.
-
@Greybeard said in Shameless Promotion of LISP - FOR KIDS!:
@dkf My recollection is that the rightmost columns of the card were reserved for a sequence number. That way, if you dropped the stack on the floor you could put them through a sorter and put things to rights.
Not that I bothered with sequence numbers or had access to a sorter. Boy, was that a pain.
That's the FORTRAN way. Column 1: C for comment. Columns 1-5: statement number if no C in column 1. Column 6: "continuation" marker saying that this line is a continuation of the line above. Columns 73+: ignored because "the IBM 704's card reader only used 72 columns".
-
@Steve_The_Cynic said in Shameless Promotion of LISP - FOR KIDS!:
O(n**2)
<sup>
is your friend. O(n2)
-
@dkf Or unicode
O(n²)
-
@anonymous234 Yes, but then you have problems doing O(2m×n)… ;)
-
@dkf You mean O(2ᵐˣⁿ)? Or maybe 2ₘₓₙ?
-
-
@anonymous234 You do realise that I can just find more symbols to stuff up there? O(2⌊{x:ξ→ζx}⌋).
No, I have no idea what that might mean.
-
@dkf And I can call the Unicode consortium and say "Emergency! There's a symbol that's NOT included in unicode!" and they'll sound the red alert and add it (along with 500 other random ones, 50 emojis, and 3 new encoding schemes).
-
@anonymous234 Then I'll just put your new characters in a
<sup>
… :p
-
@anonymous234 said in Shameless Promotion of LISP - FOR KIDS!:
There's a symbol that's NOT included in unicode!
Can't be. I thought that they exhausted all possibiliti🇪🇸 when they started adding combinations of existing symbols. Clearly they're out of i🇩🇪as.
-
@eskel said in Shameless Promotion of LISP - FOR KIDS!:
i🇩🇪as
DYM "?"ıpǝɐs
Filed under: We need a new tag cloud attack
-
@aliceif He's Australian?!
-
I love it, how the 'regional indicator symbol letter ...' code points are there only for some countries and without any sane ordering. They can now add all combinations of two latin characters and claim that the regional indicators are now future proof.
via bash.org:
<i8b4uUnderground> d-_-b
<BonyNoMore> how u make that inverted b?
<BonyNoMore> wait
<BonyNoMore> never mind
-
@dkf said in Shameless Promotion of LISP - FOR KIDS!:
@anonymous234 Then I'll just put your new characters in a
<sup>
… :pDude, what
<sup>
?
-
@FrostCat said in Shameless Promotion of LISP - FOR KIDS!:
@dkf said in Shameless Promotion of LISP - FOR KIDS!:
@anonymous234 Then I'll just put your new characters in a
<sup>
… :pDude, what
<sup>
?<sup> for the 's soul?
-
@FrostCat said in Shameless Promotion of LISP - FOR KIDS!:
Dude, what
<sup>
?Double the fun once you realise that your DOM has
<sub>
too…
-
@dkf Call me oldfashioned, but it's hard to beat ANL and ORL.
-
@dkf said in Shameless Promotion of LISP - FOR KIDS!:
@FrostCat said in Shameless Promotion of LISP - FOR KIDS!:
Dude, what
<sup>
?Double the fun once you realise that your DOM has
<sub>
too…TIL that NodeBB's API is a switch.
-
@Maciejasjmj said in Shameless Promotion of LISP - FOR KIDS!:
Goddamned rich spoiled brats. When I was a wee little lad, all we had was BASIC and we liked it. Line numbers taught you discipline - want to insert more than 10 lines of code in the middle of your program? Too bad, you should've thought of that the first time around!
RENUM FTW.
-
@OffByOne said in Shameless Promotion of LISP - FOR KIDS!:
RENUM FTW.
That didn't work so well when you used a non-trivial expression to compute the link to GOSUB to…
-
@Yamikuronue said in Shameless Promotion of LISP - FOR KIDS!:
@Jaloopa Then you'd probably want to go with a robot metaphor. Robots are cool enough they might stave off the inevitable brain death, and you can draw cute little cartoon robot guys saying "JMP" and then a little kid saying "How high?" and it'd be adorable.
Do you mean something like
-
@OffByOne Little Inferno was amazing.
It spends most of its time being kind of a amusing but not revolutionary casual game about burning shit in a fireplace, but then has this incredibly beyond-description final 30 minutes that's sad, joyful, scary, ... amazing.
I want to replay it now you bastard.
-
@blakeyrat said in Shameless Promotion of LISP - FOR KIDS!:
@OffByOne Little Inferno was amazing.
It spends most of its time being kind of a amusing but not revolutionary casual game about burning shit in a fireplace, but then has this incredibly beyond-description final 30 minutes that's sad, joyful, scary, ... amazing.
I want to replay it now you bastard.
Any chance that you'll put your replay on YouTube?
-
@OffByOne If you're even slightly interested, you should play it yourself. It's not expensive, it's the some of the best entertainment money you'll ever spend.
-
@blakeyrat Thanks for the tip.