Talk:Smallfuck

Here's the problem, as it seems to me ...

Defining Smallfuck as a "sized-down" Brainfuck, with an implementation-defined bound on the length of the memory bit-array, does *not* imply that the array-length is unbounded in the memory model. (Brainfuck itself is ambiguous on this point, and only its versions with unbounded memory -- either unbounded strorage per cell or unbounded array-length, or both -- are Turing complete.)

So its stated definition does not assure that Smallfuck can be compared to languages with memory bit-arrays of unbounded length -- which are necessary for Turing completeness. (Boolfuck is one such, and so is the F language described at http://r.s.home.mindspring.com/F/)

--r.e.s. (r dot s at mindspring dot com)

That the array-length is unbounded was supposed to be implied. I made it explicit. --Graue 12:29, 22 Jun 2005 (GMT)

Explicit is better, imo. Thanks for the response. --r.e.s.

By the way, there's already an F programming language. --Graue 12:32, 22 Jun 2005 (GMT)

Right, it's in the FORTRAN family. Perhaps eventually I'll come up with a more-distinguished name for the esoteric F language; meanwhile, there's quite a lot of material on the latter (as can be seen at my website), and confusion seems unlikely in context -- it's a pretty sure bet that no one is going to confuse FORTRAN with Brainfuck ;o) --r.e.s.

Actually you're all wrong, it is implied that the memory is bounded, and therefore smallfuck is not turing-complete. I guess I should make that explicit. lament

The issue is whether this language involves an abstract computational model, with unbounded memory in that *abstract* model. If this language is not based on such an abstraction, then of course it cannot be Turing complete. (I had suspected the latter in my original posting, but the response to it explicitly stated that memory is intended to be unbounded, which I took as referring to such an abstract model. --r.e.s.

I'd always thought it was supposed to be unbounded in the abstract model, and it was just the Smallfuck -> SMETANA implementation that didn't live up to this. Thanks for clarifying. --Graue 03:12, 24 Jun 2005 (GMT)

In your original announcement, you said that "If we forget about the memory size limits (which we do for Brainfuck anyway), Smallfuck is Turing-complete - if only because it's quite trivial to port Brainfuck programs to Smallfuck (without IO, of course)." Why the change in opinion? --Graue 21:49, 27 Jun 2005 (GMT)

Because the only reason Smallfuck exists is to be compiled into SMETANA. All the weird details in the specification (e.g. "if the pointer goes to the left of origin, the program terminates normally") are just conforming, post-facto, to the behaviour of the smallfuck->smetana compiler :). So I think it makes sense to have Smallfuck be equal in power to SMETANA. Otherwise, you could say "Sure, I can compile Smallfuck to SMETANA but I will lose Turing-completeness in the process". This way, nothing is lost. The mystical usefulness, whatever it is, is still there. lament

But is this "usefulness" also present in lookup tables?

I think the Smallfuck-to-lookup-table compiler is a pretty convincing demonstration of Smallfuck (and consequently SMETANA)'s computational power. The thing is that "the tape is bounded" plus "input is on the tape" means "the input is bounded". This is more restricted than even a finite-state automaton, which can receive an unbounded amount of input over its lifetime... and this restriction leads to the property that the whole thing can be enumerated into a lookup table.

This suggests to me that Smallfuck programs are "just compressed lookup tables", and consequently, lookup tables are "useable for computation"! The same applies to SMETANA, except I'm not even sure if SMETANA programs manage to be all that compressed! --Chris Pressey 15:23, 29 Jun 2005 (GMT)

Smallfuck vs. Brainfuck F

I've mentioned Brainfuck F as an abstract computational model defined by changing Smallfuck to presume unbounded memory cells. I think this is correct (and fair); feel free to fix if it isn't. --Graue 23:28, 26 Jun 2005 (GMT)

That does seem to me to somewhat misrepresent Brainfuck F, which includes options not found in Smallfuck; e.g., memory need not be left-bounded, and unmatched brackets may be allowed. Also, I should mention that I defined F independently of Smallfuck and posted quite a bit of material about it in Jan.2004 (some is archived in Google Groups on comp.theory in the thread "Is Binary BrainF*** Turing-complete?"). At the time, I was unable to locate any relevant discussions of such a minimalistic Brainfuck -- Smallfuck or otherwise. Were there earlier postings on Smallfuck somewhere that I hadn't found?

