5

I'm learning about lazy functional language evaluation and came across the STG machine. In order to understand it I'm building a small toy compiler for a functional language (to STG).

However there's one thing I can't really wrap my head around: according to the 1992 paper, an stg expression is either: a let binding, a case expression, an application, a constructor, a built-in operation or an unboxed literal.

Therefore if I have a program which just uses a variable, not invokes it, it must still compile to an application, because there's no "var" option in the stg expression variants (page 20 in the paper). For example:

id x = x

compiles to

id = {} \ {x} -> x {}  # application with no arguments

But, what if this id function expects a primitive value? (id :: Int# -> Int#) It can't compile to an application, because you can't "enter" a primitive value, but there's no other option?

Thanks very much

(Edit: link to the paper I'm referring to)

lav_shaun
  • 81
  • 1
  • 4
  • The linked paper references yet another paper titled "Unboxed values as first class citizens in a non-strict functional language" which might shed further light on the question: https://www.microsoft.com/en-us/research/publication/unboxed-values-as-first-class-citizens/ – danidiaz Jan 17 '22 at 13:42

1 Answers1

3

The paper cited distinguishes entering a primitive value from a closure. Your suggested compilation consisting of the application of the primitive to zero arguments is correct. The STG machine is defined to only enter the "function" part of an application if that value is a pointer to a closure (i.e. an Addr) (section 5.2, rule 1). In the case that it is not a pointer, but a primitive value, that rule doesn't apply and a different one (section 5.5, rule 10) causes the primitive value to be returned.

HTNW
  • 27,182
  • 1
  • 32
  • 60