Bill Pragnell wrote:
> Cool, I thought it might be something like that. Not that esoteric if you're a
> proper computer scientist! Me, I'm just a humble code monkey :)

Oh, it's probably esoteric even for a computer scientist. I just happened to 
do my research on these kinds of formally-specified computer languages.

-- 
Darren New, San Diego CA, USA (PST)
  "How did he die?"   "He got shot in the hand."
     "That was fatal?"
          "He was holding a live grenade at the time."

Post a reply to this message

>> Nope, I have no frame of reference so it's meaningless to me.
>
> Upper case is function names, lower case is arguments, -> is "returns".

More specifically, "->" means "this [eventually] becomes that". Rather 
like an equals sign. You might write

   2+3+4 = 5+4 = 9

Or you might just write

   2+3+4 = 9

without showing the intermediate step(s).

> Ix->x means there's a function I that takes an argument and returns it -
> identity.
>
> Kxy -> x - K takes two arguments and returns the first. (This is the "K
> combinator" or something that some famous venture capitalist named his
> company after.)
>
> Sfgx -> (fx)(gx) - Given functions f and g, apply f to x and g to x, and
> then apply the result of the first call (which is a function) the the
> result of the second call. I think.

Together, they form "the SKI combinator calculus". (Because a function 
having certain technical properties that I won't bore you with now is 
called a "combinator".)

Absurdly, the SKI calculus is Turing-complete. Yes, I know, it makes no 
sense at all. But if you can find a way to transform data into functions 
and functions back into data, then you can write SKI functions which 
turn inputs into outputs, computing any possible computable thing. (It's 
a bit like the way a normal computer can compute anything, provided you 
turn the data into binary first, and turn the resulting binary back into 
whatever.)

> Continue from there.

The X combinator, more usually written as the Greet letter Iota, forms 
the "Iota calculus". X takes a function as argument and passes it S and 
K as arguments. As I just demonstrated, the net result of doing that is 
that X(XX) is equal to K, X(X(XX)) is equal to S, and X(X(X(XX))) is 
equal to I. And we already know that once you have S, K and I, you have 
the SKI calculus, and it's Turing-complete.

So the Iota calculus is *also* Turing-complete. Despite having only 1 
data value (X) and one operator (function calls). This makes the Iota 
calculus arguably the simplest possible Turing-complete language. It 
also makes programs written in the Iota calculus INSANELY VERBOSE! 
Writing a program in this language is so hard, you could literally go 
mad trying. (It's what is colloquially known as a Turing Tarpit...)

> This is all normal "how to define a programming language formally" sorts
> of stuff. There are actual (obviously specialized) programming languages
> (like LOTOS) that you write this way.

It's easier to start from the Lambda calculus. But the SKI calculus is 
quicker to explain in a hurry.

Needless to say, all of these languages are interesting mostly from a 
"oh hey, you can invent an entire programming language with just three 
rules" standpoint. You wouldn't actually *use* them in real life.

Having just said that, Haskell is the lambda calculus with bells on.

Post a reply to this message

Invisible wrote:
>>> Nope, I have no frame of reference so it's meaningless to me.
>>
>> Upper case is function names, lower case is arguments, -> is "returns".
> 
> More specifically, "->" means "this [eventually] becomes that". 

True. My bad. Or, another way to read it is "can be replaced with".

-- 
Darren New, San Diego CA, USA (PST)
  "How did he die?"   "He got shot in the hand."
     "That was fatal?"
          "He was holding a live grenade at the time."

Post a reply to this message