--r.e.s. (r dot s at mindspring dot com)

You can find the Smallfuck announcement in the list archive.

It didn't look to me like your changes were enough to make Brainfuck F a new language, but I guess the behavior you selected for unmatched brackets is a bit interesting. If you want to make a wiki article on it, feel free. --Graue 21:18, 27 Jun 2005 (GMT)

Having just read the Smallfuck material in the list archive, it seems clear that what I've been calling "F" is just a natural Turing-complete extension (or family of extensions) to Smallfuck. I will edit the external link accordingly.

--r.e.s. (r dot s at mindspring dot com)

After looking again at the list archive, I'm afraid I made some ill-advised edits of the Smallfuck content page. I found the archive description confusing, as it states that Smallfuck has no i/o, but isn't clear imo that that only refers to i/o *commands*. Anyway, my apologies for the too-hasty edits -- I will try to restore the page, and will defer to "lament" or others to do the editing there, if any.

--r.e.s. (r dot s at mindspring dot com)

True, it has no I/O commands. But it doesn't have any memory-mapped I/O either. In fact there is no way to cause I/O to occur, from within a program... and it seems reasonable to me to describe this state of affairs as "having no I/O". Do you feel differently? --Chris Pressey 15:28, 29 Jun 2005 (GMT)

Because the abstract machine-model for Smallfuck is not well-defined imo, the meaning of i/o is likewise not well-defined. The list archive mentions a case where "all memory cells are initially filled with zeroes, but for debugging purposes can be filled with any information (which is how arguments might be passed to the program). Again, this is not really a part of the language specification." This "passing of arguments" is what I would call i/o in an appropriate abstract machine-model (such as the one I use for Smallfuck/F). In the latter model, the bit-string is entirely analogous to the tape of a TM -- and i/o occurs by interpreting the initial & final tape/memory.

--r.e.s. (r dot s at mindspring dot com)

We do consider Kipple to have I/O, even though it has no I/O commands or a way to cause I/O to occur from within a program. Perhaps a better way to make the distinction is to ask whether the language itself specifies I/O, and not whether it is possible for an implementation to provide that capability. --Graue 21:59, 29 Jun 2005 (GMT)

The Kipple spec says "When a Kipple program ends the contents of stack o are written to output." That sounds like a way to cause I/O to occur from within the program, to me.

Also, re Smallfuck - if the "this" in "this is not really a part of the language specification" refers to the entire preceding sentence, then it looks like Smallfuck leaves the initial state of the tape undefined (which is somewhat interesting in a pathological sort of way.)

At any rate, I agree that I/O isn't defined for Smallfuck (and some other languages.) The question is, is it a reasonable to assume from that, that there is "no I/O" in the language (at least for categorization purposes?) I would say so (e.g. I think it's reasonable to assume that Befunge contains "no elephants", even though there's nothing in the spec that forbids elephants, in fact they're never mentioned in it...)

I would also argue that it's always possible for an implementation to provide output in some form, except maybe for a pathological language that specifies that programs cannot produce any output... --Chris Pressey 22:28, 29 Jun 2005 (GMT)

The point is that explicit i/o commands are not needed for i/o to be produced *if* the abstract machine-model is designed that way -- e.g., like a TM, allowing memory to act as a tape that can be pre-initialised with input before a computation, and to be observable for ouput afterwards. In that case, the Smallfuck- or F-command that flips a bit is potentially an "implicit" output command, because it modifies the tape/memory that may eventually be observable (after halting). Implementations are quite another matter.

--r.e.s. (r dot s at mindspring dot com)

You're missing Chris's point. "The point is that explicit elephant commands are not needed for elephants to be produced *if* the abstract machine-model is..." Yes, it's potentially an implicit output command, but that is part of the implementation, not the language. --Graue 01:01, 30 Jun 2005 (GMT)

No. It's potentially an "implicit" output command in the abstract model. As I said, implementations are another matter.

--r.e.s. (r dot s at mindspring dot com)

There's quite a few things I'm not really getting here. Does "No I/O" mean "the language does not define I/O" or does it mean "the language defines that there shall be no I/O"? Is there really any need for a category for the latter definition? Also, what is the difference between an "abstract model" and a programming language?? --Chris Pressey 04:58, 30 Jun 2005 (GMT)

In my opinion, "no I/O" means "no separate, dedicated streams for input and output". That does not mean that there's no input/output possible; in a Smallfuck program, for example, preloading the tape may be a means of input, and considering the tape contents at the end may be a means of output. Other considerations are possible; for example, in some UTMs the virtual tape may be interleaved with the machine, so skipping the virtual TM's machine definition part may be needed for considering what is output. --pgimeno 07:33, 30 Jun 2005 (GMT)

It seems you're asking me about someone else's usage of the expression "no i/o" -- I don't use the expression myself, except in the more precise "no i/o instructions". As for your last question, you're asking how a programming language differs from an abstract model, whereas the distinction I was making is between an abstract model and implementations of that model.

--r.e.s. (r dot s at mindspring dot com)

They were general questions, not directed specifically at you. The term "No I/O" is used as a category on this wiki, and it's obvious there's (at least some) contention/confusion as to what it means. I mentioned "abstract model" because it seems to come up a lot on this page (sometimes in contrast to implementations and sometimes in contrast to programming languages,) and I need some clarification on the term before I can reason about statements that use it.

My own opinion on what to do is this: a) change descriptions re Smallfuck's I/O to say that "Smallfuck does not define any I/O", which is true, and more precise than saying it has "No I/O". b) Move discussion about the meaning of "No I/O" to Category talk:No IO. c) Make a seperate entry for Brainfuck F; even trivialler variations on Brainfuck have their own entries, so there's absolutely no reason Brainfuck F shouldn't have one. --Chris Pressey 19:07, 30 Jun 2005 (GMT)

To clarify, the proper page would actually be Category talk:No IO (lowercase t, no slash). --Graue 02:55, 1 Jul 2005 (GMT)

Binary counter

>*[[>]*<[<*]>*]

--(this comment by 123.113.49.39 at 09:13, 6 August 2015‎ UTC; please sign your comments with ~~~~)

That seems to fall off the left hand end. Perhaps this is what you're looking for ?

*[ # *>[>]*<[*<] # *]

The `#` characters mark where the "tape" is the incrementing binary number. Rdebath (talk) 20:14, 6 August 2015 (UTC)

Interpreter

I think this is an interpreter for Smallfuck. Is there anything wrong with it?

def run_sf(code: str, textfile=False) -> None:
    pointer = 0  # for instructions
    location = 0  # for tape
    tape = [0] * int(input('Indicate the number of cells in the tape:'))
    assert len(tape) > 0, 'The length of the tape must be greater than 0.'

    if textfile:
        code = ''.join(open(f'{code}', 'r').readlines())

    corresponding_bracket = {}  # dictionary where the values are the corresponding bracket positions of the keys
    bracket_stack = []  # acts as a stack for the last bracket
    for num, char in enumerate(code):
        if char == '[':
            bracket_stack.append(num)
        elif char == ']':
            assert len(bracket_stack) > 0, 'unmatched ]'
            corresponding_bracket[num] = bracket_stack[-1]
            corresponding_bracket[bracket_stack[-1]] = num
            bracket_stack.pop()
    assert len(bracket_stack) == 0, 'unmatched ['

    while pointer < len(code):
        if code[pointer] == '>':
            location += 1
            assert location < len(tape), f'The > at location #{pointer} moves the tape too far right.'
        elif code[pointer] == '<':
            assert location > 0, f'The < at location #{pointer} moves the tape too far left.'
            location -= 1
        elif code[pointer] == '*':
            tape[location] = (tape[location] + 1) % 2
        elif code[pointer] == '[':
            if tape[location] == 0:
                pointer = corresponding_bracket[pointer]
        elif code[pointer] == ']':
            if tape[location] != 0:
                pointer = corresponding_bracket[pointer]
        pointer += 1